Leetcode

1. Common Strategy & Algorithms
2. New
3. Some snippet
4. Some links
5. General Tips
- 5.1. GCD
6. Data Structures
- 6.1. Trie
7. Famous Problems and Algorithms
8. Problems
9. 400. Nth Digit

1 Common Strategy & Algorithms

Divide and conquer
DP
binary search
recursive
finding rules using examples

2 New

2.1 1 [Easy] Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

Instead of iterate the array twice, use a dictionary to store the visited ones.

  def twoSum(self, nums, target):
      buf_dict = {}
      for i in range(0,len(nums)):
          if nums[i] in buf_dict:
              return [buf_dict[nums[i]], i]
          else:
              buf_dict[target-nums[i]] = i # (HEBI: target-num)

2.2 128 [Hard] Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Record only the border value.

  def longestConsecutive(self, nums):
      ret = 0
      mydict={}
      for num in nums:
          if num in mydict:
              pass
          else:
              left = mydict[num-1] if num-1 in mydict else 0
              right = mydict[num+1] if num+1 in mydict else 0
              length = left + right + 1
              mydict[num] = length
              # (HEBI: important! Do not update the immediate, but the far-most one, because that is the edge)
              mydict[num-left] = length
              mydict[num+right] = length
              ret = length if length > ret else ret
      return ret

2.3 448 [Easy] Find All Numbers Disappeared in an Array

class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        ret=[]
        i = 0
        while i < len(nums):
            # tmp = nums[i]
            # print(nums)
            if nums[i] > 0:
                pos=nums[i]-1
                if nums[nums[i]-1] != 0:
                    nums[i] = nums[pos]
                    nums[pos] = 0
                else:
                    nums[i] = -1
            else:
                i+=1
        for i in range(len(nums)):
            if nums[i] == -1:
                ret.append(i+1)
        return ret

3 Some snippet

/**
 * rotate clockwise
 * (x,y) -> (y, -x)
 */
void rotate(std::vector<pair<int, int> > &v) {
  for (pair<int, int> &vi : v) {
    int tmp = vi.first;
    vi.first = vi.second;
    vi.second = 0 - tmp;
  }
}

4 Some links

5 General Tips

#include <climits>
int res = INT_MIN;
if (tmp > res) res = tmp;

lower_bound: larger or greater than
upper_bound: strictly larger than

To get a smaller iterator, use upper_bound and decrease it (after check if it is begin)

  auto pre_it = m_data.upper_bound(val);
  auto next_it = pre_it;
  int pre_low, pre_high;
  int next_low, next_high;
  if (pre_it == m_data.end()) {
    next_low = INT_MAX;
    next_high = INT_MAX;
   } else {
    next_low = next_it->first;
    next_high = next_it->second;
   }
  if (pre_it == m_data.begin()) {
    pre_low = INT_MIN;
    pre_high = INT_MIN;
   } else {
    pre_it--;
    pre_low = pre_it->first;
    pre_high = pre_it->second;
   }

5.1 GCD

swap
make sure x,y are POSITIVE
When divide it, make sure it is not 0!

  int GCD(int x, int y) {
    if (x > y) std::swap(x,y);
    if (x == 0) return y;
    return GCD(y%x, x);
  }

  int gcd(int a, int b) {
    while (b) {
      int r = a%b;
      a = b;
      b = r;
    }
    return a;
  }

Be careful, a%b follows the sign of a:

5 % 3 == 2
-5 % 3 == -2
5 % -3: ERROR!

6 Data Structures

6.1 Trie

Prefix tree.

7 Famous Problems and Algorithms

7.1 Maximum subarray problem and Kadane's algorithm

Problem: finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum

Kadane's algorithm:

def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

or if 0 is not a predefined return value:

