闲话茶楼
0%

java LeetCode(更)

发表于 更新于 分类于 阅读次数： Valine：

大小写敏感

类名class首字母应该大写

方法名void小写字母开头,后面的每个单词首字母大写f

源文件名和public类名相同.java

所有的 Java 程序由 public static void main(String[] args) 方法开始执行

ADT 存 取
队列 offer(Obj) poll()
栈 push(Obj) pop()
集合 add(ele) get(index)

ava自带的类

String integer.toBinaryString(int十进制)

返回二进制字符串;

翻译 intenger 转换器，tobinary二进制

int Integer.parseInt(string字符串,int指定字符串的进制)

返回十进制

1
integer

正则表达式，java具体的实现没看

image-20220228154654072

过完一遍java基础

image-20220303100236374

image-20220303101332728

1
2
3
4
5
6
7
8
9
10
//伪代码，这个不好
start=0;end=len-1;//第一个这个好记一些，但不好用
while(start+1<end){//！！！！如果数组队列只有1个，+1就会越界！！！！
    //不加一最终没法结束循环,只能判断2个及以上
    mid=start+(end-start)/2;
    if(num[mid]<target)
        start=mid;//在右边
    else
        end=mid;
}//(start,end)

用这个//折半查找，如果数组不包含，不需要判断两头情况

1
2
3
4
5
6
7
8
9
//第三种伪代码，这个好用
start=0;end=length-1;
while(start<=end){//没移过头
    mid=start+(end-start)/2;
    if(num[mid]<target)
        start=mid+1;//多移动一些
    else
        end=mid-1;
}//(end,star)移动多了

704. 二分查找

1
2
3
4
5
6
7
8
9
10
11
//数组
static int binarysearch(int[] nums, int target){
    int left = 0, right = nums.length - 1;
    while(left <= right){
        int mid = left+(right-left)/2;
        if(nums[mid] == target) return mid;//找到了
        else if(nums[mid]<target) left=mid+1;
        else right=mid-1;
    }
    return -1;//返回没找到
}

278. 第一个错误的版本First Bad Version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left=1,right=n;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(!isBadVersion(mid)) left=mid+1;//mid是最后一个好，右面的是坏
            else right=mid-1;         
        }
        return left;//(right,left)     
    }
}

410. 分割数组的最大值Split Array Largest Sum二分猜答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.Arrays;
class Solution {
    public int splitArray(int[] nums, int m) {
        int sum = Arrays.stream(nums).sum();
        int max = Arrays.stream(nums).max().getAsInt();
        return binary(nums,m,sum,max);//调用二分
    }
    //sum从大到小逼近，max从很小到达逼近，直到两个大小相似满足题意
    //high，low，mid是自己想出来的从max到sum连续数字
    //寻找合适的mid对应最小sum，最大max
    private int binary(int[] nums,int m,int high,int low){
        int mid = 0;
        while (low<=high){
        mid=low+(high-low)/2;
        if(valid(nums,m,mid))high=mid-1;
        else low=mid+1;
        //满足条件？用mid来分割数组，累加大于mid则开始下一个分组，看最终分组数量是否大于m
        }
    return low;//(high,low)对应实际(max,最小sum)
    }
    private boolean valid(int [] nums, int m,int subArraySum){
        int curSum = 0,count=1;//从数组开头开始累加，第一个分组
        for (int num:nums){
            curSum +=num;//从第一个开始加
            if(curSum>subArraySum){
                //大于sum新分组
                curSum=num;//先curSum=0,再curSum=当前num
                count++;//分组计数+1
                if(count>m) return false;
            }
        }
        return true;
    }
}

300.Longest increasing Subsequence最长递增子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int lengthOfLIS(int[] nums) {
	    List<Integer> sub = new ArrayList<>();
	    sub.add(nums[0]);
	    for(int i=1;i<nums.length;i++){
	        int num = nums[i];
	        if(num>sub.get(sub.size()-1))//当前num>动态队列最后一个就入队
	        sub.add(num);
	        else{//在缓存队列sub中找到比num大或一样的的就替换掉
	            int j=binarySearch(sub,num);//返回第j需要替换
	            sub.set(j,num);                                
	        }
	    }return sub.size();
	}
	private int binarySearch(List<Integer> list, int target){
	    int left=0,right=list.size()-1;
	    while(left <= right){
	        int mid=left+(right-left)/2;
	        if(list.get(mid)==target)return mid;
	        else if(list.get(mid)<target)left=mid+1;
	        else right=mid-1;
	    }return left;
	}

剑指 Offer 11. 旋转数组的最小数字

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int minArray(int[] numbers) {
        int left=0,right=numbers.length-1;
        while(left<=right){
            int mid=left+(right-left)/2;//用右端点作为观测点，最小值往右都小于等于右端点，最小值往左都大于等于右端点，因为有重复。
            if(numbers[right]<numbers[mid])left=mid+1;//mid在最小值往左
            else if(numbers[right]<numbers[mid])right=mid-1;//
            else right--;//重复
        }
        return numbers[left];
    }
}

33. 搜索旋转排序数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int search(int[] nums, int target) {
        int left=0,right=nums.length-1;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(nums[mid]==target)return mid;
            else if (nums[left]<=nums[mid]){//左有序,=为什么是小于等于。其实就是为了最后只剩两个数的时候，匹配。否则（3，1）报错
                if(nums[mid]>target&&nums[left]<=target)right=mid-1;//target在前半部分
                else left=mid+1;
            }else{
                if(nums[mid]<target&&nums[right]>=target)left=mid+1;
                else right=mid-1;
            }
        }return -1;

    }
}

69. x 的平方根 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int mySqrt(int x) {
        int left = 1, right = (x>>1)+1;
        //int left = 1, right = x;
        while(left<=right){
            int mid=left+(right-left)/2;
            if (mid==x/mid) return mid;
            if(mid<x/mid) left=mid+1;
            else right = mid -1;
            }
            return right;//(right,left)
    }
}

剑指 Offer 53 - I. 在排序数组中查找数字 I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int search(int[] nums, int target) {
        return help(nums,target)-help(nums,target-1);//找8，用8的尾巴（下标）-7的尾巴（下标）
        //return help(nums,target);
    }
    private int help(int[] nums,int x){
        int left = 0,right=nums.length-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]<=x)left=mid+1;
            else right=mid-1;
        }
        return left;
    }
}

35. 搜索插入位置

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left=0,right=nums.length-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target)return mid;
            else if(nums[mid]<target)left=mid+1;
            else right=mid-1;
        }
        return left;
    }
}//所以，折半查找，如果数组不包含，不需要判断两头情况

367. 有效的完全平方数

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isPerfectSquare(int num) {
        int left=1,right=(num>>1)+1;
        while(left<=right){
            int mid=left+(right-left)/2;
            long sqr=(long)mid*mid;
            if(sqr==num)return true;
            else if(sqr>num)right=mid-1;
            else left=mid+1;
        }
        return false;
    }
}

162. 寻找峰值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//为什么用while一直报错？没看明白，可能和区间端点有关系
class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        for (; left < right; ) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

74. 搜索二维矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m=matrix.length,n=matrix[0].length;
        int left=0,right=m*n-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(matrix[mid/n][mid%n]==target)return true;
            if(matrix[mid/n][mid%n]<=target){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return false;
    }
}

2.双指针

image-20220304104414594

