Skip to content

Commit b3d50ff

Browse files
melody-limelody-li
authored
Merge pull request algorithm004-01#354 from LearningChanging/master
251-Week 02
2 parents fa22913 + c8b1dbf commit b3d50ff

30 files changed

+1056
-88
lines changed

‎Week 01/id_251/LeetCode_141_251.py‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -75,7 +75,7 @@ def hasCycleSlowFastIndex(self, head):
7575
while fast and fast.next:
7676
slow = slow.next
7777
fast = fast.next.next
78-
if slow == fast:
78+
if slow is fast:
7979
return True
8080
return False
8181

‎Week 01/id_251/LeetCode_142_251.py‎

Lines changed: 99 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,99 @@
1+
# 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
2+
#
3+
# 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
4+
#
5+
# 说明：不允许修改给定的链表。
6+
#
7+
#
8+
#
9+
# 示例 1：
10+
#
11+
# 输入：head = [3,2,0,-4], pos = 1
12+
# 输出：tail connects to node index 1
13+
# 解释：链表中有一个环，其尾部连接到第二个节点。
14+
#
15+
#
16+
#
17+
#
18+
# 示例 2：
19+
#
20+
# 输入：head = [1,2], pos = 0
21+
# 输出：tail connects to node index 0
22+
# 解释：链表中有一个环，其尾部连接到第一个节点。
23+
#
24+
#
25+
#
26+
#
27+
# 示例 3：
28+
#
29+
# 输入：head = [1], pos = -1
30+
# 输出：no cycle
31+
# 解释：链表中没有环。
32+
#
33+
#
34+
#
35+
#
36+
#
37+
#
38+
# 进阶：
39+
# 你是否可以不用额外空间解决此题？
40+
# Related Topics 链表 双指针
41+
42+
43+
# leetcode submit region begin(Prohibit modification and deletion)
44+
# Definition for singly-linked list.
45+
# class ListNode(object):
46+
# def __init__(self, x):
47+
# self.val = x
48+
# self.next = None
49+
50+
"""
51+
1 哈希表
52+
2 Floyd
53+
"""
54+
55+
56+
class Solution(object):
57+
def detectCycle(self, head):
58+
"""
59+
:type head: ListNode
60+
:rtype: ListNode
61+
"""
62+
visited = set()
63+
while head:
64+
if head in visited:
65+
return head
66+
visited.add(head)
67+
head = head.next
68+
69+
#### 2 Floyd方法
70+
def slow_fast_index(self, head):
71+
slow = fast = head
72+
while fast and fast.next:
73+
slow, fast = slow.next, fast.next.next
74+
if slow is fast:
75+
return slow # return meet position
76+
# 如果不写return python 会默认 return None
77+
78+
def floyd(self, head):
79+
meet_position = self.slow_fast_index(head)
80+
if meet_position:
81+
while head != meet_position:
82+
head = head.next
83+
meet_position = meet_position.next
84+
return head
85+
86+
# 2 Floyd优化
87+
def floyd1(self, head):
88+
slow = fast = head
89+
while True:
90+
if not (fast and fast.next): # fast已到尾部 和 链表为空 都囊括了
91+
return None
92+
slow, fast = slow.next, fast.next.next
93+
if slow is fast:
94+
break
95+
while head != slow:
96+
head, slow = head.next, slow.next
97+
return head
98+
99+
# leetcode submit region end(Prohibit modification and deletion)

‎Week 01/id_251/LeetCode_155_251.py‎

Lines changed: 13 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -49,6 +49,7 @@ def push(self, x):
4949
:rtype: None
5050
"""
5151
self.data.append(x)
52+
# 这里 x < self.helper[-1] 或者 x <= self.helper[-1] 都可以
5253
if len(self.helper) == 0 or x <= self.helper[-1]:
5354
self.helper.append(x)
5455
else:
@@ -59,8 +60,11 @@ def pop(self):
5960
:rtype: None
6061
"""
6162
if self.data:
62-
del self.helper[-1]
63-
return self.data.pop()
63+
# del 时间复杂度比pop高
64+
# del self.helper[-1]
65+
# del self.data[-1]
66+
self.helper.pop()
67+
self.data.pop()
6468

6569
def top(self):
6670
"""
@@ -110,8 +114,11 @@ def pop(self):
110114
"""
111115
if self.data:
112116
if self.data[-1] == self.helper[-1]:
113-
del self.helper[-1]
114-
return self.data.pop()
117+
# del 时间复杂度比pop高
118+
# del self.helper[-1]
119+
# del self.data[-1]
120+
self.helper.pop()
121+
self.data.pop()
115122

