Leetcode-70. 爬楼梯

题目：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
其中，1 <= n <= 45

1. 递归（算法过大，超出时间限制）

    	int climbStairs(int n){if (n <= 2)return n;return climbStairs(n - 1) + climbStairs(n - 2);}
   

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--];elsenums1[tail--] = nums2[j--];}}