283. 移动零

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
//左指针左边均为非零数，左指针是一堵墙，不需要找0；
//右指针左边直到左指针处均为零，右指针找非0，搬去墙左边。
//如果起始位非0，相当于自己和自己交换，left++，right++
    public void moveZeroes(int[] nums) {
        int left = 0,right=0,n=nums.length;
        while(right<n){
            if(nums[right]!=0){//每次完成交换后左指针动
                swap(nums,left,right);
                left++;
            }right++;
        }
    }
    private void swap(int[] nums,int left,int right){
        int temp=nums[left];
        nums[left]=nums[right];
        nums[right]=temp;
    }
}

11. 盛最多水的容器

两堵墙，向里移动小的一个，有可能面积变大

如果两边相等，要不是最终答案，要不两个都不包括，不可能只包括一边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//两堵墙，向里移动小的一个，有可能面积变大
//如果两边相等，要不是最终答案，要不两个都不包括，不可能只包括一边
//暴力双指针逼近
class Solution {
    public int maxArea(int[] height) {
        int res=0,left=0,right=height.length-1;
        while(left<right){
            int minHeight = Math.min(height[left],height[right]);
            int width=right-left;
            res=Math.max(res,width*minHeight);
            if(height[left]<height[right])left++;
            else right--;
        }return res;
    }
}

1. 两数之和

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int[] twoSum(int[] nums,int target){
    Map<Integer,Integer> map = new HashMap<>();
    for(int i=0;i<nums.length;i++){
        int diff = target-nums[i];//nums[i]+diff=target
        if(map.containsKey(diff))return new int[]{map.get(diff),i};
        map.put(nums[i],i);//所有都压入Hashmap再说，return后就停止了
        }return null;
    }
}

142. 环形链表 II

快慢指针

单链表数据结构
1
2
3
4
5
6
7
public class LinkList{
    public Object data;
    public LinkList next;
    public LinkList(Object e){
        this.data=e;
    }
}

image-20220304163525117

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null&&fast.next!=null){//空或只有一个
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                fast=head;//看图a=c;
                while(slow!=fast){
                    fast=fast.next;
                    slow=slow.next;
                }return slow;
                }
            }return null;
        }
}

141. 环形链表

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(slow==fast)return true;
        }return false;
    }
}

88. 合并两个有序数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*
//先组合再排序
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i != n; ++i) {
            nums1[m + i] = nums2[i];//组合
        }
        Arrays.sort(nums1);//排序
    }
}
*/
/* 
//新建一个数组存放，双指针
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0, p2 = 0;
        int[] sorted = new int[m + n];//定义新的数组用了存放结果
        int cur;//这是需要入队列的值
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = nums2[p2++];//1到头，2入队列，直到2结束
            } else if (p2 == n) {
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {//从头比较，如果1<2,1入队列，1指针后移
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];//1>=2,同理
            }
            sorted[p1 + p2 - 1] = cur;//-1是++下轮递增
        }
        for (int i = 0; i < m + n; ++i) {//遍历
            nums1[i] = sorted[i];//回到n1
        }
    }
}
*/
//后面是空的，所以从后往前双指针
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1, p2 = n - 1;
        int tail = m + n - 1;//新定义尾巴指针区别于mn，存储合适元素
        int cur;//借用cur存储元素
        while (p1 >= 0 || p2 >= 0) {
            if (p1 == -1) {//1到头了，2入，直到结束
                cur = nums2[p2--];
            } else if (p2 == -1) {
                cur = nums1[p1--];
            } else if (nums1[p1] > nums2[p2]) {//1大，1入，1左移
                cur = nums1[p1--];
            } else {
                cur = nums2[p2--];
            }
            nums1[tail--] = cur;
        }
    }
}

剑指 Offer 22. 链表中倒数第k个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

/*
//顺序查找
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        int n = 0;
        ListNode node = null;
        for (node = head; node != null; node = node.next) {
            n++;//遍历记录长度n(0,size-1)
        }
        node = head;
        while(n>k){//从后往前数n--直到n<k,果然用for和if判断太费劲了，while容易很多
            node=node.next;
            n--;
        }
        return node;
    }
}
*/

//快慢指针，快指针比慢指针多移动k步，不需要统计长度
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;
        //快指针先移动k步
        while (fast != null && k > 0) {//不空且符合条件k不为0
            fast = fast.next;//fast移动k步直到k=0，快慢指针一起走，快指针走到外面时候，慢指针就是倒数第几个
            k--;
        }
        //快慢指针一起移动
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

876. 链表的中间结点

1
2
3
4
5
6
7
8
9
10
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

234.回文链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
import java.util.List;

/*
 * @lc app=leetcode.cn id=234 lang=java
 *
 * [234] 回文链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

// @lc code=end

/*
class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> vals = new ArrayList<Integer>();

        // 将链表的值复制到数组中
        ListNode currentNode = head;
        while (currentNode != null) {
            vals.add(currentNode.val);
            currentNode = currentNode.next;
        }

        // 使用双指针判断是否回文
        int front = 0;
        int back = vals.size() - 1;
        while (front < back) {
            if (!vals.get(front).equals(vals.get(back))) {
                return false;
            }
            front++;
            back--;
        }
        return true;
    }
}

*/
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }

        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode firstHalfEnd = endOfFirstHalf(head); //返回前半部分最后一个节点
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);//反转后半部分

        // 判断是否回文
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean result = true;
        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }        

        // 还原链表并返回结果
        firstHalfEnd.next = reverseList(secondHalfStart);//没有必要这一步
        return result;
    }

    private ListNode reverseList(ListNode head) {//反转
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    private ListNode endOfFirstHalf(ListNode head) {//快慢指针找中间的尾巴，二倍速
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

160. 相交链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 //A: a, c, b, meet
 //B: b, c, a, meet
 //because a+c+b==b+c+a
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null)return null;
        ListNode you=headA,she=headB;
        while(you!=she){
            // 若是有缘，早晚相遇;
            // 当你走到头，去重走她来时的路;
            // 当她走到头，也重走你来时的路;
            // 一路上，时而你踩着她的影子，时而她踩着你的影子;
            // 而缘分本身，就是能够坚持一直走下去。
            you= you==null? headB: you.next;
            she= she==null? headA: she.next;
        }
        return you;
    }
}

双指针two pointers 141/344/881

344. 反转字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public void reverseString(char[] s) {
        int left=0,right=s.length-1;
        char temp;
        //判空||1，判断与否都可以
            while(left<right){
                temp=s[left];
                s[left]=s[right];
                s[right]=temp;
                left++;
                right--;
            }
    }
}

class Solution {
    char temp = 0;
    public void reverseString(char[] s) {
        swap(s,0,s.length-1);
    }
    private void swap(char[] s,int left,int right){
        // 返回条件
        while(left>right){
            return;
        }
        // 递之前
        temp = s[left];
        s[left]=s[right];
        s[right]=temp;
        // 递下去
        swap(s,left+1,right-1);
        // 归回来
        // Do nothing.

    }
}

881. 救生艇

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int numRescueBoats(int[] people, int limit) {
        //先排序，最大的和最小的组合，只剩一个直接走，和小于等于limit走，大于走大的
        int res=0,left=0,right=people.length-1;
        Arrays.sort(people);
        while(left<=right){
            if(left==right){// 只剩下最后一个,直接一个走,结束
                res++;
                break;//一定要加，结束while
            }else if(people[left]+people[right]<=limit){// 最重的与最轻的一起走
                right--;
                left++;
                res++;
            }else{// 先载最重的, 而且最小的也无法一起载,那么就最重的单独走
                right--;
                res++;
            }
        }
    return res;
    }
}

3.sliding window(和two sum都很重要，高频)

