y4h2 / leetcode Goto Github PK

HTML 65.22% SCSS 34.78%

leetcode's Introduction

Foam

👋 Welcome to your new Foam Knowledge Base!

Getting started

This documentation assumes that you have a GitHub account and have Visual Studio Code installed on your Linux/macOS/Windows machine.

If you haven't yet, browse over to the main Foam documentation to get an idea of what Foam is and how to use it.
Press "Use this template" button at foam-template (that's this repository!) to fork it to your own GitHub account. If you want to keep your thoughts to yourself, remember to set the repository private.
Clone the repository to your local machine and open it in VS Code.

Open the repository as a folder using the File > Open... menu item.
When prompted to install recommended extensions, click Install all (or Show Recommendations if you want to review and install them one by one)

After setting up the repository, head to getting started to get familiar with your new knowledge base!

To learn more about how to use Foam, read the Recipes bubbles of the Foam documentation workspace.

And remember that you can always join our Foam community on Discord!

Using Foam

We've created a few Bubbles (Markdown documents) to get you started.

inbox - a place to write down quick notes to be categorized later
getting-started - learn how to use your Foam workspace
todo - a place to keep track of things to do

In the docs directory you can find everything you need to learn the basics of Foam.

Submitting Issues

As you may have noticed, issues are disabled. With the goal to keep the project fairly easy to maintain, please file your issues in the main Foam repository:

https://github.com/foambubble/foam

leetcode's People

Contributors

Watchers

leetcode's Issues

理解二分法

核心：循环不变量
二分查找又死循环了？一个视频讲透二分本质！【基础算法精讲 04】循环不变量在排序数组中查找元素的第一个和最后一个位置 | 力扣 LeetCode 高频面试题

循环不变量

求最小的nums[i] >= target
双闭区间， L, M, R。 [L, R]表示需要查询的边界， M指向正在查询的数。[0, L-1]为已经确认的<target的区间，[R+1, n-1]属于>= target的区间
终止的情况， R在L的左边，即[R+1, n-1]都>= target, [0, L-1]都< target. 所以R+1或者L是答案

# 要求nums是非递减的， 即nums[i] <= nums[i+1]
# 返回最小的满足nums[i] >= target 的i
# 如果不存在，返回len(nums)
def lower_bound(nums: List[int], target: int) -> int:
  left = 0
  right = len(nums) - 1
  while left <= right:
    mid = left + (right - left) // 2
    if nums[mid] < target:
      left = mid + 1 # [mid+1, right]
    else:
      right = mid - 1 # [left, mid  - 1]
      
  return left

左闭右开区间

def lower_bound1(nums: List[int], target: int) -> int:
  left = 0
  right = len(nums) # 左闭右开区间 [left, right)
  while left < right:
    mid = left + (right - left) // 2
    if nums[mid] < target:
      left = mid + 1  # [mid+1, right)
    else:
      right = mid  # [left, mid)

  return left # right

开区间

def lower_bound2(nums: List[int], target: int) -> int:
  left = -1
  right = len(nums) # 开区间 (left, right)
  while left + 1 < right:
    mid = left + (right - left) // 2
    if nums[mid] < target:
      left = mid # (mid, right)
    else:
      right = mid  # (left, mid)

  return right

>, >=, <, <=都能互相转换
> 等价于 >= x + 1
< 等价于 (>= x) - 1
<= 等价于 (> x) - 1

Kadane算法

the maximum array sum

dp[i]: the maximum array sum ending at i
dp[i] = max(nums[i], dp[i-1] + nums[i])

minimum swaps required to sort an array

这里的swap不限于相邻元素间的swap。
所以应该找到互相成为循环的元素组
Minimum number of swaps required to sort an array

而对于相邻元素间的swap则可以通过逆序对来求出

二分法

2305. Fair Distribution of Cookies

理解backtracking

backtracing的本质还是dfs

可以从常见的简单的dfs进行推导。

简单的dfs例子200. Number of Islands, 地图类的dfs的方案是从当前的点(i, j)向四周(i+1, j), (i-1, j), (i, j+1), (i, j-1)移动，对于下一个点一般会有条件约束，

而对于46. Permutations从当前点(i, j)向其他所有的点移动，限制是不能取重复的点