LeetCode 1-100

彩笔只能靠题解求生

1. Two Sum

Array/Hash Table
哈希表存储键值对，同时方便查找

class Solution
{
public:
    vector<int> twoSum(vector<int> &nums, int target)
    {
        map<int, int> temp; //哈希表
        for (int i = 0; i < nums.size(); i++)
        {
            if (temp.count(target - nums[i]))
            {
                return {temp[target - nums[i]], i};
            }
            temp[nums[i]] = i; //如果无解则继续加入新元素，先判断再加入是因为可能存在重复元素
        }
        return {-1, -1};//防止出错
    }
};

2. Add Two Numbers

Linked List/Math
链表 new一个节点返回的是指针 指针使用类函数->

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode head(0);//存储头节点，并为空，每次循环创建一个新的next节点
        ListNode *result = &head;//头指针
        int flag = 0;//进位标志
        while(l1||l2||flag){
            int temp = 0;
            temp+=l1?l1->val:0;
            temp+=l2?l2->val:0;
            temp+=flag;
            flag=temp/10;
            temp%=10;
            ListNode* t = new ListNode(temp);
            result->next = t;
            result = result->next;
            l1=l1?l1->next:nullptr;
            l2=l2?l2->next:nullptr;
        }
        return head.next;
    }
};

3. Longest Substring Without Repeating Characters

Hash Table/Two Pointers/String/Sliding Window
了解了滑动窗口的使用 双指针法就是滑动窗口啊 使用哈希表来减少比较次数

class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        unordered_map<char, int> window;
        int start = 0, max = 0;
        for (int i = 0; i < s.size(); ++i)
        {
            //哈希表中存在重复元素，且位于start之后时，移动start
            if (window.count(s[i]) && window[s[i]] >= start) 
            {
                start = window[s[i]] + 1;
            }

            window[s[i]] = i;

            if (i - start + 1 > max)
            {
                max = i - start + 1;
            }
        }
        return max;
    }
};

4. Median Of Two Sorted Arrays

Array/Binary Search/Divide and Conquer
需要时间复杂度控制在O(log(m+n))，比较困难，但同时也是在提示使用二分查找
可以等价于第k小的方法，每次剔除k/2，剔除后k的值也会随之变化
同时有些还用查找第(n+m+1)/2和(n+m+2)/2个元素的方法，我认为这里是可以简化的，依照解题思路查找 到k后继续找k+1个应当是较为方便的
windliang写的题解很不错
使用中位数的定义的解法我觉得很精妙，是真正的懂了数学的定义

