腾讯精选50题—Day7题目54,59,61
今天是刷题的第七天，元气满满的周一~~
目录
1. 题目54 螺旋矩阵
(1) 题目描述
(2) 思路
螺旋矩阵的问题比较简单，只要定好四个位置即可，lx、rx、by、ty，按照绿色箭头顺序遍历，在遍历的过程中保证lx不能大于rx同时by不能大于ty。
(3) 题解
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int lx = 0;
int rx = matrix[0].size() - 1;
int by = 0;
int ty = matrix.size() - 1;
int number = matrix[0].size() * matrix.size();
vector<int> result;
while(true)
{
if (lx > rx || by > ty)
break;
for (int i = lx; i <= rx; i++)
result.push_back(matrix[by][i]);
by++;
if (lx > rx || by > ty)
break;
for (int j = by; j <= ty; j++)
result.push_back(matrix[j][rx]);
rx--;
if (lx > rx || by > ty)
break;
for (int k = rx; k >= lx; k--)
result.push_back(matrix[ty][k]);
ty--;
if (lx > rx || by > ty)
break;
for (int t = ty; t >= by; t--)
result.push_back(matrix[t][lx]);
lx++;
}
return result;
}
};
结果：
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
空间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
2. 题目59 螺旋矩阵II
(1) 题目描述
(2) 思路
思路和54题类型，先声明一个空的矩阵，然后填数字。
(3) 题解
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> result(n, vector<int>(n, 0));
int lx = 0;
int rx = n - 1;
int by = 0;
int ty = n - 1;
int num = 1;
while (true)
{
if (lx > rx || by > ty)
break;
for (int i = lx; i <= rx; i++)
{
result[by][i] = num;
num++;
}
by++;
if (lx > rx || by > ty)
break;
for (int j = by; j <= ty; j++)
{
result[j][rx] = num;
num++;
}
rx--;
if (lx > rx || by > ty)
break;
for (int k = rx; k >= lx; k--)
{
result[ty][k] = num;
num++;
}
ty--;
if (lx > rx || by > ty)
break;
for (int t = ty; t >= by; t--)
{
result[t][lx] = num;
num++;
}
lx++;
}
return result;
}
};
结果：
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
空间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
3. 题目61 旋转链表
(1) 题目描述
(2) 思路
先成环，后断链。
(3) 题解
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (k == 0)
return head;
ListNode* p = head;
ListNode* tail = NULL;
int len = 0;
while (p != NULL)
{
if (p->next == NULL)
tail = p;
p = p->next;
len++;
}
if (len == 0) return NULL;
int new_k = k % len;
tail->next = head;
p = tail;
int move_step = len - new_k;
while (move_step > 0)
{
p = p->next;
move_step--;
}
ListNode* result = p->next;
p->next = NULL;
return result;
}
};
结果：
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
1
)
O(1)
O(1)