/Code-Problem-Practice

Recoding my coding practice routine

Code-Problem-Practice

Recording my coding practice routine 🚀

2020.5.5

leetcode: Math

2020.5.3

2020.4.29

leetcode: math

  • 268. Missing Number

    • XOR'ing a number by itself results in 0
    • XOR is commutative and associative

  • 273. Integer to English Words

  • 1073. Adding Two Negabinary Numbers⭐

    • Interesting!

    • Change from add from binary numbers

      C++:

          vector<int> addBinary(vector<int>& A, vector<int>& B) {
        vector<int> res;
        int carry = 0, i = A.size() - 1, j = B.size() - 1;
        while (i >= 0 || j >= 0 || carry) {
            if (i >= 0) carry += A[i--];
            if (j >= 0) carry += B[j--];
            res.push_back(carry & 1);
            carry = (carry >> 1);
        }
        reverse(res.begin(), res.end());
        return res;
    }

    vector<int> addNegabinary(vector<int>& A, vector<int>& B) {
        vector<int> res;
        int carry = 0, i = A.size() - 1, j = B.size() - 1;
        while (i >= 0 || j >= 0 || carry) {
            if (i >= 0) carry += A[i--];
            if (j >= 0) carry += B[j--];
            res.push_back(carry & 1);
            carry = -(carry >> 1);
        }
        while (res.size() > 1 && res.back() == 0)
            res.pop_back();
        reverse(res.begin(), res.end());
        return res;
    }

2020.4.28

leetcode: Binary Search

  • 74. Search a 2D Matrix

    • Don't treat it as a 2D matrix, just treat it as a sorted list

  • 981. Time Based Key-Value Store

    • This is new. We need to write a class first.
    • Hash map + map: lower_bound
    • Use binary search ⭐

  • 50. Pow(x, n) ⭐

    • Watch out for processing n<0

      double myPow(double x, int n) {
    if (n==0) return 1;
    if (n<0) return 1/x * myPow(1/x, -(n+1));
    return (n%2) ? myPow(x*x, n/2)*x:myPow(x*x, n/2);
}

    • Bit manipulation

  • 69. Sqrt(x)

    • Newton's method:

      {x}{{k+1}}={\frac {1}{2}}\left(x{k}+{\frac {n}{x_{k}}}\right),\quad k\geq 0,\quad x_{0}>0.

    • Binary search: watch out for edge cases (fastest)

2020.4.26

leetcode: Binary Search

  • 4. Median of Two Sorted Arrays⭐

    • Binary Search: median number index property
      • Search in the short array
      • edge cases solved by adding imaginary nodes (smart)

  • 35. Search Insert Position

    • Easy binary search problem

      if (nums[mid] >= target) hi = mid;
else lo = mid + 1;

  • 34. Find First and Last Position of Element in Sorted Array

    • Binary search for the left and right boundary (2 pass) ⭐ (a trick to make mid bias to the right)
    • Another way to search right bound: search left bound for target + 1

  • 744. Find Smallest Letter Greater Than Target

    • Find right bound

  • 153. Find Minimum in Rotated Sorted Array

    • Remember:

      int findMin(vector<int>& nums) {
        int lo = 0, hi = nums.size() - 1, mid;
        
        while (lo < hi) {
            mid = (lo + hi) >> 1;
            
            if (nums[mid] > nums[hi]) lo = mid + 1; // compare with right one
            else hi = mid; 
        }
        return nums[lo];
    }

    • Another way

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

  • 162. Find Peak Element

    • find the peak only on its right elements( cut the array to half)
    • Tricky one: because search we can always get a solution by searching the local maximum side

2020.4.23

leetcode: array Binary Search

2020.4.14

leetcode: array

leetcode: backtracking

2020.4.12

leetcode: array

2020.4.11

leetcode: array

2020.4.4

leetcode: daily challenge

leetcode: graph

  • 133. Clone Graph
    • learn to write BFS/DFS to traverse a graph
    • In this problem, avoid copying the same node for multiple times (mapping from an original node to its copy)
  • 207. Course Schedule
    • topological sort to detect circle, we first transform it to the adjacency-list representation.
  • 289. Game of Life ⭐
    • Simulation problem
    • In place solution: use 2nd-bit as change number (genius)

2020.4.3

leetcode: daily challenge

2020.3.31

