上一篇：献芹奏曝-Python面试题
开篇的话：本文目的是收集和归纳力扣上的算法题，希望用python语言，竭我所能做到思路最清奇、代码最简洁、方法最广泛、性能最高效，了解常见题目，找到最利于记忆的答案，更加从容的应对面试。希望广思集益，共同进步。
一、滑动窗口篇
-
3. 无重复字符的最长子串（难度系数✯）
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: cur_len = 0 # 定义当前长度 start_ind = 0 # 滑块的起始位置 end_ind = 0 # 滑块的终止位置 dict_item = {} if not s: return 0 for index, item in enumerate(s): end_ind = index # 尾部滑块动起来 if item in s[start_ind:end_ind]: cur_len = max(cur_len,end_ind-start_ind) start_ind = dict_item.get(item)+1 # 如果存在，头部滑块动起来 dict_item[item] = index # 字段的值判断后更新 return max(cur_len,end_ind-start_ind+1)View Code运行结果：1：耗时超过48%。2：内存超过74%
知识点/技巧:1：双指针、滑动窗口。2：注意返回时再重新算一下
-
239. 滑动窗口最大值（难度系数✯✯✯）
class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: head = 0 # 定义首 tail = k-1 # 定义尾 cur_max = max(nums[0:k]) result_list = [cur_max] n = len(nums) # 定义长度 for index in range(k,n): if nums[head]==cur_max: # 如果当前最大值即将被滑出,重新选举一个 cur_max=max(nums[index-k+1:index+1]) if nums[index] > cur_max: # 取而代之 cur_max = nums[index] result_list.append(cur_max) head += 1 tail += 1 return result_list超时的方法知识点/技巧:1：按照双指针滑动，直接硬搞
class Solution: """ 痛定思痛，之所以超时是由于 cur_max=max(nums[index-k+1:index+1]) 方法性能太差 定义一个 单调递减的序列，里面存储的是索引id """ def get_new_que_list(self, que_list, nums, index, k): if nums[que_list[0]] <= nums[index]: # 如果最大值 <= 当前值，清空队列 que_list = [] que_list.append(index) return que_list # 确保队列有序的关键所在 while que_list and nums[que_list[-1]] <= nums[index]: # 把队尾的元素与当前值比较，如果小就删除; que_list.pop() while que_list and que_list[0] <= index - k: # 头部元素已经滑出 que_list.pop(0) que_list.append(index) return que_list def maxSlidingWindow(self, nums, k): n = len(nums) # 定义长度 result_list = [nums[0]] que_list = [0] for i in range(k): que_list = self.get_new_que_list(que_list, nums, i, k) if result_list[0] <= nums[i]: result_list[0] = nums[i] for i in range(k, n): que_list = self.get_new_que_list(que_list, nums, i, k) result_list.append(nums[que_list[0]]) return result_list单调队列--（通过list模拟）运行结果：1：耗时超过23%。2：内存超过80%
知识点/技巧:1：维护单调队列的队首元素和队尾元素
class Solution: """ 使用collections中的队列， """ def maxSlidingWindow(self, nums, k): n = len(nums) # 定义长度 ans = [] q = collections.deque() # ps：引用collections 中的队列 for i in range(k): # 初始化 队列 (更新队尾元素) while q and nums[q[-1]]<=nums[i]: q.pop() q.append(i) ans.append(nums[q[0]]) for i in range(k,n): # 队列 (更新队尾元素) while q and nums[q[-1]]<=nums[i]: q.pop() # 队列 (更新队首元素) while q and q[0]<=i-k: q.popleft() # 注意队列删除左元素使用的是popleft() q.append(i) ans.append(nums[q[0]]) return ans单调队列--（使用collections的deque）比使用list性能更好运行结果：1：耗时超过95%。2：内存超过48%
知识点/技巧:1：维护单调队列的队首元素和队尾元素.2：注意引用的是collections中的deque()。它删除队首元素使用的popleft()
class Solution: """ 引用heapq使用堆搞定 # 注意 堆的调用都以heapq.heapXX开头， 初始化<=>heapq.heapify(h)； # 没有返回值 添加元素<=>heapq.heappush()； 删除顶元素<=>heapq.heappop()； """ def maxSlidingWindow(self, nums, k): n = len(nums) # 定义长度 ans = [] # 由于python中的是“小根堆（最小的值在根节点）” h = [(-nums[i],i) for i in range(k)] # 初始化堆：heapq.heapqify(array) heapq.heapify(h) ans.append(-h[0][0]) for i in range(k,n): while h and h[0][1]<=i-k: # 适时弹出 heapq.heappop(h) heapq.heappush(h,(-nums[i],i)) # 追加元素 ans.append(-h[0][0]) return ans优先队列--使用堆处理运行结果：1：耗时超过49%。2：内存超过14%
知识点/技巧:1：引用heapq使用堆.2：堆的调用都以heapq.heapXX开头。 初始化<=>heapq.heapify(h)； # 没有返回值 添加元素<=>heapq.heappush()； 删除顶元素<=>heapq.heappop()；
-
611. 有效三角形的个数（难度系数✯✯）
class Solution: def triangleNumber(self, nums: List[int]) -> int: # 排序 + 双指针滑动 (i为第1个指针，j 和k 分别为第2和第3个指针) nums.sort() # 排序 n = len(nums) result = 0 for i in range(n): for j in range(i+1,n): k = j+1 while k<n and nums[i]+nums[j]>nums[k]: result += 1 k += 1 return result超时的方法知识点/技巧：k的值每次从j+1开始不妥，可以优化。可以想象成游戏没有存档，每次失败后都从j+1处重新打。其实是可以适当存档的。
class Solution: def triangleNumber(self, nums: List[int]) -> int: # 排序 + 双指针滑动 nums.sort() # 排序 n = len(nums) result = 0 for i in range(n-2): k = i # 存档 for j in range(i+1,n-1): while k+1<n and nums[i]+nums[j]>nums[k+1]: k += 1 result += max(k-j,0) return result排序+指针存档运行结果：1：耗时超过54%。2：内存超过88%
知识点/技巧:1：先排序，2：对k存档，少去了很多不必要的重复计算
class Solution: def triangleNumber(self, nums) -> int: # 排序 + 双指针滑动 (i为第1个指针，j 和k 分别为第2和第3个指针) nums.sort() # 排序 n = len(nums) result = 0 for i in range(n - 2): for j in range(i + 1, n - 1): left = j right = n - 1 k = j while left <= right: mid = (right + left) // 2 if nums[mid] < nums[i] + nums[j]: k = mid left = mid + 1 else: right = mid - 1 result += max(k - j, 0) return result排序+二分查找运行结果：1：耗时超过5%。2：内存超过94%
知识点/技巧:1：先排序，2：再进行二分查找
class Solution: def triangleNumber(self, nums) -> int: # 排序 + 二分查找 nums.sort() # 排序 n = len(nums) result = 0 for i in range(n - 2): for j in range(i + 1, n - 1): k = bisect.bisect_left(nums, nums[i] + nums[j]) - 1 result += max(k - j, 0) return result利用python提供的二分查找运行结果：1：耗时超过34%。2：内存超过91%
知识点/技巧:1：先排序，2：利用python内部的二分查找