116123
def top(self):
117124
"""
@@ -140,7 +147,8 @@ def push(self, x):
140147

141148
def pop(self):
142149
if self.stack:
143-
del self.stack[-1]
150+
# del self.stack[-1]
151+
self.stack.pop()
144152

145153
def top(self):
146154
if self.stack:

‎Week 01/id_251/LeetCode_189_251.py‎

Lines changed: 6 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -46,22 +46,19 @@ def rotate(self, nums, k):
4646
# 1 暴力解法 O(n*k) 超时
4747
def force_rotate(self, nums, k):
4848
k %= len(nums)
49-
for i in range(k):
49+
for _ in range(k):
5050
previous = nums[-1]
51-
for j in range(len(nums)):
52-
previous, nums[j] = nums[j], previous
51+
for i in range(len(nums)):
52+
previous, nums[i] = nums[i], previous
5353

5454
# 2 使用额外的数组 时间空间：O(n)
5555
def new_arr_rotate(self, nums, k):
56-
new_list = [None] * len(nums)
5756
k %= len(nums)
57+
new_list = [None] * len(nums)
5858
for i in range(len(nums)):
5959
new_list[(i + k) % len(nums)] = nums[i]
6060

61-
for i in range(len(nums)):
62-
nums[i] = new_list[i]
63-
64-
# nums[:] = new_list 这样赋值也行
61+
nums[:] = new_list
6562

6663
# 3 环形旋转 ?
6764
def ring_rotation(self, nums, k):
@@ -79,7 +76,7 @@ def ring_rotation(self, nums, k):
7976
break # 次数到了或者出现循环则跳出
8077
start += 1
8178

82-
# 4 三次使用反转
79+
# 4 三次使用反转 最优解法
8380
def three_reverse_rotation(self, nums, k):
8481
k %= len(nums)
8582
"""
@@ -110,8 +107,6 @@ def p_rotate1(self, nums, k):
110107
nums[:] = nums[-k:] + nums[:-k]
111108

112109

113-
# leetcode submit region end(Prohibit modification and deletion)
114-
115110
if __name__ == '__main__':
116111
s = Solution()
117112
l = [1, 2, 3, 4]

‎Week 01/id_251/LeetCode_206. 反转链表过程图解.jpeg‎

13.2 KB
Loading

‎Week 01/id_251/LeetCode_206_251.py‎

Lines changed: 8 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -19,11 +19,10 @@
1919
"""
2020
1 迭代
2121
2 递归
22-
# 参考资料: https://www.cnblogs.com/kubixuesheng/p/4394509.html
2322
(1) 结束条件：已经反转的链表为空或者链表中只有一个元素 head = None or head.next = None
2423
(2) 递推公式：只要画一下第一层就行head
25-
! 先反转后面的链表，走到链表的末端结点 new_pre = f(head.next),
26-
!! 再将当前节点设置为后面节点的后续节点 head.next.next = head; head.next = None
24+
! 先反转后面的链表，记录头结点 new_pre = f(head.next),
25+
!! 反转当前节点 head.next.next = head; head.next = None
2726
"""
2827

2928

@@ -37,18 +36,14 @@ def reverseList(self, head):
3736
while curr:
3837
curr.next, pre, curr = pre, curr, curr.next
3938
return pre
40-
# 或者
41-
# head = pre
42-
# return head
4339

4440
def reverseList1(self, head):
4541
# 已经反转的链表为空或者链表中只有一个元素
46-
if head is None or head.next is None:
42+
# not head or not head.next ==== head is None or head.next is None
43+
if not (head and head.next):
4744
return head
48-
# 先反转后面的链表，走到链表的末端结点
45+
# 先反转后面的链表，记录头结点
4946
new_pre = self.reverseList1(head.next)
50-
# 再将当前节点设置为后面节点的后续节点
51-
head.next.next = head # 防止出现环
52-
head.next = None # 防止出现环
53-
return new_pre # 走到链表的末端结点
54-
# leetcode submit region end(Prohibit modification and deletion)
47+
# 反转当前节点
48+
head.next.next, head.next = head, None
49+
return new_pre # 返回反转好部分的头结点

