^-^
Web开发者｜阅读写作爱好者
利于java选手系统刷的Leetcode-Hot-100题解

[TOC]

  • 题目来源：LeetCode 热题 100 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台
  • 代码来源：刷了多遍所有题目后，参考各种题解，由本人根据自己的java编码习惯,系统化不断优化编码风格而来，整体编码风格成一个体系：比方说变量命名尽量见名知意，每道题的代码结构有相似性、注释丰富、链表题目几乎都会首先新建一个头节点、回溯模版、滑动窗口模版、dfs上下左右的技巧、二分法的技巧…
  • 好处：利于java选手系统刷题，因为所有的代码思维是在一个空间内的，你一看就知道是一个人写的，零散地看每个题目不同人写的题解，风格往往差异很多，新手理解起来会走弯路。

链表

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

img

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

  • intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
  • skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

img

1
2
3
4
5
6
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

img

1
2
3
4
5
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

img

1
2
3
4
5
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

  • listA 中节点数目为 m
  • listB 中节点数目为 n
  • 1 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • 如果 listA 和 listB 没有交点，intersectVal 为 0
  • 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]
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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 基本原理是 两个指针都一步一步走，到底了，就从另一指针 接着走
        // 这样实际上 两条指针的 长度 都一样 都为 a+b+c
        // 那么一定会相遇，最后相遇的节点即是交点
        if(headA == null || headB == null) return null;
        ListNode tempA = headA;
        ListNode tempB = headB;
        while(tempA != tempB) {
            tempA = tempA == null ? headB : tempA.next;
            tempB = tempB == null ? headA : tempB.next;
        }
        return tempA;
    }
}

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

img

1
2
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

img

1
2
输入：head = [1,2]
输出：[2,1]

示例 3：

1
2
输入：head = []
输出：[]

提示：

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000
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
/**
 * 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; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode newHead = head;
        head = head.next;
        newHead.next = null;
        while(head != null) {
            ListNode temp = head;
            head = head.next;
            temp.next = newHead;
            newHead = temp;
        }
        return newHead;
    }
}

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

img

1
2
输入：head = [1,2,2,1]
输出：true

示例 2：

img

1
2
输入：head = [1,2]
输出：false

提示：

  • 链表中节点数目在范围[1, 105] 内
  • 0 <= Node.val <= 9
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
/**
 * 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; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        // O(1)空间复杂度的话
        // 先利用快慢指针 找到中点
        // 接着 把中点往后的链表翻转
        // 最后和表头比较挨个比较即可
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next;
            fast = fast.next;
        }
        // 这个时候slow就是中点
        slow.next = reverse(slow.next);
        slow = slow.next;
        while(slow != null) {
            if(slow.val != head.val) {
                return false;
            }
            slow = slow.next;
            head = head.next;
        }
        return true;
    }

    private ListNode reverse(ListNode head) {

        ListNode pre = null;
        while(head != null) {
            ListNode temp = head;
            head = head.next;
            temp.next = pre;
            pre = temp;
        }
        return pre;
    }
}

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

img

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

img

1
2
3
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

img

1
2
3
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

  • 链表中节点的数目范围是 [0, 104]
  • -105 <= Node.val <= 105
  • pos 为 -1 或者链表中的一个 有效索引 。
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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        // 保证一定至少有两个节点
        if(head == null || head.next == null) return  false;
        ListNode newHead = new ListNode(0, head);
        // 慢指针先走一步
        ListNode slow = newHead.next;
        // 快指针先走两步
        ListNode fast = newHead.next.next;

        while(fast != slow) {
            slow = slow.next;
            fast = fast.next;
            if(fast == null) return false;
            fast = fast.next;
            if(fast == null) return false;
        }
        return true;
        
    }
}

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

img

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

img

1
2
3
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

img

1
2
3
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

  • 链表中节点的数目范围在范围 [0, 104] 内
  • -105 <= Node.val <= 105
  • pos 的值为 -1 或者链表中的一个有效索引
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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return null;
        ListNode newHead = new ListNode(0, head);

        // 找环的话，先都行动一次
        ListNode slow = newHead.next;
        ListNode fast = newHead.next.next;

        while(slow != fast) {
            slow = slow.next;
            fast = fast.next;
            if(fast == null) return null;
            fast = fast.next;
            if(fast == null) return null;
        }
        // 直接放在头结点
        fast = newHead;
        while(slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

img

1
2
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

1
2
输入：l1 = [], l2 = []
输出：[]

示例 3：

1
2
输入：l1 = [], l2 = [0]
输出：[0]

提示：

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        if(list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

2. 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

img

1
2
3
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

1
2
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

1
2
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零
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
/**
 * 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; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) {
            ListNode templ1 = l1;
            while (l1.val >= 10) {
                if(l1.next == null) {
                    l1.next = new ListNode(1);
                } else {
                    l1.next.val++;
                }
                l1.val -= 10;
                l1 = l1.next;
            }
            return templ1;
        }



        l1.val = l1.val + l2.val;
        if(l1.val >= 10)  {
            if(l1.next == null) {
                l1.next = new ListNode(1);
            } else {
                l1.next.val++;
            }
            l1.val -= 10;
        }
        l1.next = addTwoNumbers(l1.next, l2.next);
        return l1;
    }
}

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

img

1
2
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

1
2
输入：head = [1], n = 1
输出：[]

示例 3：

1
2
输入：head = [1,2], n = 1
输出：[1]

提示：

  • 链表中结点的数目为 sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz
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
/**
 * 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; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode newHead = new ListNode();
        newHead.next = head;

        ListNode first = newHead;
        ListNode second = newHead;
        while(n-- > 0) {
            second = second.next;
        }
        while(second.next != null) {
            second = second.next;
            first = first.next;
        }
        first.next = first.next.next;
        return newHead.next;
    }
}

24. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

img

1
2
输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

1
2
输入：head = []
输出：[]

示例 3：

1
2
输入：head = [1]
输出：[1]

提示：

  • 链表中节点的数目在范围 [0, 100] 内
  • 0 <= Node.val <= 100
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
/**
 * 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; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        
        ListNode first = head;
        head = head.next;
        first.next = null;

        ListNode second = head;
        head = head.next;
        second.next = null;

        second.next = first;

        first.next = swapPairs(head);
        
        return second;

    }
}

25. K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

img

1
2
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2：

img

1
2
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

提示：

  • 链表中的节点数目为 n
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000
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
/**
 * 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; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null || k == 1) return head;
        
        ListNode newHead = new ListNode();
        ListNode tail = newHead;
        ListNode left = head;
        
        while(left != null) {
            ListNode tempHead = new ListNode(0, left);
            ListNode slow = tempHead;
            ListNode fast = tempHead;
            int count = 0;
            while(count < k) {
                fast = fast.next;
                if(fast == null) break;
                count++;
            }
            if(count < k) break;
            left = fast.next;
            fast.next = null;
            tail.next = reverse(slow.next);
            tail = slow.next;
            tail.next = null;
        }
        tail.next = left;
        return newHead.next;
    }

    private ListNode reverse(ListNode head) {
        ListNode newHead = head;
        head = head.next;
        newHead.next = null;
        while(head != null) {
            ListNode tempHead = head;
            head = head.next;
            tempHead.next = newHead;
            newHead = tempHead;
        }
        return newHead;
    }
}

138. 随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

  • val：一个表示 Node.val 的整数。
  • random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1：

img

1
2
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

img

1
2
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

img

1
2
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

提示：

  • 0 <= n <= 1000
  • -104 <= Node.val <= 104
  • Node.random 为 null 或指向链表中的节点。
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
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        HashMap<Node, Node> hashMap = new HashMap<>();
        Node tempHead = head;
        while(tempHead != null) {
            hashMap.put(tempHead, new Node(tempHead.val));
            tempHead = tempHead.next;
        }
        tempHead = head;
        while(tempHead != null) {
            hashMap.get(tempHead).next = hashMap.get(tempHead.next);
            hashMap.get(tempHead).random = hashMap.get(tempHead.random);
            tempHead = tempHead.next;
        }
        return hashMap.get(head);
    }
}

148. 排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：

img

1
2
输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

img

1
2
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

1
2
输入：head = []
输出：[]

提示：

  • 链表中节点的数目在范围 [0, 5 * 104] 内
  • -105 <= Node.val <= 105
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
/**
 * 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; }
 * }
 */
class Solution {

    // 记住找中心节点和合并方法，都弄一个头结点就比较稳
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        
        ListNode left = head;
        ListNode middleNode = getMiddle(left);
        ListNode right = middleNode.next;
        middleNode.next = null;
        
        left = sortList(left);
        right = sortList(right);
        ListNode result = merge(left, right);
        return result;
    }

    private ListNode getMiddle(ListNode head) {
        if(head == null || head.next == null) return head;

        // 我这里中心节点需要尽量往前一个，所以弄一个头结点
        ListNode tempHead = new ListNode();
        tempHead.next = head;

        ListNode slow = tempHead;
        ListNode fast = tempHead.next.next;
        
        while(fast != null) {
            slow = slow.next;
            fast = fast.next;
            if(fast == null) break;
            fast = fast.next;
        }
        return slow;
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        // 两个方法都要新弄一个头结点
        ListNode tempHead = new ListNode();
        ListNode tail = tempHead;
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        tail.next = l1 == null ? l2 : l1;
        return tempHead.next;
    }

}

23. 合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

1
2
输入：lists = []
输出：[]

示例 3：

1
2
输入：lists = [[]]
输出：[]

