题库

题库+题解

排序+双指针，排序加上双指针可以简化定和搜索。排序可以将相同元素邻接。时间复杂度O(n^2)。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i ++ )
        {
            //因为要不重复，所以当前如果在之前出现过就跳过，排序的好处体现在这里
            if (i - 1 >=0 && nums[i - 1] == nums[i]) continue;
            int target = -nums[i];

            //第i个左边的都遍历过了，只考虑右边即可。
            int l = i + 1, r = nums.size() - 1;
            //双指针过程
            while (l < r)
            {
                if (nums[l] + nums[r] < target) l ++ ;
                else if (nums[l] + nums[r] > target) r -- ;
                else 
                {
                    vector<int> cur;
                    cur.push_back(nums[i]);
                    cur.push_back(nums[l]);
                    cur.push_back(nums[r]);
                    ans.push_back(cur);
                    //重复的直接跳过
                    while (l + 1 <= nums.size() - 1 && nums[l + 1] == nums[l]) l ++ ;
                    while (r - 1 >= 0 && nums[r - 1] == nums[r]) r -- ;
                    l ++ , r -- ;
                }
            }
        }

        return ans;
    }
};

LC.1467 两个盒子中球的颜色数相同的概率（困难）

首先要知道可重复排列数计算原理和公式，假设有1122333这样的数，要求不重复的排列数，就要用到可重复排列数计算公式。思想是首先将所有的相同的数看做不同，求总共的排列数，假设一共有sum个数，有sum!种排列方式。再对于每一种数，除以重复的种数的全排列，用公式表达如下：

$res = \frac{(S_1 + S_2 + ... + S_n)!}{S_1!*S_2!*...*S_n!}$

其中Si表示第i个数出现的次数。这样可以计算出概率的分母，对于分子，首先其必须满足分成两部分之后，左边和右边的种类数相同，然后对于左边和右边分别计算可重复排列数，并且利用乘法原理，得到最终合并之后的排列数。另外dfs过程中需要剪枝，当左边总和个数的两倍大于整体总和的时候不要继续计算了。

这道题是典型的概率类题目，之前没遇到过，记录一下。

double fact[50];

class Solution {
public:
    //计算阶乘
    void factorial()
    {
        fact[0] = 1;
        for (int i = 1; i <= 48; i ++ )
            fact[i] = fact[i - 1] * i;
    }
    //计算可重复排列数
    double get(vector<int>& balls)
    {
        int sum = 0;
        for (int i = 0; i < balls.size(); i ++ ) sum += balls[i];
        double res = fact[sum];
        for (int i = 0; i < balls.size(); i ++ ) res /= fact[balls[i]];
        return res;
    }

    //通过dfs计算所有可能的情况
    double dfs(int u, int ts, int ls, int rs, vector<int>& left, vector<int>& right, vector<int>& balls)
    {
        //剪枝
        if (ls * 2 > ts || rs * 2 > ts) return 0;
        double res = 0;
        if (u == balls.size())
        {
            int l = 0, r = 0;
            for (int i = 0; i < left.size(); i ++ )
                if (left[i]) l += 1;
            for (int i = 0; i < right.size(); i ++ )
                if (right[i]) r += 1;
            //如果左右种类数不同，不可能产生答案，直接返回0
            if (l != r) return 0;
            return get(left) * get(right);
        }
        //对于每一种球分别枚举
        for (int i = 0; i <= balls[u]; i ++ )
        {
            left[u] = i, right[u] = balls[u] - i;
            res += dfs(u + 1, ts, ls + i, rs + balls[u] - i, left, right, balls);
        }
        return res;
    }

    double getProbability(vector<int>& balls) {
        int n = balls.size();
        int sum = 0;
        for (int i = 0; i < balls.size(); i ++ ) sum += balls[i];
        factorial();
        double down = get(balls);
        vector<int> left(n, 0), right(n, 0);
        double up = dfs(0, sum, 0, 0, left, right, balls);
        return up / down;
    }
};

LC.5438 制作m束花所需的最少天数（中等）

这是周赛的第三题，答案有一个范围，并且验证答案的时间在O(n)，且具有单调性（如果第x天无法制作那么小于x天都不行，如果x天可以制作，那么大于x天都可以制作），数据规模在10^5，因此O(nlogn)的二分算法可以完成这道题。

class Solution {
public:
    int minDays(vector<int>& bd, int m, int k) {
        int n = bd.size();
        //无论如果都不能制作只有花数量不够
        if (m * k > n) return -1;

        //答案是在最小值和最大值之间，增加效率
        int l = INT_MAX, r = INT_MIN;

        for (int i = 0; i < n; i ++ )
        {
            l = min(l, bd[i]);
            r = max(r, bd[i]);
        }

        //标准二分查找答案模板
        while (l < r)
        {
            int mid = l + r >> 1;

            if (check(bd, mid, m, k)) r = mid;
            else l = mid + 1;
        }

        return l;
    }

    //check函数用O(n)的时间判断是否当前答案可行
    //这里判断是否可行有点贪心的意味
    bool check(vector<int>& bd, int mid, int m, int k)
    {
        int cnt = 0;
        int ans = 0;
        for (int i = 0; i < bd.size(); i ++ )
        {
            //如果已经过了开花时间，则连续花数 + 1
            if (bd[i] <= mid)
            {
                cnt ++ ;
                //如果有k朵花了，可以做个束
                if (cnt >= k)
                {
                    ans ++ ;
                    //当前连续花数清零
                    cnt = 0;
                }
            }
            else cnt = 0;
        }

        if (ans >= m) return true;
        else return false;
    }
};

AW.342 道路与航线（中等）

这题很有意思，是图论的题，里面使用了堆优化的dijkstra + 拓扑排序 + dfs，看起来很难写，但是事实如果理清关系，是比较好写的一道题。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 25010, M = 150010, INF = 0x3f3f3f3f;

int h[N], e[M], ne[M], w[M], idx;
int dist[N];
bool st[N];
int id[N];
int din[N];
int bid;
vector<int> block[N];
queue<int> q;

int n, mr, mp, s;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u, int bid)
{
    id[u] = bid;
    block[bid].push_back(u);

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!id[j])
            dfs(j, bid);
    }
}

void dijkstra(int bid)
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    for (int i = 0; i < block[bid].size(); i ++ )
    {
        int j = block[bid][i];
        heap.push({dist[j], j});
    }

    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.y, distance = t.x;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (id[ver] != id[j]) 
            {
                din[id[j]] -- ;
                if (din[id[j]] == 0)
                    q.push(id[j]);
            }
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                if (id[ver] == id[j])
                    heap.push({dist[j], j});
            }
        }
    }
}

void top_sort()
{
    memset(dist, 0x3f, sizeof dist);

    dist[s] = 0;

    for (int i = 1; i <= bid; i ++ )
        if (!din[i])
            q.push(i);

    while (q.size())
    {
        int t = q.front();
        q.pop();

        dijkstra(t);
    }
}

