date: 2024-10-21 tag：贪心算法
题解：
定义了两个变量：totalgas和totalcost,表示总获得的油量和消耗的油量，初始为0如果totalgas小于totalcost则表示不能跑一圈，返回-1;
用currentgas表示当前的油量，startindex表示开始的加油站下标。
遍历两个数组，记录获得油量和消耗的油量，currentgas+=gas[i]-cost[i]表示当前的油量
如果currentgas<0说明从 startindex 到当前加油站无法到达下一个加油站，因此将 startindex 更新为当前加油站的下一个索引，并重置 currentgas 为 0。
返回结果，如果满足totalgas<totalcost,则返回startindex的值，否则返回-1;
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int totalgas=0,totalcost=0;
int currentgas=0,startindex=0;
for(int i=0;i<gas.size();i++)
{
totalcost+=cost[i];
totalgas+=gas[i];
currentgas+=gas[i]-cost[i];
if(currentgas<0)
{
startindex=i+1;
currentgas=0;
}
}
return (totalgas<totalcost)? -1:startindex;
}
};
|
date: 2024-10-21 tag:贪心算法
题解
遍历nums,用to_string()函数转化为字符串
1
2
3
| sort(str.begin(),str.end(),[](const string&a,const string&b){
return a+b>b+a;
});
|
使用Lambda表达式自定义排序，比较拼接后的字符串：
a+b和b+a表示拼接字符串，a+b>b+a表示比较拼接字符串的字典序
如果 a + b 大于 b + a，这意味着在拼接后的形式中，a 排在 b 前面，应该在排序时将 a 放在 b 前面。
排序后判断字符串第一位为0，则结果为零
遍历排序字符串加到res后
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
string largestNumber(vector<int>& nums) {
vector<string>str;
for(auto num:nums)
{
str.push_back(to_string(num));
}
sort(str.begin(),str.end(),[](const string&a,const string&b){
return a+b>b+a;
});
if(str[0]=="0")return "0";
string res;
for(auto i:str)
{
res+=i;
}
return res;
}
};
|
date:2024-10-21 tag:贪心算法 动态规划
题解
用maxreach代表能够到达的最远下标，初始为0;
用for循环比较每个位置的下标i和maxreach,i>maxreach说明无法到达该位置，直接返回false。
更新maxreach,i+nums[i]表示在位置i增加步数后达到的位置,比较得出最远位置
此时maxreach大于最大下标，返回true
如果遍历完所有元素后都没有返回 true，则说明可以不能到达最后一个位置，返回 false。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
bool canJump(vector<int>& nums) {
int maxreach=0;
for(int i=0;i<nums.size();i++)
{
if(maxreach<i)return false;
maxreach=max(maxreach,i+nums[i]);
if(maxreach>=nums.size()-1)return true;
}
return false;
}
};
|
date:2024-10-21 tag:贪心算法 动态规划
题解
每次遍历更新能够跳到的最远位置maxreach,只有跳到当前跳跃的边界时，增加跳跃书，更新边界。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int jump(vector<int>& nums) {
int maxreach=0,count=0,end=0;
for(int i=0;i<nums.size()-1;i++)
{
maxreach=max(maxreach,i+nums[i]);
if(i==end)
{
count++;
end=maxreach;
}
}
return count;
}
};
|
date:2024-10-22 tag:动态规划
题解
构建amount+1大小的数组，默认值为amount+1表示默认情况下无法达到的硬币数。dp[i]表示金额i的最小硬币数目。
从金额1开始遍历amount,逐步计算出每个金额所需的最少硬币个数。
遍历硬币，对于i，如果满足i>=count,即表示当前金额i是可以用 coin 减去后得到的：
dp[i]=min(dp[i],d[i-coin]+1);更新状态转移方程
对于结果如果dp[amount]仍为初始值，返回-1。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int>dp(amount+1,amount+1);
dp[0]=0;
for(int i=1;i<=amount;++i){
for(int coin:coins)
{
if(i>=coin){
dp[i]=min(dp[i],dp[i-coin]+1);
}
}
}
return dp[amount]==amount+1?-1:dp.back();
}
};
|
date:2024-10-23 tag:哈希表
题解
把hour[i]+hour[j],hour[i]转化成一天24的余数hour[i]%24,hour[j]为(24-(hour[i]%24))%24
count数组，统计hour[i]%24出现的次数。
遍历hours，remain表示hour[i],remain_target表示hour[j],
累加满足条件的对数。
并更新remain出现的对数+1;
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
long long countCompleteDayPairs(vector<int>& hours) {
long long res=0;
vector<int>count(24,0);
for(int hour:hours)
{
int remain=hour%24;
int remain_target=(24-remain)%24;
res+=count[remain_target];
count[remain]++;
}
return res;
}
};
|
date:2024-10-24 tag:数组
题解
用count记录胜利的次数，winner_index表示玩家的编号并初始化为0.skills[winner_index]=skills[0];
遍历skills，如果skills[winner_index]>skills[i],增加胜利数count，否则将i作为胜利玩家的下标，且以及count胜利数为1。
count=k时，直接返回下标即为结果。
如果遍历结束时，没有玩家在 k 场比赛内成为赢家，则返回最后的胜者索引 current_winner_index。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int findWinningPlayer(vector<int>& skills, int k) {
int count=0,winner_index=0;
skills[winner_index]=skills[0];
for(int i=1;i<skills.size();++i){
if(skills[winner_index]>skills[i]){
count++;
}
else if(skills[winner_index]<skills[i]){
count=1;
winner_index=i;
}
if(count==k)return winner_index;
}
return winner_index;
}
};
|
date:2024-10-24 tag:动态规划
题解
构建状态转移方程dp:由于一次可以向上爬一个或者两个台阶，当前台阶花费dp[i]应该是dp[i-1]+cost[i-1]上一阶或者上上一阶dp[i-2]+cost[i-2]最下的那个
即dp[i]=min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1]);
代码
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();
vector<int>dp(n+1,0);
for(int i=2;i<=n;++i)
{
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
return dp[n];
}
};
|
date:2024-10-24 tag:动态规划
题解
先处理nums数组长度为0.1.2时，为2时偷最多的那个
然后构建动态规划方程，初始化dp[0]为nums[0],dp[1]表示偷两个中最大的那个。
对于一个dp[i]表示偷到下标为i时候的最大值，前面为dp[i-1]由题意不能偷，dp[i-2]可以偷.
构造动态规划方程：dp[i]=max(dp[i-1],dp[i-2]+nums[i])
返回偷到最后一个房子的最大金额。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int rob(vector<int>& nums) {
int n=nums.size();
if(n==0)return 0;
if(n==1)return nums[0];
if(n==2)return max(nums[0],nums[1]);
vector<int>dp(n+1,1);
dp[0]=nums[0];
dp[1]=max(nums[0],nums[1]);
for(int i=2;i<n;++i){
dp[i]=max(nums[i]+dp[i-2],dp[i-1]);
}
return dp[n-1];
}
};
|
date:2024-10-25 tag:动态规划
题解
这题和上面的小偷的题相似，小偷是偷到i时，考虑是偷i-1和i-2+num[i]哪个大，选择这家i不偷，偷前一家，或者偷这家
这题变成了选择一个数字，删除并获得点数，同时需要删除值为nums[i]-1和nums[i]+1,所以需要比较是 选择数x 和x+1,x-1的大小；
但是原先的数组是无序的，不知道x-1和x-2数的值。
我们记录下max_val max_val=*max_element(nums.begin(),nums.end());数组的最大值。
创建一个数组points，大小为max_val,来记录每个point[num]为数字为num的和
遍历nums数组，points[num]+=num
创建动态规划数组dp(max_val,0)大小为max_val,dp[i]表示选择数字i时的最大得分
初始化 dp[1] = points[1]，因为只选择 1 时的最大点数就是 points[1]。
构建动态规划方程，dp[i]=max(dp[i-1],dp[i-2]+points[i]);
dp[i-1] 表示不选 i，dp[i-2] + points[i] 表示选 i。
返回dp[max_val]表示达到最大值时的最大点数。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
if(nums.empty())return 0;
int max_val=*max_element(nums.begin(),nums.end());
vector<int>points(max_val+1,0);
for(int num:nums){
points[num]+=num;
}
vector<int>dp(max_val+1,0);
dp[1]=points[1];
for(int i=2;i<=max_val;++i){
dp[i]=max(dp[i-1],dp[i-2]+points[i]);
}
return dp[max_val];
}
};
|
date:2024-10-25 tag:动态规划
题解
动态规划方程：dp[i][j]的方案数是上一步的位置dp[i-1][j]和dp[i][j-1]之和。
初始化边界：如果这一行或一列没有障碍物，那么路径方案数都为1，如果有障碍物，障碍物自己和之后后为0，不需要再设置为1，直接break跳出循环
在不是边界的位置遇到1，表示不能到达，直接设为0，否则这个位置就是dp[i-1][j]和dp[i][j-1]之和
结果返回dp[m-1][n-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
27
28
29
30
| class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m=obstacleGrid.size(),n=obstacleGrid[0].size();
vector<vector<int>>dp(m,vector<int>(n,0));
for(int i=0;i<m;++i){
if(obstacleGrid[i][0]==1){
break;
}
dp[i][0]=1;
}
for(int j=0;j<n;++j){
if(obstacleGrid[0][j]==1){
break;
}
dp[0][j]=1;
}
for(int i=1;i<m;++i){
for(int j=1;j<n;++j){
if(obstacleGrid[i][j]==1){
dp[i][j]=0;
}
else{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
};
|
date:2024-10-26 tag:回溯
题解
创建数组current表示子集，result表示结果。
回溯函数，每次将当前current子集加入到result中，
遍历nums，将当前元素加入到current中，继续调用backtrack函数以继续生成子集，
回溯时current.pop()撤回对当前元素的选择，确保当前组合完成后返回原始状态
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<int>current;
vector<vector<int>>result;
backtrack(nums,0,current,result);
return result;
}
void backtrack(vector<int>&nums,int start,vector<int>¤t,vector<vector<int>>&result){
result.push_back(current);
for(int i=start;i<nums.size();++i){
current.push_back(nums[i]);
backtrack(nums,i+1,current,result);
current.pop_back();
}
}
};
|
date:2024-10-26 tag:双指针
题解
用两个指针i,j来表示两个字符串的开始位置，结束位置分别为n=version1.size(),m=version2.size()
循环遍历，只要字符串还有剩余的字符，就继续遍历，
初始化v1,v2为0，表示已经遍历的字符大小。当还没遇到.时，可以比较.前面的修订号，因为version[i]为0到9的字符，version[i]-'0'可以转化成int类型
列如version1 = "1.01", version2 = "1.001"在遇到.前，都为1，++i,++j继续外循环，此时v1,v2又为0，内循环后都为1。比较v1,v2没有结果，结束外循环，返回0.
代码
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 compareVersion(string version1, string version2) {
int i=0,j=0;
int n=version1.size(),m=version2.size();
while(i<n||j<m){
int v1=0,v2=0;
while(i<n&&version1[i]!='.'){
v1=v1*10+(version1[i]-'0');
++i;
}
while(j<m&&version2[j]!='.'){
v2=v2*10+(version2[j]-'0');
++j;
}
if(v1<v2)return -1;
if(v1>v2)return 1;
++i;
++j;
}
return 0;
}
};
|
date:2024-10-27 tag:并查集
题解
这道题需要使用并查集的方法来判断是否存在环，因为树在添加一条边后会变成有环的无向图。
初始化并查集，parent[i] 表示节点 i 的父节点，最初每个节点都是自己的父节点。
在 find 函数中，递归地找到 x 的根节点，并将路径上所有节点直接指向根节点，
unionset函数中，将两个集合合并，如果根节点不同，把rootx的父节点设为rooty；
然后遍历每条边，检查是否会形成环，find(u)==find(v),表示在同一集合中，直接返回该边
如果不是，将u,v合并为一个集合。
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
| class Solution {
public:
vector<int>parent;
int find(int x){
if(parent[x]!=x){
parent[x]=find(parent[x]);
}
return parent[x];
}
void unionsets(int x,int y){
int rootx=find(x);
int rooty=find(y);
if(rootx!=rooty){
parent[rootx]=rooty;
}
}
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n=edges.size();
parent.resize(n+1);
for(int i=1;i<=n;++i){
parent[i]=i;
}
for(const auto &edge:edges){
int u=edge[0];
int v=edge[1];
if(find(u)==find(v)){
return edge;
}
else{
unionsets(u,v);
}
}
return {};
}
};
|
date:2024-10-28 tag:动态规划
题解
用自底向上的方法解题，动态转移方程：triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1])比较下一层i+1元素行j和j+1最小的，
并同步更新triangle，triangle[0][0]即为从底向上加后的最小值。空间复杂度为o(1)，不需要额外的空间。
代码
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n=triangle.size();
for(int i=n-2;i>=0;--i){
for(int j=0;j<=i;++j){
triangle[i][j]+=min(triangle[i+1][j],triangle[i+1][j+1]);
}
}
return triangle[0][0];
}
};
|
date:2024-10-29 tag:DFS
题解
每个生成的二进制字符串满足：所有的长度为 2 的子字符串中至少包含一个 “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
27
28
| class Solution {
public:
vector<string> validStrings(int n) {
vector<string> ans;
string t;
auto dfs = [&](auto&& dfs, int i) {
if (i >= n) {
ans.emplace_back(t);
return;
}
for (int j = 0; j < 2; ++j) {
if ((j == 0 && (i == 0 || t[i - 1] == '1')) || j == 1) {
t.push_back('0' + j);
dfs(dfs, i + 1);
t.pop_back();
}
}
};
dfs(dfs, 0);
return ans;
}
};
|
date:2024-10-30 tag:贪心
题解
遍历找到相邻的字符奇偶性相同的s[i]%2==s[i-1]%2
要找最小的字符串，即s[i]<s[i-1]，swap交换即可
只能交换一次，直接返回s
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
string getSmallestString(string s) {
int n=s.size();
for(int i=1;i<n;++i){
if(s[i]%2==s[i-1]%2&&s[i]<s[i-1]){
swap(s[i],s[i-1]);
return s;
}
}
return s;
}
};
|
date:2024-10-30 tag:双指针
题解
shuang
从后往前遍历，将遍历结果加入到current中，遇到空格时，将目前的current反转，得到正序的单词。
处理空格的情况，因为字符串中有多个空格，结果中单词之间只能有一个空格，所以每次遇到空格需要判断current是否为空，同时判断res是否为空，因为不能在空字符前加空格。
将反转的current加入到result中
在代码中，最后一个单词需要特别处理，因为循环是基于空格 s[i] == ‘ ‘ 来判断单词结束的。
然而，如果字符串 s 的最后一个字符不是空格，那么最后一个单词在循环结束时还会存留在 current 中，没有被添加到 res。
因此，我们需要在循环后手动处理这个残留的单词。
代码
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
| class Solution {
public:
string reverseWords(string s) {
int n=s.size();
string current,res;
for(int i=n-1;i>=0;--i){
if(s[i]==' '){
reverse(current.begin(),current.end());
if(!current.empty()){
if(!res.empty()){
res+=" ";
}
}
res += current;
current.clear();
continue;
}
else{
current.push_back(s[i]);
}
}
if (!current.empty()) {
if (!res.empty()) {
res += " ";
}
reverse(current.begin(), current.end());
res += current;
}
return res;
}
};
|
date:2024-10-31 tag:回溯
题解
用搜索回溯解题，定义res为结果数组，current为搜索过程中的数组，
剪枝：因为题目没有说candidates是否有序，用sort将数组排序，排序后的回溯如果target-candidates[j]<0相当于下标j之后都不满足，直接跳出循环。
定义int j=i修改target的值，直到满足target后
current.pop_back()回溯上一步操作。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
void backtrack(vector<int>&candidates,int target,vector<int>¤t,int i,vector<vector<int>>&res){
if(target==0){
res.push_back(current);
return;
}
for(int j=i;j<candidates.size();++j){
if(candidates[j]>target)break;
current.push_back(candidates[j]);
backtrack(candidates,target-candidates[j],current,j,res);
current.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
vector<int>current;
vector<vector<int>>res;
backtrack(candidates,target,current,0,res);
return res;
}
};
|
