排序+滑动窗口
java版本
import java.util.Arrays;
class Solution {
public int minimumDifference(int[] nums, int k) {
Arrays.sort(nums);
// 选取k个
k=k-1;
int n=nums.length;
if(k==0 || n==0){
return 0;
}
int res=nums[k]-nums[0];
for(int i=0;i<n-k;i++){
res=Math.min(nums[i+k]-nums[i],res);
}
return res;
}
}
- 飞地的数量
DFS 注意,尽量返回结果的res尽量写在递归函数外面。
java版本:
class Solution {
public static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private int m, n;
private boolean[][] visited;
public int numEnclaves(int[][] grid) {
m = grid.length;
n = grid[0].length;
visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
dfs(grid, i, 0);
dfs(grid, i, n - 1);
}
for (int j = 1; j < n - 1; j++) {
dfs(grid, 0, j);
dfs(grid, m - 1, j);
}
int enclaves = 0;
for (int i = 1; i < m - 1; i++) {
for (int j = 1; j < n - 1; j++) {
if (grid[i][j] == 1 && !visited[i][j]) {
enclaves++;
}
}
}
return enclaves;
}
public void dfs(int[][] grid, int row, int col) {
if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == 0 || visited[row][col]) {
return;
}
visited[row][col] = true;
for (int[] dir : dirs) {
dfs(grid, row + dir[0], col + dir[1]);
}
}
}
网友评论