devbox
凡人多烦事01
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

coding_v3

作者：凡人多烦事01 | 2024-03-01 04:38:02

赞

踩

coding_v3

面试经典 150 题 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台

LeetCode 75 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台

数组/字符串

1.LC88【合并两个有序数组】

  1. def solve(nums1, m, nums2, n):
  2.     p1, p2 = m-1, n-1
  3.     tail = m + n -1
  4.     while p1 >= 0 or p2 >= 0:
  5.         if p1 == -1:
  6.             nums1[tail] = nums2[p2]
  7.             p2 -= 1
  8.         elif p2 == -1:
  9.             nums1[tail] = nums1[p1]
  10.             p1 -= 1
  11.         elif nums1[p1] > nums2[p2]:
  12.             nums1[tail] = nums1[p1]
  13.             p1 -= 1
  14.         else:
  15.             nums1[tail] = nums2[p2]
  16.             p2 -= 1
  17.         tail -= 1

2、LC27【原地移除指定元素】

  1. # 原地删除元素指定值
  2. def solve(nums, val):
  3.     n = len(nums)
  4.     left = 0
  5.     for i in range(n):
  6.         if nums[i] != val:
  7.             nums[left] = nums[i]
  8.             left += 1
  9.     return left

3、LC26【原地删除有序数组重复元素】

  1. # 原地删除数组重复元素
  2. def solve(nums):
  3.     n = len(nums)
  4.     left, right = 1, 1
  5.     while right < n:
  6.         if nums[right] != nums[right-1]:
  7.             nums[left] = nums[right]
  8.             left += 1
  9.         right += 1
  10.     return left

4、LC80【原地删除有序数组重复元素2】

  1. # 原地删除数组重复元素【超过两个的元素只保留两个】
  2. def solve(nums):
  3.     n = len(nums)
  4.     left, right = 2, 2
  5.     while right < n:
  6.         if nums[right] != nums[left-2]:
  7.             nums[left] = nums[right]
  8.             left += 1
  9.         right += 1
  10.     return left

5、LC1768【交替合并字符串】

  1. # 交替合并字符串
  2. def solve(word1, word2):
  3.     m, n = len(word1), len(word2)
  4.     p, q = 0, 0
  5.     res = []
  6.     while p < m or q < n:
  7.         if p < m:
  8.             res.append(word1[p])
  9.             p += 1
  10.         if q < n:
  11.             res.append(word2[q])
  12.             q += 1
  13.     return ''.join(res)

