LeetCode刷题笔记

蔚落 2023-06-05 12:39 2阅读 0赞

## [23. Merge k Sorted Lists][] ##

> 要点：
> 
> 1. 学会数据结构PriorityQueue（优先队列）的用法， 通过给优先队列传入自定义的经过复写compare方法的比较器实现大根堆或者小根堆。
> 
> 2. PriorityQueue中不能存放null值，所以每次更新优先队列都需要作判空检查，如遇null值直接剔除。

1 import java.util.Comparator;
     2 import java.util.PriorityQueue;
     3 
     4 class Solution {
     5     public ListNode mergeKLists(ListNode[] lists) {
     6         //要点1
     7         PriorityQueue<ListNode> nodesQueue = new PriorityQueue<>(new Comparator<ListNode>() {
     8             @Override
     9             //将compare方法重写为比较ListNode的val值大小
    10             public int compare(ListNode o1, ListNode o2) {
    11                 return o1.val-o2.val;
    12             }
    13         });
    14 
    15         ListNode head = new ListNode(0);
    16         for(ListNode node:lists)
    17             if(node!=null)
    18                 nodesQueue.add(node);
    19 
    20         ListNode p = head;
    21         while(!nodesQueue.isEmpty()){
    22             //判空检查，如果ListNode的下一个Node是null，则取出该Node后不再将其下一个节点放回优先队列。
    23             if(nodesQueue.peek().next==null){
    24                 p.next = new ListNode(nodesQueue.poll().val);
    25                 p = p.next;
    26             }else{
    27                 ListNode tmp = nodesQueue.poll();
    28                 p.next = new ListNode(tmp.val);
    29                 p = p.next;
    30                 nodesQueue.add(tmp.next);
    31             }
    32         }
    33         return head.next;
    34     }
    35 
    36 }

## [29. Divide Two Integers][] ##

class Solution {
        //用dividend循环减去diviso并计数减了多少次，这种方法会tle
        public static int divide(int dividend, int divisor) {
            //处理两种溢出情况
            if(dividend == -2147483648){
                if(divisor == 1)
                    return -2147483648;
                if(divisor == -1)
                    return 2147483647;
            }
            /**
               32位整数的取值范围是-2147483648~+2147483647
               将两个数都转为负数，以处理最大溢出-2147483648
            */
            
            //保存符号
            int flag = 1;
            if((dividend>0&&divisor<0)||(dividend<0&&divisor>0))
                flag = -1;
            //都转为负数
            dividend = dividend>0?-dividend:dividend;
            divisor = divisor>0?-divisor:divisor;
            int res = 0;
            if(dividend>divisor)
                return 0;
            //开始循环取商
            while(dividend<0){
                int k = 1;
                //divisor_tmp是变量，只要比dividend小就每次加倍，同时k作为商的计数也加倍
                int divisor_tmp = divisor;
                int tmp=0;
                while(dividend<divisor_tmp){
                    tmp = divisor_tmp;
                    //divisor_tmp在加倍的过程中有可能溢出，需要处理
                    if(divisor_tmp+divisor_tmp>0||divisor_tmp+divisor_tmp==-2147483648)
                        break;
                    divisor_tmp += divisor_tmp;
                    k += k;
                }
                //如果跳出加倍循环后，dividend比divisor_tmp大，说明divisor_tmp加倍超过了dividend，需要撤销上一次的加倍
                if(dividend>divisor_tmp){
                    divisor_tmp -= tmp;
                    k>>=1;
                }
                //从divideng减去divisor_tmp并保存加倍值
                dividend -= divisor_tmp;
                res += k;
            }
            return res*flag;
        }
    
    }

## [32. Longest Valid Parentheses][] ##