双指针变形，一般为同向。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
模板
def findSubArray(nums):
    N = len(nums) # 数组/字符串长度
    left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间
    sums = 0 # 用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数
    res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
    while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
        sums += nums[right] # 增加当前右边指针的数字/字符的求和/计数
        while 区间[left, right]不符合题意：# 此时需要一直移动左指针，直至找到一个符合题意的区间
            sums -= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数
            left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反
        # 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
        res = max(res, right - left + 1) # 需要更新结果
        right += 1 # 移动右指针，去探索新的区间
    return res

209. 长度最小的子数组 Minimum Size Subarray Sum 找连续子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left =0,N=nums.length,res=Integer.MAX_VALUE,sum=0;//res窗口长度初始化为无限大，最后看结果有没有修改，改了就是新结果，没改就是0
        for(int i=0;i<N;i++){//外层移动右侧数组指针
            sum += nums[i];//当前窗口内的和
            while(sum >= target){//内层循环移动left指针知道和小于target
                res=Math.min(res,i-left+1);
                sum -= nums[left++];//窗口无脑右移一格；找连续子数组
            }
        }return res==Integer.MAX_VALUE ? 0:res;
    }
}

//二分法猜答案
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left=0,right=nums.length-1,res=0;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(volidwindow(mid+1,nums,target)){
                right=mid-1;
                res=mid+1;
            }else left=mid+1;
        }return res;
    }
    private boolean volidwindow(int size,int[] nums,int s){
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
            if(i-size>=0)sum-=nums[i-size];
            if(sum>=s)return true;
        }return false;
    }
}

340会员题目

1456. 定长子串中元音的最大数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//滑动窗口，暴力定长，超出时长限制
/*class Solution {
    public int maxVowels(String s, int k) {
        char[] c=s.toCharArray();
        int left=0,n=c.length,right=0,res=0;
        while(left<=n-k){
            int count=0;
            for(right=left;right<left+k;right++){
                if(c[right]=='a'||c[right]=='e'||c[right]=='i'||c[right]=='o'||c[right]=='u'){
                count++;
                }
            }
            res=Math.max(res,count);
            left++;           
        }
        return res;
    }   
}
*/

class Solution {
    public int maxVowels(String s, int k) {
        char[] c=s.toCharArray();
        int left=0,right=0,res=0,count=0;
        while(right<c.length){
            if(c[right]=='a'||c[right]=='e'||c[right]=='i'||c[right]=='o'||c[right]=='u'){
                count++;
            }
            right++;
            if(right-left==k){
                res=Math.max(res,count);
                if(c[left]=='a'||c[left]=='e'||c[left]=='i'||c[left]=='o'||c[left]=='u'){
                    count--;
            }
                left++;
            }
        }
        return res;
    }
}

3. 无重复字符的最长子串

剑指 Offer 48. 最长不含重复字符的子字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()==0)return 0;
        HashMap<Character,Integer> map = new HashMap<>();
        int left=0,max=0;
        for(int i=0;i<s.length();i++){
            if(map.containsKey(s.charAt(i))){
                left=Math.max(left, map.get(s.charAt(i))+1);
            }
            map.put(s.charAt(i),i);
            max=Math.max(max,i-left+1);
        }
        return max;
    }
}

1004. 最大连续1的个数 III

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int longestOnes(int[] nums, int k) {
        int len=nums.length;
        int l=0,r=0,max=0,count0=0;
        //本质上来说，滑窗是双指针，一根指针指向左端点，一根指针指向右端点。
        while(r<len){
            if(nums[r]==0)count0++;
            r++;
            //右指针移动可以表示扩张窗口，左指针移动表示缩小窗口。
            //如果当前元素满足题目要求时，可以挪动右指针尝试更优解，并且更新需要记录的变量（元素，元素个数++等）
            while(count0>k){
                if(nums[l]==0)count0--;
                l++;//直到nums[l==0,跳出while]
                //如果当前窗口内的元素不满足条件，可以挪动左指针尝试调整，并且更新需要记录的变量（元素，元素个数--等）
            }
            max=Math.max(max,r-l);
            //通过以上步骤窗口就开始“滑动”起来，在滑动过程中，要记得及时更新答案。一般为求最大或最小。
        }
        return max;
    }
}

30. 串联所有单词的子串

76. 最小覆盖子串

159. 至多包含两个不同字符的最长子串

209. 长度最小的子数组

239. 滑动窗口最大值

567. 字符串的排列

632. 最小区间

727. 最小窗口子序列

转变一下刷题顺序，先以出新手村为目标

笔记：
一.数据结构：
√1数组Array 485/283/27
√2链表Linked List 203/206
√3队列Queue 933/225（用队列实现栈）/622/641
√4栈stack 20/496/232（用栈实现队列） 单调栈模板
√5哈希表Hash table 217/389/496
√6集合set 217/705（设计）
√7堆Heap 215/692
√8树&图（算法）

二.算法：
√1双指针two pointers 141/344/881
√2二分查找 binary search ==704==/35/162/74
√3滑动窗口 sliding window（技巧） 209/1456
√4递归 recursion 509/206/344/687 画一画 树的先学树
5分治 divide&conquer 169/53
6回溯 backtracking 22/78/77/46（全经典）
7深度优先搜索DFS 938/78/200
8宽度优先搜索BFS 200/547/721
9并查集 union find 200/547/721
10贪心 greedy 322/1217/55
11记忆化搜索（技巧）509/322
12动态规划 dynamic programming 509/62/121/70/279/221
13拓扑排序 topologic sort 207/210
14前缀树 trie 208/720/692（数据结构）

ArrayList 动态数组:可以实现List，能增删改遍历

常用方法：get()返回第几个的值,add(),set()修改,remove()删除,size(),sort()排序

LinkedList线性链表：可以实现Queue,List；

queue常用操作：

添加到尾部：add(),offer()不报错；

peek()返回第一个,poll()返回第一个并删掉,size()长度.

1数组Array 485/283/27

ArrayList ADT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
size();

isEmpty();

contains(Object o)是否包含，不含false;

indexOf(Object o)元素下标，不存在-1;

lastIndexOf(Object o)最大下标，不含-1;

get(int e)获取指定下标的元素;

set(int e,E element)设置指定下标的值;

add(E e)队尾添加数据;

add(int index,E element)指定下标添加元素，小于动态数组大小;

remove(int index);

remove(Object o)移除指定元素，成功返回true，失败返回false;

clear()清除所有;

sort()所有元素排序;


485. 最大连续 1 的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int count=0,max=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==1)count++;
            else if(nums[i]==0){
                max=Math.max(max,count);
                count=0;
            }
            if(i==nums.length-1)max=Math.max(max,count);
        }
        //或者直接max=Math.max(max,count);
        return max;
    }
}

27. 移除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int removeElement(int[] nums, int val) {
        int idx = 0;
        for (int x : nums) {//x移动，快指针
            if (x != val) nums[idx++] = x;//如果不一样，需要换了，idx下一个，慢指针
        }
        return idx;
    }
}
/* 
class Solution {
    public int removeElement(int[] nums, int val) {
        int j = nums.length - 1;
        for (int i = 0; i <= j; i++) {
            if (nums[i] == val) {
                swap(nums, i--, j--);//重新判断i位置换过来的新元素
            }
        }
        return j + 1;
    }
    void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
*/

26. 删除有序数组中的重复项

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//慢指针指向重复第一个，slow左边的都不重复
//快指针指向重复元素后第一个新元素
class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums==null||nums.length==0)return 0;
        int fast=1,slow=0;
        while(fast<nums.length){
            //快指针遇到不一样的，传给慢指针的下一个，慢指针刷新移动，快指针同样移动，访问过了
            if(nums[fast]!=nums[slow]){
                nums[slow+1]=nums[fast];
                slow++;
            }
            //如果前后一样，快指针继续移动
            fast++;
        }
        return slow+1;
    }
}

