新手刷题
Array数组
485. 最大连续 1 的个数
class Solution: def findMaxConsecutiveOnes(self, nums: List[int]) -> int: # 如果数组为空或长度为0，则直接返回0 if nums is None or len(nums) == 0: return 0 # count为当前连续的1的个数，res是上一个连续的1的个数 count = 0 res = 0 for num in nums: if num == 1: count += 1 # 遍历到的num为1则count+1 else: res = max(res, count) # 遇到0后，将res和count中的最大值赋值给res count = 0 # count重新为0 return max(res, count) # 因为最后一个数字为1时，并没有进行res=max(res,count),所以返回时需要再max一下
283. 移动零
1、两次遍历
class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ # 两次遍历 index = 0 # 第一次遍历，将所有非0的元素均赋值给nums[index] for i in range(len(nums)): if nums[i] != 0: nums[i], nums[index] = nums[index], nums[i] index += 1 # 第二次遍历，将索引index之后的元素全赋值为0 for i in range(index,len(nums)): nums[i] = 0 return nums
2、一次遍历
class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ # 一次遍历 # 两个指针i和j j = 0 for i in range(len(nums)): # 当前元素!=0，就把其交换到左边，等于0的交换到右边 if nums[i] != 0: nums[j],nums[i] = nums[i],nums[j] j += 1
27. 移除元素
1、首尾双指针
class Solution: def removeElement(self, nums: List[int], val: int) -> int: # 首尾双指针 if nums is None or len(nums) == 0: return 0 l = 0 r = len(nums) - 1 while(l < r): # l从头到尾找等于val的元素的索引 while(l < r and nums[l] != val): l += 1 # r从尾到头找不等于val的元素的索引 while(l < r and nums[r] == val): r -= 1 nums[l], nums[r] = nums[r], nums[l] # 因为跳出循环时，i,j可能都指向val或不指向val if nums[l] == val: return l else: return l+1
2、快慢双指针
class Solution: def removeElement(self, nums: List[int], val: int) -> int: # 快慢指针 if not nums: return 0 n = len(nums) fast = slow = 0 #两个指针初始位置都为0，fast指针用来遍历数组 while fast < n: if nums[fast] != val: #当fast指向的元素不等于val时，将fast的值赋予slow nums[slow] = nums[fast] slow += 1 fast += 1 return slow
1. 两数之和
1、暴力解法：时间复杂度为N(N*N)
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(0, len(nums)): for j in range(i + 1, len(nums)): if nums[i] + nums[j] == target: return [i,j]
2、哈希字典
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: hashtable = {} # hashmap = dict()，创建一个空字典 for i, num in enumerate(nums): # enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for循环当中。 if target - num in hashtable: # 循环遍历num时，如果hashtable中已经有另一个元素（target-num）在哈希表中，则直接返回这两个元素的索引 return [hashtable[target - num], i] hashtable[num] = i # 否则将该元素和索引添加到字典中 return []
268. 丢失的数字
1、排序
class Solution: def missingNumber(self, nums: List[int]) -> int: # 将数组排序之后，即可根据数组中每个下标处的元素是否和下标相等，得到丢失的数字。 nums.sort() for i, num in enumerate(nums): if num != i: return i return len(nums)
2、哈希集合
class Solution: def missingNumber(self, nums: List[int]) -> int: # 哈希集合：首先遍历数组nums，将数组中的每个元素加入哈希集合，然后依次检查从0到n的每个整数是否在哈希集合中，不在哈希集合中的数字即为丢失的数字。 s = set(nums) for i in range(len(nums) + 1): if i not in s: return i
78. 子集
1、使用库函数
class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: # itertools模块combinations(iterable, r)方法可以创建一个迭代器，返回iterable中所有长度为r的子序列，返回的子序列中的项按输入iterable中的顺序排序。 res = [] for i in range(len(nums) + 1): for num in itertools.combinations(nums, i): # 子序列默认是元组，所以将其转化为list res.append(list(num)) return res
2、迭代
Linked List链表
203. 移除链表元素
# 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，和双指针prev、cur dummy = ListNode(0) dummy.next = head prev, cur = dummy, head while cur: # 当head不为空时,进入循环 if cur.val == val: # 当head指向的值等于val时，进行删除操作 prev.next = cur.next cur = cur.next else: # 当head指向的值不等于val时，prev和head依次向后移 prev = cur cur = cur.next return dummy.next
206. 反转链表
1、双指针
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def reverseList(self, head: ListNode) -> ListNode: # 双指针 pre, cur = None, head # 初始化两个指针，一个指向头节点，一个指向None while cur: # 当cur指向None时，跳出循环 tmp = cur.next # 临时指针指向cur的后继节点 cur.next = pre # 断开原来cur的后继节点，使其指向pre pre = cur # pre指向cur cur = tmp # cur指向tmp，即一次循环内cur的后继节点 return pre
2、头插法
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def reverseList(self, head: ListNode) -> ListNode: # 头插法，往cur节点前插入节点 cur = None while head: newNode = ListNode(head.val) #将原始列表的节点的val形成一个节点 head = head.next # head指向下一个节点 newNode.next = cur # newNode.next指向cur cur = newNode # cur指向新的节点 return cur
Queue队列
933. 最近的请求次数
class RecentCounter: def __init__(self): # 使用列表初始化一个队列 self.lst = [] def ping(self, t: int) -> int: # 将t入队 self.lst.append(t) # 如果t与队列头元素差值大于3000，需要将对头出队，因为题目解释需要返回过去 3000 毫秒内发生的所有请求数（包括新请求） while t - self.lst[0] > 3000: self.lst.pop(0) # 最后返回队列长度即可 return len(self.lst) # Your RecentCounter object will be instantiated and called as such: # obj = RecentCounter() # param_1 = obj.ping(t)