[LeetCode] Permutation Sequence, Solution

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the k^th permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

» Solve this problem

[Thoughts]
两个解法。
第一，DFS
递归遍历所有可能，然后累加计算，直至到K为止。

第二，数学解法。

假设有n个元素，第K个permutation是
a1, a2, a3, .....   ..., an
那么a1是哪一个数字呢？

那么这里，我们把a1去掉，那么剩下的permutation为
a2, a3, .... .... an, 共计n-1个元素。 n-1个元素共有(n-1)!组排列，那么这里就可以知道

设变量K1 = K
a1 = K1 / (n-1)!

同理，a2的值可以推导为
a2 = K2 / (n-2)!
K2 = K1 % (n-1)!
 .......
a(n-1) = K(n-1) / 1!
K(n-1) = K(n-2) /2!

an = K(n-1)

实现如下：

1:       string getPermutation(int n, int k) {  
2:            vector<int> nums(n);  
3:            int permCount =1;  
4:            for(int i =0; i< n; i++)  
5:            {  
6:                 nums[i] = i+1;  
7:                 permCount *= (i+1);        
8:            }  
9:            // change K from (1,n) to (0, n-1) to accord to index  
10:            k--;  
11:            string targetNum;  
12:            for(int i =0; i< n; i++)  
13:            {    
14:                 permCount = permCount/ (n-i);  
15:                 int choosed = k / permCount;  
16:                 targetNum.push_back(nums[choosed] + '0');  
17:                 //restruct nums since one num has been picked  
18:                 for(int j =choosed; j< n-i; j++)  
19:                 {  
20:                      nums[j]=nums[j+1];  
21:                 }  
22:                 k = k%permCount;  
23:            }  
24:            return targetNum;  
25:       }  

[LeetCode] Spiral Matrix II, Solution

Given an integer n, generate a square matrix filled with elements from 1 to n² in spiral order.

For example,
Given n = 3,

You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

» Solve this problem

[Thoughts]
与Spriral Matrix（http://fisherlei.blogspot.com/2013/01/leetcode-spiral-matrix.html）类似，区别在于一个用递归来剥皮，一个用递归来构造。Code可以复用。

[Code]
红色部分为改动部分。可以看出来，与Spriral Matrix的code相比，改动非常小。

1:       vector<vector<int> > generateMatrix(int n) {  
2:            vector<vector<int>> matrix(n);  
3:            for(int i =0; i< n; i++)  
4:            {  
5:                 matrix[i].resize(n);  
6:            }  
7:            generate_order(matrix, 0, n, 0, n, 1);            
8:            return matrix;  
9:       }  
10:       void generate_order(   
11:       vector<vector<int> > &matrix,   
12:       int row_s, int row_len,   
13:       int col_s, int col_len,      
14:       int val)   
15:       {   
16:            if(row_len<=0 || col_len <=0) return;   
17:            if(row_len ==1)   
18:            {   
19:                 for(int i =col_s; i< col_s+col_len; i++)   
20:                     matrix[row_s][i] = val++;       
21:                 return;   
22:            }   
23:            if(col_len ==1)   
24:            {   
25:                 for(int i =row_s; i<row_s + row_len; i++)   
26:                     matrix[i][col_s] = val++;       
27:                 return;   
28:            }   
29:            for(int i =col_s; i<col_s+col_len-1; i++) //up  
30:                 matrix[row_s][i] = val++;   
31:            for(int i =row_s; i<row_s+row_len-1; i++)  //right  
32:                 matrix[i][col_s+col_len-1] = val++;  
33:            for(int i =col_s; i<col_s+col_len-1; i++) //bottom  
34:                 matrix[row_s+row_len-1][2*col_s+ col_len-1 -i] = val++;  
35:            for(int i =row_s; i<row_s+row_len-1; i++) //left  
36:                 matrix[2*row_s+row_len-1-i][col_s] = val++;  
37:            generate_order(matrix, row_s+1, row_len-2, col_s+1, col_len-2, val);   
38:       }  

[LeetCode] Merge Intervals, Solution

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

» Solve this problem

[Thoughts]
复用一下Insert Intervals的解法即可，http://fisherlei.blogspot.com/2012/12/leetcode-insert-interval.html
创建一个新的interval集合，然后每次从旧的里面取一个interval出来，然后插入到新的集合中。

[Code]
黄色高亮部分是复用的Code.

1:       vector<Interval> merge(vector<Interval> &intervals) {            
2:            vector<Interval> result;  
3:            for(int i =0; i< intervals.size(); i++)  
4:            {  
5:                 insert(result, intervals[i]);  
6:            }  
7:            return result;  
8:       }  
9:       void insert(vector<Interval> &intervals, Interval newInterval) {        
10:            vector<Interval>::iterator it = intervals.begin();   
11:            while(it!= intervals.end())   
12:            {   
13:                 if(newInterval.end<it->start)   
14:                 {   
15:                      intervals.insert(it, newInterval);   
16:                      return;   
17:                 }   
18:                 else if(newInterval.start > it->end)   
19:                 {   
20:                      it++;   
21:                      continue;   
22:                 }   
23:                 else   
24:                 {   
25:                      newInterval.start = min(newInterval.start, it->start);   
26:                      newInterval.end = max(newInterval.end, it->end);   
27:                      it =intervals.erase(it);             
28:                 }           
29:            }   
30:            intervals.insert(intervals.end(), newInterval);    
31:       }   

[LeetCode] Regular Expression Matching, Solution

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "a*") ? true
isMatch("aa", ".*") ? true
isMatch("ab", ".*") ? true
isMatch("aab", "c*a*b") ? true

» Solve this problem

[Thoughts]
与Wildcard Maching同一题。
http://fisherlei.blogspot.com/2013/01/leetcode-wildcard-matching.html