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 32. 最长有效括号
题目类型
- 动态规划
题目链接
思路
AC代码
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 36. 有效的数独
题目类型
- 遍历
题目链接
思路
判断行列即可 小方块用偏移量来判断
AC代码
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
bool st[9];
// 判断行
for (int i = 0; i < 9; i ++)
{
// 每次判断下一行初始化一下st
memset(st, false, sizeof st);
for (int j = 0; j < 9; j ++)
{
if (board[i][j] != '.')
{
int t = board[i][j] - '1';
if (st[t]) return false;
st[t] = true;
}
}
}
// 判断列
for (int i = 0; i < 9; i ++)
{
// 每次判断下一行初始化一下st
memset(st, false, sizeof st);
for (int j = 0; j < 9; j ++)
{
if (board[j][i] != '.')
{
int t = board[j][i] - '1';
if (st[t]) return false;
st[t] = true;
}
}
}
// 判断小方格
for (int i = 0; i < 9; i += 3)
for (int j = 0; j < 9; j += 3)
{
memset(st, false, sizeof st);
for (int x = 0; x < 3; x ++)
{
for (int y = 0; y < 3; y ++)
{
if (board[i + x][j + y] != '.')
{
int t = board[i + x][j + y] - '1';
if (st[t]) return false;
st[t] = true;
}
}
}
}
return true;
}
};
LeetCode 37. 解数独
题目类型
- 暴搜
- dfs
题目链接
思路
- 对每个没放数的格子，从1-9dfs枚举
- 选择某个数i的时候 判断rows[x][i] cols[y][i] cells[x / 3][y / 3][i]的状态
- 以上判断如果为false，回溯；为true，继续搜索下一个点(x, y + 1)
AC代码
class Solution {
public:
// 行 列 小方格的枚举每个数的状态
bool rows[9][9], cols[9][9], cells[3][3][9];
void solveSudoku(vector<vector<char>>& board) {
memset(rows, false, sizeof rows);
memset(cols, false, sizeof cols);
memset(cells, false, sizeof cells);
// 初始化
for (int i = 0; i < 9; i ++)
{
for (int j = 0; j < 9; j ++)
{
if (board[i][j] != '.')
{
int t = board[i][j] - '1';
rows[i][t] = cols[j][t] = cells[i / 3][j / 3][t] = true;
}
}
}
// 从(0, 0)开始填
dfs(board, 0, 0);
}
bool dfs(vector<vector<char>> &board, int x, int y)
{
if (y == 9) y = 0, x ++;
if (x == 9) return true;
// 如果该位置已经有数了 则换下一个位置
if (board[x][y] != '.') return dfs(board, x, y + 1);
// 否则这个位置可以插入，枚举一下
for (int i = 0; i < 9; i ++)
{
if (!rows[x][i] && !cols[y][i] && !cells[x / 3][y / 3][i])
{
rows[x][i] = cols[y][i] = cells[x / 3][y / 3][i] = true;
board[x][y] = '1' + i;
if (dfs(board, x, y + 1)) return true;
// 回溯
board[x][y] = '.';
rows[x][i] = cols[y][i] = cells[x / 3][y / 3][i] = false;
}
}
return false;
}
};
LeetCode 38. 外观数列
题目类型
题目链接
思路
AC代码
class Solution {
public:
string countAndSay(int n) {
string s = "1";
// 变换n次
for (int i = 0; i < n - 1; i ++)
{
string t;
for (int j = 0; j < s.size();)
{
int k = j + 1;
while (k < s.size() && s[k] == s[j]) k ++;
t += to_string(k - j) + s[j];
j = k;
}
s = t;
}
return s;
}
};
LeetCode 39. 组合总和
题目类型
- dfs
题目链接
思路
- 先对c排序
- 使用dfs搜索，枚举每个位置，当target == 0返回
- 并且枚举每个位置的倍数，当c[i] > target返回
- 对当前结果curpop一次
方法二是y总的解题方法
AC代码1
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> combinationSum(vector<int>& c, int target) {
vector<int> cur;
sort(c.begin(), c.end());
dfs(c, target, 0, cur);
return res;
}
void dfs(vector<int>& c, int target, int u, vector<int>& cur)
{
if (target == 0)
{
res.push_back(cur);
return;
}
for (int i = u; i < c.size(); i ++)
{
if (c[i] > target) break;
cur.push_back(c[i]);
dfs(c, target - c[i], i, cur);
// 回溯
cur.pop_back();
}
}
};
AC代码2
// 无需排序版本 但是运行时间会长
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& c, int target) {
vector<vector<int>> res;
vector<int> cur;
dfs(c, target, 0, cur, res);
return res;
}
void dfs(vector<int>& c, int target, int u, vector<int>& cur, vector<vector<int>>& res)
{
if (target == 0)
{
res.push_back(cur);
return;
}
if (u == c.size()) return;
for (int i = 0; c[u] * i <= target; i ++)
{
dfs(c, target - c[u] * i, u + 1, cur, res);
cur.push_back(c[u]);
}
// 恢复现场
for (int i = 0; c[u] * i <= target; i ++)
{
cur.pop_back();
}
}
};
LeetCode 40. 组合总和 II
题目类型
- dfs
题目链接
思路
跟上一题 LeetCode 39. 组合总和 I类似，只需要dfs的时候把重复元素统计一下，记为cnt，表示该位最多可以有cnt次倍数
AC代码
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> combinationSum2(vector<int>& c, int target) {
sort(c.begin(), c.end());
vector<int> cur;
dfs(c, target, 0, cur);
return res;
}
void dfs(vector<int>& c, int target, int u, vector<int>& cur)
{
if (target == 0)
{
res.push_back(cur);
return;
}
if (u == c.size()) return;
// 有重复元素
int k = u + 1;
while (k < c.size() && c[k] == c[u]) k ++;
int cnt = k - u;
for (int i = 0; i <= cnt && c[u] * i <= target; i ++)
{
dfs(c, target - c[u] * i, k, cur);
cur.push_back(c[u]);
}
// 恢复现场
for (int i = 0; i <= cnt && c[u] * i <= target; i ++)
{
cur.pop_back();
}
}
};