6、LC1071【字符串最大公因子】

  1. # 字符串的最大公因子
  2. import math
  3. def solve(str1, str2):
  4.     res_len = math.gcd(len(str1), len(str2))
  5.     if str1[:res_len] * (len(str1) // res_len) == str1 and str1[:res_len] * (len(str2) // res_len) == str2:
  6.         return str1[:res_len]
  7.     return ''

7、LC605【种花问题】

  1. # 种花
  2. def solve(flowerbed, n):
  3.     i = 0
  4.     m = len(flowerbed)
  5.     while i < m:
  6.         if (flowerbed[i] == 0) and (i==0 or flowerbed[i-1] == 0) and (i==m-1 or flowerbed[i+1] == 0):
  7.             i += 2
  8.             n -= 1
  9.         else:
  10.             i += 1
  11.     return n <= 0

8、LC345【翻转字符串中的元音字母】

  1. # 翻转元音字母
  2. def solve(s):
  3.     n = len(s)
  4.     lst = list(s)
  5.     i, j = 0, n-1
  6.     while i < j:
  7.         while i < n and not judge(lst[i]):
  8.             i += 1
  9.         while j > 0 and not judge(lst[j]):
  10.             j -= 1
  11.         if i < j:
  12.             lst[i], lst[j] = lst[j], lst[i]
  13.             i += 1
  14.             j -= 1
  15.     return ''.join(lst)
  16.  
  17. def judge(item):
  18.     if item in ('a','e','i','o','u','A','E','I','O','U'):
  19.         return 1
  20.     else:
  21.         return 0

9、LC151【翻转字符串中的单词】

  1. # 翻转单词
  2. def solve(s):
  3.     s = s.strip()
  4.     n = len(s)
  5.     i, j = n-1, n-1
  6.     res = []
  7.     while i >= 0:
  8.         while i >= 0 and s[i] != ' ':
  9.             i -= 1
  10.         res.append(s[i+1:j+1])
  11.         while i >= 0 and s[i] == ' ':
  12.             i -= 1
  13.         j = i
  14.     return ' '.join(res)

10、LC238【除自身以外的乘积】

  1. # 除自身以外的数组乘积
  2. def solve(nums):
  3.     ans = [1] * len(nums)
  4.     # 元素左半部分乘积
  5.     for i in range(1, len(nums)):
  6.         ans[i] = ans[i-1] * nums[i-1]
  7.     # 元素右半部分乘积
  8.     ans1 = [1] * len(nums)
  9.     for i in range(len(nums)-2,-1,-1):
  10.         ans1[i] = ans1[i+1] * nums[i+1]
  11.     res = [ans[i] * ans1[i] for i in range(len(ans))]
  12.     return res
  13.

11、LC334【递增三元子序列】

  1. # 递增的三元子序列
  2. def solve(nums):
  3.     n = len(nums)
  4.     if n < 3:
  5.         return False
  6.     small, mid = nums[0], float('inf')
  7.     for i in range(n):
  8.         if nums[i] > mid:
  9.             return True
  10.         if nums[i] > small:
  11.             mid = nums[i]
  12.         else:
  13.             small = nums[i]
  14.     return False

12、LC443【压缩字符串】

  1. # 压缩字符串
  2. def solve(chars):
  3.     def reverse(left, right):
  4.         while left < right:
  5.             chars[left], chars[right] = chars[right], chars[left]
  6.             left += 1
  7.             right -= 1
  8.             
  9.     left, write = 0, 0
  10.     n = len(chars)
  11.     for i in range(n):
  12.         if i == n-1 or chars[i] != chars[i+1]:
  13.             chars[write] = chars[i]
  14.             write += 1
  15.             nums = i - left + 1
  16.             if nums > 1:
  17.                 anchor = write
  18.                 while nums > 0:
  19.                     chars[write] = str(nums % 10)
  20.                     write += 1
  21.                     nums //= 10
  22.                 reverse(anchor, write-1)
  23.             left = i + 1
  24.     return write, chars[:write]

13、LC55【跳跃游戏】

  1. # 跳跃游戏
  2. def solve(nums):
  3.     n = len(nums)
  4.     most = 0
  5.     for i in range(n):
  6.         if i <= most:
  7.             most = max(most, i + nums[i])
  8.             if most >= n - 1:
  9.                 return True
  10.     return False

双指针

1、LC283【移动零】

  1. # 移动0
  2. def solve(nums):
  3.     i = 0
  4.     for j in range(len(nums)):
  5.         if nums[j]:
  6.             nums[i], nums[j] = nums[j], nums[i]
  7.             i += 1

2、LC392【判断子序列】

  1. # 判断子序列
  2. def solve(s, t):
  3.     if not s:
  4.         return True
  5.     i = 0
  6.     for c in t:
  7.         if s[i] == c:
  8.             i += 1
  9.             if i == len(s):
  10.                 return True
  11.     return False

3、LC11【盛水最多的容器】

  1. # 盛最多水的容器
  2. def solve(height):
  3.     i, j = 0, len(height)-1
  4.     res = 0
  5.     while i < j:
  6.         if height[i] < height[j]:
  7.             res = max(res, height[i] * (j-i))
  8.             i += 1
  9.         else:
  10.             res = max(res, height[j] * (j-i))
  11.             j -= 1
  12.     return res

4、LC167【两数之和 有序数组】

  1. # 两数之和2 有序数组
  2. def solve(nums, target):
  3.     left, right = 0, len(nums) - 1
  4.     while left < right:
  5.         total = nums[left] + nums[right]
  6.         if total == target:
  7.             return [left + 1, right + 1]
  8.         elif total < target:
  9.             left += 1
  10.         else:
  11.             right -= 1
  12.     return [-1, -1]

滑动窗口

1、LC643【子数组最大平均数】

  1. # 子数组的最大平均数
  2. def solve(nums,k):
  3.     res = total = sum(nums[:k])
  4.     for i in range(k,len(nums)):
  5.         total = total-nums[i-k]+nums[i]
  6.         res = max(res, total)
  7.     return res / k

2、LC1456【定长子串中元音的数目】

  1. # 定长字串中元音最大数目
  2. def solve(s, k):
  3.     def judge(ch):
  4.         return int(ch in 'aeiou')
  5.     n = len(s)
  6.     start = 0
  7.     for i in range(k):
  8.         start += judge(s[i])
  9.     res = start
  10.     for i in range(k,n):
  11.         start += judge(s[i]) - judge(s[i-k])
  12.         res = max(res, start)
  13.     return res

3、LC1004【最大连续1的个数】

  1. # 最大连续1的个数
  2. def solve(nums, k):
  3.     n = len(nums)
  4.     res = zeros = 0
  5.     left = right = 0
  6.     while right < n:
  7.         if nums[right] == 0:
  8.             zeros += 1
  9.         while zeros > k:
  10.             if nums[left] == 0:
  11.                 zeros -= 1
  12.             left += 1
  13.         res = max(res, right-left+1)
  14.         right += 1
  15.     return res

4、LC1493【删除一个元素后全为1的最长子数组】

  1. # 删除一个元素后全为1的最长子数组
  2. def solve(nums):
  3.     ans = 0
  4.     p0 = p1 = 0
  5.     for i in range(len(nums)):
  6.         if nums[i] == 0:
  7.             p1, p0 = p0, 0
  8.         else:
  9.             p0 += 1
  10.             p1 += 1
  11.         ans = max(ans, p1)
  12.     if ans == len(nums):
  13.         ans -= 1
  14.     return ans

5、LC209【长度最小的子数组】

  1. # 长度最小的子数组
  2. def solve(target, nums):
  3.     left, right = 0, 0
  4.     ans = len(nums) + 1
  5.     total = 0
  6.     while right < len(nums):
  7.         total += nums[right]
  8.         while  total >= target:
  9.             ans = min(ans, right - left + 1)
  10.             total -= nums[left]
  11.             left += 1
  12.         right += 1
  13.     if ans == len(nums) + 1:
  14.         return 0
  15.     else:
  16.         return ans

6、LC3【无重复字符的最长子串】

  1. # 无重复字符的最长子串
  2. def solve(s):
  3.     dic = {}
  4.     res = 0
  5.     i = -1
  6.     for j in range(len(s)):
  7.         if s[j] in dic:
  8.             i = max(dic[s[j]], i)
  9.         dic[s[j]] = j
  10.         res = max(res, j - i)
  11.     return res

前缀和

1、LC1732【找到最高海拔】

  1. # 找到最高海拔
  2. def solve(gain):
  3.     ans = total = 0
  4.     for each in gain:
  5.         total += gain
  6.         ans = max(ans, total)
  7.     return ans

2、LC724【寻找数组的中心下标】

  1. # 寻找数组的中心下标
  2. def solve(nums):
  3.     left, right = 0, sum(nums)
  4.     for i in range(len(nums)):
  5.         right -= nums[i]
  6.         if left == right:
  7.             return i
  8.         left += nums[i]
  9.     return -1

哈希表、哈希集合

1、LC2215【找出两数组的不同】

  1. # 找出两数组的不同
  2. def solve(nums1, nums2):
  3.     set1 = set(nums1)
  4.     set2 = set(nums2)
  5.     res1 = []
  6.     res2 = []
  7.     for each in set1:
  8.         if each not in set2:
  9.             res1.append(each)
  10.     for each in set2:
  11.         if each not in set1:
  12.             res2.append(each)
  13.     return [res1, res2]

2、LC1207【独一无二的出现次数】

  1. # 独一无二的出现次数
  2. def solve(arr):
  3.     dic = {}
  4.     for each in arr:
  5.         if each in dic:
  6.             dic[each] += 1
  7.         else:
  8.             dic[each] = 1
  9.     res = list(dic.values())
  10.     return len(res) == len(set(res))

3、LC1657【确定两个字符串是否接近】

  1. # 两个字符串是否接近
  2. def solve(word1, word2):
  3.     c1 = [0] * 26
  4.     c2 = [0] * 26
  5.     for each in word1:
  6.         c1[ord(each)-ord('a')] += 1
  7.     for each in word2:
  8.         c2[ord(each)-ord('a')] += 1
  9.     for i in range(26):
  10.         if c1[i] + c2[i] == 0:
  11.             continue
  12.         if c1[i] == 0 or c2[i] == 0:
  13.             return False
  14.     c1.sort()
  15.     c2.sort()
  16.     for i in range(26):
  17.         if c1[i] != c2[i]:
  18.             return False
  19.     return True

4、LC2352【相等行列对】

  1. # 相等行列对
  2. def solve(grid):
  3.     m, n = len(grid), len(grid[0])
  4.     grid_col = [[0] * m for _ in range(n)]
  5.     for i, g in enumerate(grid):
  6.         for j, x in enumerate(g):
  7.             grid_col[j][i] = x
  8.     res = 0
  9.     for each in grid:
  10.         for ee in grid_col:
  11.             if each == ee:
  12.                 res += 1
  13.     return res

栈

1、LC2390【从字符串中移除星号】

  1. # 从字符串中移除星号
  2. def solve(s):
  3.     stack = []
  4.     for each in s:
  5.         if each == '*':
  6.             stack.pop()
  7.         else:
  8.             stack.append(each)
  9.     return ''.join(stack)

2、LC735【小行星碰撞】

  1. # 小行星碰撞
  2. def solve(asteroids):
  3.     stk = []
  4.     for t in asteroids:
  5.         ok = True
  6.         while ok and stk and stk[-1] > 0 and t < 0:
  7.             a, b = stk[-1], -t
  8.             if a <= b:
  9.                 stk.pop(-1)
  10.             if a >= b:
  11.                 ok = False
  12.         if ok:
  13.             stk.append(t)
  14.     return stk

3、LC394【字符串解码】

  1. # 字符串解码
  2. def solve(s):
  3.     stk = []
  4.     res = ''
  5.     multi = 0
  6.     for each in s:
  7.         if each == '[':
  8.             stk.append([multi, res])
  9.             multi = 0
  10.             res = ''
  11.         elif each == ']':
  12.             cur_multi, cur_res = stk.pop()
  13.             res = cur_res + cur_multi * res
  14.         elif each >= '0' and each <= '9':
  15.             multi = multi * 10 + int(each)
  16.         else:
  17.             res += each
  18.     return res

队列

1、LC649【Dota2 参议院】

  1. # 参议院
  2. def solve(senate):
  3.     n = len(senate)
  4.     r = collections.deque()
  5.     d = collections.deque()
  6.     for i, c in enumerate(senate):
  7.         if c == 'R':
  8.             r.append(i)
  9.         if c == 'D':
  10.             d.append(i)
  11.     while r and d:
  12.         if r[0] < d[0]:
  13.             r.append(r[0]+n)
  14.         else:
  15.             d.append(d[0]+n)
  16.         r.popleft()
  17.         d.popleft()
  18.     return 'Radiant' if r else 'Dire'

链表

1、LC2095【删除链表的中间节点】

  1. # 删除链表的中间节点
  2. def solve(head):
  3.     if head.next is None:
  4.         return None
  5.     slow, fast, pre = head, head, None
  6.     while fast and fast.next:
  7.         pre = slow
  8.         slow = slow.next
  9.         fast = fast.next.next
  10.     pre.next = slow.next
  11.     return head

2、LC328【奇偶链表】

  1. # 奇偶链表
  2. def solve(head):
  3.     if not head:
  4.         return head
  5.     evenHead = head.next
  6.     odd, even = head, evenHead
  7.     while even and even.next:
  8.         odd.next = even.next
  9.         odd = odd.next
  10.         even.next = odd.next
  11.         even = even.next
  12.     odd.next = evenHead
  13.     return head

3、LC206【反转链表】

  1. # 反转链表
  2. def solve(head):
  3.     cur, pre = head, None
  4.     while cur:
  5.         tmp = cur.next
  6.         cur.next = pre
  7.         pre = cur
  8.         cur = tmp
  9.     return pre

4、LC2130【链表最大孪生和】

  1. # 链表最大孪生和
  2. def solve(head):
  3.     # 快慢指针找中点
  4.     slow, fast = head, head.next
  5.     while fast.next:
  6.         slow = slow.next
  7.         fast = fast.next.next
  8.     # 反转后半部分链表
  9.     cur, pre = slow.next, None
  10.     while cur:
  11.         tmp = cur.next
  12.         cur.next = pre
  13.         pre = cur
  14.         cur = tmp
  15.     # 取head和pre的值求和
  16.     res = 0
  17.     while pre:
  18.         cur_res = head.val + pre.val
  19.         res = max(cur_res, res)
  20.         head = head.next
  21.         pre = pre.next
  22.     return res

5、字符串转链表

  1. # 字符串转链表
  2. class ListNode:
  3.     def __init__(self, val=0, next=None):
  4.         self.val = val
  5.         self.next = next
  6.         
  7. def solve(s):
  8.     prehead = ListNode(-1)
  9.     prev = prehead
  10.     for each in s:
  11.         prev.next = ListNode(each)
  12.         prev = prev.next
  13.     return prehead.next

二叉树

0、二叉树定义

  1. # 二叉树
  2. class TreeNode:
  3.     def __init__(self, val=0, left=None, right=None):
  4.         self.val = val
  5.         self.left = left
  6.         self.right = right
  7.         
  8. node1 = TreeNode(2)
  9. node2 = TreeNode(5)
  10. node3 = TreeNode(7)
  11. node4 = TreeNode(9)
  12.  
  13.  
  14. node1.left = node2
  15. node1.right = node3

1、LC104【二叉树的最大深度】

深度优先

  1. # 深度优先
  2. def solve(root):
  3.     if not root:
  4.         return 0
  5.     return max(solve(root.left), solve(root.right)) + 1

广度优先

  1. # 广度优先
  2. def solve(root):
  3.     if not root:
  4.         return 0
  5.     quene = [root]
  6.     res = 0
  7.     while quene:
  8.         tmp = []
  9.         for node in quene:
  10.             if node.left:
  11.                 tmp.append(node.left)
  12.             if node.right:
  13.                 tmp.append(node.right)
  14.         quene = tmp
  15.         res += 1
  16.     return res

2、LC872【叶子相似的树】

深度优先

  1. # 叶子相似的树
  2. def solve(root1, root2):
  3.     def dfs(node):
  4.         if not node.left and not node.right:
  5.             return [node.val]
  6.         elif node.left and not node.right:
  7.             return dfs(node.left)
  8.         elif not node.left and node.right:
  9.             return dfs(node.right)
  10.         else:
  11.             return dfs(node.left) + dfs(node.right)
  12.     return dfs(root1) == dfs(root2)

3、LC1448【统计二叉树中好节点的数目】

  1. #统计二叉树中好节点的数目
  2. def solve(root):
  3.     def dfs(root, value):
  4.         if not root:
  5.             return 0
  6.         res = 0
  7.         if root.val >= value:
  8.             res += 1
  9.             value = root.val
  10.         res += dfs(root.left, value) + dfs(root.right, value)
  11.         return res
  12.     return dfs(root, -10**9)

4、LC112【路径总和1】

深度优先

  1. # 深度优先
  2. def solve(root, targetSum):
  3.     if not root:
  4.         return False
  5.     if not root.left and not root.right:
  6.         return root.val == targetSum
  7.     return solve(root.left, targetSum-root.val) or solve(root.right, targetSum-root.val)

广度优先

  1. def solve(root, tagetSum):
  2.     if not root:
  3.         return False
  4.     quene_node = [root]
  5.     quene_val = [root.val]
  6.     while quene_node:
  7.         tmp_node = quene_node.pop(0)
  8.         tmp_val = quene_val.pop(0)
  9.         if not tmp_node.left and not tmp_node.right:
  10.             if tmp_val == targetSum:
  11.                 return True
  12.             continue
  13.         if tmp_node.left:
  14.             quene_node.append(tmp_node.left)
  15.             quene_val.append(tmp_val + tmp_node.left.val)
  16.         if tmp_node.right:
  17.             quene_node.append(tmp_node.right)
  18.             quene_val.append(tmp_val + tmp_node.right.val)
  19.     return False

5、LC113【路径总和2】

回溯

  1. # 路径总和2
  2. # 回溯
  3. def solve(root, targetSum):
  4.     res, path = [], []
  5.     def back(root, target):
  6.         if not root:
  7.             return
  8.         path.append(root.val)
  9.         target -= root.val
  10.         if target == 0 and not root.left and not root.right:
  11.             res.append(path)
  12.         back(root.left, target)
  13.         back(root.right, target)
  14.         path.pop()
  15.     back(root, targetSum)
  16.     return res

6、LC437【路径总和3】

深度优先

  1. # 路径总和3
  2. # 深度优先
  3. def solve(root, targetSum):
  4.     if not root:
  5.         return 0
  6.     def kernel(root, targetSum):
  7.         if not root:
  8.             return 0
  9.         res = 0
  10.         if root.val == targetSum:
  11.             res += 1
  12.         res += kernel(root.left, targetSum - root.val)
  13.         res += kernel(root.right, targetSum - root.val)
  14.         return res
  15.     res = kernel(root, targetSum)
  16.     res += solve(root.left, targetSum)
  17.     res += solve(root.right, targetSum)
  18.     return res

7、LC1372【二叉树的最长交错路径】

深度优先

  1. # 二叉树的最长交错路径
  2. def solve(root):
  3.     res = 0
  4.     def dfs(root, direction, length):
  5.         if not root:
  6.             return
  7.         nonlocal res
  8.         res = max(res, length)
  9.         if direction == 0:
  10.             dfs(root.left, 1, length+1)
  11.             dfs(root.right, 0, 1)
  12.         if direction == 1:
  13.             dfs(root.right, 0, length+1)
  14.             dfs(root.left, 1, 1)
  15.     dfs(root, 0, 0)
  16.     dfs(root, 1, 0)
  17.     return res

8、二叉树的最近公共祖先

深度优先

  1. # 二叉树的最近公共祖先
  2. def solve(root, p, q):
  3.     if not root or root == p or root == q:
  4.         return root
  5.     left = solve(root.left, p, q)
  6.     right = solve(root.right, p, q)
  7.     if not left:
  8.         return right
  9.     if not right:
  10.         return left
  11.     return root

二叉树广度优先

1、LC199【二叉树的右视图】

  1. # 二叉树的右视图
  2. def solve(root):
  3.     depth = dict()
  4.     max_depth = -1
  5.     quene = [(root, 0)]
  6.     while quene:
  7.         node, cur_depth = quene.pop(0)
  8.         if node:
  9.             max_depth = max(max_depth, cur_depth)
  10.             depth[cur_depth] = node.val
  11.             quene.append((node.left, cur_depth+1))
  12.             quene.append((node.right, cur_depth+1))
  13.     res = []
  14.     for each in range(max_depth+1):
  15.         res.append(depth[each])
  16.     return res

2、LC1161【最大层内元素和】

  1. # 最大层内元素和
  2. def solve(root):
  3.     ans, num, quene, level = 1, -inf, [root], 1
  4.     while quene:
  5.         cur = 0
  6.         for i in range(len(quene)):
  7.             node = quene.pop(0)
  8.             cur += node.val
  9.             if node.left:
  10.                 quene.append(node.left)
  11.             if node.right:
  12.                 quene.append(node.right)
  13.         if cur > num:
  14.             ans = level
  15.             num = cur
  16.         level += 1
  17.     return ans

3、LC700【二叉搜索树中的搜索】

  1. # 二叉搜索树中的搜索
  2. def solve(root, val):
  3.     if not root:
  4.         return None
  5.     while root:
  6.         if root.val == val:
  7.             return root
  8.         root = root.right if root.val < val else root.left
  9.     return None

4、LC450【删除二叉搜索树中的节点】

  1. # 删除二叉搜索树中的节点
  2. def solve(root, key):
  3.     if not root:
  4.         return None
  5.     if key > root.val:
  6.         root.right = self.solve(root.right, key)
  7.     elif key < root.val:
  8.         root.left = self.solve(root.left, key)
  9.     else:
  10.         if not root.right:
  11.             return root.left
  12.         elif not root.left:
  13.             return root.right
  14.         elif root.right and root.left:
  15.             tmp = root.right
  16.             while tmp.left:
  17.                 tmp = tmp.left
  18.             tmp.left = root.left
  19.             root = root.right
  20.     return root

图-深度优先

1、LC841【钥匙和房间】

深度优先

  1. # 钥匙和房间
  2. # 深度优先
  3. def solve(rooms):
  4.     n = len(rooms)
  5.     visit = set()
  6.     num = 0
  7.     def dfs(x):
  8.         visit.add(x)
  9.         nonlocal num
  10.         num += 1
  11.         for each in rooms[x]:
  12.             if each not in visit:
  13.                 dfs(each)
  14.     dfs(0)
  15.     return num == n

广度优先

  1. # 广度优先
  2. def solve(rooms):
  3.     n = len(rooms)
  4.     num = 0
  5.     visit = {0}
  6.     quene = [0]
  7.     while quene:
  8.         x = quene.pop(0)
  9.         num += 1
  10.         for each in rooms[x]:
  11.             if each not in visit:
  12.                 visit.add(each)
  13.                 quene.append(each)
  14.     return num == n

2、LC547【省份数量】

深度优先

  1. # 省份数量
  2. # 深度优先
  3. def solve(isConnected):
  4.     n = len(isConnected)
  5.     visit = set()
  6.     res = 0
  7.     def dfs(i):
  8.         for j in range(n):
  9.             if isConnected[i][j] == 1 and j not in visit:
  10.                 visit.add(j)
  11.                 dfs(j)
  12.     for i in range(n):
  13.         if i not in visit:
  14.             dfs(i)
  15.             res += 1
  16.     return res

广度优先

  1. # 广度优先
  2. def solve(isConnected):
  3.     n = len(isConnected)
  4.     res = 0
  5.     visit = set()
  6.     for i in range(n):
  7.         if i not in visit:
  8.             quene = [i]
  9.             while quene:
  10.                 j = quene.pop(0)
  11.                 visit.add(j)
  12.                 for k in range(n):
  13.                     if isConnected[j][k] == 1 and k not in visit:
  14.                         quene.append(k)
  15.             res += 1
  16.     return res

图-广度优先

1、LC1926【迷宫中离入口最近的出口】

  1. # 迷宫中离入口最近的出口
  2. import collections
  3. def solve(maze, entrance):
  4.     m, n = len(maze), len(maze[0])
  5. #     print(m,n)
  6.     quene = collections.deque([(entrance[0], entrance[1], 0)])
  7.     maze[entrance[0]][entrance[1]] = '+'
  8.     while quene:
  9. #         print(quene)
  10. #         break
  11.         x, y, d = quene.popleft()
  12. #         print(x,y,d)
  13.         for nx, ny in [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]:
  14. #             print(nx,ny)
  15.             if 0 <= nx < m and 0 <= ny < n and maze[nx][ny] == '.':
  16.                 if nx == 0 or nx == m - 1 or ny == 0 or ny == n - 1:
  17.                     return d + 1
  18.                 maze[nx][ny] = '+'
  19.                 quene.append((nx, ny, d+1))
  20. #                 print(quene)
  21. #                 break
  22.     return -1

2、LC994【腐烂的橘子】

  1. #腐烂的橘子
  2. def solve(grid):
  3.     m, n = len(grid), len(grid[0])
  4.     count = 0 # 新鲜橘子的数量
  5.     quene = []
  6.     for i in range(m):
  7.         for j in range(n):
  8.             if grid[i][j] == 1:
  9.                 count += 1
  10.             elif grid[i][j] == 2:
  11.                 quene.append((i, j))
  12.     res = 0
  13.     while count > 0 and quene:
  14.         res += 1
  15.         for i in range(len(quene)):
  16.             x, y = quene.pop(0)
  17.             for nx, ny in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:
  18.                 if 0 <= nx and nx < m and 0 <= ny and ny < n:
  19.                     if grid[nx][ny] == 1:
  20.                         grid[nx][ny] = 2
  21.                         count -= 1
  22.                         quene.append((nx, ny))
  23.     if count > 0:
  24.         return -1
  25.     return res

堆/优先队列

1、LC215【数组中第k大元素】

快排

  1. # 数组中第k大元素
  2. # 快排
  3. def solve(nums, k):
  4.     k = len(nums) - k
  5.     start = 0
  6.     end = len(nums) - 1
  7.     while True:
  8.         loc = kernel(nums, start, end)
  9.         if loc == k:
  10.             return nums[loc]
  11.         elif loc < k:
  12.             start = loc + 1
  13.         else:
  14.             end = loc - 1
  15. def kernel(nums, start, end):
  16.     low = start
  17.     high = end
  18.     base = nums[start]
  19.     while low < high:
  20.         while low < high and nums[high] >= base:
  21.             high -= 1
  22.         nums[low] = nums[high]
  23.         while low < high and nums[low] < base:
  24.             low += 1
  25.         nums[high] = nums[low]
  26.     nums[low] = base
  27.     return low

堆排

  1. # 堆排
  2. def solve(nums, k):
  3.     n = len(nums)
  4.     build_max_heap(nums, n)
  5.     for k in range(n-1, n-k-1, -1):
  6.         nums[0], nums[k] = nums[k], nums[0]
  7.         heapify(nums, k, 0)
  8.     return nums[k]
  9. def build_max_heap(nums, n):
  10.     i = n // 2
  11.     while i >= 0:
  12.         heapify(nums, n, i)
  13.         i -= 1
  14. def heapify(nums, n, i):
  15.     l = 2 * i 
  16.     r = 2 * i + 1
  17.     largest = i
  18.     if l < n and nums[l] > nums[i]:
  19.         largest = l
  20.     if r < n and nums[r] > nums[largest]:
  21.         largest = r
  22.     if largest != i:
  23.         nums[largest], nums[i] = nums[i], nums[largest]
  24.         heapify(nums, n, largest)

二分查找

链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

1、LC374【猜数字大小】

  1. # 猜数字大小
  2. def solve(n):
  3.     left, right = 1, n
  4.     while left < right:
  5.         mid = left + (right - left) // 2
  6.         if guess(mid) <= 0:
  7.             right = mid
  8.         else:
  9.             left = mid + 1
  10.     return left

2、LC2300【咒语和药水的成功对数】

  1. # 咒语和药水的成功对数
  2. def solve(spells, potions, success):
  3.     res = [0] * len(spells)
  4.     idx = [i for i in range(len(spells))]
  5.     idx.sort(key=lambda x:spells[x])
  6.     potions.sort(key=lambda x:-x)
  7.     j = 0
  8.     for p in idx:
  9.         v = spells[p]
  10.         while j < len(potions) and potions[j] * v >= success:
  11.             j += 1
  12.         res[p] = j
  13.     return res

3、LC162【寻找峰值】

  1. # 寻找峰值
  2. def solve(nums):
  3.     n = len(nums)
  4.     left, right = 0, n-1
  5.     while left < right:
  6.         mid = left + (right - left) // 2
  7.         if nums[mid] > nums[mid+1]:
  8.             right = mid
  9.         else:
  10.             left = mid + 1
  11.     return right

4、LC875【爱吃香蕉的珂珂】

  1. # 爱吃香蕉的珂珂
  2. import math
  3. def solve(piles, h):
  4.     l, r = 1, max(piles)
  5.     while l < r:
  6.         mid = l + (r - l) // 2
  7. #         mid  = (l + r) // 2
  8.         print(mid)
  9.         if check(mid, piles, h):
  10.             r = mid
  11.         else:
  12.             l = mid + 1
  13.     return r
  14. def check(mid, piles, h):
  15.     cost = 0
  16.     for each in piles:
  17.         cur = math.ceil(each / mid)
  18.         cost += cur
  19.     return cost <= h

回溯

1、LC17【电话号码的字母组合】

  1. # 字母组合
  2. def solve(digits):
  3.     if not digits:
  4.         return []
  5.     mapping = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
  6.     res = []
  7.     path = []
  8.     n = len(digits)
  9.     if n == 0:
  10.         return n
  11.     def back(i):
  12.         if i == n:
  13.             res.append(''.join(path))
  14.             return
  15.         for each in mapping[int(digits[i])]:
  16.             path.append(each)
  17.             back(i+1)
  18.             path.pop()
  19.     back(0)
  20.     return res

2、LC46【全排列】

  1. # 全排列
  2. def solve(nums):
  3.     n = len(nums)
  4.     res = []
  5.     def back(i):
  6.         if i == n - 1:
  7.             res.append(nums[:])
  8.             return
  9.         for j in range(i, n):
  10.             nums[i], nums[j] = nums[j], nums[i]
  11.             back(i + 1)
  12.             nums[i], nums[j] = nums[j], nums[i]
  13.     back(0)
  14.     return res

3、LC39【组合总和】【同一个数字可以多次使用】

  1. # 组合总和
  2. def solve(candidates, target):
  3.     res = []
  4.     path = []
  5.     candidates.sort()
  6.     start = 0
  7.     n = len(candidates)
  8.     def back(path, target, candidates, start, res):
  9.         if target == 0:
  10.             res.append(path[:])
  11.             return
  12.         for i in range(start, n):
  13.             if target - candidates[i] < 0:
  14.                 break
  15.             path.append(candidates[i])
  16.             back(path, target-candidates[i], candidates, i, res)
  17.             path.pop()
  18.     back(path, target, candidates, start, res)
  19.     return res

4、LC40【组合总和2】【同一个数字只能用一次】

  1. # 组合总和2
  2. def solve(candidates, target):
  3.     res = []
  4.     path = []
  5.     candidates.sort()
  6.     start = 0
  7.     n = len(candidates)
  8.     def back(path, target, candidates, start, res):
  9.         if target == 0:
  10.             res.append(path[:])
  11.             return
  12.         for i in range(start, n):
  13.             if target - candidates[i] < 0:
  14.                 break
  15.             # 与组合1不同之处
  16.             if i > start and candidates[i] == candidates[i-1]:
  17.                 continue
  18.             path.append(candidates[i])
  19.             # 与组合1不同之处
  20.             back(path, target-candidates[i], candidates, i+1, res)
  21.             path.pop()
  22.     back(path, target, candidates, start, res)
  23.     return res

动态规划一维

1、LC1137【泰波那契数】

  1. # 泰波那契数
  2. def solve(n):
  3.     if n < 2:
  4.         return n
  5.     f = [0, 0, 1]
  6. #     if n < 3:
  7. #         return f[n]
  8.     s = 1
  9.     f0, f1, f2 = f[0], f[1], f[2]
  10.     for i in range(3, n+1):
  11.         f0 = f1
  12.         f1 = f2
  13.         f2 = s
  14.         s = f0 + f1 + f2
  15.     return s

2、LC746【最小花费爬楼梯】

  1. # 最小花费爬楼梯
  2. def solve(cost):
  3.     n = len(cost)
  4.     dp = [0] * (n+1)
  5.     for i in range(2, n+1):
  6.         dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
  7.     return dp[n]

3、LC198【打家劫舍】

  1. # 打家劫舍
  2. def solve(nums):
  3.     n = len(nums)
  4.     dp = [0] * n
  5.     if n == 1:
  6.         return nums[0]
  7.     dp[0] = nums[0]
  8.     dp[1] = max(nums[0], nums[1])
  9.     for i in range(2, n):
  10.         dp[i] = max(dp[i-1], dp[i-2]+nums[i])
  11.     return dp[n-1]

4、LC322【零钱兑换】 

  1. # 零钱兑换
  2. def solve(coins, amount):
  3.     dp = [float('inf')] * (amount + 1)
  4.     dp[0] = 0
  5.     for coin in coins:
  6.         for i in range(coin, amount + 1):
  7.             dp[i] = min(dp[i], dp[i - coin] + 1)
  8.     if dp[amount] != float('inf'):
  9.         return dp[amount]
  10.     else:
  11.         return -1

5、LC518【零钱兑换2】

  1. # 零钱兑换
  2. def solve(amount, coins):
  3.     dp = [0] * (amount + 1)
  4.     dp[0] = 1
  5.     for coin in coins:
  6.         for i in range(coin,amount+1):
  7.             dp[i] += dp[i-coin]
  8.     return dp[amount]

 

动态规划二维

1、LC62【不同路径】

  1. # 不同路径
  2. def solve(m, n):
  3.     dp = [[0] * n for i in range(m)]
  4.     for i in range(n):
  5.         dp[0][i] = 1
  6.     for j in range(m):
  7.         dp[j][0] = 1
  8.     for i in range(1,m):
  9.         for j in range(1,n):
  10.             dp[i][j] = dp[i-1][j] + dp[i][j-1]
  11.     return dp[m-1][n-1]

2、LC1143【最长公共子序列】

  1. # 最长公共子序列
  2. def solve(text1, text2):
  3.     m, n = len(text1), len(text2)
  4.     dp = [[0] * (n+1) for i in range(m+1)]
  5.     res = 0
  6.     for i in range(1, m+1):
  7.         for j in range(1, n+1):
  8.             if text1[i-1] == text2[j-1]:
  9.                 dp[i][j] = dp[i-1][j-1] + 1
  10.             else:
  11.                 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  12.             res = max(res, dp[i][j])
  13.     return res

3、LC714【买卖股票的最佳时机】【含手续费】

  1. # 买卖股票的最佳时机【含手续费】
  2. def solve(prices, fee):
  3.     n = len(prices)
  4.     dp = [[0] * 2 for i in range(n)]
  5.     dp[0][1] = -prices[0]
  6.     for i in range(1, n):
  7.         dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee)
  8.         dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
  9.     return dp[n-1][0]

