870. 优势洗牌 难度:medium
给定两个大小相等的数组 nums1
和 nums2
,nums1
相对于 nums2
的优势可以用满足 nums1[i] > nums2[i]
的索引 i
的数目来描述。
返回 nums1
的任意排列,使其相对于 nums2
的优势最大化。
示例 1:
输入: nums1 = [2,7,11,15], nums2 = [1,10,4,11]
输出: [2,11,7,15]
示例 2:
输入: nums1 = [12,24,8,32], nums2 = [13,25,32,11]
输出: [24,32,8,12]
提示:
1 <= nums1.length <= 10^5
nums2.length == nums1.length
0 <= nums1[i], nums2[i] <= 10^9
根据题意,要使得优势最大化,就要有尽可能多的优势,其实就是 “田忌赛马”;
我们首先分别将数组 nums1
和 nums2
进行排序,随后只需要不断考虑这两个数组的首个元素:
nums1
的首个元素大于 nums2
的首个元素,那么就将它们在答案中对应起来,同时从数组中移除这两个元素,并增加一点「优势」;nums1
的首个元素小于等于 nums2
的首个元素,那么移除 nums1
的首个元素。当 nums1
中没有元素时,遍历结束。
Python:
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 ans
Java:
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. 图像渲染 难度: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:
输入: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2
输出: [[2,2,2],[2,2,2]]
提示:
m == image.length
n == image[i].length
1 <= m, n <= 50
0 <= image[i][j], newColor < 2^16
0 <= sr < m
0 <= sc < n
我们从给定的起点开始,进行广度优先搜索。每次搜索到一个方格时,如果其与初始位置的方格颜色相同,就将该方格加入队列,并将该方格的颜色更新,以防止重复入队。
注意:因为初始位置的颜色会被修改,所以我们需要保存初始位置的颜色,以便于之后的更新操作。
Python:
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 image
Java:
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;
}
}
我们从给定的起点开始,进行深度优先搜索。每次搜索到一个方格时,如果其与初始位置的方格颜色相同,就将该方格的颜色更新,以防止重复搜索;如果不相同,则进行回溯。
注意:因为初始位置的颜色会被修改,所以我们需要保存初始位置的颜色,以便于之后的更新操作。
Python:
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 image
Java:
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. 岛屿数量 难度:medium
给你一个由 '1'
(陆地)和 '0'
(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
示例 1:
输入:grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出:1
示例 2:
输入:grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出:3
提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j]
的值为 '0'
或 '1'
为了求出岛屿的数量,我们可以扫描整个二维网格。如果一个位置为 11,则将其加入队列,开始进行广度优先搜索。在广度优先搜索的过程中,每个搜索到的 11 都会被重新标记为 00。直到队列为空,搜索结束。
最终岛屿的数量就是我们进行广度优先搜索的次数。
Python:
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_islands
Java:
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;
}
}
我们可以将二维网格看成一个无向图,竖直或水平相邻的 1 之间有边相连。
为了求出岛屿的数量,我们可以扫描整个二维网格。如果一个位置为 1,则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中,每个搜索到的 1 都会被重新标记为 0。
最终岛屿的数量就是我们进行深度优先搜索的次数。
Python:
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_islands
Java:
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 的所有内容了,创作不易,多多支持 👍👍👍 我是 𝓼𝓲𝓭𝓲𝓸𝓽,期待你的关注 💖💖💖 🔥 系列专栏: 算法题解