int main()
{
    cin >> n >> mr >> mp >> s;
    memset(h, -1, sizeof h);

    for (int i = 0; i < mr; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    for (int i = 1; i <= n; i ++ )
        if (!id[i])
            dfs(i, ++ bid);

    for (int i = 0; i < mp; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        din[id[b]] ++ ;
    }

    top_sort();

    for (int i = 1; i <= n; i ++ )
        if (dist[i] > INF / 2) cout << "NO PATH" << endl;
        else cout << dist[i] << endl;

    return 0;
}

LC.1477 找两个和为目标值且不重叠的子数组

这题的数据保证了每一个数都是正数，因此双指针算法很容易每次寻找一个区间，使得当前区间的和为target。如果要找两个和为目标值且不重叠的子数组，只需要记忆化之前所有的答案，f[i] 定义为从0到i的子数组满足和为target的最短长度，以动态规划的思想，可以每次得到f[i] = min(i - j + 1, f[i - 1])用O(1)的时间复杂度更新。很容易想到双指针算法去寻找一个区间，但是对于两个区间，没有及时想到记忆化的方法。

这里双指针应该用i做循环，这样每次计算f[i]比较容易。

这题融合了双指针算法和动态规划的思想，是好题。

class Solution {
public:
    int minSumOfLengths(vector<int>& arr, int target) {
        int n = arr.size();
        vector<int> f(n, 1e8);

        int res = 1e8;
        for (int i = 0, j = 0, sum = 0; i < n; i ++ )
        {
            sum += arr[i];
            while (sum > target) sum -= arr[j ++ ];
            if (sum == target)
            {
                if (j) res = min(res, i - j + 1 + f[j - 1]);
                f[i] = i - j + 1;
            }
            if (i) f[i] = min(f[i], f[i - 1]);
        }

        if (res > arr.size()) res = -1;
        return res;
    }
};

LC.10 正则表达式匹配（困难）

动态规划，dp[i][j]表示s串前i个字符和p串前j个字符是否匹配。初始条件是空串一定匹配，且s的空串可以匹配任意个以.*开头的p串位置。之后对于最后一个p串位置的字符分类讨论：

p[j] != ‘*’ : 此时p[j]有两种可能，’.’或者字符，这样就是普通的匹配，如果s[i] == p[j]那么就依赖于dp[i - 1][j - 1]，否则就不可能匹配，为false。
p[j] == ‘‘ : 的意思是匹配0个或多个前边一个字符。如果匹配0个，那么当前结果依赖dp[i][j - 2]，如果匹配多个之前的字符，是依赖dp[i - 1][j - 3]、dp[i - 2][j - 4]...如此代码会比较难写，且增加时间复杂度。从i角度来看，其实是看dp[i - 1][j]，表示当前s串的第i个字符能否被j这个*所取代。

整体的转移方程如下：

$f[i][j] = \left\{ \begin{array} if (p[j]\ ≠\ '*') = \left\{ \begin{array} f[i - 1][j - 1], & matches(s[i], p[j])\\ false, & otherwise\\ \end{array} \right. \\ otherwise = \left\{ \begin{array} f[i - 1][j]\ or\ f[i][j - 2],& matches(s[i], p[j - 1])\\ f[i][j - 2], & otherwise\\ \end{array} \right.\\ \end{array} \right.$

class Solution {
public:
    bool isMatch(string s, string p) {
        // 将s与p加上一个空格来对齐下标和个数
        s = ' ' + s;
        p = ' ' + p;
        int n = s.size(), m = p.size();
        vector<vector<bool>> f(n, vector<bool>(m, false));

        //空串和空串一定匹配
        f[0][0] = true;
        //空串可以匹配所有p中形如a*的前缀
        for (int j = 1; j < m; j ++ )
            if (p[j] == '*') f[0][j] = f[0][j - 2];

        for (int i = 1; i < n; i ++ )
            for (int j = 1; j < m; j ++ )
            {
                   //如果不是*则需要看前一个是什么以及当前是否匹配
                if (p[j] != '*') f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');
                else
                {
                    //如果是*则需要考虑p的前一个和当前是否匹配，如果匹配，有两种选择
                    if (s[i] == p[j - 1] || p[j - 1] == '.') f[i][j] = f[i - 1][j] || f[i][j - 2];
                    //否则只能p轮空
                    else f[i][j] = f[i][j - 2];
                }
            }

        return f[n - 1][m - 1];
    }
};

LC.124 二叉树中的最大路径和（困难）

这题主要是想总结一下树的题目主要考点。对于二叉树来说，90%都需要使用递归的方式来解决，一般是先递归解决左子树，再递归解决右子树。思考方式主要从以下几个方面：

想清楚当前层该问题是如何解决的，如何利用左子树和右子树已知的答案得到当前根节点的答案，有些树状dp的意思。
想清楚叶子节点的子节点，为nullptr的节点应该如何给上一层提供信息，也就是边界问题，或者是递归出口。
对于树中每一个节点，先考虑递归解决左子树相同的问题，再递归解决右子树相同的问题，之后返回当前节点的问题答案。

class Solution {
public:
    const int INF = 0x3f3f3f3f;
    int ans = -INF;
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return ans;
    }

    int dfs(TreeNode* root)
    {
        if (root == nullptr) return -INF;
        int val = root -> val;
        int left = dfs(root ->left);
        int right = dfs(root ->right);

        ans = max(ans, max({left, right, 0}) + val);
        ans = max(ans, left + right + val);

        return max({left, right, 0}) + val;
    }
};

LC.1488 避免洪水泛滥（中等）

194周赛第三题，思路是贪心。这里可以通过预处理得到当前天下一次下雨的时间点，因此可以通过贪心，每一次不下雨抽水时，优先抽走马上下次要下雨的的坑。找到马上要下雨的坑，可以通过堆来实现（寻找一个集合中的最小值）。

贪心证明首先考虑，任意一种抽水方法，如果能完成最终任务，都可以通过排序转换为当前贪心的方法。再思考，如果这样抽水最终还是无法完成防洪的任务，那么调换顺序之后，一定会更早的洪水泛滥。因此从正反两方面可以证明当前贪心是正确的。

class Solution {
public:
    vector<int> avoidFlood(vector<int>& rains) {
        unordered_map<int, int> hash;
        int n = rains.size();
        vector<int> next(n, n + 1);
        for (int i = n - 1; i >= 0; i -- )
        {
            int r = rains[i];
            if (hash.count(r) == 0) hash[r] = i;
            else 
            {
                next[i] = hash[r];
                hash[r] = i;
            }
        }

        typedef pair<int, int> PII;
        priority_queue<PII, vector<PII>, greater<PII>> heap;
        unordered_set<int> S;
        vector<int> ans;

        for (int i = 0; i < n; i ++ )
        {
            int r = rains[i];
            if (r > 0)
            {
                ans.push_back(-1);
                if (S.count(r)) return {};
                else
                {
                    S.insert(r);
                    heap.push({next[i], r});
                }
            }
            else
            {
                if (heap.empty()) ans.push_back(1);
                else{
                    auto t = heap.top();
                    heap.pop();

                    int r = t.second;
                    S.erase(r);
                    ans.push_back(r);
                }
            }
        }

        return ans;
    }
};

LC.41 缺失的第一个正数（困难）

这道题一个隐藏的思路是，下标都是从0到n - 1递增的，如果我们能将所有不超过n的数值都按规律填好，那么就可以很轻松的找到对应第一个未出现的正整数。这里如果发现已经填好的数，则跳过，如果发现置换之后死循环，也要处理。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i ++ )
        {
            //如果已经填好的数，则可以跳过
            if (nums[i] == i + 1) continue;

            while (nums[i] >= 1 && nums[i] <= n)
            {
                int t = nums[nums[i] - 1];
                //如果换了的数和现在的数一样，那其实换下去没有意义，会死循环
                if (t == nums[i]) break;
                nums[nums[i] - 1] = nums[i];
                nums[i] = t;
            }
        }

        //找到第一个没有出现过的数
        for (int i = 0; i < n; i ++ )
            if (nums[i] != i + 1)
                return i + 1;

        return n + 1;
    }
};