提示：

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] 按 升序 排列
  • lists[i].length 的总和不超过 10^4
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
/**
 * 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; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {

        if(lists == null || lists.length < 1) return null;
        ListNode newHead = new ListNode();
        ListNode tail = newHead;

        // 引入输入有可能很恶心，比如 [[], [1]], 所以先找到合理的长度
        int count = 0;
        for(ListNode list : lists) {
            if(list != null) count++;
        }
        while(count > 0) {
            ListNode tempNode = new ListNode(Integer.MAX_VALUE);
            int tempIndex = -1;
            for(int i = 0; i < lists.length; i++) {
                ListNode tempList = lists[i];
                if(tempList == null) continue;
                if(tempList.val < tempNode.val) {
                    tempNode = tempList;
                    tempIndex = i;
                }
            }
            tail.next = tempNode;
            lists[tempIndex] = lists[tempIndex].next;
            if(lists[tempIndex] == null) {
                count--;
            }
            tail = tail.next;
            tail.next = null;

        } 
        return newHead.next;
    }
}

146. LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • 最多调用 2 * 105 次 get 和 put
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.HashMap;

class LRUCache {
    // 原理就是利用 hashMap 做缓存，再用 带前后指针的链表
    // 访问过/放入过，就立马把该元素放到头部
    // 超过长度就移除末尾的那个元素
    // 小技巧：使用头结点和尾结点
    private HashMap<Integer, LinkNode> cache = new HashMap<>();
    private LinkNode head;
    private LinkNode tail;
    // 当前大小
    private int size;
    // 总的容量
    private int capacity;


    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;

        // 伪头结点 尾结点
        this.head = new LinkNode();
        this.tail = new LinkNode();
        this.head.next = tail;
        this.tail.pre = head;
    }
    
    public int get(int key) {
        LinkNode node = this.cache.get(key);
        if(node == null) {
            return -1;
        }
        // 被访问了，就放到头部
        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        LinkNode node = this.cache.get(key);
        if(node == null) {
            node = new LinkNode(key, value);
            this.cache.put(key, node);
            addToHead(node);
            ++size;
            if(size > capacity) {
                LinkNode temp = removeTail();
                cache.remove(temp.key);
                --size;
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }

    private LinkNode removeTail() {
        LinkNode node = this.tail.pre;
        removeNode(node);
        return node;
    }

    private void removeNode(LinkNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private void addToHead(LinkNode node) {
        node.next = this.head.next;
        node.pre = this.head;
        this.head.next.pre = node;
        this.head.next = node;
    }

    private void moveToHead(LinkNode node) {
        removeNode(node);
        addToHead(node);
    }

    class LinkNode {
        int key;
        int value;

        LinkNode pre;
        LinkNode next;
        public LinkNode() {}
        public LinkNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

技巧

287. 寻找重复数

给定一个包含n + 1个整数的数组 nums ，其数字都在[1, n]范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设nums只有 一个重复的整数 ，返回这个重复的数 。

你设计的解决方案必须 不修改数组nums且只用常量级O(1)的额外空间。

示例 1：

输入：nums = [1,3,4,2,2]

输出：2

示例 2：

输入：nums = [3,1,3,4,2]

输出：3

示例 3 :

输入：nums = [3,3,3,3,3]

输出：3

提示：

  • 1 <= n <= 105
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • nums 中只有一个整数出现两次或多次，其余整数均只出现一次
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 findDuplicate(int[] nums) {
        // 往循环链表想
        int slow = nums[0];
        int fast = nums[slow];

        while(slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
            fast = nums[fast];
        }
        // 确认有环后，是把快指针放在开头，然后两个都一步一步走
        fast = 0;
        while(slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return fast;
    }
}
  1. 往循环链表联想
  2. 根据访问熟悉顺序可以发现，这个访问顺序是一条循环链表，且这条循环链表循环的部分第一个节点，即是我们要找的重复的数
  3. 慢指针一开始就放在第一个真正节点，算作走了一步，快指针一开始就放在第二个真正节点，算作走了两步，然后快慢指针按照自己的节奏走
  4. 那么找到循环链表的循环部分的第一个节点的步骤：
    1. 快慢指针确认有环（这道题必定有环）
    2. 将快指针放到头结点（不要放在第一个真正节点了，这样做代表多走了一步），慢指针不动放在上一步确认有环的停留位置
    3. 快慢指针皆一步一步走，相同即为所求点

75.颜色分类

给定一个包含红色、白色和蓝色、共n个元素的数组nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数0、1和2分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]

输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]

输出：[0,1,2]

提示：

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] 为 0、1 或 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.Arrays;

class Solution {
    public void sortColors(int[] nums) {
        int[] data = new int[3];
        Arrays.stream(nums).forEach(num -> {data[num]++;});
        int index = 0;
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < data[i]; j++) {
                nums[index++] = i;
            }
        }
    }
}

学习下stream流简便写法吧

31.下一个排列

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

  • 例如，arr =[1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

  • 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
  • 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
  • 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组nums，找出nums的下一个排列。

必须原地算法修改，只允许使用额外常数空间。

示例 1：

输入：nums = [1,2,3]

输出：[1,3,2]

示例 2：

输入：nums = [3,2,1]

输出：[1,2,3]

示例 3：

输入：nums = [1,1,5]

输出：[1,5,1]

提示：

  • 1 <= nums.length <= 100

  • 0 <= nums[i] <= 100

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 {
    // 举例如：12354 需要得到下一个排列是 12435
    // 分以下三步 
    // 1.从尾到头，找到第一个升序相邻对 position 和 position+1 , 即 12354 找到 3 和 5
    // 2.从position位置到尾，找到第一个大于position的数来交换，即 3 和 4 交换，12354 变为  12453
    // 3.从position+1 位置到尾，进行排序，使得剩余的尾部从小到大，达到最小状态，即排序 53 后 12453 变为  12435
    public void nextPermutation(int[] nums) {
        if(nums == null || nums.length == 1) return;
        int position = -1;
        // 第一步找到position
        for(int i = nums.length - 2; i >= 0; i--) {
            if(nums[i] < nums[i+1]) {
                position = i;
                break;
            }
        }
        if(position == -1) {
            // 说明一直是降序
            Arrays.sort(nums);
            return;
        }
        // 第二步找到尾部第一个大于nums[position]的数交换
        for(int i = nums.length - 1; i > position; i--) {
            if(nums[i] > nums[position]) {
                int temp = nums[i];
                nums[i] = nums[position];
                nums[position] = temp;
                break;
            }
        }
        // 第三步，排序 postion + 1 到尾部
      	// 这里编码的时候出过错，得排序 position + 1 的位置，写快了，容易忘了是position下一个位置
        Arrays.sort(nums, position + 1, nums.length);
    }
}

核心的思路就是：下一个排列，意味着尽量在尾部找更好，找到该变换的位置，接着找到这个位置代表的数往后面第一个大的数交换，随后排序这个位置往后的部分即可以达到题目所求。

  1. 第一步从尾部往前找到第一个升序相邻对
    1. 有这样的升序相邻对，意味着，这样才能通过变化，找到更大的数，如果找不到，就说明就是个降序数，下一个排列就是从小到大
    2. 第一个：因为我们找的是下一个排列，所以越靠近尾部越好
    3. 相邻对：因为判断相邻就能表示尾部可以变化来达到题意，至于到底交换哪个更大的数，到第二步去完成。
  2. 第二步找到尾部第一个大于nums[position]的数，从尾部往前循环第一个大的数就是，这是因为在第一步找的就是第一个升序相邻对，这个标准意味着，从尾部往前循环的话，不会出现这个第一个大的数在中间的情况。
  3. 第三步 只需要排序 剩余的尾部，达到下一个排序的要求

136.只出现一次的数字

给你一个非空整数数组nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

输入：nums = [2,2,1]

输出：1

示例 2 ：

输入：nums = [4,1,2,1,2]

输出：4

示例 3 ：

输入：nums = [1]

输出：1

提示：

  • 1 <= nums.length <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • 除了某个元素只出现一次以外，其余每个元素均出现两次。
1
2
3
4
5
6
7
class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for(int num : nums) result ^= num;
        return result;
    }
}

169. 多数元素

给定一个大小为n的数组nums，返回其中的多数元素。多数元素是指在数组中出现次数大于⌊n/2⌋的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]

输出：3示例 2：

输入：nums = [2,2,1,1,1,2,2]

输出：2

提示：

  • n == nums.length
  • 1 <= n <= 5 * 104
  • 109 <= nums[i] <= 109
hashMap解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.HashMap;

class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(hashMap.containsKey(nums[i])) {
                hashMap.put(nums[i], hashMap.get(nums[i]) + 1);
                if(hashMap.get(nums[i]) > nums.length / 2) {
                    return nums[i];
                }
            } else {
                hashMap.put(nums[i], 1);
            }
        }
        return nums[0];
    }
}
进阶：摩尔投票解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    // 通常可以用hashMap，学习下空间复杂度O(1)的摩尔投票
    public int majorityElement(int[] nums) {
        int mayNum = 0, votes = 0;
        for(int num : nums) {
            // 每一轮循环都会去判断votes是否等于0
            // 等于0意味着可以这是新选择一个mayNum
            if(votes == 0) mayNum = num;
            // 找众数，只有mayNum才去+1，否则都-1
            votes += (num == mayNum ? 1 : -1);
            // 不断地重新判断mayNum
        }
        return mayNum;
    }
}

多维动态规划

62.不同路径

一个机器人位于一个m x n网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7

输出：28

示例 2：

输入：m = 3, n = 2

输出：3

解释：

从左上角开始，总共有 3 条路径可以到达右下角。

  1. 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3

输出：28

示例 4：

输入：m = 3, n = 3

输出：6 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int uniquePaths(int m, int n) {
        int rows = m;
        int cols = n;
        int[][] dp = new int[rows][cols];
        for(int row = 0; row < rows; row++) {
            for(int col = 0; col < cols; col++) {
                if(row == 0 || col == 0) {
                    dp[row][col] = 1;
                } else {
                    dp[row][col] = dp[row-1][col] + dp[row][col-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
}

64. 最小路径和

给定一个包含非负整数的 mxn 网格grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]

输出：7

解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]

输出：12

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 200
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 int minPathSum(int[][] grid) {

        int rows = grid.length;
        int cols = grid[0].length;
        int[][] dp = new int[rows][cols];

        for(int row = 0; row < rows; row++) {
            for(int col = 0; col < cols; col++) {
                if(row == 0 && col == 0) {
                    dp[row][col] = grid[row][col];
                } else if(row == 0 || col == 0) {
                    if(row == 0) {
                        dp[row][col] = dp[row][col-1] + grid[row][col];
                    } else {
                        dp[row][col] = dp[row-1][col] + grid[row][col];
                    }
                } else {
                    dp[row][col] = Math.min(dp[row-1][col], dp[row][col-1]);
                    dp[row][col] += grid[row][col];
                }
            }
        }
        return dp[rows-1][cols-1];
    }
}

5.最长回文子串

给你一个字符串 s，找到 s 中最长的 回文子串。

示例 1：

输入：s = “babad”

输出：“bab”

解释：“aba” 同样是符合题意的答案。

示例 2：

输入：s = “cbbd”

输出：“bb”

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成
中心扩散解法
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
class Solution {
    public String longestPalindrome(String s) {

        String result = "";
        for(int i = 0; i < s.length(); i++) {
            // 以单个为中心的回文串，计算长度
            String tempResult = get(s, i, i);
            if(i < s.length() - 1 && s.charAt(i) == s.charAt(i+1)) {
                // 如果是成对为中心的回文串，去计算长度
                String tempResult1 = get(s, i, i + 1);
                tempResult = tempResult.length() > tempResult1.length() ? tempResult : tempResult1;
            }

            if(tempResult.length() > result.length()) {
                result = tempResult;
            }
        }
        return result;
    }

    private String get(String s, int left, int right) {
   
        while(left - 1 >= 0 && right + 1 < s.length()) {
            if(s.charAt(left - 1) != s.charAt(right + 1)) {
                break;
            }
            left--;
            right++;
        }
        return s.substring(left, right + 1);
    }
}
dp解法

学习下动态规划解决方法

boolean dp[l][r] 表示字符串从 i 到 j 这段是否为回文。试想如果 dp[l][r]=true，我们要判断 dp[l-1][r+1] 是否为回文。只需要判断字符串在(l-1)和（r+1)两个位置是否为相同的字符

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
public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        int strLen = s.length();
        int maxStart = 0;  //最长回文串的起点
        int maxEnd = 0;    //最长回文串的终点
        int maxLen = 1;  //最长回文串的长度

        boolean[][] dp = new boolean[strLen][strLen];

        for (int r = 1; r < strLen; r++) {
            for (int l = 0; l < r; l++) {
                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
                    dp[l][r] = true;
                    if (r - l + 1 > maxLen) {
                        maxLen = r - l + 1;
                        maxStart = l;
                        maxEnd = r;

                    }
                }

            }

        }
        return s.substring(maxStart, maxEnd + 1);

    }

1143. 最长公共子序列

给定两个字符串text1和text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

  • 例如，”ace” 是”abcde”的子序列，但 “aec” 不是”abcde” 的子序列。

两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = “abcde”, text2 = “ace”

输出：3

解释：最长公共子序列是 “ace” ，它的长度为 3 。

示例 2：

输入：text1 = “abc”, text2 = “abc”

输出：3

解释：最长公共子序列是 “abc” ，它的长度为 3 。

示例 3：

输入：text1 = “abc”, text2 = “def”

输出：0

解释：两个字符串没有公共子序列，返回 0 。

提示：

  • 1 <= text1.length, text2.length <= 1000
  • text1 和 text2 仅由小写英文字符组成。
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 longestCommonSubsequence(String text1, String text2) {

        // 使用二维数组来表示，dp[i][j] 表示 到第一个字符串 的第i个位置 到第二个字符串 的 第j个位置的 匹配情况
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];

        for(int i = 1; i <= text1.length(); i++) {
            for(int j = 1; j <= text2.length(); j++) {
                if(text1.charAt(i-1) == text2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }


}

72.编辑距离

给你两个单词word1和 word2， 请返回将 word1转换成word2所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

示例 1：

输入：word1 = “horse”, word2 = “ros”

输出：3

解释：

horse -> rorse (将 ‘h’ 替换为 ‘r’)

rorse -> rose (删除 ‘r’)

rose -> ros (删除 ‘e’)

示例 2：

输入：word1 = “intention”, word2 = “execution”

输出：5

解释：

intention -> inention (删除 ‘t’)

inention -> enention (将 ‘i’ 替换为 ‘e’)

enention -> exention (将 ‘n’ 替换为 ‘x’)

exention -> exection (将 ‘n’ 替换为 ‘c’)

exection -> execution (插入 ‘u’)

提示：

  • 0 <= word1.length, word2.length <= 500
  • word1 和 word2 由小写英文字母组成
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
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        // dp[2][3] 的含义 就是 word1 的 前2位 到 word2 的 前3位，要两者相同的 最小变化数目
        int[][] dp = new int[m + 1][n + 1];

        for(int i = 0; i <= m; i++) {
            for(int j = 0; j <= n; j++) {
                // 一方为 0 的情况，也就是长度为0，那么自然另一方就需要 添加操作，添加到这个长度
                if(i == 0) {
                    dp[i][j] = j;
                } else if(j == 0) {
                    dp[i][j] = i;
                } else {
                    // 如果不相同那么需要 进行一步 操作来相同
                    int changeFlag = word1.charAt(i-1) == word2.charAt(j-1) ? 0 : 1;
                    
                    // 当changeFlag = 0  dp[i-1][j-1] + changeFlag = dp[i-1][j-1] 代表相同，不需要操作
                    // 当changeFlag = 1  dp[i-1][j-1] + changeFlag = dp[i-1][j-1] 代表编辑操作
                    // dp[i-1][j] + 1 代表 插入操作
                    // dp[i][j-1] + 1 代表 删除操作，dp[i][j]依然保存的是dp[i][j-1]的值 再加上做一次删除操作的 1 步
                    // 以上的所有判断，都会保存下来状态，下一轮都会用来判断
                    dp[i][j] = Math.min(dp[i-1][j-1] + changeFlag,
                                            Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1));
                }
            }
        }
        return dp[m][n];
    }
}

动态规划

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

1
2
3
4
5
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

1
2
3
4
5
6
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

  • 1 <= n <= 45
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int climbStairs(int n) {
        if(n <= 2) return n;
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}

118. 杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

1
2
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

1
2
输入: numRows = 1
输出: [[1]]

提示:

  • 1 <= numRows <= 30
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<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(List.of(1));
        if(numRows == 1) return result;
        result.add(List.of(1, 1));
        if(numRows == 2) return result;

        for(int i = 3; i <= numRows; i++) {
            List<Integer> pre = result.get(i - 2);
            List<Integer> newList = new ArrayList<>();
            for(int j = 0; j < i; j++) {
                if(j == 0 || j == i-1) {
                    newList.add(1);
                } else {
                    newList.add(pre.get(j-1) + pre.get(j));
                }
            }
            result.add(newList);
        }
        return result;
    }
}

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

1
2
3
4
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

1
2
3
4
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int rob(int[] nums) {
        
        int[] dp = new int[nums.length];
        for(int i = 0; i < nums.length; i++) {
            if(i == 0) {
                dp[i] = nums[i];
            } else if(i == 1) {
                dp[i] = Math.max(nums[0], nums[1]);
            } else {
                dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
            }
        }
        return dp[nums.length - 1];
    }
}

279. 完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

1
2
3
输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

1
2
3
输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

  • 1 <= n <= 104
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int numSquares(int n) {
        if(n == 0) return 0;
        int[] dp = new int[n+1];

        for(int num = 1; num <= n; num++) {
            dp[num] = num;
            for(int j = 1; j * j <= num; j++) {
                dp[num] = Math.min(dp[num], dp[num - j*j] + 1);
            }
        }
        return dp[n];
    }
}

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

1
2
3
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

1
2
输入：coins = [2], amount = 3
输出：-1

示例 3：

1
2
输入：coins = [1], amount = 0
输出：0

提示：

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104
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
import java.util.Arrays;

class Solution {
    public int coinChange(int[] coins, int amount) {
        // 入参判断
        if(coins == null || coins.length < 1) {
            return -1;
        }
        // dp[amount]代表的含义是 当前金额amount 最少的硬币数目
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for(int i = 1; i <= amount; i++) {
            // i 作为 金额来进行遍历
            for(int coin : coins) {
                if(i >= coin) {
                    // 当 i 这个金额比 硬币的数额更大时，当然可以进行拼凑
                    // 但是因为我们要找的是最小的数额，所以去找小的
                    dp[i] = Math.min(dp[i], dp[i-coin] + 1);
                }
            }
        }

        // 没有发生变化，自然是无法构造
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
}

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

1
2
3
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

1
2
3
4
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

1
2
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示：

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s 和 wordDict[i] 仅由小写英文字母组成
  • wordDict 中的所有字符串 互不相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;

        for(int i = 1; i <= s.length(); i++) {
            for(String word : wordDict) {
                if(i >= word.length() && s.substring(i - word.length(), i).equals(word)) {
                    if(dp[i-word.length()]) {
                        // 之前可以划分，这里自然才能存储可以划分的状态
                        dp[i] = true;
                    }
                }
            }
        }
        return dp[s.length()];
    }
}

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

1
2
3
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

1
2
输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

1
2
输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104
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 lengthOfLIS(int[] nums) {

        // 动态规划
        // 一维数组 的 dp[2] 代表 nums[2]这个数 当前 最长序列数
        // 那么自然 到了 dp[i]，去找到 从 do[0] 到dp[j](j<i) 的最大数 加 1 即是新的最长

        if(nums.length == 1) {
            return 1;
        }
        int[] dp = new int[nums.length];
        // 先直接赋值为1，因为最短肯定为1
        Arrays.fill(dp, 1);
      	// 这道题的dp数组并没有直接存储结果，而是每个位置的最长，这个最长有可能在中间
        int max = 0;

        for(int i = 0; i <  nums.length; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[j] < nums[i]) {
                    dp[i] =  Math.max(dp[i], dp[j] + 1);
                }
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }
}

152. 乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

示例 1:

1
2
3
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

1
2
3
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

提示:

  • 1 <= nums.length <= 2 * 104
  • -10 <= nums[i] <= 10
  • nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int maxProduct(int[] nums) {

        int result = nums[0];
        int positiveMax = nums[0];
        int negativeMin = nums[0]; // 始终存最小的负数
        
        for(int i = 1; i < nums.length; i++) {
            if(nums[i] < 0) {
                // 小于0，则之前存的负数乘起来，将会变大,之前存的正数乘起来，将会变小
                int temp = positiveMax;
                positiveMax = negativeMin;
                negativeMin = temp;
            }
            // 这里这样就能保证 从nums[i] 开始，还是 继续连续积 positiveMax*nums[i] | negativeMin*nums[i]
            positiveMax = Math.max(nums[i], positiveMax*nums[i]);
            negativeMin = Math.min(nums[i], negativeMin*nums[i]);
            result = Math.max(result, positiveMax);
        }
        
        return result;

    }
}

416. 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

1
2
3
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

1
2
3
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100
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
import java.util.Arrays;

class Solution {
    public boolean canPartition(int[] nums) {
        // 先根据题意进行处理
        // 拿到总和，并且总和为偶数，才能符合题意
        int sum = Arrays.stream(nums).sum();
        if(sum % 2 != 0) {
            return false;
        }
        // 要去构造dp，那么只需要找到一半的数
        int target = sum / 2;
        // dp[2][14]代表的含义是 第2个数，放了过后，还剩多少target
        boolean[][] dp = new boolean[nums.length + 1][target + 1];
        dp[0][0] = true;
        for(int i = 1; i <= nums.length; i++) {
            for(int j = 0; j <= target; j++) {
                // j 代表的是剩余的target
                if(j < nums[i-1]) {
                    // 剩余的target比数小，说明放不下了,放不下就直接拿之前的值
                    dp[i][j] = dp[i-1][j];
                } else {
                    // 说明放得下
                    dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i-1]];
                }
            }
        }
        return dp[nums.length][target];
    }
}

32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

1
2
3
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

1
2
3
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

1
2
输入：s = ""
输出：0

提示：

  • 0 <= s.length <= 3 * 104
  • s[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
class Solution {
    public int longestValidParentheses(String s) {
        int max = 0;
        Stack<Integer> stack = new Stack<>();

        // 先放一个-1，万一一开始就碰到')'
        // 而且放-1 ，后面计算长度也最合适-1， 0， 1 因为要是一开始就碰到 '()'
        // 后面计算 i - stack.peek() 才能直接得到正确的长度
        stack.push(-1);

        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '(') {
                // 左括号压栈
                stack.push(i);
            } else {
                // 右括号出栈
                stack.pop();
                if(stack.empty()) {
                    // 为空了都要压一个，防止之后连续的')'报错
                    stack.push(i);
                } else {
                    // 出了一对，就去判断长度
                    // stack.peek() 存储的就是之前的左边下标
                    // 自然 i - stack.peek() 就能得到长度
                    max = Math.max(max, i - stack.peek());
                }
            }
        }
        return max;
    }
}

动态规划
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
class Solution {
    public int longestValidParentheses(String s) {
        int max = 0;
        // 这里加上一个空格，增加长度，是因为后面有 i-2 的操作，防止越界，比如 s= "()"
        s = " " + s;

        // dp[3] 代表 字符串前3个字符的最长有效括号
        int dp[] = new int[s.length()];
        
        // 直接从2开始,就是第二个字符开始判断就行, 第一个字符单独无论如何成为不了有效括号
        for(int i = 2; i < s.length(); i++) {
            if(s.charAt(i) == '(') {
                // 如果是 左括号 必然构不成有效括号
                dp[i] = 0;
            } else {
                // 如果是右括号
                if(s.charAt(i-1) == '(') {
                    // .....() 也就是前一位是左括号，即构成一对,长度为2, 再加上往前找最大有效
                    dp[i] = dp[i-2] + 2;
                } else if(s.charAt(i - dp[i-1] - 1) == '(') {
                    // ((....)) 也就是前一位时右括号，那么去判断 最左边是否是左括号
                    // 是的话，再加上往前最大有效
                    dp[i] = dp[i-1] + 2 + dp[i- dp[i-1] - 2];
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;

    }
}

贪心算法

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

1
2
3
4
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    
    // 本身不难，关键是解法的代码写法思想
    public int maxProfit(int[] prices) {
        int buyMin = Integer.MIN_VALUE;
        int sellGet = 0;
        for(int i = 0; i < prices.length; i++) {
            // 越小的正数，其负数反而越大，所以我们找最大的那个负数，即是我们要的最小的正数
            buyMin = Math.max(buyMin, -prices[i]);
            // 所以 sellGet要么为 0 要么一定是 之前所保存的最小的数，拿当前的数去卖，保留最大的
            // 自然最后要的就是最大的
            sellGet = Math.max(sellGet, prices[i] + buyMin);
        }
        return sellGet;
    }
}

总的来说，即是找到最小的，并且在尾部找到最大的，这样便可以实现低买高卖。

55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

1
2
3
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

1
2
3
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 105
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean canJump(int[] nums) {
        
        // 题目说了，你最初位于数组的 第一个下标
        int maxRightIndex = nums[0];

        for(int i = 1; i < nums.length; i++) {
            // 这里注意 i <= maxRightIndex ，因为有可能前面一部分，始终停止了 比如 3 2 1 0 4  始终停止在了0位 无法达到4
            if(i > maxRightIndex) {
                break;
            }
            maxRightIndex = Math.max(maxRightIndex, i + nums[i]);
        }
        return maxRightIndex >= nums.length - 1;
    }
}

45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

  • 0 <= j <= nums[i]
  • i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

1
2
3
4
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

1
2
输入: nums = [2,3,0,1,4]
输出: 2

提示:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000
  • 题目保证可以到达 nums[n-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int jump(int[] nums) {
        
        // currentRight 表示当前 这一步 能跳的最远边界
        int currentRightIndex = 0;
        int maxPostion = 0;
        int steps = 0;

        for(int i = 0; i < nums.length; i++) {
            if(i > currentRightIndex) {
                // 超过了当前跳远的最远距离，需要再跳一次
                currentRightIndex = maxPostion;
                steps++;
            }
            maxPostion = Math.max(maxPostion, i + nums[i]);
        }
        
        return steps;
    }
}

763. 划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

1
2
3
4
5
6
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

示例 2：

1
2
输入：s = "eccbbbbdec"
输出：[10]

提示：

  • 1 <= s.length <= 500
  • s 仅由小写英文字母组成
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
class Solution {
    public List<Integer> partitionLabels(String s) {

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

        // 记录字符最右边的位置
        HashMap<Character, Integer> rightLocationMap = new HashMap<>();
        for(int i = 0; i < s.length(); i++) {
            rightLocationMap.put(s.charAt(i), i);
        }

        int index = 0;
        while(index < s.length()) {
            // 首先拿到 当前字符 的最右位置
            int right = rightLocationMap.get(s.charAt(index));

            for(int left = index + 1; left < right; left++) {
                // 拿到 当前字符的下一个字符 的最右位置
                // 如果 最右位置更大，则去更新为当前区间的更右
                right = Math.max(right, rightLocationMap.get(s.charAt(left)));
            }
            
            result.add(right - index + 1);
            index = right + 1;
        }
        return result;
    }
}

堆

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

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

1
2
输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

1
2
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104
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 int findKthLargest(int[] nums, int k) {
        int start = 0;
        int end = nums.length - 1;
        int targetIndex = nums.length - k;
        while(start < end) {
            int chooseIndex = getPartionIndex(nums, start, end);
            if(chooseIndex == targetIndex) {
                return nums[chooseIndex];
            } else if(chooseIndex < targetIndex) {
                start = chooseIndex + 1;
            } else {
                end = chooseIndex - 1;
            }
        }
        return nums[start];
    }

    private int getPartionIndex(int[] nums, int left, int right) {
        int key = nums[left];
        while(left < right) {
            while(left < right && nums[right] >= key) {
                right--;
            }
            nums[left] = nums[right];
            while(left < right && nums[left] < key) {
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = key;
        return left;
    }

}

347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

1
2
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

1
2
输入: nums = [1], k = 1
输出: [1]

提示：

  • 1 <= nums.length <= 105
  • k 的取值范围是 [1, 数组中不相同的元素的个数]
  • 题目数据保证答案唯一，换句话说，数组中前 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
import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] result = new int[k];
        HashMap<Integer, Node> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(!map.containsKey(nums[i])) {
                map.put(nums[i], new Node(nums[i], 1));
            } else {
                Node temp = map.get(nums[i]);
                temp.count++;
            }
        }

        List<Node> nodeList = map.values().stream().collect(Collectors.toList());
        Collections.sort(nodeList, (a, b) -> {return b.count - a.count;});
        for(int i = 0; i < k; i++) {
            result[i] = nodeList.get(i).num;
        }
        return result;

    }

    class Node {
        public int num;
        public int count;
        public Node(int num, int count) {
            this.num = num;
            this.count = count;
        }
    }


}

295. 数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

  • 例如 arr = [2,3,4] 的中位数是 3 。
  • 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

  • MedianFinder() 初始化 MedianFinder 对象。
  • void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
  • double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

  • -105 <= num <= 105
  • 在调用 findMedian 之前，数据结构中至少有一个元素
  • 最多 5 * 104 次调用 addNum 和 findMedian
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
class MedianFinder {
    
    Queue<Integer> A, B;

    public MedianFinder() {
        A = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
        B = new PriorityQueue<>(); // 小顶堆，保存较大的一半
    }
    
    // 要么 A 和 B 个数一样，要么 B 小顶堆 多一个元素
    public void addNum(int num) {
        if(A.size() != B.size()) {
            // 奇数总个数, 先放小顶堆，再从小顶堆出元素到大顶堆
            B.add(num);
            A.add(B.poll());
        } else {
            // 偶数总个数，先放大顶堆，再从大顶堆出元素到小顶堆
            A.add(num);
            B.add(A.poll());
        }
    }
    
    public double findMedian() {
        return A.size() != B.size() ? B.peek() : ((A.peek() + B.peek()) / 2.0);
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

栈

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

1
2
输入：s = "()"
输出：true

示例 2：

1
2
输入：s = "()[]{}"
输出：true

示例 3：

1
2
输入：s = "(]"
输出：false

提示：

  • 1 <= s.length <= 104
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.LinkedList;

class Solution {
    public boolean isValid(String s) {
        LinkedList<Character> stack = new LinkedList<>();

        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(c == '[' || c == '{' || c == '(') {
                stack.push(c);
            } else {
                if(stack.isEmpty()) return false;
                char top = stack.peek();
                if((c == ']' && top == '[') || (c == ')' && top == '(') || (c == '}' && top == '{') ) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

  • -231 <= val <= 231 - 1
  • pop、top 和 getMin 操作总是在 非空栈 上调用
  • push, pop, top, and getMin最多被调用 3 * 104 次
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
import java.util.LinkedList;

class MinStack {

    private LinkedList<Integer> stack;
    private LinkedList<Integer> minStack;

    public MinStack() {
        stack = new LinkedList<>();
        minStack = new LinkedList<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if(minStack.isEmpty() || minStack.peek() >= val) {
            minStack.push(val);
        } else {
            minStack.push(minStack.peek());
        }
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

1
2
输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

1
2
输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

1
2
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

1
2
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

提示：

  • 1 <= s.length <= 30
  • s 由小写英文字母、数字和方括号 '[]' 组成
  • s 保证是一个 有效 的输入。
  • s 中所有整数的取值范围为 [1, 300]
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 {

    // 3[a2[c3[q]]]2[z]a
    public String decodeString(String s) {
        int tempNum = 0;
        StringBuilder result = new StringBuilder();
        Stack<Integer> numStack = new Stack<>();
        Stack<StringBuilder> resultStack = new Stack<>();

        for(char c : s.toCharArray()){
            if(c == '['){
                // 碰到左括号，说明数字已经收集完毕，记录tempNum 和 当前result，归零。
                numStack.push(tempNum);
                resultStack.push(result);
                tempNum = 0;
                result = new StringBuilder();
            }else if(c ==']'){
                // 出最近的一个左括号入的tempNum, 当前res进行计算不入栈
                int curNum = numStack.pop();
                StringBuilder temp = new StringBuilder();
                for(int i = 0; i < curNum; i++){
                    temp.append(result);
                }
                // 与括号外合并
                result = resultStack.pop().append(temp);

            }else if(c >= '0' && c <= '9'){
                // 如果k是多位数需要x10
                tempNum = c - '0' + tempNum * 10;
            }else{
                // 如果是字母则缓慢添加
                result.append(c);
                
            }
        }
        return result.toString();
    }
}

739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

1
2
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

1
2
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

1
2
输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

  • 1 <= temperatures.length <= 105
  • 30 <= temperatures[i] <= 100
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 int[] dailyTemperatures(int[] temperatures) {
        int[] result = new int[temperatures.length];
        
        // 栈存入还未能得到答案的下标
        // 呈现的效果就是 温度 单调递减的
        // 一遇到 温度 更高的，就出栈填入答案
        LinkedList<Integer> stack = new LinkedList<>();

        for(int i = 0; i < temperatures.length; i++) {
            while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                // 当前的温度 更高 了
                // 说明得到一个答案
                // 一直循环往前填入答案
                result[stack.peek()] = i - stack.poll();    
            }    
            stack.push(i);
        }
        return result;

    }
}

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

img

1
2
3
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

img

1
2
输入： heights = [2,4]
输出： 4

提示：

  • 1 <= heights.length <=105
  • 0 <= heights[i] <= 104
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
class Solution {
    public int largestRectangleArea(int[] heights) {

        if(heights.length == 1) return heights[0];
        int result = 0;
        LinkedList<Integer> stack = new LinkedList<>();

        // 基本原理就是，stack 存储 下标， 每次都遇到新的高度，都往前判断是否更矮了
        // 更矮了意味着，前面的部分有可以确定面积了
        for(int i = 0; i < heights.length; i++) {
            
            while(!stack.isEmpty() && heights[i] < heights[stack.peek()]) {

                // 找到更低的高度了
                int curHeight = heights[stack.poll()];

                while(!stack.isEmpty() && curHeight == heights[stack.peek()]) {
                    // 相同的高度往前继续找
                    stack.poll();
                }

                // 得到宽度 计算面积
                // 注意这里的 i - stack.peek() - 1 ，因为之前一直在出栈，出完毕了相同高度的
                // 这时的stack.peek() 已经不是这个高度的，而是次高度的，所以直接 i- stack.peek() 的话就会多算一个
                int curWidth = stack.isEmpty() ? i : i - stack.peek() - 1;
                result = Math.max(result, curHeight * curWidth);
            }
            stack.push(i);
        }

        // 最后可能还有剩余的元素，用同样的方法往前计算
        while(!stack.isEmpty()) {
            // 既然是剩余的，当前高度直接拿到
            int curHeight = heights[stack.poll()];
            while(!stack.isEmpty() && curHeight == heights[stack.peek()]) {
                // 相同的高度往前继续找
                stack.poll();
            }
            // 得到宽度，剩余的元素，宽度一定为 数组长度，因为第一遍循环走到尾部了
            int curWidth = stack.isEmpty() ? heights.length : heights.length - stack.peek() - 1;
            result = Math.max(result, curHeight * curWidth);
        }
        return result;

    }
}

二分查找

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

1
2
输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

1
2
输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

1
2
输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 为 无重复元素 的 升序 排列数组
  • -104 <= target <= 104
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int 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;
    }
}

74. 搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

  • 每行中的整数从左到右按非严格递增顺序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

img

1
2
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

img

1
2
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -104 <= matrix[i][j], target <= 104
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        
        for(int row = 0; row < rows; row++) {
            for(int col = cols - 1; col >= 0; col--) {
                if(matrix[row][col] == target) {
                    return true;
                } else if(matrix[row][col] < target) {
                    break;
                } else {
                    continue;
                }
            }
        }
        return false;

    }
}

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

1
2
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

1
2
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

1
2
输入：nums = [], target = 0
输出：[-1,-1]

提示：

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums 是一个非递减数组
  • -109 <= target <= 109
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
class Solution {
    public int[] searchRange(int[] nums, int target) {
        
        int[] result = {-1, -1};
        int resultLeftIndex = -1;
        int resultRightIndex = -1;

        int left = 0;
        int right = nums.length - 1;

        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) {
                resultLeftIndex = mid;
                resultRightIndex = mid;
                break;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        if(resultLeftIndex == -1) return result;
        
        int tempLeft = getFromDirection(nums, 0, resultLeftIndex - 1, target, 1);
        int tempRight = getFromDirection(nums, resultRightIndex + 1, nums.length - 1, target, 2);
        if(tempLeft != -1) resultLeftIndex = tempLeft;
        if(tempRight != - 1) resultRightIndex = tempRight;
        result[0] = resultLeftIndex;
        result[1] = resultRightIndex;
        return result;
    }

    private int getFromDirection(int[] nums, int start, int end, int target, int direction) {
        int left = start;
        int right = end;
        int tempResult = -1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) {
                tempResult = mid;
                if(direction == 1) right = mid - 1;
                else left = mid + 1;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return tempResult;
    }

}

33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

1
2
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

1
2
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

1
2
输入：nums = [1], target = 0
输出：-1

提示：

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • nums 中的每个值都 独一无二
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • -104 <= target <= 104
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
class Solution {
    public int search(int[] nums, int target) {
        return search(nums, 0, nums.length - 1, target);
    }

    private int search(int[] nums, int left, int right, int target) {
        if(left > right) return -1;
        int mid = left + (right - left) / 2;
        int result = -1;
        if(nums[mid] == target) return mid;
        
        // 两边都有可能出现

        // 说明左边是增序
        if(nums[mid] > nums[left] && nums[left] <= target && target < nums[mid]) result = binarySearch(nums, left, mid - 1, target);
        else result = search(nums, mid + 1, right, target); // 说明右边有可能出现
        if(result != -1) return result;

        // 说明右边是增序
        if(nums[mid] < nums[right] && nums[mid] < target && target <= nums[right]) result = binarySearch(nums, mid +1, right , target);
        else result = search(nums, left, mid - 1, target);  // 说明左边有可能出现
        return result;
    }

    private int binarySearch(int[] nums, int left, int right, int target) {
        if(left > right) return -1;
        int result = -1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) {
                result = mid;
                break;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

153. 寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

  • 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

1
2
3
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

1
2
3
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。

示例 3：

1
2
3
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

提示：

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums 中的所有整数 互不相同
  • nums 原来是一个升序排序的数组，并进行了 1 至 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
31
32
class Solution {
    
    private int min = Integer.MAX_VALUE;

    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int mid = left + (right - left) / 2;
        min = nums[mid];
        
        findMin(nums, left, mid - 1);
        findMin(nums, mid + 1, right);
        return min;
    }

    private void findMin(int[] nums, int left, int right) {
        if(left > right) {
            return ;
        }
        int mid = left + (right - left) / 2;
        if(nums[mid] >= nums[left]) {
            // 说明左边是增序
            min = Math.min(min, nums[left]);
        }
        findMin(nums, left, mid - 1);
        if(nums[mid] <= nums[right]) {
            // 说明右边是增序
            min = Math.min(min, nums[mid]);
        }
        findMin(nums, mid + 1, right);
    }
}

4. 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

1
2
3
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

1
2
3
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106
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
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 求中位数，因为知道两个数组的长度，实际上就等于求 第 k 大的数
        // 我们要达到一个log(m + n)的时间复杂度，就是每次去过滤 k/2 的量
        // 直到我们求 k == 1 的时候
        int indexFirstK = (nums1.length + nums2.length + 1) / 2;
        int indexSecondK = (nums1.length + nums2.length + 2) / 2;
        return (getKth(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, indexFirstK) +
                getKth(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, indexSecondK)) * 0.5;
    }

    /**
     * 妙在什么地方
     * 第一个是 将中位数 转换为了 第k大
     * 随后 长度总和为奇数自然是 第k大
     * 还要考虑 长度总和为 偶数 自然还要知道 第 k + 1大
     *
     * 进入当前方法，要留意第一个数组为短的数组，可以使得之后的代码复用性高
     * 考虑 第一个数组过滤完的情况
     * 考虑 末端 只需要求 k 为 1 也就是 第 1 大的数的情况，那么自然只需要比较 两个数组的第一个数
     */
    private int getKth(int[] nums1, int start1, int end1,
                       int[] nums2, int start2, int end2,
                       int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;

        // 进入当前方法，要留意第一个数组为短的数组，可以使得之后的代码复用性高
        if(len1 > len2) {
            return getKth(nums2, start2, end2, nums1, start1, end1, k);
        }

        // 考虑 第一个数组过滤完的情况
        if(len1 == 0) {
            return nums2[start2 + k - 1];
        }

        // 考虑 末端 只需要求 k 为 1 也就是 第 1 大的数的情况，那么自然只需要比较 两个数组的第一个数
        if(k == 1) {
            return Math.min(nums1[start1], nums2[start2]);
        }

        // 过滤 k / 2 的数，但要注意不要过滤过头了
        int temp1 = start1 + Math.min(len1, k / 2) - 1;
        int temp2 = start2 + Math.min(len2, k / 2) - 1;

        if(nums1[temp1] > nums2[temp2]) {
            // 如果nums1的前K/2部分更大，意味着nums2的前K/2部分被过滤了
            // 但要注意，这里最后一个参数，要去 计算 具体被过滤的 个数，而不一定就是K/2个
            // 因为有可能长度不够，所以，temp参数计算过程中会有Math.min(len, k/2)
            return getKth(nums1, start1, end1, nums2, temp2 + 1, end2, k - (temp2 -start2 + 1));
        } else {
            return getKth(nums1, temp1 + 1, end1, nums2, start2, end2, k - (temp1- start1 + 1));
        }

    }


}

