Leetcode刷题记录（不分类版）

Last updated on October 11, 2024 pm

尽量保证每天至少做两题，保持手感。累计11题。

2024/5/24

（1）接雨水

42. 接雨水 - 力扣（LeetCode）

记得第一次看到这题，两眼一黑就没管了。昨晚睡觉时突然想到，想了半天，今天写的时候也没写出来。总结错误原因是：1、想到了要记录左边最大值和右边最大值，但是记录的非常笨拙；2、记录的最大值不是真的最大值，而是每个凹陷两边的最大值。还是题感不够以及思路不够灵活。刚好这道题用到的很多方法是我不会的，遂记录。

方法一：

（已超时）分别记录高度为1、2、3……等这一行能接多少雨水。需要遍历两层，记录当前列的左边和右边是否有值，若有则这一块可以接到雨水。时间复杂度O(n2);

方法二：

动态规划：1、用两个数组leftmax[]和rightmax[]分别记录某个位置左边高度的最大值和右边高度的最大值。两个最大值中小的那个减去它的高度就是这一列能接到的雨水量；2、如何得到两个数组的值？（动态规划）leftmax[0]=h[0]，rightmax[n-1]=h[n-1]。从左向右遍历，得到等式：left[ i ]=max( left[ i-1],h[ i] ) , 从右向左遍历，得到right[i]=max(right[ i+1],h[ i ])；

时间复杂度：O（n），空间复杂度：O（n）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int left[20004],right[20004];  
int cnt,tmp;
int trap(vector<int>& h) {
   int n=h.size();
   left[0]=h[0],right[n-1]=h[n-1];
   for(int i=1;i<n;i++){
      left[i]=max(left[i-1],h[i]);
      right[n-i-1]=max(right[n-i],h[i]);
   }
   for(int i=1;i<n-1;i++){
      tmp=min(left[i],right[i]);
      cnt+=tmp-h[i];
   }
   return cnt;
}
方法三：

单调栈：单调栈内存储的是下标。如果该下标高度小于栈顶，入栈；否则开始计算两个下标之间可以接的雨水量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int cnt;
int trap(vector<int>& h) {
   stack<int> r;
   for(int i=0;i<h.size();i++){
      while(!r.empty()&&h[r.top()]<h[i]){
         int cur=r.top();
         r.pop();
         if(r.empty())
            break;
         cnt+=(min(h[r.top()],h[i])-h[cur])*(i-r.top()-1);
      }
      r.push(i);
   }
   return cnt;
}

2024/5/28

（1）合并两个有序数组（字符串、数组）

88. 合并两个有序数组 - 力扣（LeetCode）

方法一：

直接合并然后排序（时间复杂度O(m+n)log(m+n)）

方法二：

逆序双指针：m、n分别指向两个数组最后一个（不是0的）元素，然后每次作比较，将大的数字放在数组的最后一个位置，相应指针和位置前移。

1
2
3
4
5
6
7
8
9
10
11
12
13
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
	 int i=m+n-1;
   while(n>0){
      if(m>0&&nums1[m-1]>nums2[n-1]){
         nums1[i--]=nums2[m-1];
         m--;
      }
      else{
			nums1[i--]=nums2[n-1];
         n--;         
      }
   }
}

2024/5/29

（1）长度最小的子数组（二分、前缀和、滑动窗口）

209. 长度最小的子数组 - 力扣（LeetCode）

方法一：暴力法（超时）
方法二：