LC.1498 满足条件的子序列数目（中等）

周赛第三题，首先读题之后，判断题目最终所求信息和数组内元素顺序无关，这样可以考虑先排序试试。如果排序，可以得到有序序列，有序序列的特点是第一个元素最小，最后一个元素最大，且单调递增。因此可以考虑使用双指针算法来求解两数相加对于某个target和的问题。

class Solution {
public:
    const int mod = 1e9 + 7;
    int numSubseq(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> pow2(n + 1);

        pow2[0] = 1;
        //这里可以先预处理出2的n次幂，之后每次要增加2的n次幂种情况，就直接调用了。
        for (int i = 1; i <= n; i ++ )
            pow2[i] = (pow2[i - 1] * 2) % mod;
        //排序，想到这里很重要
        sort(nums.begin(), nums.end());

        //标准的双指针算法
        int ans = 0;
        for (int i = 0, j = n - 1; i < n; i ++ )
        {
            while (i <= j && nums[i] + nums[j] > target) j -- ;
            if (i > j) break;

            ans = (ans + pow2[j - i]) % mod;
        }

        return ans;
    }
};

LC.718 最长重复子数组（中等）

本题有三种解法，很有意思。

动态规划解法，f[i][j]表示A数组的第i个数字和B数组的第j个数字作为最长公共子数组的最后一位时，最长公共子串长度。
滑动窗口解法。从后向前每次枚举重叠区间，再从前向后每次枚举重叠区间，作为窗口。窗口内部每次比较所有子串最长重叠每次取max。这里是固定了重叠位置，进行了枚举，因此减少了之前的重复计算。
哈希表 + 二分查找解法。Rabin-Karp算法，其实本质就是字符串哈希，字符串哈希可以线性时间复杂度检测字符串中长度为特定长度的子串。再加上二分，可以将时间复杂度降低为O((n + m)log(Min(n, m)))。

//动态规划解法
class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int n = A.size(), m = B.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));

        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                if (A[i - 1] == B[j - 1])
                    f[i][j] = f[i - 1][j - 1] + 1;
                else f[i][j] = 0;
        int res = 0;

        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                res = max(res, f[i][j]);

        return res;
    }
};

//滑动窗口解法
class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int n = A.size(), m = B.size();
        int ans = 0;
        for (int i = 0, j = m - 1; j >= 0; j -- )
        {
            int len = 0;
            for (int k = 0; j + k < m && i + k < n; k ++ )
            {
                if (A[i + k] == B[j + k]) len ++ ;
                else len = 0;
                ans = max(ans, len);
            }
        }

        for (int i = n - 1, j = 0; i >= 0; i -- )
        {
            int len = 0;
            for (int k = 0; i + k < n && j + k < m; k ++ )
            {
                if (A[i + k] == B[j + k]) len ++ ;
                else len = 0;
                ans = max(ans, len);
            }
        }

        return ans;
    }
};

//哈希表 + 二分查找
typedef unsigned long long ULL;

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int n = A.size(), m = B.size();
        int l = 0, r = min(n, m);

        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (calHash(A, B, mid)) l = mid;
            else r = mid - 1;
        }

        return r;
    }

    bool calHash(vector<int>& A, vector<int>& B, int len)
    {
        int p = 113;
        ULL res = 0;
        int n = A.size(), m = B.size();
        unordered_set<ULL> hashA;

        for (int i = 0; i <= len - 1; i ++ )
        {
            res = res * p;
            res = res + A[i];
        }
        hashA.insert(res);

        ULL mult = qmi(p, len - 1);
        for (int i = 1; i + len - 1 < n; i ++ )
        {
            res = (res - A[i - 1] * mult) * p + A[i + len - 1]; 
            hashA.insert(res);
        }

        res = 0;
        for (int i = 0; i <= len - 1; i ++ )
        {
            res = res * p;
            res = res + B[i];
        }

        if (hashA.count(res)) return true;
        for (int i = 1; i + len - 1 < m; i ++ )
        {
            res = (res - B[i - 1] * mult) * p + B[i + len - 1];
            if (hashA.count(res)) return true;
        }

        return false;
    }

    ULL qmi(ULL p, int k)
    {
        ULL res = 1;
        while (k)
        {
            if (k & 1) res = res * p;
            p = p * p;
            k >>= 1;
        }

        return res;
    }
};

LC.剑指Offer 62 圆圈中最后剩下的数字（简单）

经典的约瑟夫环问题，如果直接链表模拟，会导致TLE。仔细思考应该发现，如果定义f(n, m)为圆圈中最后剩下的数字，可以通过下述公式利用f(n - 1, m)计算，并且当n == 1时， f(1, m) = 0,也就是一定会剩下编号为0的节点。在递归公式中则将f(n - 1, m)看做了偏移量，每次n都减少，就正好对应了删除元素的意义。

class Solution {
public:
    int lastRemaining(int n, int m) {
        return f(n, m);
    }

    int f(int n, int m)
    {
        if (n == 1) return 0;

        return (m % n + f(n - 1, m)) % n;
    }
};

LC.378 有序矩阵中的第K小的元素（中等）

本题和排序矩阵查找是同一题，在于发现矩阵部分排序之后的特征。如果从左下角开始向上查找，则每次查找不需要向左，每次j只会递增。在这道题里就可以通过二分统计元素个数来最终得到答案。另外，这里要找的答案一定要在矩阵中，但是二分不保证结果一定在矩阵里，为什么还能得到正确答案呢？仔细思考后发现，如果每次统计的是小于等于mid的个数，这时如果满足条件，是右边界收缩，最终一定会靠拢到左侧边界（如果真正答案右侧还有同样满足条件的不存在于矩阵中的数，并且肯定左侧不可能有满足条件且不存在于矩阵中的数），这些满足条件的不存在的数，会因为靠拢到左边界而被排除掉，因此最终答案一定是矩阵中的数。