class Solution
{
public:
    double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2)
    {
        int m = nums1.size();
        int n = nums2.size();
        if (m > n)//保证对小的进行二分查找
        {
            return findMedianSortedArrays(nums2, nums1);
        }
        int iMin = 0, iMax = m; //iMax不能取m-1，否则可能i取不到右边界
        while (iMin <= iMax)
        {
            int i = (iMax + iMax) / 2;//nums1的分界线，在i-1和i之间，j类似
            int j = (m + n + 1) / 2 - i; //不论奇偶，都可以，利用int的特性
            if (i != 0 && j != n && nums1[i - 1] > nums2[j])//i左边比j右边大，i左移，同时注意边界
            {
                iMax = i - 1;
            }
            else if (j != 0 && i != m && nums1[i] < nums2[j - 1])//i右边比j左边小，i右移
            {
                iMin = i + 1;
            }
            else
            {
                int maxLeft = 0;
                if (i == 0)
                {
                    maxLeft = nums2[j - 1];
                }
                else if (j == 0)
                {
                    maxLeft = nums1[i - 1];
                }
                else
                {
                    maxLeft = nums1[i - 1] > nums2[j - 1] ? nums1[i - 1] : nums2[j - 1];
                }
                if ((n + m) % 2 == 1)//奇数则为左边最大的
                {
                    return maxLeft;
                }

                int minRight = 0;
                if (i == m)
                {
                    minRight = nums2[j];
                }
                else if (j == n)
                {
                    minRight = nums1[i];
                }
                else
                {
                    minRight = nums1[i] < nums2[j] ? nums1[i] : nums2[j];
                }
                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0;
    }
};

5. Logest Palindromic Substring

String/Dynamic Programming
了解了动态规划的更多用法，但显然这种方法空间代价过高
windliang的题解还是厉害
Manacher’s Algorithm也是真的厉害了 link解法5 插入#是把字符个数转化为奇数

class Solution
{
public:
    string preProcess(string s)
    {
        int n = s.length();
        if (n == 0)
        {
            return "^$";
        }
        string res = "^";
        for (int i = 0; i < n; ++i)
        {
            res.push_back('#');
            res.push_back(s[i]);
        }
        res += "#$";
        return res;
    }

    string longestPalindrome(string s)
    {
        string T = preProcess(s);
        int size = T.length();
        int *P = new int[size]();//new返回指针
        int C = 0, R = 0;
        for (int i = 1; i < size - 1; ++i)
        {
            int mirror = 2 * C - i;
            if (i < R)
            {
                P[i] = R - i < P[i] ? R - i : P[i];
            }
            else
            {
                P[i] = 0;
            }

            while (T[i - P[i] - 1] == T[i + P[i] + 1])
            {
                P[i]++;
            }

            if (i + P[i] > R)
            {
                C = i;
                R = i + P[i];
            }
        }

        int maxlen = 0, index = 0;
        for (int i = 1; i < size - 1; ++i)
        {
            if (P[i] > maxlen)
            {
                maxlen = P[i];
                index = i;
            }
        }
        int start = (index - maxlen) / 2;
        return s.substr(start, maxlen);
    }
};

6. ZigZag Conversion

String
了解了for的新的使用方式，类似foreach
考虑numRows为1的情况，用flag控制行数的改变
也可以找出每一行的规律，但需要考虑一些异常情况，题解计算中间行时，判断对应下一个对角线上的元素是否符合要求，保证了比如四个数、row为3时可能出现的问题。

class Solution
{
public:
    string convert(string s, int numRows)
    {
        if (numRows == 1)
            return s;
        vector<string> rows(min(int(s.length()), numRows));
        int curentRow = 0;
        int flag = -1;

        for (char c : s)
        {
            rows[curentRow] += c;
            if (curentRow == 0 || curentRow == numRows - 1)
                flag *= -1;
            curentRow += flag;
        }

        string res;
        for (string s : rows)
            res += s;

        return res;
    }
};

7. Reverse Integer

Math
取余符号无需考虑正负，通过使用字符串的手段可能才需要，同时需要注意有溢出的可能性，先判断是否可能溢出再运算，而不是先运算再判断有无溢出，都溢出了还能判断出啥

class Solution
{
public:
    int reverse(int x)
    {
        int res = 0;
        int maxThreshold = INT_MAX / 10;
        int minThreshold = INT_MIN / 10;
        int maxRemainder = INT_MAX % 10;
        int minRemainder = INT_MIN % 10;

        while (x)
        {
            int temp = x % 10;
            x /= 10;
            if (res > maxThreshold || (res == maxThreshold && temp > maxRemainder))
            {
                return 0;
            }
            if (res < minThreshold || (res == minThreshold && temp < minRemainder))
            {
                return 0;
            }
            res = res * 10 + temp;
        }
        return res;
    }
};

8. String to Integer

Math/String
这道题主要考虑细节问题，和其他类型的难题不同，有”+-2”、”+1”、”1-0”、”1 23”等等各种类型，一开始考虑使用 for(char c : str) 来遍历，但发现还是用使用i遍历较好，因为有”+-2”以及”1 23”等各种情况，不用i则需要其他的变量进行控制，同时还要考虑溢出等等情况，细节很多
还可以用正则表达式，但最近有点忘了如何使用，做题前有想到这个思路

class Solution {
public:
    int myAtoi(string str) {
        int res = 0;
        int i = 0;
        int flag = 1;
        //检查空格
        while (str[i] == ' ') { i++; }
        //检查符号
        if (str[i] == '-') { flag = -1; }
        //之所以不在前面的负号判断i++，因为存在-+1，不可分开判断
        if (str[i] == '+' || str[i] == '-') { i++; }
        //计算数字
        while (i < str.size() && isdigit(str[i])) {
            int r = str[i] - '0';
            //处理溢出
            if (res > INT_MAX / 10 || (res == INT_MAX / 10 && r > INT_MAX%10)) { 
                return flag > 0 ? INT_MAX : INT_MIN;
            }
            // ------------------------------------
            res = res * 10 + r;
            i++;
        }
        return flag > 0 ? res : -res;
    }
};

发现还有人用stringstream来做，通过了，还是不熟悉string

class Solution {
public:
    int myAtoi(string str) {
        int result = 0;
        stringstream ss;
        ss << str;
        ss >> result;
        return result;
    }
};

9. Palindrome Number

Math
可以考虑使用字符串
但不用字符串的方式时，可以反转一半数字来做比较，然后和原始数字比较
负数不是回文数字，个位数为0也不可能是，但0是
同时用 revertedNumber/10考虑了奇数个数字的情况，牛皮

class Solution
{
public:
    bool isPalindrome(int x)
    {
        if (x < 0 || (x != 0 && x % 10 == 0))//个位为0的判断不能省略，100100
        {
            return false;
        }
        int revertedNumber = 0;
        while (revertedNumber < x)//判断是否已经反转一半了，但必须排除个位为0的情况
        {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }
        return revertedNumber == x || revertedNumber / 10 == x;
    }
};

10. Regular Expression Matching

String/Dynamic Programming/Back Tracking
没想到还会有”aaa”和”aa”这种输入，其结果是true，那么正序扫描时就会出错，”aa*a”则反序也会出错，即无法使用水平扫描的方法来做这道题，只能使用回溯或者动态规划的方法解答。

回溯

class Solution
{
public:
    bool isMatch(string s, string p)
    {
        if (p.empty())
        {
            return s.empty();//很有灵性
        }
        //使用first_match还防止了下标的越界
        bool first_match = !s.empty() && (s[0] == p[0] || p[0] == '.');

        if (p.length() >= 2 && p[1] == '*')
        {
            return isMatch(s, p.substr(2)) || (first_match && isMatch(s.substr(1), p));
        }
        else
        {
            return first_match && isMatch(s.substr(1), p.substr(1));
        }
    }
};

DP 自顶向下和自底向上两种写法我觉得从结果获得的角度来讲，都是先获得底层结果在不断向上返回，官方题解的回溯法和自顶向下DP其实差不多，不过DP保存中间结果

class Solution
{
public:
    bool isMatch(string s, string p)
    {
        //动态规划的范围要长度+1，是因为空字符串也可被匹配
        //dp无法被压缩到一行，因为存在需要调用 dp[i][j + 2] 和 dp[i + 1][j + 1]，每一行正算反算一行都不够
        bool dp[s.length() + 1][p.length() + 1] = {0};

        for (int i = s.length(); i >= 0; --i)
        {
            for (int j = p.length(); j >= 0; --j)
            {
                if (j == p.length())
                {
                    dp[i][j] = (i == s.length());
                    continue;
                }

                bool first_match = (i != s.length()) && (s[i] == p[j] || p[j] == '.');

                if (j + 1 < p.length() && p[j + 1] == '*')
                {
                    //j+2不会越界，因为长度+1
                    dp[i][j] = dp[i][j + 2] || (first_match && dp[i + 1][j]);
                }
                else
                {
                    dp[i][j] = first_match && dp[i + 1][j + 1];
                }
            }
        }
        return dp[0][0];
    }
};

修改一下，和官方题解自底向上DP一样

class Solution
{
public:
    bool isMatch(string s, string p)
    {
        //动态规划的范围要长度+1，是因为空字符串也可被匹配
        //dp无法被压缩到一行，因为存在需要调用 dp[i][j + 2] 和 dp[i + 1][j + 1]，每一行正算反算一行都不够
        //bool dp[s.length() + 1][p.length() + 1] = {0};
        //上述写法在LeetCode会初始化有误，不是全被初始化为0，自己地方跑就没问题，上一段代码因为每个值都会更新所以没问题，而这一段有些没更新就出错了
        //代码执行出错好几次，搞得我心态都炸了
        //了解了vector的不同的初始化方式
        vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1, false));
        dp[s.length()][p.length()] = true;

        for (int i = s.length(); i >= 0; --i) //i不能从s.length()-1开始，因为存在""与"a*"匹配
        {
            for (int j = p.length() - 1; j >= 0; --j) //可以从p.length()-1开始，p为空时只有s也为空才为1，最后一列可以直接初始化解决
            {
                bool first_match = (i < s.length()) && (s[i] == p[j] || p[j] == '.');

                if (j + 1 < p.length() && p[j + 1] == '*')
                {
                    //j+2不会越界，因为长度+1
                    dp[i][j] = dp[i][j + 2] || (first_match && dp[i + 1][j]);
                }
                else
                {
                    dp[i][j] = first_match && dp[i + 1][j + 1];
                }
            }
        }
        return dp[0][0];
    }
};

