每日一题
题目
870. 优势洗牌 难度：medium
给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。
返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。
示例 1：
代码语言：javascript复制输入： nums1 = [2,7,11,15], nums2 = [1,10,4,11]
输出： [2,11,7,15]示例 2：
代码语言：javascript复制输入： nums1 = [12,24,8,32], nums2 = [13,25,32,11]
输出： [24,32,8,12]提示：
1 <= nums1.length <= 10^5nums2.length == nums1.length0 <= nums1[i], nums2[i] <= 10^9
方法一：贪心
思路
根据题意，要使得优势最大化，就要有尽可能多的优势，其实就是 “田忌赛马”；
我们首先分别将数组 nums1 和 nums2 进行排序，随后只需要不断考虑这两个数组的首个元素：
- 如果
nums1的首个元素大于nums2的首个元素，那么就将它们在答案中对应起来，同时从数组中移除这两个元素，并增加一点「优势」； - 如果
nums1的首个元素小于等于nums2的首个元素，那么移除nums1的首个元素。
当 nums1 中没有元素时，遍历结束。
解题
Python：
代码语言：javascript复制class Solution:
def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
n = len(nums1)
idx1, idx2 = list(range(n)), list(range(n))
idx1.sort(key=lambda x: nums1[x])
idx2.sort(key=lambda x: nums2[x])
ans = [0] * n
left, right = 0, n - 1
for i in range(n):
if nums1[idx1[i]] > nums2[idx2[left]]:
ans[idx2[left]] = nums1[idx1[i]]
left = 1
else:
ans[idx2[right]] = nums1[idx1[i]]
right -= 1
return ansJava：
代码语言：javascript复制class Solution {
public int[] advantageCount(int[] nums1, int[] nums2) {
int n = nums1.length;
Integer[] idx1 = new Integer[n];
Integer[] idx2 = new Integer[n];
for (int i = 0; i < n; i) {
idx1[i] = i;
idx2[i] = i;
}
Arrays.sort(idx1, (i, j) -> nums1[i] - nums1[j]);
Arrays.sort(idx2, (i, j) -> nums2[i] - nums2[j]);
int[] ans = new int[n];
int left = 0, right = n - 1;
for (int i = 0; i < n; i) {
if (nums1[idx1[i]] > nums2[idx2[left]]) {
ans[idx2[left]] = nums1[idx1[i]];
left;
} else {
ans[idx2[right]] = nums1[idx1[i]];
--right;
}
}
return ans;
}
}
733. 图像渲染
题目
733. 图像渲染 难度：easy
有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。
你也被给予三个整数 sr , sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。
为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，…，重复该过程。将所有有记录的像素点的颜色值改为 newColor 。
最后返回 经过上色渲染后的图像 。
示例 1:
输入: image = [[1,1,1],[1,1,0],[1,0,1]]，sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析: 在图像的正中间，(坐标(sr,sc)=(1,1)),在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，因为它不是在上下左右四个方向上与初始点相连的像素点。示例 2:
代码语言：javascript复制输入: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2
输出: [[2,2,2],[2,2,2]]提示:
m == image.lengthn == image[i].length1 <= m, n <= 500 <= image[i][j], newColor < 2^160 <= sr < m0 <= sc < n
方法一：BFS
思路
我们从给定的起点开始，进行广度优先搜索。每次搜索到一个方格时，如果其与初始位置的方格颜色相同，就将该方格加入队列，并将该方格的颜色更新，以防止重复入队。
注意：因为初始位置的颜色会被修改，所以我们需要保存初始位置的颜色，以便于之后的更新操作。
解题
Python：
代码语言：javascript复制class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
currColor = image[sr][sc]
if currColor == color:
return image
n, m = len(image), len(image[0])
que = collections.deque([(sr, sc)])
image[sr][sc] = color
while que:
x, y = que.popleft()
for mx, my in [(x - 1, y), (x 1, y), (x, y - 1), (x, y 1)]:
if 0 <= mx < n and 0 <= my < m and image[mx][my] == currColor:
que.append((mx, my))
image[mx][my] = color
return imageJava：
代码语言：javascript复制class Solution {
int[] dx = {1, 0, 0, -1};
int[] dy = {0, 1, -1, 0};
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
int currColor = image[sr][sc];
if (currColor == color) {
return image;
}
int n = image.length, m = image[0].length;
Queue<int[]> queue = new LinkedList<int[]>();
queue.offer(new int[]{sr, sc});
image[sr][sc] = color;
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int x = cell[0], y = cell[1];
for (int i = 0; i < 4; i ) {
int mx = x dx[i], my = y dy[i];
if (mx >= 0 && mx < n && my >= 0 && my < m && image[mx][my] == currColor) {
queue.offer(new int[]{mx, my});
image[mx][my] = color;
}
}
}
return image;
}
}
方法二：DFS
思路
我们从给定的起点开始，进行深度优先搜索。每次搜索到一个方格时，如果其与初始位置的方格颜色相同，就将该方格的颜色更新，以防止重复搜索；如果不相同，则进行回溯。
注意：因为初始位置的颜色会被修改，所以我们需要保存初始位置的颜色，以便于之后的更新操作。
解题
Python：
代码语言：javascript复制class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
n, m = len(image), len(image[0])
currColor = image[sr][sc]
def dfs(x: int, y: int):
if image[x][y] == currColor:
image[x][y] = color
for mx, my in [(x - 1, y), (x 1, y), (x, y - 1), (x, y 1)]:
if 0 <= mx < n and 0 <= my < m and image[mx][my] == currColor:
dfs(mx, my)
if currColor != color:
dfs(sr, sc)
return imageJava：
代码语言：javascript复制class Solution {
int[] dx = {1, 0, 0, -1};
int[] dy = {0, 1, -1, 0};
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
int currColor = image[sr][sc];
if (currColor != color) {
dfs(image, sr, sc, currColor, color);
}
return image;
}
public void dfs(int[][] image, int x, int y, int currColor, int color) {
if (image[x][y] == currColor) {
image[x][y] = color;
for (int i = 0; i < 4; i ) {
int mx = x dx[i], my = y dy[i];
if (mx >= 0 && mx < image.length && my >= 0 && my < image[0].length) {
dfs(image, mx, my, currColor, color);
}
}
}
}
}
200. 岛屿数量
题目
200. 岛屿数量 难度：medium
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
代码语言：javascript复制输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1示例 2：
代码语言：javascript复制输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]的值为'0'或'1'
方法一：BFS
思路
为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 11，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 11 都会被重新标记为 00。直到队列为空，搜索结束。
最终岛屿的数量就是我们进行广度优先搜索的次数。
解题
Python：
代码语言：javascript复制class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
num_islands = 0
for r in range(nr):
for c in range(nc):
if grid[r][c] == "1":
num_islands = 1
grid[r][c] = "0"
neighbors = collections.deque([(r, c)])
while neighbors:
row, col = neighbors.popleft()
for x, y in [(row - 1, col), (row 1, col), (row, col - 1), (row, col 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
neighbors.append((x, y))
grid[x][y] = "0"
return num_islandsJava：
代码语言：javascript复制class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; r) {
for (int c = 0; c < nc; c) {
if (grid[r][c] == '1') {
num_islands;
grid[r][c] = '0';
Queue<Integer> neighbors = new LinkedList<>();
neighbors.add(r * nc c);
while (!neighbors.isEmpty()) {
int id = neighbors.remove();
int row = id / nc;
int col = id % nc;
if (row - 1 >= 0 && grid[row-1][col] == '1') {
neighbors.add((row-1) * nc col);
grid[row-1][col] = '0';
}
if (row 1 < nr && grid[row 1][col] == '1') {
neighbors.add((row 1) * nc col);
grid[row 1][col] = '0';
}
if (col - 1 >= 0 && grid[row][col-1] == '1') {
neighbors.add(row * nc col-1);
grid[row][col-1] = '0';
}
if (col 1 < nc && grid[row][col 1] == '1') {
neighbors.add(row * nc col 1);
grid[row][col 1] = '0';
}
}
}
}
}
return num_islands;
}
}
方法二：DFS
思路
我们可以将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。
为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。
最终岛屿的数量就是我们进行深度优先搜索的次数。
解题
Python：
代码语言：javascript复制class Solution:
def dfs(self, grid, r, c):
grid[r][c] = 0
nr, nc = len(grid), len(grid[0])
for x, y in [(r - 1, c), (r 1, c), (r, c - 1), (r, c 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
self.dfs(grid, x, y)
def numIslands(self, grid: List[List[str]]) -> int:
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
num_islands = 0
for r in range(nr):
for c in range(nc):
if grid[r][c] == "1":
num_islands = 1
self.dfs(grid, r, c)
return num_islandsJava：
代码语言：javascript复制class Solution {
void dfs(char[][] grid, int r, int c) {
int nr = grid.length;
int nc = grid[0].length;
if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
return;
}
grid[r][c] = '0';
dfs(grid, r - 1, c);
dfs(grid, r 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c 1);
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; r) {
for (int c = 0; c < nc; c) {
if (grid[r][c] == '1') {
num_islands;
dfs(grid, r, c);
}
}
}
return num_islands;
}
}
以上就是 【算法题解】 Day10 BFS | DFS 的所有内容了，创作不易，多多支持
