Note.txt

如果leetcode一上来做的很顺手，说明基础知识还不错，思路也都有，直接做题，辅助看书就可以；
如果一上来感觉非常艰难，一天3-4道，一碰难题就想跳楼的话，可以花较多时间在看CC150上，看过一章之后，
在leetcode上做对应题目作为练习和检测。

hackerrank可不简单，反正比topcoder要难的。其中难度在Expert以上的题你试过就知道了。
个人认为leetcode还是很简单的，lintcode略难。



asdas


** Java
* (I) programming tricks
// (1) Math.floorMod
Instead of dp[i][j] = dp[i][j] < 0 ? dp[i][j] + 1000000007 : dp[i][j] % 1000000007;
you can use Math.floorMod method dp[i][j] = Math.floorMod(dp[i][j], 1000000007);

// (2) int present
int MOD = 1_000_000_007;

// (3) nested for loop continue

            search: for (int j = i+1; j < W; ++j) {
                for (String row: A)
                    if (row.charAt(i) > row.charAt(j))
			// break from cur for loop without updating dp[i]
                        continue search;
                dp[i] = Math.max(dp[i], 1 + dp[j]);
            }

// (4) int[]
int[] a = null

// (5) String
LT297
> String data = "a b c d e";
> String[] array = data.split(" ");
array = { a, b, c, d, e };

// [6] LinkedList
https://leetcode.com/problems/smallest-sufficient-team/discuss/334683/Java-backtracking-solution

> private List<Integer> findSmallest(LinkedList<String> neededSkillz, List<List<String>> people) {
        if (neededSkillz.isEmpty()) return new ArrayList<Integer>();

        String skill = neededSkillz.removeFirst();
        Integer shortest = null;
        List<Integer> shortestList = null;
        for(int person : skillCombo.get(skill)) {
            List<String> removedSkills = new ArrayList<>();

            for(String pSkill : people.get(person))
                if(neededSkillz.remove(pSkill)) 
			removedSkills.add(pSkill);
            
            List<Integer> otherSkills = findSmallest(neededSkillz, people);
            if(shortest == null || otherSkills.size() < shortest) {
                shortest = otherSkills.size();
                shortestList = otherSkills;
                shortestList.add(person);
            }
            neededSkillz.addAll(removedSkills);
        }
        
        neededSkillz.add(skill);
        
        return shortestList;
    }


// [7] console interaction
CPSC210-lecture-week12-Auction
> Scanner userInput = new Scanner(System.in);
> userResponse = userInput.next();
> userResponse.equalsIgnoreCase("y")


// [8] Array.streams() Sort and filter
https://leetcode.com/problems/filter-restaurants-by-vegan-friendly-price-and-distance/discuss/490344/Java-one-liner



* (II) Others
// (1) Comparator
> public class coinCompare implements Comparator<Integer> {
>    @Override
>    public int compare(Integer a, Integer b) {
>        return nums[a] - nums[b];
>    }
> }

Arrays.sort(idx, new coinCompare());
       
// (2) lambda
Arrays.sort(idx, (Integer a, Integer b) -> nums[a] - nums[b]);

// (3) Arrays.fill
Do not use this to fill array of arraylist, otherwise, all arraylists will be
modified simultaneously
> class Solution {
> 
>    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
>        List<List<String>> res = new ArrayList<List<String>>();
>        ArrayList<Integer>[] difs = new ArrayList[5];
>        Arrays.fill(difs, new ArrayList<Integer>());
>        difs[0].add(0);
> 
>        ArrayList<String> cur = new ArrayList<String>();
>        cur.add(String.valueOf(difs[2].size()));
>        res.add(cur);
>        return res;
>    }
> }

// (4) PQ
> PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a,b) -> a[1] - b[1]);
> for (int neigh: graph[i])
>     pq.add(new int[]{neigh, graph[neigh].length});

// (5) hash
LT818
putIfAbsent()

// (6) TreeSet
LT56 - Array
> TreeSet<Interval> tree = new TreeSet<Interval>(new Comparator<Interval>() {
>     @Override
>     public int compare(Interval i1, Interval i2) {
>         if (i1.end < i2.start) return -1;
>         else if (i1.start > i2.end) return 1;
>         else return 0;
>      }
> });



* (III) Data structures & Alg
// (i) Hash
(1) hash function for pair
LT818_BFS

