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. 接雨水
题目类型
- 三次线性扫描法
- 单调栈
题目链接
https://www.acwing.com/activity/content/problem/content/2379/
思路
参考大佬的题解: https://www.acwing.com/solution/content/121/
方法一：
- 每个位置能接受的雨水取决于左边最大、右边最大和当前高度
- 即每个位置的接受雨水 = min(左边最大, 右边最大) - 当前位置的高度
方法二（单调栈）：
- 考虑每个位置左边和右边第一个比自身不低的矩形，以及三个矩形构成的凹槽
AC代码1
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int ans = 0;
if (!n) return ans;
// 每个位置能接受的雨水取决于左边最大、右边最大和当前高度
// 即每个位置的接受雨水 = min(左边最大, 右边最大) - 当前位置的高度
// 记录每个位置的左边最大 和 右边最大
vector<int> left_max(n), right_max(n);
// 寻找左边最大
left_max[0] = height[0];
for (int i = 1; i < n; i ++)
{
left_max[i] = max(left_max[i - 1], height[i]);
}
// 寻找右边最大
right_max[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i --)
{
right_max[i] = max(right_max[i + 1], height[i]);
}
// for (int i = 0; i < n; i ++) cout << left_max[i] << " ";
// cout << endl;
// for (int i = 0; i < n; i ++) cout << right_max[i] << " ";
// cout << endl;
// 计算接收雨水量
for (int i = 0; i < n; i ++)
{
ans += min(left_max[i], right_max[i]) - height[i];
}
return ans;
}
};
AC代码2
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
stack<int> stk;
int ans = 0;
for (int i = 0; i < n; i ++)
{
while (!stk.empty() && height[stk.top()] <= height[i])
{
int top = stk.top();
stk.pop();
if (stk.empty()) break;
ans += ( min(height[stk.top()], height[i]) - height[top] ) * (i - 1 - stk.top());
}
stk.push(i);
}
return ans;
}
};
LeetCode 43. 字符串相乘
题目类型
- 乘法运算
题目链接
思路
参考算法基础高精度乘法算法：https://alexjakin.github.io/2022/05/18/jichusuanfapiangaojingduyunsuanbiji/
AC代码
class Solution {
public:
string multiply(string num1, string num2) {
int n = num1.size(), m = num2.size();
vector<int> A;
vector<int> B;
vector<int> C(n + m);
for (int i = n - 1; i >= 0; i --) A.push_back(num1[i] - '0');
for (int i = m - 1; i >= 0; i --) B.push_back(num2[i] - '0');
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
C[i + j] += A[i] * B[j];
for (int i = 0, t = 0; i < C.size(); i ++)
{
t += C[i];
C[i] = t % 10;
t /= 10;
}
//去掉前导0
int k = C.size() - 1;
while (k && !C[k]) k --;
string res;
// C高位在后低位在前
while (k >= 0) res += C[k --] + '0';
return res;
}
};
LeetCode 44. 通配符匹配
题目类型
- 动态规划
题目链接
思路
参考大佬题解
https://www.acwing.com/solution/content/127/
AC代码
class Solution {
public:
bool isMatch(string s, string p) {
int n = s.size(), m = p.size();
s = ' ' + s, p = ' ' + p;
vector<vector<bool>> f(n + 1, vector<bool>(m + 1));
f[0][0] = true;
for (int i = 0; i <= n; i ++)
{
for (int j = 1; j <= m; j ++)
{
if (p[j] == '*')
{
f[i][j] = f[i][j - 1] || (i && f[i - 1][j]);
}
else
{
f[i][j] = (s[i] == p[j] || p[j] == '?') && i && f[i - 1][j - 1];
}
}
}
return f[n][m];
}
};
LeetCode 45. 跳跃游戏 II
题目类型
- 贪心算法
- 数组
题目链接
思路
私以为这道题代码简单，难度不低
参考大佬题解：https://leetcode.cn/problems/jump-game-ii/solution/45-by-ikaruga/
AC代码1
class Solution {
public:
int jump(vector<int>& nums) {
int ans = 0;
int start = 0;
int end = 1;
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;
ans ++;
}
return ans;
}
};
AC代码2
class Solution {
public:
int jump(vector<int>& nums) {
int end = 0;
int maxPos = 0;
int ans = 0;
for (int i = 0; i < nums.size() - 1; i ++)
{
maxPos = max(maxPos, i + nums[i]);
if (i == end)
{
end = maxPos;
ans ++;
}
}
return ans;
}
};
LeetCode 46. 全排列
题目类型
- dfs
题目链接
思路
简单dfs问题，参考我之前一篇dfs相关文章，第一道例题类似题
https://alexjakin.github.io/2022/06/10/suanfajichupiandfshebfsjiqijingdianxiti/
AC代码
class Solution {
public:
int n;
vector<vector<int>> ans;
vector<int> path;
vector<bool> st;
vector<vector<int>> permute(vector<int>& nums) {
n = nums.size();
path = vector<int> (n);
st = vector<bool> (n);
dfs(nums, 0);
return ans;
}
void dfs(vector<int> &nums, int u)
{
if (u == n)
{
ans.push_back(path);
return ;
}
for (int i = 0; i < n ; i ++)
{
if (!st[i])
{
st[i] = true;
path[u] = nums[i];
dfs(nums, u + 1);
st[i] = false;
}
}
}
};
LeetCode 47. 全排列 II
题目类型
- dfs
题目链接
思路
参考y总的题解
https://www.acwing.com/solution/content/126/
AC代码
class Solution {
public:
int n;
vector<vector<int>> ans;
vector<int> path;
vector<bool> st;
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
n = nums.size();
path = vector<int> (n);
st = vector<bool> (n);
dfs(nums, 0);
return ans;
}
void dfs(vector<int> &nums, int u)
{
if ( u == n )
{
ans.push_back(path);
return ;
}
for (int i = 0; i < n; i ++)
{
if (!st[i])
{
if (i && nums[i - 1] == nums[i] && !st[i - 1]) continue;
st[i] = true;
path[u] = nums[i];
dfs(nums, u + 1);
st[i] = false;
}
}
}
};
LeetCode 48. 旋转图像
题目类型
- 技巧型
题目链接
思路
看看LeetCode题解就好，先斜翻转，再竖翻转
AC代码
class Solution {
public:
static void swap(vector<vector<int>>& matrix, int x1, int y1, int x2, int y2)
{
int t = matrix[x1][y1];
matrix[x1][y1] = matrix[x2][y2];
matrix[x2][y2] = t;
}
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int i = 0; i < n; i ++)
for (int j = 0; j < i; j ++)
swap(matrix, i, j, j, i);
for (int i = 0; i < n; i ++)
for (int j = 0; j < n / 2; j ++)
swap(matrix, i, j, i, n - j - 1);
}
};
LeetCode 49. 字母异位词分组
题目类型
- 哈希表
题目链接
思路
使用哈希表映射即可，每个组的异位词对字符排好序之后相等，例如abc、bac、cba排好序之后是abc，将其映射放入同一个组即可
例如hash[‘abc’] = [‘abc’, ‘bac’, ‘cba’]
AC代码
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> hash;
for (string& str : strs)
{
string t = str;
sort(str.begin(), str.end());
hash[str].push_back(t);
}
vector<vector<string>> res;
for (auto& item : hash)
{
res.push_back(item.second);
}
return res;
}
};
LeetCode 50. Pow(x, n)
题目类型
- 快速幂
题目链接
思路
参考大佬题解
https://leetcode.cn/problems/powx-n/solution/50-powx-n-kuai-su-mi-qing-xi-tu-jie-by-jyd/
AC代码
class Solution {
public:
double myPow(double x, int n) {
typedef long long LL;
LL k = abs(LL(n));// 注意 n 为 INT_MIN时，abs 会爆掉 int。
bool is_minus = n < 0;
double res = 1;
for (; k; k >>= 1)
{
if (k & 1) res *= x;
x *= x;
}
if (is_minus) return 1/res;
return res;
}
};