举例子来说：1 3 (4 5 6) 7, k = 2，那么3,4,5,6都会满足check函数，而每次收缩到4,5,6的时候，r都会向3靠拢，直到r = 3。或者理解为l = mid + 1的条件是l一定不满足check函数，那么一定不会收缩到不存在的数字。

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size(), m = matrix[0].size();
        int l = matrix[0][0], r = matrix[n - 1][m - 1];

        while (l < r)
        {
            int mid = l + r >> 1;
            //如果包含mid更小的值的数量大于等于k个，说明mid要更小才行
            if (check(matrix, mid, k)) r = mid;
            else l = mid + 1;
        }

        return l;
    }

    bool check(vector<vector<int>>& matrix, int mid, int k)
    {
        int n = matrix.size(), m = matrix[0].size();
        int i = n - 1, j = 0;
        int cnt = 0;
        //需要统计所有小于等于mid的值
        while (i >= 0 && j < m)
        {
            while (j < m && matrix[i][j] <= mid) j ++ ;
            cnt += j;
            i -- ;
        }

        while (i >= 0)
        {
            cnt += j;
            i -- ;
        }
        //当这个值>=k的时候，mid可能是第k个，也可能比第k个大
        //当<k时，包括mid的这些值全加起来也不到k个，因此答案一定严格大于mid
        return cnt >= k;
    }
};

LC.315 计算右侧小于当前元素的个数（困难）

由于没有给数据范围，假设数据可以随便在int范围之内取值的话，需要首先离散化。这里离散化时保序的，因为每次需要知道比当前值小的数有多少个，因此保序离散化之后使用树状数组可以得到答案。树状数组可以O(logn)的时间复杂度计算前缀和，将个数作为树状数的存储值。

class Solution {
public:
    vector<int> tr;
    int n;

    int lowbit(int x)
    {
        return x & -x;
    }

    void add(int x, int c)
    {
        for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    }

    int sum(int x)
    {
        int res = 0;
        for (int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }

    int find(int x, vector<int>& count)
    {
        int l = 0, r = count.size() - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (count[mid] <= x) l = mid;
            else r = mid - 1;
        }

        return l;
    }
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> ans;
        vector<int> count;
        vector<int> temp;
        for (int i = 0; i < nums.size(); i ++ ) temp.push_back(nums[i]);

        sort(nums.begin(), nums.end());
        nums.erase(unique(nums.begin(), nums.end()), nums.end());

        n = nums.size();
        tr.resize(n + 1, 0);
        ans.resize(temp.size(), 0);

        for (int i = temp.size() - 1; i >= 0; i -- )
        {
            int p = find(temp[i], nums);
            ans[i] = sum(p);
            add(p + 1, 1);
        }
        return ans;     
    }
};

LC.174 地下城游戏（困难）

动态规划的题，但是比较不太好想的是要从公主的房间开始倒着写DP。dp[i][j]表示到坐标为（i,j）的房间时，骑士所需要的最小血量。如果最小血量为负数，那么至少要有1点即可。

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& g) {
        int n = g.size(), m = g[0].size();

        vector<vector<int>> f(n, vector<int>(m, 1));
        //初始化公主所在房间的血量
        f[n - 1][m - 1] = max(1, 1 - g[n - 1][m - 1]);
        //初始化最后一列的所有房间的血量，因为只能向下走，所以是确定的
        for (int i = n - 2; i >= 0; i -- )
            f[i][m - 1] = max(1, f[i + 1][m - 1] - g[i][m - 1]);
        //初始化最后一行的所有房间的血量，因为只能向右走，所以是确定的
        for (int j = m - 2; j >= 0; j -- )
            f[n - 1][j] = max(1, f[n - 1][j + 1] - g[n - 1][j]);
        //剩余房间的血量是由下方和右方需要血量的最小值决定的，但是不能是负数
        for (int i = n - 2; i >= 0; i -- )
            for (int j = m - 2; j >= 0; j -- )
                f[i][j] = max(1, min(f[i + 1][j] - g[i][j], f[i][j + 1] - g[i][j]));

        return f[0][0];
    }
};

LC.1499 满足不等式的最大值（困难）

首先题目给出的性质x从小到大排序，要求的表达式中有绝对值符号，这样我们可以认为定义一个顺序，将绝对值符号去掉。这样就把下标相同的x和y放到一起，可以分开处理。这种方法在之前LC有题目也是这样分开处理的。在题目中限制中需要i和j的x下标之差<=k，意味着当某一个下标确定的时候，另一个下标正好是大小为k的滑动窗口内的最大值时，可以求得整体的最大值。这样抽象之后，可以使用单调队列解决。

//用x作为下标的版本
class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        deque<pair<int, int>> q;
        int res = INT_MIN;

        for (int i = 0; i < points.size(); i ++ )
        {
            int x = points[i][0], y = points[i][1];
            while (q.size() && x - q.front().first > k) q.pop_front();
            if (i && q.size()) res = max(res, q.front().second + x + y);
            while (q.size() && y - x >= q.back().second) q.pop_back();
            q.push_back({x, y - x});
        }

        return res;
    }
};

//用i作为下标版本
class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        deque<int> q;
        int res = INT_MIN;

        for (int i = 0; i < points.size(); i ++ )
        {
            int x = points[i][0], y = points[i][1];
            while (q.size() && x - points[q.front()][0] > k) q.pop_front();
            if (q.size()) res = max(res, x + y + points[q.front()][1] - points[q.front()][0]);
            while (q.size() && y - x > points[q.back()][1] - points[q.back()][0]) q.pop_back();
            q.push_back(i);
        }

        return res;
    }
};

LC.1504 统计全1子矩阵

计数的问题重点在于不重不漏，找到某种方法将所有的答案统计在内。这里参考85题的方式来枚举所有的子矩阵，即右下角元素作为矩阵的标志，枚举每次的宽度来不重复的枚举。当然这里也可以使用85题的方式用单调队列优化，得到O(n^2)的时间复杂解法。

这里有点动态规划的思想，就是先需要预处理好以i,j为最下边1的最长个数，这样就变成了84题的问题。

//直接解法O(n^3)
class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        vector<vector<int>> f(n, vector<int>(m, 0));

        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
            {
                if (mat[i][j]) 
                {
                    f[i][j] = 1;
                    if (i) f[i][j] += f[i - 1][j];
                }
            }
        int res = 0;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
            {
                if (f[i][j])
                {
                    int w = 1;
                    int s = f[i][j];
                    res += s;
                    while (j >= w && f[i][j - w])
                    {
                        s = min(s, f[i][j - w]);
                        res += s;
                        w ++ ;
                    }
                }
            }

        return res;
    }
};