//runtime:1 ms
//memory:44.7 MB

回溯

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

1
2
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

1
2
输入：nums = [1]
输出：[[1]]

提示：

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同
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
import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Collectors;

import static java.util.stream.Collectors.toList;

class Solution {

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

    public List<List<Integer>> permute(int[] nums) {
        backTracking(nums, 0);
        return result;
    }

    private void backTracking(int[] nums, int startIndex) {
        if(startIndex == nums.length - 1) {
            List<Integer> temp = Arrays.stream(nums).boxed().collect(toList());
            result.add(temp);
            return;
        }
        for(int i = startIndex; i < nums.length; i++) {
            swap(nums, i, startIndex);
            backTracking(nums, startIndex + 1);
            swap(nums, i, startIndex);
        }
    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }


}

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

1
2
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

1
2
输入：nums = [0]
输出：[[],[0]]

提示：

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 中的所有元素 互不相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {

    private List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> tempList = new ArrayList<>();
        backTracking(nums, 0, tempList);
        return result;
    }

    private void backTracking(int[] nums, int startIndex, List<Integer> tempList) {
        // 这里就包含了空的列表
        result.add(new ArrayList<>(tempList));
        if(startIndex == nums.length) return;

        for(int i = startIndex; i < nums.length; i++) {
            tempList.add(nums[i]);
            backTracking(nums, i + 1, tempList);
            tempList.remove(tempList.size() - 1);
        }
    }
}

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

