算法题刷题笔记_using namespace ara::exec;

语法

Java语法

java类似python collections.Counter的用法

集合互转

int[], Integer[], List<Integer>, List<String> 互相转换

CPP语法

C++语法汇总

链表

001. Java链表结点定义

package structure;

public class ListNode {
   
    public int val;
    public ListNode next;

    public ListNode() {
   
    }

    public ListNode(int val) {
   
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
   
        this.val = val;
        this.next = next;
    }

    public static ListNode fromArray(int[] list) {
   
        ListNode head = null;
        ListNode tail = null;
        for (int item : list) {
   
            ListNode node = new ListNode(item);
            if (head == null) {
   
                head = node;
                tail = node;
            } else {
   
                tail.next = node;
                tail = node;
            }
        }
        return head;
    }

    @Override
    public String toString() {
   
        StringBuilder res = new StringBuilder();
        ListNode p = this;
        while (p != null) {
   
            res.append(p.val).append(" -> ");
            p = p.next;
        }
        res.append("O");
        return res.toString();
    }
}

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

002. Python链表结点定义

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    @staticmethod
    def fromList(lst):
        head = None
        tail = None
        for item in lst:
            node = ListNode(item)
            if head is None:
                head = node
                tail = head
            else:
                tail.next = node
                tail = node
        return head

    def __str__(self):
        p = self
        res = ""
        while p is not None:
            res += f"{p.val} -> "
            p = p.next
        res += "O"
        return res

    __repr__ = __str__
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

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

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

瞎写的

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        p = head
        k = 0
        p2 = None
        while p is not None:
            p = p.next
            k += 1
            if (k - 1) == n:
                p2 = head
            if (k - 1) > n:
                p2 = p2.next
        if p2 is None and k == n:
            head = head.next
        elif p2.next is not None:
            p2.next = p2.next.next
        return head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

官方题解

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head)
        first = head
        second = dummy
        for i in range(n):
            first = first.next

        while first:
            first = first.next
            second = second.next
        
        second.next = second.next.next
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14

还是官方的好， 我写的和屎一样。希望能默写一下官方题解

206. 反转链表

206. 反转链表

迭代法

时间复杂度：$\mathcal{O}(n)$
空间复杂度：$\mathcal{O}(1)$

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None
        p = head
        while p is not None:
            tmp = p.next
            p.next = pre
            pre = p
            if tmp is None:
                break
            p = tmp
        return p
1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None
        p = head
        while p is not None:
            tmp = p.next
            p.next = pre
            pre = p
            p = tmp
        return pre
1
2
3
4
5
6
7
8
9
10

递归法

时间复杂度：$\mathcal{O}(n)$
空间复杂度：$\mathcal{O}(n)$

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        node = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return node
1
2
3
4
5
6
7
8

说实话有点没看懂

143. 重排链表

143. 重排链表

乱写的解法

import math

