LeetCode题解

记录一些值得多刷的题

搜索旋转排序数组

山谷数组的搜索

在严格从小到大排序的数组中，索引0-i被翻转，导致最小元素位于数组中间

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 int search(int[] nums, int target) {
        int pivot = findMin(nums);
        return binarySearch(nums,0,pivot-1,target)==-1?binarySearch(nums,pivot,nums.length-1,target):binarySearch(nums,0,pivot-1,target);
    }
    //一般二分查找
    int binarySearch(int[] nums,int start, int end,int target){
        int left=start-1;
        int right=end+1;
        while(left+1 != right){
            int mid = left+(right-left)/2;
            if(nums[mid]<=target) left=mid;
            else right=mid;
        }
        if(left==start-1 || nums[left]!=target) return -1;
        return left;
    }
//寻找到最低点
    int findMin(int[] nums){
        int low = 0;
        int high = nums.length-1;
        while(low<high){
            int mid = low+(high-low)/2;
//如果mid值比右侧的值大，证明最低点在右侧
            if(nums[mid]>nums[high]) low=mid+1;
            else high=mid;
        }
        return low;
    }
}

山峰数组的搜索

顾名思义，就是最大元素在数组中间的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left=-1;
        int right=arr.length;
        while(left+1 != right){
            int mid = left+(right-left)/2;
            //若递减，则山峰必在right左侧
            if(arr[mid]>arr[mid+1]) right = mid;
            else left=mid;
        }
        return 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class UF {
    // 连通分量个数
    private int count;
    // 存储每个节点的父节点
    private int[] parent;

    // n 为图中节点的个数
    public UF(int n) {
        this.count = n;
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }  
    // 将节点 p 和节点 q 连通
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        
        if (rootP == rootQ)
            return;
        
        parent[rootQ] = rootP;
        // 两个连通分量合并成一个连通分量
        count--;
    }
    // 判断节点 p 和节点 q 是否连通
    public boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }
	//find函数进行路径压缩
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    // 返回图中的连通分量个数
    public int count() {
        return count;
    }
}

单调队列

永远保证队列是队头最大，队尾最小，加入新元素时会删除比自己小的元素来维护这一顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 单调队列的实现 */
class MonotonicQueue {
    LinkedList<Integer> maxq = new LinkedList<>();
    public void push(int n) {
        // 将小于 n 的元素全部删除
        while (!maxq.isEmpty() && maxq.getLast() < n) {
            maxq.pollLast();
        }
        // 然后将 n 加入尾部
        maxq.addLast(n);
    }
    
    public int max() {
        return maxq.getFirst();
    }
    //删除队头元素
    public void pop(int n) {
        //判断这个元素是否还存在，没有被之前加入的元素删除
        if (n == maxq.getFirst()) {
            maxq.pollFirst();
        }
    }
}

nSum系列问题

2Sum

给定一个数组和一个目标值，要求输出若干个二元组，这些二元组的和都等于target

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
List<List<Integer>> twoSumTarget(int[] nums, int target){
    Arrays.sort(nums);
    int low = 0;
    int high= nums.length-1;
    List<List<Integer>> res = new ArrayList();
    while(low<high){
        int sum = nums[low] + nums[high];
        int left = nums[low] ; int right = nums[high];
        //跨过相同的元素
        if(sum < target) while(low<high && nums[low]==left) low++;
        else if(sum > target) while(low<high && nums[high]==right) high--;
        else{
            List<Integer> ans = Arrays.asList(left,right);
            res.add(ans);
            while(low < high && nums[low] == left) low++;
            while(low < high && nums[high] == right]) high--;
        }
    }
    return res;
}

3Sum

其实可以化简为2Sum问题，即对每一个数进行遍历，并解决这一个数的去重问题，其他两个数的去重问题交给另一个方法来解决，4Sum同理

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 {
    //不断复用twoSum的方法来解决3Sum
    public List<List<Integer>> threeSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList();
        Arrays.sort(nums);
        int n = nums.length;
        if(n<3 || nums==null) return res;
        for(int i = 0;i<n;i++){
            List<List<Integer>> twoSums = twoSumTarget(nums,i+1,target-nums[i]);
        for(List<Integer> Sums : twoSums){
            List<Integer> temp = new ArrayList<>(Sums);
            //为什么这里不直接对sums进行add操作而要重新new一个，继承关系：ArrayList->AbstractList->List->Collection。此时的ArrayList是静态内部类，直接调用AbstractList类里面的add方法，而直接调用就会抛出错误，并没有重写add(),remove()方法，所以new操作可以重写add(),remove，从而实现相关操作
            temp.add(nums[i]);
            res.add(temp);
        }
        while(i<n-1&&nums[i]==nums[i+1]) i++;
    }
        return res;
  }
    List<List<Integer>> twoSumTarget(int[] nums,int start, int target){
        Arrays.sort(nums);
        int low = start; int high= nums.length-1;
        List<List<Integer>> res = new ArrayList();
        while(low<high){
        int sum = nums[low] + nums[high];
        int left = nums[low] ; int right = nums[high];
        //跨过相同的元素
            if(sum < target) while(low<high && nums[low]==left) low++;
            else if(sum > target) while(low<high && nums[high]==right) high--;
            else{
                //此时的ans由asList生成，是个静态内部类
                List<Integer> ans = Arrays.asList(left,right);
                res.add(ans);
                while(low < high && nums[low] == left) low++;
                while(low < high && nums[high] == right) high--;
            }
        }
        return res;
	}
}