11. Container With Most Water

Array/Two Pointers
双指针法，因为只有移动短的一根柱子才有可能找到更大的Area

class Solution
{
public:
    int maxArea(vector<int> &height)
    {
        int left = 0, right = height.size() - 1, maxarea = 0;
        while (left < right)
        {
            maxarea = max(min(height[left], height[right]) * (right - left), maxarea);
            if (height[left] > height[right])
            {
                --right;
            }
            else
            {
                ++left;
            }
        }
        return maxarea;
    }
};

12. Integer to Roman

Math/String
与Roman to Integer不同，只能老实做，但是好奇似乎switch效率比map高，神奇
leetcode判定时初始化，似乎有没有等号效率也有区别
似乎可以转化为字符串根据数字的位数来进行转化，以后再研究研究

class Solution
{
public:
    string getRomanNum(int n)
    {
        switch (n)
        {
        case 1:
            return "I";
        case 4:
            return "IV";
        case 5:
            return "V";
        case 9:
            return "IX";
        case 10:
            return "X";
        case 40:
            return "XL";
        case 50:
            return "L";
        case 90:
            return "XC";
        case 100:
            return "C";
        case 400:
            return "CD";
        case 500:
            return "D";
        case 900:
            return "CM";
        case 1000:
            return "M";
        default:
            return "?";
        }
    }

    string intToRoman(int num)
    {
        // map<int,string> roman{{1,"I"},{4,"IV"}, {5,"V"},{9,"IX"},{10,"X"},{40,"XL"}, {50,"L"},{90,"XC"}, {100,"C"},{400,"CD"}, {500,"D"},{900,"CM"}, {1000,"M"}};
        int number[13] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        string res = "";
        for (int i = 0; i < 13; ++i)
        {
            int count = num / number[i];
            if (count)
            {
                for (int j = 0; j < count; ++j)
                {
                    res += getRomanNum(number[i]);
                }

                num -= count * number[i];
            }
        }
        return res;
    }
};

13. Roman to Integer

Math/String
了解了map的初始化，同时根据罗马数字的排序方式可以判定只要小的字符出现在大的前面，那就是减去，不用去判断题目给出的几种情况

class Solution
{
public:
    int romanToInt(string s)
    {
        map<char, int> roman{{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}};
        int res = 0;
        int size = s.length();
        for (int i = 0; i < size - 1; ++i)
        {
            if (roman[s[i]] < roman[s[i + 1]])
            {
                res -= roman[s[i]];
            }
            else
            {
                res += roman[s[i]];
            }
        }
        res += roman[s.back()];
        return res;
    }
};

14. Longest Common Prefix

String
结果这道题有很多解法 水平扫描、分治、二分查找、字典树

class Solution
{
public:
    string longestCommonPrefix(vector<string> &strs)
    {
        int size = strs.size();
        if (!size)
        {
            return "";
        }
        else if (size == 1)
        {
            return strs[0];
        }

        int min_size = strs[0].length();
        for (int i = 1; i < size; ++i)
        {
            if (strs[i].length() < min_size)
            {
                min_size = strs[i].length();
            }
        }

        string res = "";
        for (int i = 0; i < min_size; ++i)
        {
            for (int j = 1; j < size; ++j)
            {
                if (strs[j][i] != strs[0][i])
                {
                    return res;
                }
            }
            res += strs[0][i];
        }

        return res;
    }
};

15. 3Sum

Array/Two Pointers
首先排序，然后for循环第一个值，在其后方寻找第二三个值，防止重复值，其次遍历第一个值时，如果下一个相同，需要跳过，当这个值大于0时，则不可能存在三个数等于0，可以直接退出遍历。
提示里说可以使用hashmap，但是hanshmap的key值不能重复，但是给的数组却可能有重复元素，感觉hashmap其实并不好用在这题中

class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); ++i)
        {
            if (nums[i] > 0)
            {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1])
            {
                continue;
            }
            int left = i + 1, right = nums.size() - 1;
            while (left < right)
            {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0)
                {
                    result.push_back({nums[i], nums[left], nums[right]});
                    while (left < right && nums[left] == nums[left + 1])
                    {//使用left<right是为了防止left+1可能下标越界
                        ++left;
                    }
                    while (left < right && nums[right] == nums[right - 1])
                    {
                        --right;
                    }
                    ++left;
                    --right;
                }
                else if (sum > 0)
                {
                    --right;
                }
                else
                {
                    ++left;
                }
            }
        }

        return result;
    }
};

16. 3Sum Closet

Array/Two Pointers
类似15题，只不过一个是等于0，一个是求最接近target的和，其实也可以在求和中去重，但是因为只需要和，那么是不是重复解无关紧要，直接不做了。

