leetcode高级算法

不一定按顺序的随心所欲记录。

数组和字符串

Product of Array Except Self

给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
请不要使用除法，且在 O(n) 时间复杂度内完成此题。
分为两步，计算一个数字左边所有数字乘积，再计算右边所有数字乘积。

正好可以复用前面的结果，按顺序累乘。

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> r(n, 1);
    for (int i=0;i<n-1;i++){
        r[i+1] = r[i] * nums[i];
    }
    int temp = 1;
    for (int i=n-1;i>0;i--){
        temp *= nums[i];
        r[i-1] *= temp;
    }
    return r;
}

第一个缺失的正数

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。
限制了空间，所以从数组本身上找办法，让下标和数字对应，就能找出缺失的数。

但我觉得这修改了原数组，有点不太好。

int firstMissingPositive(vector<int>& nums) {
    int n=nums.size();
    for (int i=0;i<n;){
        if (nums[i]>0 && nums[i]<n && nums[i] !=i+1 && nums[nums[i]-1] != nums[i]){
            int temp=nums[nums[i]-1];
            nums[nums[i]-1] = nums[i];
            nums[i] = temp;
        }else
            i++;
    }
    int r = 1;
    for (int i=0;i<n;i++){
        if (nums[i] == i+1)
            r++;
        else
            break;
    }
    return r;
}

四数相加II

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。

四组分为两组，先记录两个数组相加的所有结果和出现次数，然后计算另两个相加是否出现相反数，结果加上次数。

int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
    unordered_map<int, int> us;
    int r = 0;
    for (int &a : A){
        for (int &b : B){
            us[a+b]++;
        }
    }
    for (int &c : C){
        for (int &d : D){
            if (us[-c-d] > 0){
                r+= us[-c-d];
            }
        }
    }
    return r;
}

寻找重复数

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
注意读题，对数字是有限制的，都在[1,n]中，所以类似抽屉原理，一定会有重复数。

二分法，取中间数，判断某一个区间内的数的数量，如果超过了区间大小，则一定有重复。

int findDuplicate(vector<int>& nums) {
    int n=nums.size();
    int l=1, r=n;
    int count;
    while(l<r){
        int mid= l + (r - l) / 2;
        count=0;
        for (int i=0;i<n;i++){
            if (nums[i] <= mid)
                count++;
        }
        if (count > mid)
            r = mid;
        else
            l = mid+1;
    }
    count=0;
    for (int i=0;i<n;i++)
        if (nums[i] == l)
            count++;
    return count > 1 ? l : -1;
}

Sliding Window Maximum

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。返回滑动窗口最大值。
线性时间复杂度。
一上来想，分治，树，堆栈，队列，都解决不了。

关键数据结构是一个，双向队列，或者说，链表。有序链表插入的复杂度显然太高了，而这个巧妙的点在于，对于窗口，先进先出，最后插入的元素，一定比前面的要后出。那么在队列中，比这个插入元素还小的元素，就没有意义了，它一定不会成为最大的了，可以删掉，这样保证最多只会比较一次大于，复杂度就维持在O(n)了。

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> res;
    deque<int> q;
    for (int i = 0; i < nums.size(); ++i) {
        if (!q.empty() && q.front() == i - k) q.pop_front();  // 头滑出窗口
        while (!q.empty() && nums[q.back()] < nums[i]) q.pop_back();  // 删掉小于新元素的值
        q.push_back(i);
        if (i >= k - 1) res.push_back(nums[q.front()]);
    }
    return res;
}

最小窗口子字符串

给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。
判断某个字符是否存在于T，或者记录它出现次数，这些操作，想到用哈希表。但更极致的是，因为是char类型，所以用vector<>(128)会更快。
有一个问题是，怎样判断我扫描过的字串刚好包含了T所有字母，反过来的临界条件（去掉某个字符则不能包含T）很好判断。判断方法我一时没有想到，于是用临界条件反过来做。那么需要一个初始状态，也就是子串即s，但此时又有一个问题，可能不存在答案，所以我先扫描一遍字典，比较字符数量，确保答案存在。

