作者：天使的泪无人知晓 | 来源：互联网 | 2023-05-18 16:56
【数组】实现一个支持动态扩容的数组实现一个大小固定的有序数组，支持动态增删改操作实现两个有序数组合并为一个有序数组学习哈希表思想，并完成leetcode上的两数之和(1)及
【数组】
- 实现一个支持动态扩容的数组
- 实现一个大小固定的有序数组，支持动态增删改操作
- 实现两个有序数组合并为一个有序数组
- 学习哈希表思想，并完成leetcode上的两数之和(1)及Happy Number(202)！(要求全部用哈希思想实现！)（选做）（注意：在第四天会进行继续学习）
练习：
1. 三数之和，Leetcode 13 https://leetcode-cn.com/problems/3sum/
思路：双指针
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n = len(nums)
res = []
for i in range(n):
j = i+1
k = n-1
if i>0 and nums[i] == nums[i-1]:
continue
while j<k:
if nums[i]+nums[j]+nums[k] == 0:
res.append([nums[i],nums[j],nums[k]])
k -= 1
j += 1
while jand nums[j] == nums[j-1]:
j += 1
while jand nums[k] == nums[k+1]:
k -= 1
elif nums[i]+nums[j]+nums[k] > 0:
k -= 1
else:
j += 1
return res
2. 求众数，Leetcode 169 https://leetcode-cn.com/problems/majority-element/
思路：字典
class Solution:
def majorityElement(self, nums: List[int]) -> int:
dic={}
for n in nums:
if n in dic:
dic[n]+=1
else:
dic[n]=1
return max(dic, key=dic.get)
3. 求缺失的第一个正数 [作为可选]，Leetcode 41 https://leetcode-cn.com/problems/first-missing-positive/
思路：整理数组
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
j = 0
while j and j + 1 == nums[j]:
j += 1
return j + 1
【链表】
- 实现单链表、循环链表、双向链表，支持增删操作
- 实现单链表反转
- 实现两个有序的链表合并为一个有序链表
- 实现求链表的中间结点
练习：
1. 环形链表，Leetcode 141 https://leetcode-cn.com/problems/linked-list-cycle/
思路：1. 快慢指针 2. 字典 3. 集合
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
'''
#快慢指针
fast, slow=head, head
while fast and fast.next:
fast=fast.next.next
slow=slow.next
if fast == slow:
return True
return False
'''
'''
#字典,使用hash的去重思想
dic={}
while head:
if head not in dic:
dic[head]=1
head=head.next
else:
return True
return False
'''
#set,使用hash的去重思想
hashset=set()
while head:
if head not in hashset:
hashset.add(head)
head=head.next
else:
return True
return False
2.合并 k 个排序链表，Leetcode 23 https://leetcode-cn.com/problems/merge-k-sorted-lists/
思路：分而治之
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists:return
n = len(lists)
return self.merge(lists, 0, n-1)
def merge(self,lists, left, right):
if left == right:
return lists[left]
mid = (right + left) // 2
l1 = self.merge(lists, left, mid)
l2 = self.merge(lists, mid+1, right)
return self.mergeTwoLists(l1, l2)
def mergeTwoLists(self,l1, l2):
if not l1:return l2
if not l2:return l1
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
京公网安备 11010802041100号