img

示例 1：

1
2
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

1
2
输入：digits = ""
输出：[]

示例 3：

1
2
输入：digits = "2"
输出：["a","b","c"]

提示：

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。
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
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

class Solution {

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

    public List<String> letterCombinations(String digits) {

        if(digits == null || digits.length() < 1) return result;

        HashMap<Character, char[]> hashMap = new HashMap<>();
        char currentChar = 'a';
        for(int num = 2; num <= 9; num++) {
            int i = 3;
            if(num == 7 || num == 9) {
                i = 4;
            }
            char[] tempArray = new char[i];
            for(int j = 0; j < i; j++) {
                tempArray[j] = currentChar++;
            }
            hashMap.put((char)(num + '0'), tempArray);
        }

        List<char[]> arrayList = new ArrayList<>();
        for(int i = 0; i < digits.length(); i++) {
            arrayList.add(hashMap.get(digits.charAt(i)));
        }

        StringBuilder sb = new StringBuilder();
        backTracking(arrayList, 0, sb);
        return result;
    }

    private void backTracking(List<char[]> list, int listIndex, StringBuilder sb) {
        if(listIndex > list.size()) return;
        if(listIndex == list.size()) {
            result.add(sb.toString());
            return;
        }

        char[] currentCharArray = list.get(listIndex);
        for(int i = 0; i < currentCharArray.length; i++) {
            sb.append(currentCharArray[i]);
            backTracking(list, listIndex + 1, sb);
            sb.setLength(sb.length() - 1);
        }
    }
}

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