接下来，从两端开始，不断去掉字符，直至无法再去掉，就找到了最小子串。但仔细一想，这是有问题的，如果两端字符相同，并且只能去掉一个的时候，去掉左边还是右边？没法判断，必须都试一试，然后比较字符串长度。于是一端移动时，另一端又要尝试回退。还要记录找到的最小长度，更新这个长度。

string minWindow(string s, string t) {
    unordered_map<char, int> mt;
    unordered_map<char, int> ms;
    int min_l= 0, min_r=INT_MAX;
    for (auto c : s)
        ms[c]++;
    for (auto c : t)
        mt[c]++;
    for (auto item : mt){
        if (item.second > ms[item.first])
            return "";
    }
    int n=s.size();
    int l=0, r=n-1;
    for (l;l<n;l++){
        if (ms[s[l]] == mt[s[l]])
            break;
        else if (ms[s[l]] > mt[s[l]])
            ms[s[l]]--;
    }
    while(true){
        for (r;r>=0;r--){
            if (ms[s[r]] == mt[s[r]])
                break;
            else if (ms[s[r]] > mt[s[r]])
                ms[s[r]]--;
        }
        if (r-l < min_r - min_l){
            min_r = r;
            min_l = l;
        }
        if (l-- == 0)
            break;
        ms[s[l]]++;
    }
    return s.substr(min_l, min_r-min_l+1);
}

接下来是优化这段代码。
不需要两个哈希表，一个就足够了，不用相互比较字符，以0为界限就可以了。
判断当前字串是否满足条件的办法：找到一个属于T的字符，cnt++，当cnt==tsize时，就恰好找到。

于是两个pos都从左端开始，分别前进，记录最小长度。

string minWindow(string s, string t) {
    string res = "";
    vector<int> letterCnt(128, 0);
    int left = 0, cnt = 0, minLen = INT_MAX;
    for (char c : t) ++letterCnt[c];
    for (int i = 0; i < s.size(); ++i) {
        if (--letterCnt[s[i]] >= 0) ++cnt;
        while (cnt == t.size()) {
            if (minLen > i - left + 1) {
                minLen = i - left + 1;
                res = s.substr(left, minLen);
            }
            if (++letterCnt[s[left]] > 0) --cnt;
            ++left;
        }
    }
    return res;
}

最长连续序列

给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
复杂度为O(n)的话，排序不用想了，数据结构几乎也就剩下哈希表了。

在这里一开始漏想到一个点，就是新添加一个数i时，怎么找到i左右的两端。比如说，已经有1、2、4、5，现在加入一个3，那么两端是1，5，显然不能是按序检查哈希表是否存在连续数字。实际上1、2、4、5也各自维护了自己的序列长度，直接加减序列长度，就能到两端位置了。

int longestConsecutive(vector<int>& nums) {
    unordered_map<int,int> m;
    int res = 0;
    for (auto & i : nums){
        if (m[i] == 0){
            int l=m[i-1], r=m[i+1];
            m[i] = l + r + 1;
            m[i-l] = m[i];
            m[i+r] = m[i];
            res = max(res, m[i]);
        }
    }
    return res;
}

螺旋矩阵

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
没有追求极致速度，而是将代码写的简洁，虽然也不是很短。

将循环硬编码更快，但要注意的是，不能四次放在一个循环内，因为有可能是没有四次的，比如九宫格，第一圈四次转完只需要中间走一个就结束了。也就是说，四次移动中间可以加一个判断条件，终止循环。（其实就是看边界条件放哪里判断比较简洁方便）

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    if (matrix.size() < 1 || matrix[0].size() < 1)
        return {};
    vector<pair<int,int>> dic = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    vector<int> res;
    int m=matrix.size(), n=matrix[0].size();
    int sum=m*n, mode=0;
    int x=0,y=-1;
    while(sum > 0){
        int temp;
        if (mode%2)
            temp = n--;
        else
            temp = --m;
        for (int i=0;i<temp;i++){
            x += dic[mode].first;
            y += dic[mode].second;
            sum--;
            res.push_back(matrix[x][y]);
        }
        mode = (mode+1)%4;
    }
    return res;
}

链表

合并K个元素的有序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
使用priority_queue，本质上就是堆排序，复杂度应该在nlogn
堆排序没有利用到有序链表这个条件。

合并两个有序链表很容易，如果采用分治法，则类似归并排序，