// (ii) unordered_map
(1) map iterator
	unordered_map<int, int> cur(dp);
            for (auto it: cur) {
                int d = it.first;
                dp[d + x] = max(dp[d + x],cur[d]);


// (iii) Set(cpp)/TreeMap(java)
We can use a TreeMap, which is an excellent structure for maintaining sorted data.
LT56

// (iv) Recursion_O(nlgn)
LT99
Whenever you call a function recursively n times, we need O(n) spaces to push the memory consumption of these calls in memory stack. There is O(N) overhead on the stack. The question asked for O(1) space. Just keep in mind, this is a side-effect of recursive solutions.

I think it's necessary to clarify it here that you can't just say "Recursion's space complexity is O(n) or O(log n)". In this question, the recursion version has average O(log n) data complexity. But recursion could be O(n) on average as well. For example, the data cost will be O(n) here:

 int fun(int n) {
    if(n<=0) return 0;
    else return fun(n-1) + n;
 }

// (v) Skip trailing space
string s = " aaa";
int i = 0;
for(; s[i] == ' '; i++) {}



** Python
* Programming tech (sample program)
(1) @lru_cache(None)
Memo optimize
LT903_official solution
LT1000_Lee solution

https://leetcode.com/problems/find-the-closest-palindrome/discuss/102396/C%2B%2B-short-solution-only-need-to-compare-5-numbers

(2) string join & split
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/discuss/166904/Python-or-BFS-tm
> res = [a,b,c,d,e]
> a = ','.join(res) 
> b = a.split(',')

a = "a,b,c,d,e"
b = res

(3) tricks
https://leetcode.com/problems/out-of-boundary-paths/discuss/102975/Python-1-line-solution

https://leetcode.com/problems/split-array-with-same-average/discuss/120842/DP-with-bitset-over-*sum*-(fast-PythonRuby-decent-C%2B%2B)

https://leetcode.com/problems/unique-substrings-in-wraparound-string/discuss/95441/Python-Concise-Solution

https://leetcode.com/problems/advantage-shuffle/discuss/149842/Python-Greedy-Solution-Using-Sort

https://leetcode.com/problems/smallest-sufficient-team/discuss/334572/Python-DP-Solution

// @functools.lru_cache(None) - cache 
https://leetcode.com/problems/make-array-strictly-increasing/discuss/377531/O(n2-log(n))-
solutionStarting-from-brute-force-improve-by-memoization

(4) Sort and filter
LT1333
def filterRestaurants(self, A, veganFriendly, maxPrice, maxDistance):
        A.sort(key=lambda (i, r, v, p, d): (-r, -i))
        return [i for i, r, v, p, d in A if v >= veganFriendly and p <= maxPrice and d <= maxDistance]


* Methods
// np.matrix, matrix multiplication
LT1269
https://leetcode.com/problems/count-vowels-permutation/discuss/398224/easy-peasy-python-O(logN)-matrix-rank


// xrange
https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/discuss/436677/Python-DP

def numWays(self, steps, n, mod=10 ** 9 + 7):
        A = [0, 1]
        for t in xrange(steps):
            A[1:] = [sum(A[i - 1:i + 2]) % mod for i in xrange(1, min(n + 1, t + 3))]
        return A[1] % mod

// sample
https://leetcode.com/problems/minimum-falling-path-sum-ii/discuss/451273/Python-DP-O(MN)





** C
https://leetcode.com/problems/longest-palindromic-substring/discuss/2923/Simple-C%2B%2B-solution-(8ms-13-lines)

(1) string manipulation
https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/1738/4ms-C-code-in-12-lines



** JavaScript
// [1] Source code
LT52
https://leetcode.com/problems/n-queens-ii/discuss/20141/Never-write-codes-like-this-lets-do-eval

It generates source code that's nested loops and ifs, and then runs that code. You can see it by inserting console.log(p); before the return line and testing a custom test case. For example for N=4 you'll see this:


// @param {number} n
// @return {number}
var totalNQueens = function(n) {
    var p = '', s = 0, l;
    for (var i = 0; i < n; i++) {
        l = '\nfor (var s# = 0; s# < ' + n + '; s#++)';
        for (var j = 0; j < i; j++)
            l += 'if (s# !== s@ && Math.abs(s# - s@) !== (# - @)) '.replace(/@/g, j);
        p += l.replace(/#/g, i);
    }
    p += '\ns++;\ns';
    console.log(p);
    return eval(p);
};

It generates source code that's nested loops and ifs, and then runs that code. You can see it by inserting console.log(p); before the return line and testing a custom test case. For example for N=4 you'll see this:

for (var s0 = 0; s0 < 4; s0++)
for (var s1 = 0; s1 < 4; s1++)if (s1 !== s0 && Math.abs(s1 - s0) !== (1 - 0)) 
for (var s2 = 0; s2 < 4; s2++)if (s2 !== s0 && Math.abs(s2 - s0) !== (2 - 0)) if (s2 !== s1 && Math.abs(s2 - s1) !== (2 - 1)) 
for (var s3 = 0; s3 < 4; s3++)if (s3 !== s0 && Math.abs(s3 - s0) !== (3 - 0)) if (s3 !== s1 && Math.abs(s3 - s1) !== (3 - 1)) if (s3 !== s2 && Math.abs(s3 - s2) !== (3 - 2)) 
s++;
s




** Data structure
(1) PQ and Multiset
PriorityQueue.remove() complexity is o(n). so the solution is o(n^2). proper data structure should be something like MultiSet (Not buildin with JDK), can be implemented using Map.

_(i) Multiset_
//
https://leetcode.com/problems/advantage-shuffle/discuss/149831/C%2B%2B-6-lines-greedy-O(n-log-n)

> vector<int> A;
> multiset<int> s(begin(A), end(A));
> s.upper_bound(B[i]) 			// this is faster
> upper_bound(s.begin(), s.end(),B[i])  // than this
Because set is BST internally, and it's algorithm designed/optimized for that. Generic binary search just works with ranges, which is slow for BST.


(2) TreeSet (java) Map (cpp)
LT870
https://leetcode.com/problems/advantage-shuffle/discuss/149840/C%2B%2BJava-Greedy-Solution-Using-Map






** Alg hints
(1) Combination (LT903)
You have two ways. One way is you can just create a table of binom[n][k] directly, all modulo MOD. Then, use the recurrence C(n,k) = C(n-1,k-1) + C(n-1,k) to populate this table. This solution uses only int.
The second way is that you could just use long. Since every value is modulo MOD, the multiplication of two of those values will fit into a long integer.


(2) DFS_constant branches
A typical setting is the matrix exploration scenario, where using for loop would increase running time significantly. Thus, try to write out the 4 direction population explicitly without using a loop.

When write out the 4 directions, there is no need to check the validity of both row and column number since each direction only change either row or column. Thus, it is only necessary to check the dimension that is changed.

> if (i - 1 >= 0 && matrix[i - 1][j] > matrix[i][j]) u = dfs(i - 1, j, matrix);
> if (i + 1 < n && matrix[i + 1][j] > matrix[i][j]) d = dfs(i + 1, j, matrix);
> if (j - 1 >= 0 && matrix[i][j - 1] > matrix[i][j]) l = dfs(i, j - 1, matrix);
> if (j + 1 < m && matrix[i][j + 1] > matrix[i][j]) r = dfs(i, j + 1, matrix);


(3) Heap and priority queue (LT23)
- Heap is a kind of data structure. It is a name for a particular way of storing data that makes certain operations very efficient. We can use a tree or array to describe it.

   18
  /  \
 10  16
/ \  / \
9 5  8 12

18, 10, 16, 9, 5, 8, 12

- Priority queue is an abstract datatype. It is a shorthand way of describing a particular interface and behavior, and says nothing about the underlying implementation.

A heap is a very good data structure to implement a priority queue. The operations which are made efficient by the heap data structure are the operations that the priority queue interface needs.


(4) Hash
LT30
https://leetcode.com/problems/substring-with-concatenation-of-all-words/discuss/13700/My-AC-c%2B%2B-code-O(n)-complexity-26ms
- Hash word into int. And then hash vector of words to int.


(5) Sort
_(i)_ Radix sort
Two imple (1) Algr2 (2) LT164

(ii) For int array
LT164
We can either sort based on decimal digit (increase a divider 10 times each time and extract the current digit) OR sort based on binary digit directly


(6) Segment tree
LT1157
Perfect ds for dividing intervals


(7) BFS
_(i) (Hadlock/A*)_
LT675

_(ii) Concise bfs imple_
LT1311
https://leetcode.com/problems/get-watched-videos-by-your-friends/discuss/470695/C%2B%2B-BFS-%2B-Sort



(8) Substring template
LT76
https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems

For most substring problem, we are given a string and need to find a substring of it which satisfy some restrictions. A general way is to use a hashmap assisted with two pointers. The template is given below.

int findSubstring(string s){
        vector<int> map(128,0);
        int counter; // check whether the substring is valid
        int begin=0, end=0; //two pointers, one point to tail and one  head
        int d; //the length of substring

        for() { /* initialize the hash map here */ }

        while(end<s.size()){

            if(map[s[end++]]-- ?){  /* modify counter here */ }

            while(/* counter condition */){ 
                 
                 /* update d here if finding minimum*/

                //increase begin to make it invalid/valid again
                
                if(map[s[begin++]]++ ?){ /*modify counter here*/ }
            }  

            /* update d here if finding maximum*/
        }
        return d;
  }


(9) Pigeon hole
LT164
Put n pigeons into m holes to calculate max distance between two pigeons. m in this case should equal to n - 1 (only in this way can we disregard distance between pigeons within the same hole)



(10) FLoyd Warshall
LT133
The Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem. The problem is to find shortest distances between every pair of vertices in a given edge weighted directed Graph.