1
2
3
4
5
6
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

1
2
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

1
2
输入: candidates = [2], target = 1
输出: []

提示：

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 1 <= target <= 40
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
class Solution {

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

    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        List<Integer> tempList = new ArrayList<>(); 
        // 对 candidates 进行排序 方便剪枝
        Arrays.sort(candidates); 
        int startIndex = 0; 
        backtrack(candidates, startIndex, tempList, 0, target);
        return result;
    }

    private void backtrack(int[] candidates, int startIndex, List<Integer> tempList, int tempSum, int target) {
        // 子集和等于 target 时，记录解
        if (tempSum == target) {
            result.add(new ArrayList<>(tempList));
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            
            if (tempSum + candidates[i] > target) {
                break;
            }
            
            tempList.add(candidates[i]);
            backtrack(candidates, i, tempList, tempSum + candidates[i], target);
            tempList.remove(tempList.size() - 1);
        }
    }

}

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

1
2
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

1
2
输入：n = 1
输出：["()"]

提示：

  • 1 <= n <= 8
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 {
    List<String> result = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        dfs("", n, n);
        return result;
    }

    private void dfs(String s, int leftNum, int rightNum) {
        
        if(leftNum > rightNum) {
            // 左括号数量超过右括号数量，当然不行
            return;
        }
        if(leftNum == 0 && rightNum == 0) {
            result.add(s);
            return;
        }
        if(leftNum > 0) {
            dfs(s + "(", leftNum - 1, rightNum);
        }
        if(rightNum > 0) {
            dfs(s + ")", leftNum, rightNum - 1);
        }
    }
}

79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

img

1
2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

img

1
2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

示例 3：

img

1
2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

