递归

将问题拆分为子问题：将两个有序数组排序，求第k个数。每次递归将k减半，原问题$k=(m+n)/2$.
$O(log(m+n))$

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int tot = nums1.size() + nums2.size();
        if(tot % 2) {
            return find(nums1, 0, nums2, 0, tot / 2 + 1);
        }
        else {
            int left = find(nums1, 0, nums2, 0, tot / 2);
            int right = find(nums1, 0, nums2, 0, tot / 2 + 1);
            return (left + right) / 2.0;
        }
        return 0.0;

    }

    // num1[i]开始的数组和nums[j]开始的数组一起排序后的第k个数是什么
    int find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {
        if(nums1.size() - i > nums2.size() - j) return find(nums2, j, nums1, i, k); 
        // k=1 即求最小数
        if(k == 1) {
            // num1[i:]为空，选择nums[j:]中第k个数
            if(nums1.size() == i) return nums2[j+k-1];
            else return min(nums1[i], nums2[j]);
        }

        // nums1[i:]为空，从nums[j:]中选第k个数
        if(nums1.size() == i) return nums2[j + k - 1];

        // si为nums1[i:]第k/2个数的下一个位置.nums1更短,有可能越界; k可能是奇数
        int si = min((int)nums1.size(), i + k / 2), sj = j + k - k / 2;
        if(nums1[si-1] < nums2[sj-1]) return find(nums1, si, nums2, j, k - (si - i));
        else return find(nums1, i, nums2, sj, k - (sj - j));
    }
};

岛屿数量

目标在边界上

class Solution {
public:
    int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
    vector<vector<char>> g;

    void dfs(int x, int y) {
        g[x][y] = 0;
        for(int i=0; i<4; ++i) {
            int a = x + dx[i], b = y + dy[i];
            if(a >= 0 && a < g.size() && b >= 0 && b < g[a].size() && g[a][b] == '1') {
                dfs(a, b);
            }
        }        
    }

    int numIslands(vector<vector<char>>& grid) {
        g = grid;
        int ret = 0;
        for(int i=0; i<g.size(); ++i) {
            for(int j=0; j<g[i].size(); ++j) {
                if(g[i][j] == '1'){
                    dfs(i, j);
                    ret++;
                }
            }
        }
        return ret;
    }
};

统计封闭岛屿的数目

目标被边界包围

class Solution {
public:
    int n, m;
    int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
    int dfs(int x, int y, vector<vector<int>>& g) {
        int ret = 1;
        g[x][y] = 1;
        for(int i=0; i<4; ++i) {
            int xx = x + dx[i], yy = y + dy[i];
            if(xx < 0 || xx >= n || yy < 0 || yy >= m) {
                ret = 0;
                continue;
            }
            if(!g[xx][yy] && !dfs(xx, yy, g)) ret = 0; // 不合法
        }    
        return ret;
    }

    int closedIsland(vector<vector<int>>& grid) {
        n = grid.size(), m = grid[0].size();
        int ret = 0;
        for(int i=0; i<n; ++i) {
            for(int j=0; j<m; ++j) {
                if(grid[i][j] == 0) ret += dfs(i, j, grid);
            }
        }
        return ret;
    }
};

DFS + 剪枝

$O(n)$

class Solution {
public:
    TreeNode* ans;

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root, p, q);
        return ans;
    }

    int dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || ans) return 0;  // ans不为空，不进行遍历，剪枝
        int state = dfs(root->left, p, q);
        if(root == p) state |= 2;
        else if(root == q) state |= 1;
        state |= dfs(root->right, p, q);
        if(state == 3 && !ans) ans = root;
        return state;
    }
};

多路归并

若为$k$路归并，每次选出一个元素需要$O(1)$，插入新元素需要$O(logk)$，时间复杂度为$O(Nlogk)$。

// 重载括号
struct Cmp{
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 小根堆
        priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;
        auto dummy = new ListNode(-1);
        auto tail = dummy;

        for(auto h: lists) if(h) heap.push(h);
        while(heap.size()) {
            auto t = heap.top();
            heap.pop();
            if(t->next) heap.push(t->next);
            tail->next = t;
            tail = tail->next;
        }
        return dummy->next;
    }
};

