b站@爱学习饲养员
（按视频学习刷题的过程记录，不完全是按照up主的思路，有时候会参考热门的题解）
数组
- 练习题 LC485
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
if nums is None or len(nums) == 0:
return 0
count = 0
result = 0
for i in range(len(nums)):
if nums[i] == 1:
count += 1
# result = max([result, count])
if result < count:
result = count
else:
count = 0
return result
- 练习题 LC283
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
l = 0
for r in range(n):
if nums[r] != 0:
nums[l] = nums[r]
l += 1
for i in range(l, n):
nums[i] = 0
- 练习题 LC27
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
# # 双指针
# l = 0
# for r in range(len(nums)):
# if nums[r] != val:
# nums[l] = nums[r]
# l += 1
# return l
# 双指针优化
l = 0
r = len(nums) - 1
while(l<=r):
if nums[l] == val:
nums[l] = nums[r]
r -= 1
else:
l += 1
return l
？？不知道为啥双指针优化的性能没有前面好
链表
- 练习题 LC203
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
dummy = ListNode(0)
dummy.next = head
prehead = dummy
while head:
if head.val == val:
prehead.next = head.next
else:
prehead = head
head = head.next
return dummy.next
- 练习题 LC206
饲养员的思路不太好理解，建议参考老汤的迭代求解思路
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# 饲养员版本
# class Solution:
# def reverseList(self, head: ListNode) -> ListNode:
# dummy = ListNode(0, head)
# while head and head.next:
# hNext = head.next
# dNext = dummy.next
# dummy.next = hNext
# head.next = hNext.next
# hNext.next = dNext
# return dummy.next
# 老杨迭代求解
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev = None
while head:
temp = head.next
head.next = prev
prev = head
head = temp
return prev
# # 老杨递归求解
# class Solution:
# def reverseList(self, head: ListNode) -> ListNode:
# if head is None or head.next is None:
# return head
# p = self.reverseList(head.next)
# head.next.next = head
# head = head.next
# return p
队列
- 练习题 LC933
class RecentCounter:
def __init__(self):
self.queue = deque()
def ping(self, t: int) -> int:
self.queue.append(t)
while len(self.queue) > 0 and t - self.queue[0] > 3000:
self.queue.popleft()
return len(self.queue)
# Your RecentCounter object will be instantiated and called as such:
# obj = RecentCounter()
# param_1 = obj.ping(t)
栈
- 练习题 LC20
class Solution:
def isValid(self, s: str) -> bool:
if len(s) == 0 or len(s) == 1:
return False
stack = []
for i in s:
if i == '(' or i == '{' or i == '[':
stack.append(i)
else:
if len(stack) == 0:
return False
if stack[-1] == '(' and i == ')':
stack.pop()
elif stack[-1] == '{' and i == '}':
stack.pop()
elif stack[-1] == '[' and i == ']':
stack.pop()
else:
return False
return True if len(stack) == 0 else False
哈希表
- 练习题 LC217
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
hashmap = {}
for i in nums:
if i in hashmap:
hashmap[i] += 1
if hashmap[i] >= 2:
return True
else:
hashmap[i] = 1
return False
- 练习题 LC389
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
if len(s) == 0:
return t
# 字典
# hashmap = {}
# for i in s:
# if i not in hashmap:
# hashmap[i] = 1
# else:
# hashmap[i] += 1
# for i in t:
# if i in hashmap:
# hashmap[i] += -1
# else:
# return i
# for key, val in hashmap.items():
# if val != 0:
# return key
# 数组
hashmap = [0] * 26
for i in s:
hashmap[ord(i)-97] += 1
for i in t:
hashmap[ord(i)-97] += -1
for i in range(26):
if hashmap[i] != 0:
return chr(i+97)
- 练习题 LC496
用了栈+哈希表
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
if len(nums1) == 0 or len(nums2) == 0:
return []
stack = []
hashmap = {}
stack.append(nums2[0])
for i in range(1, len(nums2)):
while len(stack) != 0 and stack[-1] < nums2[i]:
hashmap[stack[-1]] = nums2[i]
stack.pop()
stack.append(nums2[i])
for i in stack:
hashmap[i] = -1
return [hashmap[i] for i in nums1]
集合
- 练习题 LC217
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
numsSet = set(nums)
if len(numsSet) < len(nums):
return True
else:
return False
比用哈希表快