def max_subarray(A):
    max_ending_here = max_so_far = A[0]
    for x in A[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

7.2 longest increasing sub-sequence(LIS)

Find the longest increasing sub-sequence. O(n^2)

  int sol_nn(vector<int> &nums) {
    if (nums.size() == 0) return 0;
    if (nums.size() == 1) return 1;
    vector<int> dp(nums.size(), 1);
    int size = nums.size();
    for (int i=1;i<size;i++) {
      for (int j=0;j<i;j++) {
        if (nums[i] > nums[j]) {
          dp[i] = std::max(dp[i], dp[j] + 1);
        }
      }
    }
    int ret = 1;
    for (int i=0;i<size;i++) {
      ret = std::max(ret, dp[i]);
    }
    return ret;
  }

O(nlog(n))

  int sol_nlogn(vector<int> &nums) {
    if (nums.empty()) return 0;
    vector<int> list;
    for (int num : nums) {
      auto it = lower_bound(list.begin(), list.end(), num);
      if (it == list.end()) {
        list.push_back(num);
      } else {
        *it = num;
      }
    }
    return list.size();
  }

7.3 Dynamic Programming

Solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions

ideally, using a memory-based data structure.

There're generally just two ways for DP:

bottom up: solve sub problem, and represent bigger problem
top down: represent bigger problem by sub problems

7.3.1 Apply to LIS

The length of the LIS ending in the current element is the length of the LIS ending in the smaller one + 1.

7.4 Patience sorting

7.4.1 The sort algorithm

The algorithm derives from patience card game.

This game begins with a shuffled deck of cards. These cards are dealt one by one into a sequence of piles on the table, according to the following rules.

Initially, there are no piles. The first card dealt forms a new pile consisting of the single card.
Each subsequent card is placed on the leftmost existing pile whose top card has a value greater than or equal the new card's value, or to the right of all of the existing piles, thus forming a new pile.
When there are no more cards remaining to deal, the game ends.

clearly the complexity is O(nlogn).

7.4.2 Apply to LIS problem

First, execute the sorting algorithm as described above. The number of piles is the length of a longest subsequence. Whenever a card is placed on top of a pile, put a back-pointer to the top card in the previous pile (that, by assumption, has a lower value than the new card has). In the end, follow the back-pointers from the top card in the last pile to recover a decreasing subsequence of the longest length; its reverse is an answer to the longest increasing subsequence algorithm.

7.4.3 LIS problem another understanding

Keep a set of active lists for the longest. Actually use the reversed pile of Patience sorting. Whenever add a number to a pile, remove all other piles with the same length. This should save a lot of computing!

e.g. 58364129

58 ---
36 ---
4 ---
129

end element of smaller list is smaller than end elements of larger lists.

8 Problems

8.1 363. Max Sum of Rectangle No Larger Than K

If we want to switch row and column of a matrix if col is larger than row, simply
1. use a boolean flag
2. swap the row and column size variable.
3. when accessing data, swap the row and column, e.g. data[col][row] instead of data[row][col]
std::swap, std::max
In this problem, the reused computation is not whole, but partial: only column (or row) part computation is reused. Thus the problem matters for each one is larger.
A very interesting point is, the temp[] vector keep tracking the sum of current row, while sum keeps the sum of rows.
sums keep the sums of the rows, and use lower_bound feature of std::set for sums.lower_bound(sum - k)

  int maxSumSubmatrix(vector<vector<int> >& matrix, int k) {
    if (matrix.size() == 0) return 0;
    int row = matrix.size();
    int col = matrix[0].size();
    bool row_large = true;
    if (row > col) {
      row_large = true;
    } else {
      row_large = false;
      std::swap(row, col);
    }
    int ret = INT_MIN;

    for (int c=0;c<col;c++) {
      vector<int> temp(row, 0);
      // sums.insert(0);
      for (int i=c;i>=0;i--) {
        int sum = 0;
        set<int> sums;
        sums.insert(0);
        for (int r=0;r<row;r++) {
          temp[r] += row_large ? matrix[r][i] : matrix[i][r];
          sum += temp[r];
          auto it = sums.lower_bound(sum - k);
          if (it != sums.end()) {
            int res = sum - *it;
            ret = std::max(ret, res);
          }
          sums.insert(sum);
        }
      }
    }
    return ret;
  }

8.2 65. valid number

  EXPECT_TRUE(s.isNumber("+.8"));
  EXPECT_TRUE(s.isNumber(".1"));
  EXPECT_TRUE(s.isNumber("-5.3"));

  EXPECT_FALSE(s.isNumber(". 1"));
  EXPECT_FALSE(s.isNumber("4e+"));
  EXPECT_FALSE(s.isNumber("6e6.5"));

8.3 44. Wildcard Matching (NEEDS REVISIT!!!)

The recursive one is too cost:

  bool isMatch(string s, string p) {
    std::string pattern = p;
    std::string str = s;
    if (p.empty()) {
      if (s.empty()) return true;
      else return false;
    } else {
      char c = *p.begin();
      p = p.substr(1);
      if (c == '?') {
        if (s.empty()) return false;
        s = s.substr(1);
        return isMatch(s, p);
      } else if (c == '*') {
        for (int i=0;i<=(int)s.size();i++) {
          if (isMatch(s.substr(i), p)) {
            return true;
          }
        }
        return false;
      } else {
        if (s.empty()) return false;
        if (s[0] != c) {
          return false;
        }
        s = s.substr(1);
        return isMatch(s, p);
      }
    }
  }

This one does not have that problem, and is linear.

  bool isMatch(const char *s, const char *p) {
    const char* star=NULL;
    const char* ss=s; 
    while (*s){
      if ((*p=='?')||(*p==*s)){s++;p++;continue;}
      if (*p=='*'){star=p++; ss=s;continue;}
      if (star){ p = star+1; s=++ss;continue;}
      return false;
    }
    while (*p=='*'){p++;}
    return !*p;
  }

8.4 4. Median of Two Sorted Arrays

If want a log complexity, set up (min, max) and keep update them.

  double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size(), n = nums2.size();
    if (m > n) return findMedianSortedArrays(nums2, nums1);
    int i, j, imin = 0, imax = m, half = (m + n + 1) / 2;
    while (imin <= imax) {
      i = (imin + imax) / 2;
      j = half - i;
      if (i > 0 && j < n && nums1[i - 1] > nums2[j]) imax = i - 1;
      else if (j > 0 && i < m && nums2[j - 1] > nums1[i]) imin = i + 1;
      else break;
    }
    int num1;
    if (i == 0) num1 = nums2[j - 1];
    else if (j == 0) num1 = nums1[i - 1]; 
    else num1 = std::max(nums1[i - 1], nums2[j - 1]);
    
    if ((m + n) & 1) return num1;
    
    int num2;
    if (i == m) num2 = nums2[j];
    else if (j == n) num2 = nums1[i];
    else num2 = std::min(nums1[i], nums2[j]);
    
    return (num1 + num2) / 2.0;
  }

