算法-leetcode总结

本文详细介绍了leetcode相关分类与解法。

核心分类

一维数组

二维矩阵

排序

快排

归并排序

二分搜索

满足：单调性、搜索结果收敛，注意上界和下界

搜索插入的位置

/**
 * 35
 * 测试用例
 * [1] 1,0,2
 * [1,4] 2,0,5
 * return l 或 h+1
 */
public class SearchInsert35 {

    public static int searchInsert(int[] nums, int target) {

        int l = 0;
        int h = nums.length - 1;

        while (l <= h) {
            int middle = l + ( h-l) / 2;
            if (nums[middle] > target) {
                h = middle - 1;
            } else if (nums[middle] < target) {
                l = middle + 1;
            } else if (nums[middle] == target) {
                return middle;
            }
        }

        return l;
    }
}

X的平方根

/**
 * leetcode 69
 * 时间复杂度 O(Log(N)) 空间复杂度 O(1)
 */
public int mySqrt(int x) {
        long l = 0;
        long h = x;
        long r = l;
        while(l<=h){
            long mid = l + (h-l)/2;
            if(mid*mid==x){
                return (int) mid;
            }else if(mid*mid<x){
                r = mid;
                l = mid+1;
            }else {
                h = mid-1;
            }
        }

        return (int) r;
    }

pow(x,n) 递归进行计算

在旋转排序数组中寻找最小值

/**
 * 153
 * 寻找旋转数组最小值
 * [1]
 * [2,1]
 * [2,3,1]
 * 返回nums[l] nums[h] 都可以
 */
public class FindMinRotateArray153 {

    public static int findMin(int[] nums) {

        int l=0;
        int h= nums.length-1;

        while(l<h){
            int mid = l + (h-l)/2;
            if(nums[mid]>nums[h]){
                l = mid+1;
            }else {
                h = mid;
            }
        }

        return nums[l];
    }
}

在旋转数组中寻找target值

public int search(int[] nums, int target) {
    
    int l = 0;
    int h = nums.length-1;
    
    while(l<=h){
        int mid = l + (h-l)/2;
        
        if(target==nums[mid]){
            return mid;
        }       
        if(nums[mid]<nums[h]){
            // 说明在右边
            if(target<nums[mid] || target>nums[h]){
                h=mid-1;
            }else {
                l = mid+1;
            }
        }else {  
            // 说明在左边
            if(target>nums[mid] || target<=nums[h]){
                l=mid+1;
            }else {
                h=mid-1;
            }
        }
    }
    
    return -1;
}

求符合某条件的最小值的最大值

求峰值

public int findPeakElement(int[] nums) {
        
        int l = 0;
        int h = nums.length-1;

        while(l<h){
            int mid = l +(h-l)/2;
            if(nums[mid]>nums[mid+1]){
                h=mid;
            }else {
                l=mid+1;
            }
        }

        return l;
    }

双指针

两数之和，数组是排序的

public int[] twoSum(int[] numbers, int target) {
       if(numbers==null || numbers.length==0){
           return new int[]{};
       }
       
       int low = 0;
       int high = numbers.length-1;
    
       while(low<=high){
           if(numbers[low]+numbers[high]==target){
               return new int[]{low+1,high+1};
           }else if(numbers[low]+numbers[high]>target){
               high--;
           }else {
               low++;
           }
       }
       return new int[]{};
   }

连续子数组之和大于目标值 #209 长度最小的子数组【滑动窗口】有关

public int minSubArrayLen(int target, int[] nums) {
    int l = 0,r=0;
    int windowSum = 0;
    int minLen = Integer.MAX_VALUE;
    while(r<nums.length){
        windowSum+= nums[r];
        while(windowSum>=target){
            minLen= Math.min(minLen,r-l+1);
            windowSum -= nums[l];
            l++;
        }
        r++;
    }
    
    if(minLen==Integer.MAX_VALUE){
        return 0;
    }
    return minLen;
}