448. 找到所有数组中消失的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//数组索引和不重复数组-1完全一致
//有重复数组，重复数字，少了元素，也少了对应的索引+1
//所以只需要看索引位置就可以知道少了什么数字
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        if(nums.length==0)return null;
        for(int i=0;i<nums.length;i++){
            nums[Math.abs(nums[i])-1]=-Math.abs(nums[Math.abs(nums[i])-1]);
        }//理解nums[nums[i]-1]
        List<Integer> result=new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0) result.add(i+1);
        }
        return result;
    }
}

2链表Linked List 203/206

单向链表ADT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
isEmpty();

isLast(node) node是否最后一个结点，true false;

getFirst();

setFirst(node);

prepend(T obj)添加元素到链头，返回指向新节点的指针;

append(T obj)添加元素到表尾，返回指向新节点指针;

insert(node,T obj) node后插入新结点obj，返回新结点;

remove(node);

removeHead();

clear();

free();

getNthEntry(int n)返回第n个位置的元素，超出报错;

length();

toArry();

findData(T obj);

迭代器?Iterator

203. 移除链表元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ////创建一个新的头,加一个头来判断第一个节点
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;//head前一个
        ListNode temp = dummyHead;//当前指针
        
        while (temp.next != null) {//判断下一个是不是val，为空或者到了最后
            if (temp.next.val == val) {
                temp.next = temp.next.next;//删除下一个
            } else {
                temp = temp.next;//后移
            }
        }
        return dummyHead.next;
    }
}

206. 反转链表头插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//头插法 模板
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;//新增头
        ListNode curr = head;//1->2->3为例
        while (curr != null) {//不空也没有到尾，cur=2       
            //核心，断中间指针，换next
            ListNode next = curr.next;//next保存,next=3
            curr.next = prev;//curr.next=1           
            //后移
            prev = curr;//pre=2
            curr = next;//cur=3//还需要使用cur.next所以用next保存
        }
        return prev;
    }
}

//递归
class Solution {
	public ListNode reverseList(ListNode head) {
		//递归终止条件是当前为空传进来个空的，或者下一个节点为空递归到了最后一个
		if(head==null || head.next==null) {
			return head;
		}
		//这里的cur就是最后一个节点
		ListNode cur = reverseList(head.next);//进入递归，下一层，之后的代码先不执行
		
		//如果链表是 1->2->3->4->5，那么此时的cur就是5
		//而head是4，head的下一个是5，下下一个是空，则进入if，return 5结束(4.next)的递归
		
        //所以head.next.next 就是(4.next).next=4  5->4
		head.next.next = head;
		//防止链表循环，需要将head.next设置为空 4.next=null
		head.next = null;
		//每层递归函数都返回cur，也就是最后一个节点 ,从上一层没执行完的head.next.next = head继续,执行完所有语句结束这一层递归
		return cur;
	}
}

19. 删除链表的倒数第 N 个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next=head;
        ListNode first = dummy, second = dummy;
        for(int i=0;i<n;i++){
            first=first.next;
        }
        while(first.next!=null){
            first=first.next;
            second=second.next;
        }
        second.next=second.next.next;
        return dummy.next;
    }
}

21. 合并两个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head=new ListNode();
        ListNode res=head;
        while(list1!=null&&list2!=null){
            if(list1.val<=list2.val){
                res.next=list1;
                list1=list1.next;               
            }else{
                res.next=list2;
                list2=list2.next;
            }
            res=res.next;
        }
        //没合并完的部分
        res.next= list1==null?list2:list1;
        return head.next;
    }
}

3队列Queue 933/225（用队列实现栈）/622/641

队列ADT：

1
2
3
4
5
6
7
8
9
10
11
12
13
add(E e)队尾加入，无可用空间报错;

offer(E e)队尾加入元素，无可用返回false;

push(E e)类似与offer;

remove()移除队首并返回，空报错;

pop()移除队首并返回，空null;同pull();

element()返回队首，空报错;

peek()返回队首，空null；

933. 最近的请求次数

题目莫名其妙看不懂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class RecentCounter {
    Queue<Integer> q;
    public RecentCounter() {
        q = new LinkedList();
    }

    public int ping(int t) {
        q.add(t);
        while (q.peek() < t - 3000)//peek返回第一个元素
            q.poll();//删除并返回第一个
        return q.size();
    }
}

225. 用队列实现栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class MyStack {
    Queue<Integer> queue;
    Queue<Integer> queue_ass;

    public MyStack() {
        queue=new LinkedList<Integer>();
        queue_ass=new LinkedList<Integer>();
    }
    //思路，在插入的时候，执行操作：1给空的辅助队列输入新元素，倒过来了，2把旧队列所有入队辅助队列，3交换
    public void push(int x) {
//队列的add()方法和offer()方法的区别
//区别：两者都是往队列尾部插入元素，不同的时候，当超出队列界限的时候，
//add（）方法是抛出异常让你处理，
//offer（）方法是直接返回false
        queue_ass.offer(x);
         while(!queue.isEmpty()){
             queue_ass.offer(queue.poll());
        }
        while(!queue_ass.isEmpty()){//交换
             queue.offer(queue_ass.poll());
        }
        /*Queue<Integer> temp = queue1;//一样的交换
        queue1 = queue2;
        queue2 = temp;*/
    }
    public int pop() {
        return queue.poll();
    }
    
    public int top() {
        return queue.peek();
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }
}

622. 设计循环队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//用固定长度数组实现循环队列
//定义两个循环变量（指针），front和rear，模仿动态数组
//rear指向前一个可以插的空位，front指向队头第一个元素非空
//人为区别空和循环满的判断条件，空front==rear,循环满(front+1)%length==rear,浪费最后一个空位
public class MyCircularQueue {
    private int[]arr;
    private int front;
    private int rear;
    private int length;
    public MyCircularQueue(int k) {
        length=k+1;
        arr=new int[length];
        front=0;
        rear=0;
    }
    
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }else{
            arr[rear]=value;
            rear=(rear+1)%length;
            return true;
        } 
    }
    
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }else{
            front=(front+1)%length;
            return true;
        }
    }
    
    public int Front() {
        if(isEmpty()){
            return -1;
        }else return arr[front];

    }
    
    public int Rear() {
        if(isEmpty()){
            return -1;
        }else{
         return arr[(rear-1+length)%length];
        }
    }
    
    public boolean isEmpty() {
        return(front==rear);
    }
    
    public boolean isFull() {
        return((rear+1)%length==front);// 注意：这是这个经典设计的原因
    }
}

641. 设计循环双端队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class MyCircularDeque {//和单端循环队列区别不大,头朝后尾朝前，头增长尾缩短
    private int[] arr;
    private int front;
    private int rear;
    private int length;


    public MyCircularDeque(int k) {
        length=k+1;
        arr=new int[length];
        front=0;
        rear=0;
    }
    
    public boolean insertFront(int value) {//新的
        if(isFull())return false;
        else{
            arr[(front-1+length)%length]=value;
            front=(front-1+length)%length;
            return true;
        }
    }
    
    public boolean insertLast(int value) {
        if(isFull())return false;
        else{
            arr[rear]=value;
            rear=(rear+1)%length;
            return true;
        }
    }
    
    public boolean deleteFront() {
        if(isEmpty())return false;
        else{
            front=(front+1)%length;
            return true;
        }
    }
    
    public boolean deleteLast() {//新的
        if(isEmpty())return false;
        else{
            rear=(rear-1+length)%length;
            return true;
        }
    }
    
    public int getFront() {
        if(isEmpty())return -1;
        else return arr[front];
    }
    
    public int getRear() {
        if(isEmpty())return -1;
        else return arr[(rear-1+length)%length];
    }
    
    public boolean isEmpty() {
        if(front==rear)return true;
        else return false;
    }
    
    public boolean isFull() {
        if((rear+1+length)%length==front)return true;
        else return false;
    }
}

