Skip to content

Latest commit

 

History

History
527 lines (495 loc) · 27.6 KB

Basic.md

File metadata and controls

527 lines (495 loc) · 27.6 KB

Typical Problems

List

Traversal

# Length computation
let mut node_ptr : &ListNode = head.as_ref().unwrap();
while let Some(ref next) = node_ptr.next {
    node_ptr = next;
    l+=1;
}

Manipulation

Hard

Tree

Preorder/Inorder/Postorder Traversal

BFS Traversal

Manipulation

Review

Hard

Stack

Parsing

  • 726. Number of Atoms During iteration, think when to update parameters, when to process these parameters and re-reinitialize them, and when to invoke recursively. Note to match parentheses when subtracting subparts for the recursive call.

Stack-aided Monotonic Array

Extremely powerful for leftmost/rightmost smaller/greater problems in an array.

Recursions

Hint: provide a level parameter in each recursive call. Prefix let level_padding : String = (0..level).map(|_|{" "}).collect(); in each print message for a clear format.

Path Searching

Backtrack

A general backtrack template is provided in the template. This can help the following problems:

Permutation

A general permutation template is provided in the template. This can help the following problems:

  • 31. Next Permutation (Find the last increasing adjacent pair, the first of which is indexed with k. If k not exists, reverse the entire array. Otherwise, find the greatest l such that arr[l]>arr[k]. Swap l and k, and reverse arr[k+1..])

Dynamic Programming

Knapsack

Can use DP only if the states are enumerable, e.g, the target sum is integer. Otherwise, must apply the recursion.

Bounded

Elements can NOT be reused.

Unbounded

Elements can be reused.

Generalized Approach

// result[i][j] represent the result to reach state j only with the first i elements. i=0 implies no elements considered. 
Init result[element_count+1][state_count]

for i = 1..=element_count: 
  for j = 0..=state_count:
    // Bounded
    this_element = element[i-1]
    if j < this_element {
      Derive result[i][j] from result[i-1][j]
    } else if bounded {
      Derive result[i][j] from result[i-1][j-this_element]
    } else {
      Derive result[i][j] from result[i][j-this_element]
    }
result[element_count][state_count]

Classics

2D

Binary Search

Refer to the template for the classic binary search problem, such as first greater element, and etc.

// Assume the target must exist
low = 0i32; // inclusive and can be negative
high = nums.len() as i32 - 1;// inclusive and can be negative

while low < high {
  let mid = (low + high) / 2;
  // three branches can be merged. 
  if nums[mid]==target{
  // may additional test whether it is the first and the last to be true
  // If meeting condition: return
  // else shrink the range:
    high = mid or mid-1
    low = mid + 1; NEVER low = mid, otherwise the loop is infinite. 
  } else if nums[mid] < target {
    // similar as above
  } else {
    // similar as above
  }
}
low

// Assume the target may not exist
low = 0i32; // inclusive and can be negative
high = nums.len() as i32 - 1;// inclusive and can be negative

while low <= high {
  let mid = (low + high) / 2;
  // three branches can be merged. 
  if nums[mid]==target{
  // may additional test whether it is the first and the last to be true
  // If meeting condition: return
  // else shrink the range:
    high = mid - 1; or
    low = mid + 1; NEVER high/low = mid, otherwise the loop is infinite. 
  } else if nums[mid] < target {
    // similar as above
  } else {
    // similar as above
  }
}

Rotated Sorted List

// A general approach
let left = 0;
let right = nums.len() - 1;
while low <= high {
  // check mid_num
  if left_num < mid_num {
    // adjust the ranges given that [left, mid] is sorted.
    // Assume [left, mid] is not sorted, then suppose nums[left=0]=0 nums[left+1=-1] a[mid=2]=1, this array can never be rotated to be sorted. 
  } else if left_num > mid_num {
    // adjust the ranges given that [mid, right] is sorted. 
  } else {
    // increment left given that left_num = mid_num
  }
}
-1

Max-min

Suitable for problems where solutions are within in a range and the tentative solution is easy to verify.

H-Index

  • 275. H-Index II (Find the smallest i such that citations[i] >= n-i, return n-i)

Sort

Bucket Sort

Cardinality Sort

Wiggle Sort

# Handy code to produce a mapped index, like [0,2,4,1,3,5] or [0,2,4,1,3]
(0..(n+1)/2).map(|x|{2*x}).collect(); // [0,2,4] when n=5 or 6.
(0..n/2).map(|x|{2*x}).collect(); // [1,3] when n=5, or [1,3,5] when n=6.
In [1,3,0,2,4] or [1,3,5,0,2,4], every consecutive 3 are not adjacent.

Matrix Traversal

Spiral

Diagonal

Bit Operation

Basics

Series

Palindrome

NOTE: DP recursion for palindrome
is_palindrome(i,j) |= is_palindrome(k,j-1) && s[k-1] == s[j] for any k

Stocks Trading

Key recursion:

// no_stock_balances[i][k] represents the max balance at the end of i-th day with at most k txns, conditioned on no stock hold
// with_stock_balances[i][k] represents the max balance at the end of i-th day with at most k txns, conditioned on stocks holded
no_stock_balances[i<=0][*]=0; // initial condition
no_stock_balances[*][k=0]=0; // initial condition
with_stock_balances[*][k=0]=MIN; // imply N.A. to work with the below max operation

// sell
no_stock_balances[i][k] = max(no_stock_balances[i-1][k], with_stock_balances[i-1][k] + prices[i])
// buy
with_stock_balances[i][k] = max(with_stock_balances[i-1][k], no_stock_balances[i-1][k-1] - prices[i])

Non-intuitive Medium

Hard

Collected Template

  • Data structure:
    • BtreeMap
    • BtreeSet
    • HashMap
    • HashSet
    • Vector
    • Iterator
    • Heap
    • Stack
    • Queue
  • Bit Operation
  • Primitives
    • Option
    • Typed/Untyped structs
    • User Input
  • Algorithms
    • Binary Search
    • Union Find (Map-based & vector-based)

Tricks

Promient Problems 713 Element count in window sliding. 399 str Union Find

Unsolved: 803. Bricks Falling When Hit 126. Word Ladder II

Resources

Note

  • LRU(146) and LFU(460) has to be implemented in PYTHON, as only possible to encode in unsafe rust.