//O(n^2)的单调队列优化
class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        vector<vector<int>> f(n, vector<int>(m, 0));

        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
            {
                if (mat[i][j]) 
                {
                    f[i][j] = 1;
                    if (i) f[i][j] += f[i - 1][j];
                }
            }
        int res = 0;
        for (int i = 0; i < n; i ++ )
        {
            //因为每次计算当前总共个数，涉及到上一个最小位置的结果，要存储一下
            stack<pair<int, int>> stk;
            for (int j = 0; j < m; j ++ )
            {
                int s = 0;
                //单调递增栈，找左侧第一个小于当前值的位置
                while (stk.size() && f[i][j] <= f[i][stk.top().first]) stk.pop();
                if (stk.size()) 
                {
                    //如果栈不空则需要加上当前到上一个最小之间的结果个数
                    s += (j - stk.top().first) * f[i][j];
                    //同时左侧第一个更小的结果个数里的每一个，当前也需要加上才对
                    s += stk.top().second;
                }
                else s += (j + 1) * f[i][j]; //如果栈空的话，说明左侧全都比当前的大，那么长度就是j + 1，且没有上一个更小的数了，不存在上边的第二项
                stk.push({j, s});
                res += s;
            }
        }

        return res;
    }
};

LC.1505 最多K次交换相邻数位后得到的最小整数（困难）

题目首先是贪心性质，对于一个长整数来说，在k次交换之内将可以交换到的最小的数字交换到最高位肯定构造出的数字更小。假设当前最高位不是最小数字，那么一定存在一个和当前一样的交换，将k次之内可交换的最小值交换到最高位，得到的数字严格小于当前值。另外一个贪心性质是，当有多个数字重复的时候，一定是将排位最近的一个换到第一个最节约k的次数，因此之后所能构造出来的整数有可能会更小。

在实现上，可以用10个队列来存储0-9数字的出现位置，并且按照从前到后的顺序遍历得到一个序列，每次从序列头取出元素保证每次得到的都是最靠前的一个数字。另外，每次一个数字经过k次调换到最高位时，相当于将所有最高位和当前位置之间的数字向后挪一位，相当于其下标全部 + 1，可以看做是区间的增加操作，每次获取某一个数的下标偏移量时，相当于求和操作，可以利用树状数组和差分来实现，降低时间复杂度。如果直接使用差分，则求下标的时间复杂度还是O(n)在当前数据规模下不符合要求，因此要使用树状数组来加速操作。

class Solution {
public:
    int n;
    vector<int> tr;

    int lowbit(int x)
    {
        return x & -x;
    }

    void add(int x, int c)
    {
        for (int i = x; i <= n; i += lowbit(i)) 
            tr[i] += c;
    }

    int sum(int x)
    {
        int res = 0;
        for (int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }

    string minInteger(string num, int k) {
        n = num.size();
        tr.resize(n + 1, 0);
        //用10个队列存储每一种数字出现的下标，按先后顺序存储
        queue<int> q[10];
        num = ' ' + num;

        for (int i = 1; i <= n; i ++ )
        {
            int t = num[i] - '0';
            q[t].push(i);
        }

        string ans;
        //枚举每一位应该是什么数
        for (int i = 1; i <= n; i ++ )
        {
            //按顺序从队列里面取，这样先取到的是最小的数，别忘了break
            for (int j = 0; j < 10; j ++ )
            {
                if (!q[j].size()) continue;
                //t是在原数组中的下标
                int t = q[j].front();
                //pos是t + 偏移量之后，最新的下标
                int pos = t + sum(t);
                //这里要判断当前最新下标和正在枚举的位置之前转换次数是否大于k
                if (pos - i <= k)
                {
                    ans += j + '0';
                    //差分，相当于从1到t - 1的下标全部 + 1
                    //因为所有出队之后的数不会再次用到，并且t位置之前的数字都是按照顺序的
                    //因此可以直接将1到t - 1都右移1，已经用过的数字没有影响
                    add(1, 1), add(t, -1);
                    q[j].pop();
                    k -= pos - i;
                    break;
                }
            }
        }

        return ans;
    }
};

AW.244 谜一样的牛（简单）

树状数组 + 二分查找。树状数组存储个数的话，存储的是从1~x的所有数个数，如果一定要存储小于x的所有数个数，逻辑会麻烦一些，因此不要那么存。将查找一个数之前有x个数的位置，转换为查找当前数是第x + 1个数，就能符合上述逻辑。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int tr[N];
int a[N];
int n;

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int c)
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