leetcode: Linked List

  • 2. Add Two Numbers

    • Linked List add two number

  • 23. Merge k Sorted Lists ⭐

    • Construct on merge two sorted list

    • Merge two adjacent lists every iteration

      I agree with @cqnkxy.

During 1st iteration, we merge two lists(every list is N) into one, this will make K down to K / 2.

During 2nd iteration, we merge two lists(every list is 2N) into one, this will make K / 2 down to k /4.

During 3rd iteration, we merge two lists(every list is 4N) into one, this will make K / 4 down to k /8.

And so forth...

I think when we merge two lists, the complexity is O(list1.length) + O(list2.length).

So the total complexity is:

(2N) * (K / 2) + 
(4N) * (K / 4) + 
(8N) * (K / 8) + 
.............. + 
(2^logK*N) * (K / (2 ^logK)) 

= logK*KN

    • Priority-queue or Heap

  • 1171. Remove Zero Sum Consecutive Nodes from Linked List ⭐

    • Intuition

      Assume the input is an array.
Do you know how to solve it?
Scan from the left, and calculate the prefix sum.
Whenever meet the seen prefix,
remove all elements of the subarray between them.

      image

      image

  • 817. Linked List Components

    • use set or list to record appearance

      unordered_set<int> setG (G.begin(), G.end());

... setG.count(head->val) ... // appearance
... setG.erase(...) ... // delete

  • 445. Add Two Numbers II

    • If no reverse: stack:star:

  • 83. Remove Duplicates from Sorted List

2020.3.30

leetcode: Linked List

  • 61. Rotate List

    • Find the tail and reconnect
    • Use the circle list

  • 25. Reverse Nodes in k-Group

    • Reverse Node classical code block (use frequently)

      # Not using dummy node
prev, cur, nxt = None, head, head
while cur:
    nxt = cur.next
    cur.next = prev
    prev = cur
    cur = nxt
return prev

    • recursive solution

2020.3.27

leetcode: Linked List

2020.3.24

leetcode: Dynamic Programming

  • 332 Coin Change
    • Dynamic Programming
    • DFS search (pruning out unnecessary situations): much faster ⭐
  • 413 Arithmetic Slices
  • 221 Maximal Square ⭐
    • brute force search (my solution)
    • Dynamic Programming
  • 64 Minimum Path Sum ⭐
  • 85 Maximal Rectangle ⭐
    • similar to 221 (but solution is totally different)
    • similar to 84: histogram square
  • 85 Maximal Rectangle ⭐
    • Search left and right
    • use stack ⭐
  • 70 Climbing Stairs
    • Fibonacci array
  • 53 Maximum Subarray ⭐
    • classical subarray sum problem: O(n) time, O(1) space
  • 121 Best Time to Buy and Sell Stock ⭐
    • transform to 53 problem
    • intuitive solution: record minimum price

2020.3.20

leetcode: Dynamic Programming

  • 198 House Robber:
    • O(1) space implementation
  • 213 House Robber II:
    • Two way House Robber
  • 132 Palindrome Partition:
    • Record isPalindrome and partition number
    • prune cases: expand out from current letter
  • 62 Unique Path:
    • O(n) space implementation
  • 63 Unique Path II:
    • Similar implementation: watch out for the corner case

2020.3.17

leetcode: tree

  • 99 Binary Tree Right Side View: Depth-first Search Breadth-First Search
    • postorder search and only record first one of the level
  • 111 Minimum Depth of Binary Tree: Depth-first Search Breadth-First Search
  • 112 Path Sum: Depth-first Search Breadth-First Search
  • 103 Binary Tree Zigzag Level Order Traversal: Depth-first Search Breadth-First Search
    • use deque
  • 94 Binary Tree Inorder Traversal
  • 113 Path Sum II: Depth-first Search Breadth-First Search

2020.3.14

leetcode: tree

  • 96 Unique Binary Search Trees: Dynamic Programing

  • 95 Unique Binary Search Trees II: Dynamic Programing

  • 106 Construct Binary Tree from Inorder and Postorder Traversal ⭐

    • Solved in recursion version. This one is a quite classic problem.

  • 100 Same Tree: Inorder Traversal

  • 99 Recover Binary Search Tree ⭐

    • First, could be solved by a inorder traversal (only two nodes are swapped)
    • Second, a very interesting way to solve by Morris Traversal. Look at this website and this discussion.

leetcode: linked list

  • 206 Reverse Linked List
    • Iterative: dummy node
    • recursive: straight-forward
  • 92 Reverse Linked List II
    • iterative: dummy node