class Solution
{
public:
    int threeSumClosest(vector<int> &nums, int target)
    {
        sort(nums.begin(), nums.end());
        int result = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < nums.size(); ++i)
        {
            int left = i + 1, right = nums.size() - 1;
            while (left < right)
            {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == target)
                {
                    return target;
                }
                else if (abs(sum - target) < abs(result - target))
                {
                    result = sum;
                }

                if (sum > target)
                {
                    --right;
                }
                else
                {
                    ++left;
                }
            }
        }

        return result;
    }
};

17. Letter Combinations of a Phone Number

String/Backtracking
我觉得递归包括回溯，而且这道题也没有剪枝操作，但是用递归比较好些，用for之类的可能比较困难，这道题就是穷举所有可能性，而且还是BFS和DFS两种做法，递归是DFS，BFS可以用队列做
这个人写的不错，大大降低了空间复杂度，我也选择使用这种思想

class Solution
{
public:
    unordered_map<char, string> numbers = {{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};
    vector<string> res;
    string cur;
    void dfs(string digits)
    {
        if (!digits.size())
        {
            res.push_back(cur);
        }
        else
        {
            for (int i = 0; i < numbers[digits[0]].size(); ++i) //获得第一个数字对应字符的个数
            {
                cur.push_back(numbers[digits[0]][i]);
                dfs(digits.substr(1));
                cur.pop_back();
            }
        }
    }

    vector<string> letterCombinations(string digits)
    {
        if (digits.size())//如果digits一开始就为空，则还会存一次cur，导致错误
        { 
            dfs(digits);
        }
        return res;
    }
};

其实不需要写一个新的函数，直接调用自己就可以，但是这样写，有许多无用的return，代码看起来可能不好懂

class Solution
{
public:
    vector<string> map_ = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> res;
    string tmp;

    vector<string> letterCombinations(string digits)
    {
        if (digits.size() == 0)
        {
            if (!tmp.empty())
                res.push_back(tmp);
            return res;
        }
        string s = map_[digits[0] - '0'];
        for (int j = 0; j < s.size(); j++)
        {
            tmp.push_back(s[j]);
            letterCombinations(digits.substr(1));
            tmp.pop_back();
        }
        return res;
    }
};

18. 4Sum

Array/Hash Table/Two Pointers
可以直接做NSum算了，其实思想没有变化，只是再套一层循环，但是细节就会更多，容易错，而且好像没人用到Hash Table，毕竟存在重复元素，这类问题，重要的就是去除重复解
一开始想解NSum，一直想着怎么在一个函数内部写，但是这样的话超出2的部分怎么写没想明白，看了些解，发现还是要用递归，一开始没想到用递归

class Solution
{
public:
    vector<vector<int>> fourSum(vector<int> &nums, int target)
    {
        vector<vector<int>> res;
        int size = nums.size();
        if (size < 4)
        {
            return res;
        }
        int left, right, sum;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < size - 3; ++i)
        {
            if (i > 0 && nums[i] == nums[i - 1])
            { //跳过相同值
                continue;
            }

            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target)
            { //当前最小值
                break;
            }

            if (nums[i] + nums[size - 3] + nums[size - 2] + nums[size - 1] < target)
            { //当前最大值
                continue;
            }

            for (int j = i + 1; j < size - 2; ++j)
            { //第二个数
                if (j > i + 1 && nums[j] == nums[j - 1])
                { //j>i+1不能省略 example[0,0,0,0]，这样第二个数直接就遍历到末尾了
                    continue;
                }

                if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target)
                {//当前最小值
                    break;
                }

                if (nums[i] + nums[j] + nums[size - 2] + nums[size - 1] < target)
                {//当前最大值
                    continue;
                }

                left = j + 1;
                right = nums.size() - 1;
                while (left < right)
                {
                    sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target)
                    {
                        res.push_back({nums[i], nums[j], nums[left], nums[right]});
                        while (left < right && nums[left] == nums[left + 1])
                        { //使用left<right是为了防止left+1可能下标越界
                            ++left;
                        }
                        while (left < right && nums[right] == nums[right - 1])
                        {
                            --right;
                        }
                        ++left;
                        --right;
                    }
                    else if (sum > target)
                    { //如果和不为sum，那么，其实3，3类似的还是会依次遍历，不会跳过
                        while (left < right && nums[right] == nums[right - 1])
                        {
                            --right;
                        }
                        --right;
                    }
                    else
                    {
                        while (left < right && nums[left] == nums[left + 1])
                        { //使用left<right是为了防止left+1可能下标越界
                            ++left;
                        }
                        ++left;
                    }
                }
            }
        }
        return res;
    }
};

19. Remove Nth Node From End of List

Linked List/Two Pointers

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
public:
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        ListNode ahead(0), *index = &ahead; //哑节点ahead，因为可能删除头节点
        ahead.next = head;

        int i = 0;
        while (head)
        {
            if (i >= n)
            {
                index = index->next;
            }
            head = head->next;
            ++i;
        }
        index->next = index->next->next;
        return ahead.next;
    }
};

20. Valid Parentheses

Stack/String
需要注意细节，可能遇到右括号时栈内为空，也可能到结尾时栈内还有数据

class Solution
{
public:
    bool isValid(string s)
    {
        map<char,char> pair={{'}','{'},{']','['},{')','('}};
        stack<char> stack;
        int size = s.length();
        if (size % 2 == 1)
        { //奇数直接返回
            return false;
        }
        for (int i = 0; i < size; ++i)
        {
            if (s[i] == '}' || s[i] == ')' || s[i] == ']')
            {
                if (stack.empty())
                { //右括号比左括号多，栈内可能没有数据
                    return false;
                }
                if (pair[s[i]] == stack.top())
                {
                    stack.pop();
                    continue;
                }
                else//不匹配，返回false
                {
                    return false;
                }
            }
            stack.push(s[i]);
        }

        if (stack.empty())
        { //字符串结束，栈内还有数据
            return true;
        }
        else
        {
            return false;
        }
    }
};

21. Merge Two Sorted Lists