前缀和+二分查找：在想到使用前缀和之后，需要使用二分查找找到想要的下标才能使时间复杂度下降。而在每个语言中都已经有内置的二分查找函数，找到大于或者等于某个数的第一个位置。c++：lower_bound。时间复杂度：nlog(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int minSubArrayLen(int target, vector<int>& nums) {
	int n=nums.size();
   if(n==0)
      return 0;
   int ans=INT_MAX;   //表示最大的整数，在后面的比较时有用
   vector<int> sum(n+1,0);   //sum[i]存储的是nums[0]到nums[i-1]的和，因此要设置n+1的长度，sum[0]=0,sum[1]=nums[0]……
   for(int i=1;i<=n;i++)
      sum[i]=sum[i-1]+nums[i];   //计算前缀和
   for(int i=1;i<=n;i++){
      int s=target+sum[i-1];   //将目标加上当前坐标的前缀和，方便查找（i-1为子串第一个坐标）
      auto bound=lower_bound(sum.begin(),sum.end(),s);  //注意查找得到的是位置
      if(bound!=sum.end())
         ans=min(ans,bound-sum.begin()-(i-1));  
   }
   return ans==INT_MAX?0:ans;
}
方法三：

滑动窗口：设置左右指针表示窗口的两边，保证窗口内元素之和满足要求时，左指针右移，不断保存左右指针相差最小的那个值。当窗口不符合要求时，右指针继续右移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int min(int target,vetor<int> num){
   int n=num.size();
   if(!n)  return 0;
   int ans=INT_MAX,l=0,r=0,sum=0;
   while(r<n){
      sum+=num[r];
      while(sum>=target){
         ans=min(ans,r-l+1);
         sum-=num[l];
         l++;
      }
      r++;
   }
   return ans==INT_MAX?0:ans;
}

（2）搜索二维矩阵（二分法）

方法一：两次二分查找
1
2
3
4
5
6
7
bool searchMatrix(vector<vector<int>>& num, int t) {
	auto row=upper_bound(num.begin(),num.end(),t,[](const int b,const vector<int> &a){return b<a[0];});  //找到第一个元素大于给定元素的那一行
   if(row==num.begin())  return false;
   --row;
   return binary_search(row->begin(),row->end(),t);
   //二分查找函数，找到等于给定元素的下标，找不到就返回false
}
方法二：一次二分查找（假想成一维数组）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool searchMatrix(vector<vector<int>>& num, int t) {
   int m=num.size(),n=num[0].size;   //得到行数(m)和列数(n)
   int low=0,high=m*n-1;
   while(low<high){
      int mid=(high-low)/2+low;  //防止溢出
      int x=num[mid/n][mid%n];   //注意是n！！！不是m
      if(x<t)
         low=mid+1;
      else if(x>t)
         high=mid-1;
      else
         return true;
   }
   return false;
}

（3）打家劫舍（一维动态规划）

198. 打家劫舍 - 力扣（LeetCode）

第一步：定义子问题：从k间房屋中可以偷到的最大金额

第二步：列出递推关系。题目要求不能够偷两间相邻的房屋，因此偷k间房屋就有了两个选择，f[k]=max( f[k-1] , f[k-2]+num[k-1] )；

第三步：写出已知值。f[0]=0,f[1]=num[0];

1
2
3
4
5
6
7
8
9
10
int rob(vector<int>& num){
   int n=num.size();
   if(!n)  return 0;
   vector<int> add(n+1,0);
   add[1]=num[0];
   for(int i=1;i<n;i++){
      add[i+1]=max(add[i],add[i-1]+num[i]);
   }
   return add[n];
}

第四步：空间优化。我们发现每次都只需要用到数组的最后两个值，因此用两个整数保存这两个值即可，不需要多余空间。

1
2
3
4
5
6
7
8
int rob(vector<int>& num){
   int pre=0,cur=0,ans;
   for(int i:num){
      ans=max(pre+i,cur);
      pre=cur;
      cur=ans;
   }
}

（4）三角形最小路径和（二维动态规划）

120. 三角形最小路径和 - 力扣（LeetCode）

方法一：动态规划（自底向上）(不改动原数组)

设dp[i] [j]表示第i行第j个元素到最后一行的最短路径，则可以得到状态转移方程： dp[i] [j]=min(dp[i+1] [j] , dp[i+1] [j+1]) +triangle[i] [j]，则dp[0] [0]为所需值。

1
2
3
4
5
6
7
8
9
10
int minimumTotal(vector<vector<int>>& triangle) {
   int n=triangle.size();
   int[][] dp=new int[n+1][n+1];
   for(int i=n-1;i>=0;i--){
      for(int j=0;j<=i;j++){
         dp[i][j]=min(dp[i+j][j],dp[i+1][j+1])+triangle[i][j];
      }
   }
   return dp[0][0];
}
方法二：动态规划（空间优化）

我们会发现每次只需要用到两个先前值，因此不需要用到二维数组。dp数组不断保存每一行每个值遍历到最后一行的最短路径之和。

1
2
3
4
5
6
7
8
9
10
int minimumTotal(vector<vector<int>>& triangle) {
   int n=triangle.size();
   int[] dp=new int[n+1];
   for(int i=n-1;i>=0;i--){
      for(int j=0;j<=i;j++){
         dp[j]=min(dp[j],dp[j+1])+triangle[i][j];
      }
   }
   return dp[0];
}

2024/5/30

（1）最小路径和（二维动态规划）

64. 最小路径和 - 力扣（LeetCode）

跟昨天做的题思路很像（相当于偷个小懒hhh），也是丝滑地ac了，就是没有空间优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        int dp[205][205];
        dp[m-1][n-1]=grid[m-1][n-1];
        for(int i=m-2;i>=0;i--)
            dp[i][n-1]=dp[i+1][n-1]+grid[i][n-1];
        for(int i=n-2;i>=0;i--)
            dp[m-1][i]=dp[m-1][i+1]+grid[m-1][i];  
        for(int i=m-2;i>=0;i--){
            for(int j=n-2;j>=0;j--){
                dp[i][j]=min(dp[i+1][j],dp[i][j+1])+grid[i][j];
            }
        }
        return dp[0][0];
    }
};

