一、每日温度问题

题目: 根据每日气温列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置0来代替。例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

1.1 暴力算法

当拿到这个题目时，首先想到的是暴力算法，即用两层循环遍历。第一层循环遍历[0,n-1]个字符，第二层循环[1,n]个字符，依次比较每个字符。

实现方法

int  *dailyTemperatures_1(int* T, int TSize, int* returnSize){
    int* res = (int*)malloc(TSize*sizeof(int));
    for(int i = 0; i<TSize-1; i++){
        if(i>0 && T[i] == T[i-1]){
            res[i] = res[i-1] == 0?0:res[i-1]-1;
        }
        else{
            for(int j = i+1;j<TSize;j++){
                if(T[j]>T[i]){
                    res[i] = j-i;
                    break;
                }
                else{
                    res[i] = 0;
                }
            }
        }
    }
    *returnSize = TSize;
    return res;
}

暴力算法的算法复杂度为O(n^2)；
为了减少比较次数，采用跳跃对比的思路。

1.2 跳跃对比

跳跃对比的思路：
假设原数据为：73, 74, 75, 71, 69, 72, 76, 73
1、从右到左遍历。因为最后一天的气温不会再升高，默认等于0；
2、i 从[TSize-2,0]；从倒数第二天开始遍历比较。每次减一；
3、j 从[i+1,TSize]遍历，j+=result[j]，可以利用已经有结果的位置进行跳跃，从而减少遍历次数。
当计算71之后多少天温度长高时，因为71>69，则71可直接找到比69大的位置开始比较，即72的位置开始比较。
当计算75之后多少天温度长高时，因为75>71，则直接将j定位至比71大的位置，即72的位置，此时75>72，则又直接将j定位至比72大的位置，即76的位置。
因此跳跃算法中重点的语句是j+=result[j]，通过这种跳跃的方式减少比较次数，从而达到优化的目的。

实现方法

int  *dailyTemperatures_2(int* T, int TSize, int* returnSize){
    int* res = (int*)malloc(TSize*sizeof(int));
    res[TSize-1] = 0;
    int i, j;
    for(i = TSize -2; i>=0; i--){
        for(j = i+1; j<TSize; j+=res[j]){
            if(T[i]<T[j]){
                res[i] = j-i;
                break;
            }
            else{
                if(res[j] == 0){
                    res[i] = 0;
                    break;
                }
            }
        }
    }
    * returnSize =TSize;
    return res;
}

1.3 栈思想

算法思路：
1、将第一个元素的索引入栈。
2、将第二个元素T[i]与栈顶记录的索引index[top]所对应的元素进行对比。
T[i]小于或等于T[index[top]]，则继续将T[i]的索引入栈。
T[i]大于T[index[top]]，说明找到了大于T[index[top]]的温度，结果为索引差，res[index[top]] = i-index[top];
注意，保存完结果之后需要继续判断当前栈是否为空。
如果此时栈为空，则将T[i]入栈；
如果栈不为空，那么T[i]还需要继续和栈顶值所对应的温度比较，直至栈为空。

实现方法

int* dailyTemperatures_3(int* T, int TSize, int* returnSize) {
    * returnSize =TSize;
    int* res = (int*)calloc(TSize, sizeof(int));
    int* index = (int*)malloc(TSize*sizeof(int));
    int top = -1;
    index[++top] = 0;
    int i = 1;
    while(i<TSize){
        if(T[i]>T[index[top]]){
            res[index[top]] = i-index[top];
            top--;
            if(top == -1){
                index[++top] = i;
                i++;
            }
        }
        else{
            index[++top] = i;
            i++;
        }
    }
    
    return res;
}

总结：
由上面的对比可以看出，暴力算法比较次数最多，栈思想比较次数最少。以后此类问题（来回比较、进进出出等）都可采用栈思想进行优化。

二、杨辉三角

题目：给定一个非负整数numRows，生成杨辉三角的前numRows行。

image
在杨辉三角中，每个数是它左上方和右上方的数的和。

这里引入一个概念：动态规划法。

动态规划法

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。

基本思想与策略编辑:

由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。
首先是拆分问题，我的理解就是根据问题的可能性把问题划分成一步一步这样就可以通过递推或者递归来实现。关键就是这个步骤,动态规划有一类问题就是从后往前推到，有时候我们很容易知道:如果只有一种情况时,最佳的选择应该怎么做。然后根据这个最佳选择往前一步推导，得到前一步的最佳选择。
然后就是定义问题状态和状态之间的关系,我的理解是前面拆分的步骤之间的关系，用一种量化的形式表现出来，类似于高中学的推导公式，因为这种式子很容易用程序写出来，也可以说对程序比较亲和(也就是最后所说的状态转移方程式)。
最后找到最优解，我们应该讲最优解保存下来,为了往前推导时能够使用前一步的最优解，在这个过程中难免有一些相比于最优解差的解，此时我们应该放弃，只保存最优解，这样我们每一次都把最优解保存了下来，大大降低了时间复杂度。
虽然这一算法非常简单，但用于构造杨辉三角的迭代方法可以归类为动态规划，因为我们需要基于前一行来构造每一行。
1、拆分问题：在杨辉三角中，每一行都可以通过前一行进行递推。
2、定义问题状态和状态之间的关系：每一行中除了第一个和最后一个元素，其它元素都是前一行对应位置的元素各。
3、最优解：res[i][j] = res[i-1][j-1]+res[i-1][j];

代码实现

int** generate(int numRows, int* returnSize, int** returnColumnSizes){
    *returnSize = numRows;
    *returnColumnSizes = (int*)malloc(numRows * sizeof(int));
    int **res = (int **)malloc(sizeof(int*)*numRows);
    
    for(int i = 0; i < numRows; i++){
        (*returnColumnSizes)[i]=(i+1);
        res[i] = (int *)malloc(sizeof(int)*(i+1));
        res[i][0] = res[i][i] = 1;
        for(int j = 1; j < i; j++){
            res[i][j] = res[i-1][j-1]+res[i-1][j];
        }
    }
    return res;
}

总结：在杨辉三角问题中，使用动态规划法的空间复杂度为：O(numRows^2)。因为我们需要存储我们在 triangle 中更新的每个数字，所以空间需求与时间复杂度相同。

三、爬楼梯问题

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有 多少种不不同的⽅方法可以爬到楼顶呢?注意:给定 n 是⼀一个正整数

爬楼梯问题是典型的递归问题，但递归空间复杂度相对较高，当爬楼梯的阶数较大时，递归就不适用了。
下面我们分别用递归和动态规划来实现爬楼梯问题。

3.1 递归实现

int climbStairs(int n){
    if(n == 0) return 0;
    else if(n == 1) return 1;
    else if(n == 2) return 2;
    return climbStairs_1(n-1)+climbStairs_1(n-2);
}

3.2 动态规划法

int climbStairs(int n){
    int i = 0;
    if(n == 0) return 0;
    else if(n == 1) return 1;
    else if(n == 2) return 2;
    int i1 = 1;
    int i2 = 2;
    int sum = 0;
    for(i = 3; i <= n; i++){
        sum = i1 +i2;
        i1 = i2;
        i2 = sum;
    }
    return sum;
}