4、LC72【编辑距离】

  1. # 编辑距离
  2. def solve(word1, word2):
  3.     m, n = len(word1), len(word2)
  4.     dp = [[0] * (n+1) for i in range(m+1)]
  5.     for i in range(1, m+1):
  6.         dp[i][0] = dp[i-1][0] + 1
  7.     for j in range(1, n+1):
  8.         dp[0][j] = dp[0][j-1] + 1
  9.     for i in range(1, m+1):
  10.         for j in range(1, n+1):
  11.             if word1[i-1] == word2[j-1]:
  12.                 dp[i][j] = dp[i-1][j-1]
  13.             else:
  14.                 dp[i][j] = min(dp[i-1][j-1]+1, dp[i-1][j]+1, dp[i][j-1]+1)
  15.     return dp[m][n]

位运算

1、LC338【比特位计数】

  1. # 比特位计数
  2. def solve(n):
  3.     res = []
  4.     def count(x):
  5.         cnt = 0
  6.         while x > 0:
  7.             x = x & (x - 1)
  8.             cnt += 1
  9.         return cnt
  10.     for i in range(n+1):
  11.         res.append(count(i))
  12.     return res

2、LC136【只出现一次的数字】

  1. # 只出现一次的数字
  2. def solve(nums):
  3.     x = 0
  4.     for each in nums:
  5.         x = x ^ each
  6.     return x