ListNode* mergeKLists(vector<ListNode*>& lists) {
    priority_queue<int, vector<int>, greater<int> > pq;
    for (auto p : lists){
        while (p){
            pq.push(p->val);
            p=p->next;
        }
    }
    if (pq.size() < 1)
        return NULL;
    ListNode * root = new ListNode(pq.top());
    pq.pop();
    ListNode * temp = root;
    while (!pq.empty()){
        temp->next = new ListNode(pq.top());
        pq.pop();
        temp = temp->next;
    }
    return root;
}

链表排序

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
说到nlogn的排序，想到的也就是快排、归并、堆排了。

单向链表快排不太方便，堆排同理。归并的话，龟兔赛跑就可以找到中间节点，然后合并两个有序链表也很容易。

ListNode* sortList(ListNode* head) {
    if (head == NULL || head->next == NULL)
        return head;
    ListNode* l = head;
    ListNode* r = head;
    while(r->next && r->next->next){
        l = l->next;
        r = r->next->next;
    }
    ListNode* mid = l->next;
    l->next = NULL;
    return merge(sortList(head), sortList(mid));
}
ListNode* merge(ListNode* first, ListNode* second){
    if (first == NULL)
        return second;
    else if (second == NULL)
        return first;
    ListNode * head;
    ListNode * pos;
    if (first->val < second->val){
        head = first;
        first = first->next;
    }else{
        head = second;
        second = second->next;
    }
    pos = head;
    while(true){
        if (first == NULL){
            pos->next = second;
            break;
        }
        else if (second == NULL){
            pos->next = first;
            break;
        }
        else if (first->val < second->val){
            pos->next = first;
            first = first->next;
        }else{
            pos->next = second;
            second = second->next;
        }
        pos = pos->next;
    }
    return head;
}

复制带随机指针的链表

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的深度拷贝。

用map记录已经碰到过的指针和它的拷贝，然后按序遍历链表就行了。

RandomListNode *copyRandomList(RandomListNode *head) {
    if (head == NULL)
        return NULL;
    unordered_map<RandomListNode*, RandomListNode*> m;
    RandomListNode* nhead = head;
    RandomListNode* np = new RandomListNode(head->label);
    m[head] = np;
    while(nhead){
        RandomListNode* next = NULL;
        RandomListNode* random = NULL;
        if (nhead->next && m[nhead->next] == 0){
            next = new RandomListNode(nhead->next->label);
            m[nhead->next] = next;
        }else
            next = m[nhead->next];
        if (nhead->random && m[nhead->random] == 0){
            random = new RandomListNode(nhead->random->label);
            m[nhead->random] = random;
        }else
            random = m[nhead->random];
        nhead = nhead->next;
        np->next = next;
        np->random = random;
        np = np->next;
    }
    return m[head];
}

树和图

被围绕的区域

给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。
找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

考虑用DFS，然后需要记录中间状态，为了节约空间，直接修改原数组，将条件相关的字母改为其他标识，最后再遍历修改成最终结果。

void solve(vector<vector<char>>& board) {
    if (board.size() < 1 || board[0].size() < 1)
        return;
    int x = board.size(), y = board[0].size();
    for (int i=0;i<x;i++){
        helper(board, i, 0);
        helper(board, i, y-1);
    }
    for (int i=1;i<y;i++){
        helper(board, 0, i);
        helper(board, x-1, i);
    }
    for (int i=0;i<x;i++){
        for (int j=0;j<y;j++){
            if (board[i][j] == '1')
                board[i][j] = 'O';
            else
                board[i][j] = 'X';
        }
    }
}
void helper(vector<vector<char>> & board, int x, int y){
    if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size() && board[x][y] == 'O'){
        board[x][y] = '1';
        helper(board, x + 1, y);
        helper(board, x, y + 1);
        helper(board, x - 1, y);
        helper(board, x, y - 1);
    }
}

单词接龙

给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

