任务分解

[azl397985856]

• https://github.com/azl397985856/leetcode 下题解格式整理，需要包含“tag”，“前置知识”， “公司”等
• tag 整理，比如加入递归（要自己写教程或者网上找质量高，评价好的）
• 公司信息完善，可以参考力扣的公司标签，但是要比其更完善，这部分信息，可以从群友那里获取。
• 可视化调试（待规划）
• 小抄（比如提供一些模板，一些笔记等）
• 爬虫。 爬取 https://github.com/azl397985856/leetcode 下的题目信息，用作数据源。包括题目信息，tag信息，公司信息等

[zhenbushidashen]

领取：爬虫。 爬取 https://github.com/azl397985856/leetcode 下的题目信息，用作数据源。包括题目信息，tag信息，公司信息等

[MingkHe]

领取：整理20-40的题解格式

[yoluxi]

领取：整理41-60的题解格式

[azl397985856]

爬虫bug：

1. 重试最大次数限制，错误多少次之后跳到下一题。

2. 可以支持选择镜像源

3. 提取 tag 有 bug
   

4. 只提取代码区域的代码， 不提取思路等其他部分的代码
   

5. 提取的代码增加描述。 可以暂时改成“方法一”， “方法二” 以此类推。

6. 标签没有取
   

7. 排序应该按照1，2，3 这样，而不是 字符串排序（见上图）

[azl397985856]

关于模板（C++/Python/Java/Js）：

• 二分查找
• 排序的写法
• BFS的写法
• DFS的写法
• 回溯法
• 并查集
• 前缀树
• 图遍历
• 拓扑排序
• 双指针

[azl397985856]

可视化调试 @MingkHe 出一个 RFC

[azl397985856]

公司信息完善 @fly0o0 可以先去LeetCode 评论区搞一点。

[fly0o0]

公司信息完善 @fly0o0 可以先去LeetCode 评论区搞一点。

ok

[azl397985856]

二分法

使用场景

• 有序区间查找指定值

查找一个数

• 首先定义搜索区间为 [left, right]，注意是左右都闭合，之后会用到这个点。

你可以定义别的搜索区间形式，不过后面的代码也相应要调整，感兴趣的可以试试别的搜索区间。

• 由于我们定义的搜索区间为 [left, right]，因此当 left <= right 的时候，搜索区间都不为空。 也就是说我们的终止搜索条件为 left <= right。

举个例子容易明白一点。 比如对于区间 [4,4]，其包含了一个元素 4，因此搜索区间不为空。而当搜索区间为 [left, right) 的时候，同样对于 [4,4]，这个时候搜索区间却是空的。

• 循环体内，我们不断计算 mid ，并将 nums[mid] 与 目标值比对。
  • 如果 nums[mid] 等于目标值， 则提前返回 mid（只需要找到一个满足条件的即可）
  • 如果 nums[mid] 小于目标值， 说明目标值在 mid 右侧，这个时候搜索区间可缩小为 [mid + 1, right]
  • 如果 nums[mid] 大于目标值， 说明目标值在 mid 左侧，这个时候搜索区间可缩小为 [left, mid - 1]
• 循环结束都没有找到，则说明找不到，返回 -1 表示未找到。

Java

public int binarySearch(int[] nums, int target) {
    // 左右都闭合的区间 [l, r]
    int left = 0;
    int right = nums.length - 1;

    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid;
        if (nums[mid] < target)
			// 搜索区间变为 [mid+1, right]
            left = mid + 1;
        if (nums[mid] > target)
            // 搜索区间变为 [left, mid - 1]
            right = mid - 1;
    }
    return -1;
}

Python

def binarySearch(nums, target):
    # 左右都闭合的区间 [l, r]
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (left + right) >> 1
        if nums[mid] == target: return mid
        # 搜索区间变为 [mid+1, right]
        if nums[mid] < target: l = mid + 1
        # 搜索区间变为 [left, mid - 1]
        if nums[mid] > target: r = mid - 1
    return -1

JavaScript

function binarySearch(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (nums[mid] == target) return mid;
    if (nums[mid] < target)
      // 搜索区间变为 [mid+1, right]
      left = mid + 1;
    if (nums[mid] > target)
      // 搜索区间变为 [left, mid - 1]
      right = mid - 1;
  }
  return -1;
}

C++

暂时空缺，欢迎 PR

寻找最左边的满足条件的值

• 首先定义搜索区间为 [left, right]，注意是左右都闭合，之后会用到这个点。

你可以定义别的搜索区间形式，不过后面的代码也相应要调整，感兴趣的可以试试别的搜索区间。

• 由于我们定义的搜索区间为 [left, right]，因此当 left <= right 的时候，搜索区间都不为空。 也就是说我们的终止搜索条件为 left <= right。

举个例子容易明白一点。 比如对于区间 [4,4]，其包含了一个元素 4，因此搜索区间不为空。而当搜索区间为 [left, right) 的时候，同样对于 [4,4]，这个时候搜索区间却是空的。

• 循环体内，我们不断计算 mid ，并将 nums[mid] 与 目标值比对。
  • 如果 nums[mid] 等于目标值， 则收缩右边界，我们找到了一个备胎，继续看看左边还有没有了
  • 如果 nums[mid] 小于目标值， 说明目标值在 mid 右侧，这个时候搜索区间可缩小为 [mid + 1, right]
  • 如果 nums[mid] 大于目标值， 说明目标值在 mid 左侧，这个时候搜索区间可缩小为 [left, mid - 1]
