Q1、[简单] 翻转图像
1、题目描述
给定一个 n x n 的二进制矩阵 image ，先 水平 翻转图像，然后 反转 图像并返回 结果 。
水平翻转图片就是将图片的每一行都进行翻转，即逆序。
- 例如，水平翻转
[1,1,0]的结果是[0,1,1]。
反转图片的意思是图片中的 0 全部被 1 替换， 1 全部被 0 替换。
- 例如，反转
[0,1,1]的结果是[1,0,0]。
示例 1：
输入：image = [[1,1,0],[1,0,1],[0,0,0]] 输出：[[1,0,0],[0,1,0],[1,1,1]] 解释：首先翻转每一行: [[0,1,1],[1,0,1],[0,0,0]]； 然后反转图片: [[1,0,0],[0,1,0],[1,1,1]]示例 2：
输入：image = [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]] 输出：[[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]] 解释：首先翻转每一行: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]]； 然后反转图片: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]提示：
n == image.lengthn == image[i].length1 <= n <= 20images[i][j]==0或1.
2、解题思路
- 水平翻转：
- 对于每一行，将其元素逆序排列。例如，
[1,1,0]变为[0,1,1]。
- 对于每一行，将其元素逆序排列。例如，
- 反转：
- 对于每个元素，如果是
0，则替换为1；如果是1，则替换为0。
- 对于每个元素，如果是
- 合并操作：
- 在水平翻转的同时，直接对元素进行反转，避免额外的遍历。
3、代码实现
C++
class Solution {
public:
vector<vector<int>> flipAndInvertImage(vector<vector<int>>& image) {
int n = image.size(); // 获取矩阵的大小
vector<vector<int>> ret(n, vector<int>(n)); // 创建结果矩阵
for (int i = 0; i < n; ++i) { // 遍历每一行
for (int j = 0; j < n; ++j) { // 遍历每一列
// 水平翻转：取 image[i][n - j - 1]
// 反转：对结果取反
ret[i][j] = !image[i][n - j - 1];
}
}
return ret; // 返回结果矩阵
}
};
Java
class Solution {
public int[][] flipAndInvertImage(int[][] image) {
int n = image.length; // 获取矩阵的大小
int[][] ret = new int[n][n]; // 创建结果矩阵
for (int i = 0; i < n; i++) { // 遍历每一行
for (int j = 0; j < n; j++) { // 遍历每一列
// 水平翻转：取 image[i][n - j - 1]
// 反转：对结果取反
ret[i][j] = 1 - image[i][n - j - 1];
}
}
return ret; // 返回结果矩阵
}
}
Python
class Solution:
def flipAndInvertImage(self, image: List[List[int]]) -> List[List[int]]:
n = len(image) # 获取矩阵的大小
ret = [[0] * n for _ in range(n)] # 创建结果矩阵
for i in range(n): # 遍历每一行
for j in range(n): # 遍历每一列
# 水平翻转：取 image[i][n - j - 1]
# 反转：对结果取反
ret[i][j] = 1 - image[i][n - j - 1]
return ret # 返回结果矩阵
4、复杂度分析
时间复杂度：
- 遍历矩阵的每个元素，时间复杂度为 O(n2)。
空间复杂度：
- 创建结果矩阵，空间复杂度为 O(n2)。
Q2、[中等] 字符串中的查找与替换
1、题目描述
你会得到一个字符串 s (索引从 0 开始)，你必须对它执行 k 个替换操作。替换操作以三个长度均为 k 的并行数组给出：indices, sources, targets。
要完成第 i 个替换操作:
- 检查 子字符串
sources[i]是否出现在 原字符串s的索引indices[i]处。 - 如果没有出现， 什么也不做 。
- 如果出现，则用
targets[i]替换 该子字符串。
例如，如果 s = "abcd" ， indices[i] = 0 , sources[i] = "ab"， targets[i] = "eee" ，那么替换的结果将是 "eeecd" 。
所有替换操作必须 同时 发生，这意味着替换操作不应该影响彼此的索引。测试用例保证元素间不会重叠 。
- 例如，一个
s = "abc"，indices = [0,1]，sources = ["ab"，"bc"]的测试用例将不会生成，因为"ab"和"bc"替换重叠。
在对 s 执行所有替换操作后返回 结果字符串 。
子字符串 是字符串中连续的字符序列。
示例 1：
输入：s = "abcd", indices = [0,2], sources = ["a","cd"], targets = ["eee","ffff"] 输出："eeebffff" 解释： "a" 从 s 中的索引 0 开始，所以它被替换为 "eee"。 "cd" 从 s 中的索引 2 开始，所以它被替换为 "ffff"。示例 2：
输入：s = "abcd", indices = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"] 输出："eeecd" 解释： "ab" 从 s 中的索引 0 开始，所以它被替换为 "eee"。 "ec" 没有从原始的 S 中的索引 2 开始，所以它没有被替换。提示：
1 <= s.length <= 1000k == indices.length == sources.length == targets.length1 <= k <= 1000 <= indices[i] < s.length1 <= sources[i].length, targets[i].length <= 50s仅由小写英文字母组成sources[i]和targets[i]仅由小写英文字母组成
2、解题思路
问题分析：
- 我们需要对字符串
s执行多个替换操作。 - 每个替换操作由
indices[i],sources[i],targets[i]定义。 - 替换操作必须同时发生，且不会相互影响。
- 我们需要对字符串
算法设计：
- 使用哈希表记录每个索引对应的替换操作。
- 遍历字符串
s，对于每个字符，检查是否有替换操作需要执行。 - 如果有替换操作，则检查
sources[i]是否匹配，如果匹配则替换为targets[i]，否则保留原字符。
优化：
使用哈希表快速查找每个索引的替换操作。
在遍历字符串时，直接跳过已替换的部分。
3、代码实现
C++
class Solution {
public:
string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {
int n = s.size(), m = indices.size(); // 获取字符串和操作数组的长度
unordered_map<int, vector<int>>
ops; // 哈希表, 记录每个索引对应的替换操作
for (int i = 0; i < m; ++i) {
ops[indices[i]].push_back(i); // 将操作索引加入哈希表
}
string ret; // 存储结果字符串
for (int i = 0; i < n;) {
bool succeed = false; // 标记是否成功执行替换
if (ops.count(i)) // 如果当前索引有替换操作
{
for (int pt : ops[i]) // 遍历所有替换操作
{
if (s.substr(i, sources[pt].size()) == sources[pt]) // 检查 sources[pt] 是否匹配
{
succeed = true; // 标记成功
ret += targets[pt]; // 替换为 targets[pt]
i += sources[pt].size(); // 跳过已替换的部分
break;
}
}
}
if (!succeed) // 如果没有执行替换
{
ret += s[i]; // 保留原字符
++i; // 移动到下一个字符
}
}
return ret;
}
};
Java
class Solution {
public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
int n = s.length(), m = indices.length; // 获取字符串和操作数组的长度
Map<Integer, List<Integer>> ops = new HashMap<>(); // 哈希表，记录每个索引对应的替换操作
for (int i = 0; i < m; i++) {
ops.computeIfAbsent(indices[i], k -> new ArrayList<>()).add(i); // 将操作索引加入哈希表
}
StringBuilder ans = new StringBuilder(); // 存储结果字符串
for (int i = 0; i < n;) { // 遍历字符串
boolean succeed = false; // 标记是否成功执行替换
if (ops.containsKey(i)) { // 如果当前索引有替换操作
for (int pt : ops.get(i)) { // 遍历所有替换操作
if (s.startsWith(sources[pt], i)) { // 检查 sources[pt] 是否匹配
succeed = true; // 标记成功
ans.append(targets[pt]); // 替换为 targets[pt]
i += sources[pt].length(); // 跳过已替换的部分
break; // 跳出循环
}
}
}
if (!succeed) { // 如果没有执行替换
ans.append(s.charAt(i)); // 保留原字符
i++; // 移动到下一个字符
}
}
return ans.toString(); // 返回结果字符串
}
}
Python
class Solution:
def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
n, m = len(s), len(indices) # 获取字符串和操作数组的长度
ops = {} # 哈希表，记录每个索引对应的替换操作
for i in range(m):
if indices[i] not in ops:
ops[indices[i]] = []
ops[indices[i]].append(i) # 将操作索引加入哈希表
ans = [] # 存储结果字符串
i = 0
while i < n: # 遍历字符串
succeed = False # 标记是否成功执行替换
if i in ops: # 如果当前索引有替换操作
for pt in ops[i]: # 遍历所有替换操作
if s.startswith(sources[pt], i): # 检查 sources[pt] 是否匹配
succeed = True # 标记成功
ans.append(targets[pt]) # 替换为 targets[pt]
i += len(sources[pt]) # 跳过已替换的部分
break # 跳出循环
if not succeed: # 如果没有执行替换
ans.append(s[i]) # 保留原字符
i += 1 # 移动到下一个字符
return ''.join(ans) # 返回结果字符串
4、复杂度分析
时间复杂度：O(n+ml)，其中 n 是字符串 s 的长度，m 是数组 indices 的长度，l 是数组 sources 和 targets 中字符串的平均长度。
空间复杂度：O(n+ml)。
Q3、[中等] 图像重叠
1、题目描述
给你两个图像 img1 和 img2 ，两个图像的大小都是 n x n ，用大小相同的二进制正方形矩阵表示。二进制矩阵仅由若干 0 和若干 1 组成。
转换 其中一个图像，将所有的 1 向左，右，上，或下滑动任何数量的单位；然后把它放在另一个图像的上面。该转换的 重叠 是指两个图像 都 具有 1 的位置的数目。
请注意，转换 不包括 向任何方向旋转。越过矩阵边界的 1 都将被清除。
最大可能的重叠数量是多少？
示例 1：
输入：img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]] 输出：3 解释：将 img1 向右移动 1 个单位，再向下移动 1 个单位。 两个图像都具有 1 的位置的数目是 3（用红色标识）。示例 2：
输入：img1 = [[1]], img2 = [[1]] 输出：1示例 3：
输入：img1 = [[0]], img2 = [[0]] 输出：0提示：
n == img1.length == img1[i].lengthn == img2.length == img2[i].length1 <= n <= 30img1[i][j]为0或1img2[i][j]为0或1
2、解题思路
问题分析：
- 我们需要找到一种滑动方式，使得两个图像的重叠
1的数量最大。 - 滑动操作可以看作是对一个图像进行平移，平移的范围是
[-n+1, n-1]。
- 我们需要找到一种滑动方式，使得两个图像的重叠
算法设计：
- 使用一个二维数组
count来记录所有可能的平移向量(dx, dy)对应的重叠数量。 - 对于
img1中的每个1，计算它与img2中的每个1的平移向量(i-x, j-y)，并在count中累加对应的重叠数量。 - 最终，
count中的最大值即为最大可能的重叠数量。
- 使用一个二维数组
优化：
- 使用
count数组的大小为[2*n+1][2*n+1]，以处理负的平移向量。
- 使用
3、代码实现
C++
class Solution {
public:
int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
int n = img1.size(); // 获取矩阵的大小
vector<vector<int>> count(2 * n + 1, vector<int>(2 * n + 1, 0)); // 记录平移向量的重叠数量
for (int i = 0; i < n; ++i) // 遍历 img1 的每一行
{
for (int j = 0; j < n; ++j) // 遍历 img1 的每一列
{
if (img1[i][j] == 1) // 如果 img1[i][j] 是 1
{
for (int x = 0; x < n; ++x) // 遍历 img2 的每一行
{
for (int y = 0; y < n; ++y) // 遍历 img2 的每一列
{
if (img2[x][y] == 1) // 如果 img2[i][j] 是 1
{
// 计算平移向量 (i-x, j-y), 并累加对应的重叠数量
count[i - x + n][j - y + n] += 1;
}
}
}
}
}
}
int ret = 0; // 记录最大的重叠数
for (const auto& row : count) { // 遍历 count 数组
for (int v : row) {
ret = max(ret, v); // 更新最大值
}
}
return ret;
}
};
Java
class Solution {
public int largestOverlap(int[][] img1, int[][] img2) {
int n = img1.length; // 获取矩阵的大小
int[][] count = new int[2 * n + 1][2 * n + 1]; // 记录平移向量的重叠数量
for (int i = 0; i < n; i++) { // 遍历 img1 的每一行
for (int j = 0; j < n; j++) { // 遍历 img1 的每一列
if (img1[i][j] == 1) { // 如果 img1[i][j] 是 1
for (int x = 0; x < n; x++) { // 遍历 img2 的每一行
for (int y = 0; y < n; y++) { // 遍历 img2 的每一列
if (img2[x][y] == 1) { // 如果 img2[x][y] 是 1
// 计算平移向量 (i-x, j-y), 并累加对应的重叠数量
count[i - x + n][j - y + n] += 1;
}
}
}
}
}
}
int ret = 0; // 记录最大的重叠数
for (int[] row : count) { // 遍历 count 数组
for (int v : row) {
ret = Math.max(ret, v); // 更新最大值
}
}
return ret; // 返回结果
}
}
Python
class Solution:
def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
n = len(img1) # 获取矩阵的大小
count = [[0] * (2 * n + 1) for _ in range(2 * n + 1)] # 记录平移向量的重叠数量
for i in range(n): # 遍历 img1 的每一行
for j in range(n): # 遍历 img1 的每一列
if img1[i][j] == 1: # 如果 img1[i][j] 是 1
for x in range(n): # 遍历 img2 的每一行
for y in range(n): # 遍历 img2 的每一列
if img2[x][y] == 1: # 如果 img2[x][y] 是 1
# 计算平移向量 (i-x, j-y), 并累加对应的重叠数量
count[i - x + n][j - y + n] += 1
ret = 0 # 记录最大的重叠数
for row in count: # 遍历 count 数组
for v in row:
ret = max(ret, v) # 更新最大值
return ret # 返回结果
4、复杂度分析
时间复杂度：
- 遍历
img1和img2的每个元素，时间复杂度为 O(N4)，其中N是矩阵的大小。
- 遍历
空间复杂度：
- 使用
count数组记录平移向量的重叠数量，空间复杂度为 O(N2)。
- 使用
Q4、[困难] 树中距离之和
1、题目描述
给定一个无向、连通的树。树中有 n 个标记为 0...n-1 的节点以及 n-1 条边 。
给定整数 n 和数组 edges ， edges[i] = [ai, bi]表示树中的节点 ai 和 bi 之间有一条边。
返回长度为 n 的数组 answer ，其中 answer[i] 是树中第 i 个节点与所有其他节点之间的距离之和。
示例 1:
输入: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]] 输出: [8,12,6,10,10,10] 解释: 树如图所示。 我们可以计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) 也就是 1 + 1 + 2 + 2 + 2 = 8。 因此，answer[0] = 8，以此类推。示例 2:
输入: n = 1, edges = [] 输出: [0]示例 3:
输入: n = 2, edges = [[1,0]] 输出: [1,1]提示:
1 <= n <= 3 * 104edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != bi- 给定的输入保证为有效的树
2、解题思路
- 问题分析：
- 树是一个连通无向图，没有环。
- 我们需要计算每个节点到其他所有节点的距离之和。
- 算法设计：
- 使用 树形动态规划 的思想，通过两次深度优先搜索（DFS）来计算每个节点的距离和。
- 第一次 DFS：从根节点开始，计算每个节点的子树大小
sz和子树中所有节点到当前节点的距离和dp。 - 第二次 DFS：从根节点开始，利用第一次 DFS 的结果，计算每个节点到其他所有节点的距离和
ans。
- 优化：
- 通过动态规划，避免重复计算，将时间复杂度优化到 O(n)。
3、代码实现
C++
class Solution {
private:
vector<int> ret, sz, dp; // ret: 结果数组, sz: 子树大小, dp: 子树中所有节点到当前节点的距离和
vector<vector<int>> graph; // 邻接表表示的树
// 第一次 DFS: 计算子树大小 sz 和子树中所有节点到当前节点的距离和 dp
void dfs1(int u, int f) {
sz[u] = 1; // 当前节点的子树大小初始化为 1
dp[u] = 0; // 当前节点的距离和初始化为 0
// 遍历当前节点的所有邻居
for (auto& v : graph[u]) {
// 跳过父节点
if (v == f) {
continue;
}
dfs1(v, u); // 递归处理子节点
dp[u] += dp[v] + sz[v]; // 更新当前节点的距离和
sz[u] += sz[v]; // 更新当前节点的子树大小
}
}
// 第二次 DFS: 计算每个节点到其他所有节点的距离和 ans
void dfs2(int u, int f) {
ret[u] = dp[u]; // 当前节点的距离和即为 dp[u]
// 遍历当前节点的所有邻居
for (auto& v : graph[u]) {
// 跳过父节点
if (v == f) {
continue;
}
int pu = dp[u], pv = dp[v]; // 保存当前节点和子节点的 dp 值
int su = sz[u], sv = sz[v]; // 保存当前节点和子节点的 sz 值
// 将当前节点 u 从树中移除，重新计算 dp 和 sz
dp[u] -= dp[v] + sz[v];
sz[u] -= sz[v];
dp[v] += dp[u] + sz[u];
sz[v] += sz[u];
dfs2(v, u); // 递归处理子节点
// 恢复 dp 和 sz 的值
dp[u] = pu, dp[v] = pv;
sz[u] = su, sz[v] = sv;
}
}
public:
vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {
ret.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);
}
dfs1(0, -1); // 第一次 DFS, 以 0 为根节点
dfs2(0, -1); // 第二次 DFS, 以 0 为根节点
return ret;
}
};
Java
class Solution {
int[] ans, sz, dp; // ans: 结果数组, sz: 子树大小, dp: 子树中所有节点到当前节点的距离和
List<List<Integer>> graph; // 邻接表表示的树
// 第一次 DFS：计算子树大小 sz 和子树中所有节点到当前节点的距离和 dp
private void dfs(int u, int f) {
sz[u] = 1; // 当前节点的子树大小初始化为 1
dp[u] = 0; // 当前节点的距离和初始化为 0
for (int v : graph.get(u)) { // 遍历当前节点的所有邻居
// 跳过父节点
if (v == f) {
continue;
}
dfs(v, u); // 递归处理子节点
dp[u] += dp[v] + sz[v]; // 更新当前节点的距离和
sz[u] += sz[v]; // 更新当前节点的子树大小
}
}
// 第二次 DFS：计算每个节点到其他所有节点的距离和 ans
private void dfs2(int u, int f) {
ans[u] = dp[u]; // 当前节点的距离和即为 dp[u]
for (int v : graph.get(u)) { // 遍历当前节点的所有邻居
// 跳过父节点
if (v == f) {
continue;
}
int pu = dp[u], pv = dp[v]; // 保存当前节点和子节点的 dp 值
int su = sz[u], sv = sz[v]; // 保存当前节点和子节点的 sz 值
// 将当前节点 u 从树中移除，重新计算 dp 和 sz
dp[u] -= dp[v] + sz[v];
sz[u] -= sz[v];
dp[v] += dp[u] + sz[u];
sz[v] += sz[u];
dfs2(v, u); // 递归处理子节点
// 恢复 dp 和 sz 的值
dp[u] = pu;
dp[v] = pv;
sz[u] = su;
sz[v] = sv;
}
}
public int[] sumOfDistancesInTree(int n, int[][] edges) {
ans = new int[n]; // 初始化结果数组
sz = new int[n]; // 初始化子树大小数组
dp = new int[n]; // 初始化距离和数组
graph = new ArrayList<>(); // 初始化邻接表
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) { // 构建邻接表
int u = edge[0], v = edge[1];
graph.get(u).add(v);
graph.get(v).add(u);
}
dfs(0, -1); // 第一次 DFS，以 0 为根节点
dfs2(0, -1); // 第二次 DFS，以 0 为根节点
return ans; // 返回结果
}
}
Python
class Solution:
def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
self.ans = [0] * n # 结果数组
self.sz = [0] * n # 子树大小数组
self.dp = [0] * n # 子树中所有节点到当前节点的距离和
self.graph = [[] for _ in range(n)] # 邻接表表示的树
# 构建邻接表
for u, v in edges:
self.graph[u].append(v)
self.graph[v].append(u)
# 第一次 DFS：计算子树大小 sz 和子树中所有节点到当前节点的距离和 dp
def dfs(u, f):
self.sz[u] = 1 # 当前节点的子树大小初始化为 1
self.dp[u] = 0 # 当前节点的距离和初始化为 0
for v in self.graph[u]: # 遍历当前节点的所有邻居
if v == f: continue # 跳过父节点
dfs(v, u) # 递归处理子节点
self.dp[u] += self.dp[v] + self.sz[v] # 更新当前节点的距离和
self.sz[u] += self.sz[v] # 更新当前节点的子树大小
# 第二次 DFS：计算每个节点到其他所有节点的距离和 ans
def dfs2(u, f):
self.ans[u] = self.dp[u] # 当前节点的距离和即为 dp[u]
for v in self.graph[u]: # 遍历当前节点的所有邻居
if v == f: continue # 跳过父节点
pu, pv = self.dp[u], self.dp[v] # 保存当前节点和子节点的 dp 值
su, sv = self.sz[u], self.sz[v] # 保存当前节点和子节点的 sz 值
# 将当前节点 u 从树中移除，重新计算 dp 和 sz
self.dp[u] -= self.dp[v] + self.sz[v]
self.sz[u] -= self.sz[v]
self.dp[v] += self.dp[u] + self.sz[u]
self.sz[v] += self.sz[u]
dfs2(v, u) # 递归处理子节点
# 恢复 dp 和 sz 的值
self.dp[u], self.dp[v] = pu, pv
self.sz[u], self.sz[v] = su, sv
dfs(0, -1) # 第一次 DFS，以 0 为根节点
dfs2(0, -1) # 第二次 DFS，以 0 为根节点
return self.ans # 返回结果
4、复杂度分析
- 时间复杂度：
- 两次 DFS 遍历所有节点和边，时间复杂度为 O(n)。
- 空间复杂度：
使用邻接表存储树，空间复杂度为 O(n)。
pu, pv = self.dp[u], self.dp[v] # 保存当前节点和子节点的 dp 值
su, sv = self.sz[u], self.sz[v] # 保存当前节点和子节点的 sz 值# 将当前节点 u 从树中移除，重新计算 dp 和 sz self.dp[u] -= self.dp[v] + self.sz[v] self.sz[u] -= self.sz[v] self.dp[v] += self.dp[u] + self.sz[u] self.sz[v] += self.sz[u] dfs2(v, u) # 递归处理子节点 # 恢复 dp 和 sz 的值 self.dp[u], self.dp[v] = pu, pv self.sz[u], self.sz[v] = su, svdfs(0, -1) # 第一次 DFS，以 0 为根节点
dfs2(0, -1) # 第二次 DFS，以 0 为根节点
return self.ans # 返回结果
#### 4、复杂度分析
1. **时间复杂度**：
- 两次 DFS 遍历所有节点和边，时间复杂度为 O(n)。
2. **空间复杂度**：
- 使用邻接表存储树，空间复杂度为 O(n)。
<br>
<br>