试着空间优化一下：(分类讨论地好狗屎，但是不知道怎么分情况更简单了。。。)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int minPathSum(vector<vector<int>>& grid) {
   int m=grid.size(),n=grid[0].size();
   vector<int> dp(n,0);
   dp[0]=grid[0][0];
   for(int i=0;i<m;i++){
      for(int j=0;j<n;j++){
         if(i==0&&j!=0)
            dp[j]=dp[j-1]+grid[i][j];
         else if(j==0&&i!=0)
            dp[j]=dp[j]+grid[i][j];
        	else if(i!=0&&j!=0)
            dp[j]=min(dp[j-1],dp[j])+grid[i][j];
      }
   }
   return dp[n-1];
}

（2）不同路径（二维动规、障碍物）

63. 不同路径 II - 力扣（LeetCode）

方法一：动规数组存储该位置的路径和，遇到障碍物该位置路径数变为零。

AC，但是空间复杂度有点高，而且在初始化的时候容易犯错。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
	int m=obstacleGrid.size(),n=obstacleGrid[0].size();
   int dp[105][105];
   dp[0][0]=obstacleGrid[0][0]==1?0:1;
   for(int i=1;i<m;i++)
      dp[i][0]=dp[0][0];
   for(int i=1;i<n;i++)
      dp[0][i]=dp[0][0];
   for(int i=1;i<m;i++){
      for(int j=1;j<n;j++){
         if(obstacleGrid[i][j])
            dp[i][j]=0;
         else
            dp[i][j]=dp[i-1][j]+dp[i][j-1];
      }
   }
   return dp[m-1][n-1];
}
方法二：空间优化（滚动数组）
1
2
3
4
5
6
7
8
9
10
11
12
13
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
   int m=obstacleGrid.size(),n=obstacleGrid[0].size();
   vector<int> dp(n,0);
   dp[0]=obstacleGrid[0][0]==1?0:1;
   for(int i=0;i<m;i++){
      for(int j=0;j<n;j++){
         if(obstacleGrid[0][0])
            dp[j]=0;
         else if(j>0)
            dp[j]+=dp[j-1];
      }
   }
}

（3）最长回文子串

5. 最长回文子串 - 力扣（LeetCode）

方法一：中心扩展法

分为两种情况：1、回文串长度是奇数；2、回文串长度是偶数。因此从中心向外扩展时也就有两种情况：1、中心是当前值；2、中心是当前值与右边值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
string longestPalindrome(string s) {
   int n=s.size(),pre=0,maxL=0;
   for(int i=0;i<n;i++){
      int l=i-1,r=i;
      for(;l>=0&&r<n&&s[l]==s[r];l--,r++);
      if(maxL<r-l+1){
         maxL=r-l+1;
         pre=l+1;
      }
      l=i-1,r=i+1;
      for(;l>=0&&r<n&&s[l]==s[r];l--,r++);
      if(maxL<r-l+1){
         maxL=r-l+1;
         pre=l+1;
      }
   }
   return s.substr(pre,maxL);
}