非常经典的一个题，以前也做过，这里运用到了很多小技巧。’a’到’z’的递增，swap方法体现广搜层级，vector转换set提高查询效率，循环体前后修改值（做一个递归办法）

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    set<string> wordDic(wordList.begin(), wordList.end());
    if (wordDic.count(endWord) == 0)
        return 0;
    wordDic.erase(beginWord);
    queue<string> q;
    queue<string> qt;
    int count = 1;
    q.push(beginWord);
    while(true){
        while (!q.empty()){
            string word = q.front();
            q.pop();
            if (word == endWord)
                return count;
            for (auto & c : word){
                char temp = c;
                for (char t='a';t<='z';t++){
                    c = t;
                    if (wordDic.count(word) > 0){
                        wordDic.erase(word);
                        qt.push(word);
                    }
                }
                c = temp;
            }
        }
        count++;
        if (!qt.empty())
            q.swap(qt);
        else
            break;
    }
    return 0;
}

计算右侧小于当前元素的个数

给定一个整型数组 nums，按要求返回一个新的 counts 数组。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于nums[i] 的元素的数量。
从右边开始，一个个加入新队列排序，按照所在位置得出结果。

这题看别人的代码学到了两个二分搜索的函数lower_bound(begin, end, num), upper_bound(begin, end, num)。

vector<int> countSmaller(vector<int>& nums) {
    int n=nums.size();
    vector<int> res(n,0),tmp;
    for(int i=n-1;i>=0;i--){
        auto it=lower_bound(tmp.begin(),tmp.end(),nums[i]);
        res[i]=it-tmp.begin();
        tmp.insert(it,nums[i]);
    }
    return res;
}

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。

递归，太久没写递归程序，脑子瓦特了。

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == NULL || root->val == p->val || root->val == q->val)
        return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right)
        return root;
    else if (left == NULL)
        return right;
    else
        return left;
}

课程表

现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？
将课看作点，先修关系看作边，形成一个有向图。问题等价于这个有向图是否有环，求环可以使用dfs，记录正在visit的点。

实际上这个dfs稍微改改就是在做拓扑排序。

bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
    vector<int> visit(numCourses, 0);
    vector<int> * v = new vector<int> [numCourses];
    for (auto & p : prerequisites)
        v[p.first].push_back(p.second);
    for (int i=0;i<numCourses;i++)
        if (!dfs(i, v, visit))
            return false;
    return true;
}
bool dfs(int n, vector<int> * v, vector<int> & visit){
    visit[n] = -1;
    for (auto c : v[n]){
        if (visit[c] == -1 || (visit[c] == 0 && !dfs(c, v, visit)))
            return false;
    }
    visit[n] = 1;
    return true;
}

课程表2

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

记录下拓扑排序就可以了。

vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
    vector<int> visit(numCourses, 0);
    vector<int> topo;
    vector<int> * v = new vector<int> [numCourses];
    for (auto & p : prerequisites)
        v[p.first].push_back(p.second);
    for (int i=0;i<numCourses;i++)
        if (!dfs(i, v, visit, topo))
            return {};
    return topo;
}
bool dfs(int n, vector<int> * v, vector<int> & visit, vector<int> &topo){
    if (visit[n] == 1)
        return true;
    visit[n] = -1;
    for (auto c : v[n]){
        if (visit[c] == -1 || (visit[c] == 0 && !dfs(c, v, visit, topo)))
            return false;
    }
    visit[n] = 1;
    topo.push_back(n);
    return true;
}

二叉树中的最大路径和

给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

后序遍历递归，通过引用传参记录最大值，返回的则是经过一点的单线最大值。

int maxPathSum(TreeNode* root) {
    int m = INT_MIN;
    helper(root, m);
    return m;
}
int helper(TreeNode* node, int & m){
    if (node == NULL)
        return 0;
    int lt = max(helper(node->left, m), 0);
    int rt = max(helper(node->right, m), 0);
    m = max(m, lt + rt + node->val);
    return max(lt, rt) + node->val;
}

回溯算法

正则表达式匹配

给定一个字符串 (s) 和一个字符模式 (p)。实现支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
‘.’ 匹配任意单个字符。
‘*’ 匹配零个或多个前面的元素。
匹配应该覆盖整个字符串 (s) ，而不是部分字符串。

简单直接的回溯，时间复杂度直接爆炸。

