Algo Note

# Python
def binary_search(self, nums, target):
    # corner case 处理

    # 这里等价于nums is None or len(nums) == 0
    if not nums:
      return -1

    start, end = 0, len(nums) - 1

    # 用start + 1 < end而不是start < end的目的是为了避免死循环
      # 在first position of target的情况下不会出现死循环
      # 但是在last position of target的情况下会出现死循环
    # 样例：nums = [1, 1] target = 1
    # 为了统一模版，我们就都采用start + 1 < end，就保证不会出现死循环
    while start + 1 < end:

      # python 没有overflow的问题，直接 // 2 就可以
      # C++ 和 Java 最好写成mid = start + (end - start) / 2
      # 防止在start = 2^31 - 1, end = 2^31 - 1的情况下出现加法overflow
      mid = (start + end) // 2

      # >, =, < 的逻辑先分开写，然后再看看=的情况是否能合并到其他分支里
      if nums[mid] < target:
        start = mid
      elif nums[mid] == target:
        end = mid
      else:
        end = mid

  # 因为上面的循环退出条件是start + 1 < end
  # 因此这里循环结束的时候，start和end的关系是相邻关系
  # 因此需要再单独判断start和end这两个位置的数哪个是我们要的答案
  # 如果是找first position of target就先看start，否则就先看end
  if nums[start] == target:
    return start
  if nums[end] == target:
    return end
  return -1