从排序数组中删除重复数字II（数字最多出现2次）

public int removeDuplicates(int[] nums) {    
    int l = 1;
    int preNum = nums[0];
    int count = 1;
    
    for(int h=1;h<nums.length;h++){
        count= nums[h]==preNum? count+1:1;
        if(count<=2){
            nums[l++]=nums[h];
        }
        preNum  = nums[h];
    }
   
    return l;
}

从排序数组中删除重复数字I（数字最多出现1次）

public int removeDuplicates(int[] nums) {
       int l=1;
       int num=nums[0];
       int h = 1;
       
       for(;h<nums.length;h++){
           if(nums[h]!=num){
               nums[l]=nums[h];
               num = nums[h];
               l++;
           }
       }
   
       return l;
   }

链表-删除倒数第N个节点

public ListNode removeNthFromEnd(ListNode head, int n) {

        if(head==null){
            return null;
        }

        ListNode dummy = new ListNode(-1);
        dummy.next = head;


        ListNode fast = dummy;
        ListNode slow = dummy;
    
        for(int i=0;i<n;i++){    
            fast = fast.next;
        }

        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next;
        }
        

        ListNode next = slow.next.next;
        slow.next = next;

        return dummy.next;
    }

链表-判断是否为循环链表

/**
 * leetcode 141
 * 链表是否有环 2024-09-03 review 整理
 * 2025-04-10 笔记更新
 * 时间复杂度 O(n)  空间复杂度O(1)
 */
public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow==fast){
                return true;
            }
        }
        return false;
    }

链表-两个链表的相交点

链表–两连表相加

/**
 * 2
 * 解法：双指针+链表
 * 时间复杂度O(N) 空间复杂度O(1)
 */    
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return add(l1, l2, 0);
    }

    ListNode add(ListNode l1, ListNode l2, int sum) {

        if (l1 == null && l2 == null) {
            return sum > 0 ? new ListNode(1) : null;
        }
        int val = sum;
        val += (l1 != null ? l1.val : 0);
        val += (l2 != null ? l2.val : 0);
        ListNode node = new ListNode(val%10);
        node.next = add(l1 != null ? l1.next : null, l2 != null ? l2.next : null, val/10);
        return node;
    }

回溯

Visited数组、访问过的变量List、终止条件、状态位标记复位和List回退

单词搜索

/**
* leetcode 79
**/
public boolean exist(char[][] board, String word) {
        
        boolean[][] visited = new boolean[board.length][board[0].length];
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                // 该节点为起点
                if(backTrack(board,word,i,j,0,visited)){
                    return true;
                }
            }
        }

        return false;
    }

    boolean backTrack(char[][] board,String word,int i,int j,int index,boolean[][] visited){
        
        // 终止条件
        if(index==word.length()){
            return true;
        }
        
        // 边界条件
        if(i<0 || j<0 || i>=board.length || j>=board[0].length || visited[i][j] ){
            return false;
        }
        
        if(word.charAt(index)!=board[i][j]){
            return false;
        }

        // 遍历逻辑
        visited[i][j]=true;
        if(backTrack(board,word,i+1,j,index+1,visited)){
            return true;
        }
        if(backTrack(board,word,i,j+1,index+1,visited)){
            return true;
        }
        if(backTrack(board,word,i-1,j,index+1,visited)){
            return true;
        }
        if(backTrack(board,word,i,j-1,index+1,visited)){
            return true;
        }
        visited[i][j]=false;

        return false;
    }

全排列 (无重复元素)

/**
 * 46 数组全排列
 * Input: nums = [1,2,3]
 * Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 */   
    List<List<Integer>> ret = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        boolean[] visited = new boolean[nums.length];
        backTrack(nums,new ArrayList<>(),visited);
        return ret;
    }

    void backTrack(int[] nums,List<Integer> list,boolean[] visited){

        // 终止条件
        if(list.size()==nums.length){
            ret.add(new ArrayList<>(list));
            return;
        }

        // 逻辑
        for(int i=0;i<nums.length;i++){
            if(!visited[i]){
                visited[i]=true;
                list.add(nums[i]);
                backTrack(nums,list,visited);
                list.remove(list.size()-1);
                visited[i]=false;
            }
        }
    }