Linked List
可以用插入、合并以及递归的方法完成，插入是一个插入另一个链表，而合并是一个一个的合并到新的链表中，递归做法其实只是合并链表的一种方式

还是要注意对递归的熟悉

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {
        if (!l1)
        {
            return l2;
        }
        else if (!l2)
        {
            return l1;
        }
        else if (l1->val < l2->val)
        {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else
        {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

迭代法

22. Generate Parentheses

String/Backtracking
有趣的思路，使用next_permutation函数。回溯算法，其实就是一种深度搜索算法，题解写的也很好，但是所需的空间可能更多一些
广度优先遍历，但我觉得这题用广度是个很差的选择
闭合数是什么鬼，题解写的完全没看懂，结合这个里面的动态规划写法，我觉得这种解法是符合动态规划的思想的

class Solution
{
    vector<string> res;
    string cur = "";

public:
    vector<string> generateParenthesis(int n)
    {
        backTracking(0, 0, n);
        return res;
    }

    void backTracking(int open, int close, int n)
    {
        if (close == n)
        {
            res.push_back(cur);
            return;
        }
        if (open < n)//还可以添加开括号
        {
            cur += "(";
            backTracking(open + 1, close, n);
            cur.pop_back();
        }

        if (close < open)//闭括号个数少于开括号则添加
        {
            cur += ")";
            backTracking(open, close + 1, n);
            cur.pop_back();
        }
    }
};

这个用到了动态规划的思想，但没有保存数据，存在重复计算

class Solution
{
public:
    vector<string> generateParenthesis(int n)
    {
        if (!n)//n==0时
        {
            return {""};
        }
        vector<string> res;

        for (int i = 0; i < n; ++i)
        {
            for (string s1 : generateParenthesis(i))
            {
                for (string s2 : generateParenthesis(n - i - 1))
                {
                    res.push_back("(" + s1 + ")" + s2);
                }
            }
        }
        return res;
    }
};

保存结果的写法，这个里的动态规划写法也不错，直接少了递归，其算法中i控制了n的从1增长到n，实现递归的自底向上

class Solution
{
    vector<vector<string>> dp;

public:
    vector<string> generateParenthesis(int n)
    {
        if (dp.size() > n)
        {
            return dp[n];
        }
        vector<string> cur;
        if (!n)
        {
            cur.push_back("");
        }
        else
        {
            for (int i = n - 1; i >= 0; --i)
            {
                for (string s1 : generateParenthesis(i))
                {
                    for (string s2 : generateParenthesis(n - i - 1))
                    {
                        cur.push_back("(" + s1 + ")" + s2);
                    }
                }
            }
        }
        dp.push_back(cur);
        return dp[n];
    }
};

23. Merge k Sorted Lists

Heap / Linked List / Divide and Conquer
分治法可以复用21题的方法， 官方题解 方法三用了优先队列，这个思想上就是最小堆吧，不过现在不太想熟悉这个，下次吧

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {
        if (!l1)
        {
            return l2;
        }
        else if (!l2)
        {
            return l1;
        }
        else if (l1->val < l2->val)
        {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else
        {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }

    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        if (!lists.size())
        {
            return NULL;//return {}也可
        }
        int step = 1;
        while (step < lists.size())
        {
            for (int i = 0; i < lists.size() - step; i += 2 * step) //-step排除单个的merge
            {
                lists[i] = mergeTwoLists(lists[i], lists[i + step]);
            }
            step *= 2;
        }
        return lists[0];//当lists为空时[0]也不存在，所以开头需要另加判断
    }
};

24. Swap Nodes in Pairs

Linked List
看了别人的代码，还有递归的解法，太菜了，没想到

最初版，就是垃圾

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
public:
    ListNode *swapPairs(ListNode *head)
    {
        ListNode ahead(0), *index = &ahead, *temp;
        ahead.next = head;
        int count = 0;
        while (head)
        {
            head = head->next;
            ++count;
            if (count > 2)
            {
                index = index->next;
            }
            if (count % 2 == 0)
            {
                temp = index->next->next;
                index->next->next = head;
                temp->next = index->next;
                index->next = temp;
            }
        }

        return ahead.next;
    }
};

依然是非递归版，但进行了一些优化，其实end指针也不是必须的，但是不加代码会更复杂点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
public:
    ListNode *swapPairs(ListNode *head)
    {
        ListNode ahead(0), *pre = &ahead, *end;
        pre->next = head;
        while (head && head->next)
        { //指针不为空
            end = head->next;
            //更换顺序
            head->next = end->next;
            end->next = head;
            pre->next = end;
            //更新指针
            pre = head;
            head = head->next;
        }

        return ahead.next;
    }
};

递归版，写的太好了

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
public:
    ListNode *swapPairs(ListNode *head)
    {
        if (!head || !head->next)
        {
            return head;
        }
        ListNode *next = head->next;
        head->next = swapPairs(next->next);//写的很好，牛皮
        next->next = head;
        return next;
    }
};

25. Reverse Nodes in k-Group

Linked List
powcai 写的 题解 很好，用栈、尾插法是我不曾想到过的

无脑解法

  /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
public:
    //vector<ListNode*> temp;
    ListNode *reverseKGroup(ListNode *head, int k)
    {
        //temp.clear();这么写为什么会出错，没懂，可能还是不了解vector吧
        vector<ListNode *> temp;
        ListNode *t = head;
        for (int i = 0; i < k; ++i)
        {
            if (head == NULL)
            {
                return t; //个数不足，不翻转,直接返回head
            }
            temp.emplace_back(head);
            head = head->next;
        }

        for (int i = temp.size() - 1; i > 0; i--)
        {
            temp[i]->next = temp[i - 1];//翻转
        }
        temp[0]->next = reverseKGroup(head, k);//递归
        return temp[temp.size() - 1];
    }
};

