LeetCode 题解

发表于 更新于

LeetCode OJ is a platform for preparing technical coding interviews.

LeetCode OJ 是为与写代码有关的技术工作面试者设计的训练平台。

LeetCode OJ:http://oj.leetcode.com/

默认题目顺序为题目添加时间倒叙，本文题解顺序与OJ题目顺序一致（OJ会更新，至少目前一致。。。）。 习惯大括号换行，遇到大括号默认不换行的样例代码，导致有的换行有的没换行，实在懒得一个个改……

2015.11.17更新：今天又看leetcode，发现题目列表终于有编号了。 咦，新题目加锁了，要25 dollar一个月的捐赠……

Made By：CSGrandeur: LeetCode 题解

208.Implement Trie (Prefix Tree)

20170209

基本字典树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Trie {
public:
    struct Node
    {
        Node *nex[26];
        bool word;
        Node(){memset(nex, NULL, sizeof(nex)), word = false;}
    };
    Node *root;
    /** Initialize your data structure here. */
    Trie() {
        root = new Node;
    }

    /** Inserts a word into the trie. */
    void insert(string word) {
        Node *p = root;
        for(auto c : word)
        {
            if(p->nex[c - 'a'] == NULL)
                p->nex[c - 'a'] = new Node;
            p = p->nex[c - 'a'];
        }
        p->word = true;
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        Node *p = root;
        for(auto c : word)
        {
            if(p->nex[c - 'a'] == NULL)
                return false;
            p = p->nex[c - 'a'];
        }
        return p->word;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Node *p = root;
        for(auto c : prefix)
        {
            if(p->nex[c - 'a'] == NULL)
                return false;
            p = p->nex[c - 'a'];
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * bool param_2 = obj.search(word);
 * bool param_3 = obj.startsWith(prefix);
 */

207.Course Schedule

20170208

先构造个图。一开始没想拓扑排序的事，就用DFS来判断的，标记-1表示尚未考察，0表示暂没结果，1表示确认可选修。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> fst, nex, v;
    vector<int> ok;
    bool DFS(int i)
    {
        if(ok[i] != -1) return ok[i];
        ok[i] = 0;
        for(int j = fst[i]; j != -1; j = nex[j])
            if(!DFS(v[j]))
                return ok[i] = 0;
        return ok[i] = 1;
    }
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        fst.resize(numCourses + 1, -1);
        ok.resize(numCourses + 1, -1);
        for(int i = 0; i < prerequisites.size(); i ++)
        {
            nex.push_back(fst[prerequisites[i].first]);
            fst[prerequisites[i].first] = nex.size() - 1;
            v.push_back(prerequisites[i].second);
        }
        for(int i = numCourses - 1; i >= 0; i --)
            numCourses -= DFS(i);
        return !numCourses;
    }
};

206.Reverse Linked List

20170208

好像又是老题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre = NULL;
        while(head != NULL)
        {
            ListNode *tmp = head->next;
            head->next = pre;
            pre = head;
            head = tmp;
        }
        return pre;
    }
};

205.Isomorphic Strings

20170208

思路一是两个map互相映射，出现矛盾则说明不同构。两个map用于解决其中一个串可能有多个字符对应另一个串同一个字符，只用一个map则会掉这个坑。、

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        vector<char> mp1(128, 0), mp2(128, 0);
        for(int i = 0; i < s.length(); i ++)
        {
            if(!mp1[s[i]]) mp1[s[i]] = t[i];
            if(!mp2[t[i]]) mp2[t[i]] = s[i];
            if(mp1[s[i]] != t[i] || mp2[t[i]] != s[i])
                return false;
        }
        return true;
    }
};

思路二是把俩字符串按同一规则转换，转换后字符串直接比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    void convert(string &s)
    {
        vector<char> mp(128, 0);
        int p = 1;
        for(int i = 0; i < s.length(); i ++)
        {
            if(!mp[s[i]]) mp[s[i]] = p ++;
            s[i] = mp[s[i]];
        }
    }
    bool isIsomorphic(string s, string t) {
        convert(s);
        convert(t);
        return s == t;
    }
};

204.Count Primes

20170208

筛素数，以前比赛时候写的滚瓜烂熟的，现在竟然忘了还复习一下…… 从2开始把每个其倍数都标记成合数，然后往后枚举，枚举到的没标记的一定是素数（如果它是合数，它的质因数肯定比它小，而比它小的质数的倍数都已经标记过了），继续标记其所有倍数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int countPrimes(int n) {
        int ret = 0;
        vector<bool> pr(n, true);
        for(int i = 2; i < n; i ++)
        {
            if(pr[i])
            {
                ret ++;
                for(int j = i << 1; j < n; j += i)
                    pr[j] = false;
            }
        }
        return ret;
    }
};

203.Remove Linked List Elements

20170208

好像又是老题，开头加个哨兵节点就不用担心head节点被删除的情况了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *pre = new ListNode(0);
        pre->next = head;
        for(ListNode *p = pre; head != NULL; head = head->next)
        {
            if(head->val == val)
            {
                p->next = head->next;
            }
            else
                p = head;
        }
        return pre->next;
    }
};

202.Happy Number

20170208

直接思路是用哈希记录判循环，降低空间复杂度可以用两个值一个每次算一步，另一个每次算两步来判循环。 还有个方法是只要大于 6 就一直进行，能保证计算结束，不知道怎么证明的。 代码放传统思路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int SumSquare(int x)
    {
        int ret = 0;
        while(x)
        {
            ret += (x % 10) * (x % 10);
            x /= 10;
        }
        return ret;
    }
    bool isHappy(int n) {
        unordered_set<int> s;
        while(!s.count(n))
        {
            s.insert(n);
            n = SumSquare(n);
        }
        return s.count(1);
    }
};

201.Bitwise AND of Numbers Range*

20170208

二进制从左往右看，当遇到某位不相等的时候，最终结果后面的位都会是0，因为在n~m之间，连续的数字中这些位肯定会出现0。题目巧在如果思路转换为求二进制最长相同前缀，代码就很简单了。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int cnt = 0;
        while(m != n)
        {
            m >>= 1;
            n >>= 1;
            cnt ++;
        }
        return m << cnt;
    }
};

还有一种理解方式也很好，把n的右侧的1一一去掉，当n不大于m的时候，n剩下的就是那个相同前缀。

1
2
3
4
5
6
7
8
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        while(n > m)
            n = n & (n - 1);
        return n;
    }
};

200.Number of Islands

20170208

我一定是做了道假题。。DFS、BFS随便做，好陈旧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    const int dx[4] = {1, -1, 0, 0};
    const int dy[4] = {0, 0, 1, -1};
    int row, col;
    void BFS(vector<vector<char>> &grid, int x, int y)
    {
        queue<pair<int, int> > q;
        q.push(make_pair(x, y));
        grid[x][y] = 0;
        while(!q.empty())
        {
            pair<int, int> now = q.front();
            q.pop();
            for(int i = 0; i < 4; i ++)
            {
                pair<int, int> nex = make_pair(now.first + dx[i], now.second + dy[i]);
                if(nex.first >= 0 && nex.first < row && nex.second >= 0 && nex.second < col && grid[nex.first][nex.second] == '1') 
                {
                    grid[nex.first][nex.second] = 0;
                    q.push(nex);
                }
            }
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        int ret = 0;
        if(grid.size() == 0) return 0;
        row = grid.size();
        col = grid[0].size();
        for(int i = 0; i < grid.size(); i ++)
        {
            for(int j = 0; j < grid[0].size(); j ++)
            {
                if(grid[i][j] == '1')
                    ret ++, BFS(grid, i, j);
            }
        }
        return ret;
    }
};

199.Binary Tree Right Side View

20170208

二叉树层次遍历，加个层数标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    struct Node
    {
        TreeNode *p;
        int layer;
        Node(TreeNode *p_, int layer_):p(p_), layer(layer_){}
    };
    vector<int> rightSideView(TreeNode* root) {
        queue<Node> q;
        vector<int> ret;
        if(root != NULL)
            q.push(Node(root, 0));
        int last = -1;
        while(!q.empty())
        {
            Node now = q.front();
            q.pop();
            if(last != now.layer)
            {
                last = now.layer;
                ret.push_back(now.p->val);
            }
            if(now.p->right != NULL)
                q.push(Node(now.p->right, now.layer + 1));
            if(now.p->left != NULL)
                q.push(Node(now.p->left, now.layer + 1));
        }
        return ret;
    }
};

198.House Robber

20170207

简单的动态规划，两个数一个表示上一个没rob的当前最佳收益，另一个表示上一个rob了的，反复更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int rob(vector<int>& nums) {
        int dp[2] = {0};
        for(auto m : nums)
        {
            int tmp = dp[1];
            dp[1] = max(dp[1], dp[0] + m);
            dp[0] = max(dp[0], tmp);
        }
        return max(dp[1], dp[0]);
    }
};

191.Number of 1 Bits

20170207

做过树状数组应该对n&(n-1)很熟了，n-1让二进制末尾的1变0，这个1后面的0都变1，和n做按位与就相当于去掉了最后一个1，这样每次操作都能去掉一个1，一位一位统计就快多了。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cnt = 0;
        while(n)
        {
            cnt ++;
            n = n & (n - 1);
        }
        return cnt;
    }
};

190.Reverse Bits

20170207

首先是最直接的方法，把所有bit放到新数中的对应位置。 题目提到一句“If this function is called many times, how would you optimize it?”是很值得思考的。直接的方法进行了32次操作，每个操作里有若干次位运算，这个数字是否可以优化呢？ 一个可能思路是并行的分治。问题二分，并行用位运算实现，这样就log(32)=5次操作了。

直接思路：

1
2
3
4
5
6
7
8
9
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t ret = 0;
        for(int i = 0; i < 32; i ++)
            ret |= ((n >> i) & 1) << (31 - i);
        return ret;
    }
};

并行分治思路：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        n = (n & 0x0000FFFF) << 16 | (n & 0xFFFF0000) >> 16;
        n = (n & 0x00FF00FF) << 8 | (n & 0xFF00FF00) >> 8;
        n = (n & 0x0F0F0F0F) << 4 | (n & 0xF0F0F0F0) >> 4;
        n = (n & 0x33333333) << 2 | (n & 0xCCCCCCCC) >> 2;
        n = (n & 0x55555555) << 1 | (n & 0xAAAAAAAA) >> 1;
        return n;
    }
};

189.Rotate Array

20170207

空间复杂度不是O(1)的想都不要想。网上方法已经很多了，如： 1、后k个翻转，前面的翻转，再整个翻转。 2、前k个和后k个一一swap，就变成后n-k个做k旋转的子问题了，继续进行到结束。 3、把数组分成若干个以k为间隔的“子数组”，而且这个“子数组”是可以循环回去的，比如1, 2, 3, 4, 5, k=3，“子数组”就是1, 4, 2, 5, 3，对它做step=1的右循环。 这里放 方法3 的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k = k % nums.size();
        int readynum = 0;
        for(int i = 0; readynum < nums.size(); i ++)
        {
            int tmp = nums[i];
            for(int j = i + k; ; j = (j + k) % nums.size())
            {
                swap(tmp, nums[j]);
                readynum ++;
                if(j == i)
                    break;
            }
        }
    }
};

188.Best Time to Buy and Sell Stock IV*

20170207

一开始思路是常规的记忆化搜索，状态记录为[第i天价格][剩下k次][是否在买入状态]，是否买入状态是二值的，所以内存主要在于天数和次数的取值，小trick是k取值过大时候，可缩小到天数的1/2。结果还是超内存了，虽然网上看到有类似解法没超内存，不过看最大那组数据，还是不适合开二维数组的。

这题有个特别之处，当考察第i天时，并不关心这是多少天了，而关心的只是当前的盈利情况和剩下多少次交易机会，于是数组缩小为次数k这一维。两个数组分别表示剩下k次的买入状态余额和非买入状态余额，状态方程是buy[k]=max(buy[k], sell[k-1] - price); sell[k]=max(sell[k], buy[k] + price);。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(k > prices.size() / 2)
            k = prices.size() / 2;
        vector<int> buy(k + 1, -0x3f3f3f3f), sell(k + 1, 0);
        int ret = 0;
        for(auto price : prices)
        {
            for(int i = k; i > 0; i --)
            {
                buy[i] = max(buy[i], sell[i - 1] - price);
            }
            for(int i = k; i > 0; i --)
            {
                sell[i] = max(sell[i], buy[i] + price);
                ret = max(sell[i], ret);
            }
        }
        return ret;
    }
};

187.Repeated DNA Sequences

20170207

没遇到网上说的内存问题，直接unordered_map过掉了。用字典树应该会比较快和稳定吧。 对每个长度为10的串进行统计，大于1次就做记录。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        unordered_map<string, bool> mp;
        vector<string> ret;
        for(int i = 10; i <= s.length(); i ++)
        {
            string tmp = s.substr(i - 10, 10);
            if(!mp.count(tmp))
                mp[tmp] = 0;
            else if(mp[tmp] == 0)
            {
                ret.push_back(tmp);
                mp[tmp] = 1;
            }
        }
        return ret;
    }
};

179.Largest Number

一开始用递归写了个复杂逻辑的comp函数，后来发现，主要确定两个字符串 a, b 的 a+b 和 b+a 的大小关系，就能确定 a 和 b 的顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {  
public:  
    static bool cmp(const string &a, const string &b)
    {
        return a + b > b + a;
    }
    string largestNumber(vector& nums) {
        vector vs;
        for(auto num : nums)
            vs.push_back(to_string(num));
        sort(vs.begin(), vs.end(), cmp);
        if(atoi(vs[0].c_str()) == 0) return "0";
        string res = "";
        for(auto v : vs) res += v;
        return res;
    }
};

174.Dungeon Game

从左上角开始 DP 的话，无法做到既贪心当前最优，又保证路径最优。

从右下角开始 DP，则可以只考虑路径最优，dp[i][j]表示从(i, j)位置到终点所需最小health值。