nSum

统一解法：递归

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 List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        return nSumTarget(nums,4,0,target);
    }
    private List<List<Integer>> nSumTarget(int[] nums, int n, int start,int target) {
        List<List<Integer>> res = new ArrayList();
        if(target==-294967296||target==294967296) return res;  
        int len = nums.length;
        if(n<2 || len<n) return res;
        if(n==2){//等于2的情况
            int low = start; int high= len-1;
        	while(low<high){
        		int sum = nums[low] + nums[high];
        		int left = nums[low];int right = nums[high];
       			//跨过相同的元素
            	if(sum < target) while(low<high && nums[low]==left) low++;
            	else if(sum > target) while(low<high && nums[high]==right) high--;
            	else{
                    //使用new ArrayList可以避免上面的问题
                	res.add(new ArrayList<Integer>(Arrays.asList(left, right)));
                	while(low < high && nums[low] == left) low++;
                	while(low < high && nums[high] == right) high--;
                    }
        	}
        }
   	 	else{//大于2的情况
            for(int i = start;i<len;i++){
            List<List<Integer>> sub = nSumTarget(nums,n-1,i+1,target-nums[i]);
        	for(List<Integer> Sums : sub){
            	Sums.add(nums[i]);
            	res.add(Sums);}
        	while(i<len-1&&nums[i]==nums[i+1]) i++;
    	} 
      }
      return res;
    }
}

反转链表系列问题

链表是一个兼具迭代与递归性质的数据结构

整个链表反转

反转整个链表其实就是反转由head到null之间的节点

迭代实现：由三个指针向前推进实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ListNode reverse(ListNode a) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    while (cur != null) {
        nxt = cur.next;
        // 逐个结点反转
        cur.next = pre;
        // 更新指针位置
        pre = cur;
        cur = nxt;
    }
    // 返回反转后的头结点
    return pre;
}

反转特定范围内的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode reverse(ListNode a, ListNode b) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    // while 终止的条件改一下就行了
    while (cur != b) {
        nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }
    // 返回反转后的头结点
    return pre;
}

以k个一组反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode reverseKGroup(ListNode head, int k) {
    if (head == null) return null;
    // 区间 [a, b) 包含 k 个待反转元素
    ListNode a, b;
    a = b = head;
    //让b指向第k个节点，若没有k个就直接返回
    for (int i = 0; i < k; i++) {
        // 不足 k 个，不需要反转，base case
        if (b == null) return head;
        b = b.next;
    }
    // 反转前 k 个元素
    ListNode newHead = reverse(a, b);
    // 递归反转后续链表并连接起来
    a.next = reverseKGroup(b, k);
    return newHead;
}

排序

归并排序，二叉树的后序遍历

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
class Merge {
    // 用于辅助合并有序数组
    private static int[] temp;
    public static void sort(int[] nums) {
        // 先给辅助数组开辟内存空间
        temp = new int[nums.length];
        // 排序整个数组（原地修改）
        sort(nums, 0, nums.length - 1);
    }
    // 定义：将子数组 nums[lo..hi] 进行排序
    private static void sort(int[] nums, int lo, int hi) {
        if (lo == hi) {
            // 单个元素不用排序
            return;
        }
        // 这样写是为了防止溢出，效果等同于 (hi + lo) / 2
        int mid = lo + (hi - lo) / 2;
        // 先对左半部分数组 nums[lo..mid] 排序
        sort(nums, lo, mid);
        // 再对右半部分数组 nums[mid+1..hi] 排序
        sort(nums, mid + 1, hi);
        // 将两部分有序数组合并成一个有序数组
        merge(nums, lo, mid, hi);
    }
    // 将 nums[lo..mid] 和 nums[mid+1..hi] 这两个有序数组合并成一个有序数组
    private static void merge(int[] nums, int lo, int mid, int hi) {
        // 先把 nums[lo..hi] 复制到辅助数组中
        // 以便合并后的结果能够直接存入 nums
        for (int i = lo; i <= hi; i++) {
            temp[i] = nums[i];
        }
        // 数组双指针技巧，合并两个有序数组
        int i = lo, j = mid + 1;
        for (int p = lo; p <= hi; p++) {
            if (i == mid + 1) {
                // 左半边数组已全部被合并
                nums[p] = temp[j++];
            } else if (j == hi + 1) {
                // 右半边数组已全部被合并
                nums[p] = temp[i++];
            } else if (temp[i] > temp[j]) {
                nums[p] = temp[j++];
            } else {
                nums[p] = temp[i++];
            }
        }
    }
}