int sum(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main()
{
    cin >> n;
    for (int i = 2; i <= n; i ++ ) cin >> a[i];
    //从1~i一共有多少个数
    for (int i = 1; i <= n; i ++ ) add(i, 1);

    for (int i = n; i >= 1; i -- )
    {
        //一个数之前有a[i]个数，则当前数是第a[i] + 1个
        int k = a[i] + 1;
        int l = 1, r = n;
        while (l < r)
        {
            int mid = l + r >> 1;
            //如果包括自己一共有k个，则当前数就是第k个数
            //因为找的是第一个满足k个的位置，所以要求左边界
            if (sum(mid) >= k) r = mid;
            else l = mid + 1;
        }
        add(l, -1);
        a[i] = l;
    }

    for (int i = 1; i <= n; i ++ )
        cout << a[i] << endl;

    return 0;
}

LC.剑指offer 60.n个骰子的点数

这题的解决方式不难，但是对于状态定义和思考方式比较值得借鉴，并借此总结一下DP的状态思考。

动态规划状态思考方式主要抓住以下几个方面，会更容易思考清楚：

首先要举例子，将题目的情况写几个简单的例子，考虑其中能否将当前问题递归为更小问题解决的可能（最优子结构）。
其次要寻找独立变量，通过独立变量，能将题目中抽象出来的某个状态确定下来。比如骰子这题就是骰子个数和总共的点数，这两个变量可以确定当前投一次骰子后的状态。（确定状态）
最后要思考最后一步。这里需要和当前状态一起思考，上一个可能的状态到当前状态变化在哪？最后一步做了什么？这里说白了就是在思考状态是如何转移的。比如这题就是最后一个骰子的点数，并且根据总点数，可以得到上一次的总点数，这样就可以确信状态定义也是正确的了。（确定状态转移方程）

//f[i][j]表示第i个骰子时，点数总和为j的概率
class Solution {
public:
    vector<double> twoSum(int n) {
        vector<vector<double>> f(n + 1, vector<double>(6 * n + 1));

        for (int j = 1; j <= 6; j ++ ) f[1][j] = 1 / 6.0;

        for (int i = 2; i <= n; i ++ )
            for (int j = i; j <= 6 * i; j ++ )
            {
                double t = 0;
                for (int k = 1; k <= 6; k ++ )
                {
                    if (j - k >= 1) t += f[i - 1][j - k];
                }
                f[i][j] = t / 6.0;
            }

        vector<double> ans;
        for (int j = n; j <= 6 * n; j ++ )
            ans.push_back(f[n][j]);

        return ans;
    }
};

//另一种写法，枚举方案数
class Solution {
public:
    vector<double> twoSum(int n) {
        /*
        dp[i][j] 表示扔i个骰子总和为j的情况下，所有的方案数
        i从0到n, j从n到6n
        dp[0][n] = 1;
        dp[i][j] += dp[i - 1][j - k], 1 <= k <= 6
        */

        double tot = (double)pow(6, n);
        int dp[n + 1][6 * n + 1];
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        for (int i = 1; i <= n; i ++ )
            for (int j = i; j <= 6 * i; j ++ )
                for (int k = 1; k <= 6; k ++ )
                {
                    if (j >= k) dp[i][j] += dp[i - 1][j - k];
                }

        vector<double> ans;
        for (int i = n; i <= 6 * n; i ++ )
        {
            double cur = dp[n][i] / tot;
            ans.push_back(cur);
        }

        return ans;
    }
};

LC.5467 找到最接近目标值的函数值（困难）

线段树 + 双指针，线段树用来快速查询区间与结果，双指针利用了区间内与的单调递减的性质，将区间的枚举变成了O(n)的操作。如果看到需要每次枚举区间，可以想一想前缀和、双指针 + 单调性、区间DP、线段树（主要是区间查找）。

const int N = 100010;

struct Node
{
    int l, r;
    int t;
}tr[N * 4];

class Solution {
public:
    void pushup(int u)
    {
        tr[u].t = tr[u << 1].t & tr[u << 1 | 1].t;
    }

    void build(int u, int l, int r, vector<int>& arr)
    {
        //模板这样写不容易错，不会在else里面少一部分lr的初始化
        tr[u] = {l, r};
        if (l == r) tr[u].t = arr[l - 1];
        else
        {
            int mid = l + r >> 1;
            build(u << 1, l, mid, arr), build(u << 1 | 1, mid + 1, r, arr);
            pushup(u);
        }
    }

    int query(int u, int l, int r)
    {
        if (tr[u].l >= l && tr[u].r <= r) return tr[u].t;

        int mid = tr[u].l + tr[u].r >> 1;
        //ret查找值一定要初始化，要一个不影响答案的值，否则下边的两个if有可能会使用随机值，尤其是第二个
        int ret = INT_MAX;
        //这里要明白lr是查询区间，如果l < mid表示在左子节点中也有需要查找的部分，要继续递归
        if (l <= mid) ret = query(u << 1, l, r);
        //如果r > mid表示右子节点有需要查找的部分，要继续递归
        if (r > mid) ret = ret & query(u << 1 | 1, l, r);
        return ret;
    }
    int closestToTarget(vector<int>& arr, int target) {
        build(1, 1, arr.size(), arr);
        int ans = 2e9;
        //双指针模板，要熟练使用
        for (int l = 1, r = 1; r <= arr.size(); r ++ )
        {
            //l = r时是单个数本身，如果不满足移动l指针，则会导致左右指针错过，之后的更新答案是无意义的
            while (l < r && query(1, l, r) < target) l ++ ;
            ans = min(ans, abs(target - query(1, l, r)));
        }

        return ans;
    }
};

LC.312 戳气球（困难）

区间DP的题，定义f[i][j]为i到j这个区间内，所有戳气球的方案组合下能达到的最大值。之后枚举当前区间内最后一个被戳的气球。这题可以从dfs入手，思考记忆化搜索和动态规划。

//记忆化搜索
class Solution {
public:
    vector<vector<int>> f;
    int dfs(vector<int>& nums, int l, int r)
    {
        if (l > r) return 0;
        if (f[l][r] != -1) return f[l][r];

        for (int i = l; i <= r; i ++ )
        {
            int left = dfs(nums, l, i - 1);
            int right = dfs(nums, i + 1, r);
            f[l][r] = max(f[l][r], left + right + nums[i] * nums[l - 1] * nums[r + 1]);
        }

        return f[l][r];
    }

    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        f = vector<vector<int>>(n + 2, vector<int>(n + 2, -1));
        vector<int> tmp(n + 2);
        tmp[0] = tmp[n + 1] = 1;
        for (int i = 0; i < nums.size(); i ++ ) tmp[i + 1] = nums[i];

        return dfs(tmp, 1, n);
    }
};

//动态规划解法
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> f(n + 2, vector<int>(n + 2, 0));
        vector<int> tmp(n + 2);
        tmp[0] = tmp[n + 1] = 1;

        for (int i = 1; i <= n; i ++ ) tmp[i] = nums[i - 1];
        //这里len可以从1开始，因为之前初始化所有f为0，因此当i > k - 1时答案是0
        for (int len = 1; len <= n; len ++ )
            for (int i = 1; i + len - 1 <= n; i ++ )
            {
                int j = i + len - 1;
                for (int k = i; k <= j; k ++ )
                    f[i][j] = max(f[i][j], f[i][k - 1] + f[k + 1][j] + tmp[k] * tmp[i - 1] * tmp[j + 1]);    
            }

        return f[1][n];
    }
};

LC.1507 转变日期格式（简单）

主要考察C和C++字符串处理API的使用，要注意观察格式，转换会更容易一些。

//C语言的sprintf 和sscanf版本
class Solution {
public:
    string reformatDate(string date) {
        int day, month = 0, year;
        char month_s[4];
        sscanf(date.c_str(), "%d%*s %s %d", &day, month_s, &year);
        string months[] = {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"};
        for (int i = 0; i < 12; i ++ )
            if (months[i] == month_s)
            {
                month = i + 1;
                break;
            }
        char res[20];
        sprintf(res, "%04d-%02d-%02d", year, month, day);
        return res;
    }
};
//C++的stringstream版本
class Solution {
public:
    string reformatDate(string date) {
        string months[] = {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"};
        stringstream ssin(date);
        string cur;
        string day, month, year;
        int cnt = 0;
        while (ssin >> cur)
        {
            cnt ++ ;
            if (cnt == 1){
                while (!isdigit(cur.back())) cur.pop_back();
                day = cur;
            }
            else if (cnt == 2)
            {
                for (int i = 0; i < 12; i ++ )
                    if (months[i] == cur)
                    {
                        month = to_string(i + 1);
                        break;
                    }
            }
            else year = cur;
        }

        string ans = year + "-";
        if (month.size() < 2) ans += "0";
        ans += month + "-";
        if (day.size() < 2) ans += "0";
        ans += day;

        return ans;
    }
};

LC.1508 子数组和排序后的区间和（中等）

这道题的正解可以做到O(nlogM)，M是所有元素区间和的和。方法是使用前缀和 + 双指针 + 二分查找。

首先可以看到这题数组中的所有数都是正整数，这意味着区间和是单调递增的。当区间和是单调递增的时候，我们可以用双指针算法来计算当前区间和的和，通过公式可以转换为区间和的前缀和，同时可以统计所有区间和小于某个x的和的个数，可以通过个数来找到第k个区间和。

计算区间和的区间和可以通过如下公式推导：

$(s[i] - s[j]) + (s[i] - s[j + 1]) + ... + (s[i] - s[i - 1])\\ = s[i] * (i - j) - (s[j] + s[j + 1] + ... + s[i - 1])\\ = s[i] * (i - j) - (ss[i - 1] - s[j - 1]), j >= 1$

typedef long long LL;
typedef pair<int, LL> PIL;
class Solution {
public:
    int n;
    vector<int> s, ss;