bool isMatch(string s, string p) {
    return helper(s, p, 0, 0);
}
bool helper(string & s, string & p, int spos, int ppos){
    if (spos < s.size() && ppos < p.size() && (s[spos] == p[ppos] || p[ppos] == '.')){
        if (ppos+1 < p.size() && p[ppos+1] == '*')
            return (helper(s, p, spos+1, ppos + 2) || helper(s, p, spos, ppos+2) ||helper(s, p, spos+1, ppos));
        else
            return helper(s, p, spos+1, ppos+1);
    }else if (ppos+1 < p.size() && p[ppos+1] == '*')
        return helper(s, p, spos, ppos+2);
    else if (spos == s.size() && ppos == p.size())
        return true;
    return false;
}

回溯的问题在于，没有很好利用前面匹配的信息，而是不断试错，可以用二维数组记录一下尝试过的pos值，剪枝。

自底向上的动态规划。

bool isMatch(string s, string p) {
    int m = s.size(), n = p.size();
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
    dp[0][0] = true;
    for (int i = 0; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (j > 1 && p[j - 1] == '*') {
                dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]);
            } else {
                dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
            }
        }
    }
    return dp[m][n];
}

Remove Invalid Parentheses

删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。
说明: 输入可能包含了除 ( 和 ) 以外的字符。

BFS尝试所有结果，速度较慢。

vector<string> removeInvalidParentheses(string s) {
    queue<string> q;
    unordered_map<string, int> m;
    bool found = false;
    vector<string> res;
    q.push(s);
    while(!q.empty()){
        for (int i=q.size();i>0;i--){
            string t = q.front(); q.pop();
            if (m[t] == 1)
                continue;
            else if(isValid(t)){
                m[t] = 1;
                found = true;
                res.push_back(t);
            }
            else{
                m[t] = 1;
                for (int j=0;j<t.size();j++){
                    q.push(t.substr(0, j) + t.substr(j + 1));
                }
            }
        }
        if (found == true)
            return res;
    }
}
bool isValid(string t) {
    int cnt = 0;
    for (int i = 0; i < t.size(); ++i) {
        if (t[i] == '(') ++cnt;
        else if (t[i] == ')' && --cnt < 0) return false;
    }
    return cnt == 0;
}

高票算法。

vector<string> res;
vector<string> removeInvalidParentheses(string s) {
    dfs(s,')',0);
    return res;
}
void dfs(string s, char ch,int last){
    for(int i=0,cnt =0;i<s.size();i++){
            if(s[i] == ')' || s[i] == '(')s[i] == ch ? cnt++:cnt--;
            if(cnt <=0)continue;
            for(int j=last;j<=i;++j){
                if(s[j] ==ch &&(j == last || s[j-1] != ch))
                  dfs(s.substr(0,j)+s.substr(j+1),ch,j);
            }
        return ; //这里的return是第一个for里面的
    }
    reverse(s.begin(),s.end());
    if(ch == ')')return dfs(s,'(',0);
    res.push_back(s);
}

单词拆分

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
这里本来想着用二维组来记录，但是实际上一维组就够了，c[i]代表从0到i的子串是否可分。

c[i] = if(c[j] && str(i,j) exist)

bool wordBreak(string s, vector<string>& wordDict) {
    vector<bool> c(s.size()+1);
    c[0] = 1;
    for (int i=1;i<=s.size();i++){
        for(int j=0;j<i;j++){
            if (c[j] && find(wordDict.begin(), wordDict.end(), s.substr(j,i-j)) != wordDict.end()){
                c[i] = 1;
                break;
            }
        }
    }
    return c[s.size()];
}

排序和搜索

两个排序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。
你可以假设 nums1 和 nums2 不同时为空。
这题思路是很清晰的，但是令人烦恼的是如何优雅处理边界条件，还有代码可读性。
下面的代码是抄了别人的。

比起我自己写的要好很多，一个是虚拟数组长度，另一个是越界的处理，因为最终取值会通过min和max，所以越界的用INT_MIN和INT_MAX代替，这样也反应，有时候不能直接记数组的位置，记值和虚拟数组位置对于奇偶性、越界等问题都解决的很漂亮。

int n = nums1.size();
int m = nums2.size();
if(n > m)   //保证数组1一定最短
    return findMedianSortedArrays(nums2,nums1);