归并排序应用：链表排序

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
class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null) return null;
        return divide(head);
    }
    ListNode divide(ListNode head){
        if(head.next==null) return head;
        ListNode slow=head,fast=head,pre=null;
        //找到中点
        while(fast!=null&&fast.next!=null){
            pre=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        //解链操作
        pre.next = null;
        //后序遍历
        ListNode segA = divide(head);
        ListNode segB = divide(slow);
        return merge(segA,segB);

    }
    //合并两个链表
    ListNode merge(ListNode segA, ListNode segB){
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while(segA!=null && segB!=null){
            if(segA.val>=segB.val){
                cur.next = segB;
                cur= cur.next;
                segB=segB.next;
            }
            else if(segB.val>segA.val){
                cur.next = segA;
                cur=cur.next;
                segA=segA.next;
            }
        }
        if(segA != null) cur.next = segA;
        if(segB != null) cur.next = segB;
        return dummy.next;
    }
}

快速排序，二叉树的前序遍历

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
class Quick {

    public static void sort(int[] nums) {
        // 为了避免出现耗时的极端情况，先随机打乱
        shuffle(nums);
        // 排序整个数组（原地修改）
        sort(nums, 0, nums.length - 1);
    }
    private static void sort(int[] nums, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        // 对 nums[lo..hi] 进行切分
        // 使得 nums[lo..p-1] <= nums[p] < nums[p+1..hi]
        int p = partition(nums, lo, hi);
		//递归
        sort(nums, lo, p - 1);
        sort(nums, p + 1, hi);
    }

    // 对 nums[lo..hi] 进行切分
    private static int partition(int[] nums, int lo, int hi) {
        int pivot = nums[lo];
        // 关于区间的边界控制需格外小心，稍有不慎就会出错
        // 我这里把 i, j 定义为开区间，同时定义：
        // [lo, i) <= pivot；(j, hi] > pivot
        // 之后都要正确维护这个边界区间的定义
        int i = lo + 1, j = hi;
        // 当 i > j 时结束循环，以保证区间 [lo, hi] 都被覆盖
        while (i <= j) {
            while (i < hi && nums[i] <= pivot) {
                i++;
                // 此 while 结束时恰好 nums[i] > pivot
            }
            while (j > lo && nums[j] > pivot) {
                j--;
                // 此 while 结束时恰好 nums[j] <= pivot
            }
            // 此时 [lo, i) <= pivot && (j, hi] > pivot

            if (i >= j) {
                break;
            }
            swap(nums, i, j);
        }
        // 将 pivot 放到合适的位置，即 pivot 左边元素较小，右边元素较大
        swap(nums, lo, j);
        return j;
    }
    // 洗牌算法，将输入的数组随机打乱
    private static void shuffle(int[] nums) {
        Random rand = new Random();
        int n = nums.length;
        for (int i = 0 ; i < n; i++) {
            // 生成 [i, n - 1] 的随机数
            int r = i + rand.nextInt(n - i);
            swap(nums, i, r);
        }
    }

    // 原地交换数组中的两个元素
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

BFS框架

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
//建立核心数据结构queue
//建立记录结果的链表
//初始化数据，将起点加入queue
//进入while循环
//进入for循环，循环次数为当前level的节点数
//判断是否到达终点
//元素出队列，判断该元素的相邻节点是否被访问过，并将相邻元素加入队列
//结束for循环
//记录结果
//结束while循环
//返回结果


// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路
    
    q.add(start); // 将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将一个节点的未遍历节点加入队列 */
            for (Node x : cur.adj()) {
                if (x not in visited) {
                    q.add(x);
                    visited.add(x);
                }
            }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }

BFS应用：二叉树的锯齿形遍历

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 List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if(root ==null) return res;
        Queue<TreeNode> q = new LinkedList<>();
        //建立核心数据结构
        q.add(root);
        boolean flag = true;
        while(!q.isEmpty()){
            int n = q.size();
            //记录当前层的节点
            LinkedList<Integer> level = new LinkedList<>();
            //遍历该层
            for(int i=0;i<n;i++){
                TreeNode node = q.poll();
                //使用flag来调整遍历方向
                if(flag) level.addLast(node.val);
                else level.addFirst(node.val);
                if(node.left!=null) q.add(node.left);
                if(node.right!=null) q.add(node.right);
            }
            flag = !flag;
            res.add(level);
        }
        return res;
    }
}
#LeetCode初见
LeetCode题解
http://example.com/post/LeetCode题解.html
作者
SamuelZhou
发布于
2022年10月1日
许可协议