4栈stack 20/496/232（用栈实现队列）

栈ADT：

1
2
3
4
5
6
7
8
9
10
11
stack()建立一个空栈;

push(E item)栈顶插入，入栈;

pop()栈顶删除返回，出栈;

peek()返回栈顶元素;

empty();

search(Object o)查找位置;

20. 有效的括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isValid(String s) {
        if(s.isEmpty())return false;
        Stack<Character> stack=new Stack<Character>();
        for(char c:s.toCharArray()){
            if(c=='(')
                stack.push(')');
            else if(c=='[')
                stack.push(']');
            else if(c=='{')
                stack.push('}');
            else if(stack.empty()||c!=stack.pop())
                return false;
        }
        if(stack.empty())
            return true;
        else return false;
    }
}

496. 下一个更大元素 I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//模板
//[2,1,2,4,3]自己找自己[4,2,4,-1,-1]
//找能挡住自己的就够了
vector<int> nextGreaterElement(vector<int>& nums) {
    vector<int> ans(nums.size()); // 存放答案的数组
    stack<int> s;// 这里放元素索引，而不是元素
    for (int i = nums.size() - 1; i >= 0; i--) { // 倒着往栈里放,一开始就是从自己之后开始寻找;与顺序寻找，把所有都压入栈再找不同在于，全部一次压入栈 需要先找当前的元素自己，再找之后的更大元素，找完到下一个需要把它之前出栈的元素重新压栈;
        while (!s.empty() && s.top() <= nums[i]) { // 判定个子高矮，循环，如果小就出栈扔掉，把所有无关的小个子都扔掉直到被大个子挡住
            s.pop(); // 矮个起开，反正也被挡着了。。。
        }//栈里剩下来的第一个是比当前元素大的大个子
        ans[i] = s.empty() ? -1 : s.top(); // 这个元素身后的第一个高个,得到最大元素的值
        s.push(nums[i]); // 进队，接受之后的身高判定吧！加入
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] result=new int [nums1.length];
        Map<Integer,Integer>map=nextGreaterHelper(nums2);//找到nums2自己的nextGreaterElement
        for(int i=0;i<nums1.length;i++){//查询map
            result[i]=map.get(nums1[i]);
        }
        return result;      
    }
    //因为nums1是nums2的子集，只需要 先套用模板在nums2中nums2的nextGreaterElement,用map储存，nums1就一定能在map中 找到自己在nums2母集中对应的nextGreaterElement
    private Map<Integer,Integer> nextGreaterHelper(int[] nums){
        Map<Integer,Integer> map=new HashMap<>();
        Stack<Integer> stack=new Stack<>();
        for(int i=nums.length-1;i>=0;i--){
            while(!stack.empty()&& stack.peek()<=nums[i]){//peek(),top()无所谓
                stack.pop();
            }
            map.put(nums[i],stack.isEmpty()?-1:stack.peek());//isEmpty(),empty()无所谓
            stack.push(nums[i]);
        }
        return map;
    }
}

503. 下一个更大元素 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//用i % length取余模拟循环
//[21243]->假装变成两倍->[21243 21243] [4,2,4,-1,4]
//变化：在1循环时循环2length-1次，2所有从nums读数字都是i%length
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n=nums.length;
        int[] res=new int[n];// 存放结果
        Stack<Integer> stack=new Stack<>();
        // 假装这个数组长度翻倍了
        for(int i=2*n-1;i>=0;i--){//假装翻倍ums.length，一共执行了2*length-1次，重复的一遍更新，大部分是重复数字；有变化
            while(!stack.empty()&&stack.peek()<=nums[i%n]){//i%nums.length()实现复制模拟循环；有变化
                stack.pop();
            }
            res[i%n]=stack.empty()?-1:stack.peek();
            stack.push(nums[i%n]);
        } 
        return res;
    }
}

1118.一月有多少天

5哈希表Hash table 217/389/496

1
HashSet<String> sites = new HashSet<String>();
HashSet常用 add(),contains(),remove(),size();
1
HashMap<Integer, String> Sites = new HashMap<Integer, String>();
HashMap常用put(key,value),get(key)访问value,remove(key),size()

for-each,clear(),clone(),isEmpty()通用

217. 存在重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }
}

//HashSet不能保存相同元素，add不进去，而且自带去重，结果会短
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int x : nums) {
            if (!set.add(x)) {
                return true;
            }
        }
        return false;
    }
}
//去重判断长度的方法
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set=new HashSet<>();
        for(int x:nums)set.add(x);
        if(set.size()<nums.length)return true;
        else return false;
    }
}

389. 找不同

1
2
3
4
5
6
7
8
9
10
11
 class Solution {
    public char findTheDifference(String s, String t) {
        Set<Character> set=new HashSet<>();
        char[] charArr = s.concat(t).toCharArray();//concat()连接到字符串尾部，toCharArray()转化为字符数组
        for(int i=0;i<charArr.length;i++){
            if(set.contains(charArr[i])){//s元素有两份重合，添加的一个字母只有一份；如果包含就删去，不包含就添加，两份会先添加再删除，一份只添加不删除
                set.remove(charArr[i]);
            }else set.add(charArr[i]);
        }return (char) set.toArray()[0];
    }
}

496. 下一个更大元素 I 哈希+单调栈怎么做？

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res =new int[nums1.length];      
        for(int i=0;i<nums1.length;i++){
            int j=0;
            while(j<nums2.length&&nums1[i]!=nums2[j])j++;//跳出条件为相等或没有
            while(j<nums2.length&&nums2[j]<=nums1[i])j++;//如果相等而不是遍历后没有,下一个符合条件跳出         
            res[i] = j<nums2.length ? nums2[j] : -1;
        }return res;

    }
}

136. 只出现一次的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer>set =new HashSet<>();       
        for(int i=0;i<nums.length;i++){   
            if(set.contains(nums[i])){
                set.remove(nums[i]);
            }else set.add(nums[i]);
        }return (int)set.toArray()[0];
    }
}
*/
class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer>set =new HashSet<>();  
        for(int i:nums){//循环写法差别而已
            if(set.contains(i)){
            set.remove(i);
            }else set.add(i);
        }return (int)set.toArray()[0];
    }
}

349. 两个数组的交集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Arrays;
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set <Integer> parentSet=new HashSet<>();
        Set <Integer> childSet=new HashSet<>();
        for(int num:nums1){
            parentSet.add(num);
        }
        for(int num:nums2){
            if(parentSet.contains(num)){//重复就存
                childSet.add(num);
            }
        }
        //用数组输出，hashset调用函数转数组转不明白暴力转
        int [] res=new int[childSet.size()];
        int index=0;
        for(int value:childSet){
            res[index++]=value;
        }
        return res;
    }
}

242. 有效的字母异位词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*class Solution {
    public boolean isAnagram(String s, String t) {
        char[] sChars=s.toCharArray();
        char[] tChars=t.toCharArray();
        Arrays.sort(sChars);
        Arrays.sort(tChars);
        return Arrays.equals(sChars,tChars);
    }
}*/

