leetcode解题思路分析（一百五十三）1334

本文主要是介绍leetcode解题思路分析（一百五十三）1334 - 1341 题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

阈值距离内邻居最少的城市
有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。返回能通过某些路径到达其他城市数目最少、且路径距离最大为 distanceThreshold 的城市。如果有多个这样的城市，则返回编号最大的城市。注意，连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。

求出每个点到别的点的最短距离，然后在给定范围内遍历。

class Solution {
public:int findTheCity(int n, vector<vector<int>> &edges, int distanceThreshold) {pair<int, int> ans(INT_MAX / 2, -1);vector<vector<int>> dis(n, vector<int>(n, INT_MAX / 2));vector<vector<int>> vis(n, vector<int>(n, false));vector<vector<int>> mp(n, vector<int>(n, INT_MAX / 2));for (auto &eg: edges) {int from = eg[0], to = eg[1], weight = eg[2];mp[from][to] = mp[to][from] = weight;}for (int i = 0; i < n; ++i) {dis[i][i] = 0;for (int j = 0; j < n; ++j) {int t = -1;for (int k = 0; k < n; ++k) {if (!vis[i][k] && (t == -1 || dis[i][k] < dis[i][t])) {t = k;}}for (int k = 0; k < n; ++k) {dis[i][k] = min(dis[i][k], dis[i][t] + mp[t][k]);}vis[i][t] = true;}}for (int i = 0; i < n; ++i) {int cnt = 0;for (int j = 0; j < n; ++j) {if (dis[i][j] <= distanceThreshold) {cnt++;}}if (cnt <= ans.first) {ans = {cnt, i};}}return ans.second;}
};

工作计划的最低难度
你需要制定一份 d 天的工作计划表。工作之间存在依赖，要想执行第 i 项工作，你必须完成全部 j 项工作（ 0 <= j < i）。你每天至少需要完成一项任务。工作计划的总难度是这 d 天每一天的难度之和，而一天的工作难度是当天应该完成工作的最大难度。给你一个整数数组 jobDifficulty 和一个整数 d，分别代表工作难度和需要计划的天数。第 i 项工作的难度是 jobDifficulty[i]。返回整个工作计划的最小难度。如果无法制定工作计划，则返回 -1 。

因为一天的难度指的是当天最大值，所以要考虑的是某一段内的最大值，由此可以想到单调栈解题。套用模板即可。

class Solution {
public:int minDifficulty(vector<int>& jobDifficulty, int d) {int n = jobDifficulty.size();if (n < d) {return -1;}vector<int> dp(n);for (int j = 0, ma = 0; j < n; ++j) {ma = max(ma, jobDifficulty[j]);dp[j] = ma;}for (int i = 1; i < d; ++i) {stack<pair<int, int>> st;vector<int> ndp(n);for (int j = i; j < n; ++j) {int mi = dp[j - 1];while (!st.empty() && jobDifficulty[st.top().first] < jobDifficulty[j]) {mi = min(mi, st.top().second);st.pop();}if (st.empty()) {ndp[j] = mi + jobDifficulty[j];} else {ndp[j] = min(ndp[st.top().first], mi + jobDifficulty[j]);}st.emplace(j, mi);}swap(dp, ndp);}return dp[n - 1];}
};

矩阵中战斗力最弱的 K 行
给你一个大小为 m * n 的矩阵 mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。请你返回矩阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。军人总是排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。

class Solution {
public:vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {int cnt = 0;vector<int> ret;vector<pair<int, int>> cntPair;for (int i = 0; i < mat.size(); ++i){cnt = 0;for (auto n : mat[i]){if (n) cnt++;elsebreak;}cntPair.push_back(make_pair(i, cnt));}sort(cntPair.begin(), cntPair.end(), [=](pair<int, int>& a, pair<int, int>& b){return a.second < b.second || (a.second == b.second && a.first < b.first);});cnt = 0;for (auto p : cntPair){ret.push_back(p.first);cnt++;if (cnt >= k)break;}return ret;}
};

数组大小减半
给你一个整数数组 arr。你可以从中选出一个整数集合，并删除这些整数在数组中的每次出现。

返回至少能删除数组中的一半整数的整数集合的最小大小。

贪心算法：按出现次数排序，从大到小开始加，加到超过一半一定是最少的

class Solution {
public:int minSetSize(vector<int>& arr) {unordered_map<int, int> freq;for (int num: arr) {++freq[num];}vector<int> occ;for (auto& [k, v]: freq) {occ.push_back(v);}sort(occ.begin(), occ.end(), greater<int>());int cnt = 0, ans = 0;for (int c: occ) {cnt += c;ans += 1;if (cnt * 2 >= arr.size()) {break;}}return ans;}
};

分裂二叉树的最大乘积
给你一棵二叉树，它的根为 root 。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。由于答案可能会很大，请你将结果对 10^9 + 7 取模后再返回

递归查找一个最接近总和一半的数。

/*** 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 {
private:int sum = 0;int best = 0;public:void dfs(TreeNode* node) {if (!node) {return;}sum += node->val;dfs(node->left);dfs(node->right);}int dfs2(TreeNode* node) {if (!node) {return 0;}int cur = dfs2(node->left) + dfs2(node->right) + node->val;if (abs(cur*2 - sum) < abs(best*2 - sum)) {best = cur;}return cur;}int maxProduct(TreeNode* root) {dfs(root);dfs2(root);return (long long)best * (sum - best) % 1000000007;}
};

跳跃游戏 V
给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到：
i + x ，其中 i + x < arr.length 且 0 < x <= d 。
i - x ，其中 i - x >= 0 且 0 < x <= d 。
除此以外，你从下标 i 跳到下标 j 需要满足：arr[i] > arr[j] 且 arr[i] > arr[k] ，其中下标 k 是所有 i 到 j 之间的数字（更正式的，min(i, j) < k < max(i, j)）。
你可以选择数组的任意下标开始跳跃。请你返回你最多可以访问多少个下标。
请注意，任何时刻你都不能跳到数组的外面。

先按照高度和索引记一个数组，然后dp从低点开始遍历一遍即可完成。


class Solution {
public:int maxJumps(vector<int>& arr, int d) {int n = arr.size();vector<int> dp(n, 1);vector<pair<int, int>> arr2;for (int i = 0; i < n; ++i) {arr2.push_back({arr[i], i});}sort(arr2.begin(), arr2.end());for (int i = 0; i < n; ++i) {int j = arr2[i].second;for (int k = j - 1; k >= max(0, j - d) && arr[k] < arr[j]; --k) {dp[j] = max(dp[j], dp[k] + 1);}for (int k = j + 1; k <= min(n - 1, j + d) && arr[k] < arr[j]; ++k) {dp[j] = max(dp[j], dp[k] + 1);}}return *max_element(dp.begin(), dp.end());}
};

电影评分
请你编写一个解决方案：
查找评论电影数量最多的用户名。如果出现平局，返回字典序较小的用户名。
查找在 February 2020 平均评分最高的电影名称。如果出现平局，返回字典序较小的电影名称。
字典序，即按字母在字典中出现顺序对字符串排序，字典序较小则意味着排序靠前。

# Write your MySQL query statement below
(select u.name results
from MovieRating mr 
left join Users u using(user_id) 
group by u.user_id
order by count(movie_id) desc, u.name asc
limit 1)union all(select m.title results
from MovieRating mr 
left join Movies m using(movie_id)
where date_format(mr.created_at,'%Y-%m') = '2020-02'
group by m.movie_id
order by avg(rating) desc, m.title asc
limit 1)