全排列 (有重复元素)

/**
 * 47 数组全排列
 * 去重,比如[1,1,2]
 * Input: nums = [1,1,2]
 * Output:
 * [[1,1,2],
 *  [1,2,1],
 *  [2,1,1]]
 */ 
   List<List<Integer>> ret = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {

        boolean[] visited = new boolean[nums.length];
        Arrays.sort(nums);
        backTrack(nums, new ArrayList<>(), visited);

        return ret;
    }

    void backTrack(int[] nums, List<Integer> list, boolean[] visited) {

        // 终止条件
        if (list.size() == nums.length) {
            ret.add(new ArrayList<>(list));
            return;
        }

        for (int i = 0; i < nums.length; i++) {

            // 去重
            if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
                continue;
            }
            if (!visited[i]) {
                visited[i] = true;
                list.add(nums[i]);
                backTrack(nums, list, visited);
                list.remove(list.size() - 1);
                visited[i] = false;
            }

        }
    }

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

/** 77
 * time complexity O(K*combine(N,K))
 * space complexity O(K*combine(N,K))
 **/
List<List<Integer>> ret = new ArrayList<>();
    int N;
    int K;
    public List<List<Integer>> combine(int n, int k) {
        N=n;
        K=k;
        backTrack(1,new ArrayList<>());
        return ret;
    }

    void backTrack(int i, List<Integer> list){
        if(list.size()==K){
            ret.add(new ArrayList<>(list));
            return;
        }
        for(int j=i;j<=N;j++){
            list.add(j);
            backTrack(j+1,list);
            list.remove(list.size()-1);
        }
    }

和为target的组合（无重复元素）元素可以被多次使用

List<List<Integer>> ret = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    backTrack(candidates,0,target,new ArrayList<>());
    return ret;
}
   
void backTrack(int[] nums,int k,int target,List<Integer> list){
   
    // 边界条件
    if(target<0){
        return;
    }
    // 终止条件
    if(target==0){
        ret.add(new ArrayList<>(list));
        return;
    }
   
    // 遍历逻辑
    for(int i=k;i<nums.length;i++){
        list.add(nums[i]);
        backTrack(nums,i,target-nums[i],list); 
        list.remove(list.size()-1);
    }
}

和为target的组合（有重复元素）元素只能被使用一次

List<List<Integer>> ret = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backTrack(candidates, target, 0, new ArrayList<>());
        return ret;
    }

    void backTrack(int[] nums, int target, int start, List<Integer> list) {
        // 边界条件
        if (target < 0) {
            return;
        }
        // 终止条件
        if (target == 0) {
            ret.add(new ArrayList<>(list));
            return;
        }

        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1] ) {
                continue;
            } 
            list.add(nums[i]);
            backTrack(nums, target - nums[i], i+1, list);
            list.remove(list.size() - 1);

        }
    }

电话号码的组合

/**
 * 17
 * 给定一个字符串是"数字"，问按键有多少种组合
 */ 
String[] table = new String[]{"abc","def","ghi","jkl","mno",
                                  "pqrs","tuv","wxyz"};

    List<String> ret = new ArrayList<>();                  

    public List<String> letterCombinations(String digits) {
        if(digits==null || digits.length()==0){
            return new ArrayList<>();
        }
        backTrack(digits,0,new StringBuffer());
        return ret;
    }

    void backTrack(String digits,int index,StringBuffer sb){

        // 终止条件
        if(index>digits.length()){
            return;
        }
        // 满足条件
        if(index==digits.length()){
            ret.add(sb.toString());
            return;
        }
        int num = digits.charAt(index)-'2';
        for(int i=0;i<table[num].length();i++){
            sb.append(table[num].charAt(i));
            backTrack(digits,index+1,sb);
            sb.deleteCharAt(sb.length()-1);
        }
    }