int L1,L2,R1,R2,c1,c2,lo = 0, hi = 2*n;  //我们目前是虚拟加了'#'所以数组1是2*n+1长度
while(lo <= hi)   //二分
{
    c1 = (lo+hi)/2;  //c1是二分的结果
    c2 = m+n- c1;
    L1 = (c1 == 0)?INT_MIN:nums1[(c1-1)/2];   //map to original element
    R1 = (c1 == 2*n)?INT_MAX:nums1[c1/2];
    L2 = (c2 == 0)?INT_MIN:nums2[(c2-1)/2];
    R2 = (c2 == 2*m)?INT_MAX:nums2[c2/2];

    if(L1 > R2)
        hi = c1-1;
    else if(L2 > R1)
        lo = c1+1;
    else
        break;
}
return (max(L1,L2)+ min(R1,R2))/2.0;

数学

最大数

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。
重点是找到那个排序规则，起初我以为，先把数组都变成字符串，然后按序比较，如果都相同则长度较短的放前面，后来发现有问题。比如3和34，显然343 > 334，所以这个规则不成立。

蠢的不行，为什么没想到用结果去比，直接比ab和ba两种拼接谁更大就好了。这其实也说明一个问题，就是贪心在这里是可行的，局部最优和整体最优是等价的。

string largestNumber(vector<int>& nums) {
    vector<string> vs;
    for (auto & num : nums)
        vs.push_back(to_string(num));
    sort(vs.begin(), vs.end(), [](const string& a, const string& b){return (a+b) > (b+a);});
    string r;
    for (auto & s : vs)
        r += s;
    return (r.size() < 1 || r[0] == '0') ? "0" : r;
}

其他

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
比较自然的想法，从左到右遍历时，先找到一个位置a，然后如果出现了不小于a高度的位置b，很显然，a、b位置之间的雨水就已经决定了，后面可以从b开始往右找。
但上述有一个问题，就是如果往右一直找不到更高的，那么算法就没法结束，而且也不代表就不能积水，比如4、2、3这样的排列。此时a一定是最高的那个位置，换成从右往左走就一定能找到。
最后代码就变成从左往右遍历，当没找到更高的，算法无法结束时，从右往左遍历。

也可以先遍历一次找到最高的位置，然后从两端往中间走。

int trap(vector<int>& height) {
    int n=height.size();
    int res=0;
    int i,j;
    for (i=0;i<n;i++){
        int temp=0;
        if (height[i] > 0){
            for (j=i+1;j<n;j++){
                if (height[j] >= height[i]){
                    temp += height[i] * (j - i - 1); 
                    i = j-1;
                    break;
                }else
                    temp -= min(height[j], height[i]);
            }
            res += max(temp, 0);
            if (j == n)
                break;
        }
    }
    for (int m=n-1;m>=i;m--){
        int temp=0;
        if (height[m] > 0){
            for (int k=m-1;k>=i;k--){
                if (height[k] >= height[m]){
                    temp += height[m] * (m - k - 1); 
                    m = k+1;
                    break;
                }else
                    temp -= min(height[m], height[k]);
            }
            res += max(temp, 0);
        }
    }
    return res;
}

动态规划

乘积最大子序列

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
一维的数据结构就足够，但比较坑的是，存在负数，导致前面小的值，再次乘一个负数，可能变成最大值，所以不能只记一个最大值，还要记住最小负数。

因为只用看上一位的结果，所以可以优化成两个整型变量。

int maxProduct(vector<int>& nums) {
    int n = nums.size();
    if (n<1) return 0;
    int posMax = nums[0];
    int negMax = nums[0];
    int r = nums[0];
    for (int i=1;i<n;i++){
        int tempPosMax = posMax;
        posMax = max(nums[i],max(nums[i] * tempPosMax, nums[i] * negMax));
        negMax = min(nums[i],min(nums[i] * negMax, nums[i] * tempPosMax));
        r = max(r, posMax);
    }
    return r;
}

完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

虽然这题放在动态规划里，但不得不说，数学是真的强，这个爆炸快捷的四平方定理。

int numSquares(int n) {
    while (n % 4 == 0) n /= 4;
    if (n % 8 == 7) return 4;
    for (int a = 0; a * a <= n; ++a) {
        int b = sqrt(n - a * a);
        if (a * a + b * b == n) {
            return !!a + !!b;
        }
    }
    return 3;
}