‎Week 01/id_251/LeetCode_24_251.py‎

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -60,10 +60,14 @@ def swapPairs1(self, head):
6060
def swapPairs2(self, head):
6161
if not head or not head.next:
6262
return head
63-
second = head.next
6463
# head --> second --> f(second.next) to second --> head --> f(second.next)
64+
# 先head指向 f(second.next), 然后 second指向head 最后 返回 新头结点
65+
second = head.next
6566
head.next = self.swapPairs2(second.next)
6667
second.next = head
6768
return second
69+
# ======>
70+
# head.next, head, head.next = self.swapPairs2(head.next.next), head.next, head
71+
# return head
6872

6973
# leetcode submit region end(Prohibit modification and deletion)

‎Week 01/id_251/LeetCode_25. K 个一组翻转链表图解.jpeg‎

731 KB
Loading

‎Week 01/id_251/LeetCode_25_251.py‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
# 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
2+
#
3+
# k 是一个正整数，它的值小于或等于链表的长度。
4+
#
5+
# 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
6+
#
7+
# 示例 :
8+
#
9+
# 给定这个链表：1->2->3->4->5
10+
#
11+
# 当 k = 2 时，应当返回: 2->1->4->3->5
12+
#
13+
# 当 k = 3 时，应当返回: 3->2->1->4->5
14+
#
15+
# 说明 :
16+
#
17+
#
18+
# 你的算法只能使用常数的额外空间。
19+
# 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
20+
#
21+
# Related Topics 链表
22+
23+
24+
# leetcode submit region begin(Prohibit modification and deletion)
25+
# Definition for singly-linked list.
26+
# class ListNode(object):
27+
# def __init__(self, x):
28+
# self.val = x
29+
# self.next = None
30+
31+
"""
32+
1 看图 https://leetcode-cn.com/problems/reverse-nodes-in-k-group/solution/tu-jie-kge-yi-zu-fan-zhuan-lian-biao-by-user7208t/
33+
"""
34+
35+
36+
class Solution(object):
37+
def reverseKGroup(self, head, k):
38+
"""
39+
:type head: ListNode
40+
:type k: int
41+
:rtype: ListNode
42+
"""
43+
pre, end, pre.next, end.next = self, self, head, head
44+
45+
while end:
46+
# 三个一组取出
47+
for i in range(k):
48+
if end is None:
49+
break
50+
end = end.next
51+
# 判断不是整数倍跳出
52+
if end is None:
53+
break
54+
start, end.next, _next = pre.next, None, end.next
55+
pre.next, start.next = self.reverse(start), _next
56+
end = pre = start
57+
return self.next
58+
59+
def reverse(self, head):
60+
pre, curr = None, head
61+
while curr:
62+
curr.next, pre, curr = pre, curr, curr.next
63+
return pre
64+
65+
# leetcode submit region end(Prohibit modification and deletion)

‎Week 01/id_251/LeetCode_26_251.py‎

Lines changed: 11 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -45,14 +45,24 @@
4545
"""
4646

4747

48-
# leetcode submit region begin(Prohibit modification and deletion)
4948
class Solution(object):
5049
def removeDuplicates(self, nums):
5150
"""
5251
:type nums: List[int]
5352
:rtype: int
5453
"""
5554

55+
# 最优解法
56+
def two_index(self, nums):
57+
j = 0
58+
for i in range(len(nums)):
59+
if nums[i] != nums[j]:
60+
j += 1
61+
nums[j], nums[i] = nums[i], nums[j]
62+
# 不需要考虑数组中超出新长度后面的元素
63+
# nums[j] = nums[i]
64+
return j + 1
65+
5666
def count_dup(self, nums):
5767
count_dup = 0
5868
for i in range(1, len(nums)):
@@ -62,20 +72,10 @@ def count_dup(self, nums):
6272
nums[i - count_dup] = nums[i]
6373
return len(nums) - count_dup
6474

65-
def two_index(self, nums):
66-
j = 0
67-
for i in range(len(nums)):
68-
if nums[i] != nums[j]:
69-
j += 1
70-
nums[j] = nums[i]
71-
return j + 1
72-
7375
def count_non_dup(self, nums):
7476
count_ndup = 0
7577
for i in range(1, len(nums)):
7678
if nums[i] != nums[i - 1]:
7779
count_ndup += 1
7880
nums[count_ndup] = nums[i]
7981
return count_ndup + 1
80-
81-
# leetcode submit region end(Prohibit modification and deletion)

0 commit comments

Comments
 (0)