括号生成（左括号数量+右边括号数量）

List<String> ret = new ArrayList<>();
public List<String> generateParenthesis(int n) {
    backTrack(n,0,0,new StringBuffer());
    return ret;   
}
   
void backTrack(int n,int l, int r,StringBuffer sb){  
    // 边界条件
    if(l>n || r>n || r>l ){
        return;
    }
    // 终止条件
    if(l==n && r==n){
        ret.add(sb.toString());
        return;
    }
   
    // 遍历逻辑
   
    // 左括号
    sb.append('(');
    backTrack(n,l+1,r,sb);
    sb.deleteCharAt(sb.length()-1);
   
    // 右括号
    sb.append(')');
    backTrack(n,l,r+1,sb);
    sb.deleteCharAt(sb.length()-1);
}

DFS

单词拆分（一个长word和List[]单词）（搜索+中间状态存储）
被围绕的区域，标记围绕的O为X 被围绕的区域

岛屿的数量

   /**
    * 200
    * 计算island数量
    */    
   public int numIslands(char[][] grid) {
           int count=0;
           int m = grid.length;
           int n = grid[0].length;
           for(int i=0;i<grid.length;i++){
               for(int j=0;j<n;j++){
                   if(grid[i][j]=='1'){
                       dfs(i,j,m,n,grid);
                       count++;
                   }
               }
           }
           return count;
       }
   
       void dfs(int i,int j, int m,int n,char[][] grid){
           if(i<0 || j<0 || i>=m || j>=n || grid[i][j]=='0'){
               return;
           }
           grid[i][j]='0';
           dfs(i+1,j,m,n,grid);
           dfs(i-1,j,m,n,grid);
           dfs(i,j+1,m,n,grid);
           dfs(i,j-1,m,n,grid);
       }