    int mod = 1e9 + 7;
    PIL get(LL mid)
    {
        int cnt = 0;
        LL sum = 0;
        for (int i = 1, j = 0; i <= n; i ++ )
        {
            while (j < i && s[i] - s[j] > mid) j ++ ;
            cnt += i - j;
            sum += s[i] * (i - j) - ss[i - 1];
            if (j) sum += ss[j - 1];
        }
        return {cnt, sum};
    }

    LL f(int x)
    {
        LL l = 0, r = ss.back();
        while (l < r)
        {
            LL mid = l + r >> 1;
            //t.first表示查找到的个数，也就是新数列中该数的位置。
            auto t = get(mid);
            if (t.first >= x) r = mid;
            else l = mid + 1;
        }
        auto t = get(l);
        //t.second通过双指针计算出来的是所有 <=mid 的区间和之和，如果有相同值，都会被计算进去
        //由于t.first可能不是连续的，比如第k - 1的位置计算出的t.first < x，而k位置计算出来的t.first > x，最终二分是有结果，但是t.first并不是正好要查找的x位置，所以要减去所有重复元素的重复计算，要找最小的满足值
        LL v = t.second;
        v = v - (t.first - x) * l;

        return v;
    }

    int rangeSum(vector<int>& nums, int _n, int left, int right) {
        n = _n;
        s.resize(n + 1), ss.resize(n + 1);
        //计算区间的前缀和，以及前缀和的前缀和
        for (int i = 1; i <= n; i ++ )
        {
            s[i] = s[i - 1] + nums[i - 1];
            ss[i] = ss[i - 1] + s[i];
        }
        //通过前缀和思想，可以将答案等同于新数列中1~right的和减去1~left - 1的和
        //这样不用写两次二分，代码重用，问题归一化
        LL ans = f(right) - f(left - 1);
        int ret = ans % mod;
        return ret;
    }
};

LC.95 不同的二叉搜索树（中等）

递归的建树，判断空子树的情况，每次新建root节点。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if (n == 0) return vector<TreeNode*>{};
        return build(1, n);
    }

    vector<TreeNode*> build(int l, int r)
    {
        vector<TreeNode*> ans;
        //放一个空指针，省掉了下方的一些讨论
        if (l > r) 
        {
            ans.push_back(nullptr);
            return ans;
        }
        else
        {
            for (int i = l; i <= r; i ++ )
            {
                auto left = build(l, i - 1);
                auto right = build(i + 1, r);
                for (int j = 0; j < left.size(); j ++ )
                    for (int k = 0; k < right.size(); k ++ )
                    {
                        TreeNode* root = new TreeNode(i);
                        root ->left = left[j], root -> right = right[k];
                        ans.push_back(root);
                    }
            }
            return ans;
        }
    }
};

LC.剑指offer11.旋转数组的最小值（简单）

这个题二分的时候数组mid的值有可能和左右两边的边界相等，导致无法判断是收缩左边界还是右边界。这里可以在无法判断的时候有边界-1，这样就可以缓慢缩小范围。

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int n = numbers.size();
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (numbers[mid] < numbers[r]) r = mid;
            else if (numbers[mid] > numbers[r]) l = mid + 1;
            else r = r - 1;
        }

        return numbers[r];
    }
};

LC.410 分割数组的最大值（困难）

有两种方法，动态规划和二分。

动态规划中f[i][j]定义为前i个数字分为j组时最大和的最小值。假设原来是min(max(a1,b1), max(a2, b2), max(a3, b3))，现在要求的是min(max(a1, b1, c), max(a2, b2, c), max(a3, b3, c))，这时如果c < min(max(a1,b1), max(a2, b2), max(a3, b3))，那么现在的和不变，还是之前的和，如果c >= min(max(a1,b1), max(a2, b2), max(a3, b3))，那么最小的那个max肯定被更新了，并且所有小于c的max项都变成了c，这样最小值就是c了。因此在求min的时候，新的min(max(a1, b1, c), max(a2, b2, c), max(a3, b3, c)) = min(min(max(a1,b1), max(a2, b2), max(a3, b3)),c)。

求极小化极大的问题，可以使用二分。通过贪心直接可以统计是不是分成m份可以使得有一种方法，所有的和都小于某一个值x。如果能够验证可以找到这种方法，那么比x大的值都可以找到分割方法，因此右边界收缩，否则左边界收缩。

题解

//动态规划
typedef long long LL;
class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int n = nums.size();
        vector<LL> sum(n + 1, 0);
        for (int i = 1; i <= n; i ++ ) sum[i] = sum[i - 1] + nums[i - 1];

        vector<vector<LL>> f(n + 1, vector<LL>(m + 1, LONG_MAX));

        f[0][0] = 0;

        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
            {
                if (j > i) continue;
                for (int k = 1; i - k >= j - 1; k ++ )
                {
                    f[i][j] = min(f[i][j],max(f[i - k][j - 1], sum[i] - sum[i - k]));
                }
            }

        return f[n][m];
    }
};

//二分查找
typedef long long LL;
class Solution {
public:
    bool check(vector<int>& nums, LL x, int m)
    {
        LL sum = 0;
        int cnt = 1;
        for (int i = 0; i < nums.size(); i ++ )
        {
            if (sum + nums[i] > x)
            {
                cnt ++ ;
                sum = nums[i];
            }
            else sum += nums[i];
        }

        return cnt <= m;
    }
    int splitArray(vector<int>& nums, int m) {
        LL sum = 0;
        LL l = 0, r;
        for (auto i : nums) sum += i;
        //这里l一定要取数组中最大值，否则当mid小于maxv时，统计个数会错误
        for (LL i : nums) l = max(l, i);
        r = sum;
        while (l < r)
        {
            LL mid = l + r >> 1;
            if (check(nums, mid, m)) r = mid;
            else l = mid + 1;
        }

        return l;
    }
};

LC.LCP13 寻宝（困难）

非常难的一道题，综合了BFS、状压DP求哈密尔顿路径，需要设计好实现方式，包括如何查找下标和序号。但是写出来非常有成就感。

const int INF = 0x3f3f3f3f / 2;
class Solution {
public:
    int cnt = 0;
    int id_cnt = 0;
    unordered_map<int, int> id;
    int n, m;

    //bfs过程，求解某一个M到其他所有位置的最短距离
    void bfs(vector<string>& maze, vector<vector<int>>& dist, int x, int y)
    {
        //需要存储一个当前点位置，和到当前点为止的最短距离
        queue<pair<int, pair<int, int>>> q;
        dist[x][y] = 0;
        q.push({0, {x, y}});

        while (q.size())
        {
            int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
            auto t = q.front();
            q.pop();

            int len = t.first;
            int xx = t.second.first, yy = t.second.second;
            //遍历上下左右四个方向
            for (int i = 0; i < 4; i ++ )
            {
                int a = xx + dx[i], b = yy + dy[i];
                if (a < 0 || a >= n || b < 0 || b >= m) continue;
                if (maze[a][b] == '#') continue;
                //如果遍历过了就直接下一个位置，不重复遍历
                if (dist[a][b] != INF) continue;
                //最短距离 + 1
                dist[a][b] = len + 1;
                q.push({len + 1, {a, b}});
            }
        }
    }

