Leetcode-70. 爬楼梯
题目：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
其中，1 <= n <= 45
- 递归（算法过大，超出时间限制）
int climbStairs(int n) { if (n <= 2) return n; return climbStairs(n - 1) + climbStairs(n - 2); }
- 动态规划，因为前两个的和可以表示第三个的结果。
我们首先想到，走上第三阶的方法，可以看成：1.走上第二阶之后再走一阶，2.走上第一阶之后再走两阶，所以我们的思路是动态规划，第三阶的走法是前两阶走法的总和；
int climbStairs(int n) { //因为第一阶和第二阶可以直接表示，我们就直接返回 //从第三阶开始，我们可以用前两阶的和表示 //走上第三阶的方法，可以看成： //1.走上第二阶之后再走一阶 //2.走上第一阶之后再走两阶 //所以第三阶的走法是前两阶走法的总和 if (n <= 2) return n; int dp[3]; dp[1] = 1; dp[2] = 2; int ret; for (int i = 3; i <= n; i++) { //这里每次进入循环证明还没结束，需要更新ret以及dp[2]和dp[1]的值 ret = dp[1] + dp[2]; dp[1] = dp[2]; dp[2] = ret; } return dp[2]; }
Leetcode-88. 合并两个有序数组
1.暴力求解
思路：直接将nums2的元素放到nums1的后面，直接排序
int cmp(int* a, int* b) { return *a - *b; } void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { for (int i = 0; i != n; ++i) { nums1[m + i] = nums2[i]; } qsort(nums1, nums1Size, sizeof(int), cmp); }
2.逆向双指针
思路：两个指针分别从nums1和nums2的最后一个非0元素开始，tail从nums1的最后一个元素开始，nums1[i]与nums2[j]比较，谁大谁就移到nums[tail]中；还要考虑到nums1的元素或者nums2的元素已经走完的情况，谁先走完，就把另外一个数组的元素移到nums[tail]处；
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { //i从nums1的最后一个非0元素开始遍历 //j从nums2的最后开始遍历 //tail从nums1的最后一个元素开始遍历 int i = m - 1, j = n - 1, tail = m + n - 1; while (i >= 0 || j >= 0) { //nums1的元素全部走完时，将nums2中的元素全部移到tail； if (i == -1) nums1[tail--] = nums2[j--]; //nums2的元素全部走完时，将nums2中的元素全部移到tail； else if (j == -1) nums1[tail--] = nums1[i--]; //谁大谁就移到tail处 else if (nums1[i] > nums2[j]) nums1[tail--] = nums1[i--]; else nums1[tail--] = nums2[j--]; } }