区间集合

1、LC435【无重叠区间】

  1. # 无重叠区间
  2. def solve(intervals):
  3.     n = len(intervals)
  4.     intervals.sort(key=lambda x:x[1])
  5.     right = intervals[0][1]
  6.     ans = 1
  7.     for i in range(1, n):
  8.         if intervals[i][0] >= right:
  9.             ans += 1
  10.             right = intervals[i][1]
  11.     return n - ans

2、LC452【用最少数量的箭引爆气球】

  1. # 用最少数量的箭引爆气球
  2. def solve(points):
  3.     n = len(points)
  4.     points.sort(key=lambda x:x[1])
  5.     right = points[0][1]
  6.     ans = 1
  7.     for i in range(1, n):
  8.         if points[i][0] > right:
  9.             ans += 1
  10.             right = points[i][1]
  11.     return ans

单调栈

1、LC739【每日温度】

  1. # 每日温度
  2. def solve(temperatures):
  3.     n = len(temperatures)
  4.     stack = []
  5.     ans = [0] * n
  6.     for i in range(n):
  7.         cur = temperatures[i]
  8.         while stack and cur > temperatures[stack[-1]]:
  9.             pre_index = stack.pop()
  10.             ans[pre_index] = i - pre_index
  11.         stack.append(i)
  12.     return ans

2、LC901【股票价格的跨度】

  1. class StockSpanner:
  2.  
  3.     def __init__(self):
  4.         self.stack = [(-1, inf)]
  5.         self.idx = -1
  6.     def next(self, price: int) -> int:
  7.         self.idx += 1
  8.         while price >= self.stack[-1][1]:
  9.             self.stack.pop()
  10.         self.stack.append((self.idx, price))
  11.         return self.idx - self.stack[-2][0]
  12.  
  13.  
  14. # Your StockSpanner object will be instantiated and called as such:
  15. # obj = StockSpanner()
  16. # param_1 = obj.next(price)

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/171022
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号