这道题也可以用二分答案来直接从左上角贪心，不过速度会慢很多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//DP
class Solution {  
public:  
    int calculateMinimumHP(vector& dungeon) {
        int rows = dungeon.size(), cols = dungeon[0].size();
        vectordp(rows);
        for(int i = rows - 1; i >= 0; i --)
        {
            dp[i] = vector(cols, 0);
            for(int j = cols - 1; j >= 0; j --)
            {
                if(i < rows - 1 && j < cols - 1)
                    dp[i][j] = max(1, min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j]);
                else if(i < rows - 1) dp[i][j] = max(1, dp[i + 1][j] - dungeon[i][j]);
                else if(j < cols - 1) dp[i][j] = max(1, dp[i][j + 1] - dungeon[i][j]);
                else dp[i][j] = max(1, -dungeon[i][j] + 1);
            }
        }
        return dp[0][0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//二分答案
class Solution {  
public:  
    int calculateMinimumHP(vector& dungeon) {
        int left = 1, right = 0x3f3f3f3f, mid;
        while(left < right) { mid = left + right >> 1;
            if(Test(mid, dungeon)) right = mid;
            else left = mid + 1;
        }
        return left;
    }
    bool Test(int mid, vector tmp)
    {
        int rows = tmp.size(), cols = tmp[0].size();
        for(int i = 0; i < rows; i ++)
        {
            for(int j = 0; j < cols; j ++) { if(i && j && tmp[i - 1][j] + mid > 0 && tmp[i][j - 1] + mid > 0)
                    tmp[i][j] = max(tmp[i - 1][j] + tmp[i][j], tmp[i][j - 1] + tmp[i][j]);
                else if(i && tmp[i - 1][j] + mid > 0)
                    tmp[i][j] = tmp[i - 1][j] + tmp[i][j];
                else if(j && tmp[i][j - 1] + mid > 0)
                    tmp[i][j] = tmp[i][j - 1] + tmp[i][j];
                else if(i || j)
                    tmp[i][j] = -mid;
            }
        }
        return tmp[rows - 1][cols - 1] + mid > 0;
    }
};

173.Binary Search Tree Iterator

变形的非递归中序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {  
public:  
    stack s;
    TreeNode *now;
    BSTIterator(TreeNode *root) {
        while(!s.empty()) s.pop();
        now = root;
        while(now)
        {
            s.push(now);
            now = now->left;
        }
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !s.empty();
    }

    /** @return the next smallest number */
    int next() {
        now = s.top();
        s.pop();
        TreeNode *tmp = now;
        now = now->right;
        while(now)
        {
            s.push(now);
            now = now->left;
        }
        return tmp->val;
    }
};

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

172.Factorial Trailing Zeroes

阶乘的每个数中，每个因子 2 和每个因子 5 可以构成一个0，而 2 远比 5 多，比如 8 就有三个 2，于是统计因子 5 的个数。

让输入 n 迭代除以 5，第一次得到 5 的倍数的个数，第二次是 25 倍数的个数，最后得到所有因子 5 的个数。

1
2
3
4
5
6
7
8
9
class Solution {  
public:  
    int trailingZeroes(int n) {
        int ret = 0;
        while(n)
            ret += n /= 5;
        return ret;
    }
};

171.Excel Sheet Column Number

比用Number算Title容易点，在算每一位时候记得加 1 。

1
2
3
4
5
6
7
8
9
class Solution {  
public:  
    int titleToNumber(string s) {
        int ret = 0;
        for(auto c : s)
            ret = ret * 26 + c - 'A' + 1;
        return ret;
    }
};

169.Majority Element

很有意思的题目，要求的数占超过一半，那么在O(n)时间里把不同的数抵消掉，“多数数”肯定会被留下来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {  
public:  
    int majorityElement(vector& nums) {
        int x, cnt = 0;
        for(auto num : nums)
        {
            if(cnt == 0)
                x = num, cnt ++;
            else
                cnt += num == x ? 1 : -1;
        }
        return x;
    }
};

168.Excel Sheet Column Title

跳过 0 的 26 进制，处理每一位的时候要减 1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {  
public:  
    string convertToTitle(int n) {
        string ret;
        while(n)
        {
            ret += (n - 1) % 26 + 'A';
            n = (n - 1) / 26;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

166.Fraction to Recurring Decimal

有边界数据，所以直接转成long long做，处理正负号。

对小数部分，每次求余数乘 10 再做下一位，当余数重复出现就是循环了。找重复用unordered_map。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {  
public:  
    string fractionToDecimal(int numerator, int denominator) {
        string ret = "";
        long long num = numerator, deno = denominator, nm;
        if(num * deno < 0) ret = "-";
        num = abs(num), deno = abs(deno);
        ret += to_string(num / deno);
        if(num % deno == 0) return ret;
        unordered_map mp;
        ret += '.';
        for(long long now = num % deno * 10; now; )
        {
            mp[now] = ret.length();
            ret += '0' + now / deno;
            now = now % deno * 10;
            if(mp.count(now))
            {
                ret.insert(mp[now], 1, '(');
                ret += ')';
                break;
            }
        }
        return ret;
    }
};

165.Compare Version Numbers

按.分开，逐个按数字大小比较。 C++怎么就没个方便的split函数呢。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {  
public:  
    int compareVersion(string version1, string version2) {
        int vpos1(0), vpos2(0), lp1(0), lp2(0);
        version1 += ".", version2 += ".";
        while(vpos1 < version1.length() || vpos2 < version2.length())
        {
            int vnum1(0), vnum2(0);
            vpos1 = version1.find(".", lp1);
            vpos2 = version2.find(".", lp2);
            if(vpos1 < version1.length())
                vnum1 = atoi(version1.substr(lp1, vpos1 - lp1).c_str()), lp1 = vpos1 + 1;
            if(vpos2 < version2.length()) 
                vnum2 = atoi(version2.substr(lp2, vpos2 - lp2).c_str()), lp2 = vpos2 + 1; 
            if(vnum1 > vnum2) return 1;
            else if(vnum1 <vnum2) return -1;
        }
        return 0;
    }
};

164.Maximum Gap

很久没碰过桶排序了，这道题有个很有意思的推理——把 n 个数放到 n 个桶里，两种情形，1、每个桶一个数。2、存在有多个数的桶，那也一定有其他的空桶。

这两种情况下，最大gap都是某个桶的最小值与它前面最近的有数的桶的最大值之差，所以避免了桶内排序，O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {  
public:  
    int maximumGap(vector& nums) {
        if(nums.size() < 2) return 0;
        int maxNum = *max_element(nums.begin(), nums.end());
        int minNum = *min_element(nums.begin(), nums.end());
        int gap = ceil((double)(maxNum - minNum) / (nums.size() - 1));
        int bcnt = nums.size();
        if(gap == 0) return 0;
        vector<pair<int, int> > bucket(bcnt, make_pair(-1, -1));
        for(int i = 0; i < nums.size(); i ++) 
        { 
            int bsite = (nums[i] - minNum) / gap; 
            if(bucket[bsite].first == -1 || bucket[bsite].first > nums[i])
                bucket[bsite].first = nums[i];
            if(bucket[bsite].second == -1 || bucket[bsite].second < nums[i])
                bucket[bsite].second = nums[i];
        }
        int last = minNum, ans = 0;
        for(int i = 0; i < bucket.size(); i ++)
        {
            if(bucket[i].first != -1)
                ans = max(ans, bucket[i].first - last);
            if(bucket[i].second != -1)
                last = bucket[i].second;
        }
        return ans;
    }
};

162.Find Peak Element

O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {  
public:  
    int findPeakElement(vector& nums) {
        int left = 0, right = nums.size() - 1, mid;
        while(left < right) { mid = left + right >> 1;
            if(nums[mid] < nums[mid + 1])
                left = mid + 1;
            else right = mid;
        }
        return left;
    }
};

160.Intersection of Two Linked Lists

先统计两个链表长度，将 长链表 对准 距离末尾 与短链表长度相同 位置，同步遍历返回交叉点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {  
public:  
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int na, nb;
        ListNode *ha = headA, *hb = headB;
        for(na = nb = 0; ha || hb;)
        {
            if(ha) na ++, ha = ha->next;
            if(hb) nb ++, hb = hb->next;
        }
        while(na > nb) headA = headA->next, na --;
        while(nb > na) headB = headB->next, nb --;
        while(headA != headB) headA = headA->next, headB = headB->next;
        return headA;
    }
};

155.Min Stack

一开始做的是每个元素存两个数的数组，一个表示数值，一个表示“上一个最小值下标”。然后觉得这样的话，不是最小值的那些位置，其实浪费了空间。 还是用两个数组或者两个栈，一个存数，一个存最小值好了。 看Discuss里24ms的答案也没什么特别的，运行时间的浮动吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class MinStack {  
public:  
    stack v;
    stack m;
    void push(int x) {
        if(v.empty() || x <= m.top())
            m.push(x);
        v.push(x);
    }

    void pop() {
        if(v.empty()) return;
        if(!m.empty() && m.top() == v.top())
            m.pop();
        v.pop();
    }

    int top() {
        return v.top();
    }

    int getMin() {
        return m.top();
    }
};

154.Find Minimum in Rotated Sorted Array II

首先如果首尾大量相同元素，那么“先去掉末尾连续相同元素”和“二分的时候nums[mid]==nums[left]时left++”这样的方法，都会退化为O(n)。于是尽可能想二分的方法，有了下面这个分治的方法，然而经不起推敲，其实即便分治，还是会退化成O(n)。贴上两种代码吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {  
public:  
    int findMin(vector& nums) {
        int left = 0, right = nums.size() - 1, mid = 0;
        while(left < right && nums[left] >= nums[right])
        {
            mid = left + right >> 1;
            if(nums[mid] > nums[left]) left = mid + 1;
            else if(nums[mid] == nums[left]) left ++;
            else right = mid;
        }
        return nums[left];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {  
public:  
    int findMin(vector& nums) {
        findRelMin(nums, 0, nums.size());
    }
    int findRelMin(vector& nums, int left, int right)
    {
        if(left >= right - 1) return nums[left];
        int mid = left + right >> 1;
        if(nums[left] == nums[right - 1])
        {
            int l = findRelMin(nums, left, mid);
            int r = findRelMin(nums, mid, right);
            return min(l, r);
        }
        int s = left, e = right;
        while(left < right) { mid = left + right >> 1;
            if(nums[mid] >= nums[s]) left = mid + 1;
            else right = mid;
        }
        return left == e ? nums[s] : nums[left];
    }
};

153.Find Minimum in Rotated Sorted Array

二分

1
2
3
4
5
6
7
8
9
10
11
class Solution {  
public:  
    int findMin(vector& nums) {
        int left = 0, right = nums.size(), mid;
        while(left < right) { mid = left + right >> 1;
            if(nums[mid] >= nums[0]) left = mid + 1;
            else right = mid;
        }
        return left == nums.size() ? nums[0] : nums[left];
    }
};

152.Maximum Product Subarray

维护当前位置连续乘积的最大值 tmpp 和最小值 tmpn ，最大值和最小值都可能由三种情况得到：上一个数的 tmppA[i]，上一个数的 tmpnA[i]，A[i]本身。

不断更新答案，最终输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProduct(int A[], int n) {
        int tmpp = A[0], tmpn = A[0], tmp, ans = A[0];
        for(int i = 1; i < n; i ++)
        {
            tmp = tmpp;
            tmpp = max(max(A[i], A[i] * tmpp), A[i] * tmpn);
            tmpn = min(min(A[i], A[i] * tmp), A[i] * tmpn);
            ans = max(ans, tmpp);
        }
        return ans;
    }
};

151.Reverse Words in a String

先翻转整个字符串，然后从前往后一个单词一个单词地再翻转一次，同时去除多余空格，等于是扫描两遍，O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void reverseWords(string &s) {
        reverse(s.begin(), s.end());
        int start = 0, end = 0, j = 0;
        while(start != s.length())
        {
            while(start != s.length() && s[start] == ' ') start ++;
            for(end = start; end != s.length() && s[end] != ' '; end ++);
            if(j != 0 && start <= end - 1) s[j ++] = ' ';
            for(int i = end - 1; start < i; start ++, i --)
                swap(s[i], s[start]), s[j ++] = s[start];
            while(start < end) s[j ++] = s[start ++];
        }
        s.resize(j);
    }
};

150.Evaluate Reverse Polish Notation

逆波兰表达式计算四则运算。用栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int evalRPN(vector &tokens) {
        int a, b;
        stack s;
        for(int i = 0; i < tokens.size(); i ++) { if(isdigit(tokens[i][0]) || tokens[i].length() > 1)
            {
                s.push(atoi(tokens[i].c_str()));
                continue;
            }
            a = s.top();s.pop();
            b = s.top();s.pop();
            switch(tokens[i][0])
            {
                case '+': s.push(b + a); break;
                case '-': s.push(b - a); break;
                case '*': s.push(b * a); break;
                case '/': s.push(b / a); break;
            }
        }
        return s.top();
    }
};

149.Max Points on a Line

平面上一条直线最多穿过多少点。乍一看好熟悉的问题，做了这么久计算几何。。。却还真没做过这个小问题。

第一反应当然不能O(n^3)枚举了，枚举圆周好像也不行，毕竟是考察所有点，不是某个点。那么应该就是哈希斜率了吧。

肯定少不了竖直的线，哈希斜率这不像是这类OJ让写的题吧。。忘了map这回事了。

确定思路之后，还是看看别人博客吧，少走点弯路，然后就学习了还有unordered_map这么个东西，还有一个博客 的思路挺好，避免double问题，把斜率转化成化简的x、y组成字符串。

再另外就是重叠的点了，想让题目坑一点，怎能少得了这种数据，单独处理一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    int maxPoints(vector &points) {
        int ans = 0;
        for(int i = 0; i < points.size(); i ++)
        {
            unordered_map<string, int> mp;
            int tmpans = 0, same = 0;
            for(int j = i + 1; j < points.size(); j ++)
            {
                int x = points[j].x - points[i].x, y = points[j].y - points[i].y;
                int g = gcd(x, y);
                if(g != 0) x /= g, y /= g;
                else {same ++; continue;}
                if(x < 0) x = -x, y = -y;
                string tmp = to_string(x) + " " + to_string(y);
                if(!mp.count(tmp)) mp[tmp] = 1;
                else mp[tmp] ++;
                tmpans = max(tmpans, mp[tmp]);
            }
            ans = max(tmpans + 1 + same, ans);
        }
        return ans;
    }
    int gcd(int a, int b)
    {
        return a ? gcd(b % a, a) : b;
    }
};

148.Sort List

又长见识了，原来链表也可以O(nlogn)排序的。没往下想就查了一下，看到人说用归并，于是才开始想能不能实现。。。

O(n)找到中点，把中点的next变成NULL，对两部分递归。递归结束后对两部分归并，先找到newhead，即两部分的头部val较小的那个，然后归并就把小的从newhead往后续。

把最后的next赋值NULL，返回newhead。

又有空数据@_@.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *sortList(ListNode *head) {
        int n = 0;
        ListNode *p = head;
        while(p != NULL)
            n ++, p = p->next;
        if(n <= 1) return head; n >>= 1;
        p = head;
        while(-- n)
            p = p->next;
        ListNode *tmp = p->next;
        p->next = NULL;
        ListNode *nl = sortList(head);
        ListNode *nr = sortList(tmp);
        ListNode *newhead;
        if(nl->val < nr->val)
        {
            newhead = nl;
            nl = nl->next;
        }
        else
        {
            newhead = nr;
            nr = nr->next;
        }
        p = newhead;
        while(nl != NULL && nr != NULL)
        {
            if(nl->val < nr->val) p->next = nl, p = p->next, nl = nl->next;
            else p->next = nr, p = p->next, nr = nr->next;
        }
        while(nl != NULL) p->next = nl, p = p->next, nl = nl->next;
        while(nr != NULL) p->next = nr, p = p->next, nr = nr->next;
        p->next = NULL;
        return newhead;
    }
};

147.Insertion Sort List

指针操作很烦啊。。暴力枚举插入位置，注意细节就能过了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        ListNode *newhead = head;
        if(head == NULL) return NULL;
        head = head->next;
        newhead->next = NULL;
        while(head != NULL)
        {
            if(head->val < newhead->val)
            {
                ListNode *tmp = head->next;
                head->next = newhead;
                newhead = head;
                head = tmp;
                continue;
            }
            ListNode *pre = newhead, *p = newhead->next;
            while(p != NULL && p->val < head->val)
            {
                p = p->next;
                pre = pre->next;
            }
            pre->next = head;
            head = head->next;
            pre = pre->next;
            pre->next = p;
        }
        return newhead;
    }

};

146.LRU Cache

新建数据类class Val，保存key、val和访问自增标记updatecnt。

用unordered_map更新数据，增加updatecnt，并把更新的数据放入队列，最关键是处理capacity满了的时候，队列依次出队，map中不存在的和updatecnt和最新数据不相等的项目都忽略，直到发现updatecnt和map中存的最新状态相等，则为(最近未使用)数据，出队后在map中erase。思路有点像STL队列实现版本的Dijkstra。

有一个博客 的方法更好，map中存的是链表的节点指针，链表顺序表示访问情况，这样就把map内容和链表的每个节点一一对应了，没有冗余节点，且更新操作也是O(1)的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Val{
public:
    int key;
    int val;
    int updatecnt;
};
class LRUCache{
public:
    int cap;
    unordered_map<int, Val> mp;
    queue q;
    LRUCache(int capacity) {
        cap = capacity;
    }

    int get(int key) {
        if(mp.count(key))
        {
            mp[key].updatecnt ++;
            q.push(mp[key]);
            return mp[key].val;
        }
        return -1;
    }

    void set(int key, int value) {
        if(mp.count(key))
        {
            mp[key].val = value;
            mp[key].updatecnt ++;
            q.push(mp[key]);
        }
        else
        {
            if(mp.size() == cap)
            {
                Val tmp;
                while(!q.empty())
                {
                    tmp = q.front();
                    q.pop();
                    if(mp.count(tmp.key) && tmp.updatecnt == mp[tmp.key].updatecnt)
                        break;
                }
                mp.erase(mp.find(tmp.key));
                mp[key].key = key;
                mp[key].val = value;
                mp[key].updatecnt = 0;
                q.push(mp[key]);
            }
            mp[key].key = key;
            mp[key].val = value;
            mp[key].updatecnt = 0;
            q.push(mp[key]);
        }
    }
};

145.Binary Tree Postorder Traversal

二叉树的非递归后序遍历，考研的时候非常熟悉了，现在写又要想好久。重点是关于右子树遍历时候需要一个标记，或者标记根节点出栈次数，或者标记右子树是否访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector postorderTraversal(TreeNode *root) {
        vector ans;
        if(root == NULL) return ans;
        stack<TreeNode*> s;
        TreeNode *visited;
        while(root != NULL || !s.empty())
        {
            while(root != NULL)
                s.push(root), root = root->left;
            root = s.top();
            if(root->right == NULL || visited == root->right)
            {
                ans.push_back(root->val);
                s.pop();
                visited = root;
                root = NULL;
            }
            else
            {
                root = root->right;
            }
        }
        return ans;
    }
};

144.Binary Tree Preorder Traversal

前序遍历的非递归就容易多了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector preorderTraversal(TreeNode *root) {
        stack<TreeNode*> s;
        vector ans;
        if(root == NULL) return ans;
        s.push(root);
        while(!s.empty())
        {
            root = s.top();
            s.pop();
            ans.push_back(root->val);
            if(root->right != NULL) s.push(root->right);
            if(root->left != NULL) s.push(root->left);
        }
    }
};

143.Reorder List

找到中间位置，把中间之后的链表反转，两个指针一个从头一个从尾开始互插，奇偶和指针绕得有点晕，理清就好了。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode *head) {
        int n = 0;
        ListNode *pre, *p = head;
        while(p)
            n ++, p = p->next;
        if(n < 3) return; n >>= 1;
        pre = p = head;
        p = p->next;
        while(n --) p = p->next, pre = pre->next;
        while(p != NULL)
        {
            ListNode *tmp = p->next;
            p->next = pre;
            pre = p;
            p = tmp;
        }
        ListNode *tail = pre;
        p = head;
        while(true)
        {
            ListNode *tmp1 = p->next, *tmp2 = tail->next;
            p->next = tail;
            tail->next = tmp1;
            p = tmp1;
            if(p == tail || p == tmp2) break;
            tail = tmp2;
        }
        p->next = NULL;
    }
};

142.Linked List Cycle II

设置两个指针slow和fast，从head开始，slow一次一步，fast一次两步，如果fast能再次追上slow则有圈。 设slow走了n步，则fast走了2*n步，设圈长度m，圈起点到head距离为k，相遇位置距离圈起点为t，则有：

n = k + t + pm; (1)

2*n = k + t + qm;(2)

这里p和q是任意整数。（不过fast速度是slow二倍，则肯定在一圈内追上，p就是0了）

2 * (1) - (2) 得k = lm - t;(l = q - 2 * p)

即 k 的长度是若干圈少了 t 的长度。 因此这时候，一个指针从head开始，另一个从相遇位置开始，都每次只走一步，当从head开始的指针走到圈开始位置时，两指针刚好相遇。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == NULL) return NULL;
        ListNode *slow, *fast;
        slow = fast = head;
        int n = 0;
        do
        {
            n ++;
            if(slow == NULL || fast == NULL) return NULL;
            slow = slow->next;
            fast = fast->next;
            if(fast == NULL) return NULL;
            fast = fast->next;
            if(fast == NULL) return NULL;
        }while(slow != fast);
        fast = head;
        while(slow != fast)
            slow = slow->next, fast = fast->next;
        return fast;
    }
};

141.Linked List Cycle

呃，时间逆序做的结果。。。成买一送一了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == NULL) return false;
        ListNode *slow, *fast;
        slow = fast = head;
        int n = 0;
        do
        {
            n ++;
            if(slow == NULL || fast == NULL) return NULL;
            slow = slow->next;
            fast = fast->next;
            if(fast == NULL) return NULL;
            fast = fast->next;
            if(fast == NULL) return NULL;
        }while(slow != fast);
        return true;
    }
};

140.Word Break II

先递推，dp[i] == true 表示 s 中前 i 个字符的串是符合要求的，枚举位置 i ，对于 i 枚举位置 j < i，如果 dp[j] == true且 j ~ i的串在字典中，则dp[i] = true。

同时对于这样的 j, i，site[i].push_back(j)，即在 i 位置的可行迭代表中增加位置 j。

完成site之后，从尾部倒着DFS过去就得到了所有串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    vector DFS(const string &s, vector *site, int ith)
    {
        vector res;
        for(int i = 0; i < site[ith].size(); i ++)
        {
            vector tmp;
            string str = s.substr(site[ith][i], ith - site[ith][i]);
            if(site[site[ith][i]].size() == 0)
                res.push_back(str);
            else
            {
                tmp = DFS(s, site, site[ith][i]);
                for(int j = 0; j < tmp.size(); j ++)
                    res.push_back(tmp[j] + " " + str);
            }
        }
        return res;
    }
    vector wordBreak(string s, unordered_set &dict) {
        vector *site = new vector[s.length() + 1];
        bool *dp = new bool[s.length() + 1];
        memset(dp, 0, sizeof(bool) * s.length());
        dp[0] = true;
        for(int i = 1; i <= s.length(); i ++)
        {
            for(int j = 0; j < i; j ++)
            {
                if(dp[j] == true && dict.count(s.substr(j, i - j)))
                   site[i].push_back(j), dp[i] = true;
            }
        }
        return DFS(s, site, s.length());
    }
};

139.Word Break

参考Word Break II，对于dp标记，当dp[i]为true时候可以停止枚举后面的 j，优化一下常数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool wordBreak(string s, unordered_set &dict) {
        bool *dp = new bool[s.length() + 1];
        memset(dp, 0, sizeof(bool) * (s.length() + 1));
        dp[0] = true;
        for(int i = 1; i <= s.length(); i ++)
            for(int j = 0; j < i; j ++)
            {
                dp[i] = dp[i] || dp[j] && dict.count(s.substr(j, i - j));
            }
        return dp[s.length()];
    }
};

138.Copy List with Random Pointer

第一次遍历，把每个节点复制一份放到对应节点的下一个，即组成二倍长的链表：ori1->copy1->ori2->copy2->...

