LeetCode热题100：简单模拟
摘要
轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转
k 个位置，其中 k 是非负数。
1
2
3
4
5
6
7
8
9
10
11
12
13
| #include<bits/stdc++.h>
using namespace std;
class Solution {
public:
void rotate(vector<int>& v, int k) {
vector<int > vv(v.size());
for(int i = 0 ; i < v.size() ; i ++){
vv[(i+k) % v.size()] = v[i];
}
v = vv;
}
};
|
缺失的第一个正数
给你一个未排序的整数数组 nums
，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n)
并且只使用常数级别额外空间的解决方案。
1）O(N*logN)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
unordered_set<int > st;
for(auto it : nums){
st.insert(it);
}
for(int i = 1 ; ; i ++){
if(!st.count(i)){
return i;
}
}
return nums.size()+1;
}
};
|
2）O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
for(int i = 0 ; i < nums.size() ; i ++){
while(nums[i] > 0 && nums[i] <= nums.size() && nums[i] != nums[nums[i]-1]){
int x = i, y = nums[i]-1;
swap(nums[x], nums[y]);
}
}
for(int i = 0 ; i < nums.size() ; i ++){
if(nums[i] != i+1){
return i+1;
}
}
return nums.size()+1;
}
};
|
矩阵置零
给定一个 *m* x *n* 的矩阵，如果一个元素为
0 ，则将其所在行和列的所有元素都设为 0
。请使用 原地 算法。
1）空间复杂度O(N + M)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include<bits/stdc++.h>
using namespace std;
class Solution {
public:
void setZeroes(vector<vector<int>>& v) {
int n = v.size(), m = v[0].size();
vector<bool > row(n, false), col(m, false);
for(int i = 0 ; i < n ; i ++){
for(int j = 0 ; j < m ; j ++){
if (v[i][j] == 0) {
row[i] = col[j] = true;
}
}
}
for(int i = 0 ; i < n ; i ++){
for(int j = 0 ; j < m ; j ++){
if (row[i] || col[j]){
v[i][j] = 0;
}
}
}
}
};
|
2）空间复杂度O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<bits/stdc++.h>
using namespace std;
class Solution {
public:
void setZeroes(vector<vector<int>>& v) {
int n=v.size(), m=v[0].size();
bool row0 = false, col0 = false;
for(int i = 0 ; i < n ; i ++){
if(v[i][0] == 0) col0 = true;
}
for(int j = 0 ; j < m ; j ++){
if(v[0][j] == 0) row0 = true;
}
for(int i = 1 ; i < n ; i ++){
for(int j = 1 ; j < m ; j ++){
if(v[i][j] == 0){
v[0][j] = v[i][0] = 0;
}
}
}
for(int i = 1 ; i < n ; i ++){
for(int j = 1 ; j < m ; j ++){
if(v[0][j] == 0 || v[i][0] == 0) v[i][j] = 0;
}
}
if(col0){
for(int i = 0 ; i < n ; i ++){
v[i][0] = 0;
}
}
if(row0){
for(int i = 0 ; i < m ; i ++){
v[0][i] = 0;
}
}
}
};
|
螺旋矩阵
给你一个 m 行 n 列的矩阵
matrix ，请按照 顺时针螺旋顺序
，返回矩阵中的所有元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include<bits/stdc++.h>
using namespace std;
class Solution {
public:
const int dirx[4] = {0, 1, 0, -1};
const int diry[4] = {1, 0, -1, 0};
vector<int> spiralOrder(vector<vector<int>>& v) {
vector<int > ans;
int n = v.size(), m = v[0].size();
int d = 0;
vector<vector<bool> > vis(n, vector<bool>(m));
int cnt = 0, x = 0, y = 0;
while(cnt < n*m){
vis[x][y] = true;
ans.push_back(v[x][y]);
cnt++;
int nx = x + dirx[d % 4];
int ny = y + diry[d % 4];
if(!(nx >= 0 && nx < n) || !(ny >= 0 && ny < m) || vis[nx][ny]){
d++;
nx = x + dirx[d % 4];
ny = y + diry[d % 4];
}
x = nx; y = ny;
}
return ans;
}
};
|
旋转图像
给定一个 n × n 的二维矩阵 matrix
表示一个图像。请你将图像顺时针旋转 90 度。
你必须在原地
旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要
使用另一个矩阵来旋转图像。
1）空间复杂度O(N*M)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include<bits/stdc++.h>
using namespace std;
class Solution {
public:
void rotate(vector<vector<int>>& v) {
vector<vector<int> > t = v;
for(int i = 0 ; i < v.size() ; i ++){
for(int j = 0 ; j < v[i].size() ; j ++){
t[j][v.size()-1-i] = v[i][j];
}
}
v = t;
}
};
|
2）空间复杂度O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<bits/stdc++.h>
using namespace std;
class Solution {
public:
void rotate(vector<vector<int>>& v) {
int n = v.size();
for(int i = 0 ; i < n/2 ; i ++){
for(int j = 0 ; j < (n+1)/2 ; j ++){
int tmp = v[i][j];
v[i][j] = v[n-1-j][i];
v[n-1-j][i] = v[n-1-i][n-1-j];
v[n-1-i][n-1-j] = v[j][n-1-i];
v[j][n-1-i] = tmp;
}
}
}
};
|