C++11泛型写法

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 小根堆
        auto cmp = [](ListNode* a, ListNode* b){return a->val > b->val;};
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> heap(cmp);
        auto dummy = new ListNode(-1);
        auto tail = dummy;

        for(auto h: lists) if(h) heap.push(h);
        while(heap.size()) {
            auto t = heap.top();
            heap.pop();
            if(t->next) heap.push(t->next);
            tail->next = t;
            tail = tail->next;
        }
        return dummy->next;
    }
};

双指针

寻找每次未选择的最小数

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        auto dummy = new ListNode(-1, nullptr);
        auto tail = dummy;
        while(list1 && list2) {
            if(list1->val <= list2->val) tail->next = list1, list1 = list1->next, tail = tail->next;
            else tail->next = list2, list2 = list2->next, tail = tail->next;
        }

        if(list1) tail->next = list1;
        else tail->next = list2;

        return dummy->next;
    }
};

零钱兑换

零钱-物品
总金额-背包容量
零钱面值-物品体积
零钱个数-物品总价值
末尾判断：存在零钱总和等于总金额方案

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<int> f(amount+1, 2e9);
        f[0] = 0;

        for(auto x: coins) {
            for(int j=x; j<=amount; ++j) {
                f[j] = min(f[j], f[j-x] + 1);
            }
        }
        if(f[amount] == 2e9) return -1;
        return f[amount];

    }
};

零钱兑换II

状态属性：方案数量

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<int> f(amount+1, 0);
        f[0] = 1;

        for(auto x: coins) {
            for(int j=x; j<=amount; ++j) {
                f[j] += f[j-x];
            }
        }
        return f[amount];
    }
};

前缀和+链表删除

$O(n)$

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        unordered_map<int, ListNode*> hash;
        auto dummy = new ListNode(0, head);
        hash[0] = dummy;

        int sum = 0;
        while(head) {
            sum += head->val;
            if(hash.count(sum)) {
                auto p = hash[sum];      
                int tmp = sum;          
                for(auto q = p->next; q != head; q = q->next) {
                    tmp += q->val;
                    hash.erase(tmp);
                }
                p->next = head->next;
            }
            else {
                hash[sum] = head;
            }
            head = head->next;
        }
        return dummy->next;
    }
};

判断合法括号序列问题

题库关键词：括号序列
$O(n)$
左括号进栈 优化空间复杂度-> 遍历字符，记录左括号数量，若遍历过程中出现负数则为false
星号处理：用 low 和 high 记录左括号的数量范围，若出现 low > high 则为false
边界条件：low 最小值为0

class Solution {
public:
    bool checkValidString(string s) {
        int low = 0, high = 0;
        for(auto c: s) {
            if(c == '(') low++, high++;
            else if(c == ')') low--, high--;
            else low--, high++;
            low = max(0, low);
            if(low > high) return false;
        }
        return low == 0;
    }
};

二维数组中的查找

每一行递增，每一列递增，但行末元素不一定大于下一行首元素.
$O(n+m)$

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.size()==0 || matrix[0].size()==0) return false;
        int n = matrix.size(), m = matrix[0].size();
        int i = 0, j = m - 1;
        while(i < n && j >= 0) {
            if(matrix[i][j] == target) return true;
            if(matrix[i][j] > target) --j;
            else ++i;
        }
        return false;
    }
};

搜索二维矩阵

二分+矩阵坐标变换
$O(log(nm))$

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size() == 0 || matrix[0].size() == 0) return false;
        int n = matrix.size(), m = matrix[0].size();
        int i = 0, j = n * m - 1;
        while(i < j) {
            int mid = (i + j) >> 1;
            if(matrix[mid / m][mid % m] >= target) j = mid;
            else i = mid + 1;
        }
        if(matrix[i/m][i%m] == target) return true;
        return false;
    }
};

解法一

结论：尽可能拆分为2和3，且2不超过两个

class Solution {
public:
    int integerBreak(int n) {
        if(n <= 3) return 1 * (n - 1);
        int ret = 1;
        while(n >= 5) n -= 3, ret *= 3;
        return n * ret;
    }
};

解法二 DP

状态表示：$dp[i]$表示将$i$拆分后的最大乘积
状态方程：$dp[i] = max(dp[i], j * (i-j), j * dp[i-j])$

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1, 0);
        dp[2] = 1;
        for(int i=3; i<=n; ++i) {
            for(int j=1; j<=i/2; ++j) {
                dp[i] = max(dp[i], j * (i-j));
                dp[i] = max(dp[i], j * dp[i-j]);
            }
        }

        // for(int i=2; i<=n; ++i) printf("%d ", dp[i]);
        return dp[n];
    }
};