# Python
# 相向双指针(partition in quicksort)
def partition(self, A, start, end) {
  if start >= end:
    return

  left, right = start, end

  # key point 1: pivot is the value, not the index
  pivot = A[(start + end) // 2]

  # key point 2: every time compare left with right, it should be
  # left <= right not left < right
  while left <= right:
    while left <= right and A[left] < pivot:
      left += 1
    while left <= right and A[right] > pivot:
      right -= 1
    if left <= right:
      A[left], A[right] = A[right], A[left]
      left += 1
      right -= 1
}

# 背向双指针
  left = position
  right = position + 1

  while left >= 0 and right < len(s):
    if left 和 right 可以停下来了:
      break
    left -= 1
    right += 1

# 同向双指针
  end = 0
  for start in range(len):
    # 不满足则循环到满足搭配为止
    while end < len and (start 到 end 之间不满足条件):
      end += 1
    if start 到 end 之间满足条件:
      处理 start 到 end 这段区间(处理start, end这次搭配)

# 合并双指针
def merge(list1, list2):
  new_list = []
  i, j = 0, 0

  # 合并的过程只能操作i, j的移动，不要去用list1.pop(0)之类的操作
  # 因为pop(0)是O(n)的时间复杂度
  while i < len(list1) and j < len(list2):
    if list1[i] < list2[j]:
      new_list.append(list1[i])
      i += 1
    else:
      new_list.append(list2[j])
      j += 1

  # 合并剩下的数到new_list里
  # 不要用new_list.extend(list[i:])之类的方法
  # 因为list1[i:]会产生额外空间消耗
  while i < len(list1):
    new_list.append(list1[i])
    i += 1

  while j < len(list2):
    new_list.append(list2[j])
    j += 1

  return new_list

# Python
# quick sort
class Solution:
  def sortIntegers(self, A):
    self.quickSort(A, 0, len(A) - 1)

  def quickSort(self, A, start, end):
    if start >= end:
      return

    left, right = start, end

    # key point 1: pivot is the value, not the index
    pivot = A[(start + end) // 2]

    # key point 2: every time you compare left with right, it should be
    # left <= right not left < right
    while left <= right:
      while left <= right and A[left] < pivot:
        left += 1

      while left <= right and A[right] > pivot:
        right -= 1

      if left <= right:
        A[left], A[right] = A[right], A[left]

        left += 1
        right -= 1

    self.quickSort(A, start, right)
    self.quickSort(A, left, end)

# Python
# merge sort
class Solution:
  def sortIntegers(self, A):
    if not A:
      return A

    tmp = [0] * len(A)
    self.merge_sort(A, 0, len(A) - 1, temp)

  def merge_sort(self, A, start, end, temp):
    if start >= end:
      return

    # 处理左半区间
    self.merge_sort(A, start, (start + end) // 2, temp)

    # 处理右半区间
    self.merge_sort(A, (start + end) // 2 + 1, end, temp)

    # 合并排序数组
    self.merge(A, start, end, temp)

  def merge(self, A, start, end, temp):
    middle = (start + end) // 2
    left_index = start
    right_index = middle + 1
    index = start

    while left_index <= middle and right_index <= end:
      if A[left_index] < A[right_index]:
        temp[index] = A[left_index]
        index += 1
        left_index += 1
      else:
        temp[index] = A[right_index]
        index += 1
        right_index += 1

    while left_index <= middle:
      temp[index] = A[left_index]
      index += 1
      left_index += 1

    while right_index <= end:
      temp[index] = A[right_index]
      index += 1
      right_index += 1

    for i in range(start, end + 1):
      A[i] = temp[i]

def partition(arr, l, r):
    pivot = arr[r]
    i = l
    for j in range(l, r):
        if arr[j] <= pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[r] = arr[r], arr[i]
    return i

def optimized_partition(arr, l, r):
    pivot = arr[l]
    i = l + 1
    j = r
    while i <= j:
        if arr[i] < pivot and arr[j] > pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
            j -= 1
        if arr[i] >= pivot:
            i += 1
        if arr[j] <= pivot:
            j -= 1
    
    arr[l], arr[j] = arr[j], arr[l]
    return j

def quick_select_recursive(arr, l, r, k):
    # pivot_idx = partition(arr, l, r)
    pivot_idx = optimized_partition(arr, l, r)
    if (pivot_idx == k - 1):
        return arr[pivot_idx]
    elif (pivot_idx > k - 1):
        return quick_select(arr, l, pivot_idx - 1, k)
    else:
        return quick_select(arr, pivot_idx + 1, r, k)

def quick_select_iterative(arr, l, r, k):
    while True:
        # pivot_idx = partition(arr, l, r)
        pivot_idx = optimized_partition(arr, l, r)
        if (pivot_idx == k - 1):
            return arr[pivot_idx]
        elif (pivot_idx > k - 1):
            r = pivot_idx - 1
        else:
            l = pivot_idx + 1

# Python
def divide_conquer(root):

  # 递归出口
  # 一般处理 node == null 就够了
  # 大部分情况下不需要处理 node == leaf
  if root is None:
    return ...

  # 处理左子树
  left_result = divide_conquer(node.left)

  # 处理右子树
  right_result = divide_conquer(node.right)

  # 合并答案
  result = merge left_result and right_result to get merge result

  return result

class BSTIterator {
 public:
  BSTIterator(TreeNode* root) {
    curr_ = root;
  }
  
  int next() {
    while (curr_ != nullptr) {
      stack_.push_back(curr_);
      curr_ = curr_->left;
    }
    curr_ = stack_.back();
    stack_.pop_back();
    int val = curr_->val;
    curr_ = curr_->right; // !!!! very important here
    return val;
  }
  
  bool hasNext() {
    if (stack_.empty() && curr_ == nullptr) return false; // has to check both
    return true;
  }
 private:
  TreeNode* curr_;
  deque<TreeNode*> stack_;
};

# Python
def inorder_traversal(root):
  if root is None:
    return []

  # 创建一个dummy node，右指针指向root
  # 并放到stack里，此时stack的栈顶dymmy是iterator的当前位置
  dummy = TreeNode(0)
  dummy.right = root
  stack = [dummy]
  inorder = []

  # 每次将iterator挪到下一个点
  # 也就是调整stack使得栈顶到下一个点
  while stack:
    node = stack.pop()
    if node.right:
      node = node.right
      while node:
        stack.append(node)
        node = node.left

    if stack:
      inorder.append(stack[-1])

  return inorder

# Python
def bfs(start_node):

  # BFS必须要用队列queue，别用栈stack！
  # distance(dict) 有两个作用，一个是记录一个点是否被丢进过队列了，避免重复访问
  # 另外一个是记录start_node到其他所有节点的最短距离
  # 如果只求连通性的话，可以换成set就行
  # node做key的时候比较的是内存地址
  queue = collections.deque([start_node])
  distance = {start_node: 0}

  # while 队列不空，不停地从队列里拿出一个点，拓展邻居节点放到队列中
  while queue:
    node = queue.popleft()

    # 如果有明确的终点可以在这里加终点的判断
    if node 是终点:
      break or return something
    for neighbor in node.get_neighbors():
      if neighbor in distance:
        continue
      queue.append(neighbor)
      distance[neighbor] = distance[node] + 1

  # 如果需要返回所有点离起点的距离，就return hashmap
  return distance

  # 如果需要返回所有连通的节点，就return HashMap里的所有点
  return distance.keys()

  # 如果需要返回离终点的最短距离
  return distance[end_node]

# Python
# topological sort
def get_indegrees(nodes):
  counter = {node: 0 for node in nodes}

  for node in nodes:
    for neighbor in node.get_neighbors():
      counter[neighbor] += 1

  return counter

def topological_sort(nodes):
  # 统计入度
  indegrees = get_indegrees(nodes)

  # 所有入度为 0 的点都放到队列里
  queue = collections.deque([node for node in nodes if indegrees[node] == 0])

  # 用BFS算法一个个把点从图里挖出来
  topo_order = []

  while queue:
    node = queue.popleft()
    topo_order.append(node)
    for neighbor in node.get_neighbors():
      indegrees[neighbor] -= 1
      if indegrees[neighbor] == 0:
        queue.append(neighbor)

  # 判断是否有循环依赖
  if len(topo_order) != len(nodes):
    return 有循环依赖(环)，没有拓扑排序

  return topo_order

# Python
def dfs(参数列表):
  if 递归出口：
    记录答案
    return

  for 所有的拆解可能性:
    修改所有的参数
    dfs(参数列表)
    还原所有被修改过的参数

  return something 如果需要的话，很多时候不需要return值，除了分治的写法

# Python
# 带删除特定元素功能的堆
from heapq import heappush, heappop

class Heap:
  def __int__(self):
    self.minheap = []
    self.deleted_set = set()

  def push(self, index, val):
    heappush(self.minheap, (val, index))

  def _lazy_deletion(self):
    while self.minheap and self.minheap[0][1] in self.deleted_set:
      heappop(self.minheap)

  def top(self):
    self._lazy_deletion()
    return self.minheap[0]

  def pop(self):
    self._lazy_deletion()
    heappop(self.minheap)

  def delete(self, index):
    self.deleted_set.add(index)

  def is_empty(self):
    return not bool(self.minheap)

# Python
class UnionFind:
  def __init__(self):
    # 初始化父指针，集合大小，集合数量
    self.father = {}
    self.size_of_set = {}
    self.num_of_set = 0

  def add(self, x):
    # 点如果已经出现，操作无效
    if x in self.father:
      return

    # 初始化点的父亲为 空对象 None
    # 初始化该点所在集合大小为 1
    # 集合数量增加 1
    self.father[x] = None
    self.num_of_set += 1
    self.size_of_set[x] = 1

  def merge(self, x, y):
    # 找到两个节点的根
    root_x, root_y = self.find(x), self.find(y)

    # 如果根不是同一个则连接
    if root_x != root_y:
      # 将一个点的根变成新的根
      # 集合数量减少 1
      # 计算新的根所在集合大小
      self.father[root_x] = root_y
      self.num_of_set -= 1
      self.size_of_set[root_y] += self.size_of_set[root_x]

  def find(self, x):
    # 指针 root 指向被查找的点x
    # 不断找到 root 的父亲
    # 直到 root 指向 x 的根节点
    root = x
    while self.father[root] != None:
      root = self.father[root]

    # 将路径上所有点指向根节点 root
    while x != root:

      # 暂存 x 原本的父亲
      # 将 x 指向根节点
      # x 指针上移至 x 的父节点
      original_father = self.father[x]
      self.father[x] = root
      x = original_father
    return root

  # 两个节点连通 等价于 两个节点的根相同
  def is_connected(self, x, y):
    return self.find(x) == self.find(y)

  # 获取集合数量
  def get_num_of_set(self):
    return self.num_of_set

  # 获取某个点所在集合大小
  def get_size_of_set(self, x):
    return self.size_of_set[self.find(x)]

// Let me try to re-implement java solution with C++
class TrieNode {
 public:
  TrieNode()
    : children(), is_word(), word() {}

  // 儿子节点
  std::unordered_map<char, TrieNode*> children;

  // 根节点到该节点是否是一个单词
  bool is_word;

  // 根节点到该节点的单词是什么
  std::string word;
};

class Trie {
 public:
  Trie() : root_(new TrieNode()) {}
  TrieNode* GetRoot() { return root_; }

  // 插入单词
  void Insert(std::string word) {
    TrieNode* node = root_;
    for (int i = 0; i < word.size(); ++i) {
      char c = word[i];
      // leetcode 1268
      // if (!node->children.count(c)) {
      // if (node->children.find(c) == node->children.end()) {
      if (node->children[c] == nullptr) {
        node->children[c] = new TrieNode();
      }
      node = node->children[c];
    }
    node->is_word = true;
    node->word = word;
  }

  // 判断单词 word 是不是在字典树中
  bool HasWord(std::string word) {
    TrieNode* node = root_;
    for (int i = 0; i < word.size(); ++i) {
      char c = word[i];
      // leetcode 1268
      // if (!node->children.count(c)) {
      // if (node->children.find(c) == node->children.end()) {
      if (node->children[c] == nullptr) {
        return false;
      }
      node = node->children[c];
    }
    return node->is_word;
  }

  // 判断前缀 prefix 是不是在字典树中
  bool HasPrefix(std::string prefix) {
    TrieNode* node = root_;
    for (int i = 0; i < prefix.size(); ++i) {
      char c = prefix[i];
      // leetcode 1268
      // if (!node->children.count(c)) {
      // if (node->children.find(c) == node->children.end()) {
      if (node->children[c] == nullptr) {
        return false;
      }
      node = node->children[c];
    }
    return true; // this is the only difference with the HasWord function
  }
 private:
  TrieNode* root_;
};

// Java
class TrieNode {
  // 儿子节点
  public Map<Character, TrieNode> children;

  // 根节点到该节点是否是一个单词
  public boolean isWord;

  // 根节点到该节点的单词是什么
  public String word;

  public TrieNode() {
    children = new HashMap<Character, TrieNode>();
    isWord = false;
    word = null;
  }
}

public class Trie {
  private TrieNode root;

  public Trie() {
    root = new TrieNode();
  }

  public TrieNode getRoot() {
    return root;
  }

  // 插入单词
  public void insert(String word) {
    TrieNode node = root;
    for (int i = 0; i < word.length(); i++) {
      char letter = word.charAt(i);
      if (!node.children.containsKey(letter)) {
        node.children.put(letter, new TrieNode());
      }
      node = node.children.get(letter);
    }

    node.isWord = true;
    node.word = word;
  }

  // 判断单词 word 是不是在字典树中
  public boolean hasWord(String word) {
    int L = word.length();
    TrieNode node = root;
    for (int i = 0; i < L; i++) {
      char letter = word.charAt(i);
      if (!node.children.containsKey(letter)) {
        return false;
      }
      node = node.children.get(letter);
    }
    return node.isWord;
  }

  // 判断前缀 prefix 是不是在字典树中
  public boolean hasPrefix(String prefix) {
    int L = prefix.length();
    TrieNode node = root;
    for (int i = 0; i < L; i++) {
      char letter = prefix.charAt(i);
      if (!node.children.containsKey(letter)) {
        return false;
      }
      node = node.children.get(letter);
    }
    return true;
  }
}

def left-rotate(T, x):
    y = x.right          # set y
    x.right = y.left     # turn y's left subtree into x's right subtree
    if y.left != T.nil
      y.left.p = x
    y.p = x.p            # link x's parent to y
    if x.p == T.nil
      T.root = y
    elif x == x.p.left
      x.p.left = y
    else x.p.right = y
    y.left = x           # put x on y's left
    x.p = y

class Solution {
 public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* A, TreeNode* B) {
    if (root == nullptr) return nullptr;

    // !!! 如果root为A或B，立即返回，无需继续向下寻找
    if (root == A || root == B) return root;

    // 分别去左右子树寻找A和B
    TreeNode* left = lowestCommonAncestor(root->left, A, B);
    TreeNode* right = lowestCommonAncestor(root->right, A, B);

    // !!! 如果A，B分别存在于两棵子树，root为LCA，返回root(return answer)
    if (left != nullptr && right != nullptr) return root;

    // 左子树有一个点或者左子树有LCA
    if (left != nullptr) return left;

    // 右子树有一个点或者右子树有LCA
    if (right != nullptr) return right;

    // 左右子树啥都没有
    return nullptr;
  }
};

// C++
#include <unordered_map>

struct LinkedNode {
  LinkedNode(int key, int value, LinkedNode* next)
    : key(key), value(value), next(next) {}

  int key;
  int value;
  LinkedNode* next;
};

class LRUCache {
 public:
  LRUCache(int capacity)
    : capacity_(capacity), dummy_(new LinkedNode(0, 0, nullptr)), tail_(dummy_) {}

  // Google style: Get
  int Get(int key) {
    if (key_to_previous_.find(key) == key_to_previous_.end()) {
      return -1;
    }
    LinkedNode* previous = key_to_previous_.at(key);
    LinkedNode* current = previous->next;

    Kick(previous);
    return current->value;
  }

  // Google style: Set
  void Set(int key, int value) {
    if (key_to_previous_.find(key) != key_to_previous_.end()) {
      Kick(key_to_previous_.at(key));
      tail_->value = value;
      return;
    }

    PushBack(new LinkedNode(key, value, nullptr)); // 如果key不存在，则存入新节点
    if (key_to_previous_.size() > capacity_) { // 如果缓存超出上限
      PopFront();
    }
  }

 private:
  void PushBack(LinkedNode* node) {
    key_to_previous_[node->key] = tail_;
    tail_->next = node;
    tail_ = node;
  }

  void PopFront() { // 删除头部
    LinkedNode* head = dummy_->next;
    key_to_previous_.erase(head->key);
    dummy_->next = head->next;
    key_to_previous_[head->next->key] = dummy_;
  }

  // change "previous->node->next->...->tail_"
  // to "previous->next->...->tail_->node"
  void Kick(LinkedNode* previous) { // 将数据移至尾部
    LinkedNode* node = previous->next;
    if (node == tail_) {
      return;
    }

    // update the current node from linked list
    previous->next = node->next;

    // update the previous node in hash map
    key_to_previous_[node->next->key] = previous;
    node->next = nullptr;
    PushBack(node);
  }

  int capacity_;
  LinkedNode* dummy_;
  LinkedNode* tail_;

  std::unordered_map<int, LinkedNode*> key_to_previous_;
};

def longestIncreasingSubsequence(self, nums):
  if nums is None or not nums:
    return 0

  # state: dp[i] 表示以第i个数结尾的LIS的长度
  # initialization：dp[0..n-1] = 1
  dp = [1] * len(nums)

  # function: dp[i] = max(dp[i] + 1), j < i && nums[j] < nums[i]
  for i in range(len(nums)):
    for j in range(i):
      if nums[j] < nums[i]:
        dp[i] = max(dp[i], dp[j] + 1)

  # answer, 任意一个位置都可能是LIS的结尾
  return max(dp)

def longestIncreasingSubsequence(self, nums):
  if nums is None or not nums:
    return 0

  # state: dp[i] 表示以第i个数结尾的LIS的长度
  # initialization：dp[0..n-1] = 1
  dp = [1] * len(nums)

  # prev[i]代表dp[i]的最优值是从哪个dp[j]算过来的
  prev = [-1] * len(nums)

  # function dp[i] = max{dp[j] + 1}, j < i and nums[j] < nums[i]
  for i in range(len(nums)):
    for j in range(i):
      if nums[j] < nums[i] and dp[i] < dp[j] + 1:
        dp[i] = dp[j] + 1
        prev[i] = j

  # answer: max(dp[0..n-1])
  longest, last = 0, -1
  for i in range(len(nums)):
    if dp[i] > longest:
      longest = dp[i]
      last = i

  path = []
  while last != -1
    path.append(nums[last])
    last = prev[last]
  print(path[::-1])

  return longest

class Solution {
 public:
  int lengthOfLIS(vector<int>& nums) {
    vector<int> tails(nums.size() + 1, 0x3f3f3f3f);

    for (int& n : nums) {
      int idx = BinarySearch(tails, n);
      tails[idx] = n;
    }

    int result = 0;
    for (int& n : tails) {
      if (n != 0x3f3f3f3f) {
        ++result;
      }
    }
    return result;
  }

 private:
  int BinarySearch(vector<int>& nums, int target) {
    int start = 0;
    int end = nums.size() - 1;
    while (start + 1 < end) {
      int mid = start + (end - start) / 2;
      if (nums[mid] == target) return mid;
      else if (nums[mid] < target) start = mid;
      else end = mid;
    }
    return end;
  }
};

class Solution:
    """
    @param A: An integer matrix
    @return: an integer
    """
    def longestContinuousIncreasingSubsequence2(self, A):
        if not A or not A[0]:
            return 0

        n, m = len(A), len(A[0])
        points = []
        for i in range(n):
            for j in range(m):
                points.append((A[i][j], i, j))

        points.sort()

        longest_hash = {}
        for i in range(len(points)):
            key = (points[i][1], points[i][2])
            longest_hash[key] = 1
            for dx, dy in [(1, 0), (0, -1), (-1, 0), (0, 1)]:
                x, y = points[i][1] + dx, points[i][2] + dy
                if x < 0 or x >= n or y < 0 or y >= m:
                    continue
                if (x, y) in longest_hash and A[x][y] < points[i][0]:
                    longest_hash[key] = max(longest_hash[key], longest_hash[(x, y)] + 1)

        return max(longest_hash.values())