刷题练习2021-12-16
动态规划:42. 接雨水
class Solution {
public int trap(int[] height) {
int result = 0;
for(int i=0;i<height.length;i++) {
int left = i-1;
int right = i+1;
int maxLeft = 0;
int maxRight = 0;
while(left>=0) {
maxLeft = Math.max(maxLeft,height[left]);
left--;
}
while(right<height.length) {
maxRight = Math.max(maxRight,height[right]);
right++;
}
int tmp = Math.min(maxRight,maxLeft)-height[i];
result+=tmp>0?tmp:0;
}
return result;
}
}
记录
class Solution {
public int trap(int[] height) {
int result = 0;
int[] maxLeft = new int[height.length];
int[] maxRight = new int[height.length];
maxLeft[0] = height[0];
maxRight[height.length-1] = height[height.length-1];
for(int i=1;i<height.length;i++) {
maxLeft[i]=Math.max(maxLeft[i-1],height[i]);
}
for(int i=height.length-2;i>=0;i--) {
maxRight[i]=Math.max(maxRight[i+1],height[i]);
}
for(int i=0;i<height.length;i++) {
int tmp = Math.min(maxLeft[i],maxRight[i])-height[i];
result += tmp>0?tmp:0;
}
return result;
}
}
搜索与回溯:
1. 51 N皇后
解答:
class Solution {
private String dotLine="";
public List<List<String>> solveNQueens(int n) {
List<List<String>> result = new LinkedList<>();
for(int i=0;i<n;i++) dotLine+=".";
int[][] marked = new int[n][n];
Deque<String> path = new LinkedList<>();
solveNQueens0(path,result,marked,0);
return result;
}
private void solveNQueens0(Deque<String> path, List<List<String>> result,int[][] marked,int row) {
int n = marked.length;
if(row==n) {
result.add(new LinkedList<>(path));
return;
}
for(int i=0;i<n;i++) {
if(marked[row][i]!=0) continue;
StringBuilder sb = new StringBuilder(dotLine);
sb.replace(i,i+1,"Q");
path.addLast(sb.toString());
markSurouding(marked,row,i,1);
solveNQueens0(path,result,marked,row+1);
markSurouding(marked,row,i,-1);
path.pollLast();
}
}
private void markSurouding(int[][] marked,int i,int j,int state) {
marked[i][j]+=state;
for(int col=0;col<marked.length;col++) {
if(col!=j) marked[i][col]+=state;
}
for(int row=0;row<marked.length;row++) {
if(row!=i) marked[row][j]+=state;
}
int[][] direction = new int[][]{{1,1},{1,-1},{-1,1},{-1,-1}};
for(int k=0;k<4;k++) {
int pos_i = i;
int pos_j = j;
while (true) {
pos_i += direction[k][0];
pos_j+=direction[k][1];
if(pos_j<0||pos_j>=marked.length||pos_i<0||pos_i>=marked.length) {
break;
}
marked[pos_i][pos_j]+=state;
}
}
}
}
2 40. 组合总和 II(排序去重,负target剪枝)
给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
注意:解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
解答:
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> result = new LinkedList<>();
Deque<Integer> path = new LinkedList<>();
combinationSum0(result,candidates,target,path,0);
return result;
}
private void combinationSum0(List<List<Integer>> result,int[] candidates,int target,Deque<Integer> path,int start) {
if(target==0) {
result.add(new LinkedList<>(path));
}
if(target<0) return;
Set<Integer> alreadyRead = new HashSet<>();
for(int i=start;i<candidates.length;i++) {
if(alreadyRead.contains(candidates[i])) continue;
alreadyRead.add(candidates[i]);
path.addLast(candidates[i]);
combinationSum0(result,candidates,target-candidates[i],path,i+1);
path.pollLast();
}
}
}
3 200. 岛屿数量
class Solution {
public int numIslands(char[][] grid) {
int row = grid.length;
int col = grid[0].length;
boolean[][] visited = new boolean[row][col];
int result = 0;
for(int i=0;i<row;i++) {
for(int j=0;j<col;j++) {
result+=search(grid,visited,i,j)?1:0;
}
}
return result;
}
private boolean search(char[][] grid,boolean[][] visited,int i,int j) {
if(i<0||j<0||i>=grid.length||j>=grid[0].length||visited[i][j]||grid[i][j]=='0') return false;
visited[i][j] = true;
search(grid,visited,i+1,j);
search(grid,visited,i,j+1);
search(grid,visited,i,j-1);
search(grid,visited,i-1,j);
return true;
}
}
4 695岛屿的最大面积
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int result = 0;
boolean[][] visited = new boolean[grid.length][grid[0].length];
for(int i=0;i<grid.length;i++) {
for(int j=0;j<grid[0].length;j++) {
result = Math.max(result,helper(grid,visited,i,j));
}
}
return result;
}
private int helper(int[][] grid,boolean[][] visited,int i,int j) {
if(i<0||j<0||i>=grid.length||j>=grid[0].length||visited[i][j]||grid[i][j]==0) return 0;
visited[i][j] = true;
return 1+helper(grid,visited,i+1,j)+helper(grid,visited,i,j+1)+
helper(grid,visited,i-1,j)+helper(grid,visited,i,j-1);
}
}
5 463. 岛屿的周长
class Solution {
public int islandPerimeter(int[][] grid) {
boolean[][] visited = new boolean[grid.length][grid[0].length];
for(int i=0;i<grid.length;i++) {
for(int j=0;j<grid[0].length;j++) {
if(grid[i][j]==1) {
return search(grid,visited,i,j);
}
}
}
return 0;
}
private int search(int[][] grid,boolean[][] visited,int i,int j) {
if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j]==0) return 1;
if(visited[i][j]) return 0;
visited[i][j] = true;
return search(grid,visited,i+1,j)+search(grid,visited,i,j+1)+
search(grid,visited,i-1,j)+search(grid,visited,i,j-1);
}
}