第二次遍历，利用复制节点总是对应节点的下一个节点特性，将每个ori->next->random指向ori->random->next，中间判断一下空指针。

第三次遍历，把两个链表拆开，恢复原链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode *p = head, *newhead = NULL, *tmp;
        if(p == NULL) return NULL;
        while(p != NULL)
        {
            tmp = new RandomListNode(p->label);
            tmp->next = p->next;
            p->next = tmp;
            p = tmp->next;
        }
        newhead = head->next;
        p = head;
        while(p != NULL)
        {
            tmp = p->next;
            tmp->random = p->random == NULL ? NULL : p->random->next;
            p = tmp->next;
        }
        p = head;
        while(p != NULL)
        {
            tmp = p->next;
            p->next = tmp->next;
            p = tmp->next;
            tmp->next = p == NULL ? NULL : p->next;
        }
        return newhead;
    }
};

137.Single Number II

方法一：设置cnt[32]记录 32个比特位的1的个数，出现3次的数的对应位的1总数为3的倍数，则统计之后每个位对3取模，剩下的位为1的则对应个数为1的那个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int singleNumber(int A[], int n) {
        int cnt[32] = {0};
        for(int i = 0; i < n; i ++)
        {
            int tmp = A[i];
            for(int j = 0; j < 33; tmp >>= 1, j ++)
                cnt[j] += tmp & 1;
        }
        int ans = 0;
        for(int i = 0; i < 32; i ++)
            ans |= (cnt[i] % 3) << i;
        return ans;
    }
};

方法二：设置int one, two模拟两位二进制来统计各比特位1次数，每当one和two对应二进制位都为1的时候把one和two都清零，最后剩下的one就是要求的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int singleNumber(int A[], int n) {
        int one = 0, two = 0;
        for(int i = 0; i < n; i ++)
        {
            two |= one & A[i];
            one ^= A[i];
            int tmp = one & two;
            two ^= tmp;
            one ^= tmp;
        }
        return one;
    }
};

136.Single Number

一路异或过去就可以了。

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int singleNumber(int A[], int n) {
        int tmp = 0;
        for(int i = 0; i < n; i ++)
            tmp ^= A[i];
        return tmp;
    }
};

135.Candy

时间复杂度 O(n)的方法还是容易想了，优化为空间复杂度O(1)的话也不难，只是思考代码的时候会有点绕。

上坡一步步来，下坡走个等差数列，波峰位置比较一下上坡时候记录的最大值和下坡求的的最大值，取较大的，具体看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int candy(vector &ratings) {
        int cnt = 0, i, j, start, nownum;
        for(i = 0; i < ratings.size(); i ++) 
        { 
            if(i == 0 || ratings[i] == ratings[i - 1]) 
                nownum = 1; 
            else if(ratings[i] > ratings[i - 1])
                nownum ++;
            if(i + 1 < ratings.size() && ratings[i + 1] < ratings[i])
            {
                start = 1;
                for(j = i + 1; j < ratings.size() && ratings[j] < ratings[j - 1]; start++, j ++); 
                if(start > nownum)
                    cnt += (start + 1) * start >> 1;
                else
                    cnt += ((start - 1) * start >> 1) + nownum;
                nownum = 1;
                i = j - 1;
            }
            else
                cnt += nownum;
        }
        return cnt;
    }
};

134.Gas Station

证明题。

一、如果从 i 到 j 的时候理论计算气量刚好为负数，则 i ~ j 的加气站都不可以作为起点。

反证一下，从前往后去掉站，如果去掉的站能增加气，即正数，则结果更糟。如果去掉的站是负数，那么负数如果抵消了之前的正数，则在到 j 之前已经负数了，如果不能抵消之前的正数，那么结果还是更糟。

二、判断是否能成行，一个环的和为非负就可以。

假设环为正， 0 ~ j 刚好为负， j + 1 ~ k 刚好为负数，k + 1 之后为正，则 k + 1 为答案。

也反证一下，k + 1 出发，到gas.size() - 1都为正，则转回来到 j - 1 都会为正。如果到 j 时候为负，则整个环不可能为正，所以到 j 的时候也为正，剩下的一样。这样就能够成功转一圈。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int canCompleteCircuit(vector &gas, vector &cost) {
       int i, ans, sum, all;
       for(i = ans = sum = all = 0; i < gas.size(); i ++)
       {
           sum += gas[i] - cost[i];
           all += gas[i] - cost[i];
           if(sum < 0) { sum = 0; ans = i + 1; } } return all >= 0 ? ans : -1;
    }
};

133.Clone Graph

label是唯一的，递归，用unordered_map标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    unordered_map<int, UndirectedGraphNode *> mp;
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if(node == NULL || mp.count(node->label)) return NULL;
        UndirectedGraphNode *tmp = new UndirectedGraphNode(node->label);
        mp[node->label] = tmp;
        for(int i = 0; i < node->neighbors.size(); i ++)
        {
            cloneGraph(node->neighbors[i]);
            tmp->neighbors.push_back(mp[node->neighbors[i]->label]);
        }
        return tmp;
    }
};

132.Palindrome Partitioning II

O(n^2)的动态规划。

cutdp[i] 表示前 i 个字符最小切割几次。

paldp[i][j] == true 表示 i ~ j 是回文。

在枚举 i 和 i 之前的所有 j 的过程中就得到了 paldp[j][i] 的所有回文判断，而对于 i + 1，paldp[j][i + 1]可由 s[j]、s[i + 1]、dp[j + 1][i]在O(1)判断。

cutdp[i]为所有 j (j < i)，当paldp[j + 1][i] true的 cutdp[j] + 1的最小值。注意一下边界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minCut(string s) {
        bool paldp[s.length()][s.length()];
        int cutdp[s.length()];
        for(int i = 0; i < s.length(); i ++) { cutdp[i] = 0x3f3f3f3f; for(int j = i - 1; j >= -1; j --)
            {
                if(s.at(j + 1) == s.at(i) && (j + 2 >= i - 1 || paldp[j + 2][i - 1]))
                {
                    paldp[j + 1][i] = true;
                    cutdp[i] = min(cutdp[i], (j >= 0 ? (cutdp[j] + 1) : 0));
                }
                else
                    paldp[j + 1][i] = false;

            }
        }
        return cutdp[s.length() - 1];
    }
};

131.Palindrome Partitioning

O(n^2)动态规划，paldp[i][j] == true表示 i ~ j 是回文。这里DP的方法是基本的，不再多说。

得到paldp之后，DFS一下就可以了。因为单字符是回文，所以DFS的终点肯定都是解，所以不必利用其他的结构存储答案信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vectorres;
    vector tmp;
    bool **paldp;
    void DFS(string s, int ith)
    {
        if(ith == s.length())
        {
            res.push_back(tmp);
            return;
        }
        for(int i = ith; i < s.length(); i ++)
        {
            if(paldp[ith][i])
            {
                tmp.push_back(s.substr(ith, i - ith + 1));
                DFS(s, i + 1);
                tmp.pop_back();
            }
        }
        return;
    }
    vector partition(string s) {
        paldp = new bool*[s.length()];
        for(int i = 0; i < s.length(); i ++)
            paldp[i] = new bool[s.length()];
        for(int i = 0; i < s.length(); i ++) for(int j = i; j >= 0; j --)
                paldp[j][i] = s.at(i) == s.at(j) && (j + 1 >= i - 1 || paldp[j + 1][i - 1]);
        DFS(s, 0);
        return res;
    }
};

130.Surrounded Regions

周围四条边的O做起点搜索替换为第三种符号，再遍历所有符号把O换成X，第三种符号换回O。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    typedef pair<int, int> pii;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    queue q;
    void solve(vector &board) {
        if(board.size() == 0) return;
        int width = board[0].size();
        int height = board.size();
        for(int i = 0; i < width; i ++)
        {
            if(board[0][i] == 'O')
                board[0][i] = '#', q.push(pair<int, int>(0, i));
            if(board[height - 1][i] == 'O')
                board[height - 1][i] = '#', q.push(pii(height - 1, i));
        }
        for(int i = 1; i < height - 1; i ++)
        {
            if(board[i][0] == 'O')
                board[i][0] = '#', q.push(pii(i, 0));
            if(board[i][width - 1] == 'O')
                board[i][width - 1] = '#', q.push(pii(i, width - 1));
        }
        while(!q.empty())
        {
            pii now = q.front();
            q.pop();
            for(int i = 0; i < 4; i ++) 
            { 
               int ty = now.first + dx[i]; 
               int tx = now.second + dy[i]; 
               if(tx >= 0 && tx < width && ty >= 0 && ty < height && board[ty][tx] == 'O')
               {
                   board[ty][tx] = '#';
                   q.push(pii(ty, tx));
               }
            }
        }
        for(int i = 0; i < height; i ++)
            for(int j = 0; j < width; j ++)
            {
                if(board[i][j] == 'O') board[i][j] = 'X';
                else if(board[i][j] == '#') board[i][j] = 'O';
            }
    }
};

129.Sum Root to Leaf Numbers

遍历一遍加起来。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int ans;
    void DFS(TreeNode *now, int tmp)
    {
        if(now->left == NULL && now->right == NULL)
        {
            ans += tmp * 10 + now->val;
            return;
        }
        if(now->left != NULL)
        {
            DFS(now->left, tmp * 10 + now->val);
        }
        if(now->right != NULL)
        {
            DFS(now->right, tmp * 10 + now->val);
        }
    }
    int sumNumbers(TreeNode *root) {
        if(root == NULL) return 0;
        ans = 0;
        DFS(root, 0);
        return ans;
    }
};

128.Longest Consecutive Sequence

方法一：一开始竟然想了并查集，其实绕弯了，多此一举。哈希+并查集，把每个数哈希，枚举每个数看相邻的数在不在数组里，并查集合并，只是并查集的复杂度要比O(1)大一些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    unordered_map<int, int> mp, cnt;
    int ans = 1;
    int fa(int i)
    {
        i == mp[i] ? i : (mp[i] = fa(mp[i]));
    }
    int longestConsecutive(vector &num) {
        for(int i = 0; i < num.size(); i ++)
            mp[num[i]] = num[i], cnt[num[i]] = 1;
        for(int i = 0; i < num.size(); i ++)
        {
            if(mp.count(num[i] + 1) && fa(num[i]) != fa(num[i] + 1))
            {
                cnt[fa(num[i] + 1)] += cnt[fa(num[i])];
                ans = max(cnt[fa(num[i] + 1)], ans);
                mp[fa(num[i])] = fa(num[i] + 1);
            }
        }
        return ans;
    }
};

方法二：哈希+枚举相邻数。相邻的数在数组里的话，每个数至多访问一次；相邻的数不在数组里的话，枚举会中断。所以设哈希复杂度为O(1)的话，这个方法是严格的O(n)。

其实这个题的数据挺善良，如果出了2147483647, -2147483648，那还是用long long 稳妥些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    unordered_map<int, bool> vis;
    int longestConsecutive(vector &num) {
        int ans = 0;
        for(int i = 0; i < num.size(); i ++)
            vis[num[i]] = false;
        for(int i = 0; i < num.size(); i ++)
        {
            if(vis[num[i]] == false)
            {
                int cnt = 0;
                for(int j = num[i]; vis.count(j); j ++, cnt ++)
                {
                    vis[j] = true;
                }
                for(int j = num[i] - 1; vis.count(j); j --, cnt ++)
                {
                    vis[j] = true;
                }
                ans = max(ans, cnt);
            }
        }

        return ans;
    }
};

127.Word Ladder II

用数组类型的队列，BFS过程中记录pre路径，搜完后迭代回去保存路径。

似乎卡了常数，用queue队列，另外存路径的方法超时了。

想更快就双向广搜吧。让我想起了POJ那个八数码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Node
{
public:
    string str;
    int pace;
    int pre;
    Node(){}
    Node(string s, int pa, int pr)
    {
        str = s;
        pace = pa;
        pre = pr;
    }
};
class Solution {
public:
    vector ans;
    vector findLadders(string start, string end, unordered_set &dict) {
        vector q;
        q.push_back(Node(end, 1, -1));
        unordered_map<string, int> dis;
        dis[end] = 1;
        for(int i = 0; i < q.size(); i ++) 
        { 
            Node now = q[i]; 
            if(dis.count(start) && now.pace >= dis[start])
                break;
            for(int j = 0; j < now.str.length(); j ++)
            {
                string tmp = now.str;
                for(char c = 'a'; c <= 'z'; c ++) 
                { 
                   tmp[j] = c; 
                   if((dict.count(tmp) || tmp == start) && (!dis.count(tmp) || dis[tmp] == now.pace + 1)) 
                   { 
                       dis[tmp] = now.pace + 1; 
                       q.push_back(Node(tmp, now.pace + 1, i)); 
                   } 
                } 
            } 
        } 
        for(int i = q.size() - 1; i >= 0 && q[i].pace == dis[start]; i --)
        {
            if(q[i].str == start)
            {
                vector tmp;
                for(int j = i; j != -1; j = q[j].pre)
                    tmp.push_back(q[j].str);
                ans.push_back(tmp);
            }
        }
        return ans;
    }
};

126.Word Ladder

直接BFS。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int ladderLength(string start, string end, unordered_set &dict) {
        typedef pair<string, int> pii;
        unordered_set flag;
        queue q;
        q.push(pii(start, 1));
        while(!q.empty())
        {
            pii now = q.front();
            q.pop();
            for(int i = 0; i < now.first.length(); i ++)
            {
                string tmp = now.first;
                for(char j = 'a'; j <= 'z'; j ++)
                {
                    tmp[i] = j;
                    if(tmp == end) return now.second + 1;
                    if(dict.count(tmp) && !flag.count(tmp))
                    {
                        q.push(pii(tmp, now.second + 1));
                        flag.insert(tmp);
                    }
                }
            }
        }
        return 0;
    }
};

125.Valid Palindrome

做过刘汝佳 白书的人想必都知道ctype.h和isdigit(), isalpha(), tolower(), toupper()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool valid(char &x)
    {
        x = tolower(x);
        return isdigit(x) || isalpha(x);
    }
    bool isPalindrome(string s) {
        if(s.length() == 0) return true;
        for(int i = 0, j = s.length() - 1; i < j; i ++, j --)
        {
            while(!valid(s[i]) && i < s.length()) i ++; while(!valid(s[j]) && j >= 0) j --;
            if(i < j && s[i] != s[j]) return false;
        }
        return true;
    }
};

124.Binary Tree Maximum Path Sum

后续遍历，子问题为子树根节点向叶子节点出发的最大路径和。

即 l = DFS(now->left), r = DFS(now->right)。

此时，ans可能是 now->valid,可能是左边一路上来加上now->valid，可能是右边一路上来，也可能是左边上来经过now再右边一路下去，四种情况。

四种情况更新完ans后，now返回上一层只能是 now->valid或左边一路上来或右边一路上来，三种情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int ans;
    int DFS(TreeNode *now)
    {
        if(now == NULL) return 0;
        int l = max(DFS(now->left), 0);
        int r = max(DFS(now->right), 0);
        ans = max(ans, l + r + now->val);
        return max(l + now->val, r + now->val);
    }
    int maxPathSum(TreeNode *root) {
        if(root == NULL) return 0;
        ans = -0x3f3f3f3f;
        DFS(root);
        return ans;
    }
};

123.Best Time to Buy and Sell Stock III

前缀pre[i]处理 0 ~ i 买卖一次最优解，后缀suf[i]处理 i ~ prices.size() - 1 买卖一次最优解。

所有位置pre[i] + suf[i]最大值为答案O(n)。

处理最优解的时候是维护前（后）缀prices最小（大）值，与当前prices做差后和前（后）缀最优解比较取最优，O(n)。

总复杂度O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxProfit(vector &prices) {
        int ans = 0;
        vector pre(prices.size()), suf(prices.size());
        for(int i = 0, mtmp = 0x3f3f3f3f; i < prices.size(); i ++) 
        { 
           mtmp = i ? min(mtmp, prices[i]) : prices[i]; 
           pre[i] = max(prices[i] - mtmp, i ? pre[i - 1] : 0);
        } 
        for(int i = prices.size() - 1, mtmp = 0; i >= 0; i --)
        {
            mtmp = i != prices.size() - 1 ? max(mtmp, prices[i]) : prices[i];
            suf[i] = max(mtmp - prices[i], i != prices.size() - 1 ? suf[i + 1] : 0);
        }
        for(int i = 0; i < prices.size(); i ++)
            ans = max(ans, pre[i] + suf[i]);
        return ans;
    }
};

122.Best Time to Buy and Sell Stock II

可以买卖多次，把所有上坡差累加即可。

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int maxProfit(vector &prices) {
        int ans = 0;
        for(int i = 1; i < prices.size(); i ++) { if(prices[i] > prices[i - 1])
                ans += prices[i] - prices[i - 1];
        }
        return ans;
    }
};

121.Best Time to Buy and Sell Stock

维护前（后）缀最小（大）值，和当前prices做差更新答案。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxProfit(vector &prices) {
        int ans = 0;
        for(int i = prices.size() - 1, mtmp = 0; i >= 0; i --)
        {
            mtmp = max(mtmp, prices[i]);
            ans = max(mtmp - prices[i], ans);
        }
        return ans;
    }
};

120.Triangle

竟然遇到了ACM递推入门题，想必无数ACMer对这题太熟悉了。

从下往上递推，一维数组滚动更新即可。这里懒省事，直接把原数组改了。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int minimumTotal(vector &triangle) {
        for(int i = triangle.size() - 2; i >= 0; i --)
        {
            for(int j = 0; j < triangle[i].size(); j ++)
                triangle[i][j] = min(triangle[i][j] + triangle[i + 1][j], triangle[i][j] + triangle[i + 1][j + 1]);
        }
        return triangle.size() == 0 ? 0 : triangle[0][0];
    }
};

119.Pascal's Triangle II

滚动数组递推，从后往前以便不破坏上一层递推数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector getRow(int rowIndex) {
        vector ans(rowIndex + 1, 0);
        ans[0] = 1;
        for(int i = 0; i <= rowIndex; i ++) { for(int j = i; j >= 0; j --)
            {
                ans[j] = (i == 0 || j == 0 || j == i ? 1 : ans[j] + ans[j - 1]);
            }
        }
        return ans;
    }
};

118.Pascal's Triangle

递推。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector generate(int numRows) {
        vector v;
        for(int i = 0; i < numRows; i ++)
        {
            vector tmp;
            for(int j = 0; j <= i; j ++)
            {
                tmp.push_back(i == 0 || j == 0 || j == i ? 1 : v[i - 1][j] + v[i - 1][j - 1]);
            }
            v.push_back(tmp);
        }
        return v;
    }
};

117.Populating Next Right Pointers in Each Node II

题目要求空间复杂度O(1)，所以递归、队列等传统方法不应该用。

