# Leetcode

## 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;
}
}
```

## 5 General Tips

```#include <climits>
int res = INT_MIN;
if (tmp > res) res = tmp;
```
• lowerbound: larger or greater than
• upperbound: 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!

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

```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 lowerbound 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)

• according to left and remaining, decide how to update
```  int lastRemaining(int n) {
int step = 1;
bool left = true;
int remaining = n;
while (remaining > 1) {
if (left) {
left = false;
step <<=1;
remaining >>= 1;
} else {
left = true;
if (remaining % 2 == 1) {
}
step <<= 1;
remaining >>= 1;
}
}
}
```

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

Given a string s, find the longest subsequence that

1. have at least k repeat for each characters
2. 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:

1. 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));
}

```