Leetcode 801-900

862. Shortest Subarray with Sum at Least K (hard)

一个数组A，求和大于等于K的最短子数组长度

• $1 \le A.length \le 50000$
• $-10^5 \le A[i] \le 10^5$
• $1 \le K \le 10^9$

Input: A = [1], K = 1
Output: 1
Input: A = [1,2], K = 4
Output: -1
Input: A = [2,-1,2], K = 3
Output: 3

思路

首先应该想到和前缀和有关，然后从前缀和出发进行形式化推导

对y来说，即求满足P[y] - p[x] >= K的最大x

从这里出发，可以发现如果x1 < x2 && P[x1] >= P[x2]，那么x2一定优于x1，因此只需要考虑x2即可

所以可以维护一个单调递增的队列，存放前缀和数组的秩

对y而言，将队列前方满足P[y] - P[x] >= K的元素都出队，每次出队时更新最小距离即可

这里直接出队，是因为一个x被y用过后，之后的元素不会再用它来更新最小距离，因此可以直接出队列

复杂度是$O(N)$

int shortestSubarray(vector<int>& A, int K) {
    vector<long long> prefix = { 0 };
    for (int n : A) prefix.push_back(prefix.back() + n);
    deque<int> q;
    int dis = A.size() + 1;
    for (int i = 0; i < prefix.size(); i++) {
        while (!q.empty() && prefix[q.back()] >= prefix[i]) q.pop_back();
        while (!q.empty() && prefix[q.front()] <= prefix[i] - K) {
            dis = min(dis, i - q.front());
            q.pop_front();
        }
        q.push_back(i);
    }
    return dis > A.size() ? -1 : dis;
}

---

887. Super Egg Drop (Hard)

有K个鸡蛋，N层楼，求摔碎鸡蛋的最低楼层

思路一

而要问M层楼，N个鸡蛋扔法，则要用动态规划，$dp[i][j]$表示i层楼用j个鸡蛋测，最少需要次数

dp[i][1]=i

dp[0][j]=0

而到dp[i][j]转移方程，则想第一次在哪个楼层扔鸡蛋，设在k层，那么

• 鸡蛋碎了，变成k-1层扔j-1个蛋的最少次数+1
• 鸡蛋没碎，变成i-k层扔j个蛋的最少次数+1

因此dp[i][j]=min(max(dp[i-k][j], dp[k-1][j-1])+1 for k in [1,i-1])

代码如下，注意mn不能大于i

不过下面会超时，因为复杂度过高

int superEggDrop(int K, int N) {
    int dp[N+1][K+1];
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= N; i ++) {
        dp[i][1] = i;
        for (int j = 2; j <= K; j ++) {
            int mn = N;
            for (int k = 1; k < i; k ++)
                mn = min(mn, max(dp[k-1][j-1], dp[i-k][j])+1);
            dp[i][j] = min(mn, i);
        }
    }
    return dp[N][K];
}

思路二

改为$dp[i][j]$表示i次机会内j个鸡蛋能覆盖的最大楼层数

dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + 1

i从1开始增加，dp[i][j]大于等于N时即为最少次数

相比上面解法，这样不用对每一个楼层都计算对应次数，只用O(N*K)复杂度

int superEggDrop(int K, int N) {
    int dp[N + 1][K + 1];
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= K; j ++) {
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + 1;
            if (dp[i][j] >= N) return i;
        }
    }
    return N;
}

---

889. Construct Binary Tree from Preorder and Postorder Traversal (Medium)

给出一棵树的中序和后序遍历，恢复这棵树

值得注意的是，中序和后序并不足以恢复整棵树，因为不知道一个节点是左孩子还是右孩子，例如下图两棵树，前序遍历都是1234，后序都是2431，并不知道4是3的左孩子还是右孩子

只有对完整二叉树来说，才可以得到唯一解，不过这道题给出一个解即可

    1       1
   / \     / \
  2  3    2   3
    /          \
   4            4

思路

代码如下，并不复杂，同样查找点，然后恢复树即可

TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
    return helper(pre, 0, post, 0, pre.size());
}
TreeNode* helper(const vector<int>& pre, int p, const vector<int>& post, int q, int len) {
    if (len == 0) return nullptr;
    TreeNode* root = new TreeNode(pre[p]);
    if (len == 1) return root;
    int leftHead = pre[p + 1], rank = q;
    while (post[rank] != leftHead) rank ++;
    root->left = helper(pre, p + 1, post, q, rank - q + 1);
    root->right = helper(pre, p + rank - q + 2, post, rank + 1, len + q - rank - 2);
    return root;
}