本题可以利用生成的next指针来横向扫描，即得到一层的next指针之后，可以利用这一层的next指针来给下一层的next指针赋值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    TreeLinkNode *findNext(TreeLinkNode *head)
    {
        while(head != NULL && head->left == NULL && head->right == NULL)
            head = head->next;
        return head;
    }
    void connect(TreeLinkNode *root) {
        if(root == NULL) return;
        TreeLinkNode *head, *last, *nexhead;
        for(head = root; head != NULL; head = nexhead)
        {
            head = findNext(head);
            if(head == NULL) break;
            if(head->left != NULL) nexhead = head->left;
            else nexhead = head->right;
            for(last = NULL; head != NULL; last = head, head = findNext(head->next))
            {
                if(head->left != NULL && head->right != NULL)
                    head->left->next = head->right;
                if(last == NULL) continue;
                if(last->right != NULL)

                    last->right->next = head->left != NULL ? head->left : head->right;
                else

                    last->left->next = head->left != NULL ? head->left : head->right;
            }
        }
    }
};

116.Populating Next Right Pointers in Each Node

不用考虑连续的空指针，就不用额外实现找下一个子树非空节点，比Populating Next Right Pointers in Each Node II 容易处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(root == NULL) return;
        TreeLinkNode *head, *nexhead, *last;
        for(head = root; head->left != NULL; head = nexhead)
        {
            nexhead = head->left;
            last = NULL;
            while(head != NULL)
            {
                head->left->next = head->right;
                if(last != NULL) last->right->next = head->left;
                last = head;
                head = head->next;
            }
        }
    }
};

115.Distinct Subsequences

典型动态规划。dp[i][j] 表示 T 的前 j 个字符在 S 的前 i 个字符中的解。

对于dp[i + 1][j + 1]，由两部分组成：

一、 j + 1 对应到 S 前 i 个字符中的解，忽略 S 的第 i + 1 个字符。

二、判断 S 的第 i + 1 个字符是否和 T 的第 j + 1 个字符相同，如果相同，则加上dp[i][j]，否则不加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int numDistinct(string S, string T) {
        if(S.length() < T.length()) return 0;
        vector dp(S.length() + 1, vector(T.length() + 1, 0));
        for(int i = 0; i < S.length(); i ++)
            dp[i][0] = 1;
        dp[0][1] = 0;
        for(int i = 0; i < S.length(); i ++)
        {
            for(int j = 0; j < T.length(); j ++)
            {
                dp[i + 1][j + 1] = dp[i][j + 1];
                if(S[i] == T[j]) dp[i + 1][j + 1] += dp[i][j];
            }
        }
        return dp[S.length()][T.length()];
    }
};

114.Flatten Binary Tree to Linked List

题意是优先左子树靠前，且排成一列用右子树指针，不管val的大小关系。

后序遍历一遍即可，递归返回子树中尾节点指针，注意各种条件判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *DFS(TreeNode *now)
    {
        if(now->left == NULL && now->right == NULL) return now;
        TreeNode *leftok = NULL, *rightok = NULL;
        if(now->left != NULL) leftok = DFS(now->left);
        if(now->right != NULL) rightok = DFS(now->right);
        if(leftok != NULL)
        {
            leftok->right = now->right;
            now->right = now->left;
            now->left = NULL;
            return rightok ? rightok : leftok;
        }
        else return rightok;
    }
    void flatten(TreeNode *root) {
        if(root == NULL) return;
        DFS(root);
    }
};

113.Path Sum II

传统递归，把路径上的数字插入vector，终点判断是否插入答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int goal;
    vectorv;
    vector curv;
    void DFS(TreeNode *now, int cursum)
    {
        curv.push_back(now->val);
        if(now->left == NULL && now->right == NULL)

        {
            if(cursum + now->val == goal)
            {
                v.push_back(curv);
                curv.pop_back();
                return;
            }
        }
        if(now->left != NULL) DFS(now->left, cursum + now->val);
        if(now->right != NULL) DFS(now->right, cursum + now->val);
        curv.pop_back();
    }
    vector pathSum(TreeNode *root, int sum) {
        goal = sum;
        if(root == NULL) return v;
        DFS(root, 0);
        return v;
    }
};

112.Path Sum

遍历树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int goal;
    bool DFS(TreeNode *now, int cursum)
    {
        if(now->left == NULL && now->right == NULL)
            return cursum + now->val == goal;
        if(now->left != NULL && DFS(now->left, cursum + now->val)) return true;
        if(now->right != NULL && DFS(now->right, cursum + now->val)) return true;
    }
    bool hasPathSum(TreeNode *root, int sum) {
        goal = sum;
        if(root == NULL) return false;
        return DFS(root, 0);
    }
};

111.Minimum Depth of Binary Tree

还是遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode *root) {
        if(root == NULL) return 0;
        if(root->left == NULL) return minDepth(root->right) + 1;
        else if(root->right == NULL) return minDepth(root->left) + 1;
        else return min(minDepth(root->left), minDepth(root->right)) + 1;
    }
};

110.Balanced Binary Tree

遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode *now)
    {
        if(now == NULL) return 0;
        int l = maxDepth(now->left) + 1;
        int r = maxDepth(now->right) + 1;
        return abs(l - r) > 1 || l < 0 || r < 0 ? -2 : max(l, r); } bool isBalanced(TreeNode *root) { return maxDepth(root) >= 0;
    }
};

109.Convert Sorted List to Binary Search Tree

每次找中点作为根节点，将两边递归，返回根节点指针作为左右节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *sortedListToBST(ListNode *head) {
        if(head == NULL) return NULL;
        ListNode *p, *mid, *pre;
        for(p = mid = head, pre = NULL; p->next != NULL; mid = mid->next)
        {
            p = p->next;
            if(p->next == NULL) break;
            p = p->next;
            pre = mid;
        };
        TreeNode *root = new TreeNode(mid->val);
        if(pre != NULL) pre->next = NULL, root->left = sortedListToBST(head);
        else root->left = NULL;
        root->right = sortedListToBST(mid->next);
        if(pre != NULL) pre->next = mid;
        return root;
    }
};

108.Convert Sorted Array to Binary Search Tree

递归做，比链表的容易些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *convert(vector &num, int left, int right)
    {
        if(right == left) return NULL;
        int mid = right + left >> 1;
        TreeNode *root = new TreeNode(num[mid]);
        root->left = convert(num, left, mid);
        root->right = convert(num, mid + 1, right);
    }
    TreeNode *sortedArrayToBST(vector &num) {
        return convert(num, 0, num.size());
    }
};

107.Binary Tree Level Order Traversal II

宽搜和深搜都可以，找对层数就行了。

本以为这题亮点是如何一遍实现从底向上顺序的vector，AC之后上网一查也全是最后把vector翻转的。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };

 */
class Solution {
public:
    vectorv;
    void DFS(TreeNode *now, int depth)
    {
        if(v.size() <= depth) v.push_back(vector(0)); v[depth].push_back(now->val);
        if(now->left != NULL) DFS(now->left, depth + 1);
        if(now->right != NULL) DFS(now->right, depth + 1);
    }
    vector levelOrderBottom(TreeNode *root) {
        if(root == NULL) return v;
        DFS(root, 0);
        for(int i = 0, j = v.size() - 1; i < j; i ++, j --)
            swap(v[i], v[j]);
        return v;
    }
};

106.Construct Binary Tree from Inorder and Postorder Traversal

数据结构经典题。后序遍历的结尾是根节点 Proot，在中序遍历中找到这个节点 Iroot，则 Iroot两边即为左右子树。根据左右子树节点个数，在后序遍历中找到左右子树分界（左右子树肯定不交叉），则几个关键分界点都找到了，对左右子树递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *build(vector &inorder, int ileft, int iright, vector &postorder, int pleft, int pright)
    {
        if(iright == ileft)
            return NULL;
        int root;
        for(root = ileft; inorder[root] != postorder[pright - 1]; root ++);
        TreeNode *node = new TreeNode(inorder[root]);
        node->left = build(inorder, ileft, root, postorder, pleft, pleft + root - ileft);
        node->right = build(inorder, root + 1, iright, postorder, pleft + root - ileft, pright - 1);
        return node;
    }
    TreeNode *buildTree(vector &inorder, vector &postorder) {
        return build(inorder, 0, inorder.size(), postorder, 0, postorder.size());
    }
};

105.Construct Binary Tree from Preorder and Inorder Traversal

和上一题Construct Binary Tree from Inorder and Postorder Traversal方法一样，前序和后序的信息作用相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *build(vector &inorder, int ileft, int iright, vector &preorder, int pleft, int pright)
    {
        if(iright == ileft)
            return NULL;
        int root;
        for(root = ileft; inorder[root] != preorder[pleft]; root ++);
        TreeNode *node = new TreeNode(inorder[root]);
        node->left = build(inorder, ileft, root, preorder, pleft + 1, pleft + root - ileft);
        node->right = build(inorder, root + 1, iright, preorder, pleft + root - ileft + 1, pright);
        return node;
    }
    TreeNode *buildTree(vector &preorder, vector &inorder) {
        return build(inorder, 0, inorder.size(), preorder, 0, preorder.size());

    }
};

104.Maximum Depth of Binary Tree

遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode *root) {
        if(root == NULL) return 0;
        if(root->left == NULL) return maxDepth(root->right) + 1;
        if(root->right == NULL) return maxDepth(root->left) + 1;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

103.Binary Tree Zigzag Level Order Traversal

BFS，奇偶层轮流走，一层左到右，一层右到左。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector ans;
    vector zigzagLevelOrder(TreeNode *root) {
        if(root == NULL) return ans;
        vector<TreeNode*> q1, q2;
        q1.push_back(root);
        int depth = 0;
        while(!q1.empty() || !q2.empty())
        {
            ans.push_back(vector(0));
            for(int i = q1.size() - 1; i >= 0; i --)
            {
                ans[depth].push_back(q1[i]->val);
                if(q1[i]->left != NULL) q2.push_back(q1[i]->left);
                if(q1[i]->right != NULL) q2.push_back(q1[i]->right);
            }
            depth ++;
            q1.clear();
            if(q2.empty()) continue;
            ans.push_back(vector(0));
            for(int i = q2.size() - 1; i >= 0; i --)
            {
                ans[depth].push_back(q2[i]->val);
                if(q2[i]->right != NULL) q1.push_back(q2[i]->right);
                if(q2[i]->left != NULL) q1.push_back(q2[i]->left);
            }
            q2.clear();
            depth ++;
        }
        return ans;
    }
};

102.Binary Tree Level Order Traversal

懒省事直接在上一题Binary Tree Zigzag Level Order Traversal的代码上改了一下。

只用一个队列的话，增加个层数信息存队列里即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector ans;
    vector levelOrder(TreeNode *root) {
 if(root == NULL) return ans;
        vector<TreeNode*> q1, q2;
        q1.push_back(root);
        int depth = 0;
        while(!q1.empty() || !q2.empty())
        {
            ans.push_back(vector(0));
            for(int i = 0; i < q1.size(); i ++) { ans[depth].push_back(q1[i]->val);
                if(q1[i]->left != NULL) q2.push_back(q1[i]->left);
                if(q1[i]->right != NULL) q2.push_back(q1[i]->right);
            }
            depth ++;
            q1.clear();
            if(q2.empty()) continue;
            ans.push_back(vector(0));
            for(int i = 0; i < q2.size(); i ++) { ans[depth].push_back(q2[i]->val);
                if(q2[i]->left != NULL) q1.push_back(q2[i]->left);
                if(q2[i]->right != NULL) q1.push_back(q2[i]->right);
            }
            q2.clear();
            depth ++;
        }
        return ans;
    }
};

101.Symmetric Tree

递归：左指针和右指针，对称递归，即(左的左)和(右的右)对应，(左的右)和(右的左)对应。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool judge(TreeNode *l, TreeNode *r)
    {
        if(l->val != r->val) return false;
        if(l->left != r->right && (l->left == NULL || r->right == NULL)
        || l->right != r->left && (l->right == NULL || r->left == NULL))
            return false;
        if(l->left != NULL && !judge(l->left, r->right)) return false;
        if(l->right != NULL && !judge(l->right, r->left)) return false;
        return true;
    }
    bool isSymmetric(TreeNode *root) {
        if(root == NULL) return true;
        if(root->left == NULL && root->right == NULL) return true;
        else if(root->left != NULL && root->right == NULL
            || root->left == NULL && root->right != NULL) return false;
        return judge(root->left, root->right);
    }
};

非递归：左右子树分别做一个队列，同步遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        if(root == NULL) return true;
        if(root->left == NULL && root->right == NULL) return true;
        else if(root->left != NULL && root->right == NULL
            || root->left == NULL && root->right != NULL) return false;
        queue q1, q2;
        q1.push(root->left);
        q2.push(root->right);
        while(!q1.empty())
        {
            TreeNode *now1 = q1.front(), *now2 = q2.front();
            q1.pop();
            q2.pop();
            if(now1->val != now2->val) return false;
            if(now1->left != NULL || now2->right != NULL)
            {
                if(now1->left == NULL || now2->right == NULL) return false;
                q1.push(now1->left);
                q2.push(now2->right);
            }
            if(now1->right != NULL || now2->left != NULL)
            {
                if(now1->right == NULL || now2->left == NULL) return false;
                q1.push(now1->right);
                q2.push(now2->left);
            }
        }
        return true;
    }
};

100.Same Tree

同步遍历，比较判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if(p == NULL && q == NULL) return true;
        if(p != q && (p == NULL || q == NULL) || p->val != q->val) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

99.Recover Binary Search Tree

中序遍历是二叉查找树的顺序遍历，a, b表示前驱节点和当前节点，因为只有一对数值翻转了，所以肯定会遇到前驱节点val比当前节点val大的情况一次或两次，遇到一次表示翻转的是相邻的两个节点。ans1和ans2指向两个被翻转的节点，当遇到前驱val比当前val大的情况时候，根据第一次还是第二次给ans1和ans2赋值，最终翻转回来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *a, *b;
    TreeNode *ans1, *ans2;
    bool DFS(TreeNode *now)
    {
        if(now->left != NULL)
            DFS(now->left);
        a = b;
        b = now;
        if(a != NULL && a->val > b->val)
        {
            if(ans1 == NULL) ans1 = a;
            ans2 = b;
        }
        if(now->right != NULL)
            DFS(now->right);
    }
    void recoverTree(TreeNode *root) {
        if(root == NULL) return;
        a = b = ans1 = ans2 = NULL;
        DFS(root);
        swap(ans1->val, ans2->val);
    }
};

98.Validate Binary Search Tree

中序遍历，更新前驱节点，与当前节点比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *pre = NULL;
    bool isValidBST(TreeNode *root) {
        if(root == NULL) return true;
        if(root->left != NULL && !isValidBST(root->left)) return false;
        if(pre != NULL && pre->val >= root->val) return false;
        pre = root;
        if(root->right != NULL && !isValidBST(root->right)) return false;
        return true;
    }
};

97.Interleaving String

动态规划。如果结果是true，则任意 i, j，s1[i] 之前的字符 和 s2[j]之前的字符，都能够交叉为 s3[i + j] 之前的字符。

由此，当dp[i][j]时，如果s1[i]==s3[i+j]，则尝试s1[i]与s3[i+j]对应，如果dp[i-1][j]是true，则dp[i][j]也为true。如果s2[j]==s3[i+j]则同样处理。

直到最后，判断dp[s1.length()-1][s2.length()-1]是否为true。为方便初始化，坐标后移了一位。

题目不厚道的出了s1.length()+s2.length() != s3.length()的数据，特判一下。

看到网上也都是O(n^2)的解法，我也就放心了。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if(s1.length() + s2.length() != s3.length())
            return false;
        vector dp(s1.length() + 1, vector(s2.length() + 1, false));
        for(int i = 0; i <= s1.length(); i ++)
            for(int j = 0; j <= s2.length(); j ++) 
            { 
               if(!i && !j) dp[i][j] = true; 
               dp[i][j] = dp[i][j] || i > 0 && s3[i + j - 1] == s1[i - 1] && dp[i - 1][j];
               dp[i][j] = dp[i][j] || j > 0 && s3[i + j - 1] == s2[j - 1] && dp[i][j - 1];
            }
        return dp[s1.length()][s2.length()];
    }
};

96.Unique Binary Search Trees II

LeetCode目前为止感觉最暴力的。递归遍历所有情况，每次返回子问题（左右子树）的vector的解，两层循环组合这些解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector generate(int start, int end)
    {
        vectorres;
        if(start > end)
        {
            TreeNode *tmp = NULL;
            res.push_back(tmp);
            return res;
        }
        for(int i = start; i <= end; i ++)
        {
            vector l = generate(start, i - 1), r = generate(i + 1, end);
            for(int j = 0; j < l.size(); j ++)
                for(int k = 0; k < r.size(); k ++) { TreeNode *tmp = new TreeNode(i); tmp->left = l[j];
                    tmp->right = r[k];
                    res.push_back(tmp);
                }
        }
        return res;
    }
    vector generateTrees(int n) {
        return generate(1, n);
    }
};

95.Unique Binary Search Trees

经典问题，卡特兰数，可递推，可用公式（公式用组合数，也要写循环）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int COM(int n, int m)
    {
        m = n - m < m ? n - m : m;
        int res, i, j;
        for(i = n, res = j = 1; i > n - m; i --)
        {
            res *= i;
            for(; j <= m && res % j == 0; j ++)
                res /= j;
        }
        return res;
    }
    int numTrees(int n) {
        return COM(n << 1, n) / (n + 1);

    }
};

94.Binary Tree Inorder Traversal

数据结构基础

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector res;
    void inorder(TreeNode *now)
    {
        if(now == NULL) return;
        inorder(now->left);
        res.push_back(now->val);
        inorder(now->right);
    }
    vector inorderTraversal(TreeNode *root) {
        inorder(root);
        return res;
    }
};

93.Restore IP Addresses

四层递归枚举分割位置，判断数字范围和前导零，处理字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector res;
    void DFS(string s, int last, int cur, string now)
    {
        if(cur == 3)
        {
            if(last == s.length()) return;
            string tmp = s.substr(last, s.length() - last);
            if(atoi(tmp.c_str()) <= 255 && (tmp.length() == 1 || tmp[0] != '0'))
                res.push_back(now + tmp);
            return;
        }
        string lin;
        for(int i = last; i < s.length(); i ++)
        {
            string tmp = s.substr(last, i - last + 1);
            if(atoi(tmp.c_str()) <= 255 && (tmp.length() == 1 || tmp[0] != '0'))
                DFS(s, i + 1, cur + 1, now + tmp + ".");
        }
    }
    vector restoreIpAddresses(string s) {
        DFS(s, 0, 0, "");
        return res;
    }
};

92.Reverse Linked List II

在表头添加一个(哨兵)会好写很多，额外的newhead可以帮助标记翻转之后更换了的头指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode *newhead = new ListNode(0);
        newhead->next = head;
        ListNode *pre = newhead, *p = head, *start = NULL;
        ListNode *tmp;
        for(int i = 1; p != NULL; i ++)
        {
            tmp = p->next;
            if(i == m)
                start = pre;
            if(i > m && i <= n) p->next = pre;
            if(i == n)
            {
                start->next->next = tmp;
                start->next = p;
            }
            pre = p;
            p = tmp;
        }
        tmp = newhead->next;
        free(newhead);
        return tmp;
    }
};

91.Decode Ways

递推：dp[i]表示前 i 个数字的解码种数。