> 连同下面的解释，参考自 https://www.acwing.com/solution/LeetCode/content/114/
> 
> ### 算法 ###
> 
> (双指针扫描、贪心) O(n)O(n)  
> 假设当前从前到后统计合法括号子串，令(的权值为1，)的权值为-1。首先记录start为某个起点，则在i向后移动的过程中，若当前\[start,i\]区间和等于0，该字符串是合法的；若区间和大于0，则说明目前缺少右括号，可以不修改start；若区间和小于0，则说明区间已经不合法了，需要修正start为i+1。初始时start从0开始即可。  
> 可是对于…((((合法)(((这种情况，以上算法不能够准确捕捉到最长的合法子串，此时我们逆向考虑，将以上过程反向，从后向前统计，即可处理所有的情况。
> 
> ### 时间复杂度 ###
> 
> 两次线性扫描，故时间复杂度为O(n)O(n)。

class Solution {
        public int longestValidParentheses(String s) {
           char[] chars = s.toCharArray();
            int[] marks = new int[chars.length];
            for(int i=0; i<chars.length;i++)
                marks[i] = chars[i]=='('?1:-1;
    
            int pr = 0;
            int pl = 0;
            int distance = 0;
            int tmp = 0;
            while(pr<marks.length){
                tmp+=marks[pr];
                if(tmp<0){
                    tmp = 0;
                    pl = pr+1;
                }
                if(tmp == 0)
                    distance = pr-pl+1>distance?pr-pl+1:distance;
                pr++;
            }
    
            pr = marks.length-1;
            pl = pr;
            tmp = 0;
            while(pl>=0){
                tmp += marks[pl] ;
                if(tmp>0) {
                    tmp = 0;
                    pr = pl-1;
                }
                if(tmp == 0)
                    distance = pr-pl+1>distance?pr-pl+1:distance;
    
                pl--;
            }
            return distance;
        }
    }

## [554. Brick Wall][] ##

> 这是在FreeWheel面试中遇到的一道题目，思考一下题目并不难。
> 
> 穿过最少砖的直线肯定是穿过缝隙最多的线，所以可以遍历整个List，获取每一行每条缝隙对应的砖宽， 将砖宽度和砖宽度出现的次数存入Map，最后遍历map获取出现次数最多的宽度，总行数-出现次数即为结果。
> 
> 要注意几个边界条件：
> 
> 1. 如果每行都只有一块相同长度的砖块,（例如输入为:\[\[1\]\[1\]\[1\]\]），则任何划线方式在每行都会穿过一块砖，注意题目说明了不能在墙的左右边界划线；
> 
> 2. 只要有任意一行出现了两块以及两块以上的砖，则至少可以穿越一条砖缝。
> 
>     import java.util.*;
>         class Solution {
>             public int leastBricks(List<List<Integer>> wall) {
>                 Map<Integer, Integer> map = new HashMap<>();
>                 int max = 1;//初始为1，如果不是出现了[[1][1][1]]的输入，则至少能穿越一个缝隙
>                 boolean flag = true;//此标志就是为了判断是否出现了[[1][1][1]]的输入
>                 for(List list: wall){
>                     int tmp = 0;
>                     if(list.size()>1)//只要有任意一行砖块的数量超过1块，则不可能是类似于[[1][1][1]]的输入
>                         flag = false;
>     //统计每个砖缝出现的位置，在砖缝出现位置最多的地方划线即可
>                     for(int i = 0; i<list.size()-1; i++){
>                         tmp+=(Integer)list.get(i);
>                         if(!map.containsKey(tmp))
>                             map.put(tmp,1);
>                         else{
>                             int cnt = map.get(tmp)+1;
>                             map.put(tmp, cnt);
>                             max = cnt>max?cnt:max;
>                         }
>                     }
>                 }
>                 if(!flag)
>                     return wall.size()-max;
>                 else 
>                     return wall.size();
>             }
>         }

深度优先搜索专题

## [130. 被围绕的区域][130.] ##

先用dfs把跟边缘相连的‘O’标记为'\#', 这样剩下的‘O’都是被围绕的区域。再遍历这个二维字符数组，把所有的'O'换为‘X’， 所有的'\#'换回'O'

class Solution {
        public void solve(char[][] board) {
         
    //行数或者列数小于等于2的矩阵所有的元素都在边上
            if(board == null||board.length<3||board[0].length<3)
                return;
    //用dfs将所有的'O'标记为'#'
            for(int i = 0; i < board.length; i++){
                for(int j = 0; j<board[0].length;j++){
                    boolean isEdge = (i==0 || j==0 || i==board.length-1 || j==board[0].length-1 );
                    if(isEdge && board[i][j] == 'O'){
                        dfs(board, i, j);
                    }
                }
            }
    //把所有的'O'换为‘X’， 所有的'#'换回'O'
            for(int i = 0; i < board.length; i++){
                for(int j = 0; j<board[0].length;j++){
                    if(board[i][j] == 'O')
                        board[i][j] = 'X';
                    if(board[i][j] == '#')
                        board[i][j] = 'O';
                }
            }
        }
        
    //dfs深度优先遍历
        void dfs(char[][] board, int i, int j){
            if(i<0||i>=board.length||j<0||j>=board[0].length||board[i][j]=='X'||board[i][j]=='#')
                return;
            board[i][j] = '#';
            dfs(board, i-1, j);
            dfs(board, i+1, j);
            dfs(board, i, j-1);
            dfs(board, i, j+1);
        }
    
    }

**DFS使用栈来把递归转为循环**

非递归的方式，我们需要记录每一次遍历过的位置，我们用 `stack` 来记录，因为它先进后出的特点。

class Solution {
        public void solve(char[][] board) {
            //棋盘的行数或者列数小于3的时候所有的元素都是边上的元素
            if (board == null || board.length < 3 || board[0].length < 3) return;
            int m = board.length;
            int n = board[0].length;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 从边缘第一个是o的开始搜索
                    boolean isEdge = (i == 0 || j == 0 || i == m - 1 || j == n - 1);
                    if (isEdge && board[i][j] == 'O') {
                        dfs(board, i, j);
                    }
                }
            }
    
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 'O') {
                        board[i][j] = 'X';
                    }
                    if (board[i][j] == '#') {
                        board[i][j] = 'O';
                    }
                }
            }
        }
        
        public void dfs(char[][] board, int i, int j) {
            int[] dx = {-1, 0, 1, 0};
            int[] dy = {0, 1, 0, -1};
            Stack<int[]> stack = new Stack<>();
            stack.push(new int[]{i,j});
            board[i][j] = '#';
            while (!stack.isEmpty()) {
                int[] current = stack.pop();
                for(int k = 0; k<4; k++){
                    int x = current[0] + dx[k];
                    int y = current[1] + dy[k];
                    if(x>0 && x<board.length && y>0 && y<board[0].length && board[x][y] == 'O'){
                        board[x][y] = '#';
                        stack.push(new int[]{x, y});
                    }
                }
            }
        }
    }

与本题及其类似的零一道题:

## [200. Number of Islands][] ##

class Solution {
        public int numIslands(char[][] grid) {
            if(grid == null || grid.length == 0 || (grid.length == 1 && grid[0] == null))
                return 0;
            int cnt = 0;
            for(int i = 0; i<grid.length; i++){
                for(int j = 0; j<grid[0].length; j++){
                    if(grid[i][j] == '1'){
                        cnt++;
                        //用深搜将所有与(i, j)相连的1都变为0
                        dfs(grid, i, j);
                    }
                }
            }
            return cnt;
        }
        
        int[][] d = {
        {-1, 0},{0, 1},{1, 0},{0, -1}};
        void dfs(char[][] grid, int i, int j){
            if(i>=0 && i< grid.length && j>=0 && j<grid[0].length && grid[i][j] == '1'){
                grid[i][j] = '0';
                for(int k = 0; k < 4; k++){
                    int x = i + d[k][0];
                    int y = j + d[k][1];
                    dfs(grid, x, y);
                }
                return;
            }
            return;
        }
    }

## [329. Longest Increasing Path in a Matrix][] ##

朴素dfs, 暴力深搜，TLE

package 搜索与遍历_BFS_DFS_树和图的遍历.DFS.leetcode深搜题.leetCode329;
    
    public class leetcode329Longest_Increasing_Path_in_a_Matrix_朴素DFS {
        int m, n;
        int[][] dirs = {
        {-1, 0}, {0, 1,}, {1, 0}, {0, -1}};
    
        public int longestIncreasingPath(int[][] matrix) {
            if (matrix == null || matrix.length == 0 || (matrix.length == 1 && matrix[0].length == 0))
                return 0;
            m = matrix.length;
            n = matrix[0].length;
            int ans = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    ans = Math.max(ans, dfs(i, j, matrix));
                }
            }
            return ans;
        }
    
    
        int dfs(int i, int j, int[][] matrix) {
            int res = 0;
            for (int[] d : dirs) {
                int x = i + d[0];
                int y = j + d[1];
                if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
                    res = Math.max(res, dfs(x, y, matrix));
                }
            }
            return ++res;
        }
    }

