## Sunday, April 7, 2013

### [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 kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
» Solve this problem

[Thoughts]

a1, a2, a3, .....   ..., an

a2, a3, .... .... an, 共计n-1个元素。 n-1个元素共有(n-1)!组排列，那么这里就可以知道

a1 = K1 / (n-1)!

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 n2 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]

[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]

[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]

http://fisherlei.blogspot.com/2013/01/leetcode-wildcard-matching.html