链表操作

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
public:
    ListNode *reverseKGroup(ListNode *head, int k)
    {
        if (head == NULL)
        { //不添加则会出错
            return NULL;
        }
        ListNode *prev = NULL, *curr = head, *next;
        for (int i = 0; i < k; ++i)
        {

            if (curr == NULL) //head==NULL而k不为0时，下一次函数k=0，直接跳过for循环
            {                 //个数不足，最后一部分再翻转一次
                return reverseKGroup(prev, i);
            }

            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        //k=0时跳过for，此时head==NULL，出错
        head->next = reverseKGroup(curr, k); 
        return prev;
    }
};

26. Remove Duplicates from Sorted Array

Array/Two Pointers
一直想着赋值给i，忘了可以赋值给i+1，结果一直想着，怎么搞指针可以直接一直指向重复值的第二个位置

class Solution
{
public:
    int removeDuplicates(vector<int> &nums)
    {
        if (nums.size() == 0)//传入空数组时，如果不添加判断，index会返回1，导致出错
        {//可以改为nums.size()<2时返回nums.size()
            return 0;
        }
        int index = 0;
        for (int i = 1; i < nums.size(); ++i)
        {
            if (nums[i] != nums[index])//i可以和index比较，也可以和i-1比较，
            {
                nums[++index] = nums[i];
            }
        }

        return index + 1;//之所以要加1是因为返回的是长度而不是最大下标
    }
};

27. Remove Element

Array/Two Pointers
和26题类似，只是删除重复元素变成了删除制定元素，两种方法，一种前移元素，另一种是移动尾部元素

class Solution
{
public:
    int removeElement(vector<int> &nums, int val)
    {
        if (nums.size() == 0) //传入空数组时，如果不添加判断，index会返回1，导致出错
        {
            return 0;
        }
        int index = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (nums[i] != val)
            {

                nums[index] = nums[i];
                ++index;
            }
        }

        return index; //之所以要加1是因为返回的是长度而不是最大下标
    }
};

28. Implement strStr()

Two Pointers/String
看似简单，其实有很多方法，尤其是KMP，这个题解不错，对于库函数的了解其实也很重要， return haystack.find(needle); 就够了，但是面试肯定不能这么写
看这些算法就耗费来好几天，有毒
BF、KMP、
BM

• 坏字符 主串 aaaaaaaaa，模式串baaa，匹配到b时主串中的a为坏字符，此时si为0，而对应的xi为3，此时反而倒退，所以需要好后缀来进行补全

Sunday算法 偏移表
库函数、Horspool、自动机
这么多解法，简直不能算简单题

BF算法，暴风(Brute Force)算法

class Solution
{
public:
    int strStr(string haystack, string needle)
    {
        if (needle.empty())
        { //空字符串
            return 0;
        }
        if (needle.size() > haystack.size())
        {
            return -1;
        }
        int j;
        for (int i = 0; i < haystack.size() - needle.size() + 1; ++i)
        {//+1是因为减去needle-1长度，第一个数还是要比较的
            if (haystack[i] == needle[0])
            {
                for (j = 1; j < needle.size(); ++j)
                { //&&i<haystack.size()，减少了这个一下子效率就上去了
                    if (needle[j] != haystack[i + j])
                    {
                        break;
                    }
                }

                if (j == needle.size())
                {
                    return i;
                }
            }
        }

        return -1;
    }
};

BF写法二 其实思想相同，只是写法不同

class Solution
{
public:
    int strStr(string haystack, string needle)
    {
        if (needle.empty())
        { //空字符串
            return 0;
        }
        if (needle.size() > haystack.size())
        {
            return -1;
        }
        int j = 0;
        for (int i = 0; i < haystack.size(); ++i)
        {
            if (haystack[i] == needle[j])
            {
                ++j;
                if (j == needle.size())
                {
                    return i - j + 1;//因为前面++j了
                }
            }
            else
            {
                i -= j;
                j = 0;
            }
        }
        return -1;
    }
};

29. Divide Two Integers

Math / Binary Search
题解 这个另写一个函数，不断递归很巧妙

class Solution
{
public:
    int divide(int dividend, int divisor)
    {
        //边界条件
        if (divisor == 1)
            return dividend;
        if (dividend == 0)
            return 0;
        if (divisor == -1)
        {
            if (dividend == INT_MIN)
                return INT_MAX;
            return -dividend;
        }

        //判断符号
        bool sign = (dividend > 0) ^ (divisor > 0);
        //一般情况
        int res = div(abs(dividend), divisor);
        return sign ? -res : res;
    }

    int div(long dividend, long divisor)
    {

        dividend = abs(dividend);
        divisor = abs(divisor);
        if (dividend < divisor)
            return 0;
        int count = 1;
        long temp = divisor;
        while (temp + temp <= dividend)
        {
            temp = temp + temp;
            count = count + count;
        }
        return count + div(dividend - temp, divisor);
    }
};

31. Next Permutation

Array
没有想明白当a[i-1]做22题的时候没想到还有next_permutation()函数

class Solution
{
public:
    void nextPermutation(vector<int> &nums)
    {
        int index = nums.size() - 1, i;
        for (; index > 0; --index)
        { 
            if (nums[index] > nums[index - 1])
            {
                for (i = index + 1; i < nums.size(); ++i)
                {
                    if (nums[i] <= nums[index - 1])//要找到比nums[index-1]大的，所以遇到相等的就退出
                    {
                        break;
                    }
                }
                swap(nums[index - 1], nums[i - 1]);//i
                reverse(nums.begin() + index, nums.end());
                break;
            }
        }

        if (index == 0)//此时序列整体为降序，则从头开始
        {
            reverse(nums.begin(), nums.end());
        }
    }
};

34. Find First and Last Position of Element in Sorted Array

Array/Binary Search
二分查找进阶形式
一开始还想着能不能有做法一遍找到左边界和右边界，后来看了题解也是需要两遍，不过完全孤立的两遍查找我觉得还可以再优化优化
二分查找左闭右闭时，如果没有找到最终结果right二分查找的指针更新确实复杂，需要多思考，题解写的很好，我写的虽然有一些优化，但其实看起来还是题解更好懂