记忆化搜索， accpet:

class Solution {
        int m, n;
        int[][] dirs = {
        {-1,0},{0,1,},{1,0},{0,-1}};
        public int longestIncreasingPath(int[][] matrix) {
            if(matrix == null || matrix.length == 0 || (matrix.length == 1 && matrix[0].length == 0))
                return 0;
            m = matrix.length;
            n = matrix[0].length;
            int[][] cache = new int[m][n];
            int ans = 0;
            for(int i = 0; i<m; i++){
                for(int j = 0; j<n; j++){
                    ans = Math.max(ans,dfs(i, j, matrix,cache));
                }
            }
            return ans;
        }
        
    
        int dfs(int i, int j, int[][] matrix, int[][] cache){
            if(cache[i][j] != 0)
                return cache[i][j];
            for(int[] d :  dirs){
                int x = i + d[0];
                int y = j + d[1];
                if(x>=0 && x<m&&y>=0&&y<n&&matrix[x][y]>matrix[i][j]){
                    cache[i][j] = Math.max(cache[i][j], dfs(x,y,matrix,cache));
                }
            }
            return ++cache[i][j];
        }
    }

## [695. Max Area of Island][] ##

package 搜索与遍历_BFS_DFS_树和图的遍历.DFS.leetcode深搜题;
    
    public class leetCode695Max_Area_of_Island {
        int[][] dirs = {
        {-1,0},{0,1},{1,0},{0,-1}};
        int m, n;
        public int maxAreaOfIsland(int[][] grid) {
            if(grid == null || grid.length == 0 || (grid.length == 1 && grid[0].length == 0))
                return 0;
            m = grid.length;
            n = grid[0].length;
            //boolean[][] visited = new boolean[m][n];
            int max = 0;
            for(int i = 0; i<m; i++){
                for(int j = 0; j<n; j++){
                    if(grid[i][j] == 1)
                        max = Math.max(max, dfs(i, j, grid));
                }
            }
            return max;
        }
    
        int dfs(int i, int j, int[][] grid){
            grid[i][j] = 0;
            int res = 0;
            for(int[] d:dirs){
                int x = i+d[0];
                int y = j+d[1];
                if(x>=0 && x<m && y>=0 && y<n && grid[x][y] == 1){
                    res += dfs(x, y, grid);
                }
            }
            return ++res;
        }
    }