class Solution {
    public boolean isAnagram(String s, String t) {
        Map<Character,Integer> map=new HashMap<>();
        for(char ch:s.toCharArray()){
            map.put(ch,map.getOrDefault(ch,0)+1);//getOrDefault获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值(定义ch,0默认值)
        }
        for(char ch:t.toCharArray()){
            Integer count=map.get(ch);
            if(count==null){
                return false;
            }else if(count>1){
                map.put(ch,count-1);//更新
            }else {
                map.remove(ch);
            }
        }
        return map.isEmpty();
    }
}

剑指 Offer 03. 数组中重复的数字

HashSet.add() 不进去重复元素，会return false

而HashMap.put()会更新

1
2
3
4
5
6
7
8
class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set=new HashSet<>();
        for(int num:nums){
            if(!set.add(num))return num;
        }return -1;
    }
}

6集合set 217/705（设计）

705. 设计哈希集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//数组
class MyHashSet {
/** Initialize your data structure here. */
    boolean[]nodes =new boolean[10000000];//boolean类型的数组，好用
    public MyHashSet() {
    }
    public void add(int key) {
        nodes[key]=true;
    } 
    public void remove(int key) {
        nodes[key]=false;
    }
    public boolean contains(int key) {
        return nodes[key];
    }
}

7堆Heap 215/692

image-20220309214446810

已知堆的父节点，左孩子2k+1，右孩子2k+2；

已知孩子节点k，parent (k-1)/2 int不要小数

Heapify 堆排序（大根堆、小根堆） T(N)=O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private void buildHeap(int[] A){//传入数组，堆排序，并且要求是大根堆
    for(int i=A.length/2;i--)//为什么length/2？所有双亲节点，叶子节点占一半
		heapify(A,A.length,i);
}
//从二分之一开始往前，对应每个双亲结点，以及它自己的双亲结点（之后会递归到存储数组的开头），从下往上，堆排序；每次具体排序都从这个结点作为根节点自上而下遍历排序到自己的叶子节点，因为之前上层的排序有可能使下面的排序不符合堆。
//完成大根堆后，才能考虑通过交换最大根元素到最后一个叶子节点，找根和孩子节点最大，不断把上浮的大元素交换到叶子，完成堆排序。堆排序看后面！
static void heapify(int arr[],int n,int i){
    int largest=i;//初始化largest as root
    int lChild=2*i+1;//左右孩子指针
    int rChild=2*i+2;
    //在三个结点中先找最大，用largest指针标记最大，找到后交换largest到根节点
    if(lChild<n&&arr[lChild]>arr[largest])
        largest=lChild;
    if(rChild<n&&arr[rChild]>arr[largest])
        largest=rChild;
    if(largest!=i){//最大不是根结点，就交换值
        int temp=arr[i];
        arr[i]=arr[largest];
        arr[largest]=arr[i];
        heapify(arr,n,largest]);//largest此时指向改变的位置
    }
}

网页捕获_10-3-2022_102336_www.cnblogs.com

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//HeapSort 每次把第一个元素拿出来，对剩下的做Heapify，没法直接拿，把头和尾做调换，把最后一个尾巴叶子节点砍掉 T（n）=nlog(n)
public void sort(int arr[]){
    int n=arr.length;
    //build
    for (int i=n/2-1;i>=0;i--)//算一下，i=n/2-1确定最后叶子节点对应的根，很巧妙,找双亲或者i=(n-1)/2
        heapify(arr,n,i);
    //one by one extract an element for heap
    for (int i=n-1;i>0;i--){
        //move current root to end
        int temp=arr[0];
        arr[0]=arr[i];
        arr[i]=temp;
        
        //对除了最后一个元素（已经完成了排序），剩下的所有重生成堆heapify
        heapify(arr,i,0);//用i排除最后一个很巧妙
    }
    
}

PriorityQueue JAVA默认小根堆

img

image-20220310112716034

剑指 Offer 40. 最小的k个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

// 保持堆的大小为K，然后遍历数组中的数字，遍历的时候做如下判断：
// 1. 若目前堆的大小小于K，将当前数字放入堆中。
// 2. 否则判断当前数字与大根堆堆顶元素的大小关系，如果当前数字比大根堆堆顶还大，这个数就直接跳过；
//    反之如果当前数字比大根堆堆顶小，先poll掉堆顶，再将该数字放入堆中。

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k==0||arr.length==0)return new int[0];
        //使用大根堆，Java的PriorityQueue默认小根堆，添加comparator参数变成大根堆
        Queue<Integer> heap = new PriorityQueue<>((v1, v2) -> v2 - v1);
        //Queue<Integer> heap =new PriorityQueue<>((v1, v2) -> v2 - v1);
        for(int e:arr){
            //当前是大根堆，只有小于堆顶入堆
            if (heap.size() < k) {
                heap.offer(e);
            } else if (e < heap.peek()) {
                heap.poll();
                heap.offer(e);
            }//删除最大元素，保证（已读取最小的）大根堆里只有k个元素
            
        }
        //用int数组返回
        int[] res=new int[heap.size()];
        int j=0;
        for(int e:heap){
            res[j++]=e;
        }return res;

    }
}

703. 数据流中的第 K 大元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class KthLargest {
    PriorityQueue<Integer> pq;
    int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        pq = new PriorityQueue<Integer>();
        for (int x : nums) {
            add(x);
        }
    }
    
    public int add(int val) {
        pq.offer(val);
        if (pq.size() > k) {
            pq.poll();
        }
        return pq.peek();
    }
}

215. 数组中的第K个最大元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findKthLargest(int[] nums, int k) {
        if(nums.length<k||nums.length==0)return -1;
        Queue<Integer> pq=new PriorityQueue<Integer>();
        // Java 里没有 heapify ，因此我们逐个将前 k 个元素添加到 pq 里
        for(int i=0;i<k;i++){
            pq.offer(nums[i]);
        }//先读取k个进去
        //再读取后面的
        for(int i=k;i<nums.length;i++){
            // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
            if(nums[i]>pq.peek()){
                    pq.poll();
                    pq.offer(nums[i]);
            }
        }
        return pq.peek();
    }
}

动态规划没看

53. 最大子数组和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//思路1，暴力，每一个元素做第一位，循环找对应最大和，最后比较最大是哪个第一个元素，相当于两层循环
class Solution {
    public int maxSubArray(int[] nums) {
        int result=nums[0];//这样定义很巧妙
        for(int i=0;i<nums.length;i++){
            int count=0,res=nums[0];
            for(int j=i;j<nums.length;j++){
                count=count+nums[j];
                res=Math.max(res,count);
            }
            result=Math.max(result,res);
        }
        return result;
    }
}//超出时间限制，结果应该是没问题，需要优化
//暴力法无法通过

8递归 recursion 509/206/344/687 画一画

509. 斐波那契数

1
2
3
4
5
6
class Solution {
    public int fib(int n) {
        if(n<2) return n;
        return fib(n-1)+fib(n-2);
    }
}

9分治 divide&conquer 169/53,考的少先跳过

169. 多数元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//找众数
//1暴力找

//2排序看中间
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[(nums.length-1)/2];
    }
}
//3hashmap计数

//4分治？
//5摩尔投票？

10 扫描线

252. 会议室

input:[[0,30],[5,10],[15,20]] outpit:false 能否同时参加

1
2
3
4
5
6
7
8
9
10
public boolean canAttendMeeting(int[][] intervals){
    if(intervals.length==0)return true;
    Arrays.sor(intervals,(a,b)->a[0]-b[0]);//分类完比较起点终点就是扫描线
    for(int i=0;i<intervals.length-1;i++){
        if(intervals[i][1]>intervals[i+1][0]){
            return false;//前一个结束的比后一个开始的迟
        }
    }
    return true;
}

