1. Array 题目

T11. 盛最多水的容器T283. 移动零T70. 爬楼梯T15. 3数之和T141. 环形链表

1.1 题目解析

T11. 盛最多水的容器 记住双指针模板。左右夹逼的办法 首先定义一个列表的index, 然后进行height[i]的比较，进而根据结果分别移动左index或者右边index. class Solution: def maxArea(self, height: List[int]) -> int: l ,r = 0 , len(height)-1 #记住，index是从0到len(height)-1 ； 如果是遍历那就是 in range(len(height)) area = 0 while l < r : contain = min(height[l],height[r])*(r-l) area= max(area,contain) if height[l] <= height[r]: l += 1 else: r -= 1 return area

时间复杂度O(n) 2. T283. 移动零 此题的思路是 仍然是双指针模型。 重要的是将非零的元素与它前面的第一个零交换。 首先创造一个slow 一个fast, 两个都从左边出发，fast 从0 开始，遇到非零的 就传递给slow；slow 接收到非零后+1。 直到fast访问到 len(nums)-1的位置。

class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ fast = slow =0 while fast < len(nums): if nums[fast] != 0: nums[fast] , nums[slow] = nums[slow] , nums[fast] if nums[slow] != 0: slow += 1 fast += 1

时间复杂度O(n) 4. T70. 爬楼梯 思路： kn= kn-1 + kn-2

class Solution: def climbStairs(self, n: int) -> int: if n == 1: return 1 if n == 2: return 2 one_step_before = 2 two_step_before = 1 extra_staires = 0 if n >= 3: while extra_staires < n-2: all_way = one_step_before + two_step_before two_step_before = one_step_before one_step_before = all_way extra_staires +=1 return all_way

时间复杂度O(1) 5. T15. 3数之和

class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: n = len(nums) if n < 3: return [] res = [] nums.sort() for i in range(n): if nums[i] > 0: return res if i >= 1 and nums[i] == nums[i-1]: #此处是i >= 1 continue L = i + 1 R = n - 1 while L < R: if (nums[i] + nums[L] + nums[R]) == 0: res.append([nums[i], nums[L], nums[R]]) while L < R and nums[L] == nums[L+1]:#此处用while L = L + 1 while L < R and nums[R] == nums[R-1]: R = R - 1 L = L + 1 R = R - 1 elif (nums[i] + nums[L] + nums[R]) > 0:#此处加小括号 R = R - 1 else: L = L + 1 return res

时间复杂度O(n^2) 6. T141. 环形链表

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def hasCycle(self, head: ListNode) -> bool: try: slow = head fast = head.next while slow is not fast: slow = slow.next fast = fast.next.next return True except: return False