8.5 last remaining (contest 2)

Move head, record step
according to left and remaining, decide how to update

  int lastRemaining(int n) {
    int head = 1;
    int step = 1;
    bool left = true;
    int remaining = n;
    while (remaining > 1) {
      if (left) {
        left = false;
        head = head + step;
        step <<=1;
        remaining >>= 1;
      } else {
        left = true;
        if (remaining % 2 == 1) {
          head += step;
        }
        step <<= 1;
        remaining >>= 1;
      }
    }
    return head;
  }

8.6 longest subsequence with at least k repeat / without any repeat

Given a string s, find the longest subsequence that

have at least k repeat for each characters
have no repeat for each word

These are two problems. For the first one, count and split the ones that don't have k repeatition. Note:

use recur(s,k,min,max) format instead of creating substring! Otherwise time limit execeed.

  class Solution {
  public:
    int longestSubstring(string s, int k) {
      // calculate the frequency of each character
      // if all > k, good
      // otherwise, split the string by all that is less than k
      return recur(s, k, 0, s.size());
    }

    int recur(string &s, int k, int min, int max) {
      int ret = 0;
      map<char, int> m;
      for (int i=min;i<max;i++) {
        m[s[i]]++;
      }
      string split;
      for (auto mi : m) {
        if (mi.second < k) {
          split += mi.first;
        }
      }
      if (split.empty()) return max - min;
      // do split
      size_t idx = min;
      size_t last_idx = min;
      idx = s.find_first_of(split, last_idx);
      while (idx != string::npos && idx < max) {
        int tmp = recur(s, k, last_idx, idx);
        ret = std::max(ret, tmp);
        last_idx = idx+1;
        idx = s.find_first_of(split, last_idx);
      }
      string sub = s.substr(last_idx);
      int tmp = recur(s, k, last_idx, max);
      ret = std::max(ret, tmp);
      return ret;
    }
  };

The second problem is an DP problem. The trick is, every time, record the visited list, using a map: map to the index of that visit. Do not need to update everything before. If we found a character visited before that index, simply update that only.

9 400. Nth Digit

  /**
   *
   1 - 9 : 9
   10 - 99 : 2 * 90
   100 - 999 : 3 * 900
   1000 - 9999: 4 * 90000
  */
  class Solution {
  public:
    int findNthDigit(int nn) {
      long n = nn;
      std::pair<long, long> p = get_lvl(n);
      long lvl = p.first;
      long remaining = p.second;
      long base = get_base(lvl);

      long num = remaining / lvl + base - 1;
      long offset = remaining % lvl;
      if (offset != 0) {
        num++;
      }
      if (offset != 0) {
        offset = lvl + 1 - offset;
      }
      return get_digit(num, offset);
    }

    long get_digit(long num, long offset) {
      while (--offset>0) {
        num /= 10;
      }
      return num % 10;
    }

    /**
     * Get base number (100..)
     */
    long get_base(long cat) {
      long ret=1;
      while (--cat>0) {
        ret *= 10;
      }
      return ret;
    }

    /**
     * find the lvl it belongs, start from 1
     * @return (lvl, remaining)
     */
    std::pair<long, long> get_lvl(long n) {
      std::pair<long, long> p = {1,0};
      while (n > 0) {
        n -= get_total(p.first);
        p.first++;
      }
      p.first--;
      p.second = n + get_total(p.first);
      return p;
    }

    /**
     * get the total num of lvl level
     */
    long get_total(long level) {
      long ret=level * 9;
      while (--level>0) {
        ret *= 10;
      }
      return ret;
    }
  };

neat solution:

  public int findNthDigit(int n) {
      int len = 1;
      long count = 9;
      int start = 1;

      while (n > len * count) {
          n -= len * count;
          len += 1;
          count *= 10;
          start *= 10;
      }

      start += (n - 1) / len;
      String s = Integer.toString(start);
      return Character.getNumericValue(s.charAt((n - 1) % len));
  }