253. 会议室 II 飞机起飞

input:[[0,30],[5,10],[15,20]] outpit:2 最少需要几个房间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int minMeetingRooms(int[][] intervals){
    List<int[]> list = new ArrayList<>();
    for(int[] interval: intervals){
        list.add(new int[]{interval[0],1});
        list.add(new int[]{interval[1],-1});
    }
    Collection.sort(list,(a,b)->a[0]==b[0]?a[1]-b[1]:a[0]-b[0]);
    int res=0,count=0;
    for(int[]point:list){
        count +=point[1];
        res=Math.max(res,count);        
    }
    return res;
}

11 树

144. 二叉树的前序遍历

94. 二叉树的中序遍历

145. 二叉树的后序遍历

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

//前序递归遍历，叶子结点下面加一行空判断结束递归
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root, result);
        return result;
    }
    public void preorder(TreeNode root, List<Integer> result){
        if(root==null)return;//如果为空，上一个根是叶子，结束此递归
        result.add(root.val);//压入顺序表
        //递归前
        preorder(root.left, result);//递归
        preorder(root.right, result);//递归
        //递归后不需要做什么了
    }
}
//中序递归遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        inorder(root,result);
        return result;
    }
    private void inorder(TreeNode root,List result){
        if(root == null)return;
        inorder(root.left,result);
        result.add(root.val);
        inorder(root.right,result);
    }
}
//后序递归遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        postorder(root, result);
        return result;
    }
    private void postorder(TreeNode root, List<Integer> result){
        if(root == null)return;
        postorder(root.left,result);
        postorder(root.right,result);
        result.add(root.val);
    }
}

字符串中只有isEmpty()方法，其它没太大区别

迭代，好理解的思路，不同写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//前序遍历，迭代，迭代结果中左右，压栈中，右左，让右在栈底
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        //不同于递归，需要判空
        if(root == null)return result;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);//中
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if(node.right!=null){
                stack.push(node.right);
            }
            if(node.left!=null){
                stack.push(node.left);
            }
        }
        return result;
    }
}
//后续递归遍历，基于前序遍历，中左右，调整顺序，中，右左，方便在中先访问先处理，顺序一致；反转result为左右中
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if(root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        //先前序遍历，但是结果是中右左
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            //先把左压入栈底
            if(node.left!=null){
                stack.push(node.left);
            }
            if(node.right!=null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}
//中序遍历，访问顺序和，result处理顺序不一致，输出左中右，入栈，左右
//迭代，从头开始一直往左，经历了中和左，把所有左都压入栈；到头，为空，上一个元素，也就是存在栈顶部一个，左出栈，或者中出栈，看它右边有没有，先指针指向右边右压，有就重复步骤：压栈左深度遍历，没有就出栈栈顶，也就是更早之前来时的路。
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if(root==null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()){//cur!=null负责左深度;isEmpty负责返回来时的路
            //不断往左子树方向走，每走一次就将当前节点保存到栈中
			//这是模拟递归的调用
            if(cur!=null){
                stack.push(cur);
                cur=cur.left;//一动一次cur
                //当前节点为空，说明左边走到头了，从栈中弹出节点并保存
			    //然后转向右边节点，继续上面整个过程
            }else{
                cur=stack.pop();//第一次移动cur，回
                result.add(cur.val);
                cur=cur.right;//第二次移动cur，右
            }
            //从左深度走到了右深度
        }
        return result;
    }
}

用标记的方法统一迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//标记迭代，统一写法,不好理解
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<Integer>();
        Stack<TreeNode> stack=new Stack<>();
        if(root!=null)stack.push(root);//先让栈中有根再说，然后入栈访问，访问完了用null标记一下，出栈处理加到result里
        while(!stack.isEmpty()){
            // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
            // 将空节点弹出
            TreeNode node = stack.pop();
            if(node!=null){//未访问
                // 添加右节点（空节点不入栈）
                if(node.right!=null)stack.push(node.right);
                // 添加中节点
                stack.push(node);//已访问
                // 中节点访问过，但是还没有处理，加入空节点做为标记。
                stack.push(null);//给访问元素打上标记
                 // 添加左节点（空节点不入栈）
                if(node.left!=null)stack.push(node.left);//出栈从左开始
                // 只有遇到空节点的时候，才将下一个节点放进结果集
            }else{//已访问出栈为空
                // 重新取出栈中元素
                node=stack.pop();
                // 加入到结果集
                result.add(node.val);//出栈已访问元素，剩下的是其它或者未访问元素，下一轮pop直接访问
            }
        }
        return result;
    }
}

//统一迭代前序遍历，书写，参考统一中序
class Solution{
    public List<Integer> preorderTraversal(TreeNode root){
        List<Integer> result=new LinkedList<>();//用ArrayList还是LinkedList存没什么区别
        Stack<TreeNode> stack=new Stack<>();
        //同意书写，先无脑压栈root，不需要判空
        if(root!=null)stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node= stack.pop();
            if(node!=null){//没遇上标记
                //前序遍历，中左右，右左中压栈,给中的（栈）上面打上标记
                if(node.right!=null)stack.push(node.right);
                if(node.left!=null)stack.push(node.left);
                stack.push(node);
                stack.push(null);
            }else{
                node=stack.pop();
                result.add(node.val);
            }
        }
        return result;
    }
}
//统一书写后续递归，左右中，用中右左压栈
class Solution{
    public List<Integer> postorderTraversal(TreeNode root){
        List<Integer> result=new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root!=null)stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node=stack.pop();
            if(node!=null){
                stack.push(node);
                stack.push(null);
                if(node.right!=null)stack.push(node.right);
                if(node.left!=null)stack.push(node.left);
            }else{
                node=stack.pop();
                result.add(node.val);
            }
        }
        return result;
    }
}

102. 二叉树的层序遍历

BFS 模板

1
2
3
4
5
6
7
8
9
10
11
12
13
void bfs(TreeNode root) {
    Queue<TreeNode> queue = new ArrayDeque<>();//ArrayDeque或者LinkedList
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll(); //按需result.add
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

DFS模板

1
2
3
4
5
6
void dfs(TreeNode root) {//层次遍历中会用到deep
    if (root == null)return;//空处理，可以在外面
    //按需result.add
    dfs(root.left);
    dfs(root.right);
}

深度优先遍历递归做层次遍历 模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution{
    //[6][4,7][1,3,5,8]
    public List<List<Integer>> result=new ArrayList<List<Integer>>();//全局变量，二维数组储存层次结果
    public List<List<Integer>> levelOrder(TreeNode root){//定义层次遍历,这么写方便切换两种方法
        //迭代外判空
        if(root==null)return result;
        dfs(1, root);
        return result;
    }
    //DFS递归
    public void dfs(Integer deep, TreeNode root){//deep:123,result:0123
        if(result.size()<deep){//
            result.add(new ArrayList<Integer>());//初始size=0,[null]->[null][null]
        }
        //左深度
        result.get(deep-1).add(root.val);
        //deep从开始，result从0开始所以-1
        //[null]->[null,6][null],ArrayList,null不显示，这儿方便理解
        if(root.left!=null)dfs(deep+1,root.left);
        //对6左：[n,6][n]->对4左：[n,6][n,4][n]->对1左：[n,6][n,4][n,1][n]->^->对1右->1结束
        if(root.right!=null)dfs(deep+1,root.right);
        //对4右：[n,6][n,4][n,1][n]->对3左：[n,6][n,4][n,1,3][n]->对3右：^—>3结束->4结束
        //对6右：[n,6][n,4,7][n,1,3][n]->对7左：[n,6][n,4,7][n,1,3,5][n]->对5左^->对5右^->5结束->对7右：[n,6][n,4,7][n,1,3,5,8][n]->^^,结束876
    }
}

广度优先遍历递归做层次遍历，队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//BFS很简单，借用队列就好了
class Solution{
    public List<List<Integer>> result=new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null)return result;
        bfs(root);
        return result;
    }
    public void bfs(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();//queue一维，result二维       
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> itemList=new ArrayList<Integer>();        
            int len=queue.size();
            //将队列中现存的元素都拿出来(也就是获取这一层的节点)，放到临时list中；同时BFS
            while(len>0){//不断遍历队列
                TreeNode node=queue.poll();
                itemList.add(node.val);
                if(node.left!=null)queue.add(node.left);
                if(node.right!=null)queue.add(node.right);
                len--;
            }
            result.add(itemList);
            //将临时list加入最终返回结果中
        }
    }
}