`dp[i] = if(一)dp[i-1] + if(二)dp[i-2]``

当 i 位置不为0，可加上 i - 1位置的解。当当前位置和前一位置组成的两位数满足解码且高位不为0，可加上 i - 2 位置的解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int numDecodings(string s) {
        if(s.length() == 0) return 0;
        vector dp(s.length() + 1, 0);
        dp[0] = 1;
        for(int i = 0; i < s.length(); i ++) 
        { 
           dp[i + 1] = (s[i] != '0' ? dp[i] : 0) + 
               (i > 0 && s[i - 1] != '0' && atoi(s.substr(i - 1, 2).c_str()) <= 26 ? dp[i - 1] : 0);
        }
        return dp[s.length()];
    }
};

90.Subsets II

统计地存map里，map[i]= j 表示 S 中有 j 个 i。map是有序的，用迭代器递归枚举放入集合的个数。

也可以先排序，用set标记每个数时候被放入过，第一次放入之后才可以继续放同一个数。

代码是用map的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector res;
    vector now;
    map<int, int> mp;
    void DFS(map<int, int>::iterator i)
    {
        if(i == mp.end())
        {
            res.push_back(now);
            return;
        }
        map<int, int>::iterator tmp = i;
        i ++;
        DFS(i);
        for(int j = 0; j < tmp->second; j ++)
        {
            now.push_back(tmp->first);
            DFS(i);
        }
        for(int j = 0; j < tmp->second; j ++)
            now.pop_back();
    }
    vector subsetsWithDup(vector &S) {
        for(int i = 0; i < S.size(); i ++)
            !mp.count(S[i]) ? (mp[S[i]] = 1) : mp[S[i]] ++;
        DFS(mp.begin());
        return res;
    }
};

89.Gray Code

格雷码有多种生成方法，可参考维基百科 。

1
2
3
4
5
6
7
8
class Solution {
public:
    vector grayCode(int n) {
        vector res;
        for(int i = 0; i < (1 << n); i ++) res.push_back((i >> 1) ^ i);
        return res;
    }
};

88.Merge Sorted Array

从后往前，对 A 来说一个萝卜一个坑，肯定不会破坏前面的数据。具体看代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        int p = m + n - 1, i = m - 1, j = n - 1;
        for(; i >= 0 && j >= 0;)
        {
            if(A[i] > B[j]) A[p --] = A[i --];
            else A[p --] = B[j --];
        }
        while(i >= 0) A[p --] = A[i --];
        while(j >= 0) A[p --] = B[j --];
    }
};

87.Scramble String

直接搜索可以过，记忆化搜索可提高效率。

dp[i][j][k]表示从 s1[i] 和 s2[j] 开始长度为 k 的字符串是否是scrambled string。

枚举分割位置，scrambled string要求字符串对应字母的个数是一致的，可以直接排序对比。递归终点是刚好只有一个字母。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    string S1, S2;
    vector<vector > dp;
    bool judge(string a, string b)
    {
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        for(int i = 0; i < a.length(); i ++)
            if(a[i] != b[i]) return false;
        return true;
    }
    int DFS(int s1start, int s2start, int len)
    {
        int &ans = dp[s1start][s2start][len - 1];
        if(len == 1) return ans = S1[s1start] == S2[s2start];
        if(ans != -1) return ans;
        if(!judge(S1.substr(s1start, len), S2.substr(s2start, len)))
            return ans = 0;
        ans = 0;
        for(int i = 1; i < len; i ++)
        {
            ans = ans
            || DFS(s1start, s2start, i) && DFS(s1start + i, s2start + i, len - i)
            || DFS(s1start, s2start + len - i, i) && DFS(s1start + i, s2start, len - i);

        }
        return ans;
    }
    bool isScramble(string s1, string s2) {
        S1 = s1, S2 = s2;
        dp = vector<vector >
            (s1.length(), vector
                (s1.length(), vector
                    (s1.length(), -1)));
        return DFS(0, 0, s1.length());
    }
};

86.Partition List

分存大小最后合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        ListNode *shead, *bhead, *smaller, *bigger, *p;
        for(shead = bhead = smaller = bigger = NULL, p = head; p != NULL; p = p->next)
        {
            if(p->val < x) { if(shead == NULL) shead = p; if(smaller != NULL) smaller->next = p;
                smaller = p;
            }
            else
            {
                if(bhead == NULL)
                    bhead = p;
                if(bigger != NULL)
                    bigger->next = p;
                bigger = p;
            }
        }
        if(smaller != NULL) smaller->next = bhead;
        if(bigger != NULL) bigger->next = NULL;
        return shead != NULL ? shead : bhead;
    }
};

85.Maximal Rectangle

方法一：linecnt[i][j]统计第 i 行到第 j 位置有多少个连续的 '1'，接下来枚举列，每一列相当于一次直方图最大矩形统计，计算每个位置向前和向后最远的不少于当前位置值的位置，每次更新结果，总复杂度O(n^2)。

找(最远位置)用迭代指针，理论复杂度略高于O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    int maximalRectangle(vector &matrix) {
        if(matrix.size() == 0) return 0;
        int H = matrix.size(), W = matrix[0].size();
        int ans = 0;
        vector left(H), right(H);
        vector linecnt(H, vector(W, 0));
        for(int i = 0; i < H; i ++)
        {
            int last = 0;
            for(int j = 0; j < W; j ++)
            {
                if(matrix[i][j] == '1') last ++;
                else last = 0;
                linecnt[i][j] = last;
            }
        }
        for(int k = 0; k < W; k ++)
        {
            for(int i = 0; i < H; i ++) 
            { 
               if(i == 0) left[i] = -1; 
               else 
               { 
                   left[i] = i - 1; 
                   while(left[i] > -1 && linecnt[left[i]][k] >= linecnt[i][k])
                        left[i] = left[left[i]];
               }
            }
            for(int i = H - 1; i >= 0; i --)
            {
                if(i == H - 1) right[i] = H;
                else
                {
                    right[i] = i + 1;
                    while(right[i] < H && linecnt[right[i]][k] >= linecnt[i][k])
                        right[i] = right[right[i]];
                }
                ans = max(ans, (right[i] - left[i] - 1) * linecnt[i][k]);
            }
        }
        return ans;
    }
};

用单调栈，理论复杂度O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    int maximalRectangle(vector &matrix) {
        if(matrix.size() == 0) return 0;
        vector linecnt(matrix.size(), vector(matrix[0].size(), 0));
        for(int i = 0; i < matrix.size(); i ++)
        {
            int last = 0;
            for(int j = 0; j < matrix[0].size(); j ++)
            {
                if(matrix[i][j] == '1') last ++;
                else last = 0;
                linecnt[i][j] = last;
            }
        }
        int ans = 0;
        for(int k = 0; k < matrix[0].size(); k ++)
        {
            stack s, site;
            vectorlast(matrix.size());
            for(int i = 0; i < matrix.size(); i ++) { while(!s.empty() && s.top() >= linecnt[i][k])
                    s.pop(), site.pop();
                if(!s.empty()) last[i] = site.top() + 1;
                else last[i] = 0;
                s.push(linecnt[i][k]);
                site.push(i);
            }
            while(!s.empty()) s.pop(), site.pop();
            for(int i = matrix.size() - 1; i >= 0; i --)
            {
                while(!s.empty() && s.top() >= linecnt[i][k])
                    s.pop(), site.pop();
                if(!s.empty()) ans = max(ans, (site.top() - last[i]) * linecnt[i][k]);
                else ans = max(ans, (int)(matrix.size() - last[i]) * linecnt[i][k]);
                s.push(linecnt[i][k]);
                site.push(i);
            }
        }
        return ans;
    }
};

方法二：每个 1 的点当作一个矩形的底部，left[j]、right[j]、height[j]表示当前行第 j个位置这个点向左、右、上伸展的最大矩形的边界，作为滚动数组，下一行的数据可以由上一行结果得到，总复杂度O(n^2)。

left[j] = max(这一行最左, left[j]（上一行最左） );

right[j] = min(这一行最右，right[j]（上一行最右） );

height[j] = height[j - 1] + 1;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    int maximalRectangle(vector &matrix) {
        if(matrix.size() == 0) return 0;
        int H = matrix.size(), W = matrix[0].size();
        vector left(W, -1), right(W, W), height(W, 0);
        int ans = 0;
        for(int i = 0; i < H; i ++)
        {
            int last = -1;
            for(int j = 0; j < W; j ++) 
            { 
               if(matrix[i][j] == '1') 
               { 
                   if(last == -1) last = j; 
                   left[j] = max(left[j], last); 
                   height[j] ++;
               } 
               else 
               { 
                   last = -1; left[j] = -1; height[j] = 0; 
               } 
             } last = -1; 
             for(int j = W - 1; j >= 0; j --)
             {
                if(matrix[i][j] == '1')
                {
                    if(last == -1) last = j;
                    right[j] = min(right[j], last);
                    ans = max(ans, height[j] * (right[j] - left[j] + 1));
                }
                else
                {
                    last = -1;
                    right[j] = W;
                }
            }
        }
        return ans;
    }
};

84.Largest Rectangle in Histogram

参考上一题Maximal Rectangle方法一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int largestRectangleArea(vector &height) {
        if(height.size() == 0) return 0;
        vector left(height.size()), right(height.size());
        int ans = 0;
        for(int i = 0; i < height.size(); i ++) 
        { 
           if(i == 0) left[i] = -1; 
           else 
           { 
               left[i] = i - 1; 
               while(left[i] > -1 && height[i] <= height[left[i]])
                   left[i] = left[left[i]]; 
           } 
        } 
        for(int i = height.size() - 1; i >= 0; i --)
        {
            if(i == height.size() - 1) right[i] = height.size();
            else
            {
                right[i] = i + 1;
                while(right[i] < height.size() && height[i] <= height[right[i]])
                    right[i] = right[right[i]];
            }
            ans = max(ans, (right[i] - left[i] - 1) * height[i]);
        }
        return ans;
    }
};

83.Remove Duplicates from Sorted List II

加个表头乱搞吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if(head == NULL || head->next == NULL) return head;
        ListNode *newhead = new ListNode(0);
        newhead->next = head;
        for(ListNode *pre = newhead, *now = head, *nex = head->next; nex != NULL;)
        {
            if(now->val == nex->val)
            {
                while(nex != NULL && now->val == nex->val)
                {
                    free(now);
                    now = nex;
                    nex = nex->next;
                }
                free(now);
                pre->next = nex;
                if(nex == NULL) break;
            }
            else pre = now;
            now = nex;
            nex = nex->next;
        }
        head = newhead->next;
        free(newhead);
        return head;
    }
};

82.Remove Duplicates from Sorted List

直接操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if(head == NULL || head->next == NULL) return head;
        for(ListNode *pre = head, *p = head->next; p != NULL;)
        {
            while(p != NULL && pre->val == p->val)
            {
                pre->next = p->next;
                free(p);
                p = pre->next;
            }
            if(p == NULL) break;
            pre = p;
            p = p->next;
        }
        return head;
    }
};

81.Search in Rotated Sorted Array II

以mid为界，左右两边至少有一边是有序的。由于不可避免地会有O(n)的可能性，所以确定的时候二分，不确定的时候单位缩减边界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool search(int A[], int n, int target) {
        int left = 0, right = n - 1, mid;
        while(left < right) { mid = left + right >> 1;
            if(target < A[mid] && A[left] < target) right = mid;
            else if(target < A[right] && A[mid] < target) left = mid + 1;
            else
            {
                if(A[left] == target || A[right] == target) return true;
                else if(A[left] < target) left ++;
                else if(target < A[right]) right --;
                else return false;
            }
        }
        return A[left] == target ? true : false;
    }
};

80.Remove Duplicates from Sorted Array II

记下放了几个，多了不放。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        int i, j, cnt;
        for(i = j = cnt = 0; i < n; i ++)
        {
            if(j != 0 && A[j - 1] == A[i]) cnt ++;
            else cnt = 0;
            if(cnt < 2) A[j ++] = A[i];
        }
        return j;
    }
};

基础DFS。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    bool DFS(int x, int y, vector &board, string word, int ith)
    {
        if(board[x][y] != word[ith]) return false;
        if(ith == word.length() - 1) return true;
        board[x][y] = '.';
        for(int i = 0; i < 4; i ++) 
        { 
           int nx = x + dx[i]; int ny = y + dy[i]; 
           if(nx >= 0 && ny >= 0 && nx < board.size() && ny < board[0].size())
            {
                if(DFS(nx, ny, board, word, ith + 1))
                {
                    board[x][y] = word[ith];
                    return true;
                }
            }
        }
        board[x][y] = word[ith];
        return false;
    }
    bool exist(vector &board, string word) {
        for(int i = 0; i < board.size(); i ++)
        {
            for(int j = 0; j < board[0].size(); j ++)
            {
                if(DFS(i, j, board, word, 0)) return true;
            }
        }
        return false;
    }
};

78.Subsets

基础DFS。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector now;
    vector res;
    void DFS(vector &S, int ith)
    {
        if(ith == S.size())
        {
            res.push_back(now);
            return;
        }
        DFS(S, ith + 1);
        now.push_back(S[ith]);
        DFS(S, ith + 1);
        now.pop_back();
    }
    vector subsets(vector &S) {
        sort(S.begin(), S.end());
        DFS(S, 0);
        return res;
    }
};

77.Combinations

基础DFS。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector now;
    vector res;
    void DFS(int n, int ith, int sum, int k)
    {
        if(sum == k)
        {
            res.push_back(now);
            return;
        }
        if(sum + n - ith + 1 > k)
        {
            DFS(n, ith + 1, sum, k);
        }
        now.push_back(ith);
        DFS(n, ith + 1, sum + 1, k);
        now.pop_back();
    }
    vector combine(int n, int k) {
        DFS(n, 1, 0, k);
        return res;
    }
};

76.Minimum Window Substring

先统计 T 中各字符都有多少个，然后两个下标一前(i)一后(j)在 S 上跑， 当 i 跑到把 T 中字符都包含的位置时候，让 j 追到第一个包含 T 的字符的地方，更新结果，去掉 j 这个位置字符的统计，让 i 继续跑，如此反复。

i 和 j 都只遍历一遍 S，复杂度 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    string minWindow(string S, string T) {
        vector cnt(256, 0), need(256, 0);
        int sum = 0, len = 0x3f3f3f3f;
        string ans;
        for(int i = 0; i < T.size(); i ++)
            need[T[i]] ++;
        for(int i = 0, j = 0; i < S.length(); j ++)
        {
            while(i < S.length() && sum < T.length())
            {
                if(cnt[S[i]] < need[S[i]])
                    sum ++;
                cnt[S[i]] ++;
                i ++;
            }
            while(sum == T.length() && j < S.length())
            {
                cnt[S[j]] --;
                if(cnt[S[j]] < need[S[j]])
                    break;
                j ++;
            }
            if(sum < T.length()) break;
            if(i - j < len)
                ans = S.substr(j, i - j), len = i - j;
            sum --;
        }
        return ans;
    }
};

75.Sort Colors

轮流找：

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    void sortColors(int A[], int n) {
        int find = 0;
        for(int i = 0, j = n - 1; i < n; i ++) { if(A[i] == find) continue; while(j > i && A[j] != find) j --;
            if(j > i) swap(A[i], A[j]);
            else i --, j = n - 1, find ++;
        }
    }
};

找到哪个放哪个：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void sortColors(int A[], int n) {
        int p0, p1, p2;
        for(p0 = 0, p1 = p2 = n - 1; p0 < p1; )
        {
            if(A[p0] == 0) p0 ++;
            if(A[p0] == 1) swap(A[p0], A[p1 --]);
            if(A[p0] == 2)
            {
                swap(A[p0], A[p2 --]);
                p1 = p2;
            }
        }
    }
};

74.Search a 2D Matrix

写两个二分查找。或者把整个矩阵看作一维，直接二分，换算坐标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool searchMatrix(vector &matrix, int target) {
        int left, right, mid;
        for(left = 0, right = matrix.size(); left < right - 1; ) { mid = left + right >> 1;
            if(matrix[mid][0] > target)
                right = mid;
            else left = mid;
        }
        if(left == matrix.size() || right == 0) return false;
        vector &a = matrix[left];
        for(left = 0, right = a.size(); left < right - 1;) { mid = left + right >> 1;
            if(a[mid] > target) right = mid;
            else left = mid;
        }
        if(left == a.size() || right == 0) return false;
        return a[left] == target;
    }
};

73.Set Matrix Zeroes

O(m+n)的方法是容易想到的，而空间复杂度O(1)，只要利用原矩阵的一行和一列来使用O(m+n)的方法就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    void setZeroes(vector &matrix) {
        if(matrix.size() == 0) return;
        int x = -1, y = -1;
        for(int i = 0; i < matrix.size(); i ++)
        {
            for(int j = 0; j < matrix[0].size(); j ++)
            {
                if(matrix[i][j] == 0)
                {
                    if(x == -1)
                    {
                        x = i, y = j;
                    }
                    else
                    {
                        matrix[x][j] = 0;
                        matrix[i][y] = 0;
                    }
                }
            }
        }
        if(x == -1) return;
        for(int i = 0; i < matrix.size(); i ++)
            for(int j = 0; j < matrix[0].size(); j ++)
                if((matrix[x][j] == 0 || matrix[i][y] == 0) && (i != x && j != y))
                    matrix[i][j] = 0;
        for(int i = 0; i < matrix.size(); i ++) matrix[i][y] = 0;
        for(int j = 0; j < matrix[0].size(); j ++) matrix[x][j] = 0;
    }
};

72.Edit Distance

动态规划，先初始化 dp[i][0] 和 dp[0][i]，即每个字符串对应空串的编辑距离为串长度，之后对每个位置取子问题加上当前位置 改、删、增得解的最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minDistance(string word1, string word2) {
        vector dp(word1.length() + 1, vector(word2.length() + 1, 0));
        for(int i = 0; i < word1.length(); i ++) dp[i + 1][0] = i + 1;
        for(int i = 0; i < word2.length(); i ++) dp[0][i + 1] = i + 1;
        for(int i = 0; i < word1.length(); i ++)
            for(int j = 0; j < word2.length(); j ++)
            {
                if(word1[i] != word2[j])
                    dp[i + 1][j + 1] = min(dp[i][j] + 1, min(dp[i][j + 1] + 1, dp[i + 1][j] + 1));
                else
                    dp[i + 1][j + 1] = min(dp[i][j], min(dp[i][j + 1] + 1, dp[i + 1][j] + 1));
            }
        return dp[word1.length()][word2.length()];
    }
};

71.Simplify Path

好烦人的题，没什么好说的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    string simplifyPath(string path) {
        stack s;
        string str;
        for(int i = 0; i < path.length(); i ++)
        {
            if(path[i] == '/')
            {
                if(str == "..")
                {
                    if(!s.empty())

                        s.pop();
                }
                else if(str != "." && str != "")
                    s.push(str);
                str.clear();
            }
            else
                str += path[i];
        }
        if(str == "..")
        {
            if(!s.empty())
                s.pop();
        }
        else if(str != "." && str != "")
            s.push(str);
        if(s.empty()) return "/";
        for(str.clear(); !s.empty(); s.pop())
            str = "/" + s.top() + str;
        return str;
    }
};

70.Climbing Stairs

递推，就是斐波那契数列。

1
2
3
4
5
6
7
8
class Solution {
public:
    int climbStairs(int n) {
        return (int)
            (pow((1+sqrt(5))/2, n + 1) / sqrt(5) -
            pow((1-sqrt(5))/2, n + 1) / sqrt(5) + 0.1);
    }
};

69.Sqrt(x)

牛顿迭代。 设输入为n，f(x)=x^2-n，解就是f(x)=0时的x。 设猜了一数x[0]，那么在f(x)在x[0]处的切线与x轴的交点x[1]更接近目标解（可画图看看）。 那么递推下去，x[i]=(x[i-1]+n/x[i-1])/2，用double，越推越精确，直到自己想要的精度。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int sqrt(int x) {
        double now, last;
        if(x == 0) return 0;
        for(now = last = (double)x; ; last = now)
        {
            now = (last + (x / last)) * 0.5;
            if(fabs(last - now) < 1e-5) break;
        }
        return (int)(now + 1e-6);
    }
};

68.Text Justification

每行限制长度，空格均匀插入，不能完全平均的情况下优先靠前的单词间隔。

最后一行特别处理，单词间只有一个空格，剩下的放在末尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    vector fullJustify(vector &words, int L) {
        vector ans;
        int cnt = 0, i, j, k, l;
        for(i = 0, j = 0; j < words.size(); i ++)
        {
            if(i < words.size())
            {
                cnt += words[i].length();
                if(i == j) continue;
            }
            if(i == words.size() || (L - cnt) / (i - j) < 1)
            {
                int blank = 0;
                if(i < words.size())
                    blank = (i - j - 1) ? (L - cnt + words[i].length()) / (i - j - 1) : 0;
                string tmp = "";
                l = i < words.size() ? (L - cnt + words[i].length() - blank * (i - j - 1)) : 0;
                for(k = j; k < i; k ++, l --)
                {
                    tmp += words[k];
                    if(k != i - 1)
                    {
                        if(i != words.size())
                        {
                            for(int bl = 0; bl < blank; bl ++) tmp += " "; if(l > 0) tmp += " ";
                        }
                        else
                            tmp += " ";
                    }
                }
                while(tmp.length() < L) tmp += " ";
                ans.push_back(tmp);
                cnt = 0;
                j = i;
                i --;
            }
        }
        return ans;
    }
};

67.Plus One

大整数加法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector plusOne(vector &digits) {
        int cur, i;
        if(digits.size() == 0) return digits;
        for(i = digits.size() - 1, cur = 1; i >= 0; i --)
        {
            int tmp = digits[i] + cur;
            cur = tmp / 10;
            digits[i] = tmp % 10;
        }
        if(cur) digits.insert(digits.begin(), cur);
        return digits;
    }
};

66.Valid Number

用DFA也不麻烦，题目定义太模糊，为了理解规则错很多次也没办法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:

    int f[11][129];
    const int fail = -1;    //非法
    const int st = 0;       //起始
    const int pn = 1;       //正负号
    const int di = 2;       //整数部分
    const int del = 3;      //前面无数字小数点
    const int ddi = 4;      //小数部分
    const int ndel = 5;     //前面有数字小数点
    const int dibl = 6;     //数后空格
    const int ex = 7;       //进入指数
    const int epn = 8;      //指数符号
    const int edi = 9;      //指数数字
    const int end = 10;     //正确结束
    void buildDFA()
    {
        memset(f, -1, sizeof(f));
        f[st][' '] = st;
        f[st]['+'] = f[st]['-'] = pn;
        for(int i = '0'; i <= '9'; i ++)
        {
            f[st][i] = f[pn][i] = f[di][i] = di;
            f[del][i] = f[ndel][i] = f[ddi][i] = ddi;
            f[ex][i] = f[epn][i] = f[edi][i] = edi;
        }
        f[di]['.'] = ndel;
        f[st]['.'] = f[pn]['.'] = del;
        f[di][' '] = f[ndel][' '] = f[ddi][' '] = f[dibl][' '] = f[edi][' '] = dibl;
        f[di][0] = f[ndel][0] = f[dibl][0] = f[ddi][0] = f[edi][0] = end;
        f[di]['e'] = f[ndel]['e'] = f[ddi]['e'] = ex;
        f[ex][' '] = ex;
        f[ex]['+'] = f[ex]['-'] = epn;
    }
    bool DFA(const char *s)
    {
        int situ = st;
        for(int i = 0;; i ++)
        {
            situ = f[situ][s[i]];
            if(situ == end) return true;
            if(situ == fail) return false;
        }
        return true;
    }
    bool isNumber(const char *s) {
        buildDFA();
        return DFA(s);
    }
};

65.Add Binary

翻转，大整数加法，再翻转。无心情优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string addBinary(string a, string b) {
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        string c;
        int cur = 0, i;
        for(i = 0; i < min(a.length(), b.length()); i ++) { int tmp = a[i] - '0' + b[i] - '0' + cur; cur = tmp >> 1;
            c += (tmp & 1) + '0';
        }
        string &t = a.length() > b.length() ? a : b;
        for(; i < t.length(); i ++) { int tmp = t[i] - '0' + cur; cur = tmp >> 1;
            c += (tmp & 1) + '0';
        }
        if(cur) c += '1';
        reverse(c.begin(), c.end());
        return c;
    }
};

64.Minimum Path Sum

递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minPathSum(vector &grid) {
        if(grid.size() == 0) return 0;
        for(int i = 0; i < grid.size(); i ++)
        {
            for(int j = 0; j < grid[0].size(); j ++) { int tmp = 0x3f3f3f3f; if(i > 0) tmp = min(tmp, grid[i][j] + grid[i - 1][j]);
                if(j > 0) tmp = min(tmp, grid[i][j] + grid[i][j - 1]);
                grid[i][j] = tmp == 0x3f3f3f3f ? grid[i][j] : tmp;
            }
        }
        return grid[grid.size() - 1][grid[0].size() - 1];
    }
};

63.Unique Paths II

递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int uniquePathsWithObstacles(vector &obstacleGrid) {
        if(obstacleGrid.size() == 0) return 0;
        obstacleGrid[0][0] = obstacleGrid[0][0] != 1;
        for(int i = 0; i < obstacleGrid.size(); i ++)
            for(int j = 0; j < obstacleGrid[0].size(); j ++) { if(i == 0 && j == 0) continue; if(obstacleGrid[i][j] == 1) { obstacleGrid[i][j] = 0; continue; } if(i > 0)
                    obstacleGrid[i][j] += obstacleGrid[i - 1][j];
                if(j > 0)
                    obstacleGrid[i][j] += obstacleGrid[i][j - 1];
            }
        return obstacleGrid[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1];
    }
};

62.Unique Paths

这是当年学组合数时候的经典题型吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int COM(int a, int b)
    {
        b = min(b, a - b);
        int ret = 1, i, j;
        for(i = a, j = 1; i > a - b; i --)
        {
            ret *= i;
            for(; j <= b && ret % j == 0; j ++)
                ret /= j;
        }
        return ret;
    }
    int uniquePaths(int m, int n) {
        return COM(m + n - 2, m - 1);
    }
};

61.Rotate List

因为k可能比长度大，需要求长度然后k对长度取模。那么就不要矫情地追求双指针一遍扫描了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        if(head == NULL) return NULL;
        int cnt;
        ListNode *en, *p;
        for(cnt = 1, en = head; en->next != NULL; cnt ++, en = en->next);
        k %= cnt;
        for(p = head, cnt --; cnt != k; cnt --, p = p->next);
        en->next = head;
        en = p->next;
        p->next = NULL;
        return en;
    }
};

60.Permutation Sequence

一位一位算，每一位优先没使用过的较小的数字，而其后剩下的m个位置有 m! 种排列方法，用 k 减去，直到k不大于这个方法数，则这一位就是枚举到的这个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int permu[10];
    bool vis[10];
    string getPermutation(int n, int k) {
        permu[0] = 1;
        for(int i = 1; i < 10; i ++) permu[i] = permu[i - 1] * i;
        memset(vis, 0, sizeof(vis));
        string ans;
        for(int i = 1; i <= n; i ++)
        {
            for(int j = 1; j <= n; j ++) { if(!vis[j]) { if(k > permu[n - i])
                        k -= permu[n - i];
                    else 
                    {
                        ans += '0' + j;
                        vis[j] = true;
                        break;
                    }
                }
            }
        }
        return ans;
    }
};

59.Spiral Matrix II

直接算每个位置的数是多少有木有很霸气→_→。 先看当前位置之外有几个嵌套的正方形，再看当前位置在当前正方形四条边的第几条，求出坐标(x,y)位置的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector res;
    vector nsq;
    int calnum(int i, int j, int n)
    {
        int num, tmp;
        tmp = min(min(i, j), min(n - 1 - i, n - 1 - j));
        num = nsq[tmp];
        if(i == tmp) return num + j - tmp + 1;
        if(n - j - 1 == tmp) return num + n - 2 * tmp + i - tmp;
        if(n - i - 1 == tmp) return num + 2 * (n - 2 * tmp) - 2 + n - j - tmp;
        return num + 3 * (n - 2 * tmp) - 3 + n - i - tmp;
    }
    vector generateMatrix(int n) {
        nsq.push_back(0);
        for(int i = n; i > 0; i -= 2) nsq.push_back(4 * i - 4);
        for(int i = 1; i < nsq.size(); i ++) nsq[i] += nsq[i - 1];
        for(int i = 0; i < n; i ++)
        {
            vector tmp;
            for(int j = 0; j < n; j ++)
            {
                tmp.push_back(calnum(i, j, n));
            }
            res.push_back(tmp);
        }
        return res;
    }
};

58.Length of Last Word

从后往前找。

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int lengthOfLastWord(const char *s) {
        int i, j;
        for(i = strlen(s) - 1; i >= 0 && s[i] == ' '; i --);
        for(j = i - 1; j >= 0 && s[j] != ' '; j --);
        return i < 0 ? 0 : i - j;
    }
};

57.Insert Interval

end 比 newInterval 的 start 小的 intervals 直接插入，从 end 比 newInterval 的 start 大的 intervals 开始，到 start 比 newInterval 的 end 大的 intervals 结束，对这部分区间合并，再把之后的 intervals直接插入，特判 newInterval 最小和最大两种极端情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector res;
    vector insert(vector &intervals, Interval newInterval) {
        if(intervals.size() == 0) 
        {
            res.push_back(newInterval);
            return res;
        }
        int i, j;
        for(i = 0; i < intervals.size() && newInterval.start > intervals[i].end; i ++)
            res.push_back(intervals[i]);
        for(j = i; j < intervals.size() && newInterval.end >= intervals[j].start; j ++);
        if(j != 0 && i != intervals.size())
            res.push_back(Interval(min(intervals[i].start, newInterval.start),
                                max(intervals[j - 1].end, newInterval.end)));
        else
            res.push_back(newInterval);
        for(; j < intervals.size(); j ++)
            res.push_back(intervals[j]);
        return res;
    }
};

56.Merge Intervals

先按start排个序，然后慢慢合并。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector res;
    static bool cxompp(const Interval &a, const Interval &b)
    {return a.start < b.start;}
    vector merge(vector &intervals) {
        if(intervals.size() == 0) return res;
        sort(intervals.begin(), intervals.end(), cxompp);
        Interval last = intervals[0];
        for(int i = 1; i < intervals.size(); i ++) { if(last.end >= intervals[i].start)
                last.end = max(last.end, intervals[i].end);
            else
                res.push_back(last), last = intervals[i];
        }
        res.push_back(last);
        return res;
    }
};

55.Jump Game

维护最大可跳距离，每个位置都枚举一次。

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    bool canJump(int A[], int n) {
        if(n == 0) return false;
        int i, jumpdis;
        for(i = jumpdis = 0; i < n && jumpdis >= 0; i ++, jumpdis --)
            jumpdis = max(A[i], jumpdis);
        return i == n;
    }
};

54.Spiral Matrix

模拟转一遍吧。写了俩代码，差不多，处理拐弯的方式略有不同。

代码一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};
    vector res;
    bool JudgeValid(int x, int y,
        vector &vis, vector &matrix)
    {
        return x >= 0 && x < matrix.size() && y >= 0 && y < matrix[0].size() && 
           vis[x][y] == false;
    }
    vector spiralOrder(vector &matrix) {
        int dir, x, y, nx, ny;
        if(matrix.size() == 0) return res;

        vector vis(matrix.size(), vector(matrix[0].size(), false));
        for(dir = x = y = 0; JudgeValid(x, y, vis, matrix); x = nx, y = ny)
        {
            res.push_back(matrix[x][y]);
            vis[x][y] = true;
            nx = x + dx[dir];
            ny = y + dy[dir];
            if(!JudgeValid(nx, ny, vis, matrix))
            {
                dir = (dir + 1) % 4;
                nx = x + dx[dir];
                ny = y + dy[dir];
            }
        }
        return res;
    }
};

代码二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};
    vector res;
    vector spiralOrder(vector &matrix) {
        int dir, x, y, nx, ny;
        int l, r, u, d;
        if(matrix.size() == 0) return res;

        l = u = -1;
        r = matrix[0].size();
        d = matrix.size();
        for(dir = x = y = 0; res.size() < matrix.size() * matrix[0].size();
            x = nx, y = ny)
        {
            res.push_back(matrix[x][y]);
            nx = x + dx[dir];
            ny = y + dy[dir];
            if(nx == d || nx == u || ny == r || ny == l)
            {
                dir = (dir + 1) % 4;
                if(dir == 0) l ++, r --, d --;
                else if(dir == 3) u ++;
                nx = x + dx[dir];
                ny = y + dy[dir];
            }
        }
        return res;
    }
};

53.Maximum Subarray

最大子串和，子串要求至少包含一个数字。

一个变量 sum 表示当前求得的子串和，当 sum 小于0时，对后面的子串没有贡献，则把 sum 置零，中间处理一下要求至少包含一个数字的要求即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxSubArray(int A[], int n) {
        int ans = A[0], sum = 0;
        for(int i = 0; i < n; i ++)
        {
            sum += A[i];
            if(sum < 0)
                sum = 0, ans = max(ans, A[i]);
            else ans = max(ans, sum);
        }
        return ans;
    }
};

52.N-Queens II

题目没说 n 的取值范围，就不用 位运算 做标记了。

老老实实开三个 bool 数组，一个标记纵列，另外两个标记两个斜列，一行一行DFS。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector col, lc, rc;
    int ans;
    void DFS(int cur, int n)
    {
        if(cur == n)
        {
            ans ++;
            return;
        }
        for(int i = 0; i < n; i ++)
        {
            if(!col[i] && !lc[n - cur - 1 + i] && !rc[cur + i])
            {
                col[i] = lc[n - cur - 1 + i] = rc[cur + i] = true;
                DFS(cur + 1, n);
                col[i] = lc[n - cur - 1 + i] = rc[cur + i] = false;
            }
        }
    }
    int totalNQueens(int n) {
        ans = 0;
        col.resize(n, 0);
        lc.resize(n << 1, 0);
        rc.resize(n << 1, 0);
        DFS(0, n);
        return ans;
    }
};

51.N-Queens

同上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    vector tmp;
    vector res;
    vector col, lc, rc;
    void DFS(int cur, int n)
    {
        if(cur == n)
        {
            res.push_back(tmp);
            return;
        }
        string now(n, '.');
        for(int i = 0; i < n; i ++)
        {
            if(!col[i] && !lc[n - cur - 1 + i] && !rc[cur + i])
            {
                col[i] = lc[n - cur - 1 + i] = rc[cur + i] = true;
                now[i] = 'Q';
                tmp.push_back(now);
                DFS(cur + 1, n);
                tmp.pop_back();
                now[i] = '.';
                col[i] = lc[n - cur - 1 + i] = rc[cur + i] = false;
            }
        }
    }
    vector solveNQueens(int n) {
        col.resize(n, 0);
        lc.resize(n << 1, 0);
        rc.resize(n << 1, 0);
        DFS(0, n);
        return res;
    }
};

50.Pow(x, n)

很多人用特判错过了 n=-2147483648 这么优美的 trick，而不特判的话，似乎只能 long long 了。

经典的快速幂，用二进制理解也好，用折半理解也好，网上很多资料。

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    double pow(double x, int n) {
        double res = 1;
        long long nn = n;
        if(nn < 0) x = 1 / x, nn = -nn; while(nn) { if(nn & 1) res *= x; x *= x; nn >>= 1;
        }
        return res;
    }
};

49.Anagrams

这概念以前没听过诶。。题也没看到样例，不知道以后会不会更新，网上查了才明白啥意思。

调换单词字母顺序能一致的单词集合全放进答案。比如有tea, eat, aet，就都要放进答案，有cat, atc，就都要放进答案，而如果孤零零有个dog，没其他可和他一组的，那么就不放进答案。

手写hash能更快些，但是题目没给数据范围，给hash数组定多大都没合理性，干脆用unordered_map好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector res;
    vector anagrams(vector &strs) {
        unordered_map<string, int> mp;
        for(int i = 0; i < strs.size(); i ++)
        {
            string tmp = strs[i];
            sort(tmp.begin(), tmp.end());
            if(!mp.count(tmp)) mp[tmp] = 0;
            else mp[tmp] ++;
        }
        for(int i = 0; i < strs.size(); i ++) { string tmp = strs[i]; sort(tmp.begin(), tmp.end()); if(mp.count(tmp) && mp[tmp] > 0)
                res.push_back(strs[i]);
        }
        return res;
    }
};

48.Rotate Image

四个一组，就地旋转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void rotate(vector &matrix) {
        if(matrix.size() == 0) return;
        int len = matrix.size();
        int lenlimi = len + 1 >> 1;
        for(int i = 0; i < lenlimi; i ++)
            for(int j = 0; j < (len & 1 ? lenlimi - 1 : lenlimi); j ++)
            {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[len - j - 1][i];
                matrix[len - j - 1][i] = matrix[len - i - 1][len - j - 1];
                matrix[len - i - 1][len - j - 1] = matrix[j][len - i - 1];
                matrix[j][len - i - 1] = tmp;
            }
    }
};

47.Permutations II

有重复数字，把数字统计起来好了。因为题目没说数字大小，所以统计用了unordered_map。

也可以把数组排序，DFS时跳过重复的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    unordered_map<int, int> mp;
    vector tmp;
    vector res;
    int numsize;
    void DFS(int cnt)
    {
        if(cnt == numsize)
        {
            res.push_back(tmp);
        }
        for(unordered_map<int, int>::iterator it = mp.begin(); it != mp.end(); it ++)
        {
            if(it->second != 0)
            {
                tmp.push_back(it->first);
                it->second --;
                DFS(cnt + 1);
                tmp.pop_back();
                it->second ++;
            }
        }
    }
    vector permute(vector &num) {
        numsize = num.size();
        for(int i = 0; i < num.size(); i ++)
        {
            if(!mp.count(num[i])) mp[num[i]] = 1;
            else mp[num[i]] ++;
        }
        DFS(0);
        return res;
    }
};

46.Permutations

虽然题目没说有没有重复数字。。既然 Permutations II 说有了，那就当这个没有吧。

传统DFS。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector res;
    void DFS(int cur, vector &num)
    {
        if(cur == num.size())
        {
            res.push_back(num);
            return;
        }
        for(int i = cur; i < num.size(); i ++)
        {
            swap(num[cur], num[i]);
            DFS(cur + 1, num);
            swap(num[cur], num[i]);
        }
    }
    vector permute(vector &num) {
        DFS(0, num);
        return res;
    }
};

45.Jump Game II

维护一步最远到达的位置，到达这个位置之前的位置需要的步数都是一样的，到达这个位置的时候，下一步的最远位置已经更新完毕。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int jump(int A[], int n) {
        int nex = 0, pace = 0, far = 0;
        for(int i = 0; i <= nex && i < n - 1; i ++)
        {
            far = max(far, A[i] + i);
            if(i == nex)
            {
                pace ++;
                nex = far;
            }
        }
        return pace;
    }
};

44.Wildcard Matching

同步扫描两个字符串，每当 p 遇到 * ，记录s和p的当前扫描位置，当 s 与 p 不匹配时，跑扫描指针回到 * 后一个字符， s 扫描指针回到上次遇到 * 之后与 p 开始匹配位置的下一个位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int last_star = -1, last_s = -1, i, j;
        for(i = j = 0; s[i]; )
        {
            if(s[i] == p[j] || p[j] == '?') i ++, j ++;
            else if(p[j] == '*') last_star = ++ j, last_s = i;
            else if(last_star != -1) i = ++ last_s, j = last_star;
            else return false;
        }
        while(p[j] == '*') j ++;
        return !s[i] && !p[j];
    }
};

43.Multiply Strings

翻转num1和num2，大整数乘法，把结果再翻转。注意 int 和 char 的转换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string multiply(string num1, string num2) {
        string ans(num1.length() + num2.length() + 1, 0);
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        int cur = 0, i, j, k;
        for(i = 0; i < num1.length(); i ++)
        {
            for(j = 0; j < num2.length(); j ++) { ans[i + j] += cur + (num1[i] - '0') * (num2[j] - '0'); cur = ans[i + j] / 10; ans[i + j] %= 10; } for(k = i + j; cur; k ++) { ans[k] += cur; cur = ans[k] / 10; ans[k] %= 10; } } for(k = ans.length() - 1; k > 0 && ans[k] == 0; k --);
        ans.resize(k + 1);
        for(int i = 0; i < ans.length(); i ++)
            ans[i] += '0';
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

42.Trapping Rain Water

对于每个位置，取这个位置左边最高的和右边最高的的较低者，如果较低者比这个位置高，则这个位置存水高度为较低者减该位置高度。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int trap(int A[], int n) {
        vector pre;
        int i, maxheight, ans;
        for(i = maxheight = 0; i < n; i ++) { maxheight = max(A[i], maxheight); pre.push_back(maxheight); } for(maxheight = ans = 0, i = n - 1; i > 0; i --)
        {
            maxheight = max(A[i], maxheight);
            ans += max(0, min(pre[i] - A[i], maxheight - A[i]));
        }
        return ans;
    }
};

41.First Missing Positive

题目要求时间O(n)，空间O(1)，经分析，不得不破坏原数组 A。

方法一：

剔除非整数，把原数组 A 当作存在标记，存在的数 x 则 A[x-1]取负数。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        int i, j;
        for(i = j = 0; i < n; i ++) if(A[i] > 0)
                A[j ++] = A[i];
        for(i = 0; i < j; i ++)
            if(abs(A[i]) <= j)
                A[abs(A[i]) - 1] = -abs(A[abs(A[i]) - 1]);
        for(i = 0; i < j; i ++) if(A[i] > 0) return i + 1;
        return j + 1;
    }
};

方法二：把出现的符合范围的数swap到下标和数对应的位置，再次遍历，数和下标不对应则是第一个没出现的数。注意处理有重复数字。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        int i;
        for(i = 0; i < n; i ++)
            while(A[i] <= n && A[i] > 0 && A[i] != i + 1 && A[A[i] - 1] != A[i])
                swap(A[i], A[A[i] - 1]);
        for(i = 0; i < n; i ++)
            if(A[i] != i + 1) return i + 1;
        return i + 1;
    }
};

40.Combination Sum

基础DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector tmp;
    vector ans;
    void DFS(vector &num, int ith, int now, int target)
    {
        if(now == target)
        {
            ans.push_back(tmp);
            return;
        }
        if(ith == num.size()) return;
        int cnt = 0;
        while(now <= target)
        {
            DFS(num, ith + 1, now, target);
            now += num[ith];
            cnt ++;
            tmp.push_back(num[ith]);
        }
        while(cnt --) tmp.pop_back();
    }
    vector combinationSum(vector &candidates, int target) {
        sort(candidates.begin(), candidates.end());
        DFS(candidates, 0, 0, target);
        return ans;
    }
};

39.Combination Sum II

如果一个数没有被用，那么后面重复的这个数就别用，避免重复解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector tmp;
    vector ans;
    void DFS(vector &num, int ith, int now, int target)
    {
        if(now == target)
        {
            ans.push_back(tmp);
            return;
        }
        if(ith == num.size()) return;
        int nex;
        for(nex = ith + 1; nex < num.size() && num[nex] == num[ith]; nex ++);
        DFS(num, nex, now, target);
        if(num[ith] + now <= target)
        {
            now += num[ith];
            tmp.push_back(num[ith]);
            DFS(num, ith + 1, now, target);
            tmp.pop_back();
        }
    }
    vector combinationSum2(vector &num, int target) {
        sort(num.begin(), num.end());
        DFS(num, 0, 0, target);
        return ans;
    }
};

38.Count and Say

直接模拟，递推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string countAndSay(int n) {
        string f[2];
        f[0] = "1";
        for(int i = 1; i < n; i ++)
        {
            f[i & 1].clear();
            for(int j = 0; j < f[i & 1 ^ 1].length();)
            {
                int cnt;
                char x = f[i & 1 ^ 1][j];
                for(cnt = 0; j < f[i & 1 ^ 1].length() && f[i & 1 ^ 1][j] == x; cnt ++, j ++);
                f[i & 1] += '0' + cnt;
                f[i & 1] += x;
            }
        }
        return f[n & 1 ^ 1];
    }
};

37.Sudoku Solver

这道题考察回溯和数独结果的判断。ACM做过，就直接拿dancing links代码了，4ms。

关于dancing links，对于面试题来说变态了些，应该不至于考察。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
class Solution {
public:
    int rw[10], cl[10], in[10], RW[81], CL[81], IN[81], goal;
    char buf[100];
    void Mark(int i, int num)
    {
        rw[RW[i]] ^= 1 << num;
        cl[CL[i]] ^= 1 << num;
        in[IN[i]] ^= 1 << num;
    }
    void init()
    {
        int i;
        for(i = 0; i < 10; ++ i)
            cl[i] = rw[i] = in[i] = 0;
        for(i = goal = 0; buf[i]; ++ i)
            goal += buf[i] == '.';
        for(i = 0; i < 81; ++ i)
        {
            RW[i] = i / 9, CL[i] = i % 9, IN[i] = i / 3 % 3 + i / 27 * 3;
            if(buf[i] != '.')
                Mark(i, buf[i] - '1');
        }
    }
    inline int Judge(int i, int num)
    {return ~(rw[RW[i]] | cl[CL[i]] | in[IN[i]]) & (1 << num);}
    int Oper(int sx, int k, int cur)
    {
        Mark(sx, k), buf[sx] = k + '1';
        if(dfs(cur + 1)) return 1;
        Mark(sx, k), buf[sx] = '.';
        return 0;
    }
    int JudgeRWCLIN(int cur)
    {
        int i, j, k, x, cnt, sx;
        for(i = 0; i < 9; ++ i)
            for(k = 0; k < 9; ++ k)
            {
                if(~rw[i] & (1 << k))
                {
                    for(j = cnt = 0; j < 9; ++ j)
                    {
                        x = i * 9 + j;
                        if(buf[x] == '.' && Judge(x, k)) ++ cnt, sx = x;
                    }
                    if(cnt == 0) return 0;
                    else if(cnt == 1)
                        return Oper(sx, k, cur);
                }
                if(~cl[i] & (1 << k))
                {
                    for(j = cnt = 0; j < 9; ++ j)
                    {
                        x = j * 9 + i;
                        if(buf[x] == '.' && Judge(x, k)) ++ cnt, sx = x;
                    }
                    if(cnt == 0) return 0;
                    else if(cnt == 1)
                        return Oper(sx, k, cur);
                }
                if(~in[i] & (1 << k))
                {
                    for(j = cnt = 0; j < 9; ++ j)
                    {
                        x = i / 3 * 27 + j / 3 * 9 + i % 3 * 3 + j % 3;
                        if(buf[x] == '.' && Judge(x, k)) ++ cnt, sx = x;
                    }
                    if(cnt == 0) return 0;
                    else if(cnt == 1)
                        return Oper(sx, k, cur);
                }
            }
        return 2;
    }

    bool dfs(int cur)
    {
        int i, j, num, cnt;
        if(cur == goal) return true;
        for(i = 0; i < 81; ++ i)
            if(buf[i] == '.')
            {
                for(j = cnt = 0; j < 9; ++ j)
                    if(Judge(i, j)) ++ cnt, num = j;
                if(cnt == 0) return false;
                if(cnt == 1)
                        return Oper(i, num, cur);
            }
        if((num = JudgeRWCLIN(cur)) == 0) return false;
        else if(num == 1) return true;
        for(i = 0; i < 81; ++ i)
            if(buf[i] == '.')
            {
                for(j = 0; j < 9; ++ j)
                    if(Judge(i, j))
                    {
                        Mark(i, j), buf[i] = j + '1';
                        if(dfs(cur + 1)) return true;
                        Mark(i, j), buf[i] = '.';
                    }
            }
        return false;
    }
    void solveSudoku(vector &board) {
        int site = 0;
        for(int i = 0; i < 9; i ++)
            for(int j = 0; j < 9; j ++)
                buf[site ++] = board[i][j];
        init();
        dfs(0);
        site = 0;
        for(int i = 0; i < 9; i ++)
            for(int j = 0; j < 9; j ++)
                board[i][j] = buf[site ++];
    }
};

36.Valid Sudoku

行列九宫格都判断一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isValidSudoku(vector &board) {
        bool flag[3][9][9];
        memset(flag, false, sizeof(flag));
        for(int i = 0; i < 9; i ++)
        {
            for(int j = 0; j < 9; j ++)
            {
                if(board[i][j] != '.')
                {
                    int x = board[i][j] - '1';
                    if(flag[0][i][x] == true) return false;
                    flag[0][i][x] = true;
                    if(flag[1][j][x] == true) return false;
                    flag[1][j][x] = true;
                    if(flag[2][i / 3 * 3 + j / 3][x] == true) return false;
                    flag[2][i / 3 * 3 + j / 3][x] = true;
                }
            }
        }
        return true;
    }
};

35.Search Insert Position

二分

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        int left, right, mid;
        for(left = 0, right = n; left < right; ) { mid = left + right >> 1;
            if(A[mid] == target) return mid;
            if(A[mid] > target) right = mid;
            else left = mid + 1;
        }
        return left;
    }
};

34.Search for a Range

二分，容易错。可以用lower_bound和upper_bound。

手工代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector searchRange(int A[], int n, int target) {
        int left, right, mid, l, r;
        for(left = 0, right = n; left < right; ) { mid = left + right >> 1;
            if(A[mid] >= target) right = mid;
            else left = mid + 1;
        }
        l = left;
        for(left = 0, right = n; left < right; ) { mid = left + right >> 1;
            if(A[mid] > target) right = mid;
            else left = mid + 1;
        }
        r = left - 1;
        if(l >= n || A[l] != target) return vector(2, -1);
        vector ans = {l, r};
        return ans;
    }
};

STL：

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    vector searchRange(int A[], int n, int target) {
        int l = lower_bound(A, A + n, target) - A;
        int r = upper_bound(A, A + n, target) - A;
        if(l == n || A[l] != target) return vector(2, -1);
        vector ans = {l, r - 1};
        return ans;
    }
};

33.Search in Rotated Sorted Array

还是二分，但是要判断一下 mid 在哪部分里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int search(int A[], int n, int target) {
        int left = 0, right = n - 1, mid;
        while(left < right) { mid = left + right >> 1;
            if(A[mid] == target) return mid;
            if(A[mid] >= A[left])
            {
                if(target < A[mid] && A[left] <= target) right = mid;
                else left = mid + 1;
            }
            else
            {
                if(target <= A[right] && A[mid] < target) left = mid + 1;
                else right = mid;
            }
        }
        return A[left] == target ? left : -1;
    }
};

32.Longest Valid Parentheses

这道题时间限制在O(n)，用一个 stack 实现括号配对+统计, 为了方便实现，写成数组的形式。

对不同深度的括号配对统计个数，一层配对成功把该层统计结果加给上一层，这一层清空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int longestValidParentheses(string s) {
        vector cnt(1, 0);
        int i, ans;
        for(i = ans = 0; i < s.length(); i ++) { if(s[i] == '(') cnt.push_back(0); else { if(cnt.size() > 1)
                {
                    cnt[cnt.size() - 2] += *cnt.rbegin() + 2;
                    cnt.pop_back();
                    ans = max(ans, *cnt.rbegin());
                }
                else
                    cnt[0] = 0;
            }
        }
        return ans;
    }
};

31.Next Permutation

从后往前找到第一个非降序的 num[i]，再重新从后往前找到第一个比 num[i] 大的，swap(num[i], num[j])，再把 i 之后的排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    void nextPermutation(vector &num) {
        int i, j;
        for(i = num.size() - 2; i >= 0 && num[i] >= num[i + 1]; i --);
        for(j = num.size() - 1; j > i && num[j] <= num[i]; j --);
        if(i < j)
        {
            swap(num[i], num[j]);
            sort(num.begin() + i + 1, num.end());
        }
        else
            reverse(num.begin(), num.end());
    }
};

30.Substring with Concatenation of All Words

直观的方法是枚举起点，判断这个起点下的子串是否合法，O(S.length()*L.size())。

其实可以把 S 分成 L[0].length() 个序列，每个序列都是元素间相隔 L[0].length() 的(string开头)，这些序列互不相干。

如下表，假设 L[0].length()=4，第一行数字为分组组号，第二行数字表示 S 的序号。 

1
2
(0)|(1)|(2)|(3)|(0)|(1)|(2)|(3)|(0)|(1)|(2)|(3)|(0)|(1)|(2)|(3)|(0)|(1)|(2)|(3)|(0)|
 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16| 17| 18| 19| 20|
对每个序列，用单调队列的思路来处理，一个一个子串入队，当包含了 L 中所有 string 的时候，保存答案。当新元素入队时超出统计允许时————即 L 中有 3 个 "str", 而这时候遇到第 4 个————则开始出队，一直出到队列里不足 3 个 "str"，然后继续。

这样复杂度为O(L[0].length() * S.length() / L[0].length()) = O(S.length())。目前提交结果是180ms。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
public:
    vector findSubstring(string S, vector &L) {
        vector ans;
        if(L.size() == 0) return ans;
        unordered_map<string, int> mp, sum;
        int llen = L[0].length(), i, front, rear;
        for(int i = 0; i < L.size(); i ++)
        {
            if(!mp.count(L[i])) mp[L[i]] = 1;
            else mp[L[i]] ++;
        }
        for(i = 0; i < llen; i ++)
        {
            sum = mp;
            int cnt = 0;
            for(front = rear = i; front + llen <= S.length(); front += llen) { 
               string tmp = S.substr(front, llen); 
               if(sum.count(tmp)) 
               {
                    if(sum[tmp] > 0)
                    {
                        sum[tmp] --;
                        cnt ++;
                        if(cnt == L.size())
                        {
                            ans.push_back(rear);
                        }
                    }
                    else
                    {
                        while(sum[tmp] == 0)
                        {
                            string ntmp = S.substr(rear, llen);
                            sum[ntmp] ++;
                            cnt --;
                            rear += llen;
                        }
                        sum[tmp] --;
                        cnt ++;
                        if(cnt == L.size())
                        {
                            ans.push_back(rear);
                        }
                    }
                }
                else
                {
                    while(rear < front)
                    {
                        string ntmp = S.substr(rear, llen);
                        sum[ntmp] ++;
                        cnt --;
                        rear += llen;
                    }
                    rear += llen;
                    cnt = 0;
                }
            }
        }
        return ans;
    }
};

29.Divide Two Integers

假设 dividend 与 divisor 正负一致， divisor^(2^n) 为最接近 dividend 的 divisor 的幂，那么令 newdividend = dividend - divisor^(2^n)，ans = ans + 2^n，问题就更新为 newdividend 除以 divisor，如此迭代。用 divisor(2n) 是因为 divisor 不停地辗转加自己就可以得到了。

有 -2147483648 这样的极限数据，因为 int 范围是 -2147483648~+2147483647，发现负数比正数范围(多1)，干脆把所有数都转成负数算，这样就避免用 long long 了。最后考察一下flag。

（如果转成正数的话，int 的 -(-2147483648)还是 -2147483648。。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int divide(int dividend, int divisor) {
        bool flag = false;
        if(divisor > 0) divisor = -divisor, flag ^= true;
        if(dividend > 0) dividend = -dividend, flag ^= true;
        int ans = 0, res = divisor, ex = 1;
        if(divisor < dividend) return 0; while(res >= dividend - res)
        {
            res += res;
            ex += ex;
        }
        while(res <= divisor && dividend) { if(res >= dividend)
            {
                dividend -= res;
                ans += ex;
            }
            res >>= 1;
            ex >>= 1;
        }
        return flag ? -ans : ans;
    }
};

28.Implement strStr()

KMP。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    char *strStr(char *haystack, char *needle) {
        int hlen = (int)strlen(haystack), nlen = (int)strlen(needle);
        if(nlen == 0) return haystack;
        vector next(nlen + 1);
        next[0] = -1;
        for(int i = 0, j = -1; i < nlen;)
        {
            if(j == -1 || needle[i] == needle[j])
            {
                i ++, j ++;
                if(needle[i] != needle[j]) next[i] = j;
                else next[i] = next[j];
            }
            else j = next[j];
        }
        for(int i = 0, j = 0; i < hlen;)
        {
            if(j == -1 || haystack[i] == needle[j])
                i ++, j ++;
            else j = next[j];
            if(j == nlen) return haystack + i - j;
        }
        return NULL;
    }
};

27.Remove Element

两个游标 i, j 异步挪动，把不等于给定值的数往前挪。

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int removeElement(int A[], int n, int elem) {
        int i, j;
        for(i = j = 0; i < n; i ++)
            if(A[i] != elem) A[j ++] = A[i];
        return j;
    }
};

26.Remove Duplicates from Sorted Array

两个游标 i, j 异步挪动，不重复值往前挪。

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        int i, j;
        for(i = j = 1; i < n; i ++)
            if(A[i] != A[i - 1]) A[j ++] = A[i];
        return n ? j : 0;
    }
};

25.Reverse Nodes in k-Group

用头插法来做的，顺序插入到首节点之后，就反转了。每 k 个节点处理之后，把首节指针点移动到下 k 个的开头。最后面不足 k 个的话，再反转回来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int Reverse(ListNode *&pre, ListNode *&p, int k)
    {
        int i;
        ListNode *nex, *tmp;
        for(i = 1; p != NULL; i ++, p = tmp)
        {
            if(i == 1) nex = p;
            tmp = p->next;
            p->next = pre->next;
            pre->next = p;
            if(i == k) i = 0, pre = nex;
        }
        nex->next = NULL;
        return i;
    }
    ListNode *reverseKGroup(ListNode *head, int k) {
        if(head == NULL) return NULL;
        ListNode *tmphead = new ListNode(0), *pre = tmphead, *p = head;
        tmphead->next = head;
        if(Reverse(pre, p, k) != 1)
        {
            p = pre->next;
            Reverse(pre, p, k);
        }
        return tmphead->next;
    }
};

24.Swap Nodes in Pairs

Reverse Nodes in k-Group的简化版。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 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 == NULL) return NULL;
        ListNode *tmphead = new ListNode(0), *pre = tmphead, *p = head, *tmp, *nex;
        tmphead->next = head;
        for(int i = 0; p != NULL; i ++, p = tmp)
        {
            if(i & 1 ^ 1) nex = p;
            tmp = p->next;
            p->next = pre->next;
            pre->next = p;
            if(i & 1) pre = nex;
        }
        nex->next = NULL;
        return tmphead->next;
    }
};

23.Merge k Sorted Lists

一个堆（这里用了优先级队列），把所有 list 的首元素放堆里，O(logn)取得最小值插入新队列，异步推进。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    struct comp
    {
        bool operator()(ListNode *a,ListNode *b)
        {return a->val > b->val;}
    };
    ListNode *mergeKLists(vector &lists) {
        ListNode *tmphead = new ListNode(0), *p = tmphead;
        priority_queue<ListNode*, vector<ListNode*>, comp> q;
        for(int i = 0; i < lists.size(); i ++) if(lists[i] != NULL) q.push(lists[i]); while(!q.empty()) { p->next = q.top();
            p = p->next;
            q.pop();
            if(p ->next != NULL) q.push(p->next);
        }
        return tmphead->next;
    }
};

22.Generate Parentheses

DFS，保持当前右括号不多于左括号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    string tmp;
    vector ans;
    void DFS(int left, int right, int n)
    {
        if(left == right && left == n)
        {
            ans.push_back(tmp);
            return;
        }
        if(left < n)
        {
            tmp[left + right] = '(';
            DFS(left + 1, right, n);
        }
        if(right < left)
        {
            tmp[left + right] = ')';
            DFS(left, right + 1, n);
        }
    }
    vector generateParenthesis(int n) {
        tmp.resize(n << 1);
        DFS(0, 0, n);
        return ans;
    }
};

21.Merge Two Sorted Lists

归并排序的一次操作，设个哨兵头结点，结束后free。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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) {
        ListNode *thead = new ListNode(0), *p = thead;
        while(l1 != NULL && l2 != NULL)
        {
            if(l1->val < l2->val) p->next = l1, p = l1, l1 = l1->next;
            else p->next = l2, p = l2, l2 = l2->next;
        }
        while(l1 != NULL) p->next = l1, p = l1, l1 = l1->next;
        while(l2 != NULL) p->next = l2, p = l2, l2 = l2->next;
        p = thead->next;
        free(thead);
        return p;
    }
};

20.Valid Parentheses

用栈配对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool isValid(string s) {
        stack st;
        for(int i = 0; i < s.length(); i ++)
        {
            switch(s[i])
            {
                case '(': st.push('('); break;
                case '[': st.push('['); break;
                case '{': st.push('{'); break;
                case ')':
                    if(st.empty() || st.top() != '(') return false;
                    st.pop(); break;
                case ']':
                    if(st.empty() || st.top() != '[') return false;
                    st.pop(); break;
                case '}':
                    if(st.empty() || st.top() != '{') return false;
                    st.pop(); break;

            }
        }
        return st.empty();
    }
};

19.Remove Nth Node From End of List

两个指针相隔 n 距离，前面的指针到了末尾，后面的指针就是删除的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 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 *pre, *slow, *quick;
        ListNode *newhead = new ListNode(0);
        newhead->next = head;
        int i = 0;
        for(pre = slow = quick = newhead; quick != NULL; i ++)
        {
            pre = slow;
            if(i >= n) slow = slow->next;
            quick = quick->next;
        }
        pre->next = slow->next;
        free(slow);
        return newhead->next;
    }
};

18.4Sum

尝试了O(n^2)的，但是应该常数很大吧，超时了。就是哈希存两两的和，然后通过查哈希表找到 两两+两两，要判断数字重复情况。这题数据量挺大的，O(n^3)如果用不太好的方式实现的话也会超。

O(n^3)方法：先对num排序，然后从两头枚举两个数，O(n^2)，后两个数在前两个数之间的两端开始，和小了左边的往右，和大了右边的往左调整，O(n)，总共O(n^3)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector ans;
    vector fourSum(vector &num, int target) {
        if(num.size() < 4) return ans;
        sort(num.begin(), num.end());
        for(int left = 0; left < num.size() - 3;) { for(int right = num.size() - 1; right > left + 2;) 
            {
                int ml = left + 1, mr = right - 1;
                while(ml < mr) 
                { 
                    int tmpsum = num[left] + num[right] + num[ml] + num[mr]; 
                    if(tmpsum > target) mr --;
                    else if(tmpsum < target) ml ++;
                    else
                    {
                        vector tmp = {num[left], num[ml], num[mr], num[right]};
                        ans.push_back(tmp);
                        ml ++;
                        mr --;
                    }
                    for(; ml != left + 1 && ml < mr && num[ml] == num[ml - 1]; ml ++);
                    for(; mr != right - 1 && ml < mr && num[mr] == num[mr + 1]; mr --); 
                } 
                for(right --; right > left + 2 && num[right] == num[right + 1]; right --);
            }
            for(left ++; left < num.size() - 3 && num[left] == num[left - 1]; left ++);
        }
        return ans;
    }
};

17.Letter Combinations of a Phone Number

基础DFS。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    const vector v = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector ans;
    string tmp;
    void DFS(int cur, string d)
    {
        if(cur == d.length())
        {
            ans.push_back(tmp);
            return;
        }
        for(int i = 0; i < v[d[cur] - '0'].length(); i ++)
        {
            tmp[cur] = v[d[cur] - '0'][i];
            DFS(cur + 1, d);
        }
    }
    vector letterCombinations(string digits) {
        tmp.resize(digits.length());
        DFS(0, digits);
        return ans;
    }
};

16.3Sum Closest

O(n^2)，先排序，枚举第一个数，后两个数一个在第一个数后边一个开始，一个从 末尾开始，和4Sum类似调整。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int threeSumClosest(vector &num, int target) {
        bool findans = false;
        int ans;
        sort(num.begin(), num.end());
        for(int i = 0; i < num.size(); i ++)
        {
            for(int left = i + 1, right = num.size() - 1; left < right;) 
            { 
                int tmpsum = num[i] + num[left] + num[right]; 
                if(tmpsum > target) right --;
                else if(tmpsum < target) left ++;
                else return tmpsum;
                if(!findans || abs(tmpsum - target) < abs(ans - target))
                    ans = tmpsum, findans = true;
            }
        }
        return ans;
    }
};

15.3Sum

同上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector ans;
    vector threeSum(vector &num) {
        if(num.size() < 3) return ans;
        sort(num.begin(), num.end());
        for(int i = 0; i < num.size();)
        {
            for(int left = i + 1, right = num.size() - 1; left <right;)
            {
                int tmpsum = num[i] + num[left] + num[right];
                if(tmpsum < 0) left ++; else if(tmpsum > 0) right --;
                else
                {
                    vector tmp = {num[i], num[left], num[right]};
                    ans.push_back(tmp);
                    left ++;
                    right --;
                }
                for(; left != i + 1 && left < right && num[left] == num[left - 1]; left ++);
                for(; right != num.size() - 1 && left < right && num[right] == num[right + 1]; right --);
            }
            for(i ++; i < num.size() && num[i] == num[i - 1]; i ++);
        }
        return ans;
    }
};

14.Longest Common Prefix

一个一个扫

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    string ans;
    string longestCommonPrefix(vector &strs) {
        if(strs.size() == 0) return ans;
        if(strs.size() == 1) return strs[0];
        for(int j = 0; ; j ++)
        {
            for(int i = 1; i < strs.size(); i ++)
                if(strs[i].size() == j || strs[i][j] != strs[i - 1][j]) return ans;
            ans += strs[0][j];
        }
        return ans;
    }
};

13.Roman to Integer

各有各的方法，重点是记录(上一个)数比(这个)数大或小，来确定谁减谁。基本是右结合的，所以从后往前扫好处理些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {  
public:  
    int ro[128];
    int romanToInt(string s) {
        ro['I'] = 1;
        ro['V'] = 5;
        ro['X'] = 10;
        ro['L'] = 50;
        ro['C'] = 100;
        ro['D'] = 500;
        ro['M'] = 1000;
        int ans = -1, last;
        for(int i = s.length() - 1; i >= 0; i --)
        {
            if(ans == -1) ans = ro[s[i]];
            else
            {
                if(last > ro[s[i]]) ans -= ro[s[i]];
                else ans += ro[s[i]];
            }
            last = ro[s[i]];
        }
        return ans;
    }
};

12.Integer to Roman

每个十进制位格式是一样的，只是字母替换一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector table = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
    string ro = "IVXLCDM";
    char convert(char x, int i)
    {
        if(x == 'I') return ro[i];
        if(x == 'V') return ro[i + 1];
        if(x == 'X') return ro[i + 2];
    }
    string intToRoman(int num) {
        string ans;
        for(int i = 0; num; i += 2, num /= 10)
        {
            int x = num % 10;
            string tmp = table[x];
            for(int j = 0; j < tmp.size(); j ++)
                tmp[j] = convert(tmp[j], i);
            ans = tmp + ans;
        }
        return ans;
    }
};

11.Container With Most Water

从两端开始枚举，较高的挡板往中间枚举的话一定无法得到更优解，故反复从较低挡板向中间枚举，O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxArea(vector &height) {
        int left = 0, right = height.size() - 1, ans = -1;
        while(left < right)
        {
            ans = max(ans, min(height[left], height[right]) * (right - left));
            if(height[left] < height[right]) left ++;
            else right --;
        }
        return ans;
    }
};

10.Regular Expression Matching

每遇到一个 * ，问题都会出现分枝，需要用到栈或者递归。

没有 * 的情况好处理，遇到 * 的时候，穷举所有匹配长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        if(*p == 0) return *s == 0;
        if(*(p + 1) != '*')
        {
            if(*s && (*s == *p || *p == '.'))
               return isMatch(s + 1, p + 1);
            return false;
        }
        else
        {
            for(; *s && (*s == *p || *p == '.'); s ++)
                if(isMatch(s, p + 2)) return true;
            return isMatch(s, p + 2);
        }
    }
};

9.Palindrome Number

首先处理负数的trick。然后主要思路就是通过 while(...) a = a * 10 + x % 10; 来将 x 翻转。

但是注意到 x 很大的时候，翻转的 x 会超出 int 范围，也许会刚好成为另一个和 a 得出的数相等的正数，所以不能完全翻转后判断，而可以在翻转恰好一半的时候判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) return false; 
        if(x == 0) return true; 
        int a = 0, b = x, cnt = 1; 
        while(x /= 10) cnt ++; 
        for(; b && cnt >= 0; b /= 10, cnt -= 2)
        {
            if(cnt == 1) return a == b / 10;
            else if(cnt == 0) return a == b;
            a = a * 10 + b % 10;
        }
        return false;
    }
};

8.String to Integer (atoi)

任何类似多符号、符号数字间有空格的小问题都直接输出 0，这就好办了。处理越界用 long long。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int atoi(const char *str) {
        long long ans = 0;
        bool flag = false;
        for(; *str == ' '; str ++);
        if(*str == '+') str ++;
        else if(*str == '-') flag = true, str ++;
        for(; isdigit(*str); str ++)
        {
            ans = ans * 10 + *str - '0';
            if((flag ? -ans : ans) > INT_MAX) return INT_MAX;
            else if((flag ? -ans : ans) < INT_MIN) return INT_MIN;
        }
        return (int)(flag ? -ans : ans);
    }
};

7.Reverse Integer

还是关于越界的讨论，不过这道题本身没有设置处理方式，重点在于面试时的交流。

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int reverse(int x) {
        int a = 0;
        for( int b = x >= 0 ? x : -x; b; b /= 10)
            a = a * 10 + b % 10;
        return x >= 0 ? a : -a;
    }
};

6.ZigZag Conversion

题意的 "z" 字形指一列nRows个，然后斜着往右上一格一个回到第一行，然后再一列nRows个。比如nRows=5，如下： 

1
2
3
4
5
1          9          17          25
2       8 10       16 18       24 26
3    7    11    15    19    23    27    …
4 6       12 14       20 22       28 30
5         13          21          29
每行字母在原字符串中的间隔是有规律的，虽然两层for循环，但是s中每个字母只访问了一次，O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string convert(string s, int nRows) {
        if(nRows == 1) return s;
        string ans;
        int a = (nRows << 1) - 2, b = 0;
        for(int i = 0; i < nRows; i ++, a -= 2, b += 2)
        {
            bool flag = false;
            for(int j = i; j < s.length();

                    j += flag ? (b ? b : a) : (a ? a : b), flag ^= 1)
                ans += s[j];
        }
        return ans;
    }
};

5.Longest Palindromic Substring

网上O(n)的方法是厉害啊。。。简单解释如下：

1、预处理字符串，前后加(哨兵)字符比如 !，每个字母旁边加辅助字符比如#，这样例如字符串 s="ababbcbb" 就变成 tmp="!#a#b#a#b#b#c#b#b#!"。这样的好处是不用讨论回文串长度的奇偶。

2、对转化后的串，维护一个 center 和一个 reach，center 是当前已发现的 reach 最远的回文串中心位置，reach 是这个回文串最右端的位置，center和reach可初始化为 1，即第一个#的位置。

3、维护一个数组vector r(tmp.length())，r[i] 表示 i 位置为中心的回文串半径。

4、在考察位置 i 的时候，所有 j < i 的 r[j] 都是已知的子问题。如果 i 在 reach 的左边，则 i 包含在以 center 为中心的回文串中，那么可以想到，如果和 i 关于 center 对称位置的 mirrori 为中心的回文串覆盖范围没有到达 center 为中心的回文串边缘，则 i 为中心的回文串肯定和 mirrori 的一样。而如果 mirrori 的回文串到达了边缘甚至超过，或者 i 本来就在 reach 的右边，那么对 i 为中心的回文串进行一次扩展，则结果 或者刚好不扩展，或者一定更新了reach。无论怎样，这里都得到了 r[i]。知道了所有 r[i]，答案就出来了。

核心问题在于第4步“对 i 为中心的回文串进行扩展”的复杂度。每次发生“对 i 扩展”，必然是对 reach 的扩展(也可能刚好不扩展，这个不影响复杂度），而 reach 的扩展范围是 tmp 的长度大约 2n，所以总复杂度为 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string longestPalindrome(string s) {
        int center = 1, reach = 1, ansstart = 0, anslength = 0;
        string tmp = "!#";
        for(int i = 0; i < s.length(); i ++)
            tmp += s[i], tmp += '#';
        tmp + '!';
        vector r(tmp.length());
        for(int i = 2; i < tmp.length(); i ++) { int mirrori = center * 2 - i; r[i] = reach > i ? min(r[mirrori], reach - i) : 0;
            for(; tmp[i + r[i] + 1] == tmp[i - r[i] - 1]; r[i] ++);
            if(i + r[i] > reach)
                reach = i + r[i], center = i;
            if(r[i] > anslength)
            {
                ansstart = i - r[i] >> 1;
                anslength = r[i];
            }
        }
        return s.substr(ansstart, anslength);
    }
};

4.Median of Two Sorted Arrays

如果 A[pa] < B[pb]，那么 A[pa] 一定在 A 与 B 合并后的前 pa + pb + 2 个数中。

证明： A 中有 pa + 1 个数 <= A[pa]，B 中有小于 pb + 1 个数 <= A[pa]，合并后有少于pa + pb + 2 个数 <= A[pa]。

利用这个性质迭代找 A 与 B 合并后的第 k 大数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int findKth(int A[], int m, int B[], int n, int k)
    {
        int pm, pn;
        while(true)
        {
            if(m == 0) return B[k - 1];
            if(n == 0) return A[k - 1];
            if(k == 1) return min(A[k - 1], B[k - 1]);
            if(m <= n) pm = min(k >> 1, m), pn = k - pm;
            else
                pn = min(k >> 1, n), pm = k - pn;
            if(A[pm - 1] < B[pn - 1]) A += pm, m -= pm, k -= pm; else if(A[pm - 1] > B[pn - 1]) 
                B += pn, n -= pn, k-= pn;
            else break;
        }
        return A[pm - 1];
    }
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        if((m + n) & 1) return findKth(A, m, B, n, (m + n >> 1) + 1);
        else return (findKth(A, m, B, n, m + n >> 1) +

            findKth(A, m, B, n, (m + n >> 1) + 1)) * 0.5;
    }
};

3.Longest Substring Without Repeating Characters

维护一个不重复字符的区间。

代码一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector isin(128, false);
        int ans = 0;
        for(int front = 0, rear = 0; front < s.length(); front ++)
        {
            if(isin[s[front]])
                for(; rear < front && isin[s[front]]; isin[s[rear]] = false, rear ++);
            isin[s[front]] = true;
            ans = max(ans, front - rear + 1);
        }
        return ans;
    }
};

代码二：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector site(128, -1);
        int nowstart = -1, ans = 0;
        for(int i = 0; i < s.length(); i ++) { if(site[s[i]] >= nowstart)
                nowstart = site[s[i]] + 1;
            site[s[i]] = i;
            ans = max(i - nowstart + 1, ans);
        }
        return ans;
    }
};

2.Add Two Numbers

大整数加法的链表版。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 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 *ans = new ListNode(0), *p = ans;
        int cur = 0;
        while(l1 != NULL || l2 != NULL || cur)
        {
            p->val = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + cur;
            cur = p->val / 10;
            p->val %= 10;
            if(l1) l1 = l1->next;
            if(l2) l2 = l2->next;
            if(l1 || l2 || cur)
                p->next = new ListNode(0);
            p = p->next;
        }
        return ans;
    }
};

1.Two Sum

哈希存位置，O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector twoSum(vector &numbers, int target) {
        unordered_map<int, int> mp;
        vector ans;
        for(int i = 0; i < numbers.size(); i ++)
        {
            if(mp.count(target - numbers[i]))
            {
                ans.push_back(mp[target - numbers[i]] + 1);
                ans.push_back(i + 1);
                break;
            }
            if(!mp.count(numbers[i])) mp[numbers[i]] = i;
        }
        return ans;
    }
};