leetcode解题思路分析（九十六）832

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

翻转图像
给定一个二进制矩阵 A，我们想先水平翻转图像，然后反转图像并返回结果。水平翻转图片就是将图片的每一行都进行翻转，即逆序。例如，水平翻转 [1, 1, 0] 的结果是 [0, 1, 1]。反转图片的意思是图片中的 0 全部被 1 替换， 1 全部被 0 替换。例如，反转 [0, 1, 1] 的结果是 [1, 0, 0]。

在一次遍历中，即进行逆序也进行值的反转，用双指针完成任务

class Solution {
public:vector<vector<int>> flipAndInvertImage(vector<vector<int>>& image) {int n = image.size();for (int i = 0; i < n; i++) {int left = 0, right = n - 1;while (left < right) {if (image[i][left] == image[i][right]) {image[i][left] ^= 1;image[i][right] ^= 1;}left++;right--;}if (left == right) {image[i][left] ^= 1;}}return image;}
};

字符串中的查找与替换
某个字符串 S 需要执行一些替换操作，用新的字母组替换原有的字母组（不一定大小相同）。

唯一的问题是Indices可能不是递增，所以先遍历一遍看看哪些需要改哪些不用改，然后依次修改即可


class Solution {
public:string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {stringstream ss;// 构建mark表示是否需要被替换int mark[s.size()];memset(mark, 0, sizeof(mark));for (int i = 0; i < indices.size(); ++i){if (s.substr(indices[i], sources[i].size()) == sources[i]){mark[indices[i]] = i+1;}}// 默认值是0，所以必须>0才考虑int n = s.size();int i = 0;while (i < n){if (mark[i] == 0){ss << s[i];++i;}else{ss << targets[mark[i]-1];i += sources[mark[i]-1].size();}}return ss.str();}
};

树中距离之和
给定一个无向、连通的树。树中有 N 个标记为 0…N-1 的节点以及 N-1 条边。第 i 条边连接节点 edges[i][0] 和 edges[i][1] 。返回一个表示节点 i 与其他所有节点距离之和的列表 ans。

重复很多相同的子情况，所以用动态规划很合理。为了减少计算量，这里有个很巧妙的设计：经过一次树形动态规划后其实我们获得了在 u 为根的树中，每个节点为根的子树的答案 dp，我们可以利用这些已有信息来优化时间复杂度。假设 u的某个后代节点为 v，如果要算 v 的答案，本来我们要以 v 为根来进行一次树形动态规划。但是利用已有的信息，我们可以考虑树的形态做一次改变，让 v 换到根的位置，u 变为其孩子节点，同时维护原有的 dp 信息。在这一次的转变中，我们观察到除了 u 和 v 的 dp 值，其他节点的 dp 值都不会改变，因此只要更新 dp[u] 和 dp[v] 的值即可。

class Solution {
public:vector<int> ans, sz, dp;vector<vector<int>> graph;void dfs(int u, int f) {sz[u] = 1;dp[u] = 0;for (auto& v: graph[u]) {if (v == f) {continue;}dfs(v, u);dp[u] += dp[v] + sz[v];sz[u] += sz[v];}}void dfs2(int u, int f) {ans[u] = dp[u];for (auto& v: graph[u]) {if (v == f) {continue;}int pu = dp[u], pv = dp[v];int su = sz[u], sv = sz[v];dp[u] -= dp[v] + sz[v];sz[u] -= sz[v];dp[v] += dp[u] + sz[u];sz[v] += sz[u];dfs2(v, u);dp[u] = pu, dp[v] = pv;sz[u] = su, sz[v] = sv;}}vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {ans.resize(n, 0);sz.resize(n, 0);dp.resize(n, 0);graph.resize(n, {});for (auto& edge: edges) {int u = edge[0], v = edge[1];graph[u].emplace_back(v);graph[v].emplace_back(u);}dfs(0, -1);dfs2(0, -1);return ans;}
};

图像重叠
给你两个图像 img1 和 img2 ，两个图像的大小都是 n x n ，用大小相同的二维正方形矩阵表示。（并且为二进制矩阵，只包含若干 0 和若干 1 ）转换其中一个图像，向左，右，上，或下滑动任何数量的单位，并把它放在另一个图像的上面。之后，该转换的重叠是指两个图像都具有 1 的位置的数目。（请注意，转换不包括向任何方向旋转。）最大可能的重叠是多少？

计算便宜量，然后比较取最大值

class Solution {
public:const int N=30;int cnt[4000];int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {int n=img1.size();using pii=pair<int,int>;int res=0;vector<pii> vec;for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(img2[i][j])vec.push_back({i,j});    //找出img2中所有1的坐标for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(img1[i][j]){for(auto& [row,col]:vec)   //遍历img2中所有1的坐标{int a=row-i+N;         //计算img1到img2的偏移量，+N防止负数int b=col-j+N;cnt[flat(a,b)]++;       //相同偏移量对应计数+1res=max(res,cnt[flat(a,b)]);}}return res;}int flat(int& row,int& col) //编码计算{return (row<<6)+col;}
};

矩形重叠
矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。矩形的上下边平行于 x 轴，左右边平行于 y 轴。如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。给出两个矩形 rec1 和 rec2 。如果它们重叠，返回 true；否则，返回 false 。

两矩形相交，则长和宽的投影必相交，即x/y轴的两条线都要相交才算重叠

class Solution {
public:bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {return (min(rec1[2], rec2[2]) > max(rec1[0], rec2[0]) &&min(rec1[3], rec2[3]) > max(rec1[1], rec2[1]));}
};

新21点
爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：
爱丽丝以 0 分开始，并在她的得分少于 K 分时抽取数字。抽取时，她从 [1, W] 的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。每次抽取都是独立的，其结果具有相同的概率。
当爱丽丝获得不少于 K 分时，她就停止抽取数字。爱丽丝的分数不超过 N 的概率是多少？

概率论数学题

class Solution {
public:double new21Game(int n, int k, int maxPts) {if (k == 0) {return 1.0;}vector<double> dp(k + maxPts);for (int i = k; i <= n && i < k + maxPts; i++) {dp[i] = 1.0;}dp[k - 1] = 1.0 * min(n - k + 1, maxPts) / maxPts;for (int i = k - 2; i >= 0; i--) {dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts;}return dp[0];}
};

推多米诺
一行中有 N 张多米诺骨牌，我们将每张多米诺骨牌垂直竖立。
在开始时，我们同时把一些多米诺骨牌向左或向右推。
返回表示最终状态的字符串。

L和R隔开的部分是一个个子数组，每个子数组再取中间值考虑每个成员的倒向即可


class Solution {
public:string pushDominoes(string dominoes) {int n = dominoes.size();int* diff = new int[n];memset(diff, 0, sizeof(int)*n);// 从左往右int weight = 0;for (int i = 0; i < n; ++i){if (dominoes[i] == 'R'){weight = n;}else if (dominoes[i] == 'L'){weight = 0;}else{weight = max(weight-1, 0);}diff[i] = weight;}// 从右往左weight = 0;for (int i = n-1; i >= 0; --i){if (dominoes[i] == 'L'){weight = n;}else if (dominoes[i] == 'R'){weight = 0;}else{weight = max(weight-1, 0);}diff[i] -= weight;}for (int i = 0; i < n; ++i){dominoes[i] = diff[i] > 0 ? 'R' : (diff[i] < 0 ? 'L' : '.');}return dominoes;}
};