2127. 参加会议的最多员工数
因为发错了显示过于相似 多加点字让它不那么相似
题解
本题是一道难题，本题有一个很重要的条件即每个人只能喜欢一个人，平时在说到三角恋时常常喜欢用一个图来表示A喜欢B，B喜欢C，C喜欢A，用有向箭头表示每个人喜欢的方向，得到的就是一个三角形仅有三个节点的有向图，那么本题也可以做同样的处理构建出一个有向图。
接下来就要考虑这个有向图的特点了，该图任意节点的入度不受限制但出度必定为1。如果我们要让尽可能多的人同时坐在圆桌上，就要找到一条有向图中的路径，这个路径要么自身就是一个环，这样环内的所有人都可以在满足题目条件的情况下坐在同一个圆桌上（类似三角恋，只不过人数更多，从环上任意一点开始最终会回到该点），要么只有一个二元环，即存在一个A喜欢B，B喜欢A的小环，这样只需让A和B坐在一起，再将喜欢A的以及后续一连串人放在A旁边，将喜欢B的及后续一串放在B旁边（如C->D->B)。这样也可以坐在同一个圆桌上且满足题目条件。注意在这一安排的基础上还可以将其他的二元环继续安排在圆桌上，考虑C->D->B，G->E->A的情况，若A和B互相喜欢，则前面提到的两条链可以安排在圆桌上，在C和G之间还可以继续安排其他二元环对应的链(如下方手绘图所示)，除此以外均不能安排在同一个圆桌上。那么就要解决找到二元环或者更大的环的问题。
如何寻找有向图中的环呢，比较经典的是使用拓扑排序，在拓扑排序结束后，如果还有图中的节点没有处理，则说明这些节点位于环中，此时根据环的大小做不同处理，若环大小为2则要将对应的两个节点后面的两条最长的链加和再与之前的二元环得到的双链长度和加和，若环大于2则直接使用环的长度并更新当前的最大环的长度。每个节点后面的最长链的长度可以在拓扑排序的过程中记录下来，当有更长的链时更新链长度即可。最终将双链和与单独的最大环的长度比较取二者中的最大值。
代码
class Solution {
public:
int maximumInvitations(vector<int>& favorite) {
int n = favorite.size();
vector<int> inDegree(n, 0);
vector<bool> visited(n, false);
vector<int> dp(n, 1);
// 计算入度
for (int i = 0; i < n; i++) {
inDegree[favorite[i]]++;
}
// 拓扑排序的队列
queue<int> q;
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
// 拓扑排序
while (!q.empty()) {
int curr = q.front();
q.pop();
visited[curr] = true;
int next = favorite[curr];
dp[next] = max(dp[next], dp[curr] + 1);
inDegree[next]--;
if (inDegree[next] == 0) {
q.push(next);
}
}
int maxCycle = 0; // 最大环的大小
int sumChain = 0; // 所有双向链的和
// 处理剩余的环
for (int i = 0; i < n; i++) {
if (!visited[i]) {
int cycleLen = 0;
int curr = i;
// 计算环的大小
while (!visited[curr]) {
visited[curr] = true;
cycleLen++;
curr = favorite[curr];
}
// 如果是大小为2的环
if (cycleLen == 2) {
int len1 = dp[i];
int len2 = dp[favorite[i]];
sumChain += len1 + len2;
} else {
maxCycle = max(maxCycle, cycleLen);
}
}
}
return max(maxCycle, sumChain);
}
};
1462. 课程表 IV
题解
本题注意题目中明确说明了题目中不存在环，并且注意到课程数很少（小于等于100）而查询数量可能非常大（10的5次方），因此同样可以先将依赖关系构建成一张图，再遍历所有课程对这些课程既可使用bfs也可使用dfs，此处使用dfs。构建一个二维布尔型数组，数组的行表示前置节点，列下标表示后置节点，数组的值表示前置节点是否是后置节点的前置条件。在搜索过程中将每个节点的后置节点对应的后面的课程传播到当前节点中，即以后置节点为前置条件的节点都会以当前节点为前置条件。考虑到课程数比较小，这样做占用的空间也在可接受的范围内，但会大大加快查询的速度。
代码
class Solution {
public:
int numCourse;
vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
numCourse = numCourses;
vector<vector<int>> graph(numCourses);
for (const auto& prereq : prerequisites) {
graph[prereq[0]].push_back(prereq[1]);
}
vector<vector<bool>> isPrerequisite(numCourses, vector<bool>(numCourses, false));
for (int course = 0; course < numCourses; ++course) {
vector<bool> visited(numCourses, false);
dfs(course, graph, visited, isPrerequisite);
}
vector<bool> answer;
for (const auto& query : queries) {
answer.push_back(isPrerequisite[query[0]][query[1]]);
}
return answer;
}
private:
void dfs(int course, const vector<vector<int>>& graph, vector<bool>& visited, vector<vector<bool>>& isPrerequisite) {
visited[course] = true;
for (int nextCourse : graph[course]) {
if (!visited[nextCourse]) {
isPrerequisite[course][nextCourse] = true;
dfs(nextCourse, graph, visited, isPrerequisite);
for (int k = 0; k < numCourse; ++k) {
if (isPrerequisite[nextCourse][k]) {
isPrerequisite[course][k] = true;
}
}
}
}
}
};
2658. 网格图中鱼的最大数目
题解
本题注意只要相连的有鱼的格子就可以在一次打鱼的过程中全部收走，这就意味着不同的有鱼的区域不会重叠，因为一旦存在重叠就可以在一次打鱼过程中收走，就可以视为同一个区域。这就意味着可以将已经访问过的格子标记为已访问而不会出现同一个格子会被从不同区域重复访问到的情况。则直接从头遍历grid数组，碰到大于0的格子就使用dfs或者bfs，此处使用bfs来向四周遍历，遍历过程中如果遇到大于0的格子就继续遍历，遇到为0的格子就停止遍历，将所有已经访问过大于0的格子都标记为-1，将该区域所有格子中的鱼的个数加和即得该区域的鱼的总和，继续向后遍历grid数组，执行同样的操作。
代码
class Solution {
public:
int findMaxFish(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
int maxFish = 0;
vector<pair<int, int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] > 0) {
int currentAreaFish = 0;
queue<pair<int, int>> q;
q.push({i, j});
currentAreaFish += grid[i][j];
grid[i][j] = -1;
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
for (const auto& dir : dirs) {
int newR = r + dir.first;
int newC = c + dir.second;
if (newR >= 0 && newR < m && newC >= 0 && newC < n &&
grid[newR][newC] > 0) {
currentAreaFish += grid[newR][newC];
grid[newR][newC] = -1;
q.push({newR, newC});
}
}
}
maxFish = max(maxFish, currentAreaFish);
}
}
}
return maxFish;
}
};
684. 冗余连接
题解
本题是一道经典的在无向图中寻找环的问题，比较经典的方法就是使用并查集，依次遍历图中的边，如果两个节点不在同一个集合中就放入同一个集合，如果在同一个集合中则证明到现在为止遍历的全部的边构成的图中存在环且最后遍历的这条边就是环中的一条边，根据题目条件可知图中最多有一个环（只有一个冗余边），则删掉这条边图中就没有环了，剩下的边构成的即为树。而这条边满足输入中最后出现这一条件，因为就是这条边使得图中构成了环。
代码
class Solution {
public:
struct dsu{
vector<size_t> pa;
explicit dsu(size_t size):pa(size+1){iota(pa.begin(),pa.end(),0);}
size_t find(size_t x){
while(pa[x]!=x){
x = pa[x];
}
return x;
}
void union_set(size_t x, size_t y){
size_t rootX = find(x);
size_t rootY = find(y);
pa[rootY] = rootX;
}
};
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
dsu unionfind(edges.size());
for(const auto& edge : edges){
if(unionfind.find(edge[0]) != unionfind.find(edge[1])){
unionfind.union_set(edge[0],edge[1]);
}else{
return edge;
}
}
return vector<int>{};
}
};
2493. 将节点分成尽可能多的组
题解
本题是一道难题，也是看了题解才明白如何解决该题。
要想解决该题，首先要观察到一个非常重要的现象，即任何可以被分成两个以上不同组的连通图中的所有节点，最终都可以通过合并归类到两个组中。如当前有四个不同的组，则一定可以将第四组和第二组合并到一起，因为二者都和第三组相连，二第四组和第一组又无关，因此合并后一定满足条件，现在变为三组，同理可以将第三组和第一组合并，这样就变成了两组，由此可以发现，只要图能够被分为两组，且只有位于不同组的节点之间有边，该图就可以被分成不同的组，即图必须是一个二分图。
判断二分图的常用办法即涂色法，即将图中节点分为两组后，每组中的全部节点都是同一种颜色。在实际实现时，只需将每个节点的相邻节点都涂为和当前节点不同的颜色即可，一旦出现冲突即说明该图不是二分图。
第二个难点是观察到是二分图的情况下，一个连通图最多可以被分成的组的个数即为图的直径(图中两个节点之间最远的距离)，其实想到了之后验证起来就会觉得这也是一个很显然的事情（会的不难，难的不会，验证想法的难度总小于想到想法本身），只考虑直径这条路径，则这条路径从任意一端开始，执行bfs，将一次bfs中同一层的所有节点都放在同一个组中，如此反复，最终到直径的另一端，一定可以得到一种有效的分组，而直径又是图中的两节点之间的最长距离，因此不可能有数量更多的分组了。无向图的直径的计算最简便直接的方法是对每个节点都执行bfs，找到离该节点最远的节点的距离，所有距离中的最大值即为该图的直径。
代码
class Solution {
public:
int bfs(int start, vector<vector<int>>& adj, int n) {
vector<int> levels(n + 1, -1);
queue<int> q;
q.push(start);
levels[start] = 0;
int maxLevel = 0;
while (!q.empty()) {
int curr = q.front();
q.pop();
for (int next : adj[curr]) {
if (levels[next] == -1) {
levels[next] = levels[curr] + 1;
maxLevel = max(maxLevel, levels[next]);
q.push(next);
}
}
}
return maxLevel + 1; // 返回最大可能的分组数
}
bool isBipartite(int start, vector<vector<int>>& adj, vector<int>& color, int n) {
queue<int> q;
q.push(start);
color[start] = 0;
while (!q.empty()) {
int curr = q.front();
q.pop();
for (int next : adj[curr]) {
if (color[next] == -1) {
color[next] = 1 - color[curr];
q.push(next);
} else if (color[next] == color[curr]) {
return false;
}
}
}
return true;
}
void dfs(int node, vector<vector<int>>& adj, vector<bool>& visited, vector<int>& component) {
visited[node] = true;
component.push_back(node);
for (int next : adj[node]) {
if (!visited[next]) {
dfs(next, adj, visited, component);
}
}
}
int magnificentSets(int n, vector<vector<int>>& edges) {
vector<vector<int>> adj(n + 1);
for (const auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
vector<bool> visited(n + 1, false);
vector<vector<int>> components;
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
vector<int> component;
dfs(i, adj, visited, component);
components.push_back(component);
}
}
int result = 0;
for (const auto& component : components) {
vector<int> color(n + 1, -1);
if (!isBipartite(component[0], adj, color, n)) {
return -1;
}
// 对于每个连通分量，尝试从每个节点开始BFS，取最大值
int maxGroups = 0;
for (int node : component) {
maxGroups = max(maxGroups, bfs(node, adj, n));
}
result += maxGroups;
}
return result;
}
};
827. 最大人工岛
题解
本题先从头遍历数组，遇到陆地则使用bfs或者dfs遍历整个连通区域。构建一个数组，对每个连通区域中的所有陆地都用同一个大于0的数字表示，数组中的下标代表该连通区域使用的数字，数组的值表示该连通区域的陆地个数，如将第一个遇到的连通区域所有陆地都赋值为2，第二个则全部赋值为3，第三个全部赋值为4。再从头遍历数组，对于所有为0的位置，查看其四个方向的位置的值，若大于0则说明是一个区域，获得四个方向全部大于0的值对应编号区域的陆地数量(注意去重)，将数量加和再加1即得该处将0变为陆地后能得到的更大连通区域中包含陆地的个数，将该值与记录的最大值比较并更新最大值。
代码
class Solution {
private:
vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
void dfs(vector<vector<int>>& grid, int x, int y, int mark, int& size) {
int n = grid.size();
grid[x][y] = mark;
size++;
for (const auto& dir : dirs) {
int nx = x + dir.first;
int ny = y + dir.second;
if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 1) {
dfs(grid, nx, ny, mark, size);
}
}
}
public:
int largestIsland(vector<vector<int>>& grid) {
int n = grid.size();
vector<int> area(n * n + 2, 0);
int mark = 2;
// 第一次遍历：标记不同的岛屿
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
int size = 0;
dfs(grid, i, j, mark, size);
area[mark] = size;
mark++;
}
}
}
if (mark == 2) return 1;
if (mark == 3 && area[2] == n * n) return n * n;
int maxArea = 0;
// 第二次遍历：尝试将0变成1
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
// 使用数组记录相邻的岛屿标记
int neighbors[4] = {0}; // 最多4个相邻岛屿
int idx = 0;
for (const auto& dir : dirs) {
int nx = i + dir.first;
int ny = j + dir.second;
if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] > 1) {
// 检查是否已经记录过这个岛屿标记
bool found = false;
for (int k = 0; k < idx; k++) {
if (neighbors[k] == grid[nx][ny]) {
found = true;
break;
}
}
if (!found) {
neighbors[idx++] = grid[nx][ny];
}
}
}
// 计算将当前0变成1后的面积
int currentArea = 1;
for (int k = 0; k < idx; k++) {
currentArea += area[neighbors[k]];
}
maxArea = max(maxArea, currentArea);
}
}
}
return maxArea == 0 ? area[2] : maxArea;
}
};
3151. 特殊数组 I
题解
本题是一道简单题，只需记录前一个数字的奇偶性，将当前数字的奇偶性与前一个数字比较，如果不同则将奇偶性替换为当前数字的奇偶性。简单说即为使用长度为2的滑动窗口，保证窗口内的两个数字奇偶性不同即可，否则返回false。
代码
class Solution {
public:
bool isArraySpecial(vector<int>& nums) {
for(int i=0;i<nums.size()-1;i++){
if(nums[i]%2==nums[i+1]%2){
return false;
}
}
return true;
}
};
1752. 检查数组是否经排序和轮转得到
题解
本题是一道简单题，数组中的数字只会被旋转一次，因此符合要求的数组最多只会有两个连续的非递减序列且第二个序列的最大值小于等于第一个序列的最小值。则使用一个变量指示当前是第几个序列，如果当前值大于等于上一个值则序列号不变，否则将序列号加一，注意此处说的当前值和上一个值包括循环的数组比较，即数组最后的值和数组的第一个值。最后若序列号小于等于2则满足条件，否则不满足条件。
代码
class Solution {
public:
bool check(vector<int>& nums) {
int count = 1;
int n = nums.size();
for(int i=0;i<n;i++){
if(nums[i]>nums[(i+1)%n]){
count++;
}
}
return count<=2;
}
};
3105. 最长的严格递增或递减子数组
题解
本题是一道简单题，用一个数字记录当前递增或递减子数组的长度和当前是递增还是递减，当递增性或者递减性被打破时将该数字与记录的最大值比较并尝试更新最大值，再将数字重置为2（被打破说明有两个数字的递增递减性发生变化），若遇到下一个数字与前一个数字相同则将数字重置为1并尝试更新最大值，直到数组末尾，再次更新最大值避免漏掉到数组末尾的最后一段子数组。
代码
class Solution {
public:
int longestMonotonicSubarray(vector<int>& nums) {
int result = 0;
int current = 1;
bool up = true;
for(int i=0;i<nums.size()-1;i++){
if(nums[i]>nums[i+1]){
if(up){
up = false;
result = max(result, current);
current = 2;
}else{
current++;
}
}else if(nums[i]<nums[i+1]){
if(up){
current++;
}else{
up = true;
result = max(result, current);
current = 2;
}
}else{
result = max(result, current);
current = 1;
}
}
result = max(result, current);
return result;
}
};
1 个赞
1800. 最大升序子数组和
题解
本题是一道简单题，只需要考虑递增子数组，则如果出现了前后两个数字递减或者相同的情况就重置数组的起始位置和数组和，直到再次遇到递增的情况，将每个递增子数组的和（注意单个数字也算一种递增子数组）与保存的最大值比较并更新最大值。
代码
class Solution {
public:
int maxAscendingSum(vector<int>& nums) {
int tempsum = nums[0];
int result = nums[0];
for(int i=1;i<nums.size();i++){
if(nums[i] <= nums[i-1]){
result = max(tempsum,result);
tempsum = nums[i];
}else{
tempsum += nums[i];
}
}
result = max(tempsum,result);
return result;
}
};
1790. 仅执行一次字符串交换能否使两个字符串相等
题解
本题是一道简单题，直接逐字符遍历两个字符串并挨个字符比较，记录两个字符串中同一位置上出现不同字符的次数并且分别记录出现的不同字符，如果遍历完成后不同字符出现了两次并且出现的不同字符字符相同仅位置不同（一共只有两个字符，则为a[0]=b[1]且a[1]=b[0]），则返回true。否则返回false。
代码
class Solution {
public:
bool areAlmostEqual(string s1, string s2) {
int count = 0;
vector<char> s1d;
vector<char> s2d;
for(int i=0;i<s1.size();i++){
if(s1[i]!=s2[i]){
count++;
if(count>2){
return false;
}
s1d.push_back(s1[i]);
s2d.push_back(s2[i]);
}
}
if(count==0){
return true;
}else if(count==1){
return false;
}else{
if(s1d[0]==s2d[1] && s1d[1]==s2d[0]){
return true;
}
}
return false;
}
};
1726. 同积元组
题解
本题注意满足条件的两组数字，进行任意的位置交换都被认为是不同的元组，因此满足条件的两组数字共有8种不同的元组构成方式，则本题只要找到所有乘积相同的两组数字，将这些数字的组数乘8即得最终的结果。
同时发现题目中说明所有的数字均为不同的正整数，则任意两个数字相乘得到一个乘积，如果同一个乘积出现了多次，说明有不同的两数字组可以得到相同的乘积（所有数字均不相同，同一个数字不可能和两个不同数字相乘得到相同的乘积，则能得到相同的乘积两个数字必定均不相同），本题只要求计算出最终的数量而不要求列出具体的组合。则计算出数组中全部的两两相乘的乘积并放入哈希表中统计乘积出现的次数，再对出现次数大于等于2的乘积，计算从中挑选出2个的组合数，将全部组合数加和乘8即得最终结果。
代码
class Solution {
public:
int tupleSameProduct(vector<int>& nums) {
unordered_map<int,int> count;
for(int i=0;i<nums.size();i++){
for(int j=i+1;j<nums.size();j++){
count[nums[i]*nums[j]] = count[nums[i]*nums[j]]+1;
}
}
int result = 0;
for(const pair<int,int>& c : count){
if(c.second >= 2){
result += c.second*(c.second-1)/2;
}
}
return result*8;
}
};
3160. 所有球里面不同颜色的数目
题解
本题要统计在每次染色后所有现存的球上的不同颜色有多少种。则需要记录三个数据，一个是当前所有球上共有多少种不同的颜色，另一个则是当前存在的各种颜色对应的存在的球的个数，以及不同编号的球上当前对应的颜色编号（初始默认所有球上的颜色编号均为0表示没有颜色），可以用哈希表来记录每种颜色对应的球的个数和不同球对应的颜色，对每个查询，给对应的球涂色，如果该球以前存在一个颜色，则查询哈希表并将该颜色对应的球的个数减一，如果归零则将颜色种类减一，并将新的颜色对应的球的个数加一，如果之前新的新色对应的个数为0则将颜色种类加一，将此时的颜色数作为该查询对应的结果插入数组末尾，最终返回结果数组。
代码
class Solution {
public:
vector<int> queryResults(int limit, vector<vector<int>>& queries) {
unordered_map<int,int> balls;
int count = 0;
unordered_map<int,int> colors;
vector<int> result;
for(const auto& query : queries){
if(colors[balls[query[0]]]>0){
if(colors[balls[query[0]]]==1){
count--;
}
colors[balls[query[0]]] = colors[balls[query[0]]]-1;
}
if(colors[query[1]]==0){
count++;
}
colors[query[1]] = colors[query[1]]+1;
balls[query[0]] = query[1];
result.push_back(count);
}
return result;
}
};
2349. 设计数字容器系统
题解
本题需要保存两个数据，一个是不同的index对应的数字，另外则是一个数字对应的全部index，由于要快速返回某个数字对应的最小index，同时要频繁插入和删除某个数字对应的不同index且某个数字对应的index没有重复。故可以使用c++中的set容器来保存某个数字对应的index。故用两个哈希表，一个哈希表的键为index，值为数字，另一个哈希表的键为数字，值为一个set。对插入或者替换操作，在修改index表对应的数字时也要向数字为键的哈希表中的set插入index，而对find操作则直接返回数字对应的set中的最小值，不存在最小值则返回-1。
代码
class NumberContainers {
public:
NumberContainers() {
}
void change(int index, int number) {
if (index_to_number.count(index)) {
int old_number = index_to_number[index];
number_to_indices[old_number].erase(index);
if (number_to_indices[old_number].empty()) {
number_to_indices.erase(old_number);
}
}
index_to_number[index] = number;
number_to_indices[number].insert(index);
}
int find(int number) {
if (number_to_indices.count(number)) {
return *number_to_indices[number].begin();
} else {
return -1;
}
}
private:
unordered_map<int, int> index_to_number;
unordered_map<int, set<int>> number_to_indices;
};
1 个赞
2364. 统计坏数对的数目
题解
本题是一道很有意思的题目，首先可以想到与其找j-i != nums[j]-nums[i]的情况，不如找j-i == nums[j]-nums[i]的情况。因为后者大概是少数，而如果保持原来的等式形式，等式两边都同时涉及两个无关的变量，此时要计算出任意一边都必须同时知道两方的数据，而对于全部的数据，要全部计算出来只能通过暴力计算的形式全部算出，但如果简单的变换一下等式，变为j-nums[j]==i-nums[i]可以发现只是将以前的等式两边做了移项，等式仍然成立，但此时等式两边都变为了仅和同一个下标相关，在算法实现中就产生了非常大的影响，因为此时我们只需遍历一次数组，将全部i-nums[i]的值计算出来，统计不同差值各自的个数，对于个数大于1的差值，通过不断计算求和（假设个数为n，则满足等式条件的两两下标的组合个数为n-1+n-2+n-3…+1即n*(n-1)/2)最终即得得出全部满足j-nums[j]==i-nums[i]条件的下标组合的个数。再用该数组能得到的两两组合的总数减去满足等式条件的组合个数即得最终个数。
代码
class Solution {
public:
long long countBadPairs(std::vector<int>& nums) {
std::unordered_map<int, int> count;
for (int i = 0; i < nums.size(); ++i) {
count[i - nums[i]]++;
}
long long total_pairs = (long long)nums.size() * (nums.size() - 1) / 2;
long long good_pairs = 0;
for (auto const& [diff, freq] : count) {
if (freq > 1) {
good_pairs += (long long)freq * (freq - 1) / 2;
}
}
return total_pairs - good_pairs;
}
};
总结
本题要注意，对于一些描述比较抽象的问题，要将题目中的一些条件和意义对应到计算机的算法当中，如i有着数组下标这一真实的数据结构含义，因此通过变换就可以优化在算法中的计算效率，这是由数组本身的特性决定的。即只能一个一个的访问，因此要在一次访问中得到尽可能最有用的信息以避免后续重复访问，如果数组计算是可以并行进行的，如能同时进行下标0和后面全部数组下标的差值及下标对应的数组值的差值的计算，则就没必要进行这样的变换处理，因为能并行的情况下也只需要n次计算就能得出最终的结果。
1 个赞
3174. 清除数字
题解
本题每次在移除数字的时候也会移除离数字最近的左侧的非数字字符，则每次碰到数字时需要移除连续的数字和紧挨着数字左侧的连续的相同个数的非数字字符，如果按照正常的从左向右访问数组，则无法预知后面连续的数字的个数，则无法确定前面要删除的非数字个数，但如果从右向左访问数组，当遇到非数字字符时就一定可以知道右侧出现了多少个数字字符。则可以将本题看成一个栈问题，遇到数字字符入栈，遇到非数字字符就删掉字符并将一个数字出栈，如果栈高度为0则保留该非数字字符，后续被保留的字符继续在之前保留字符构成的字符串的前方拼接。由于具体的数字对本题无影响，因此只需要一个变量记录栈的高度，遇到非数字字符删掉字符并减少栈的高度即可。
代码
class Solution {
public:
string clearDigits(string s) {
string result = "";
int stack_height = 0;
for (int i = s.length() - 1; i >= 0; --i) {
if (isdigit(s[i])) {
stack_height++;
} else {
if (stack_height > 0) {
stack_height--;
} else {
result = s[i] + result;
}
}
}
return result;
}
};
2 个赞
1910. 删除一个字符串中所有出现的给定子字符串
题解
本题注意在删掉一个出现的子字符串后，在该子字符串前后的字符可能会组成一个新的满足题意的子字符串，有点像消消乐在消掉一个连续图案后前后的图案可能又可以组成连续图案再次消掉，达成连击。则可以利用c++的字符串处理函数直接找到匹配part字符串的起始位置，从字符串中删掉该位置处的part字符串，再次寻找匹配part字符串的位置，如此反复直到找不到part的位置。因此s的长度并不长，因此该方法的速度也很快。
代码
class Solution {
public:
string removeOccurrences(string s, string part) {
while (s.find(part) != string::npos) {
s.erase(s.find(part), part.size());
}
return s;
}
};
3 个赞
2342. 数位和相等数对的最大和
题解
本题可以用哈希表保存不同数字的数位和对应的最大的两个数字，在遇到新的有相同数位和的数字时将其和这两个数字比较，如果比最大值大，则更新最大值，将最大值放在次大值处，如果仅比次大值大，则仅更新次大值，计算这两个新的最大值的和并与保存的和比较。
代码
class Solution {
public:
int maximumSum(vector<int>& nums) {
unordered_map<int,pair<int,int>> sums;
int sum = 0;
int maxsum = -1;
for(const auto& num : nums){
sum = sumofnum(num);
if(num > sums[sum].first){
sums[sum].second = sums[sum].first;
sums[sum].first = num;
if(sums[sum].second > 0){
maxsum = max(maxsum,sums[sum].first+sums[sum].second);
}
}else if(num > sums[sum].second){
sums[sum].second = num;
maxsum = max(maxsum,sums[sum].first+sums[sum].second);
}
}
return maxsum;
}
int sumofnum(int num){
int sum = 0;
while(num != 0){
sum += num % 10;
num = num / 10;
}
return sum;
}
};
3066. 超过阈值的最少操作数 II
题解
本题注意到题目中会多次用到nums中的最小值，操作中的第三步min(x,y)*2+max(x,y)如果先拿到nums中的最小值，删掉这个最小值，再取出nums中的最小值则先取得的一定是更小的那个，后取得的是更大的那个。则此处可使用最小堆，弹出堆顶元素即为nums中的最小值，执行题目所述操作得到新的数字后再将新的数字插入堆中，如此反复直到堆顶元素大于等于k，返回记录的操作次数。
代码
class Solution {
public:
int minOperations(vector<int>& nums, int k) {
priority_queue<long long int,vector<long long int>,greater<long long int>> min_heap(nums.begin(), nums.end());
int opnum = 0;
long long int small = 0;
long long int big = 0;
while(min_heap.top() < k){
small = min_heap.top();
min_heap.pop();
big = min_heap.top();
min_heap.pop();
min_heap.push(small*2+big);
opnum++;
}
return opnum;
}
};
