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

基本字典树

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表示确认可选修

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

好像又是老题

/**
 * 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则会掉这个坑。、

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;
    }
};

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

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开始把每个其倍数都标记成合数,然后往后枚举,枚举到的没标记的一定是素数(如果它是合数,它的质因数肯定比它小,而比它小的质数的倍数都已经标记过了),继续标记其所有倍数。

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节点被删除的情况了。

/**
 * 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 就一直进行,能保证计算结束,不知道怎么证明的。 代码放传统思路。

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。题目巧在如果思路转换为求二进制最长相同前缀,代码就很简单了。

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剩下的就是那个相同前缀。

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随便做,好陈旧。

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

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

/**
 * 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了的,反复更新。

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,一位一位统计就快多了。

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次操作了。

直接思路:

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;
    }
};

并行分治思路:

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 的代码。

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);

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次就做记录。

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 的顺序。

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值。

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

//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];
    }
};
//二分答案
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

变形的非递归中序遍历。

/**
 * 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 的个数。

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 。

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)时间里把不同的数抵消掉,“多数数”肯定会被留下来。

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 。

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。

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函数呢。。。

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)

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)

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

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

/**
 * 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的答案也没什么特别的,运行时间的浮动吧。

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)。贴上两种代码吧。

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];
    }
};
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

二分

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]本身。

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

 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)。

 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

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

 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组成字符串。

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

 /**
  * 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。

又有空数据@_@.

 /**
  * 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

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

 /**
  * 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)的。

 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

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

 /**
  * 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

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

 /**
  * 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

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

 /**
  * 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

设置两个指针slowfast,从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开始的指针走到圈开始位置时,两指针刚好相遇。

 /**
  * 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

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

 /**
  * 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] == truej ~ i的串在字典中,则dp[i] = true

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

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

 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,优化一下常数。

 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,中间判断一下空指针。

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

 /**
  * 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的那个数。

 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就是要求的数。

 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

一路异或过去就可以了。

 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)的话也不难,只是思考代码的时候会有点绕。

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

 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 的时候也为正,剩下的一样。这样就能够成功转一圈。

 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标记。

 /**
  * 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的最小值。注意一下边界。

 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的终点肯定都是解,所以不必利用其他的结构存储答案信息。

 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。

 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

遍历一遍加起来。。。

 /**
  * 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)大一些。

 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 稳妥些。

 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那个八数码。

 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。

 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()。

 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或左边一路上来或右边一路上来,三种情况。

 /**
  * 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)。

 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

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

 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做差更新答案。

 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对这题太熟悉了。

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

 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

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

 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

递推。。

 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指针赋值。

 /**
  * 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 容易处理。

 /**
  * 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],否则不加。

 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的大小关系。

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

 /**
  * 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,终点判断是否插入答案。

 /**
  * 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

遍历树。

 /**
  * 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

还是遍历。

 /**
  * 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

遍历。

 /**
  * 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

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

 /**
  * 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

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

 /**
  * 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翻转的。。。

 /**
  * 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两边即为左右子树。根据左右子树节点个数,在后序遍历中找到左右子树分界(左右子树肯定不交叉),则几个关键分界点都找到了,对左右子树递归。

 /**
  * 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方法一样,前序和后序的信息作用相同。

 /**
  * 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

遍历。

 /**
  * 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,奇偶层轮流走,一层左到右,一层右到左。

 /**
  * 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的代码上改了一下。

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

 /**
  * 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

递归:左指针和右指针,对称递归,即(左的左)和(右的右)对应,(左的右)和(右的左)对应。

 /**
  * 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);
     }
 };

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

 /**
  * 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

同步遍历,比较判断。

 /**
  * 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赋值,最终翻转回来。

 /**
  * 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

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

 /**
  * 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, js1[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)的解法,我也就放心了。。。

 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的解,两层循环组合这些解。

 /**
  * 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

经典问题,卡特兰数,可递推,可用公式(公式用组合数,也要写循环)。

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

数据结构基础

 /**
  * 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

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

 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可以帮助标记翻转之后更换了的头指针。

 /**
  * 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 位置的解。

 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的方法。

 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

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

 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 来说一个萝卜一个坑,肯定不会破坏前面的数据。具体看代码。

 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要求字符串对应字母的个数是一致的,可以直接排序对比。递归终点是刚好只有一个字母。

 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

分存大小最后合并。

 /**
  * 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)

 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)。

 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;

 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方法一。

 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

加个表头乱搞吧。

 /**
  * 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

直接操作。

 /**
  * 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)的可能性,所以确定的时候二分,不确定的时候单位缩减边界。

 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

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

 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。

 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。

 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。

 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 继续跑,如此反复。

ij 都只遍历一遍 S,复杂度 O(n)

 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

轮流找:

 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 ++;
         }
     }
 };

找到哪个放哪个:

 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

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

 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)的方法就行了。

 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],即每个字符串对应空串的编辑距离为串长度,之后对每个位置取子问题加上当前位置 改、删、增得解的最小值。

 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

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

 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

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

 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,越推越精确,直到自己想要的精度。

 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

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

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

 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

大整数加法。

 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也不麻烦,题目定义太模糊,为了理解规则错很多次也没办法。

 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

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

 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

递推

 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

递推

 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

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

 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对长度取模。那么就不要矫情地追求双指针一遍扫描了。

 /**
  * 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不大于这个方法数,则这一位就是枚举到的这个数。

 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)位置的数。

 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

从后往前找。

 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 最小和最大两种极端情况。

 /**
  * 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排个序,然后慢慢合并。。。

 /**
  * 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

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

 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

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

代码一:

 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;
     }
 };

代码二:

 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 置零,中间处理一下要求至少包含一个数字的要求即可。

 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。

 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

同上

 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 了。

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

 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好了。

 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

四个一组,就地旋转。

 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时跳过重复的数字。

 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。

 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

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

 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 开始匹配位置的下一个位置。

 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 的转换。

 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

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

 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]取负数。

 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到下标和数对应的位置,再次遍历,数和下标不对应则是第一个没出现的数。注意处理有重复数字。

 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

 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

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

 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

直接模拟,递推。

 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,对于面试题来说变态了些,应该不至于考察。

 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

行列九宫格都判断一下。

 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

二分

 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。

手工代码:

 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:

 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 在哪部分里。

 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 实现括号配对+统计, 为了方便实现,写成数组的形式。

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

 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 之后的排序。

 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 的序号。

(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。

 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。。)

 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。

 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 异步挪动,把不等于给定值的数往前挪。

 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 异步挪动,不重复值往前挪。

 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 个的话,再反转回来。

 /**
  * 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的简化版。

 /**
  * 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)取得最小值插入新队列,异步推进。

 /**
  * 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,保持当前右括号不多于左括号。

 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。

 /**
  * 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

用栈配对。

 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 距离,前面的指针到了末尾,后面的指针就是删除的位置。

 /**
  * 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)

 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。

 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类似调整。

 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

同上。

 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

一个一个扫

 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

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

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

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

 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)。

 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

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

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

 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 得出的数相等的正数,所以不能完全翻转后判断,而可以在翻转恰好一半的时候判断。

 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。

 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

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

 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          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)。

 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)。

 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 大数。

 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

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

代码一:

 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;
     }
 };

代码二:

 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

大整数加法的链表版。

 /**
  * 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)。

 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;
     }
 };