2019年7月

最长上升子序列

问题描述

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence

思路

建立一个tmp数组，作为到tmp[i]时上升子序列的长度，最开始将tmp初始化为1。
因为nums[0]之前没有比它更小的数，所以tmp[i]不做任何改变，为初始值1；
i从2到n-1变化时,令j从0到i-1变化，当nums[j]比num[i]小时，在tmp[j]+1中寻找最大值。

题解

class Solution {
public:
    static bool cmp(int a,int b){
        return a>b;
    }
    int lengthOfLIS(vector<int> &nums) {
        int n = nums.size();
        if (n == 0) return 0;
        vector<int> tmp(n, 1);
        for (int i = 1; i < n; i++) {
            int cur = nums[i];
            for (int j = 0; j < i; j++) {
                if (cur > nums[j]) {
                    tmp[i] = max(tmp[j] + 1, tmp[i]);
                }
            }
        }
        sort(tmp.begin(), tmp.end(), cmp);
        return tmp[0];
    }
};

字符串解码

题目描述

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例:
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-string

思路

遇到这种括号匹配的问题，自然会想到用栈解决。
在遇到左括号前，将重复的次数存储在num中。
遇到左括号入栈，并将num清0。
将左括号之后，右括号之前的字母存到ret中。
碰到左括号入栈，并将并将num、ret清0。
如此重复，在遇到右括号的时候，将nums.top()次【因为数字在最内层括号的左边】的ret【要重复的部分还没入栈】，加到strs.top()中，然后令ret=str.top()作为新一次的需要重复的部分,在这个过程中别忘记弹出nums.pop()、strs.pop()。
重复以上步骤即可。

题解

class Solution {
public:
    string decodeString(string s) {
        string ret = "";
        int len = s.length();
        int num = 0;
        stack<int> nums;
        stack<string> strs;
        for (int i = 0; i < len; i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                num = num * 10 + s[i] - '0';
            } else if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z'))
            { ret = ret + s[i]; }
            else if (s[i] == '[') {
                nums.push(num);
                num = 0;
                strs.push(ret);
                ret = "";
            } else {
                int tmp=nums.top();
                nums.pop();
                for(int j=0;j<tmp;j++){
                    strs.top()=strs.top()+ret;
                }
                ret=strs.top();
                strs.pop();
            }
        }
        return ret;
    }
};

两数相加 II

问题描述

给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。

进阶:
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例:
输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers-ii

思路

数字相加的时候是从链表的末端开始的，所以用栈将两个链表存储起来会比较合适。
和两数相加I的思路一样，将情况分为3种：
1、两个栈都不为空
2、栈1为空
3、栈2为空
将每次相加的结果取余，余数为低位，压入栈中，栈底就是sum的最低位。
进位为相加的结果/10。
需要注意的是进位也要参与每次的加法。

通过栈构建链表时，需要特别注意：

ListNode *ret 为要返回的头节点。
一定要先建立cur = new ListNode(tmp.top());再让 ret = cur;
否则，ret只有一个节点。

题解

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        stack<int> stack1;
        stack<int> stack2;
        stack<int> tmp;
        int addtion = 0;
        while (l1 != nullptr) {
            stack1.push(l1->val);
            l1 = l1->next;
        }
        while (l2 != nullptr) {
            stack2.push(l2->val);
            l2 = l2->next;
        }
        while (!stack1.empty() || !stack2.empty()) {
            if (!stack1.empty() && !stack2.empty()) {
                tmp.push((stack1.top() + stack2.top() + addtion) % 10);
                addtion = (stack1.top() + stack2.top() + addtion) / 10;
                stack1.pop();
                stack2.pop();
            } else if (!stack1.empty()) {
                tmp.push((stack1.top() + addtion) % 10);
                addtion = (stack1.top() + addtion) / 10;
                stack1.pop();
            } else {
                tmp.push((stack2.top() + addtion) % 10);
                addtion = (stack2.top() + addtion) / 10;
                stack2.pop();
            }
        }
        ListNode *ret, *cur = nullptr;

        if (addtion == 1) {
            tmp.push(1);
        }
        while (!tmp.empty()) {
            if (cur == nullptr) {
                cur = new ListNode(tmp.top());
                ret = cur;
                tmp.pop();
            } else {
                cur->next = new ListNode(tmp.top());
                tmp.pop();
                cur = cur->next;
            }
        }
        return ret;
    }
};

搜索二维矩阵 II

问题描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。每列的元素从上到下升序排列。

示例:
现有矩阵 matrix 如下：

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii

思路1

暴力法。复杂度为O(m*n)。

题解

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
     for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }

        return false;
    }  
};

思路2

每层循环，然后在每层中用二分。最坏时间复杂度为O(n*log(m))。

题解

class Solution {
public:
    bool searchMatrix(vector<vector<int>> &matrix, int target) {
        int n = matrix.size();
        if (n == 0) return false;
        int m = matrix[0].size();
        int flag;
        for (int i = 0; i < n; i++) {
            int left = 0;
            int right = m - 1;
            int mid;
            flag = false;
            while (left <= right) {
                mid = (left + right) / 2;
                if (target < matrix[i][mid]) {
                    right=mid-1;
                } else if (target > matrix[i][mid]) {
                    left=mid+1;
                } else{
                    flag=1;
                    break;
                }
            }
            if(flag==1){
                break;
            }
        }
        return flag;
    }
};

不同的二叉搜索树

问题描述

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees

思路

由i个不同数字组成的二叉搜索树的数量，只与数字的数量i有关，与数的大小无关。
dp[i]代表n个节点数的树的种数。dp[0]、dp[1]均为1；
求n个节点构成的树的种类时，for(int j=1;j<=i;j++){dp[i]+=dp[j-1]*dp[i-j];}，表示根节点为1
的时候树的种类加上根节点为2...一直加到根节点为n的树的种类。
外层循环for(int i=2;i<=n;i++)为了求出每次的dp[j-1]*dp[i-j]。

题解

class Solution {
public:
    int numTrees(int n) {
        vector<int>dp(n+1,0);
        dp[0]=dp[1]=1;
        for(int i=2;i<=n;i++){
            for(int j=1;j<=i;j++){
                dp[i]+=dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }
};
  1. 1
  2. ...
  3. 7
  4. 8
  5. 9
  6. 10
  7. 11
  8. 12
  9. 13
  10. ...
  11. 25