leetcode解题思路分析（一百六十六）1438 - 1444 题
- 绝对差不超过限制的最长连续子数组
给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。如果不存在满足条件的子数组，则返回 0 。
存储当前有序子数组的集合，采用滑动指针移动求出解
class Solution {
public:int longestSubarray(vector<int>& nums, int limit) {multiset<int> s;int n = nums.size();int left = 0, right = 0;int ret = 0;while (right < n) {s.insert(nums[right]);while (*s.rbegin() - *s.begin() > limit) {s.erase(s.find(nums[left++]));}ret = max(ret, right - left + 1);right++;}return ret;}
};- 有序矩阵中的第 k 个最小数组和
给你一个 m * n 的矩阵 mat，以及一个整数 k ，矩阵中的每一行都以非递减的顺序排列。你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。
可以用小根堆或者二分查找来做
class Solution {
public:int kthSmallest(vector<vector<int>>& mat, int k) {int m = mat.size();vector<int> prev = mat[0];for (int i = 1; i < m; ++i) {prev = move(merge(prev, mat[i], k));}return prev[k - 1];}vector<int> merge(const vector<int>& f, const vector<int>& g, int k) {if (g.size() > f.size()) {return merge(g, f, k);}priority_queue<Entry> q;for (int i = 0; i < g.size(); ++i) {q.emplace(0, i, f[0] + g[i]);}vector<int> ans;while (k && !q.empty()) {Entry entry = q.top();q.pop();ans.push_back(entry.sum);if (entry.i + 1 < f.size()) {q.emplace(entry.i + 1, entry.j, f[entry.i + 1] + g[entry.j]);}--k;}return ans;}private:struct Entry {int i, j, sum;Entry(int _i, int _j, int _sum): i(_i), j(_j), sum(_sum) {}bool operator< (const Entry& that) const {return sum > that.sum;}};
};- 用栈操作构建数组
给你一个数组 target 和一个整数 n。
给你一个空栈和两种操作：
“Push”：将一个整数加到栈顶。
“Pop”：从栈顶删除一个整数。
同时给定一个范围 [1, n] 中的整数流。
使用两个栈操作使栈中的数字（从底部到顶部）等于 target。
每次操作一个数字时，如果它在 target 中，则只需要将它 Push 入栈即可。如果不在 target 中，可以先将其 Push 入栈，紧接着 Pop 出栈。
class Solution {
public:vector<string> buildArray(vector<int>& target, int n) {vector<string> res;int prev = 0;for (int number : target) {for (int i = 0; i < number - prev - 1; i++) {res.emplace_back("Push");res.emplace_back("Pop");}res.emplace_back("Push");prev = number;}return res;}
};- 形成两个异或相等数组的三元组数目
给你一个整数数组 arr 。
现需要从数组中取三个下标 i、j 和 k ，其中 (0 <= i < j <= k < arr.length) 。
a 和 b 定义如下：
a = arr[i] ^ arr[i + 1] ^ … ^ arr[j - 1]
b = arr[j] ^ arr[j + 1] ^ … ^ arr[k]
注意：^ 表示 按位异或 操作。
请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。
本题是前缀和的进阶版用法，异或前缀和。
class Solution {
public:int countTriplets(vector<int> &arr) {int n = arr.size();unordered_map<int, int> cnt, total;int ans = 0, s = 0;for (int k = 0; k < n; ++k) {int val = arr[k];if (cnt.count(s ^ val)) {ans += cnt[s ^ val] * k - total[s ^ val];}++cnt[s];total[s] += k;s ^= val;}return ans;}
};- 收集树上所有苹果的最少时间
给你一棵有 n 个节点的无向树，节点编号为 0 到 n-1 ，它们中有一些节点有苹果。通过树上的一条边，需要花费 1 秒钟。你从 节点 0 出发，请你返回最少需要多少秒，可以收集到所有苹果，并回到节点 0 。无向树的边由 edges 给出，其中 edges[i] = [fromi, toi] ，表示有一条边连接 from 和 toi 。除此以外，还有一个布尔数组 hasApple ，其中 hasApple[i] = true 代表节点 i 有一个苹果，否则，节点 i 没有苹果。
需要先做一次 DFS 求出每个点对应的子树上的苹果的数量，存入一个数组中，方便下面做 O(1) 的查询.在做好这些准备工作之后，我们再做一次 DFS 求解需要花费的最小时间
class Solution {
public:static constexpr int MAX_N = int(1E5) + 5;vector <int> g[MAX_N];int apple[MAX_N], ans;int getAppleNumber(int o, int from, vector<bool>& hasApple) {apple[o] = hasApple[o];for (const auto &son: g[o]) {if (son == from) {continue;}apple[o] += getAppleNumber(son, o, hasApple);} return apple[o];}void dfs(int o, int from) {for (const auto &son: g[o]) {if (son == from) {continue;}if (apple[son]) {ans += 2;dfs(son, o);}}}int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {memset(apple, 0, sizeof apple);for (const auto &e: edges) {int u = e[0], v = e[1];g[u].push_back(v);g[v].push_back(u);}getAppleNumber(0, -1, hasApple);ans = 0;dfs(0, -1);return ans;}
};- 切披萨的方案数
给你一个 rows x cols 大小的矩形披萨和一个整数 k ，矩形包含两种字符： ‘A’ （表示苹果）和 ‘.’ （表示空白格子）。你需要切披萨 k-1 次，得到 k 块披萨并送给别人。切披萨的每一刀，先要选择是向垂直还是水平方向切，再在矩形的边界上选一个切的位置，将披萨一分为二。如果垂直地切披萨，那么需要把左边的部分送给一个人，如果水平地切，那么需要把上面的部分送给一个人。在切完最后一刀后，需要把剩下来的一块送给最后一个人。请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。由于答案可能是个很大的数字，请你返回它对 10^9 + 7 取余的结果。
*动态规划解题
class Solution {
public:int ways(vector<string>& pizza, int k) {int m = pizza.size(), n = pizza[0].size(), mod = 1e9 + 7;vector<vector<int>> apples(m + 1, vector<int>(n + 1));vector<vector<vector<int>>> dp(k + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));// 预处理for (int i = m - 1; i >= 0; i--) {for (int j = n - 1; j >= 0; j--) {apples[i][j] = apples[i][j + 1] + apples[i + 1][j] - apples[i + 1][j + 1] + (pizza[i][j] == 'A');dp[1][i][j] = apples[i][j] > 0;}}for (int ki = 2; ki <= k; ki++) {for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {// 水平方向切for (int i2 = i + 1; i2 < m; i2++) {if (apples[i][j] > apples[i2][j]) {dp[ki][i][j] = (dp[ki][i][j] + dp[ki - 1][i2][j]) % mod;}}// 垂直方向切for (int j2 = j + 1; j2 < n; j2++) {if (apples[i][j] > apples[i][j2]) {dp[ki][i][j] = (dp[ki][i][j] + dp[ki - 1][i][j2]) % mod;}}}}}return dp[k][0][0];}
};