• 由于不会提前返回，因此我们需要检查最终的 left，看 nums[left]是否等于 target。
  • 如果不等于 target，或者 left 出了右边边界了，说明至死都没有找到一个备胎，则返回 -1.
  • 否则返回 left 即可，备胎转正。

Java

public int binarySearchLeft(int[] nums, int target) {
	// 搜索区间为 [left, right]
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        }
        if (nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        }
        if (nums[mid] == target) {
            // 收缩右边界
            right = mid - 1;
        }
    }
    // 检查是否越界
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}

Python

def binarySearchLeft(nums, target):
    # 左右都闭合的区间 [l, r]
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (left + right) >> 1
        if nums[mid] == target:
            # 收缩右边界
            r = mid - 1;
        # 搜索区间变为 [mid+1, right]
        if nums[mid] < target: l = mid + 1
        # 搜索区间变为 [left, mid - 1]
        if nums[mid] > target: r = mid - 1
    if l >= len(nums) or nums[l] != target: return -1
    return l

JavaScript

function binarySearchLeft(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (nums[mid] == target)
      // 收缩右边界
      right = mid - 1;
    if (nums[mid] < target)
      // 搜索区间变为 [mid+1, right]
      left = mid + 1;
    if (nums[mid] > target)
      // 搜索区间变为 [left, mid - 1]
      right = mid - 1;
  }
  // 检查是否越界
  if (left >= nums.length || nums[left] != target) return -1;
  return left;
}

C++

暂时空缺，欢迎 PR

寻找最右边的满足条件的值

• 首先定义搜索区间为 [left, right]，注意是左右都闭合，之后会用到这个点。

你可以定义别的搜索区间形式，不过后面的代码也相应要调整，感兴趣的可以试试别的搜索区间。

• 由于我们定义的搜索区间为 [left, right]，因此当 left <= right 的时候，搜索区间都不为空。 也就是说我们的终止搜索条件为 left <= right。

举个例子容易明白一点。 比如对于区间 [4,4]，其包含了一个元素 4，因此搜索区间不为空。而当搜索区间为 [left, right) 的时候，同样对于 [4,4]，这个时候搜索区间却是空的。

• 循环体内，我们不断计算 mid ，并将 nums[mid] 与 目标值比对。
  • 如果 nums[mid] 等于目标值， 则收缩左边界，我们找到了一个备胎，继续看看右边还有没有了
  • 如果 nums[mid] 小于目标值， 说明目标值在 mid 右侧，这个时候搜索区间可缩小为 [mid + 1, right]
  • 如果 nums[mid] 大于目标值， 说明目标值在 mid 左侧，这个时候搜索区间可缩小为 [left, mid - 1]
• 由于不会提前返回，因此我们需要检查最终的 right，看 nums[right]是否等于 target。
  • 如果不等于 target，或者 right 出了左边边界了，说明至死都没有找到一个备胎，则返回 -1.
  • 否则返回 right 即可，备胎转正。

Java

public int binarySearchRight(int[] nums, int target) {
	// 搜索区间为 [left, right]
    int left = 0
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
			// 搜索区间变为 [mid+1, right]
            left = mid + 1;
        }
        if (nums[mid] > target) {
			// 搜索区间变为 [left, mid-1]
            right = mid - 1;
        }
        if (nums[mid] == target) {
            // 收缩左边界
            left = mid + 1;
        }
    }
    // 检查是否越界
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

Python

def binarySearchRight(nums, target):
    # 左右都闭合的区间 [l, r]
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (left + right) >> 1
        if nums[mid] == target:
            # 收缩左边界
            l = mid + 1;
        # 搜索区间变为 [mid+1, right]
        if nums[mid] < target: l = mid + 1
        # 搜索区间变为 [left, mid - 1]
        if nums[mid] > target: r = mid - 1
    if r < 0 or nums[r] != target: return -1
    return r

JavaScript

function binarySearchRight(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (nums[mid] == target)
      // 收缩左边界
      left = mid + 1;
    if (nums[mid] < target)
      // 搜索区间变为 [mid+1, right]
      left = mid + 1;
    if (nums[mid] > target)
      // 搜索区间变为 [left, mid - 1]
      right = mid - 1;
  }
  // 检查是否越界
  if (right < 0 || nums[right] != target) return -1;
  return right;
}

C++

暂时空缺，欢迎 PR

[azl397985856]

BFS(WIP)

使用场景

• 最短路径问题

模板

Python

from collections import deque

# n * m 大小的矩阵
n, m = len(grid), len(grid[0])
# 扩展方向
direction = [[0, 1], [0, -1], [-1, 0], [1, 0]]
# 记录节点是否被访问
visited = [[False for _ in range(m)] for _ in range(n)]
queue = deque()
# 深度
level = 0
# 加入初始节点
queue.append([0, 0])
visited[0][0] = True
while len(queue) > 0:
    top = queue.popleft()
    x, y = top[0], top[1]
    # 扩展节点
    for d in direction:
        next_x = x + d[0]
        next_y = y + d[1]
        # 判断相邻节点是否有效
        if (
            next_x < 0
            or next_x >= n
            or next_y < 0
            or next_y >= m
            or visited[next_x][next_y]
        ):
            continue
        queue.append([next_x, next_y])
        visited[next_x][next_y] = True
    # 深度增加
    level += 1