4. [#45 跳跃游戏 II](https://leetcode.cn/problems/jump-game-ii/) 贪心算法，本质上也是个搜索问题。

### 贪心算法

什么情况下用贪心算法，贪心算法看起来比较简单，局部最优--> 全局最优

我个人理解本质上是个搜索问题，只不过减枝了大部分不需要的搜索，那么问题来了，如何设计和寻找减枝的算法呢？先用暴力算法，然后再思考，有哪些不必要的计算？

1. 加油站⛽️问题  [加油站](https://leetcode.cn/problems/gas-station/description/?envType=study-plan-v2&envId=top-interview-150)  O(n^2)-->O(n) 

2. 买卖股票🏦的问题（一次和多次） 

3. 容器盛水问题 【贪心+双指针】O(n^2)-->O(n) 

4. 跳跃游戏 nums[i]代表可以跳跃的步数, 是否可以到达最后一个位置 

   ```java
    public boolean canJump(int[] nums) {
   
          int max=0;  
         for(int i=0;i<=max && i<nums.length;i++){
            max = Math.max(max,nums[i]+i);
            if(max>=(nums.length-1)){
               return true;
            }
         }
   
         return false;   
       }

跳跃游戏2，到达最后一个位置的，最小的步数

public int jump(int[] nums) {
   
       int step = 0;
       int start = 0;
       int end = 0;
       int maxEnd = 0;
       while (true) {
   
           // 判断是否已经满足条件
           if (maxEnd >= (nums.length - 1)) {
               break;
           }
           // 一轮迭代最远到那个地方
           for (int i = start; i <= end; i++) {
               maxEnd = Math.max(nums[i] + i, maxEnd);
           }
           // 迭代步数+1
           step++;
           start = end + 1;
           end = maxEnd;
       }
       return step;
   }

链表 ➡️➡️

反转链表
删除倒数K个节点 –快慢指针
链表数学+1

有序链表的合并

/**
 * leetcode 21
 * 两个链表是排序的，合并为新的合并的链表
 */
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null){return list2;}
        if(list2==null){return list1;}

        ListNode newHead = null;
        if(list1.val<=list2.val){
            newHead = new ListNode(list1.val);
            newHead.next = mergeTwoLists(list1.next,list2);
        }else {
            newHead = new ListNode(list2.val);
            newHead.next = mergeTwoLists(list1,list2.next);
        }
        return newHead;
    }

环形链表–判断是否有环

/**
 * leetcode 141
 * 链表是否有环
 * 时间复杂度 O(n)  空间复杂度O(1)
 */
public  boolean hasCycle(ListNode head) {
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
                return true;
            }
        }
        return false;
    }

环形链表–寻找相交点

/**
 *142
 * 时间复杂度 O(n) 空间复杂度 O(1)
 * 2(a+b) = a+b+c+b => 推导出a=c
 * 解题步骤：1. 确定是否有环 2. slow指针从head开始 fast指针从相交处开始，下一次相交点就是环的起点
 */
public ListNode detectCycle(ListNode head) {

        if(head==null || head.next==null){
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

        // 快慢指针两个节点是否会相遇
        do{
            fast = fast.next.next;
            slow = slow.next;
        }while(fast!=null && fast.next!=null && slow!=fast);

        // 不存在环
        if(slow!=fast){
            return null;
        }

        // 寻找环的起点
        ListNode start = head;
        while(start!=fast){
            start = start.next;
            fast  = fast.next;
        }
        return start;
    }

链表删除重复值，只保留一个

   public ListNode deleteDuplicates(ListNode head) {
           if(head==null || head.next==null){
               return head;
           }
           if(head.val==head.next.val){
               head=deleteDuplicates(head.next);
           }else {
               head.next = deleteDuplicates(head.next);
           }
           return head;
       }

8. 链表删除重复值，重复值不保留

   ```java
    public ListNode deleteDuplicates(ListNode head) {
           if(head==null){
               return null;
           }
   
           boolean headDup = false;
           while(head.next!=null && head.val==head.next.val){
               head = head.next;
               headDup=true;
           }
   
           ListNode next = deleteDuplicates(head.next);
           if(headDup){
               return next;
           }
   
           head.next = next;
           return head;
       }

随机链表复制【第一步链表复制 & 需要有一个Map保存旧链表与新链表节点的映射，第二步随机指针添加】
#61 旋转链表【先找到尾部节点，并且计算链表长度；然后再找到倒数第K+1个节点，然后进行指针转化】
分隔链表分隔链表第一轮

HashMap

最长连续不重复子字符串

/**
 * 3
 * 最长不重复子串的长度
 */      
public static int  lengthOfLongestSubstring(String s) {
        if(s==null || s.length()==0){
            return 0;
        }

        int start = 0;
        int max = Integer.MIN_VALUE;
        Map<Character,Integer> map = new HashMap<>();
        for(int i=0;i<s.length();i++){
            char cc =  s.charAt(i);
            if(map.get(cc)!=null){
                start = Math.max(start,map.get(cc)+1);
            }
            map.put(cc,i);
            max = Math.max(max,i-start+1);
        }

        return max;
    }

栈和队列

括号匹配

用堆栈实现一个队列

class MyQueue {
    
    Stack<Integer> popStack;
    Stack<Integer> pushStack;

    public MyQueue() {
        popStack = new Stack<>();
        pushStack = new Stack<>();
    }
    
    public void push(int x) {
        pushStack.push(x);
    }
    
    public int pop() {
        fillPopStack();
        return popStack.isEmpty()?-1:popStack.pop();
    }
    
    public int peek() {
        fillPopStack();
        return popStack.isEmpty()?-1:popStack.peek();
    }
    
    public boolean empty() {
        return popStack.isEmpty() && pushStack.isEmpty();
    }
    
    void fillPopStack(){
          if(popStack.isEmpty()){
            while(!pushStack.isEmpty()){
                popStack.push(pushStack.pop());
            }
        }
    }
}

最小栈申请两个栈，一个原始的数据栈，另一个是保存当前最小值的栈。

public class MinStack  {
    Stack<Integer> dataStack;

    Stack<Integer> minStack;

    /** initialize your data structure here. */
    public MinStack() {
        dataStack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int x) {
        dataStack.push(x);
        if(minStack.isEmpty()){
            minStack.push(x);
        }else {
            Integer peek = minStack.peek();
            minStack.push(Math.min(peek,x));
        }
    }

    public void pop() {
        dataStack.pop();
        minStack.pop();
    }

    public int top() {
        if(dataStack.isEmpty()){
            return -1;
        }
        return dataStack.peek();
    }

    public int getMin() {
        if(minStack.isEmpty()){
            return -1;
        }
        return minStack.peek();
    }
}

单调栈（也就是说栈中的元素是单调的，递增或递减，一般用来解决符合某种单调条件的差值）

// leetcode 739 日常温度 
public int[] dailyTemperatures(int[] temperatures) {
        // stack 存储的是未被处理的数据，一旦满足条件，就处理，pop，stack的元素满足某种单调条件
        Stack<Integer> stack = new Stack<>();
        int[] ret = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int peek = stack.pop();
                ret[peek] = i - peek;
            }
            stack.push(i);
        }
        return ret;
    }

