Solution to LeetCode Problems: Unique Paths II

Unique Paths II

Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.
Note: m and n will be at most 100.

Thoughts:
We cannot use the combination trip anymore. Are we forced to use graph search?
Set the paths to the top-left of the grid, i.e. (0,0) as 1, if not blocked. Then any point in the grid has the number fo unique paths:

1. if blocked  
2.   0  
3. else  
4.   path_from_left + path_from_top  

So we can simply traverse the grid row by row and fill up the values. Extra memory allocation is not necessary, we can use the original grid.


Solution:

1. class Solution {  
2. public:  
3.     int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {  
4.         const size_t RR = obstacleGrid.size();  
5.         const size_t CC = obstacleGrid[0].size();  
6.           
7.         // fill up the grid system  
8.         for(size_t r = 0; r < RR; ++r)  
9.             for(size_t c = 0; c < CC; ++c)  
10.             {  
11.                 if (obstacleGrid[r][c] == 1)  
12.                     // blocked...  
13.                     obstacleGrid[r][c] = 0;  
14.                 else if (r == 0 && c == 0)  
15.                     // starting point  
16.                     obstacleGrid[r][c] = 1;  
17.                 else {  
18.                     int right_ways = (c == 0 ? 0 : obstacleGrid[r][c-1]);  
19.                     int top_ways = (r == 0 ? 0 : obstacleGrid[r-1][c]);  
20.                     obstacleGrid[r][c] = right_ways + top_ways;  
21.                 }  
22.             }  
23.           
24.         return obstacleGrid[RR - 1][CC - 1];  
25.     }  
26. };  

Solution to LeetCode Problems: Unique Paths

Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.


Thoughts:
Of course, this can be solved by applying either DFS or BFS on a directed graph. Any better solution?
Since the robot can only choose "right" or "down", the total number of each movement are fixed to (m+n-2). We can first pick up (m-1) "down" moves, and the other movements can be "right" direction only.
So the total number of unique paths are Combination(m+n-2, m-1).
The combination has factorial calculations, so we have to be careful avoiding overflow. Here the algorithm is taken from TAOCP.

Solution:

1. class Solution {  
2. public:  
3.     unsigned long long  
4.     choose(unsigned long long n, unsigned long long k) {  
5.         if (k > n) {  
6.             return 0;  
7.         }  
8.         unsigned long long r = 1;  
9.         for (unsigned long long d = 1; d <= k; ++d) {  
10.             r *= n--;  
11.             r /= d;  
12.         }  
13.         return r;  
14.     }  
15.   
16.     int uniquePaths(int m, int n) {  
17.         if (m == 1 || n == 1)  
18.             return 1;  
19.               
20.         if (m < n) swap(m, n);  
21.           
22.         return choose(m+n-2, n-1);         
23.     }  
24. };  

Solution to LeetCode Problems: Valid Sudoku

Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character'.'.

A partially filled sudoku which is valid.

Thoughts:
Mark every used number in a row, column or block. When a re-marking occurs, return false. Note the method used to calculate the block ID using row and column indices.

Solution:

1. // ⑨ ばか
2. #define BAKA 9  
3.   
4. class Solution {  
5. public:  
6.     bool isValidSudoku(vector<vector<char> > &board) {  
7.         array<bool, BAKA> row[BAKA];  
8.         array<bool, BAKA> col[BAKA];  
9.         array<bool, BAKA> box[BAKA];  
10.   
11.         // as standard C array  
12.         // the variables are not initialized...  
13.         for(auto r = 0; r < BAKA; ++r)  
14.             for(auto c = 0; c < BAKA; ++c)  
15.                 row[r][c] = col[r][c] = box[r][c] = false;  
16.   
17.         for(auto r = 0; r < BAKA; ++r)  
18.             for(auto c = 0; c < BAKA; ++c)  
19.             {  
20.                 char ch=board[r][c];  
21.                 if (ch == '.')  
22.                     continue;   // blank, no effect  
23.                   
24.                 ch -= '1';  
25.                   
26.                 if (row[r][ch])  
27.                     return false;  
28.                 row[r][ch] = true;  
29.                   
30.                 if (col[c][ch])  
31.                     return false;  
32.                 col[c][ch] = true;  
33.                   
34.                 if (box[r / 3 * 3 + c / 3][ch])  
35.                     return false;  
36.                 box[r / 3 * 3 + c / 3][ch] = true;  
37.             }  
38.               
39.         return true;  
40.     }  
41. }; 

Solution to LeetCode Problems: Anagrams

Anagrams

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

Thoughts:

What is the definition of anagrams?
One thing has to be thought over: do "" and "" together make a pair of anagrams?

After we defined anagrams, the algorithm straight in the mind is hash. What is a good hash algorithm? There are several possibilities. Two of them are: 1. hash by sorting the string; 2. hash by counting the number of used characters, respectively. The latter is used in the solution.

Solution:

