leetcode刷题笔记

滑动窗口的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        # write code here
        res = []
        #窗口大于数组长度的时候，返回空
        if size <= len(num) and size != 0: 
            #数组后面要空出窗口大小，避免越界
            for i in range (len(num) - size + 1):
                #寻找每个窗口最大值
                max = 0;
                for j in range(i, i + size):
                    if num[j] > max:
                        max = num[j]
                res.append(max)
        return res

滑动窗口的最大和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxInWindows(self, num: List[int], size: int) -> List[int]:
        res = []
        n = len(num)
        # 如果窗口大小大于数组长度或为0,直接返回空列表
        if size > n or size == 0:
            return res
        # 初始化第一个窗口的和
        window_sum = sum(num[:size])
        res.append(window_sum)
        # 滑动窗口,计算每个窗口的和
        for i in range(size, n):
            window_sum = window_sum - num[i - size] + num[i]
            res.append(window_sum)
        return res

#O(nlogn) O(logn)

合并区间 排序 + 一次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        intervals.sort(key=lambda x: x[0])
        res = [intervals[0]] # 将第一个区间加入答案，然后依次考虑之后的每个区间：
        for i in range(1, len(intervals)): # 如果答案数组中最后一个区间的右端点小于当前考虑区间的左端点，说明两个区间不会重合，因此我们可以直接将当前区间加入答案数组末；否则，说明两个区间重合，我们需要用当前区间的右端点更新答案数组中最后一个区间的右端点，将其置为二者的较大值。最后，我们返回答案数组即可。
            if intervals[i][0] <= res[-1][1]:
                res[-1][1] = max(intervals[i][1], res[-1][1])
            else:
                res.append(intervals[i])
        return res

乘积小于k的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def numSubarrayProductLessThanK(nums, k):
    if k == 0:
        return 0
    ans, s, j = 0, 1, 0
    for i, v in enumerate(nums):
        s *= v
        while j <= i and s >= k:
            s //= nums[j]
            j += 1
        if s < k:
            for m in range(j, i+1):
                temp = nums[m:i+1]
                print(temp)
        ans += i - j + 1
    return ans
def main():
    nums = list(map(int, input().split()))
    k = int(input())
    result = numSubarrayProductLessThanK(nums, k)
    return result
print(main())

Problem: 剑指 Offer 18. 删除链表的节点

image.png

思路

解法是通过修改指针的指向关系来实现删除效果

解题方法

如果头节点就是要删除的,直接返回头节点的下一个节点
否则遍历链表,找到节点前一个节点
将前一个节点的next指向下下个节点,实现跳过删除效果
最后返回新的头节点

复杂度

时间复杂度:
O(n)

空间复杂度:
O(1)

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

image-1.png

思路

双指针

解题方法

初始化双指针,first走k-1步;循环中,first和second同时向后走,当first为None,second.val即为目标节点值;返回second

复杂度

时间复杂度:
O(n) 需要遍历整个链表

空间复杂度:
O(1) 只用到了两个节点引用变量

Problem: 剑指 Offer 25. 合并两个排序的链表

image-2.png

思路

使用一个dummy节点串接两个链表

解题方法

初始化dummy节点,用于连接结果链表
将l1和l2头节点值较小者连接到结果链表
指针后移,继续比较下一个节点
最后将非空链表直接连接在结果链表后面

复杂度

时间复杂度:
O(n+m)

空间复杂度:
O(1)

Problem: 剑指 Offer 52. 两个链表的第一个公共点

image-3.png

思路

该算法用于查找两个单链表相交的第一个节点。它的思路是利用两个链表在无环的情况下最终会同时遍历完毕的特性。具体来说:

  1. 初始化两个指针 A 和 B,分别指向两个链表的头结点。
  2. 同时遍历两个链表,当 A 到达链表尾部时,将 A 重新定位到另一个链表的头部;当 B 到达链表尾部时,将 B 重新定位到另一个链表的头部。
  3. 如果两个链表存在相交的节点,那么两个指针必定会相遇,这时就返回其中一个指针所指向的节点。如果两个链表不存在相交的节点,那么最终两个指针都会遍历完两个链表并同时为 None,跳出循环。

复杂度

时间复杂度分析:

  • 最坏情况下,两个链表都没有交点,需要遍历完两个链表,时间复杂度为 O(m+n),其中 m 和 n 分别是两个链表的长度。
  • 最好情况下,两个链表第一个节点就是交点,时间复杂度为 O(1)。
  • 平均时间复杂度为 O(m+n)。