提示：

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board 和 word 仅由大小写英文字母组成
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 Solution {

    private int[] position = new int[] {-1, 0, 1, 0, -1};

    public boolean exist(char[][] board, String word) {
        int rows = board.length;
        int cols = board[0].length;

        boolean[][] visited = new boolean[rows][cols];

        for(int row = 0; row < rows; row++) {
            for(int col = 0; col < cols; col++) {
                if(board[row][col] == word.charAt(0)) {
                    if(dfs(board, row, col, visited, 0, word)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, int row, int col, boolean[][] visited, int index, String word) {
        if(index == word.length() - 1) {
            return true;
        }

        visited[row][col] = true;

        for(int k = 0; k < 4; k++) {
            int m = row + position[k];
            int n = col + position[k+1];
            if(m >= 0 && m < board.length && n >= 0 && n < board[0].length
                && !visited[m][n] && board[m][n] == word.charAt(index+1)) {
                if(dfs(board, m, n, visited, index + 1, word)) {
                    return true;
                }
            }
        }

        visited[row][col] = false;
        return false;
    }
}

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串。返回 s 所有可能的分割方案。

示例 1：

1
2
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

1
2
输入：s = "a"
输出：[["a"]]

提示：

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成
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 {

    List<List<String>> result = new ArrayList<>();
    
    public List<List<String>> partition(String s) {
        List<String> tempList = new ArrayList<>();
        backTracking(s, 0, tempList);
        return result;
    }

    private void backTracking(String s, int startIndex, List<String> tempList) {
        if (startIndex == s.length()) {
            result.add(new ArrayList<>(tempList)); 
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (isPalindrome(s, startIndex, i)) {
                // 直接先判断是否是回文串
                tempList.add(s.substring(startIndex, i + 1));
                backTracking(s, i + 1, tempList);
                tempList.remove(tempList.size() - 1); 
            }
        }
    }
    
    private boolean isPalindrome(String s, int left, int right) {
        while (left <= right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}

51. N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

img

1
2
3
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

1
2
输入：n = 1
输出：[["Q"]]

提示：

  • 1 <= n <= 9
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
class Solution {
    
    private List<List<String>> result = new ArrayList<>();
    
    public List<List<String>> solveNQueens(int n) {
        // 题目暗含了一个信息，每行最终只会有一个皇后
        // 所以我们就由每行来进行遍历
        char[][] board = new char[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        backTracking(board, 0, n);
        return result;
    }
    
    private void backTracking(char[][] board, int row, int n) {
        if(row == n) {
            List<String> tempResult = new ArrayList<>();
            Arrays.stream(board).forEach(a -> {
               tempResult.add(new String(a));
            });
            result.add(tempResult);
            return;
        }

        for(int col = 0; col < n; col++) {
            if(isValid(board, row, col, n)) {
                board[row][col] = 'Q';
                backTracking(board, row + 1, n);
                board[row][col] = '.';
            }
        }
    }

    private boolean isValid(char[][] board, int row, int col, int n) {

        // 判断该列有没有皇后
        for(int i = 0; i < n; i++) {
            if(board[i][col] == 'Q') {
                return false;
            }
        }
        // 判断左上角有没有皇后
        for(int i = row-1, j = col-1; i >= 0 && j >= 0; i--,j--) {
            if(board[i][j] == 'Q') {
                return false;
            }
        }
        // 判断右上角有没有皇后
        for(int i = row-1, j = col + 1; i>=0&&j<n; i--,j++) {
            if(board[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}

图论

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

1
2
3
4
5
6
7
输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

1
2
3
4
5
6
7
输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] 的值为 '0' 或 '1'
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 {



    private int[] position = {-1, 0, 1, 0, -1};

    public int numIslands(char[][] grid) {
        int islandCount = 0;
        int rows = grid.length;
        int cols = grid[0].length;


        for(int row = 0; row < rows; row++) {
            for(int col = 0; col < cols; col++) {
                if(grid[row][col] == '1') {
                    islandCount++;
                    dfs(grid, row, col);
                }
            }
        }
        return islandCount;
    }

    private void dfs(char[][] grid, int row, int col) {
        if(grid[row][col] == '0') return;
        grid[row][col] = '0';
        for(int k = 0; k < 4; k++) {
            int m = row + position[k];
            int n = col + position[k+1];
            if(m >= 0 && m < grid.length && n >= 0 && n < grid[0].length && grid[m][n] == '1') {
                dfs(grid, m, n);
            }
        }
    }
}

994. 腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

  • 值 0 代表空单元格；
  • 值 1 代表新鲜橘子；
  • 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

示例 1：

img

1
2
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4

示例 2：

1
2
3
输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。

示例 3：

1
2
3
输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • grid[i][j] 仅为 0、1 或 2
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
class Solution {

    private int[] position = {-1, 0, 1, 0, -1};

    public int orangesRotting(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        
        LinkedList<List<Integer>> queue = new LinkedList<>();
        int count = 0;

        for(int row = 0; row < rows; row++) {
            for(int col = 0; col < cols; col++) {
                if(grid[row][col] == 2) {
                    // 找新鲜的
                    dfs(grid, row, col, queue);
                }
            }
        }



        while(!queue.isEmpty()) {
            // 分钟数
            count++;
            int currentSize = queue.size();
            List<List<Integer>> tempList = new ArrayList<>();
            // 这里要先去全部感染这一层
            for(int i = 0; i < currentSize; i++) {
                List<Integer> tempLocation = queue.pollFirst();
                grid[tempLocation.get(0)][tempLocation.get(1)] = 2;
                tempList.add(tempLocation);
            }
            // 再找新鲜一层的坐标
            for(int i = 0; i < currentSize; i++) {
                dfs(grid, tempList.get(i).get(0), tempList.get(i).get(1), queue);
            }
        }

        for(int row = 0; row < rows; row++) {
            for(int col = 0; col < cols; col++) {
                if(grid[row][col] == 1) {
                    return -1;
                }
            }
        }
        return count;
    }


    private void dfs(int[][] grid, int row, int col, LinkedList<List<Integer>> queue) {

        for(int k = 0; k < 4; k++) {
            int nextI = row + position[k];
            int nextJ = col + position[k+1];
            if(nextI >=0 && nextI < grid.length && nextJ >= 0 && nextJ < grid[0].length) {
                if(grid[nextI][nextJ] == 1) {
                    // 只保留新鲜的一层坐标
                    queue.addLast(List.of(nextI, nextJ));
                }
            }
        }
    }
}

207. 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

  • 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

1
2
3
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

1
2
3
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

提示：

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • prerequisites[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
class Solution {

    // 本质上就是拓扑排序
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        
        Map<Integer, List<Integer>> hashMap = new HashMap<>(); // key：前提课程 相关的 value:后续课程
        int[] degreeArray = new int[numCourses];  // 入度表, degreeArray[3] = 0 说明3号课程；不需要其他前提课程, degreeArray[2] = 3 说明2号课程需要3个前提课程；
        for(int[] array : prerequisites) {
            degreeArray[array[0]]++; // // [0,1]想要学习0, 必先学习1 所以记录0课程的入度
            List<Integer> tempList = hashMap.getOrDefault(array[1], new ArrayList<Integer>());
            tempList.add(array[0]);
            hashMap.put(array[1], tempList);
        }

        LinkedList<Integer> queue = new LinkedList<>();
        // 拓扑排序，把入度为0的入队，说明该课程应该是首先学习的
        for(int i = 0; i < degreeArray.length; i++) {
            if(degreeArray[i] == 0) {
                queue.addLast(i);
                numCourses--;
            }
        }
        
        while(!queue.isEmpty()) {
            int preCourse = queue.pollFirst();
            List<Integer> tempList = hashMap.get(preCourse);
            if(tempList != null && tempList.size() > 0) {
                 // 找到和 pre 相邻的节点，都去减少一度，减少后度数为0的话入队
                for(Integer nextNum : tempList) {
                    degreeArray[nextNum]--;
                    if(degreeArray[nextNum] == 0) {
                        queue.addLast(nextNum);
                        numCourses--;
                    }
                }
            }
        }

        return numCourses == 0;
    }
}

208. 实现 Trie (前缀树)

**Trie**（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

提示：

  • 1 <= word.length, prefix.length <= 2000
  • word 和 prefix 仅由小写英文字母组成
  • insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次
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
class Trie {
    // 基本的原理 是 每一层都是26个字母，一层一层的记录
    TrieNode root = null;

    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode temp = root;
        for(int i = 0; i < word.length(); i++) {
            if(temp.childNode[word.charAt(i) - 'a'] == null) {
                temp.childNode[word.charAt(i) - 'a'] = new TrieNode();
            }
            temp = temp.childNode[word.charAt(i) - 'a'];
        }
        // 记录 该单词 的最后端点 为 true
        temp.isVal = true;
    }
    
    public boolean search(String word) {
        TrieNode temp = root;
        for(int i = 0; i < word.length(); i++) {
            if(temp == null) {
                break;
            }
            temp = temp.childNode[word.charAt(i) - 'a'];
        }
        return temp != null ? temp.isVal : false;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode temp = root;
        for(int i = 0; i < prefix.length(); i++) {
            if(temp == null) {
                break;
            }
            temp = temp.childNode[prefix.charAt(i) - 'a'];
        }
        return temp != null;
    }

    class TrieNode {
        // 26个英文字母
        TrieNode[] childNode = new TrieNode[26];
        // 单词的最后端点 为 true
        boolean isVal;
        TrieNode() {
            isVal = false;
        }
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

二叉树

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

img

1
2
输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

1
2
输入：root = []
输出：[]

示例 3：

1
2
输入：root = [1]
输出：[1]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100
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
import java.util.ArrayList;

/**
 * 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 {
    private List<Integer> result = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        start(root);
        return result;
    }

    private void start(TreeNode root) {
        if(root == null) {
            return;
        }
        start(root.left);
        result.add(root.val);
        start(root.right);
    }
}

104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

img

1
2
输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

1
2
输入：root = [1,null,2]
输出：2

提示：

  • 树中节点的数量在 [0, 104] 区间内。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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 int maxDepth(TreeNode root) {
        // 学习一下 一行解决
		return root != null ?  1 + Math.max(maxDepth(root.left), maxDepth(root.right)) :  0;
    }


}

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

img

1
2
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

img

1
2
输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

1
2
输入：root = []
输出：[]

提示：

  • 树中节点数目范围在 [0, 100] 内
  • -100 <= Node.val <= 100
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
/**
 * 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 TreeNode invertTree(TreeNode root) {
        if(root == null) return null;
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

101. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

img

1
2
输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

img

1
2
输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

  • 树中节点数目在范围 [1, 1000] 内
  • -100 <= Node.val <= 100
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
/**
 * 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 boolean isSymmetric(TreeNode root) {
		return root == null ? true : isSymmetric(root.left, root.right);
    }

    private boolean isSymmetric(TreeNode left, TreeNode right) {
        // 都为空 则递归结束，对称
        if(left == null && right == null) {
            return true;
        }
        if(left == null || right == null) {
            // 其一为空，另一不为空，非对称
            return false;
        }
        if(left.val != right.val) {
            // 值不相同 非对称
            return false;
        }

        // 根据对称原则 去 递归
        return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
    }
}

543. 二叉树的直径

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

示例 1：

img

1
2
3
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2：

1
2
输入：root = [1,2]
输出：1

提示：

  • 树中节点数目在范围 [1, 104] 内
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
/**
 * 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 {

    private int diameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        //  利用的还是求树的最大深度！！！
        helper(root);
        return diameter;
    }

    private int helper(TreeNode  root) {
        if(root == null) {
            return 0;
        }
        int left = helper(root.left);
        int right = helper(root.right);
        diameter = Math.max(diameter, left + right);
        return 1 + Math.max(left, right);
    }
}

102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

img

1
2
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

1
2
输入：root = [1]
输出：[[1]]

示例 3：

1
2
输入：root = []
输出：[]

提示：

  • 树中节点数目在范围 [0, 2000] 内
  • -1000 <= Node.val <= 1000
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
import java.util.ArrayList;
import java.util.LinkedList;

/**
 * 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<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null) return result;
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        int count = queue.size();
        while(!queue.isEmpty()) {
            int currentSize = count;
            count = 0;
            List<Integer> tempResult = new ArrayList<>();
            for(int i = 0; i < currentSize; i++) {
                TreeNode node = queue.pollFirst();
                tempResult.add(node.val);
                if(node.left != null) {
                    queue.offerLast(node.left);
                    count++;
                }
                if(node.right != null) {
                    queue.offerLast(node.right);
                    count++;
                }
            }
            result.add(tempResult);
        }
        return result;
    }
}

108. 将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

示例 1：

img

1
2
3
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

img

1
2
3
输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 按 严格递增 顺序排列
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
/**
 * 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 TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    private TreeNode build(int[] nums, int startIndex, int endIndex) {
        if(startIndex > endIndex) return null;

        
        int midIndex = startIndex + (endIndex - startIndex) / 2;
        TreeNode root = new TreeNode(nums[midIndex]);
        root.left = build(nums, startIndex, midIndex - 1);
        root.right = build(nums, midIndex + 1, endIndex);
        return root;
    }
}

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左

    子树

    只包含

    小于

    当前节点的数。

  • 节点的右子树只包含 大于 当前节点的数。

  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

img

1
2
输入：root = [2,1,3]
输出：true

示例 2：

img

1
2
3
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

  • 树中节点数目范围在[1, 104] 内
  • -231 <= Node.val <= 231 - 1
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
/**
 * 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 {
    boolean flag = false;
    int preNum = 0;
    
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;

        boolean left = isValidBST(root.left);
        if(!flag) {
            flag = true;
            preNum = root.val;
        } else {
            if(root.val <= preNum) {
                return false;
            }
            preNum = root.val;
        }
        boolean right = isValidBST(root.right);
        return left && right;
    }


}

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

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

示例 1：

img

1
2
输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

img

1
2
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

提示：

  • 树中的节点数为 n 。
  • 1 <= k <= n <= 104
  • 0 <= Node.val <= 104
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
import java.util.HashSet;

/**
 * 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 {
    private int num;
    private int currentK;
    public int kthSmallest(TreeNode root, int k) {
        currentK = k;
        helper(root, k);
        return num;
    }
    private void helper(TreeNode root, int k) {
        if(root == null) return;
        helper(root.left, k);
        currentK--;
        if(currentK == 0) {
            num = root.val;
        }
        helper(root.right, k);
    }
}

199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1:

img

1
2
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:

1
2
输入: [1,null,3]
输出: [1,3]

示例 3:

1
2
输入: []
输出: []

提示:

  • 二叉树的节点个数的范围是 [0,100]
  • -100 <= Node.val <= 100
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
import java.util.ArrayList;
import java.util.LinkedList;

/**
 * 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> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root == null) return result;
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        int count = queue.size();
        while(!queue.isEmpty()) {
            int currentSize = count;
            count = 0;
            for(int i = 0; i < currentSize; i++) {
                TreeNode node = queue.pollFirst();
                if(i == currentSize - 1) {
                    result.add(node.val);
                }
                if(node.left != null) {
                    queue.offerLast(node.left);
                    count++;
                }
                if(node.right != null) {
                    queue.offerLast(node.right);
                    count++;
                }
            }
        }
        return  result;
    }
}

114. 二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

  • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

img

1
2
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

1
2
输入：root = []
输出：[]

示例 3：

1
2
输入：root = [0]
输出：[0]

提示：

  • 树中结点数在范围 [0, 2000] 内
  • -100 <= Node.val <= 100
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 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 void flatten(TreeNode root) {
        if(root == null) return;
        TreeNode left = root.left;
        TreeNode right = root.right;
        root.left = null;
        root.right = null;

        TreeNode tempTail = construct(root, left);
        construct(tempTail, right);

    }
    private TreeNode construct(TreeNode preTail, TreeNode bRoot){
        if(bRoot == null) return preTail;

        preTail.right = bRoot;
        preTail = preTail.right;
        TreeNode left = preTail.left;
        TreeNode right = preTail.right;
        preTail.left = null;
        preTail.right = null;
        if(left != null) {
            preTail = construct(preTail, left);
        }
        if(right != null) {
            preTail = construct(preTail, right);
        }
        return preTail;
        
    }
}

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

img

1
2
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

1
2
输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder 和 inorder 均 无重复 元素
  • inorder 均出现在 preorder
  • preorder 保证 为二叉树的前序遍历序列
  • inorder 保证 为二叉树的中序遍历序列
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
import java.util.HashMap;

/**
 * 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 TreeNode buildTree(int[] preorder, int[] inorder) {
        // 道理其实就是找到左右区间

        // inOrderMap 记录下 中序每个数 的位置， 方便快速找到
        HashMap<Integer, Integer> inOrderMap = new HashMap<>();
        for(int i = 0; i < inorder.length; i++) {
            inOrderMap.put(inorder[i], i);
        }

        return buildTree(0, preorder, inorder, inOrderMap, 0, inorder.length - 1);
    }

    private TreeNode buildTree(int rootIndex, int[] preOrder, int[] inOrder, HashMap<Integer, Integer> inOrderMap,
                               int inOrderStartIndex, int inOrderEndIndex) {
        // 条件范围, 该节点rootIndex当然得在范围内
        // inOrderStartIndex 当然得在范围内，且不能超过 inOrderEndIndex
        // inOrderEndIndex 当然得在范围内
        if(rootIndex < 0 || rootIndex >= preOrder.length ||
                inOrderStartIndex < 0 || inOrderStartIndex >= inOrder.length || inOrderStartIndex > inOrderEndIndex ||
                inOrderEndIndex < 0 || inOrderEndIndex >= inOrder.length) {
            return null;
        }

        // 拿到根节点
        int val = preOrder[rootIndex];
        // 拿到 该根节点 的中序位置
        int inOrderIndex = inOrderMap.get(val);
        // 拿到 该 根节点的左子树长度
        int leftLength = inOrderIndex - inOrderStartIndex;

        // 开始构建
        TreeNode root = new TreeNode(val);
        root.left = buildTree(rootIndex+1, preOrder, inOrder, inOrderMap, inOrderStartIndex, inOrderIndex - 1);
        root.right = buildTree(rootIndex+leftLength + 1, preOrder, inOrder, inOrderMap, inOrderIndex+1, inOrderEndIndex);
        return root;

    }
}

437. 路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

img

1
2
3
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

1
2
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

提示:

  • 二叉树的节点个数的范围是 [0,1000]
  • -109 <= Node.val <= 109
  • -1000 <= targetSum <= 1000
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
/**
 * 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 int pathSum(TreeNode root, int targetSum) {
		// 递归,但开始的要每个都开始去找，所以需要 主方法完成每个节点去找，子方法去判断是否满足，有多少条
       return root == null ? 0 : getResult(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
    }

    private int getResult(TreeNode root, long targetSum) {
        // 注意他妈的 这里的入参 变成了 long
        if(root == null) {
            return 0;
        }
        int count = root.val == targetSum ? 1 : 0;
        count += getResult(root.left, targetSum - root.val);
        count += getResult(root.right, targetSum - root.val);
        return count;
    }
}

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

img

1
2
3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

img

1
2
3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

1
2
输入：root = [1,2], p = 1, q = 2
输出：1

提示：

  • 树中节点数目在范围 [2, 105] 内。
  • -109 <= Node.val <= 109
  • 所有 Node.val 互不相同 。
  • p != q
  • p 和 q 均存在于给定的二叉树中。
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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 找到了直接返回
        if(root == null || root == p || root == q) return root;
        // 先往左边找
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 再往右边找
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 都找到左子节点了，还是没找到，直接返回右边
        if(left == null) return right;
        // 都找到右子节点了，还是没找到，直接返回右边
        if(right == null) return left;
        // 两边都没找到，返回根节点
        return root;
    }
}

124. 二叉树中的最大路径和

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

img

1
2
3
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

img

1
2
3
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

  • 树中节点数目范围是 [1, 3 * 104]
  • -1000 <= Node.val <= 1000
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
/**
 * 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 {
    int result = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        helper(root);
        return result;
    }
    private int helper(TreeNode root) {
        if(root == null) return 0;
        int left = helper(root.left);
        int right = helper(root.right);
        
        // 临时计算 从这个节点，左右最大进行保存
        int temp = root.val;
        if(left > 0) temp += left;
        if(right > 0) temp += right;
        result = Math.max(result, temp);
        
        // 递归返回最大
        return Math.max(root.val, Math.max(left, right) + root.val);
    }
}

矩阵

73. 矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1：

img

1
2
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

img

1
2
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示：

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -231 <= matrix[i][j] <= 231 - 1
方法一：原地算法
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
class Solution {

    // 使用原地算法解决
    public void setZeroes(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        // 记录第一行，第一列是否有0
        boolean firstRowFlag = false;
        boolean firstColFlag = false;
        
        for(int col = 0; col < cols; col++) {
            if(matrix[0][col] == 0) firstRowFlag = true;
        }
        for(int row = 0; row < rows; row++) {
            if(matrix[row][0] == 0) firstColFlag = true;
        }

        // 从除第一行第一列的位置开始，有0，就去把这一行列的开头置零，标记一下就行
        for(int row = 1; row < rows; row++) {
            for(int col = 1; col < cols; col++) {
                if(matrix[row][col] == 0) {
                    matrix[0][col] = 0;
                    matrix[row][0] = 0;
                }
            }
        }

        // 开始除横坐标0之外置零
        for(int row = 1; row < rows; row++) {
            if(matrix[row][0] == 0) {
                Arrays.fill(matrix[row], 0);
            }
        }

        // 开始除纵坐标0之外置零
        for(int col = 1; col < cols; col++) {
            if(matrix[0][col] == 0) {
                for(int row = 0; row < rows; row++) {
                    matrix[row][col] = 0;
                }
            }
        }

        // 最后置零第一行列
        if(firstRowFlag) Arrays.fill(matrix[0], 0);
        if(firstColFlag) {
            for(int row = 0; row < rows; row++) {
                matrix[row][0] = 0;
            }
        }
        
    }
}
方法二
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
class Solution {
    public void setZeroes(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;

        boolean[] rowFlag = new boolean[rows];
        boolean[] colFlag = new boolean[cols];
       

        for(int row = 0; row < rows; row++) {
            for(int col = 0; col < cols; col++) {
               if(matrix[row][col] == 0) {
                 rowFlag[row] = true;
                 colFlag[col] = true;
               }
            }
        }

        for(int row = 0; row < rows; row++) {
            if(rowFlag[row]) {
                for(int col = 0; col < cols; col++) {
                    matrix[row][col] = 0;
                }
            }
        }

        for(int col = 0; col < cols; col++) {
            if(colFlag[col]) {
                for(int row = 0; row < rows; row++) {
                    matrix[row][col] = 0;
                }
            }
        }


    }


}

54. 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

img

1
2
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

img

1
2
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100
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 Solution {

    private List<Integer> result = new ArrayList<>();

    public List<Integer> spiralOrder(int[][] matrix) {

        int rows = matrix.length;
        int cols = matrix[0].length;

        // 记录打印边界，行的上下边界，列的左右边界
        int upRow = 0;
        int downRow = rows - 1;
        int leftCol = 0;
        int rightCol = cols - 1;

        // 当前的位置
        int curRow = 0;
        int curCol = 0;

        while(true) {
            
            // 从左到右
            while(curCol <= rightCol) {
                result.add(matrix[curRow][curCol++]);
            }
            upRow++; // 上边界往下调一格
            curRow++; // 这一行打印完毕
            curCol--; // 循环结束过后 curCol 为 rightCol + 1，当然要 减1 回到正轨

            if(upRow > downRow) break;

            // 从上往下
            while(curRow <= downRow) {
                result.add(matrix[curRow++][curCol]);
            }

            rightCol--;
            curCol--;
            curRow--;

            if(rightCol < leftCol) break;

            // 从右往左
            while(curCol >= leftCol) {
                result.add(matrix[curRow][curCol--]);
            }

            downRow--;
            curRow--;
            curCol++;

            if(downRow < upRow) break;

            // 从下往上
            while(curRow >= upRow) {
                result.add(matrix[curRow--][curCol]);
            }

            leftCol++;
            curCol++;
            curRow++;

            if(leftCol > rightCol) break;
        }
        return result;

    }
}

48. 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在** 原地** 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

img

1
2
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

img

1
2
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000
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 void rotate(int[][] matrix) {
        // 每次只考虑四个间隔90度的旋转

        int temp = 0;
        int n = matrix.length - 1;
        // 一圈一圈地旋转，一共需要 n/2圈
        for(int i = 0; i <= n/2; i++) {
            for(int j = i; j < n-i; j++) {
                // 先暂时存右上角
                temp = matrix[j][n-i];
                // 左上角 给 右上角
                matrix[j][n-i] = matrix[i][j];
                // 左下角 给 左上角
                matrix[i][j] = matrix[n-j][i];
                // 右下角 给 左下角
                matrix[n-j][i] = matrix[n-i][n-j];
                // 右上角 给 右下角
                matrix[n-i][n-j] = temp;
            }
        }
    }
}

240. 搜索二维矩阵 II

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

示例 1：

img

1
2
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

img

1
2
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • -109 <= matrix[i][j] <= 109
  • 每行的所有元素从左到右升序排列
  • 每列的所有元素从上到下升序排列
  • -109 <= target <= 109
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;

        for(int row = 0; row < rows; row++) {
            for(int col = cols - 1; col >= 0; col--) {
                if(matrix[row][col] == target) {
                    return true;
                } else if(matrix[row][col] < target) {
                    break;
                } else {
                    continue;
                }
            }
        }
        return false;
    }
}

普通数组

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

1
2
3
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

1
2
输入：nums = [1]
输出：1

示例 3：

1
2
输入：nums = [5,4,-1,7,8]
输出：23

提示：

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxSubArray(int[] nums) {
        // dp[2] 代表的是 从 2 往前的 最大子序列和
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int result = dp[0];
        for(int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i], nums[i] + dp[i-1]);
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

1
2
3
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

1
2
3
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104
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
class Solution {
    public int[][] merge(int[][] intervals) {
        List<List<Integer>> resultList = new ArrayList<>();
        
        Arrays.sort(intervals, (a, b) -> {return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0];});

        int left = intervals[0][0];
        int right = intervals[0][1];

        for(int i = 1; i < intervals.length; i++) {
            if(right >= intervals[i][1]) {
                continue;
            }
            if(right >= intervals[i][0]) {
                right = intervals[i][1];
                continue;
            }
            resultList.add(List.of(left, right));
            left = intervals[i][0];
            right = intervals[i][1];
        }
        resultList.add(List.of(left, right));
        int[][] result = new int[resultList.size()][2];

        for(int i = 0; i < result.length; i++) {
            int[] temp = new int[2];
            temp[0] = resultList.get(i).get(0);
            temp[1] = resultList.get(i).get(1);
            result[i] = temp;
        }
        return result;
    }
}

189. 轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

1
2
3
4
5
6
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

1
2
3
4
5
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

  • 1 <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 105
方法一
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 void rotate(int[] nums, int k) {
        k %= nums.length;
        if(k == 0) return;
        // 反转整个数组
        reverse(nums, 0, nums.length - 1);
        // 反转前k个
        reverse(nums, 0, k - 1);
        // 反转后n-k个
        reverse(nums, k, nums.length - 1);
        
    }

    private void reverse(int[] nums, int left, int right) {
        if(left > right) return;

        while(left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            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
class Solution {
    public void rotate(int[] nums, int k) {
        k = k % (nums.length );
        if(k == 0) {
            return;
        }
        int slowIndex = -1;
        int fastIndex = -1;
        while(fastIndex < k - 1) fastIndex++;
        while(fastIndex < nums.length - 1) {
            slowIndex++;
            fastIndex++;
        }
        slowIndex++;
        fastIndex = 0;
        int[] resultNum = new int[nums.length];
        for(int i = 0; i < resultNum.length; i++) {
            if(i < k) {
                resultNum[i] = nums[slowIndex++];
            } else {
                resultNum[i] = nums[fastIndex++];
            }
        }
        for(int i = 0; i < resultNum.length; i++) {
            nums[i] = resultNum[i];
        }
    }
}

238. 除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

1
2
输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

1
2
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

  • 2 <= nums.length <= 105
  • -30 <= nums[i] <= 30
  • 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
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[] productExceptSelf(int[] nums) {
        int[] preMuti = new int[nums.length];
        int[] tailMuti = new int[nums.length];
        Arrays.fill(preMuti, 1);
        Arrays.fill(tailMuti, 1);

        int[] result = new int[nums.length];
        for(int i = 1; i < nums.length; i++) {
            preMuti[i] = preMuti[i-1] * nums[i-1];
        }
        for(int i = nums.length - 2; i >= 0; i--) {
            tailMuti[i] = tailMuti[i+1] * nums[i+1];
        }
        for(int i = 0; i < nums.length; i++) {
            result[i] = preMuti[i] * tailMuti[i];
        }
        return result;
    }
}

41. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

1
2
3
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：

1
2
3
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：

1
2
3
输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

提示：

  • 1 <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1
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
class Solution {

    // 题目隐含了条件：这里的最小正数一定出现在 1 ~ nums.length + 1 这里面
    // 其实就是把数字放在该放的下标位置
    // 放完一轮，从头开始找不一致的即为最小
    // 数组第一个就放1，也就是 i 下标，应该放 i+1, 如 0 下标位置 放 1， 1应该放在 0 下标位置
    public int firstMissingPositive(int[] nums) {
        
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == (i+1)) {
                continue;
            } else {
                if(nums[i] <= 0 || nums[i] > nums.length) {
                    continue;
                } else {
                    // 能找到正确的位置
                    // 交换对应的下标
                    // 只能往后换
                    // nums[i] 这个值 应该 放在 （nums[i] - 1） 这个下标位置
                    if(nums[nums[i] - 1] == nums[i]) {
                        // 如果目标下标位置 存放 的就是 正确的值，则跳过
                        continue;
                    }
                    // 否则就交换
                    swap(nums, i, nums[i] - 1);
                    i--;
                }
            }
        }

        // i 下标位置 需要存放的 是 i+1 的值
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] != i + 1) {
                return i + 1;
            }
        }
        // 走到这里说明 1~nums.length 都在对应下标位置，自然最小正数是 nums.length + 1
        return nums.length + 1;

    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

子串

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

1
2
输入：nums = [1,1,1], k = 2
输出：2

示例 2：

1
2
输入：nums = [1,2,3], k = 3
输出：2

提示：

  • 1 <= nums.length <= 2 * 104
  • -1000 <= nums[i] <= 1000
  • -107 <= k <= 107
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
import java.util.HashMap;

class Solution {
    public int subarraySum(int[] nums, int k) {
        
        // 废了好大劲才理解
        
        // key 前缀和  value 前缀和为此的个数
        Map<Integer, Integer> preSumFreq = new HashMap<>();

        // 前缀和为0的个数，有一种，所有数字都不选
        preSumFreq.put(0, 1);

        int preSum = 0;
        int count = 0;

        for(int num : nums) {
            // 前缀和
            preSum += num;
            
            // 只要存在 preSum - k 那么就意味着 preSum 首先存在，且preSum-k存在，那么自然 preSum - (preSum-k) 就能够等于k
            // 所以我们只需要看 preSumFreq.get(preSum-k)的种数
            if(preSumFreq.containsKey(preSum-k)) {
                count += preSumFreq.get(preSum-k);
            }
            
            // 不存在就把这个放进入
            preSumFreq.put(preSum, preSumFreq.getOrDefault(preSum, 0) + 1);
        }
        return count;
    }
}

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

1
2
输入：nums = [1], k = 1
输出：[1]

提示：

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length
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
import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {

        int[] ans = new int[nums.length - k + 1];
        // 使用双端队列，单调递减的规则来做即可
        Deque<Integer> queue = new LinkedList<>();

        // 未形成窗口
        for(int i = 0; i < k; i++) {
            
            while(!queue.isEmpty() && queue.peekLast() < nums[i]) {
                // 遇到更大的，得把之前更小的扔掉
                queue.removeLast();
            }
            queue.addLast(nums[i]);
        }

        // 形成窗口
        ans[0] = queue.peekFirst();
        for(int i = k; i < nums.length; i++) {
            if(queue.peekFirst() == nums[i-k]) {
                // i-k 即是 这个范围之前的一位
                // 也就是说要是这个区间把 最大值滑过去了
                // 双端队列当然 得扔掉第一个值
                queue.removeFirst();
            }
            while(!queue.isEmpty() && queue.peekLast() < nums[i]) {
                queue.removeLast();
            }
            queue.addLast(nums[i]);
            ans[i-k+1] = queue.peekFirst();
        }
        return ans;
    }
}

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

1
2
3
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

1
2
3
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

1
2
3
4
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

  • m == s.length
  • n == t.length
  • 1 <= m, n <= 105
  • s 和 t 由英文字母组成
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
class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> hashMap = new HashMap<>();
        for(char c : t.toCharArray()) hashMap.put(c, hashMap.getOrDefault(c, 0) + 1);
        
        int keySize = hashMap.size();
        int countKey = 0;
        int resultLeftIndex = -1;
        int resultLength = s.length() + 1;

        int left = 0;
        for(int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if(hashMap.containsKey(c)) {
                hashMap.put(c, hashMap.get(c) - 1);
                // 从1变为0，说明该字母用完了
                if(hashMap.get(c) == 0) countKey++;
            }
            // 当达到要求，左指针循环往右，找更短的长度
            while(countKey == keySize) {
                // 临时记录一下满足条件的长度
                if(right - left + 1 < resultLength) {
                    // 如果比已经记录的还要短，更新
                    resultLeftIndex = left;
                    resultLength = right - left + 1;
                }
                char leftC = s.charAt(left);
                if(hashMap.containsKey(leftC)) {
                    hashMap.put(leftC, hashMap.get(leftC) + 1);
                    // 从0变为1，说明该字母变为 没有用完的状态
                    if(hashMap.get(leftC) == 1) countKey--;
                }
                // 左指针继续往右，如果 countKey 还等于 keySize，说明还有更短的 
                left++;
            }
        }
        return resultLength == s.length() + 1 ? "" : s.substring(resultLeftIndex, resultLeftIndex +  resultLength);
    }
}

滑动窗口

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

给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成
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 lengthOfLongestSubstring(String s) {

        // 存储 当前时刻 每个字符的 最右边位置
        Map<Character, Integer> hashMap = new HashMap<>();

        int left = 0; // 记录 不含有重复字符 的 子串 左边下标
        int result = 0;
        
        // 循环以 右边下标 的意义 开始循环
        for(int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            
            if(!hashMap.containsKey(c)) {
                // 没有当然直接记录，新字符的 位置
                hashMap.put(c, right);
            } else {
                // 如果有记录，则去拿到 这个字符 上一次出现位置的 下一个位置
                int preIndex = hashMap.get(c) + 1;
                // 如果这个位置 比 left 还更靠右，自然滑动窗口 左边往右滑动
                if(preIndex > left) left = preIndex;
                hashMap.put(c, right);
            }

            result = Math.max(result, right - left + 1);
        }

        return result;
    }
}

438.找到字符串中所有字母异位词

给定两个字符串s和p，找到s中所有p的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

输入: s = “cbaebabacd”, p = “abc”

输出: [0,6]

解释:

起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。

起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

示例 2:

输入: s = “abab”, p = “ab”

输出: [0,1,2]

解释:

起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。

起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。

起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。

提示:

  • 1 <= s.length, p.length <= 3 * 104
  • s 和 p 仅包含小写字母
解法一
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 Solution {
    public List<Integer> findAnagrams(String s, String p) {

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

        int left = 0; // 滑动窗口左边坐标
        
        // 比方说 a:2 说明 a 还有2个 
        HashMap<Character, Integer> hashMap = new HashMap<>();
        for(int i = 0; i < p.length(); i++) {
            char c = p.charAt(i);
            hashMap.put(c, hashMap.getOrDefault(c, 0) + 1);
        }

        int zero = hashMap.size(); // p 不同的字符 个数
        int countZero = 0; // 记录 用完的不同字符 数量 比方说 p 为“aabc” ，countZero为3 的话 意味着 滑动窗口里面a、b、c都用完了

        // 滑动窗口右边坐标
        for(int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);

            if(hashMap.containsKey(c)) {
                // 这个字符属于 p 的话, 说明被使用 还剩余的数量减一
                hashMap.put(c, hashMap.get(c) - 1);
                // 当数量变为了0， 这里肯定是从 1 变为0，那么说明这个字符使用完毕，countZero 加1
                if(hashMap.get(c) == 0) countZero++;
                if(countZero == zero) {
                    // 说明所有字符都使用完毕，这个滑动窗口符合要求
                    result.add(left);
                }
            }
            // 一旦滑动窗口的大小和 p的长度相同，就该 窗口左边 往右移动一位了
            if(right - left + 1 == p.length()) {
                char tempC = s.charAt(left++);
                if(hashMap.containsKey(tempC)) {
                    hashMap.put(tempC, hashMap.get(tempC) + 1);
                    // 说明从0 变为的 1 ，自然就是 这个字符 没有被使用完毕了
                    if(hashMap.get(tempC) == 1) countZero--;
                }
            }
        }
        return result;
    }
}
解法二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        
        char[] pChars = p.toCharArray();
        Arrays.sort(pChars);
        p = new String(pChars);
        
        for(int i = 0; i + p.length() - 1 < s.length() ; i++) {
            char[] sChars = s.substring(i, i + p.length()).toCharArray();
            Arrays.sort(sChars);
            if(p.equals(new String(sChars))) {
                result.add(i);
            }
        }
        return result;
    }
}

双指针

11.盛最多水的容器

给定一个长度为n的整数数组height。有n条垂线，第 i 条线的两个端点是(i, 0)和(i, height[i]) 。

找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]

输出：49

解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。示例 2：

输入：height = [1,1]

输出：1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxArea(int[] height) {
        // 短板效应，面积只取决于短板，因为长板就算遇到更长的，短板在那儿，面积也没法变大
        // 所以，还是只能移动短板

        int left = 0;
        int right = height.length - 1;
        int result = 0;

        while(left < right) {
            result = height[left] < height[right] ? 
                Math.max(result, (right - left) * height[left++])  :
                Math.max(result, (right - left) * height[right--]);
        }
        return result;
    }
}

15.三数之和

给你一个整数数组nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且 j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为0且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]

输出：[[-1,-1,2],[-1,0,1]]

解释：

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。

nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。

nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。

不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。

注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]

输出：[]

解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]

输出：[[0,0,0]]

解释：唯一可能的三元组和为 0 。

提示：

  • 3 <= nums.length <= 3000
  • 105 <= nums[i] <= 105
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>> threeSum(int[] nums) {
        // 基本的逻辑就是，先排序，再基于 一个点，右边剩余的点用左右指针来找，中途顺便去重
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums); // 排好序就有了大小关系
        for(int firstIndex = 0; firstIndex < nums.length - 2; firstIndex++) {
            // 因为拍好了序，第一个点就大于0，右边肯定相加不能等于0
            if(nums[firstIndex] > 0) break; 
            // 直接把相同的第一个数过滤掉
            if(firstIndex > 0 && nums[firstIndex] == nums[firstIndex - 1]) continue;

            // 双指针确认第三个数

            // 第二个数 自然是 第一个数的下一个
            int secondIndex = firstIndex + 1;

            // 双指针，第三个数 自然是 数组中最后一个
            int thirdIndex = nums.length - 1;

            while(secondIndex < thirdIndex) {
                int sum = nums[firstIndex] + nums[secondIndex] + nums[thirdIndex];
                if(sum < 0) {
                    // 偏小，第二个数往右移，并且相同的话还要过滤
                    while(secondIndex < thirdIndex && nums[secondIndex] == nums[++secondIndex]);
                } else if(sum > 0) {
                    // 偏大，第三个数往左移，并且相同的话还要过滤
                    while(secondIndex < thirdIndex && nums[thirdIndex] == nums[--thirdIndex]);
                } else {
                    // 找到了，也要去过滤相同的
                    result.add(List.of(nums[firstIndex], nums[secondIndex], nums[thirdIndex]));
                    while(secondIndex < thirdIndex && nums[secondIndex] == nums[++secondIndex]);
                    while(secondIndex < thirdIndex && nums[thirdIndex] == nums[--thirdIndex]);
                }
            }
        }
        return result;
    }
}

42.接雨水

给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]

输出：6

解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]

输出：9

提示：

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105
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 Solution {
    public int trap(int[] height) {

        int max = -1;
        int result = 0;
        // 单调递减栈
        LinkedList<Integer> stack = new LinkedList<>();

        for(int i = 0; i < height.length; i++) {
            // 一开始就是0 去过滤
            if(max == -1 && height[i] == 0) continue;
            if(max == -1) {
                // 第一个边界
                max = height[i];
                stack.push(height[i]);
                continue;
            }

            // 超过了最高
            if(height[i] > max) {
                // 那么之前一定能用之前的max填满
                // 一边计算，一边全部出栈
                while(stack.peek() < max) {
                    result += (max - stack.poll());
                }
                // 把之前的最高出栈，记录新的最高
                stack.poll();
                stack.push(height[i]);
                max = height[i]; // 置新的max
                continue;
            }

            if(height[i] > stack.peek()) {
                // 没有超过最高，但比栈顶元素高, 因为是单调递减栈
                // 所以 往前遍历 更矮的, 注意这里使用了队列保证相对位置
                LinkedList<Integer> queue = new LinkedList<>();
                while(height[i] > stack.peek()) {
                    result += (height[i] - stack.poll());
                    queue.addLast(height[i]);
                }
                // 再依次入栈，保证相对位置
                while(!queue.isEmpty()) stack.push(queue.pollFirst());
            }
            stack.push(height[i]);
        }
        return result;
    }
}

283.移动零

给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

1
2
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

1
2
输入: nums = [0]
输出: [0]

提示:

  • 1 <= nums.length <= 104
  • 231 <= nums[i] <= 231 - 1
解法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    // 新方法
    public void moveZeroes(int[] nums) {
        // 左待换位置
        int left = 0;
        for(int right = 0; right < nums.length; right++) {
            if(nums[right] != 0) {
                // 右指针走到该换的位置
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                // 换完了，左指针右移一位
                left++;
            }
        }
    }
}
解法二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.Arrays;

class Solution {
    public void moveZeroes(int[] nums) {
        int[] newNums = new int[nums.length];
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) newNums[index++] = nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = newNums[i];
        }
    }
}

哈希

49.字母异位词

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

字母异位词是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

1
2
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

1
2
输入: strs = [""]
输出: [[""]]

示例 3:

1
2
输入: strs = ["a"]
输出: [["a"]]

提示：

  • 1 <= strs.length <= 104
  • 0 <= strs[i].length <= 100
  • strs[i] 仅包含小写字母
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<List<String>> groupAnagrams(String[] strs) {

        // 其实已经想到 到底该怎么记录  hashMap的 key了
        // 没想到的是，直接排序，那么相同结构的字符串，自然排完序就是同样的字符串
        // 非常适合作为hashMap的key
        List<List<String>> result = new ArrayList<>();
        HashMap<String, List<String>> hashMap = new HashMap<>();

        for(String str : strs) {
            char[] tempChars = str.toCharArray();
            Arrays.sort(tempChars);
            String tempString = new String(tempChars);
            List<String> list = hashMap.getOrDefault(tempString, new ArrayList<String>());
            list.add(str);
            hashMap.put(tempString, list);
        }
        hashMap.values().forEach(value -> {
            result.add(value);
        });
        return result;
    }
}

128.最长连续序列

给定一个未排序的整数数组nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为O(n)的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]

输出：4

解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]

输出：9

提示：

  • 0 <= nums.length <= 105
  • 109 <= nums[i] <= 109
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
import java.util.HashSet;

class Solution {
    public int longestConsecutive(int[] nums) {
        
        // 这方法有点意思，通过HashMap去往前往后查
        HashSet<Integer> hashSet = new HashSet<>();
        Arrays.stream(nums).forEach(num -> {hashSet.add(num);});

        int result = 0;
        for(int num : nums) {
            int tempResult = 1;
            int preNum = num - 1;
            int nextNum = num + 1;
            hashSet.remove(num);
            while(hashSet.contains(preNum)) {
                tempResult++;
                hashSet.remove(preNum);
                preNum--;
            }
            while(hashSet.contains(nextNum)) {
                tempResult++;
                hashSet.remove(nextNum);
                nextNum++;
            }
            result = Math.max(result, tempResult);
        }
        return result;
    }
}

1.两数之和

给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9

输出：[0,1]

解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6

输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6

输出：[0,1]

提示：

  • 2 <= nums.length <= 104
  • 109 <= nums[i] <= 109
  • 109 <= target <= 109
  • 只会存在一个有效答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
      
        int[] result = new int[2];
        for(int i = 0; i < nums.length; i++) {
            
            if(hashMap.containsKey(target - nums[i])) {
                result[0] = i;
                result[1] = hashMap.get(target - nums[i]);
                break;
            }
            hashMap.put(nums[i], i);
        }
        return result;
    }
}
2024-08-09 该篇文章被 nino 打上标签: 算法 Java 归为分类: 程序员

上一篇：2024年8月底写过的无聊的诗 下一篇：2024年8月初写过的无聊的诗
以上
© 2024-1999 nino / 联系 / 支持 / 订阅 / 近邻
🌊看过大海的人不会忘记海的广阔🌊 本站由Hexo驱动｜使用Hexo-theme-A4主题