• 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)

  • 相关阅读:
    原论文一比一复现 | 更换 RT-DETR 主干网络为 【VGG13】【VGG16】【VGG19】| 对比实验必备
    如何借助小程序，不卖货却一天汇集2000+吃货！
    【网络安全】网站中间件存在的解析漏洞
    kafka操作5
    使用正则表达式在中英文之间添加空格
    Fuzz测试 发现软件中的隐患和漏洞的秘密武器
    大数据Flink（七十一）：SQL的时间属性
    WebRTC实现简单音视频通话功能
    简单三招，就能将ppt翻译成英文，快来学习
    java计算机毕业设计小区车辆管理系统源码+数据库+系统+lw文档+mybatis+运行部署
  • 原文地址：https://blog.csdn.net/dipizhong7224/article/details/133967032