空间复杂度分析:

  • 算法只使用了两个指针变量,因此空间复杂度为 O(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
class Solution:
    def getIntersectionNode(self, headA, headB):
        # 检测链表是否存在环
        def hasCircle(head):
            slow, fast = head, head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
                if slow == fast:  # 存在环
                    p = head
                    q = slow
                    while p != q:
                        p = p.next
                        q = q.next
                    return q  # 返回环入口
            return None  # 不存在环

        
        if not headA or not headB:
            return None
        
        # 检测两个链表是否存在环
        nodeA = hasCircle(headA)
        nodeB = hasCircle(headB)

        # 如果两个链表都不存在环
        if not nodeA and not nodeB:
            A, B = headA, headB
            while A != B:
                A = A.next if A else headB
                B = B.next if B else headA
            return A

        # 如果有一个链表存在环
        if nodeA and not nodeB or not nodeA and nodeB:
            return None

        # 如果两个链表都存在环
        p, q = nodeA, nodeB
        while p != q:
            p = p.next
            q = q.next
        return p

        # A, B = headA, headB
        # while A != B:
        #     A = A.next if A else headB
        #     B = B.next if B else headA

        # return A

Problem: 剑指 Offer 06. 从尾到头打印链表

image-4.png

思路

递归

解题方法

定义列表res来保存反向结果,编写递归函数recurse,输入一个节点
在recurse内部,先递归打印下一节点,再将当前节点值append到res里
最后返回res

复杂度

时间复杂度:
O(n)

空间复杂度:
O(n)

Problem: 剑指 Offer 24. 反转链表

image-5.png

思路

1. 迭代的方式原地反转链表。

具体来说,它通过不断修改节点的 next 指针来反转链表,实现了链表的原地反转。

算法步骤
初始化两个指针变量 prev 和 curr，分别指向 None 和 head。
遍历链表,每次将当前节点 curr 从链表中移除,并将其插入到 prev 指针所指向的节点之后。
curr 指针向后移动一位,继续遍历链表。
重复步骤 2 和 3,直到遍历完整个链表。
此时 prev 指向了反转后的链表的头节点,返回 prev 即可。

复杂度

时间复杂度为 O(n),空间复杂度为 O(1),

2. 递归来反转单链表

递归终止条件是当前节点或其后继节点为空时，返回当前节点。
递归地反转后续节点。
将当前节点的指针指向前一个节点。

复杂度

递归方法的时间复杂度为 O(n)，空间复杂度也是 O(n)，因为需要额外的栈空间存储递归调用的信息。
相比原地反转的迭代方法，递归方法的优点是可以保留原始链表结构不变，缺点是需要额外的栈空间。

Code

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(object):
    # 迭代原地反转
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        prev, curr = None, head
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        return prev

    # # 递归
    # def reverseList(self, head):
    #     """
    #     :type head: ListNode
    #     :rtype: ListNode
    #     """
    #     # 递归终止条件
    #     if not head or not head.next:
    #         return head
        
    #     # 递归反转后续节点
    #     new_head = self.reverseList(head.next)
        
    #     # 修改节点的指针方向
    #     head.next.next = head
    #     head.next = None
        
    #     return new_head

Problem: 剑指 Offer 35. 复杂链表的复制

image-6.png

思路

首先遍历原链表,对每个节点创建一个新的节点,并插入到原节点的后面。
然后再次遍历链表,在遍历过程中设置新节点的random指针,将其指向原节点random指针的下一个节点。
最后拆分链表,将奇数位置的节点组成原链表,偶数位置的节点组成新的复制链表。

解题方法

链表的复制,包括节点复制、random指针复制和链表拆分。

复杂度

时间复杂度为O(n)。利用了原链表的结构,没有使用额外空间,因此空间复杂度为O(1)。

code

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
"""
# Definition for a Node.
class Node:
    def __init__(self, x, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random
"""
class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head:
            return None
        # 复制链表节点
        cur = head
        while cur is not None:
            next = cur.next
            cur.next = Node(cur.val)
            cur.next.next = next
            cur = next
        # 复制random指针
        cur = head
        while cur != None:
            curNew = cur.next
            curNew.random = cur.random.next if cur.random else None
            cur = cur.next.next
        # 拆分链表
        cur = head 
        head_new = head.next
        curNew = head.next
        while cur:
            cur.next = cur.next.next
            cur = cur.next
            curNew.next = cur.next if cur else None
            curNew = curNew.next

        return head_new

单链表相加

用单链表表示十进制整数，求两个正整数的和
image-8.png
思路：可以先它他们进行反转，相加之后，得到结果，再把结果进行反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class SolutionAdd {
    // 反转链表
    public ListNode  reverseList(ListNode node){
        ListNode pre = null;
        ListNode q= null;
        while (node != null) {
            q= node.next;
            node.next = pre;
            pre = node;
            node = q;
        }
        return pre;
    }
    // 单链表相加
    public ListNode  addTwoNumbers(ListNode head1, ListNode head2) {
        // 虚拟头节点
        ListNode listNode = new ListNode(0);
        ListNode p = listNode;
        // sum 用来存放进位
        int sum = 0;
        while (head1 != null || head2 != null || sum!=0) {
            if (head1 != null) {
                sum += head1.val;
                head1 = head1.next;
            }

            if (head2 != null) {
                sum += head2.val;
                head2 = head2.next;
            }
            p.next = new ListNode(sum % 10);
            sum = sum / 10;
            p = p.next;
        }
        return listNode.next;
    }
}

时间复杂度：O(n+m)
空间复杂度：O(1)

总结

对于双指针，在做关于单链表的题有用

“判断单链表是否有环”

可以设置一个慢指针和一个快指针来遍历这个链表。慢指针一次移动一个节点，而快指针一次移动两个节点，如果该链表没有环，则快指针会先遍历完这个表，如果有环，则快指针会在第二次遍历时和慢指针相遇。

“如何一次遍历就找到链表中间位置节点”

一样是设置一个快指针和慢指针。慢的一次移动一个节点，而快的两个。在遍历链表的时候，当快指针遍历完成时，慢指针刚好达到中点。

“单链表中倒数第 k 个节点”

设置两个指针，其中一个指针先移动k个节点。之后两个指针以相同速度移动。当那个先移动的指针遍历完成的时候，第二个指针正好处于倒数第k个节点。

在处理与链表相关的一些问题的时候，可以考虑双指针哦。双指针另外一个应用的比较多的领域就是：在排序数组在求和，

队列和栈

栈是先进后出，而队列则先进先出，这是两种既相似又相反的数据结构，使得他们经常会被关联在一起。

剑指 Offer 09. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

imagedl2.png

用队列实现栈

imagedl1.png

二分查找

二分查找不断缩小查找范围，直到只有一个元素
四种变形二分查找的模版代码，比如对于一个有序数组arr = [1，2，3，3，3，4，5，5，7]，target = 3，那么

1.寻找第一个大于 target 的元素的下标
对应方法名格式为
int upper(int[] arr, int target){
//如果都不存在，则返回-1
}

2.如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，如果不存在，则返回第一个大于 target 的元素下标。
对应方法名
int floor_upper(int[] arr, int target){
//如果都不存在，则返回-1
}

3.寻找最后一个小于 target 的元素的下标，
对应方法名格式为
int lower(int[] arr, int target){

//如果都不存在，则返回-1
}

4.如果数组中存在元素等于 target，则返回第一个等于target 的下标，如果不存在，则返回最后一个小于 target 的元素的下标。
int floor_lower(int[] arr, int target){

//如果都不存在，则返回-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
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
99
100
101
102
103
104
105

public class BinarySearch {
    //寻找第一个大于target的元素的下标
    public int upper(int[] arr, int target) {
        //先判断特殊情况
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int l = 0;
        int r = arr.length - 1;
        if (arr[r] <= target) {
            return -1;
        }
        while (l < r) {
            int mid = (r - l) / 2 + l;
            if (arr[mid] > target) {
                r = mid;
            } else { // arr[mid] <= target
                l = mid + 1;
            }
        }
        return l;
    }

    // 若数组存在元素等于target，则返回最后一个等于target的元素下标
    // 若不存在则返回，第一个大于target的元素下标
    public int floor_upper(int[] arr, int target) {
        //先判断特殊情况
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int l = 0;
        int r = arr.length - 1;
        if (arr[r] < target) {
            return -1;
        }
        while (l < r) {
            int mid = (r - l) / 2 + l;
            if (arr[mid] > target) {
                r = mid;
            } else { // arr[mid] <= target
                l = mid + 1;
            }
        }
        if (l - 1 >= 0 && arr[l - 1] == target) {
            l = l - 1;
        }
        return l;
    }

    //寻找最后一个小于target的元素下标
    public int lower(int[] arr, int target) {
        //先判断特殊情况
        if (arr == null || arr.length == 0 || arr[0] >= target) {
            return -1;
        }
        int l = 0;
        int r = arr.length - 1;
        if (arr[l] >= target) {
            return -1;
        }
        while (l + 1< r) {
            int mid = (r - l) / 2 + l;
            if (arr[mid] >= target) {
                r = mid - 1;
            } else { // arr[mid] < target
                l = mid;
            }
        }
        return l;
    }

    // 若数组存在元素等于target，则返回第一个等于target的元素下标
    // 若不存在，则返回最后一个小于target的元素的下标
    public int floor_lower(int[] arr, int target) {
        //先判断特殊情况
        if (arr == null || arr.length == 0 || arr[0] > target) {
            return -1;
        }
        int l = 0;
        int r = arr.length - 1;
        while (l < r) {
            int mid = (r - l) / 2 + l;
            if (arr[mid] >= target) {
                r = mid - 1;
            } else { // arr[mid] < target
                l = mid;
            }
        }
        if (l + 1 < arr.length && arr[l + 1] == target) {
            l = l + 1;
        }
        return l;

    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 2,3,3,3,4,5,5,7};
        int target = 3;
        BinarySearch b = new BinarySearch();
        int index = b.floor_upper(arr, target);
        System.out.println("index = "+ index + ", value = " + arr[index]);
    }

}
#leetcode
leetcode刷题笔记
https://www.prime.org.cn/2024/04/02/leetcode刷题/
Author
emroy
Posted on
April 2, 2024
Licensed under