class Solution
{
public:
    vector<int> searchRange(vector<int> &nums, int target)
    {
        int left = 0, right = nums.size(), mid, index1 = -1, index2 = -1; //若找到target，用index1、index2表示左右边界

        while (left < right)
        {
            mid = left + (right - left) / 2;
            if (nums[mid] == target)
            {
                index1 = mid, index2 = mid;
                //找左边界，继续二分查找
                while (left < index1)
                {
                    mid = left + (index1 - left) / 2;
                    if (nums[mid] < target)
                    {
                        left = mid + 1;
                    }
                    else
                    {
                        index1 = mid;
                    }
                }
                //找右边界，找到的值会是大于边界的第一个值，所以要-1
                while (index2 < right)
                {
                    mid = index2 + (right - index2) / 2;
                    if (nums[mid] > target)
                    {
                        right = mid;
                    }
                    else
                    {
                        index2 = mid + 1;
                    }
                }
                --index2;
                break;
            }
            else if (nums[mid] < target)
            { //小于目标值left移动
                left = mid + 1;
            }
            else
            { //大于时都移动right，可以找到左边界
                right = mid;
            }
        }

        return {index1, index2};
    }
};

35. Search Insert Position

Array/binary Search
做多了二分查找的题，如果最终没找到target，left在右，right在左，left和right范围选择决定了while要不要等号

class Solution
{
public:
    int searchInsert(vector<int> &nums, int target)
    {
        int left = 0, right = nums.size(), middle;
        while (left <= right)
        {
            middle = left + (right - left) / 2;
            if (middle == nums.size())
            {
                return middle;
            }

            if (nums[middle] == target)
            {
                return middle;
            }
            else if (nums[middle] > target)
            {
                right = middle - 1;
            }
            else
            {
                left = middle + 1;
            }
        }
        return left;
    }
};

36. Valid Sudoku

Hash Table
题解用了一次遍历全判断完的办法，但是对于有确定的内容，我觉得可以不用哈希表，可以直接用数组，只不过需要字符转数字，注意从子宫格到坐标的映射或者映射到子宫格
位运算 牛皮 这个题解里的每一次处理一个子宫格和行与列，降低空间复杂度，但是每个元素需要遍历三次。而 这个 则是使用9个int来保存每一个数字的出现位置，不过每一个数字需要27位 运算符优先级

class Solution
{
public:
    bool isValidSudoku(vector<vector<char>> &board)
    {
        int number[10] = {0};
        for (int rows = 0; rows < board.size(); ++rows)
        {
            for (int cols = 0; cols < board[rows].size(); ++cols)
            {
                if (board[rows][cols] == '.')//遇到.则跳过
                { 
                    continue;
                }
                int n = board[rows][cols] - '0';//char转int
                //前9位存储子宫格号，中9位存储行号，后9位存储列号，共27位
                int index = (1 << cols) | (1 << rows + 9) | (1 << (rows / 3 * 3 + cols / 3 + 18)); 
                if ((number[n] & index) == 0)//相与，不重合则返回0
                { //注意&操作加括号，运算符优先级
                    number[n] |= index;
                }
                else//存在重合，返回false
                { 
                    return false;
                }
            }
        }
        return true;
    }
};

38. Count and Say

String
我用的是迭代的方法，没有用递归
主要是字符串首尾的处理

class Solution
{
public:
    string read(string str)
    {
        int count = 1;
        string temp = "";

        for (int i = 1; i < str.size(); ++i)//处理首部
        {
            if (str[i] != str[i - 1])
            {
                temp += to_string(count) + str[i - 1];
                count = 0;
            }
            ++count;
        }
        temp += to_string(count) + str[str.size() - 1];//处理尾部，最后一个元素肯定会漏

        return temp;
    }
    string countAndSay(int n)
    {
        string str = "1";
        if (n == 1)
        {
            return str;
        }
        else
        {
            for (int i = 2; i <= n; ++i)
            {
                str = read(str);
            }
        }
        return str;
    }
};

39. Combination Sum

Array / Backtracking
Two Sum 的高级版，由于可以重复使用元素，所以使用dfs会比较好

简陋版

class Solution
{
public:
    vector<vector<int>> res;
    vector<int> temp;
    int sum = 0;

    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        sort(candidates.begin(), candidates.end());
        dfs(candidates, 0, target);

        return res;
    }

    void dfs(vector<int> &candidates, int i, int target)
    {

        for (int j = i; j < candidates.size(); ++j)
        {
            if (candidates[j] == target - sum)
            {
                temp.push_back(candidates[j]);
                res.push_back(temp);
                temp.pop_back();
                return;
            }
            else if (candidates[j] < target - sum)
            {
                sum += candidates[j];
                temp.push_back(candidates[j]);
                dfs(candidates, j, target);
                temp.pop_back();
                sum -= candidates[j];
            }
            else
            {//剪枝
                return;
            }
        }
    }
};

代码优化 这个 写的不错 不排序则无法剪枝

class Solution
{
public:
    vector<vector<int>> res;
    vector<int> temp;

    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        dfs(candidates, 0, target, 0);
        return res;
    }

    void dfs(vector<int> &candidates, int index, int target, int sum)
    {
        if (sum > target)
        {
            return;
        }
        if (sum == target)
        {
            res.push_back(temp);
            return;
        }
        for (int j = index; j < candidates.size(); ++j)
        {//没有剪枝操作，因为没有排序
            temp.push_back(candidates[j]);
            dfs(candidates, j, target, sum + candidates[j]);
            temp.pop_back();
        }
    }
};

48. Rotate Image

Array
可以先转置再翻转行，简单的线代
题解 的方法二有想到不断旋转四个元素，但太难写。只想到一个个元素的交换，没想到可以直接创建一个长度为4的临时列表