并查集专题

# 两道并查集 #

## [547. Friend Circles][] ##

## [200. Number of Islands][] ##

# LintCode #

## [386. 最多有k个不同字符的最长子字符串][386._k] ##

> ### 描述 ###
> 
> 给定字符串*S*，找到最多有k个不同字符的最长子串*T*。
> 
> 样例
> 
> 样例 1:
> 
>     输入: S = "eceba" 并且 k = 3
>     输出: 4
>     解释: T = "eceb"
> 
> 样例 2:
> 
>     输入: S = "WORLD" 并且 k = 4
>     输出: 4
>     解释: T = "WORL" 或 "ORLD"
> 
> ### 挑战 ###
> 
> O(n) 时间复杂度

public static int lengthOfLongestSubstringKDistinct(String s, int k) {
            // write your code here
            int result = 0;
            int left = 0;
            //声明一个HashMap，用来存储k Distinct，还可以根据value用来判断元素是否可以删除
            HashMap<Character, Integer> map = new HashMap<>();
            for (int right = 0; right < s.length(); right++) {
                //右指针依次把字符串中的字符放到map中
                map.put(s.charAt(right),right);
                //当map元素大于k Distinct时，得到满足要求的子字符串
                while (map.size() > k) {
                    // 删除最左的字符，删除成功，则退出循环
                    char leftChar = s.charAt(left);
                    //如果map.get(leftChar) == left条件成立，则说明leftChar从一开始
                    //在left位置被添加到map中去后就没有更新过, 对应leftChar的下标还是
                    //left, 如果在第一次被加到left位置之后，后面又出现了这个元素，则这个
                    //map.get(leftChar)时得到的是最新添加该元素的下标；
                    //在移动左指针的时候，如果这个元素在left和right之间只出现了一次，就要 
                    //从map的统计中去掉。
                    if (map.get(leftChar) == left) {
                        map.remove(leftChar);
                    }
                    // 左指针右移
                    left++;
                }
                //子结果即左右指针之间的长度
                int subResult = right - left + 1;
                //结果取最大
                result = Math.max(result,subResult);
            }
            return result;
        }