方法二：动态规划

不知道为什么力扣不能完全通过……不理解

理解了，因为没有初始化为false啊啊啊啊我要气死了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
string longestPalindrome(string s) {
    int len=s.length();
    int left=0,right=0,res=0;//记录左右边界和右-左的长度
    bool dp[1005][1005]={false};
    for(int i=len-1;i>=0;i--){
        for(int j=i;j<len;j++){//j=i这步就将每个单个字符dp赋为了true
            if(s[i]==s[j]&&(j - i <= 1 || dp[i + 1][j - 1])){
                dp[i][j] = true;
                if(j-i>res){
                    res=j-i;//res记得也得更新！
                    left=i;
                    right=j;
                }
            }
        }
    }
    return s.substr(left,res+1);//左闭右开
}

（4）删除有序数组中的重复项 II（双指针）

80. 删除有序数组中的重复项 II

方法一：双指针（？）

自己写的，有点丑陋……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int removeDuplicates(vector<int>& nums) {
        if(nums.size()<3)
            return nums.size();
        int i=0;
        while(i<nums.size()-1){
            int j=i+2;
            while(j<nums.size()&&nums[i]==nums[i+1]&&nums[i]==nums[j]){
                nums.erase(nums.begin()+j);
            }
            if(nums[i]==nums[i+1])
                i+=2;
            else
                i+=1;
        } 
        return nums.size();       
    }
方法二：单指针

首先，定义一个指针 i，用来记录不重复元素的位置。

遍历数组 nums，对于数组中的每个元素 num：

  • 如果 i 小于 2（即数组前两个元素），或者当前元素 num 大于 nums[i - 2]（说明当前元素和前两个元素不相同），则将当前元素 num 赋值给 nums[i]，并将指针 i 向后移动一位，相当于将当前元素保留下来。
  • 如果当前元素 num 和 nums[i - 2] 相同（说明当前元素已经重复出现两次以上），则不做任何操作，直接继续遍历下一个元素。

最后返回指针 i，即为删除重复元素后数组的新长度。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
   public int removeDuplicates(int[] nums) {
       int i = 0;
       for (int num : nums) {
           if (i < 2 || num > nums[i - 2]) {
               nums[i++] = num;
           }
       }
       return i;
   }
}

（5）买卖股票的最佳时机

121. 买卖股票的最佳时机

自己写的代码太丑陋了而且还有bug（不知道为啥），这是chatgpt写的，跟我一样的思路怎么就这么简洁呢呃呃呃，怎么不算天才呢

我用了两个数组去记录……左边最小值和右边最大值，怎么不算愚蠢呢……

1
2
3
4
5
6
7
8
9
int maxProfit(vector<int>& prices) {
    int minPrice = INT_MAX;
    int maxProfit = 0;
    for (int price : prices) {
        minPrice = min(minPrice, price);   //记录到目前位置的股票价格最小值
        maxProfit = max(maxProfit, price - minPrice);  //维护利润最大值
    }
    return maxProfit;
}

2024/5/31

（1）买卖股票的最佳时机||（动规、贪心）

122. 买卖股票的最佳时机 II - 力扣（LeetCode）

方法一：直接求解/贪心

按照直接求解的思路，如果要使利润最大化，只需要把股票价格看成折线图，计算每一次上升的利润。如果把距离看为1，就看每两天是否有利润，只要有就增加利润值。

按照贪心的思路，由于股票的购买没有限制，因此相当于找到若干个不相交的区间，使区间内利润和最大。如果区间长度为1，也就等同于了刚刚的思路。

1
2
3
4
5
6
int maxProfit(vector<int>& prices) {
	int maxp=0,n=prices.size();
   for(int i=0;i<n-1;i++)
     	maxp+=max(0,prices[i+1]-prices[i]);  //省去了每次判断两个股票值的大小
   return maxp;
}
方法二：动态规划

