Leetcode题解（20）

59. Spiral Matrix II

题目

这道题copy网上的代码

 1 class Solution {
 2 private:
 3     int step[4][2];
 4     bool canUse[100][100];
 5 public:
 6     void dfs(int dep, vector<vector<int> > &matrix, int direct, int x, int y)
 7     {
 8         for(int i = 0; i < 4; i++)
 9         {
10             int j = (direct + i) % 4;
11             int tx = x + step[j][0];
12             int ty = y + step[j][1];
13             if (0 <= tx && tx < matrix.size() && 0 <= ty && ty < matrix[0].size() && canUse[tx][ty])
14             {
15                 canUse[tx][ty] = false;
16                 matrix[tx][ty] = dep;              
17                 dfs(dep + 1, matrix, j, tx, ty);               
18             }            
19         }
20     }
21     
22     vector<vector<int> > generateMatrix(int n) {
23         // Start typing your C/C++ solution below
24         // DO NOT write int main() function
25         step[0][0] = 0;
26         step[0][1] = 1;
27         step[1][0] = 1;
28         step[1][1] = 0;
29         step[2][0] = 0;
30         step[2][1] = -1;
31         step[3][0] = -1;
32         step[3][1] = 0;
33         vector<vector<int> > ret(n, vector<int>(n));
34         memset(canUse, true, sizeof(canUse));
35         dfs(1, ret, 0, 0, -1);
36         
37         return ret;        
38     }
39     
40 };

----------------------------------------------------------------------------分割线----------------------------------------------------------------------

60. Permutation Sequence

题目

分析：这道题主要考数学推断

在n!个排列中，第一位的元素总是(n-1)!一组出现的，也就说如果p = k / (n-1)!，那么排列的最开始一个元素一定是nums[p]。

假设有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 class Solution {
 2 public:
 3     string getPermutation(int n, int k) {
 4         vector<int> nums(n);
 5         int pCount = 1;
 6         for(int i = 0 ; i < n; ++i) {
 7             nums[i] = i + 1;
 8             pCount *= (i + 1);
 9         }
10 
11         k--;
12         string res = "";
13         for(int i = 0 ; i < n; i++) {
14             pCount = pCount/(n-i);
15             int selected = k / pCount;
16             res += ('0' + nums[selected]);
17             
18             for(int j = selected; j < n-i-1; j++)
19                 nums[j] = nums[j+1];
20             k = k % pCount;
21         }
22         return res;
23     }
24 };

------------------------------------------------------------------------分割线--------------------------------------------------------------------------

61. Rotate List

题目

代码如下：

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* rotateRight(ListNode* head, int k) {
12         //如果k值大于链表长度应该怎么处理
13         if(NULL == head)
14             return NULL;
15         ListNode* temp = head;
16         int count = 0;
17         while(temp != NULL)
18         {
19             count++;
20             temp = temp->next;
21         }
22         k = k%count;
23         if(k == 0)
24             return head;
25         ListNode *first,*second;
26         first = head;
27         int i=k;
28         while(i--)
29         {
30             //if(NULL == first)
31             //    return NULL;
32             first = first->next;
33         }
34         second = head;
35         while(first->next != NULL)
36         {
37             first = first->next;
38             second = second->next;
39         }
40         temp = head;
41         head = second->next;
42         first->next = temp;
43         second->next = NULL;
44         return head;
45     }
46 };