简单题专题

## [463. Island Perimeter][] ##

package 刷题;
    
    public class Solution463 {
        int m, n;
        public int islandPerimeter(int[][] grid) {
            if(grid==null || grid.length==0 || (grid.length == 1 && grid[0].length== 0))
                return 0;
            m = grid.length;
            n = grid[0].length;
            int res = 0;
            for(int i = 0; i<m; i++){
                for(int j = 0; j<n; j++){
                    if(grid[i][j] == 1)
                        res += find(i, j, grid);
                }
            }
            return res;
        }
    
        int find(int i, int j, int[][] grid){
            int res = 0;
            if(i-1<0 || grid[i-1][j] == 0)
                res++;
            if(i+1>=m || grid[i+1][j] == 0)
                res++;
            if(j-1<0 || grid[i][j-1] == 0)
                res++;
            if(j+1>=n || grid[i][j+1] == 0)
                res++;
            return res;
        }
    }

## [733. Flood Fill][] ##

package 刷题;
    
    public class Solution733 {
        int m, n;
        int[][] dirs = {
                 {-1,0},{0,1},{1,0},{0,-1}};
        public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
            if(image==null || image.length==0 || (image.length==1 && image[0].length == 0))
                return image;
            m = image.length;
            n = image[0].length;
            int oldColor = image[sr][sc];
            if(sr<0 || sr>m || sc<0 || sc>n || oldColor == newColor)
                return image;
            dfs(image, sr, sc, newColor, oldColor);
            return image;
        }
    
        void dfs(int[][] image, int sr, int sc, int newColor, int oldColor){
            if(sr<0 || sr>=m || sc<0 || sc>=n || image[sr][sc]!=oldColor)
                return;
            image[sr][sc] = newColor;
            for(int[] d : dirs){
                dfs(image, sr+d[0], sc+d[1],newColor, oldColor);
            }
            return;
        }
    }

## [104. Maximum Depth of Binary Tree][] ##

class Solution {
                  public int maxDepth(TreeNode root) {
            if(root==null)
                return 0;
            return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
        }
    }

## [111. Minimum Depth of Binary Tree][] ##

class Solution {
    //很多人写出的代码都不符合 1,2 这个测试用例，是因为没搞清楚题意
    
    //题目中说明:叶子节点是指没有子节点的节点，这句话的意思是 1 不是叶子节点
    
    //题目问的是到叶子节点的最短距离，所以所有返回结果为 1 当然不是这个结果
    
        public int minDepth(TreeNode root) {
            if(root == null)
                return 0;
            if(root.left==null && root.right == null)
                return 1;
            if(root.left == null)
                return minDepth(root.right)+1;
            if(root.right == null)
                return minDepth(root.left)+1;
            else
                return Math.min(minDepth(root.left),minDepth(root.right))+1;
        }
    }

转载于:https://www.cnblogs.com/greatLong/p/11369523.html

[23. Merge k Sorted Lists]: https://leetcode-cn.com/problems/merge-k-sorted-lists/
[29. Divide Two Integers]: https://leetcode-cn.com/problems/divide-two-integers/
[32. Longest Valid Parentheses]: https://leetcode-cn.com/problems/longest-valid-parentheses/
[554. Brick Wall]: https://leetcode-cn.com/problems/brick-wall/
[130.]: https://leetcode-cn.com/problems/surrounded-regions/
[200. Number of Islands]: https://leetcode-cn.com/problems/number-of-islands/
[329. Longest Increasing Path in a Matrix]: https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/
[695. Max Area of Island]: https://leetcode-cn.com/problems/max-area-of-island/
[547. Friend Circles]: https://leetcode-cn.com/problems/friend-circles/
[386._k]: https://www.lintcode.com/problem/longest-substring-with-at-most-k-distinct-characters/leaderboard
[463. Island Perimeter]: https://leetcode-cn.com/problems/island-perimeter/
[733. Flood Fill]: https://leetcode-cn.com/problems/flood-fill/
[104. Maximum Depth of Binary Tree]: https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
[111. Minimum Depth of Binary Tree]: https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/