虽然知道可以动态规划但是就是想不到怎么规划！！！

首先要设置状态，可以设置dp[i] [0]表示第i天交易完时手里没有股票的最大利润，dp[i] [1]则表示手里有股票。下面就可以列状态转移方程。（一开始真的想复杂了，所以完全不知道这怎么转移）对于dp[i] [0]，有两种情况：1、dp[i] [0]=dp[i-1] [0]（和前一天保持一致） 2、dp[i] [0]=dp[i-1] [1]+prices[i]（前一天有股票，今天卖出，获得今天的收益，不用管成本）对于dp[i] [1]：1、dp[i] [1]=dp[i-1] [1]；2、dp[i] [1]=dp[i-1] [0]-prices[i]

遍历结束后，我们手中有两个值，dp[n-1] [0]和dp[n-1] [1]，显然最后手里没有股票的话利润才是最大的，因此应该返回dp[n-1] [0]。

对于这道题也可以空间优化，因为每次都只是用到了前一天的两个值而已。

1
2
3
4
5
6
7
8
9
10
11
int maxProfit(vector<int>& prices) {
	int n=prices.size(),dp0,dp1,newdp0,newdp1;
   dp0=0,dp1=-prices[0];
   for(int i=1;i<n;i++){
      newdp0=max(dp0,dp1+prices[i]);
      newdp1=max(dp1,dp0-prices[i]);
      dp0=newdp0;
      dp1=newdp1;
   }
   return dp0;
}

（2）三数之和（双指针）

15. 三数之和 - 力扣（LeetCode）

方法一:自己写的（我也想写双指针法？？）

通过了308/313个用例呜呜呜我哭死。最后是时间超了，我的代码好丑陋……感觉超时间应该是因为用到了查找函数，有点丑陋。。

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
vector<vector<int>> threeSum(vector<int>& nums) {
        int n=nums.size(),cur;
        vector<vector<int>> num;
   	  sort(nums.begin(),nums.end());
        if(n<3||nums[0]>0||nums[n-1]<0)
            return num;
        vector<int> tmp;
        for(int i=0;i<n-2;i++){
            if(nums[i]>0)
                break;
           if(i>0&&nums[i]=nums[i+1])
              continue;
            for(int j=i+1;j<n-1;j++){
                cur=nums[i]+nums[j];
                cur=0-cur;
                auto it=find(nums.begin()+j+1,nums.end(),cur);
                if(it!=nums.end()){
                    tmp={nums[i],nums[j],nums[it-nums.begin()]};
                    if(num.empty()||find(num.begin(),num.end(),tmp)==num.end())
                    num.push_back(tmp);
                }
            }
        }
        return num;
    }
方法二：（相向）双指针法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<vector<int>> threeSum(vector<int>& nums) {
   sort(nums.begin(),nums.end());  //第一步排序
   vector<vector<int>> num;    
   int n=nums.size();   //我好不容易严谨一会上来就判断n是不是小于3，结果题目写了n>=3
   if(nums[n-1]+num[n-2]+nums[n-3]<0)  return num;   //最大三数和都小于0了
   for(int i=0;i<n-2;i++){
      int x=nums[i];
      if(i&&x=nums[i-1])   break;  //跳过重复元素
      if(nums[i]+num[i+1]+nums[i+2]>0)   break;   //三数之和已经大于0
      if(nums[n-1]+num[n-2]+nums[i]<0)   continue;  //和最大两个数相加都大于0
      int j=i+1,k=n-1;   //一前一后两个指针
      while(j<k){
         int t=x+nums[j]+nums[k];
         if(t>0)  k--;
         else if(t<0)  s--;
         else{
            num.push_back{x,nums[j],nums[k]};
            for(++j;j<k&&nums[j]==nums[j-1];++j);
            for(--k;j<k&&nums[k]==nums[k+1];--k);  //跳过重复的数字
         }
      }
   }
   return num;
}

（3）买卖股票的最佳时机|||（k次）(动态规划)

188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

