面向腾子的leetcode刷题
临阵磨枪说是
NO.146 LRU缓存
https://leetcode.cn/problems/lru-cache/solutions/259678/lruhuan-cun-ji-zhi-by-leetcode-solution/
题目提到键值对，想到构建hash表，涉及到出入顺序，想到栈、队列和链表，由于要实现顺序更新，使用双向链表
hash表键自设，值为指向链表元素的引用 双向链表键与hash表键一致，值为实际存储值
class DLinkedNode:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.cache = dict()
# 使用伪头部和伪尾部节点
self.head = DLinkedNode()
self.tail = DLinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
self.capacity = capacity
self.size = 0 # 当前缓存中的节点数
def get(self, key: int) -> int:
if key not in self.cache: # 实例变量
return -1
# 如果 key 存在，先通过哈希表定位，再移到头部
node = self.cache[key]
self.moveToHead(node)
return node.value
def put(self, key: int, value: int) -> None:
if key not in self.cache:
# 如果 key 不存在，创建一个新的节点
node = DLinkedNode(key, value)
# 添加进哈希表
self.cache[key] = node
# 添加至双向链表的头部
self.addToHead(node)
self.size += 1
if self.size > self.capacity:
# 如果超出容量，删除双向链表的尾部节点
removed = self.removeTail()
# 删除哈希表中对应的项
self.cache.pop(removed.key)
self.size -= 1
else:
# 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
node = self.cache[key]
node.value = value
self.moveToHead(node)
def addToHead(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def removeNode(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def moveToHead(self, node):
self.removeNode(node)
self.addToHead(node)
def removeTail(self):
node = self.tail.prev
self.removeNode(node)
return nodeNO.3 无重复字符的最长子串
使用双指针+哈希，构建滑动窗口，左指针每次右移一次，右指针右移至出现重复（使用hash判断）
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
length = len(s)
if length <= 1: return length
left,right = 0,1
hashset = set()
longest = 0
hashset.add(s[left])
while right < length:
if s[right] not in hashset:
hashset.add(s[right])
longest = max(longest, right - left + 1)
right += 1
else:
hashset.remove(s[left])
left += 1
return longestNO.1262 可被三整除的最大和
动态规划
三个变量来表示状态：dp[0]表示能被3整除且余数为0的元素的最大和，dp[1]表示能被3整除且余数为1的元素的最大和，dp[2]表示能被3整除且余数为2的元素的最大和。每步进一次更新三个位置的数
如果n%3余数为0，则n加入012哪个位置都不会改变余数，所以三个位置都加n
如果余数为1，则对于dp[0]要比较dp[0]和dp[2]+n的大小，因为此时这两者的余数都为0，较大者更新dp[0]，同理更新1和2位置
余数为2同理
关于初始化的问题，要求的值就是要返回的dp[0]，因为此时数组还没有步进，所以是零，而对于位置1和2，因为此时数组还没有步进，所以不存在，因此要设置为负无穷才能正常运行，所以虽然012三个位置在数组中是并列的，但是它们在初始化时在逻辑上其实不在同一层
class Solution:
def maxSumDivThree(self, nums: List[int]) -> int:
dp = [0, float('-inf'), float('-inf')]
for num in nums:
remainder = num % 3
if remainder == 0:
dp[0] += num
dp[1] += num
dp[2] += num
elif remainder == 1:
dp[0], dp[1], dp[2] = max(dp[0], dp[2] + num), max(dp[1], dp[0] + num), max(dp[2], dp[1] + num)
else:
dp[0], dp[1], dp[2] = max(dp[0], dp[1] + num), max(dp[1], dp[2] + num), max(dp[2], dp[0] + num)
return dp[0]NO. 21 合并两个有序链表
初始化两个同时指向新链表头部的结点，一个一直向后走（并进行逻辑判断），另一个用于便捷的返回新链表
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
cur = dummy = ListNode()
while list1 and list2:
if list1.val < list2.val:
cur.next = list1
list1 = list1.next
else:
cur.next = list2
list2 = list2.next
cur = cur.next
cur.next = list1 if list1 else list2
return dummy.nextNO. 23 合并K个升序链表
利用上一题的解法，先将左半部分链表合并，再将右半部分合并，最后将这两个部分合并
class Solution:
# 21. 合并两个有序链表
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
cur = dummy = ListNode() # 用哨兵节点简化代码逻辑
while list1 and list2:
if list1.val < list2.val:
cur.next = list1 # 把 list1 加到新链表中
list1 = list1.next
else: # 注：相等的情况加哪个节点都是可以的
cur.next = list2 # 把 list2 加到新链表中
list2 = list2.next
cur = cur.next
cur.next = list1 if list1 else list2 # 拼接剩余链表
return dummy.next
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
m = len(lists)
if m == 0: return None # 注意输入的 lists 可能是空的
if m == 1: return lists[0] # 无需合并，直接返回
left = self.mergeKLists(lists[:m // 2]) # 合并左半部分
right = self.mergeKLists(lists[m // 2:]) # 合并右半部分
return self.mergeTwoLists(left, right) # 最后把左半和右半合并NO.1 两数之和
创建一张hashmap，键为数组中的值，值为其位置
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashtable = {}
for i in range(len(nums)):
if target - nums[i] in hashtable:
return [hashtable[target - nums[i]], i]
hashtable[nums[i]] = i
return []NO.24 两两交换链表中的节点
迭代
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
node0 = dummy = ListNode(next=head) # 用哨兵节点简化代码逻辑
node1 = head
while node1 and node1.next: # 至少有两个节点
node2 = node1.next
node3 = node2.next
node0.next = node2 # 0 -> 2
node2.next = node1 # 2 -> 1
node1.next = node3 # 1 -> 3
node0 = node1 # 下一轮交换，0 是 1
node1 = node3 # 下一轮交换，1 是 3
return dummy.next # 返回新链表的头节点递归
真不会
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None: # 递归边界
return head # 不足两个节点，无需交换
node1 = head
node2 = head.next
node3 = node2.next
node1.next = self.swapPairs(node3) # 1 指向递归返回的链表头
node2.next = node1 # 2 指向 1
return node2 # 返回交换后的链表头节点NO.870 优势洗牌
本质是田忌赛马，将nums1和nums2逐个比较，使用双指针，分别指向nums2的头和尾
用nums1的最小值比较nums2的最小值，如果超过则nums1得分（符合要求逻辑）步进
如果没超过，则用nums1最小值和nums2最大值比，步进
class Solution:
def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
n = len(nums1)
ans = [0] * n
nums1.sort()
# 不能修改nums2，于是生成一个排序过后的nums2的下标组成的list
ids = sorted(range(n), key=lambda i: nums2[i])
left, right = 0, n - 1
for x in nums1:
if x > nums2[ids[left]]:
ans[ids[left]] = x # 用下等马比下等马
left += 1
else:
ans[ids[right]] = x # 用下等马比上等马
right -= 1
return ans