class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        nodes = []
        p = head
        while p is not None:
            nodes.append(p)
            pre = p
            p = p.next
            pre.next = None
        N = len(nodes)
        mid = math.floor(len(nodes) / 2)
        list2 = list(reversed(nodes[mid:]))
        list1 = nodes[:mid]
        if len(list2) > len(list1):
            list1.append(list2.pop())
        lst = [list1, list2]
        for i in range(N):
            if i == 0:
                head = list1[0]
                p = head
            else:
                p.next = lst[i % 2][i // 2]
                p = p.next

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

按照题解默写的线性表解法

class Solution:
    def reorderList(self, head: ListNode) -> None:
        if head is None:
            return None
        p = head
        vec = []
        while p is not None:
            vec.append(p)
            p = p.next
        i = 0
        j = len(vec) - 1
        while i < j:
            vec[i].next = vec[j]
            i += 1
            if i == j:
                break
            vec[j].next = vec[i]
            j -= 1
        vec[i].next = None  # 容易想错
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

234. 回文链表

234. 回文链表
快慢指针 + 翻转链表

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        pre = None
        slow = head
        fast = head
        while fast is not None and fast.next is not None:
            tmp = slow.next
            slow.next = pre
            pre = slow
            fast = fast.next.next
            slow = tmp
1
2
3
4
5
6
7
8
9
10
11

21. 合并两个有序链表

21. 合并两个有序链表

瞎写的不带头结点的方法

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        pp = None
        res = None
        p1 = l1
        p2 = l2
        while p1 is not None or p2 is not None:
            if p1 is None and p2 is not None:
                p = p2
                p2 = p2.next
            elif p1 is not None and p2 is None:
                p = p1
                p1 = p1.next
            else:
                if p1.val < p2.val:
                    p = p1
                    p1 = p1.next
                else:
                    p = p2
                    p2 = p2.next
            if pp is not None:
                pp.next = p
                pp = pp.next
            else:
                pp = res = p
        return res
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:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        pp = dummy = ListNode(-1)
        p1 = l1
        p2 = l2
        while p1 is not None and p2 is not None:
            if p1.val < p2.val:
                p = p1
                p1 = p1.next
            else:
                p = p2
                p2 = p2.next
            pp.next = p
            pp = pp.next
        pp.next = p1 if p1 is not None else p2
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2. 两数相加

2. 两数相加

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        p1 = l1
        p2 = l2
        ret = None
        p = None
        carry = 0
        while p1 is not None or p2 is not None:
            v1 = p1.val if p1 is not None else 0
            v2 = p2.val if p2 is not None else 0
            num = v1 + v2 + carry
            node = ListNode(num % 10)
            carry = num // 10
            if ret is None:
                ret = node
                p = ret
            else:
                p.next = node
                p = p.next
            p1 = p1.next if p1 is not None else None
            p2 = p2.next if p2 is not None else None
        if carry:
            p.next = ListNode(carry)
        return ret
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

328. 奇偶链表

328. 奇偶链表

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if head is None: # 用例 []
            return None
        odds = None
        evens = None
        index = 1
        p = head
        evens_head = None
        while p is not None:
            if index % 2:
                if odds is not None:
                    odds.next = p
                odds = p
            else:
                if evens is not None:
                    evens.next = p
                else:
                    evens_head = p
                evens = p
            p = p.next
            index += 1
        if evens is not None:  # 用例 [1]
            evens.next = None  # 注意了
        odds.next = evens_head
        return head
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:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        oddHead, evenHead = head, head.next
        odd, even = oddHead, evenHead
        while even and even.next:
            odd.next = even.next
            odd = odd.next         # 别忘了自己要移动
            even.next = odd.next
            even = even.next
        odd.next = evenHead
        return head
1
2
3
4
5
6
7
8
9
10
11
12
13

141. 环形链表

141. 环形链表

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if head is None or head.next is None:
            return False
        slow = head
        fast = head.next
        while slow != fast:
            if not slow or not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next
        return True
1
2
3
4
5
6
7
8
9
10
11
12

147. 链表插入排序

官方题解

147. 对链表进行插入排序

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        dummyHead = ListNode(0)
        dummyHead.next = head
        lastSorted = head
        curr = head.next
        while curr:
            # 排序区最后的元素小于等于当前元素，把当前元素放排序区后面就行
            if lastSorted.val <= curr.val:
                lastSorted = lastSorted.next
            # 否则
            else:
                prev = dummyHead
                while prev.next.val <= curr.val:
                    prev = prev.next
                # prev.next.val > curr.val
                # prev.val <= curr.val
                lastSorted.next = curr.next
                curr.next = prev.next
                prev.next = curr
            curr = lastSorted.next
        return dummyHead.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

148. 链表归并排序

148. 排序链表

• 伪代码

merge函数参考 merge-two-sorted-lists

subLength = 1 
while subLength < len(listNode):
	构造 prev, curr
	while curr 非空:
		构造head1, head2, 两个链表长度为subLengh, 结尾为空
		将curr指向下一个节点
		合并两个有序链表
		构造新的prev
	subLength *= 2
1
2
3
4
5
6
7
8
9

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        def merge(head1: ListNode, head2: ListNode) -> ListNode:
            dummyHead = ListNode(0)
            temp, temp1, temp2 = dummyHead, head1, head2
            while temp1 and temp2:
                if temp1.val <= temp2.val:
                    temp.next = temp1
                    temp1 = temp1.next
                else:
                    temp.next = temp2
                    temp2 = temp2.next
                temp = temp.next
            if temp1:
                temp.next = temp1
            elif temp2:
                temp.next = temp2
            return dummyHead.next

        if not head:
            return head

        length = 0
        node = head
        while node:
            length += 1
            node = node.next

        dummyHead = ListNode(0, head)
        subLength = 1
        while subLength < length:
            prev, curr = dummyHead, dummyHead.next
            while curr:
                # 构造 head1
                head1 = curr
                for i in range(1, subLength):
                    if curr.next:
                        curr = curr.next
                    else:
                        break
                # 构造 head2
                head2 = curr.next
                curr.next = None  # head1 结尾为空
                curr = head2
                for i in range(1, subLength):
                    if curr and curr.next:
                        curr = curr.next
                    else:
                        break
                # 将curr指向下一个节点，并让head2 结尾为空
                succ = None
                if curr:
                    succ = curr.next
                    curr.next = None
                curr = succ
                # 合并两个有序链表
                merged = merge(head1, head2)
                # 套到上一个节点上
                prev.next = merged
                # 构造新的prev
                while prev.next:
                    prev = prev.next
            subLength *= 2

        return dummyHead.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

23. 合并K个升序链表

23. 合并K个升序链表

• 分治合并

class Solution {
   
    public ListNode mergeTwoLists(ListNode a, ListNode b) {
   
        if (a == null || b == null) {
   
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
   
            if (aPtr.val < bPtr.val) {
   
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
   
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
   
        if (l == r) {
   
            return lists[l];
        }
        if (l > r) {
   
            return null;
        }
        int mid = (l + r) >> 1;
        return mergeTwoLists(
                merge(lists, l, mid),
                merge(lists, mid + 1, r)
        );
    }

    public ListNode mergeKLists(ListNode[] lists) {
   
        return merge(lists, 0, lists.length - 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

• 堆排序

class Solution {
   
    public ListNode mergeKLists(ListNode[] lists) {
   
        PriorityQueue<Status> queue = new PriorityQueue<>();
        for (ListNode node : lists) {
   
            if (node != null) {
   
                queue.offer(new Status(node.val, node));
            }
        }
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while (!queue.isEmpty()) {
   
            Status f = queue.poll();
            tail.next = f.ptr;
            tail = tail.next;
            if (f.ptr.next != null) {
   
                queue.offer(new Status(f.ptr.next.val, f.ptr.next));
            }
        }
        return head.next;
    }

    class Status implements Comparable<Status> {
   
        int val;
        ListNode ptr;

        Status(int val, ListNode ptr) {
   
            this.val = val;
            this.ptr = ptr;
        }

        public int compareTo(Status status2) {
   
            return this.val - status2.val;
        }
    }
}
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

86. 分隔链表

86. 分隔链表

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        if not head:
            return head
        head1 = ListNode(0)
        p1 = head1
        head2 = ListNode(0)
        p2 = head2
        p = head
        while p:
            if p.val < x:
                p1.next = p
                p1 = p1.next
            else:
                p2.next = p
                p2 = p2.next
            p = p.next
        if head1.next is None:
            return head2.next
        if head2.next is None:
            return head1.next
        p1.next = head2.next
        p2.next = None
        return head1.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

基本编程思想

二分

001. labuladong框架

搜索一个元素时，搜索区间两端闭
while条件带等号，否则需要打补丁
if相等就返回，其他事情甭操心
mid必须加减一，因为区间两端闭
while结束就凉了，凄凄惨惨返-1

搜索左右区间时，搜索区间要阐明
左闭右开最常见，其余逻辑便自明
while要用小于号，这样才能不漏掉
if相等别返回，利用mid锁边界

nums = [1, 1, 3, 6, 6, 6, 7, 8, 8, 9]


def binary_search(nums, target):
    '''找一个数'''
    l = 0
    r = len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        # 如果是Java Cpp
        # mid = l + (r - l) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            l = mid + 1
        elif nums[mid] > target:
            r = mid - 1
    return -1


print("binary_search", binary_search(nums, 6))


def lower_bound(nums, target):
    '''找左边界'''
    l = 0
    r = len(nums)
    while l < r:
        mid = (l + r) // 2
        if nums[mid] == target:
            r = mid
        elif nums[mid] < target:
            l = mid + 1
        elif nums[mid] > target:
            r = mid
    # 对未命中情况进行后处理
    if l == len(nums):
        return -1
    return l if nums[l] == target else -1


print("lower_bound", lower_bound(nums, 6))
print("lower_bound", lower_bound(nums, 2))


def upper_bound(nums, target):
    '''找右边界'''
    l = 0
    r = len(nums)
    while l < r:
        mid = (l + r) // 2
        if nums[mid] == target:
            l = mid + 1
        elif nums[mid] < target:
            l = mid + 1
        elif nums[mid] > target:
            r = mid
    if l == 0:
        return -1
    return l - 1 if nums[l - 1] == target else -1


print("upper_bound", upper_bound(nums, 100))
print("upper_bound", upper_bound(nums, -1))
print("upper_bound", upper_bound(nums, 2))
print("upper_bound", upper_bound(nums, 6))
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

002. 实现lower_bound与upper_bound

• 默写labuladong算法小抄

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def lower_bound(nums, target):
            l = 0
            r = len(nums)
            while l < r:
                mid = (l + r) // 2
                if nums[mid] == target:
                    r = mid
                elif nums[mid] < target:
                    l = mid + 1
                elif nums[mid] > target:
                    r = mid
            if l >= len(nums):
                return -1
            return l if nums[l] == target else -1
        def upper_bound(nums, target):
            l = 0
            r = len(nums)
            while l < r:
                mid = (l + r) // 2
                if nums[mid] == target:
                    l = mid + 1
                elif nums[mid] < target:
                    l = mid + 1
                elif nums[mid] > target:
                    r = mid
            if l == 0:
                return -1
            return l - 1 if nums[l - 1] == target else -1
        return [lower_bound(nums, target), upper_bound(nums, target)]

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

LeetCode官方题解将LB与UB整合到了一行代码中(cpp)

并且二分查找的具体方式也有所不同

int binarySearch(vector<int>& nums, int target, bool lower) {
   
    int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();
    while (left <= right) {
   
        int mid = (left + right) / 2;
        if (nums[mid] > target || (lower && nums[mid] >= target)) {
   
            right = mid - 1;
            ans = mid;
        } else {
   
            left = mid + 1;
        }
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

翻译成python代码

def binary_search(nums, target, lower):
    l = 0
    r = len(nums) - 1
    ans = len(nums)
    while l <= r:  # diff
        mid = (l + r) // 2
        # 满足左边就一定会满足右边
        if (nums[mid] > target) or (lower and nums[mid] >= target):
            r = mid - 1  # diff
            ans = mid  # diff
        else:
            l = mid + 1  # common
    return ans
1
2
3
4
5
6
7
8
9
10
11
12
13

TODO: 更深入地学习labuladong算法小抄中关于二分的部分

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

300. 最长递增子序列

300. 最长递增子序列

贪心 + 二分

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        N = len(nums)
        dp = []
        for i, num in enumerate(nums):
            if len(dp) == 0 or dp[-1] < num:
                dp.append(num)
            else:
                # lower_bound
                l = 0
                r = len(dp)
                while l < r:
                    mid = (l + r) // 2
                    if dp[mid] == num:
                        r = mid
                    elif dp[mid] < num:
                        l = mid + 1
                    elif dp[mid] > num:
                        r = mid
                dp[l] = num
        return len(dp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

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

题解：详细通俗的思路分析， 多解法
上述题解的题解3需要再看一下，感觉写的比官方的简洁

下面的解法参考官方题解两个有序数组的第k元素的方法，还有些不熟悉的地方。

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def getKthElement(k):
            index1 = index2 = 0
            while True:
                # 特殊情况(写错了)
                # if index1 + k > n - 1:
                #     return nums1[n - 1]
                # elif index2 + k > m - 1:
                #     return nums2[m - 1]
                # elif k == 1:
                #     return min(nums1[index1 + k], nums2[index2 + k])
                # ---------------------------
                # nums1 普遍偏小的情况
                if index1 == n:
                    return nums2[index2 + k - 1]
                # nums2 普遍偏小的情况
                if index2 == m:
                    return nums1[index1 + k - 1]
                # 死循环退出条件
                if k == 1:
                    return min(nums1[index1], nums2[index2])
                # 正常情况
                half = k // 2
                new_index1 = min(index1 + half - 1, n - 1)
                new_index2 = min(index2 + half - 1, m - 1)
                if nums1[new_index1] < nums2[new_index2]:
                    k -= new_index1 - index1 + 1
                    index1 = new_index1 + 1  # 忘了 + 1
                else:
                    k -= new_index2 - index2 + 1
                    index2 = new_index2 + 1  # 忘了 + 1

        n = len(nums1)
        m = len(nums2)
        total_len = (n + m)
        if total_len % 2:
            return getKthElement((total_len + 1) // 2)
        else:
            return (getKthElement(total_len // 2) + getKthElement(total_len // 2 + 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

33. 搜索旋转排序数组

33. 搜索旋转排序数组

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        N = len(nums)
        l = 0
        r = N - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            # 左边有序
            # “左边有序”的判断一定要<=，其他的判断可以无脑两个<=
            # if nums[0] < nums[mid]:
            if nums[0] <= nums[mid]:
                # 目标值在左边
                # if nums[0] <= target <= nums[mid]:
                if nums[0] <= target < nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
            # 右边有序
            else:
                # 目标值在右边
                # if nums[mid] <= target <= nums[N - 1]:
                if nums[mid] < target <= nums[N - 1]:
                    l = mid + 1
                else:
                    r = mid - 1
        return -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

167. 两数之和 II - 输入有序数组

167. 两数之和 II - 输入有序数组

• 二分

时间 $O(N\log N)$ 空间 $O(N)$

class Solution {
   
    public int[] twoSum(int[] numbers, int target) {
   
        for (int i = 0; i < numbers.length; ++i) {
   
            int low = i + 1, high = numbers.length - 1;
            while (low <= high) {
   
                int mid = (high - low) / 2 + low;
                if (numbers[mid] == target - numbers[i]) {
   
                    return new int[]{
   i + 1, mid + 1};
                } else if (numbers[mid] > target - numbers[i]) {
   
                    high = mid - 1;
                } else {
   
                    low = mid + 1;
                }
            }
        }
        return new int[]{
   -1, -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

• 双指针

时间 $O(N)$ 空间 $O(1)$

class Solution {
   
    public int[] twoSum(int[] numbers, int target) {
   
        int low = 0, high = numbers.length - 1;
        while (low < high) {
   
            int sum = numbers[low] + numbers[high];
            if (sum == target) {
   
                return new int[]{
   low + 1, high + 1};
            } else if (sum < target) {
   
                ++low;
            } else {
   
                --high;
            }
        }
        return new int[]{
   -1, -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

• 双指针 + 二分

时间 ：最好 $O(\log N)$ ，最坏 $O(N)$

class Solution {
   
    public int[] twoSum(int[] numbers, int target) {
   
        int i = 0, j = numbers.length - 1;
        while (i < j) {
   
            int m = (i + j) >>> 1;
            if (numbers[i] + numbers[m] > target) {
   
                j = m - 1;
            } else if (numbers[m] + numbers[j] < target) {
   
                i = m + 1;
            } else if (numbers[i] + numbers[j] > target) {
   
                j--;
            } else if (numbers[i] + numbers[j] < target) {
   
                i++;
            } else {
   
                return new int[]{
   i + 1, j + 1};
            }
        }
        return new int[]{
   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

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        i, j = 0, len(numbers) - 1
        while i <= j:
            m = (i + j) // 2
            if numbers[i] + numbers[m] > target:
                j = m - 1
            elif numbers[m] + numbers[j] < target:
                i = m + 1
            elif numbers[i] + numbers[j] < target:
                i += 1
            elif numbers[i] + numbers[j] > target:
                j -= 1
            else:
                return [i + 1, j + 1]
        return [-1, -1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

分治

240. 搜索二维矩阵 II

240. 搜索二维矩阵 II

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        N = len(matrix)
        if not N:
            return False
        M = len(matrix[0])
        i = N - 1
        j = 0
        while i >= 0 and j < M:
            if matrix[i][j] == target:
                return True
            if matrix[i][j] < target:
                j += 1
            elif matrix[i][j] > target:
                i -= 1
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

贪心

621. 任务调度器

• 模拟法

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        freq = collections.Counter(tasks)
        rest = list(freq.values())
        M = len(rest)
        nextValid = [1] * M
        time = 0
        for _ in tasks:
            time += 1
            # 下一个最早可用时间
            minNextValid = min(nextValid[i] for i in range(M) if rest[i] > 0)
            time = max(time, minNextValid)  # 写错成了min
            best = -1
            for i in range(M):
                # 在剩余任务中，时间满足
                if rest[i] > 0 and nextValid[i] <= time:
                    # 剩余次数最多
                    if best == -1 or rest[i] > rest[best]:
                        best = i
            rest[best] -= 1
            # 根据样例、需要间隔n个
            nextValid[best] = time + n + 1
        return time
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:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        freq = collections.Counter(tasks)
        maxExec = max(freq.values())
        maxCount = sum(1 for cnt in freq.values() if cnt == maxExec)
        return max(  # 没想到
            (maxExec - 1) * (n + 1) + maxCount,
            len(tasks)  # 没想到
        )
1
2
3
4
5
6
7
8
9

861. 翻转矩阵后的得分

861. 翻转矩阵后的得分

class Solution {
   
public:
    int matrixScore(vector<vector<int>> &A) {
   
        int m = A.size(), n = A[0].size();
        //m 行 n 列
        int ret = m * (1 << (n - 1)); // 忘了 m * ()
        // 先“翻转”行再“翻转”列。翻转行必然使第一列全为1
        for (int j = 1; j < n; ++j) {
    //遍历第j列
            int nOnes = 0;
            for (int i = 0; i < m; ++i) {
    //第i行
                if (A[i][0] == 1) {
     //如果某一行第一列是0，该行会翻转
                    nOnes += A[i][j]; // 手抖写成  A[i][0]
                } else {
   
                    nOnes += (1 - A[i][j]);
                }
            }
            int k = max(nOnes, m - nOnes);
            ret += k * (1 << (n - 1 - j));
        }
        return ret;
    }
};
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

860. 柠檬水找零

先把大面额的钱找出去

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        counter = dict(zip([5, 10, 20], [0] * 3))
        for bill in bills:
            if bill == 5:
                counter[5] += 1
            elif bill == 10:
                if counter[5] < 1:
                    return False
                counter[5] -= 1
                counter[10] += 1
            else: # 20
                if counter[10] >=1 and counter[5] >= 1:
                    counter[5] -= 1
                    counter[10] -= 1
                elif counter[5] >= 3:
                    counter[5] -= 3
                else:
                    return False
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

649. Dota2 参议院

649. Dota2 参议院

自己瞎写， 超时

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        ix = 0
        senate = list(senate)
        while True:
            if len(senate) == 1:
                break
            for i in itertools.chain(
                    range(ix + 1, len(senate)),
                    range(ix),
            ):
                if senate[i] != senate[ix]:
                    del senate[i]
                    break
            ix += 1
            if ix >= len(senate):
                ix = 0
        return "Dire" if senate[0] == "D" else "Radiant"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

官方题解

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        n = len(senate)
        r_list = collections.deque()
        d_list = collections.deque()

        for i, ch in enumerate(senate):
            if ch == "R":
                r_list.append(i)
            else:
                d_list.append(i)

        while r_list and d_list:
            if r_list[0] < d_list[0]:
                r_list.append(r_list[0] + n)
            else:
                d_list.append(d_list[0] + n)
            r_list.popleft()
            d_list.popleft()

        return "Radiant" if r_list else "Dire"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

TODO:
自己写一遍

376. 摆动序列

376. 摆动序列

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        N = len(nums)
        if N < 2:
            # 考虑长度为 1 和 0 的情况
            return N
        pre_delta = nums[1] - nums[0]
        ans = 1 if pre_delta == 0 else 2
        for i in range(2, N):
            delta = nums[i] - nums[i - 1]
            if (delta > 0 and pre_delta <= 0) or (delta < 0 and pre_delta >= 0):
                ans += 1
                pre_delta = delta
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14

TODO:
自己写一遍
看DP题解

135. 分发糖果

135. 分发糖果

class Solution:
    def candy(self, ratings: List[int]) -> int:
        L = len(ratings)
        left = [1] * L
        right = [1] * L
        for i in range(1, L):
            if ratings[i] > ratings[i - 1]:
                left[i] = left[i - 1] + 1
        cnt = left[L - 1]
        for i in reversed(range(0, L - 1)):
            if ratings[i] > ratings[i + 1]:
                right[i] = right[i + 1] + 1
            cnt += max(left[i], right[i])
        return cnt
1
2
3
4
5
6
7
8
9
10
11
12
13
14

455. 分发饼干

排序+贪心

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        s_N = len(s)
        s_start = 0
        cnt = 0
        for child_demand in g:
            while s_start < s_N:
                biscuit = s[s_start]
                s_start += 1
                if biscuit >= child_demand:
                    cnt += 1
                    break
            if s_start >= s_N:
                break
        return cnt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

605. 种花问题

605. 种花问题

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        N = len(flowerbed)

        def available(i):
            if flowerbed[i] == 0 and \
                    (i == 0 or flowerbed[i - 1] == 0) and \
                    (i == N - 1 or flowerbed[i + 1] == 0):
                return True
            return False

        cnt = 0
        for i in range(N):
            if available(i):
                cnt += 1
                flowerbed[i] = 1
        return n <= cnt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

官方题解看不懂，这个题解思路和我一样，但是会提前return，比我做得好。

【1】种花问题：简单的贪心

class Solution {
   
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
   
        for(int i=0; i<flowerbed.length; i++) {
   
            if(flowerbed[i] == 0 && (i == 0 || flowerbed[i-1] == 0) && (i == flowerbed.length-1 || flowerbed[i+1] == 0)) {
   
                n--;
                if(n <= 0) return true;
                flowerbed[i] = 1;
            }
        }

        return n <= 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

搜索法

回溯法

51. N 皇后

51. N 皇后
baseline

from typing import List
class Solution:

    def dfs(self, i):
        if i >= self.n:
            self.res.append(["".join(row) for row in self.board])
            return
        for j in range(self.n):
            if self.isValid(i, j):
                self.board[i][j] = "Q"
                self.dfs(i + 1)
                self.board[i][j] = "."

    def isValid(self, x, y):
        for i in range(x):
            if self.board[i][y] == "Q":
                return False
        for j in range(y):
            if self.board[x][j] == "Q":
                return False
        i = x - 1
        j = y - 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21