堆

在Java中的数据结构叫优先队列，默认是最小堆。如果是最大堆，需要改下compare函数。

二叉树 🌲

本质上是搜索【从上往下、从下往上、前、中、后】解题思路：1. 从上往下搜索的过程中引入全局存储，可以记录搜索的路径等 2. 递归/递归一般是从下往上传递结果值，也可以是从下往上按照规则进行搜索，从上反推。

递归结果的值再进行逻辑判断。

前、中、后序遍历

层次遍历–从上到下

/**
 * 102
 * 解题思路：BFS
 * 时间复杂度 O(N)
 * 空间复杂度 O(N)
 */ 
public static List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> result=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> dataList=new ArrayList<>();
            //每层有多少个节点
            int levelNum=queue.size();
            for(int i=0;i<levelNum;i++){
                TreeNode data = queue.poll();
                dataList.add(data.val);
                if(data.left!=null){queue.add(data.left);}
                if(data.right!=null){queue.add(data.right);}
            }
            result.add(dataList);
        }
        return result;
    }

层次遍历（Z之形打印）

/**
 * 103
 * ZAG遍历
 * 时间复杂度 O(n)
 * 空间复杂度 O(K+n) K=level number
 */ 
public List<List<Integer>> levelOrderReverse(TreeNode root) {
        if(root==null){
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<List<Integer>> list = new ArrayList<>();
        boolean reverse = false;
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> levelList = new ArrayList<>();
            for(int i=0;i<size;i++){
                TreeNode currentNode = queue.poll();
                levelList.add(currentNode.val);
                if(currentNode.left!=null){queue.add(currentNode.left);}
                if(currentNode.right!=null){queue.add(currentNode.right);
                }
                if(reverse){
                    levelList.add(currentNode.val);
                }else{
                    levelList.add(0,currentNode.val);
                }
            }
            list.add(levelList);
            reverse = !reverse;
        }
        return list;
    }

二叉树的右视图

/**
 * 199 二叉树右视图
 * root->right->left
 * if(exist) add;
 * 时间复杂度 O(N) 空间复杂度O(logN)
 */
    List<Integer> ret = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        dfs(root,ret,0);
        return ret;
    }

    void dfs(TreeNode root,List<Integer> list,int depth){
        if(root==null){
            return;
        }

        if(list.size()==depth){
            list.add(root.val);
        }

        dfs(root.right,list,depth+1);
        dfs(root.left,list,depth+1);
    }

判断对称树

二叉树最近公共祖先

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
           if(root==null){
               return null;
           }
   
           if(root==p || root==q){
               return root;
           }
   
           TreeNode left = lowestCommonAncestor(root.left,p,q);
           TreeNode right = lowestCommonAncestor(root.right,p,q);
   
           if(left!=null && right!=null){
               return root;
           }else if(left==null && right!=null){
               return right;
           }else if(left!=null && right==null){
               return left;
           }
   
           return null;
   
       }

