LeetCode初级算法-数组

LeetCode的评测机貌似配置不同,同一代码多次提交会有不同的耗时且差别较大

有的简直是像打了鸡血一样跑的飞快,所以下文的“结果”看看就好了,没什么参考价值

1、从排序数组中删除重复项

(1).传送门

传送门:从排序数组中删除重复项

(2).结果

超过99.39%

(3).代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int removeDuplicates(vector<int>& nums)
{
if(nums.empty())
return 0;
int num = 1,i = 1,sz = nums.size();
for(;i < sz;i++)
{
if(nums[i] != nums[i-1])
{
num++;
nums[num-1] = nums[i];
}
}
return num;
}
};

2、买卖股票的最佳时机 II

(1).传送门

传送门:从排序数组中删除重复项

(2).结果

超过100.00%

缺点:代码太长了。。。即使是这种风格,它也太长了

(3).代码

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

class Solution {
public:
int maxProfit(vector<int>& prices) {
int sz = prices.size(),p = 0;
bool buy = false;
for(int i = 0;i < sz;i++){
if(i == 0 || i == sz-1){
if(i == 0){
if(prices[i+1] > prices[i]){
p -= prices[i];
buy = 1;
}
}
else{
if(buy)
p += prices[i];
}
}
else {
if(buy)
{
if(prices[i] > prices[i+1])
{
buy = 0;
p += prices[i];
}
}
else {
if(prices[i] < prices[i+1])
{
buy = 1;
p -= prices[i];
}
}
}
}
return p;
}
};

3、旋转数组

(1).传送门

传送门:旋转数组

(2).结果

超过99.97%

缺点:空间复杂读应该还可以继续优化,另外此题说有三种解法,还有两种懒得想了

(3).代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int sz = nums.size();
if(k == 0 || k == sz)
return ;
if(k > sz)
k %= sz;
vector<int>::iterator it1,it2,it3;
it1 = nums.begin();
it3 = nums.end();
it2 = it3 - k;
nums.insert(it1,it2,it3);
it3 = nums.end();
it2 = it3-k;
nums.erase(it2,it3);
}
};

4、存在重复

(1).传送门

传送门:存在重复

(2).结果

超过63.83%

缺点:偷懒了,直接使用了两个STL函数来解决这个问题,结果也如所预料的那样比较慢

(3).代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
int sz = nums.size();
sort(nums.begin(),nums.end());
int m = unique(nums.begin(),nums.end())-nums.begin();
if(m == sz)
return false;
return true;
}
};

5、只出现一次的数字

(1).传送门

传送门:只出现一次的数字

(2).结果

超过97.67%

(3).代码

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
int singleNumber(vector<int>& nums) {
int sz = nums.size();
int p = 0;
for(int i = 0;i < sz;i++)
p ^= nums[i];
return p;
}
};

6、两个数组的交集 II

(1).传送门

传送门:两个数组的交集 II

(2).结果

超过100.00%

(3).代码

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
class Solution 
{
public:
vector<int> intersect(vector<int>& num1, vector<int>& num2) {
vector<int> v;
vector<int>::iterator pos1,pos2;
sort(num1.begin(),num1.end());
sort(num2.begin(),num2.end());
pos1 = num1.begin(); pos2 = num2.begin();
while(pos1 != num1.end() && pos2 != num2.end())
{
if(*pos1 == *pos2)
{
v.push_back(*pos1);
pos1++;
pos2++;
}
else
{
if(*pos1 > *pos2)
{
pos2++;
}
else
{
pos1++;
}
}
}
return v;
}
};

7、加一

(1).传送门

传送门:加一

(2).结果

超过100.00%

直接模拟,考虑进位

(3).代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int sz = digits.size();
sz--;
bool flag = 1;
while(flag && sz >= 0)
{
if(digits[sz] == 9)
{
digits[sz] = 0;
}
else
{
digits[sz] += 1;
flag = 0;
}
sz--;
}
if(flag)
digits.insert(digits.begin(),1);
return digits;
}
};

8、移动零

(1).传送门

传送门:移动零

(2).结果

超过99.55%

(3).代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int cou = 0;
vector<int>::iterator it;
for(it = nums.begin();it != nums.end();)
{
if(*it == 0)
{
cou++;
nums.erase(it);
}
else
it++;
}
for(int i = 1;i <= cou;i++)
nums.push_back(0);
}
};

9、两数之和

(1).传送门

传送门:两数之和

(2).结果

超过66.08%

(3).代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> re(2);
map<int,int> m;
int sz = nums.size();
for(int i = 1;i < sz;++i)
m[nums[i]] = i;
for(int i = 0;i < sz-1;++i)
{
if(m[target-nums[i]] > 0 && m[target-nums[i]]!= i)
{
re[0] = i;
re[1] = m[target-nums[i]];
return re;
}
}
return re;
}
};

10、有效的数独

(1).传送门

传送门:有效的数独

(2).结果

超过84.09%

缺点:暴力枚举,复杂度大

(3).代码

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
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
map<int,int> m,m1,m2;
// 枚举9个3x3的小宫
for(int i = 0;i < 9;i += 3)
{
for(int j = 0;j < 9;j += 3)
{
for(int k = 0;k < 3;k++)
{
for(int l = 0;l < 3;l++)
{
if(board[i+k][j+l] != '.')
{
m[board[i+k][j+l]-'0']++;
if(m[board[i+k][j+l]-'0'] > 1)
return false;
}
}
}
m.clear();
}
}
// 枚举大的9x9
for(int i = 0;i < 9;i++)
{
for(int j = 0;j < 9;j++)
{
if(board[i][j] != '.')
{
m1[board[i][j]-'0']++;
if(m1[board[i][j]-'0'] > 1)
return false;
}
}
m1.clear();
for(int j = 0;j < 9;j++)
{
if(board[j][i] != '.')
{
m2[board[j][i]-'0']++;
if(m2[board[j][i]-'0'] > 1)
return false;
}
}
m2.clear();
}
return true;
}
};

11、旋转图像

(1).传送门

传送门:旋转图像

(2).结果

超过24.60%

牛客网算法课初级班左神有讲

(3).代码

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
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int sz = matrix[0].size();
if(sz == 1)
return ;
int tR = 0,tC = 0;
int dR = sz-1,dC = sz-1;
while(tR < dR)
{
int times = dC-tC;
int tmp;
for(int i = 0;i < times;i++)
{
tmp = matrix[tR][tC+i];
matrix[tR][tC+i] = matrix[dR-i][tC];
matrix[dR-i][tC] = matrix[dR][dC-i];
matrix[dR][dC-i] = matrix[tR+i][dC];
matrix[tR+i][dC] = tmp;
}
tR++,tC++,dR--,dC--;
}
return ;
}
};