LeetCode 1. 两数之和
题目链接
思路1 暴力枚举
两重循环枚举下标 i,ji,j，然后判断 nums[i]+nums[j] 是否等于 target。
复杂度O（n^2）
AC代码1
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
for(int i = 0; i < nums.size(); i ++)
{
for(int j = 0; j < i; j ++)
{
if(nums[i] + nums[j] == target)
{
res = vector<int> {i, j};
}
}
if(res.size() > 0) break;
}
return res;
}
};
思路2 哈希表优化
使用哈希表边查找边存储
查找target - num[i]是否在哈希表中 存在则返回
将num[i]插入哈希表的插入和查询操作的复杂度O（1），总复杂度O（n）
AC代码2
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
unordered_map<int, int> hash;
// 边找边插入
for(int i = 0; i < nums.size(); i ++)
{
int another = target - nums[i];
if(hash.count(another))
{
res = vector<int> {hash[another], i};
break;
}
hash[nums[i]] = i;
}
return res;
}
};
LeetCode 31. 下一个排列
题目类型
- 数组
- 找规律题
题目链接
思路
建议画图用例子模拟
[2 3 5 4 1] => [2 4 1 3 5]
- 先用指针k从后往前找，找到第一个不满足nums[k - 1]>nums[k]的位置，即k即往后的都为降序
- 如果k在nums起始位置，则将整个数组反转，否则执行3
- 用指针t从指针k所在位置往右寻找，找到第一个大于nums[k-1]的数,此时整个数为nums[t - 1]
- 并且将nums[k-1]和nums[t - 1]互换
- 将k后面的序列反转
AC代码
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int k = nums.size() - 1;
// 2 3 5 4 1
// 此时处于5这个位置
while (k > 0 && nums[k - 1] >= nums[k]) k --;
// 整个序列都是降序
if (k <= 0)
{
reverse(nums.begin(), nums.end());
}
else
{
int t = k;
while (t <= nums.size() - 1 && nums[t] > nums[k - 1]) t ++;
swap(nums[k - 1], nums[t - 1]);
reverse(nums.begin() + k, nums.end());
}
}
};
LeetCode 33. 搜索旋转排序数组
题目类型
- 双指针
- 二分（最优解）
题目链接
思路
朴素做法和双指针算法比较简单，但是都没有利用旋转这个前提
二分做法：
- 利用二分寻找分界点位置
- 两个有序序列的分界点画图很容易知道是nums[0]
- 如果target大于nums[0]说明在第一个区间 如果小于nums[0]说明在第二个区间
- 在target所在区间再进行一次二分
AC代码1
// 朴素做法
class Solution {
public:
int search(vector<int>& nums, int target) {
for (int i = 0; i < nums.size(); i ++)
{
if (nums[i] == target) return i;
}
return -1;
}
};
AC代码2
// 双指针做法
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size() - 1;
int i = 0, j = n;
while (i <= j)
{
if (nums[i] != target) i ++;
else return i;
if (nums[j] != target) j --;
else return j;
}
return -1;
}
};
AC代码3（最优解）
class Solution {
public:
int search(vector<int>& nums, int target) {
if (nums.empty()) return -1;
// 用二分先找到两个有序序列的分段点位置
int l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (nums[mid] >= nums[0]) l = mid;
else r = mid - 1;
}
// 这里两个序列有个分界点 Nums[0]
if (target >= nums[0]) l = 0; // 在第一个区间
else l = r + 1, r = nums.size() - 1; // 在第二个区间
while (l < r)
{
int mid = l + r >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
if (nums[r] == target) return r;
else return -1;
}
};
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置
题目类型
- 双指针
- 二分（最优解，代码简单）
题目链接
https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array
思路
使用双指针前后扫描定位，注意边界问题即可
使用二分最容易，也是最优解，代码最简洁
AC代码1
// 双指针
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res;
if (nums.size() == 0)
{
res.push_back(-1), res.push_back(-1);
return res;
}
int i = 0, j = nums.size() - 1;
if (i < j)
{
while (i < nums.size() - 1 && nums[i] < target) i ++;
while (j > 0 &&nums[j] > target) j --;
}
if (nums[i] != target && nums[j] != target)
{
res.push_back(-1); res.push_back(-1);
return res;
}
else if (i <= j && nums[i] == target && nums[j] == target)
{
res.push_back(i); res.push_back(j);
}
return res;
}
};
AC代码2
// 二分
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.empty()) return {-1, -1};
int n = nums.size();
// 寻找左边界
int l = 0, r = n - 1;
while (l < r)
{
int mid = l + r >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
// 存储好左边界l
int L = l;
if (nums[l] != target) return {-1, -1};
// 寻找右边界
l = 0, r = n - 1;
while (l < r)
{
int mid = l + r + 1>> 1;
if (nums[mid] <= target) l = mid;
else r = mid - 1;
}
return {L, r};
}
};
LeetCode 35. 搜索插入位置
题目类型
二分
题目链接
思路
使用二分搜素比较简单 直接AC，这里只讲搜索左边界的思路（对应是AC代码1），右边界的思路（对应AC代码2）
- 使用二分搜索≤target数的位置l
- 如果target > nums[l]，则插入位置为l+1，否则为l
AC代码1
// 二分写法一：
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int n = nums.size();
int l = 0, r = n - 1;
while (l < r)
{
int mid = l + r >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
if (target > nums[l]) return l + 1;
else return l;
}
};
AC代码2
// 二分写法二
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int n = nums.size();
int l = 0, r = n - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (nums[mid] <= target) l = mid;
else r = mid - 1;
}
if (target <= nums[r]) return r;
else return r + 1;
}
};
LeetCode 41. 缺失的第一个正数
题目类型
- 哈希表
- 技巧法
题目链接
思路
方法一（哈希表）：
- 将 nums 中每个元素放入哈希表中
- 从res = 1开始，每次查询一次hash.count(res)
- 如果存在，则res++
- 如果不存在，返回res，res为所求结果
方法二：
- 如果满足条件nums[i] >= 0 && nums[i] < n && nums[i] != i && nums[i] != nums[nums[i]]
- 遍历nums数组，每次将nums[i]元素放到相应的i位置
AC代码1
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
unordered_set<int> hash;
for (auto x : nums)
{
hash.insert(x);
}
int res = 1;
while (hash.count(res)) res ++;
return res;
}
};
AC代码2
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
if (!n) return 1;
// 映射一下
for (auto&x : nums)
if (x != INT_MIN) x --;
for (int i = 0; i < n; i ++)
{
while (nums[i] >= 0 && nums[i] < n && nums[i] != i && nums[i] != nums[nums[i]])
{
swap(nums[i], nums[nums[i]]);
}
}
// 查询
for (int i = 0; i < n; i ++)
{
if (nums[i] != i)
return i + 1;
}
return n + 1;
}
};
LeetCode 42. 接雨水
题目类型
思路
AC代码
LeetCode 45 跳跃游戏 II
题目类型
思路
AC代码
class Solution {
public:
int jump(vector<int>& nums) {
int start = 0;
int end = 1;
int res = 0;
while (end < nums.size())
{
int maxPos = 0;
// 能跳跃的最大距离
for (int i = start; i < end; i ++)
{
maxPos = max(maxPos, i + nums[i]);
}
start = end;
end = maxPos + 1;
res ++;
}
return res;
}
};
LeetCode 53. 最大子数组和
题目类型
- 动规
题目链接
思路
AC代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res = nums[0];
for (int i = 1; i < nums.size(); i ++)
{
nums[i] = max(nums[i], nums[i - 1] + nums[i]);
res = max(res, nums[i]);
}
return res;
}
};
LeetCode 54. 螺旋矩阵
题目类型
- 搜索
题目链接
思路
- 定义四个方向的向量
- 每次遇到边界或者已经访问过了就改变运动方向
- 使用变量d代表下一次运动方向，运动顺序依次是右（0） 下（1） 左（2）上（3），每次对d取模4，得到下一次运动方向向量
AC代码
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
int n = matrix.size();
int m = matrix[0].size();
if (!n) return res;
vector<vector<bool>> st(n, vector<bool>(m));
// 定义四个方向向量 右 下 左 上
int dx[] = {0, 1, 0, - 1}, dy[] = {1, 0, -1, 0};
// d指的是下一次运动方向
for (int i = 0, x = 0, y = 0, d = 0; i < n * m; i ++)
{
res.push_back(matrix[x][y]);
st[x][y] = true;
// 计算下一次运动位置
int a = x + dx[d], b = y + dy[d];
if (a < 0 || a >= n || b < 0 || b >= m || st[a][b]) // 改变方向
{
d = (d + 1) % 4;
a = x + dx[d], b = y + dy[d];
}
x = a, y = b;
}
return res;
}
};
##
题目类型
思路
AC代码
LeetCode 55. 跳跃游戏
题目类型
思路
AC代码
class Solution {
public:
bool canJump(vector<int>& nums) {
for (int i = 0, j = 0; i < nums.size(); i ++)
{
if (i > j) return false;
j = max(j, i + nums[i]);
}
return true;
}
};
LeetCode 56. 合并区间
题目类型
- 贪心
题目链接
思路
AC代码
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& a) {
vector<vector<int>> res;
if (!a.size()) return res;
sort(a.begin(), a.end());
int l = a[0][0], r = a[0][1];
for (int i = 1; i < a.size(); i ++)
{
if (a[i][0] > r) // 不相交
{
res.push_back({l, r});
l = a[i][0], r = a[i][1];
}
else // 两个区间相交
{
r = max(r, a[i][1]);
}
}
res.push_back({l, r});
return res;
}
};
##
题目类型
思路
AC代码
