leetcode刷题
数组
简单
1.两数之和
我的算法思想：
通过遍历两次数组计算每两个元素的和，找到一对与target相等的元素返回即可。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
for(int i = 0;i < nums.size() - 1;i++)
{
for(int j = i + 1;j < nums.size();j++)
{
if(nums[i] + nums[j] == target)
{
ans = {i,j};
return ans;
}
}
}
return ans;
}
};
|
学习：
1.Vector作为C++中的动态数组容器，可以容纳多种数据类型，支持随机存储；定义及初始化操作：
| vector v1 |
v1是一个元素类型为T的空容器 |
| vector v2(v1) |
使用v1中的元素初始化v2 |
| vector v2 = v1 |
同上 |
| vector v3(n,val) |
v3中包含n个值为val的元素 |
| vector v4 {a,b,c…} |
使用a,b,c…初始化v4 |
| vector> matrix(M,vector(N)) |
二维数组初始化 |
| vector v5(n) |
v5中包含n个默认值的初始化元素 |
常用操作：
| v1 = {a,b,c…} |
用元素{a,b,c….}替代v1中元素 |
|
2.寻找更优的算法：
利用哈希表可以将寻找 target - x 的时间从O(N)降到O(1);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> hashtable;
for(int i = 0;i < nums.size();i++)
{
auto it = hashtable.find(target - nums[i]);
if(it != hashtable.end())
{
return {it->second,i};
}
hashtable[nums[i]] = i;
}
return {};
}
};
|
注意：C++中哈希表find()函数是以key键值作为参数寻找哈希表中元素，对于本题应该将x的值作为key，对应index索引值作为指向值。
26.删除有序数组中的重复项
思想
利用两个指针遍历有序数组，如果快指针与慢指针值相同，快指针后移；不同，则将快指针指向的值赋给慢指针，然后慢指针后移，直到快指针走到最后。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int n = nums.size();
if(n == 0)
{
return 0;
}
int index = 0;
for(int i = 1;i < nums.size();i++)
{
if(nums[i] != nums[index])
{
nums[++index] = nums[i];
}
}
return index + 1;
}
};
|
注意：
1.题目中提示有判断结果的方式，根据算法的返回值来比对对应长度的数组是否相同，不需要将数组重复元素删除，将重复元素后移返回对应长度即可。
2.思考二：可以调用Unique方法，但本质还是上述思想，将非重复元素前移。
1
2
3
4
5
6
7
8
| class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int n = nums.size();
auto pos = unique(nums.begin(),nums.end());
return distance(nums.begin(),pos);
}
};
|
27移除元素
我的算法思想：双指针法(头尾指针)：
从头尾同时遍历数组，根据题目要求，数组前半部分元素 != val值，后半部分 == val值，故当头指针指向元素的值 == val，与尾指针对应元素交换，尾指针前移；当不等时，头指针后移。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n = nums.size();
if(n == 1 && nums[0] == val)
{
return 0;
}
int i = 0,j = n - 1;
while(i <= j)
{
if(nums[i] == val)
{
nums[i] = nums[j--];
}
else
{
i++;
}
}
return j + 1;
}
};
|
改进：头指针的值等于结果数组的长度；将尾指针初始位置后移一位，不用再单独判断n = 1的情况，同时while截至条件不需要等于。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n = nums.size();
int i = 0,j = n;
while(i < j)
{
if(nums[i] == val)
{
nums[i] = nums[j-1];
j--;
}
else
{
i++;
}
}
return i;
}
};
|
思想二：双指针法(头头指针)
设置两个头指针，只要保证结果数组中左半部分的正确性即可，故令两个指针速度不同，慢指针指向左半数组应当填充元素位置，快指针用于遍历整个数组，当快指针指向元素 != val，将其加入慢指针指向位置，同时快慢指针后移；否则快指针后移。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n = nums.size();
int slow = 0;
for(int fast = 0;fast < n;fast++)
{
if(nums[fast] != val)
{
nums[slow++] = nums[fast];
}
}
return slow;
}
};
|
35搜索插入位置
我的算法思想：二分查找
由于题目要求时间复杂度必须为O(log n)，所以首先想到二分查找的方法，如果找到目标值就返回mid索引，未找到目标值代表最终结果时low > high；只有两种情况：
1.nums[mid] > target：high前移，low指向应该插入位置
2.nums[mid] < target：low后移，low指向应该插入位置
其中low永远指向第一个小于target的后一元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int low = 0;
int high = nums.size()-1;
int mid = 0;
while(low <= high){
mid = (low+high)/2;
if(nums[mid] == target)
{
return mid;
}
else if(nums[mid] > target)
{
high = mid - 1;
}
else{
low = mid + 1;
}
}
return low;
}
};
|
采用移位计算mid防止溢出
1
| int mid = ((right - left) >> 1) + left;
|
思想二：递归
66.加一
我的思想：
从最后一位开始判断是否是9，如果是9，需要化0然后进位；否则加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
| class Solution {
public:
vector<int> Binary(vector<int>& digits,int index){
if(digits[index] == 9)
{
digits[index] = 0;
if(index == 0)
{
digits.insert(digits.begin(),1);
}
else
{
Binary(digits,index - 1);
}
}
else{
digits[index] += 1;
return digits;
}
return digits;
}
vector<int> plusOne(vector<int>& digits) {
int n = digits.size();
return Binary(digits,n-1);
}
};
|
改进：直接遍历判断即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int n = digits.size();
for(int i = n - 1;i>=0;i--)
{
if(++digits[i] < 10){
return digits;
}
else{
digits[i] = 0;
if(digits[0] == 0){
digits.insert(digits.begin(),1);
}
}
}
return digits;
}
};
|
再提速：循环内只判断是否等于9，如果可以从循环退出，意味第一位需要进位。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int n = digits.size();
for(int i = n - 1;i>=0;i--)
{
if(++digits[i] < 10){
return digits;
}
else{
digits[i] = 0;
}
}
digits.insert(digits.begin(),1);
return digits;
}
};
|
88.合并两个有序数组
我的思想：双指针
分别从头遍历两个数组，按照输入案例，需要保证有序性，即相等元素nums1在前；同时由于vector特性，需要特殊处理空数组情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i=0,j=0;
if(m + n == n){
nums1 = nums2;
}
while(i<m && j<n){
if(nums1[i]<=nums2[j])
i++;
else{
nums1.insert(nums1.begin()+i,nums2[j]);
nums1.pop_back();
m++;
j++;
}
}
while(j<n){
nums1[i++] = nums2[j++];
}
}
};
|
需要注意插入到nums1中的元素不能覆盖原有元素；
双指针改进：逆双指针
由于nums1数组后n位都是0，故可以从后遍历，每次选取较大的值放入；
内置函数法：
1.先将两个数组合并，再sort
2.直接merge（merge要求两个待合并排序的数组排序规则相同）
1
2
|
merge(first.begin(),first.begin()+len1,second.begin(),second.begin()+len2,result.begin());
|