1. class Solution {  
2. public:  
3.     struct StringHash  
4.     {  
5.         char hash[26];  
6.           
7.         StringHash(const string& str)  
8.         {  
9.             fill(hash, hash+26, 0);  
10.             for(auto& ch : str)  
11.                 ++ hash[ch - 'a'];  
12.         }  
13.           
14.         bool operator<(const StringHash& sh) const  
15.         {  
16.             for(size_t i = 0; i < 26; ++i)  
17.                 if ( this->hash[i] < sh.hash[i] )  
18.                     return true;  
19.                 else if ( this->hash[i] > sh.hash[i] )  
20.                     return false;  
21.             return false;  
22.         }  
23.     };  
24.   
25.     vector<string> anagrams(vector<string> &strs)   
26.     {  
27.         map<StringHash, vector<vector<string>::iterator>>  hash_map;  
28.   
29.         for(auto iter=begin(strs); iter != end(strs); ++iter)  
30.             hash_map[StringHash(*iter)].push_back(iter);  
31.   
32.         vector<string> ret;  
33.         for(auto hsm : hash_map)  
34.             if (hsm.second.size() >= 2)  
35.                 for(auto i : hsm.second)  
36.                     ret.push_back(*i);  
37.   
38.         return ret;  
39.     } 

Solution to LeetCode Problems: Count and Say

Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the n^th sequence.
Note: The sequence of integers will be represented as a string.

Thoughts:
Scan the string while maintaining a "state" that counts the numbers. Save previous results for accelerating the next string generation.


Solution:

1. class Solution {  
2. public:  
3.     // save previous history for accelerated calculation  
4.     vector<string> history;  
5.       
6.     Solution()  
7.     {  
8.         history.emplace_back(string("1"));  
9.     }  
10.       
11.     string generate_seq(const string& in)  
12.     {  
13.         string generated;  
14.         char scratch[64];  
15.         char current = in[0];  
16.         int count = 0;  
17.           
18.         auto commit = [&]()  
19.         {  
20.             sprintf(scratch, "%d%c", count, current);  
21.             generated += scratch;  
22.         };  
23.           
24.         for(auto ch : in)  
25.             if (ch != current)  
26.             {  
27.                 // we met another character  
28.                 commit();  
29.   
30.                 count = 1;  
31.                 current = ch;  
32.             }  
33.             else  
34.                 ++count;  
35.           
36.         commit();   // commit the last continuous char accumulation  
37.         return generated;  
38.     }  
39.       
40.     string countAndSay(int n)   
41.     {  
42.         while(n-1 >= history.size())  
43.             // exploit the r-value reference  
44.             history.emplace_back(generate_seq(history.back()));  
45.               
46.         return history[n-1];  
47.     }  
48. };  

Solution to LeetCode Problems: Subsets

Subsets

Given a set of distinct integers, S, return all possible subsets.
Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Thoughts:
For a set with n elements, the number of subsets is 2^n. Every element has "chosen" or "not-chosen" state, this led direct use of bit operations.

Solution:

1. class Solution {  
2. public:  
3.     vector<vector<int> > subsets(vector<int> &S) {  
4.         sort(begin(S), end(S)); // ensure non-descending results  
5.           
6.         const size_t n = S.size();  
7.         const size_t num_sets = pow(2, n);  
8.           
9.         vector<vector<int>> ret(num_sets);  
10.       
11.         for(size_t bitwise = 0; bitwise < num_sets; ++bitwise)  
12.         {  
13.             size_t bit_chk = 1;  
14.             for(size_t bit = 0; bit < n; ++bit)  
15.                 if ((bit_chk << bit) & bitwise)  
16.                     ret[bitwise].push_back(S[bit]);  
17.         }  
18.           
19.         return ret;  
20.     }  
21. }; 

Solution to LeetCode Problems: Merge Sorted Array

Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Thoughts:
A direct solution is, allocate an array with length [m+n] and merge. Then copy the merged array to the original array A. I strongly doubt if it would be the expected answer.

Let's assume only O(1) space could be used instead. Then we have to consider the exploit of excess space in array A, with length n. We can merge the two arrays there, and when the space is all used up, data at starting of A should be either useless (already merged) or at the right place (if all elements in B are smaller than A).

Then we rotate the array leftwise by m. Such coding can be implemented by three reverses: [0, m+n), [0, n), [n, m+n). This is illustrated in Programming Pearls.

Solution:

1. class Solution {  
2. public:  
3.     void merge(int A[], int m, int B[], int n) {  
4.         // Iterator used through merging  
5.         int merge_A = 0;   
6.         int merge_B = 0;  
7.           
8.         // merge is done at the end of m-th element, A[]  
9.         int merge_iter = m;  
10.           
11.         while(merge_A < m || merge_B < n)  
12.         {  
13.             // check if we reached the end of merge region, if so,   
14.             // start from beginning  
15.             if (merge_iter == m + n)  
16.                 merge_iter = 0;  
17.   
18.             if (merge_A == m)  // merge A is done  
19.                 A[merge_iter++] = B[merge_B++];  
20.             else if (merge_B == n) // merge B is done  
21.                 A[merge_iter++] = A[merge_A++];  
22.             else  
23.                 A[merge_iter++] = (A[merge_A] < B[merge_B] ? A[merge_A++] : B[merge_B++]);  
24.         }  
25.           
26.         // merge is complete, now the array looks like  
27.         // 4567 | 123  
28.         // so we need to reverse it -- ref. Programming Pearls  
29.         reverse(A, A+m);  
30.         reverse(A+m, A+m+n);  
31.         reverse(A, A+m+n);  
32.     }  
33. };