Counting Inversions
Merge-Sort Count Binary Indexed Tree
Binary Indexed Tree
Introduction A good tutorial is here: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees Imagine that we have an array A[N], where we do lots of interval sum operations but only a few modifications . Then it is too costy to do a sweep through the array...
Word Ladder ii
Description Difficulty: 4.0/5.0 URL: https://oj.leetcode.com/problems/word-ladder-ii/ Solution We have to use DFS to find all shortest paths. One possible pruning is that we use earliest_visit[str] to record the currently earlist time to reach str for each valid word str in the...
Word Break ii
Description URL: https://oj.leetcode.com/problems/word-break-ii/ Difficulty: 3.0/5.0 Solution We use DFS to enumerate each possible separation of the string. To avoid some of the redundant computation, we use an unordered set not_possible to record the position that already has been visited and...
Surrounded Regions
Description Difficulty: 1.5/2.0 URL: https://oj.leetcode.com/problems/surrounded-regions/ Solution We BFS from each boundary position with ‘O’. If a position with ‘O’ is visited in the BFS, it must be reachable from boundary position with ‘O’. Then we keep it to ‘O’, while...