    int minimalSteps(vector<string>& maze) {
        n = maze.size(), m = maze[0].size();
        //这里要记录一下T的位置，因为最终答案要从最后一个M走到T，不需要再去O了
        //因此应该是所有的遍历完全的情况，加上到T的距离之和的最短是答案
        int fi = 0, fj = 0;
        //因为后边要用状压DP求哈密尔顿路径，所以要记录S点在{S, M}矩阵中的编号
        int id_s = 0;
        //为了方便起见，将所有方格内的点编上编号，其中编号从0开始
        //这样可以将二维坐标变成1维，并且可以还原回去
        vector<vector<int>> g(n, vector<int>(m));
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
            {
                //编上编号
                g[i][j] = cnt;
                //如果是S或者M，那么要加到哈密尔顿路径中需要遍历的点的集合中
                if (maze[i][j] == 'S' || maze[i][j] == 'M')
                {
                    if (maze[i][j] == 'S') id_s = id_cnt;
                    //用哈希表进行一个映射，从而可以用邻接矩阵中的id_cnt查找g中的编号
                    id[id_cnt ++ ] = cnt;
                }
                else if (maze[i][j] == 'T')
                    fi = i, fj = j;
                cnt ++ ;
            }

        //这里是邻接矩阵，将所有{S,M}依次编号，之后方便进行状压DP求解
        vector<vector<int>> d(id_cnt, vector<int>(id_cnt, INF));

        //自己到自己的距离为0
        for (int i = 0; i < id_cnt; i ++ )
            d[i][i] = 0;

        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                //如果是O，则需要求O到所有{S, M}集合的距离，M -> O -> M的距离对需要枚举
                if (maze[i][j] == 'O')
                {
                    vector<vector<int>> dist(n, vector<int>(m, INF));
                    bfs(maze, dist, i, j);

                    //枚举所有M -> O -> M的距离，其中每对的最小值作为哈密尔顿路径权重值
                    for (int u = 0; u < id_cnt; u ++ )
                        for (int v = u + 1; v < id_cnt; v ++ )
                        {
                            int p1 = id[u], p2 = id[v];
                            //将g中的坐标还原回去，这样才能得到对应距离下标x, y
                            int x1 = p1 / m, y1 = p1 % m;
                            int x2 = p2 / m, y2 = p2 % m;

                            d[v][u] = d[u][v] = min(d[u][v], dist[x1][y1] + dist[x2][y2]);
                        }
                }

        //计算所有点到终点T的距离，这里T是需要特殊区别于S和M的，因为T不需要去搬石头
        vector<vector<int>> dist_T(n, vector<int>(m, INF));
        bfs(maze, dist_T, fi, fj);
        int ans = INF;

        //状压DP求解哈密尔顿路径
        vector<vector<int>> f(1 << id_cnt, vector<int>(id_cnt, INF));

        //id_s是编号，f[i][j]表示状态为i的情况下，处于j时，所走过的最短路径
        f[1 << id_s][id_s] = 0;

        //枚举所有状态
        for (int i = 0; i < 1 << id_cnt; i ++ )
            //枚举所有停靠点
            for (int j = 0; j < id_cnt; j ++ )
                //如果当前点是被走到的
                if (i >> j & 1)
                    //枚举停靠点
                    for (int k = 0; k < id_cnt; k ++ )
                        //停靠点不能被走到
                        if (!(i >> k & 1))
                            //那么当前点可以走到停靠点，状态为f[i | (1 << k)][k]
                            f[i | (1 << k)][k] = min(f[i | (1 << k)][k], f[i][j] + d[j][k]);

        //枚举所有可以停靠的点，且状态为全部为1，即都走过一遍
        for (int j = 0; j < id_cnt; j ++ )
        {
            int p = id[j];
            int x = p / m, y = p % m; 
            //从某个停靠点走到T终点的最小值就是答案
            ans = min(ans, f[(1 << id_cnt) - 1][j] + dist_T[x][y]);
        }
        //如果答案太大，说明是不可达
        //这里INF设置为 0x3f3f3f3f / 2防止溢出
        if (ans >= INF) return -1;
        else return ans;
    }   
};

LC.1477 找两个和为目标值且不重叠的子数组

这题因为数据范围中确定了所有的值都是正整数，因此和只能越来越大，有单调性，因此可以使用双指针算法进行求解。但是对于一个比较普通的情况，如果值是可正可负的，那么需要更加通解的方法，下一题就使用了这种方法。

LC.546 移除盒子

比较有特点的DP定义，三维dp。最开始的思路认为和戳气球一样，是一个区间dp，但是仔细思考之后，发现区间dp要求区间是闭合的，这样每次子问题的递归可以考虑成连续的，但是这题中每次考虑区间和子问题时，会导致中间有一部分无法使用，从而子问题无法简单递归。这里dp数组的定义为从l到r区间中，并且在r位置之后还有k个和a[r]元素相同的元素。这样每次状态转移就可以变成连续的，即：

$f[l][r][k] = max(f[l][r - 1][0] + (k + 1)^2 * (k + 1)^2, max(f[l][i][k + 1] + f[i + 1][r - 1][0]),if(a[i] == a[r])), i ∈[l, r - 1];$

这里有两项，第一项是将r元素和后边的k个元素一起计算然后再计算之前的元素部分；第二项就是枚举分割点位置，从l到r - 1枚举，并且只有当中间的元素和a[r]相同时才可以继承当前的k个元素的子问题，并且加上当前不继承部分的单独计算问题，即f[i + 1][r - 1][0]。

这题的dp设计思路告诉我们，当某些区间dp无法很好表示子问题的时候，可以考虑将区间中某些性质表示为第三维度，从而更好的去确定一个状态，从而递归子状态。

class Solution {
public:
    int dp[110][110][110];

    int removeBoxes(vector<int>& boxes) {
        memset(dp, 0, sizeof dp);
        int n = boxes.size();
        return dfs(boxes, 0, n - 1, 0);    
    }

    int dfs(vector<int>& boxes, int l, int r, int k)
    {
        if (l > r) return 0;
        if (dp[l][r][k]) return dp[l][r][k];

        //加速用的，注销也可以AC
        //当右边有连续和相同元素时，可以将问题递归为更简单的子问题
        while (r > l && boxes[r] == boxes[r - 1])
        {
            r -- , k ++ ;
        }
        //先计算状态转移方程第一项
        dp[l][r][k] = dfs(boxes, l, r - 1, 0) + (k + 1) * (k + 1);
        for (int i = l; i < r; i ++ )
        {
            //当前位置和r位置下元素相同的时候才计算
            if (boxes[i] == boxes[r])
            {
                //取max
                dp[l][r][k] = max(dp[l][r][k], dfs(boxes, l, i, k + 1) + dfs(boxes, i + 1, r - 1, 0));
            }
        }

        return dp[l][r][k];
    }
};

题库题解

题库

题库+题解

双指针

C++ STL使用技巧

天の痕