leetcode解题思路分析（一百零三）881

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

救生艇
第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。返回载到每一个人所需的最小船数。(保证每个人都能被船载)。

贪心算法：双指针滑动，如果最轻+最重可以坐得下，则一起走，否则把最重的人先驮走

class Solution {
public:int numRescueBoats(vector<int> &people, int limit) {int ans = 0;sort(people.begin(), people.end());int light = 0, heavy = people.size() - 1;while (light <= heavy) {if (people[light] + people[heavy] > limit) {--heavy;} else {++light;--heavy;}++ans;}return ans;}
};

细分图中的可到达结点
给你一个无向图（原始图），图中有 n 个节点，编号从 0 到 n - 1 。你决定将图中的每条边细分为一条节点链，每条边之间的新节点数各不相同。现在得到一个新的细分图，请你计算从节点 0 出发，可以到达多少个节点？节点是否可以到达的判断条件为：如果节点间距离是 maxMoves 或更少，则视为可以到达；否则，不可到达。给你原始图和 maxMoves ，返回新的细分图中从节点 0 出发可到达的节点数。

dijkstra算法

#define pii pair<int, int>class Solution {
public:int reachableNodes(vector<vector<int>>& edges, int M, int N) {vector<vector<pii>> graph(N);for (vector<int> edge: edges) {int u = edge[0], v = edge[1], w = edge[2];graph[u].push_back({v, w});graph[v].push_back({u, w});}map<int, int> dist;dist[0] = 0;for (int i = 1; i < N; ++i)dist[i] = M+1;map<pii, int> used;int ans = 0;priority_queue<pii, vector<pii>, greater<pii>> pq;pq.push({0, 0});while (!pq.empty()) {pii top = pq.top();pq.pop();int d = top.first, node = top.second;if (d > dist[node]) continue;dist[node] = d;// Each node is only visited once.  We've reached// a node in our original graph.ans++;for (auto pair: graph[node]) {// M - d is how much further we can walk from this node;// weight is how many new nodes there are on this edge.// v is the maximum utilization of this edge.int nei = pair.first;int weight = pair.second;used[{node, nei}] = min(weight, M - d);// d2 is the total distance to reach 'nei' (nei***or) node// in the original graph.int d2 = d + weight + 1;if (d2 < min(dist[nei], M+1)) {pq.push({d2, nei});dist[nei] = d2;}}}// At the end, each edge (u, v, w) can be used with a maximum// of w new nodes: a max of used[u, v] nodes from one side,// and used[v, u] nodes from the other.for (vector<int> edge: edges) {int u = edge[0], v = edge[1], w = edge[2];ans += min(w, used[{u, v}] + used[{v, u}]);}return ans;}
};

三维形体投影面积
在 N * N 的网格中，我们放置了一些与 x，y，z 三轴对齐的 1 * 1 * 1 立方体。每个值 v = grid[i][j] 表示 v 个正方体叠放在单元格 (i, j) 上。现在，我们查看这些立方体在 xy、yz 和 zx 平面上的投影。投影就像影子，将三维形体映射到一个二维平面上。在这里，从顶部、前面和侧面看立方体时，我们会看到“影子”。返回所有三个投影的总面积。

从顶部看，由该形状生成的阴影将是网格中非零值的数目。从侧面看，由该形状生成的阴影将是网格中每一行的最大值。从前面看，由该形状生成的阴影将是网格中每一列的最大值。

class Solution {
public:int projectionArea(vector<vector<int>>& grid) {int N = grid.size();int ans = 0;for (int i = 0; i < N;  ++i) {int bestRow = 0;  // largest of grid[i][j]int bestCol = 0;  // largest of grid[j][i]for (int j = 0; j < N; ++j) {if (grid[i][j] > 0) ans++;  // top shadowbestRow = max(bestRow, grid[i][j]);bestCol = max(bestCol, grid[j][i]);}ans += bestRow + bestCol;}return ans;}
};

两句话中的不常见单词
句子是一串由空格分隔的单词。每个单词仅由小写字母组成。如果某个单词在其中一个句子中恰好出现一次，在另一个句子中却没有出现，那么这个单词就是不常见的。给你两个句子 s1 和 s2 ，返回所有不常用单词的列表。返回列表中单词可以按任意顺序组织。

字符串拼接

class Solution {
public:vector<string> uncommonFromSentences(string s1, string s2) {std::vector<string> ret;std::map<string, int>::iterator iter;WordsCount(s1);WordsCount(s2);for (iter = m_map.begin(); iter != m_map.end(); ++iter){if (iter->second == 1){ret.push_back(iter->first);}}return ret;}void WordsCount(string s){int pos = 0, cnt = 0;for (int i = 0; i < s.size(); ++i){if (s[i] == ' '){string sub = s.substr(pos, cnt);pos = i + 1;cnt = 0;m_map[sub]++;}else{cnt++;}}string sub = s.substr(pos, cnt);m_map[sub]++;}private:std::map<string, int> m_map;
};

螺旋矩阵 III
在 R 行 C 列的矩阵上，我们从 (r0, c0) 面朝东面开始这里，网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。现在，我们以顺时针按螺旋状行走，访问此网格中的每个位置。每当我们移动到网格的边界之外时，我们会继续在网格之外行走（但稍后可能会返回到网格边界）。最终，我们到过网格的所有 R * C 个空间。按照访问顺序返回表示网格位置的坐标列表。

读懂题意照着走就完事

class Solution {
public:vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {vector<vector<int>> res;vector<pair<int, int>> around = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};  //顺时针方向int x = r0, y = c0, num = 1, dir = 0;  //{x, y}为当前位置，num为当前查找的数字，dir为当前的方向int Left = c0 - 1, Right = c0 + 1, Upper = r0 - 1, Bottom = r0 + 1;  //四个方向的边界while (num <= R * C) {if (x >= 0 && x < R && y >= 0 && y < C) {  //{x， y}位置在矩阵中res.push_back({x, y});num += 1;}if (dir == 0 && y == Right) {  //向右到右边界dir += 1;  //调转方向向下Right += 1;  //右边界右移}else if (dir == 1 &&  x == Bottom) {  //向下到底边界dir += 1;Bottom += 1;  //底边界下移}else if (dir == 2 && y == Left) {  //向左到左边界dir += 1;Left--;  //左边界左移}else if (dir == 3 && x == Upper) {  //向上到上边界dir = 0;Upper--;  //上边界上移}x += around[dir].first;   //下一个节点y += around[dir].second;}return res;}
};

可能的二分法
给定一组 N 人（编号为 1, 2, …, N），我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。形式上，如果 dislikes[i] = [a, b]，表示不允许将编号为 a 和 b 的人归入同一组。当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。

转化为图的问题，或者用集合存放并查找

class Solution {
public:bool paint(int x, int c, vector<vector<int>>& edges, vector<int>& colors) {if (colors[x] == c) return true;else if (colors[x] != 0 && colors[x] != c) return false;colors[x] = c;int reversed = (c == 1 ? 2 : 1);for (auto& e : edges[x]) {if (!paint(e, reversed, edges, colors)) {colors[x] = 0;return false;}}return true;}bool possibleBipartition(int N, vector<vector<int>>& dislikes) {vector<vector<int>> edges(N);for (auto e : dislikes) {edges[e[0]-1].push_back(e[1]-1);}vector<int> colors(N, 0);for (int i = 0; i < N; ++i) {if(!paint(i, 1, edges, colors) && !paint(i, 2, edges, colors)) {return false;}}return true;}
};

鸡蛋掉落
给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。已知存在楼层 f ，满足 0 <= f <= n ，任何从高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中重复使用这枚鸡蛋。请你计算并返回要确定 f 确切的值的最小操作次数是多少？

经典动态规划问题，也可以反向思维考虑t次操作、k个鸡蛋最多能到多少层楼

class Solution {
public:int superEggDrop(int k, int n) {if (n == 1) {return 1;}vector<vector<int>> f(n + 1, vector<int>(k + 1));for (int i = 1; i <= k; ++i) {f[1][i] = 1;}int ans = -1;for (int i = 2; i <= n; ++i) {for (int j = 1; j <= k; ++j) {f[i][j] = 1 + f[i - 1][j - 1] + f[i - 1][j];}if (f[i][k] >= n) {ans = i;break;}}return ans;}
};