8. 二叉树转为链表  （PreNode和左右child节点提前保存）

9. 二叉树+target数字，是否存在根节点到叶子结点之和为目标值。

10. 二叉树+target数字，不一定是根节点到叶子结点，但是肯定是从父节点到子节点

   ```java
      public int pathSum(TreeNode root, int sum) {
           if (root == null)
               return 0;
           return pathSumFrom(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
       }
   
       private int pathSumFrom(TreeNode node, long sum) {
           if (node == null)
               return 0;
           return (node.val == sum ? 1 : 0)
                   + pathSumFrom(node.left, sum - node.val) + pathSumFrom(node.right, sum - node.val);
       }

二叉树的直径

int maxLen = 0;
public int diameterOfBinaryTree(TreeNode root) {
    dfs(root);
    return maxLen;
}
    
public int dfs(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int l = dfs(root.left);
    int r = dfs(root.right);
    maxLen = Math.max(l+r, maxLen);
    return Math.max(l,r)+1;
}

二叉搜索树

二叉搜索树中第K小的元素

 /**
 * 230
 * 中序遍历，count计数
 */
int val = -1;
    int count=0;
    int _k;
    public  int kthSmallest(TreeNode root, int k) {
        this._k=k;
        dfs(root);
        return val;
    }

    void dfs(TreeNode root){
        if(root==null){
            return;
        }
        dfs(root.left);
        count++;
        if(count==_k){
            val=root.val;
            return;
        }
        dfs(root.right);
    }

验证二叉搜索树

/**
 * 98
 * 判断是否为BST
 * 时间复杂度O(N) 空间复杂度O(1)
 */    
     public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
        if (root == null) return true;
        if (root.val >= maxVal || root.val <= minVal) return false;
        return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
    }

验证二叉搜索树的后序遍历序列是否合法
二叉搜索树最近公共祖先
#530 二叉搜索树的最小绝对差【中序遍历+前置节点】
判断是否为二叉搜索树判断是否为二叉搜索树【中序遍历+数值区间】

动态规划 🟪🟪➡️🟪🟪

前置状态存储的含义
状态转移方程
一维和多维

最长回文子串 dp[i][j]=true/false代表是否是回文串【二维】O(N^2)
最小路径和向➡️向⬇️ 移动【二维】 O(N^2)
最长递增子序列【一维】F[N]代表小于等于nums[N]的子数组的最大长度 O(N^2)

字符串123->abc 求可能的个数 leetcode91

public int numDecodings(String s) {
       
        if(s == null || s.length() == 0) {
            return 0;
        }
        int n = s.length();
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = s.charAt(0) != '0' ? 1 : 0;
        for(int i = 2; i <= n; i++) {
            int first = Integer.valueOf(s.substring(i-1, i));
            int second = Integer.valueOf(s.substring(i-2, i));
            if(first >= 1 && first <= 9) {
               dp[i] += dp[i-1];  
            }
            if(second >= 10 && second <= 26) {
                dp[i] += dp[i-2];
            }
        }
        return dp[n];
    }

并查集

本质上是个搜索问题，按照“业务逻辑”搜索，并且标记状态，然后继续进行搜索。

最长连续序列–先保存数据，然后再进行连续数字搜索。
合并区间 – 先排序，再合并 O(NLogN)

错题本❌

优先队列，默认是最小堆。
二分搜索，注意边界条件，使用[1,2] 和[1,2,3]作为测试用例验证
回溯，注意终止条件，以及visited、以及状态回溯等。

后端技术

#算法

算法-leetcode总结

https://yyb345.github.io/07-leetcode总结/

Author

杨一博

Posted on

October 1, 2024

Licensed under

网关-API网关核心技术 Previous

消息队列-Kafka原理 Next