我是真的没有想到还有|||……后面好像还有IV。今天下午都要买卖股票啦，哈哈哈（苦笑）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int maxProfit(vector<int>& prices) {
	const int inf=INT_MIN/2;  //除以二是为了防止溢出
   int n=prices.size();
   int buy1=inf; //第一次买后的最大收益，初始值设置为最低
   int sell1=0;  //第一次卖掉后的最大收益
   int buy2=inf;
   int sell2=0;
   for(int i=0;i<n;i++){  //变量更新的顺序可以随意调换
      sell1=max(sell1,buy1+prices[i]);
      buy1=max(buy1,-prices[i]);
      sell2=max(sell2,buy2+prices[i]);
      buy2=max(buy2,sell1-prices[i]);
   }
   return sell2;
}

（4）买卖股票的最佳时期（k次）

188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int maxProfit(int k, vector<int>& prices) {
	int n=prices.size();
   k=min(k,n/2);
   vector<int> buy(k+1);
   vector<int> sell(k+1);
   for(int i=0;i<n;i++){
      buy[i]=INT_MIN/2;
      sell[i]=0;
   }
   for(int i=0;i<n;i++){
      for(int j=1;j<=k;j++){
         buy[j]=max(buy[j],sell[j-1]-prices[i]);
         sell[j]=max(sell[j],buy[j-1]+prices[i]);
      }
   }
   return sell[k];
}

（5）阶乘后的0（数学）

172. 阶乘后的零 - 力扣（LeetCode）

这居然是中等？？你的中等我的中等好像不一样？？自己ac了但是贴个复杂度更小的解法

1
2
3
4
5
6
7
8
int trailingZeroes(int n) {
   int ans=0;
   while(n){
      n=n/5;
      ans+=n;
   }
   return ans;  //就是~这么简单
}

2024/6/1

休息一天。。头疼

2024/6/2

（1）直线上最多的点数

149. 直线上最多的点数 - 力扣（LeetCode）

枚举直线+哈希表：外层循环遍历每一个点，求出跟该点在同一条直线上的点的最大值，然后再得到所有点中的最大值。题目中用字符串保存斜率，求出x坐标差和y坐标差后，求出他们的最大公约数，分别除去再存储，可以有效的维护相同斜率的哈希表，也可以很好地使x坐标差为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 maxPoints(vector<vector<int>>& points) {
        int n = points.size(), ans = 1;
        for (int i = 0; i < n; i++) {
            map<string, int> map;  //每次循环都要重新构造哈希表
            int maxv = 0;
            for (int j = i + 1; j < n; j++) {
                int x1 = points[i][0], y1 = points[i][1], x2 = points[j][0], y2 = points[j][1];
                int a = x1 - x2, b = y1 - y2;
                int k = gcd(a, b);
                string key = to_string(a / k) + "_" + to_string(b / k);
                map[key]++;
                maxv = max(maxv, map[key]);
            }
            ans = max(ans, maxv + 1);
        }
        return ans;
    }// 求最大公约数的代码
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
};

求最小公倍数的代码：

1
2
3
4
5
6
int lcm(int a, int b) {
    // 先求最大公约数
    int num = gcd(a, b);
    // 利用最大公约数求最小公倍数
    return (a * b) / num;
}

（2）零钱兑换（一维动规）

322. 零钱兑换 - 力扣（LeetCode）

很好的题目，使我小脑萎缩。

1
2
3
4
5
6
7
8
9
10
int coinChange(vector<int>& coins, int amount) {
   int MAX=amount+1;
   vector<int> dp(amount+1,MAX);  //若最后dp(amount)为max证明凑不到
   dp[0]=0;
   for(int i=0;i<=amount;i++)
      for(int j=0;j<(int)coins.size();++j)
         if(coins[j]<=i)
            dp[i]=min(dp[i],dp[i-coins[j]]+1);
   return dp[amount]==MAX?-1:dp[amount];
}
C++
#C++ #Leetcode
Leetcode刷题记录（不分类版）
http://example.com/2024/05/24/Leetcode刷题记录（不分类版）/
Author
Yaodeer
Posted on
May 24, 2024
Licensed under