107. 二叉树的层序遍历 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 //bfs
 /*
class Solution {
    public List<List<Integer>> result=new ArrayList<>();
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root==null)return result;
        bfs(root);
        return result;
    }
    private void bfs(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();
        List<List<Integer>> assList=new ArrayList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            //需要临时小列表一段一段存
            //len到头了new
            List<Integer> itemList=new ArrayList<>();
            int len=queue.size();
            while(len>0){
                //每次出队列所有父类节点，上一层结点，入队下一层孩子节点，结束while，line=0
                TreeNode node=queue.poll();
                if(node.left!=null)queue.add(node.left);
                if(node.right!=null)queue.add(node.right);
                itemList.add(node.val);
                len--;
            } 
            assList.add(itemList);//辅助list
        }
        for(int i=assList.size()-1;i>=0;i--){//反转
            result.add(assList.get(i));
        }
    }
}*/
//dfs
class Solution {
    public List<List<Integer>> result=new ArrayList<>();
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root==null)return result;
        dfs(1,root);
        Collections.reverse(result);//反转，理解一下
        return result;
    }
    private void dfs(Integer deep,TreeNode root){
        //先判断有处放吗
        if(result.size()<deep){
            result.add(new ArrayList<Integer>());
        }
        result.get(deep-1).add(root.val);
        if(root.left!=null)dfs(deep+1,root.left);
        if(root.right!=null)dfs(deep+1,root.right);
    }
}

Collections.reverse() Collections.swap()

199. 二叉树的右视图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 //层次遍历，原本是所有都加入到itemList，现在只需要把每行最后一个加到result中就可以,一维,bfs
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        if(root==null)return result;
        queue.add(root);
        while(!queue.isEmpty()){
            int len=queue.size();
            while(len>0){//继续分层，因为只需要最后一个
                TreeNode node=queue.poll();
                if(node.left!=null)queue.add(node.left);
                if(node.right!=null)queue.add(node.right);
                len--;
                if(len==0)result.add(node.val);
            }
        }
        return result;
    }
}

637. 二叉树的层平均值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<Double> result = new ArrayList<>();
        if(root==null)return result;
        //bfs
        queue.add(root);
        while(!queue.isEmpty()){
            int length=queue.size();//需要记录一下
            int len=length;
            Double sum=0.0;
            while(len>0){
                TreeNode node=queue.poll();
                if(node.left!=null)queue.add(node.left);
                if(node.right!=null)queue.add(node.right);
                sum+=node.val;
                len--;
            }
            result.add(sum/length);
        }
        return result;
    }
}

429. N 叉树的层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//ERROR调不明白
class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> list = new ArrayList<>();
        Deque<Node> que = new LinkedList<>();
        if (root == null) {
            return list;
        }
        que.offerLast(root);
        while (!que.isEmpty()) {
            int levelSize = que.size();
            List<Integer> levelList = new ArrayList<>();
            for (int i = 0; i < levelSize; i++) {
                Node poll = que.pollFirst();
                levelList.add(poll.val);
                List<Node> children = poll.children;
                if (children == null || children.size() == 0) {
                    continue;
                }
                for (Node child : children) {
                    if (child != null) {
                        que.offerLast(child);
                    }
                }
            }
            list.add(levelList);
        }
        return list;
    }
}

515. 在每个树行中找最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root==null)return result;
        //bfs
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int len=queue.size();
            int max=queue.peek().val;//有可能是负值
            while(len>0){
                TreeNode node = queue.poll();
                if(node.left!=null)queue.add(node.left);
                if(node.right!=null)queue.add(node.right);
                max= max < node.val ? node.val : max;
                len--;
            }
            result.add(max);
        }
        return result;
    }
}

116. 填充每个节点的下一个右侧节点指针

117. 填充每个节点的下一个右侧节点指针 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public Node connect(Node root) {
        LinkedList<Node> queue = new LinkedList<>();//定义为LinkedList就可以使用get了！
        if(root==null)return root;
        queue.add(root);
        while(!queue.isEmpty()){
            int len=queue.size();//遍历小层
            //返回root，不是结构化的list<list<>>
            //先连起来next
            //connect,建立在层次队列的基础上
            Node node=queue.peek();
            for(int i=1;i<len;i++){
                node.next=queue.get(i);
                node=queue.get(i);
            }
            //bfs
            while(len>0){
                node=queue.poll();
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
                  len--;
            }
        }  
        return root;
    }
}

104. 二叉树的最大深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//层次遍历试试看有几层
class Solution {
    public int maxDepth(TreeNode root) {
        Queue<TreeNode> queue= new LinkedList<>();
        int deep =0;
        if(root==null)return deep;
        //BFS
        queue.add(root);
        while(!queue.isEmpty()){
            int len=queue.size();
            while(len>0){
                TreeNode node = queue.poll();
                if(node.left!=null)queue.add(node.left);
                if(node.right!=null)queue.add(node.right);
                len--;
            }
            deep++;
        }
        return deep;
    }
}

111. 二叉树的最小深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 //层次遍历，最先遍历到左右孩子都为空时候，最小深度
class Solution {
    public int minDepth(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        int deep=0;
        if(root==null)return deep;
        queue.add(root);
        while(!queue.isEmpty()){
            int len = queue.size();
            deep++;
            while(len>0){
                TreeNode node = queue.poll();
                if(node.left!=null)queue.add(node.left);
                if(node.right!=null)queue.add(node.right);
                if(node.left==null&&node.right==null)return deep;
                len--;
            }
        }
        return deep;
    }
}

226. 翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//DFS递归
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null)return root;null也不影响递归
        swapChild(root);//java 中swap不能交换指针
        //位于前序后续都可以，中序不行，会重复遍历
        invertTree(root.left);
        invertTree(root.right);
        
        return root;//主要是为了最后一次有返回值
    }
    private void swapChild(TreeNode node){
        TreeNode temp=node.left;
        node.left=node.right;
        node.right=temp;
    }
}*/
//BFS
class Solution {
    public TreeNode invertTree(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        if(root==null)return root;
        queue.add(root);
        while(!queue.isEmpty()){
            int len=queue.size();
            while(len>0){
                TreeNode node=queue.poll();
                swapChild(node);
                if(node.left!=null)queue.add(node.left);
                if(node.right!=null)queue.add(node.right);
                len--;
            }    
        }   
        return root;
    }
    private void swapChild(TreeNode node){
        TreeNode temp=node.left;
        node.left=node.right;
        node.right=temp;
    }
 }

12 10大排序算法

欢迎关注我的其它发布渠道