class Solution
{
public:
    void rotate(vector<vector<int>> &matrix)
    {
        int size = matrix.size();
        for (int i = size - 1; i >= 0; --i)
        { //矩阵转置 下三角形从下到上swap
            for (int j = 0; j < i; ++j)
            {
                swap(matrix[i][j], matrix[j][i]);
            }
        }

        for (int i = 0; i < size; ++i)//翻转
        {
            for (int j = 0; j < size / 2; ++j)
            {
                swap(matrix[i][j], matrix[i][size - 1 - j]);
            }
        }
        /*翻转的另一种写法，注意&，不加&则遍历为只读
        for (auto &row : matrix)
        {
            reverse(row.begin(), row.end());
        }
        */
    }
};

还是这个 题解 风骚，直接交换三次就ok了，主要还是坐标的确定比较麻烦，但其实画了图发现其实四个点和边界的距离都是 i 和 j ，这就方便了坐标的确定。

class Solution
{
public:
    void rotate(vector<vector<int>> &matrix)
    {
        int size = matrix.size();
        for (int i = 0; i < size / 2; ++i)
        {
            for (int j = i; j < size - i - 1; ++j)
            {
                swap(matrix[i][j], matrix[j][size - 1 - i]);
                swap(matrix[i][j], matrix[size - 1 - i][size - 1 - j]);
                swap(matrix[i][j], matrix[size - 1 - j][i]);
            }
        }
    }
};

53. Maximum Subarray

Array / Divide an Conquer / Dynamic Programming
还是需要熟悉DP，还有 分治法，但是这么用分治法感觉有点逗比

class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
        int dp = 0, max = INT_MIN;//注意用INT_MIN，因为内部元素类型是int，存在负数
        for (int i : nums)
        {
            dp = i > dp + i ? i : dp + i;
            if (dp > max)
            {
                max = dp;
            }
            //可以直接调用max函数，但是我自己写的max却无法使用？有毒了
            //dp = max(dp + i, i);
            //res = max(res, dp);//找到问题了，调用max函数时，不要定义一个为max的变量

            //------贪心算法---------和DP只有细微的差异
            //sum += i;
            //res = max(res, sum);
            //if (sum < 0)
            //{
            //    sum = 0;
            //}
        }
        return max;
    }
};

56. Merge Intervals

Sort / Array
看 官方题解 就ok了

58. Length of Last Word

String
这个还行，通过res做判断

class Solution
{
public:
    int lengthOfLastWord(string s)
    {
        s.erase(s.find_last_not_of(' ') + 1);//除去尾部空格
        s = ' ' + s;//防止“a”类型
        for (int i = s.size() - 1; i >= 0; --i)
        {
            if (s[i] == ' ')
            {
                return s.size() - i - 1; //size()-1  -   (i+1)  +1
            }
        }
        return 0;
    }
};

66. Plus One

Array
再简单的题目，都有没有想到的 点 ，如果到第一位还需要进位，这表明应该新建一个长度加一的新数组，第一位为1，后续全为0。我没有想到，而是直接在开头插入了1

优化版

class Solution
{
public:
    vector<int> plusOne(vector<int> &digits)
    {

        for (int i = digits.size() - 1; i >= 0; --i)
        {
            if (digits[i] == 9)//直接判断是不是9
            {
                digits[i] = 0;
            }
            else
            {
                ++digits[i];
                return digits;
            }
        }

        //for循环没返回表明全是9
        //完全不需要新建一个长度加一的数组，直接末尾填充一个0就好了，再把第一个数字置1，比插入也好
        digits.push_back(0);
        digits[0] = 1;

        return digits;
    }
};

67. Add Binary

Math / String
就是简单题也有好的 题解

class Solution
{
public:
    string addBinary(string a, string b)
    {
        string ans;
        ans.reserve(max(a.size(), b.size()) + 1);//分配空间
        int carry = 0, s1 = a.size() - 1, s2 = b.size() - 1;
        while (s1 >= 0 || s2 >= 0 || carry == 1)
        {
            carry += s1 >= 0 ? a[s1--] - '0' : 0;
            carry += s2 >= 0 ? b[s2--] - '0' : 0;
            ans.push_back((carry & 1) + '0');//必须加括号，+的优先级比&高
            carry >>= 1;//右移运算符
        }
        reverse(ans.begin(), ans.end());//反转字符串
        return ans;
    }
};

70. Climbing Stairs

Dynamic Programming
看了题解，这就是斐波那契数列，而且甚至用不到数组，只需要几个变量就好了
Binets 方法和斐波那契公式其中重要的还是数学，而不是编程了，但是时间复杂度还能从O(n)下降为O(logn)

递归确实效率太低了，重复计算太多，保留中间计算过的内容其实就可以转换为动态规划了

class Solution
{
public:
    int climbStairs(int n)
    {
        if (n == 1 || n == 0)
        {
            return 1;
        }
        else
        {
            return climbStairs(n - 1) + climbStairs(n - 2);
        }
    }
};

动态规划

class Solution
{
public:
    int climbStairs(int n)
    {
        if (n < 2)
        {
            return 1;
        }
        int memo[n + 1] = {1};
        memo[1] = 1;
        for (int i = 2; i <= n; ++i)
        {
            memo[i] = memo[i - 1] + memo[i - 2];
        }
        return memo[n];
    }
};

88. Merge Sorted Array

Array/Two Pointers
一开始没看懂题目nums1已经长度为m+n了，然后在想申请数组空间再排序划算吗……

class Solution
{
public:
    void merge(vector<int> &nums1, int m, vector<int> &nums2, int n)
    {
        int p1 = m - 1, p2 = n - 1, p = m + n - 1;//p的初始化很好，防止了nums1.size()大于m+n
        while (p1 >= 0 && p2 >= 0)
        {
            nums1[p--] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--];
        }
        //p1有多无所谓，本来就是在p1中排序
        if (p2 >= 0)
        {
            //copy(nums2.begin(),nums2.begin()+p2+1,num1.begin());//p2加一转换为长度
            for (int i = 0; i <= p2; ++i)
            {
                nums1[i] = nums2[i];
            }
        }
    }
};