刷题练习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);
    }
}