阅读量:0
目录
一、内容描述
该部分内容主要讲解Leetcode网站中，面试经典150题中1-10题，该部分主要包括动态数组、排序、双指针、贪心和动态规划的内容。每题包括题目描述、示例、提示、部分模拟计算、代码实现和结果展示。
笔者参加过一些算法竞赛，有些微薄见解如下：在学习算法的过程中，我们通常会进行题型分类学习，如动态规划问题，我们首先会做一些相关例题，主要学习什么题适合动态规划解决以及如何设动态规划计算法思路两个方面。但是我们对于未学习的算法有时候初步学习的时候有较大难度，因此笔者认为模拟计算是一个很好的方式，不管是在学习别人的代码还是作为自己代码的演算都有其重要意义。最后，希望读者在学习算法和算法题的过程中，也能够体会到算法的精妙之处，也可以尝试记录自己学习过程，硅步逐印终千里，愿我们一同在学习的路上。
Leetcode刷题网址：面试经典 150 题 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台最经典 150 题，掌握面试所有知识点
https://leetcode.cn/studyplan/top-interview-150/
二、算法之路
【1】合并两个有序数组（题号：88）
题目描述：
给你两个按非递减顺序排列的整数数组nums1和nums2，另有两个整数m和n，分别表示nums1和nums2中的元素数目。
请你合并 nums2到nums1中，使合并后的数组同样按非递减顺序排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
提示：
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-10^9 <= nums1[i], nums2[j] <= 10^9
模拟计算：
代码实现：
/* title:88. 合并两个有序数组 author:yunyue time:2024/2/28 website:https://leetcode.cn/problems/merge-sorted-array/?envType=study-plan-v2&envId=top-interview-150 */ #include<bits/stdc++.h> #include<vector> using namespace std; //列表遍历 void print(vector<int>& vec){ vector<int>::iterator it; for(it = vec.begin(); it != vec.end(); ++it) { cout << *it << " "; } } //列表合并方法1 //设计思路：数组升序合并，实质上可以看做，从nums1和nums2两个数组逐个比较最大位数字，选择其中更大值从后往前添加至合并后数组 void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int i=m+n-1;//注意元素个数和数组下标的关系 m--; n--; while(n>=0){ while(m>=0&&nums1[m]>nums2[n]){ //循环比较nums1与nums2当前最大值，直至m数组全部放入合并后新nums1的对应位置 swap(nums1[m--],nums1[i--]);//当满足nums1最大值大于nums2时，将其放入合并后新nums1的高位 } swap(nums1[i--],nums2[n--]); //当nums1数组全部放入合并后新nums1对应位置后，nums2还有剩余数字，则由于原本数组为升序直接依次放入合并后新nums1数组 } } //列表合并方法2 //设计思路：直接将两个数组合并，利用vector中的sort直接进行数组排序 void merge2(vector<int>& nums1, int m, vector<int>& nums2, int n){ nums1.insert(nums1.begin()+m,nums2.begin(),nums2.end()); nums1.erase(nums1.begin()+m+n,nums1.end()); //清楚掉最后的0 sort(nums1.begin(),nums1.end()); //排序 } int main(){ vector<int> nums1; vector<int> nums2; int m,n,num; cin>>m>>n; //输入nums1和nums2的元素个数 for(int i=0;i<m;i++){//输入nums1元素 cin>>num; nums1.push_back(num); } nums1.insert(nums1.end(),n,0);//按合并后元素个数填充0 for(int i=0;i<n;i++){//输入nums2元素 cin>>num; nums2.push_back(num); } // cout<<"方法1排序："<<endl; // merge(nums1,m,nums2,n); // print(nums1); cout<<"方法2排序：" <<endl; merge2(nums1,m,nums2,n); print(nums1); return 0; }结果展示：
【2】移除元素（题号：27）
题目描述：
给你一个数组nums和一个值val，你需要原地移除所有数值等于val的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用O(1)额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明：
为什么返回数值是整数，但输出的答案是数组呢?请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度2, 并且nums中的前两个元素均为2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为2，而nums=[2,2,3,3]或nums=[2,2,0,0]，也会被视作正确答案。
示例2：
输入：nums=[0,1,2,2,3,0,4,2],val = 2
输出：5,nums=[0,1,3,0,4]
解释：函数应该返回新的长度5, 并且nums中的前五个元素为0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
代码实现：
/* title:27.移除元素 author:yunyue time:2024/2/28 website:https://leetcode.cn/problems/remove-element/description/?envType=study-plan-v2&envId=top-interview-150 */ #include<bits/stdc++.h> using namespace std; //数组遍历 void print(vector<int>& vec){ vector<int>::iterator it; for(it = vec.begin(); it != vec.end(); ++it) { cout << *it << " "; } cout<<endl; } /*删除数组中指定元素 设计思路：利用vector的迭代器，遍历数组元素，查找待删元素val，利用erase()函数删除。 */ int removeElement(vector<int>& nums, int val){ vector<int>::iterator it;//构造vector迭代器 for(it=nums.begin();it!=nums.end();){ if(*it==val){//当前元素等于val时，消除该元素，注意此时it不需要自增（删除后的元素） nums.erase(it); continue; } it++; } return nums.size(); } /* 其他思路： 1.利用双指针删除，两个指针同时从左端开始，当右指针元素不为等于val时，用右指针元素覆盖左指针元素（效果就是保留非val元素），左右指针同时向后移动； 2.或者双指针，从数组两端移动，当左端遍历的元素等于val时，使用右端指针元素覆盖左端元素 作者：力扣官方题解 链接：https://leetcode.cn/problems/remove-element/solutions/730203/yi-chu-yuan-su-by-leetcode-solution-svxi/ 来源：力扣（LeetCode） */ //双指针 int removeElement2(vector<int>& nums, int val) { int n = nums.size(); int left = 0; for (int right = 0; right < n; right++) { if (nums[right] != val) {//当前元素不为val时，将右指针元素覆盖左指针元素，左右指针同时移动，最后left即表示为非val元素的个数 nums[left] = nums[right]; left++; } } return left; } //双指针优化 /* 如果左指针left指向的元素等于val，此时将右指针right 指向的元素复制到左指针left的位置，然后右指针right左移一位。 如果赋值过来的元素恰好也等于val，可以继续把右指针right指向的元素的值赋值过来（左指针left指向的等于val的元素的位置继续被覆盖）， 直到左指针指向的元素的值不等于val为止。 当左指针left和右指针right 重合的时候，左右指针遍历完数组中所有的元素。 这样的方法两个指针在最坏的情况下合起来只遍历了数组一次。与方法一不同的是，方法二避免了需要保留的元素的重复赋值操作。 */ int removeElement3(vector<int>& nums, int val) { int left = 0, right = nums.size(); while (left < right) { if (nums[left] == val) { nums[left] = nums[right - 1]; right--; } else { left++; } } return left; } int main(){ vector<int> nums; int number,val; char chr; cout<<"输入数组:"; //动态输入数组，回车时结束输入 while (cin>>number) { nums.push_back(number); cin.get(chr); if (chr != ',') break; } // print(nums); cout<<"输入要删除元素："; cin>>val; int count;//统计剩余元素数量 count=removeElement(nums,val); cout<<"剩余元素："; print(nums); cout<<"剩余元素个数："<<count; return 0; }结果展示：
【3】删除有序数组中的重复项（题号：26）
题目描述：
给你一个非严格递增排列的数组nums，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回nums中唯一元素的个数。
考虑nums的唯一元素的数量为k，你需要做以下事情确保你的题解可以被通过：
更改数组nums，使nums的前k个元素包含唯一元素，并按照它们最初在nums中出现的顺序排列nums的其余元素与nums的大小不重要。
返回 k 。
示例1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
提示：
1 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
nums 已按 非严格递增 排列
模拟计算：
代码实现：
/* title:26.删除有序数组中的重复项 author:yunyue time:2024/2/28 website:https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150 */ #include<bits/stdc++.h> using namespace std; void print(vector<int>& vec){ vector<int>::iterator it; for(it=vec.begin();it!=vec.end();it++){ cout<<*it<<" "; } cout<<endl; } /* 方法：双指针,不需要删除数组元素 设计思路： 使用双指针，右指针每步经过判断都向后移动，左指针指向当前待替换元素，当right与right-1不等时， 说明出现新的未重复元素，寄替换left指向元素，两指针同时向后移动，这样的效果能保证从开始到left 的序列为不重复的序列，left的数值即为不重复元素个数。 */ int removeDuplicates(vector<int>& nums) { int count=nums.size(); if(count==0) return 0; int left=1,right=1;//从下标为1开始，left指向代替换元素，right快速向后遍历 while(right<count){//right到达count时，说明数组遍历结束 if(nums[right]!=nums[right-1]){//当right与right-1不相等时候，由于数组序列是按序的，说明right指向元素还未重复出现 nums[left]=nums[right];//用right元素替换left left++;//替换成功后移动至下一个位置，即新的替换位置 } right++;//right每步经过判断都向后移动 } return left; } int main(){ vector<int> nums; int number; char chr; cout<<"输入数组："; //数组动态输入，回车结束 while(cin>>number){ nums.push_back(number); cin.get(chr); if(chr!=',') break; } int count; count=removeDuplicates(nums); cout<<"删除重复元素后元素个数："<<count<<endl; return 0; }结果展示：
【4】删除有序数组中的重复项 II（题号：80）
题目描述：
给你一个有序数组 nums ，请你原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。
示例1：
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。
示例2：
输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。
提示：
1 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
nums 已按升序排列
模拟计算：
代码实现：
/* title:80.删除有序数组中的重复项 II author:yunyue time:2024/2/28 website:https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/description/?envType=study-plan-v2&envId=top-interview-150 */ #include<bits/stdc++.h> using namespace std; void print(vector<int>& vec){ vector<int>::iterator it; for(it=vec.begin();it!=vec.end();it++){ cout<<*it<<" "; } cout<<endl; } /*方法：双指针(快慢指针) (1)当count值小于等于2时，无需删除元素，直接返回count值 (2)当count值大于2时，使用快慢指针方式，slow始终指向代替换元素的位置，当fast指针与slow-2不相等时， 表示当前fast指针所指向元素还未重复超过两次，用fast指针元素覆盖slow指针元素。 */ int removeDuplicates(vector<int>& nums) { int count=nums.size(); if(count<=2) return count;//当序列小于等于2时，无需删除 int slow=2,fast=2;//快慢指针 while(fast<count){//快指针遍历整个序列 if(nums[fast]!=nums[slow-2]){//slow指针代替换位置，slow-2保证重复位置最多预留2位 nums[slow]=nums[fast];//用fast指针元素替换slow指针元素 slow++; } fast++;//逐个元素一次遍历 } return slow; } int main(){ vector<int> nums; int number; char chr; cout<<"输入数组："; while(cin>>number){ nums.push_back(number); cin.get(chr); if(chr!=',') break; } int count; count=removeDuplicates(nums); cout<<"删除重复元素后元素个数："<<count<<endl; return 0; }结果展示：
【5】多数元素（题号：169）
题目描述：
给定一个大小为n的数组nums，返回其中的多数元素。多数元素是指在数组中出现次数大于⌊n/2⌋的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例1：
输入：nums = [3,2,3]
输出：3
示例2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
提示：
n == nums.length
1 <= n <= 5 * 104
-10^9 <= nums[i] <= 10^9
代码实现：
/* title:169.多数元素 author:yunyue time:2024/2/29 website:https://leetcode.cn/problems/majority-element/description/?envType=study-plan-v2&envId=top-interview-150 */ #include<bits/stdc++.h> using namespace std; void print(vector<int>& vec){ vector<int>::iterator it; for(it=vec.begin();it!=vec.end();it++){ cout<<*it<<" "; } cout<<endl; } /* 方法1：map映射 注意： (1)性能不同： unordered_map是不按键值排序的，插入的时间是O(logn),查询时间是O(1) map是按键值排序的，插入的时间是O(logn),查询时间是O(logn)； (2)实现不同： map的底层由红黑树构成，unordered_map底层由哈希表构成; (3)使用范围不同： unordered_map的使用比较局限，它的key只能是int、double等基本类型以及string，而不能是自己定义的结构体 map可以支持所有类型的键值对。 */ int majorityElement(vector<int>& nums) { map<int, int> counts; int majority=0,count=0; vector<int>::iterator it;//vector容器迭代器 for (it=nums.begin();it!=nums.end();it++){ counts[*it]++;//对应位置计数自增 if(counts[*it]>count) {//若当前key对应的value值大于暂时的最大统计数count时，保存该元素值给majority，更新count majority=*it; count=counts[*it]; } } return majority; } /* 方法2：排序 设计思路：当一个元素数量大于n/2时，经过排序后的中间数字必然为该元素。 */ int majorityElement2(vector<int>& nums){ sort(nums.begin(),nums.end()); return nums[nums.size()/2]; } int main(){ vector<int> nums; int number; char chr; cout<<"请输入数组元素："; while(cin>>number){ nums.push_back(number); cin.get(chr); if(chr!=',') break; } int majority=majorityElement(nums); cout<<"多数元素："<<majority<<endl; cout<<"数组元素："; print(nums); return 0; }结果展示：
【6】轮转数组（题号：189）
题目描述：
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例1：
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例2：
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
提示：
1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 10^5
模拟计算：
代码实现：
/* title:189.轮转数组 author:yunyue time:2028/2/29 website:https://leetcode.cn/problems/rotate-array/description/?envType=study-plan-v2&envId=top-interview-150 */ #include<bits/stdc++.h> #include<vector> using namespace std; void print(vector<int>& vec){ vector<int>::iterator it; for(it=vec.begin();it!=vec.end();it++){ cout<<*it<<" "; } cout<<endl; } /* 方式1：取mod计算新位置 设计思路：复制数组元素，新位置的计算方式为(原下标+轮转轮数)mod数组个数 */ void rotate(vector<int>& nums, int k) { vector<int> vec; vec.assign(nums.begin(),nums.end());//复制原数组 for(int i=0;i<nums.size();i++){ nums[(i+k)%nums.size()]=vec[i];//直接计算轮转后结果的下标，对原数组进行覆盖 } } /* 方式2：交换法 设计思路： 举个例子1 2 3 4 5 6 ，交换2轮， 结果可知5 6 1 2 3 4，故可知1 3 5为一组，2 4 6为一组，同时这两组中元素对应位置遵循前后闭环交换， 可使用swap函数实现，当各组循环交换一轮后实现最终轮转。 */ void rotate2(vector<int>& nums,int k){ int n=nums.size(); k=k%n; int count=__gcd(k, n);//计算组数 for(int start=0;start<count;++start){ int current=start;//存放当前组待交换元素下标 int prev=nums[start];//存放当前组首个元素，避免交换后被覆盖 do { int next=(current+k)%n;//计算轮转后当前元素新下标 swap(nums[next],prev);//交换组内相邻两个元素 current=next;//更新待交换元素下标 } while(start!=current);//直至每组内元素交换一圈 } } int main(){ vector<int> nums; int number; char chr; cout<<"请输入数组："; while(cin>>number){ nums.push_back(number); cin.get(chr); if(chr!=',') break; } cout<<"请输入轮转步数："; int k; cin>>k; rotate(nums,k); cout<<"轮转结果："; print(nums); return 0; }结果展示：
【7】买卖股票的最佳时机（题号：121）
题目描述：
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第2天（股票价格=1）的时候买入，在第5天（股票价格=6）的时候卖出，最大利润=6-1= 5。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4
模拟计算：
代码实现：
/* title:121.买卖股票的最佳时机 author:yunyue time:2024/2/29 website:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/?envType=study-plan-v2&envId=top-interview-150 */ #include<bits/stdc++.h> using namespace std; void print(vector<int>& vec){ vector<int>::iterator it; for(it=vec.begin();it!=vec.end();it++){ cout<<*it<<" "; } cout<<endl; } /* 方法：最大差值 设计思路：每次比较当前价格和当前最低价格，当前价格更低时，更新minprice; 否则每次prices数组移动，保存与当前最低价格的最大获利。 */ int maxProfit(vector<int>& prices){ int minprice=1e9;//存放历史最低价格 int maxprofit=0;//存放历史最大获利 for(int i=0;i<prices.size();i++){ if(minprice>prices[i]){//若历史最低价格大于当前价格，更新minprice minprice=prices[i]; } else{//若历史最低价格未更新，则比较 历史最大获利 和 当前价格 - 历史最低价，较大值存于maxprofit maxprofit=maxprofit>(prices[i]-minprice)?maxprofit:prices[i]-minprice; } } return maxprofit; } int main(){ vector<int> nums; int number; char chr; cout<<"输入价格："; while(cin>>number){ nums.push_back(number); cin.get(chr); if(chr!=',') break; } int maxprofit=maxProfit(nums); cout<<"最大获利为："<<maxprofit<<endl; return 0; }结果展示：
【8】买卖股票的最佳时机II（题号：122）
题目描述：
给你一个整数数组prices，其中prices[i]表示某支股票第i天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。
返回你能获得的最大利润 。
示例1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第2天（股票价格=1）的时候买入，在第3天（股票价格=5）的时候卖出, 这笔交易所能获得利润=5-1=4。
随后，在第4天（股票价格=3）的时候买入，在第5天（股票价格=6）的时候卖出, 这笔交易所能获得利润=6-3=3。总利润为 4 + 3 = 7 。
示例2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第1天（股票价格=1）的时候买入，在第5天 （股票价格=5）的时候卖出, 这笔交易所能获得利润=5-1=4。总利润为4。
示例3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为0。
提示：
1 <= prices.length <= 3 * 10^4
0 <= prices[i] <= 10^4
模拟计算：
代码实现：
/* title:122.买卖股票的最佳时机 II author:yunyue time:2024/2/29 website:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/?envType=study-plan-v2&envId=top-interview-150 */ #include<bits/stdc++.h> #include<vector> using namespace std; void print(int vec[][2]){ for(int i=0;i<6;i++){ cout<<vec[i][0]<<" "<<vec[i][1]<<endl; } } /* 方法1：动态规划 设计思路： 构建状态转移方程，用dp[i][0]表示当前未持有股票状态时获益情况，dp[i][1]表示当前持有股票状态时获益情况； dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])，比较选择上一轮未持有股票本轮也未买股票情况获益和将上一轮股票持有卖出后两者最大值， 作为当前未持有股票的最大收益； dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])，比较选择上一轮股票继续持有总获益和在上一轮股票未持有下买入当前股票的总获益最大值， 作为当前持有股票的最大获益。 */ int maxProfit(vector<int>& prices) { int n=prices.size(); int dp[n][2]; dp[0][0]=0;//初始化 dp[0][1]=-prices[0]; for(int i=1;i<n;i++){ dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]); dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]); } // cout<<"dp:"<<endl; // print(dp); return dp[n-1][0]; } /* 方法2：贪心算法 */ int maxProfit2(vector<int>& prices){ int profit=0; for(int i=1;i<prices.size();i++){ profit+=max(0,prices[i]-prices[i-1]); } return profit; } int main(){ vector<int> prices; int number; char chr; cout<<"请输入价格："; while(cin>>number){ prices.push_back(number); cin.get(chr); if(chr!=',') break; } int profit=maxProfit(prices); cout<<"最大获利："<<profit<<endl; return 0; }结果展示：
【9】跳跃游戏（题号：55）
题目描述：
给你一个非负整数数组nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回true；否则，返回false。
示例1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳1步，从下标0到达下标1, 然后再从下标1跳3步到达最后一个下标。
示例2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为3的位置。但该下标的最大跳跃长度是0， 所以永远不可能到达最后一个下标。
提示：
1 <= nums.length <= 10^4
0 <= nums[i] <= 10^5
代码实现：
/* title:55.跳跃游戏 author:yunyue time:2024/3/1 website:https://leetcode.cn/problems/jump-game/?envType=study-plan-v2&envId=top-interview-150 */ #include<bits/stdc++.h> #include<vector> using namespace std; void print(vector<int>& vec){ vector<int>::iterator it; for(it=vec.begin();it!=vec.end();it++){ cout<<*it<<" "; } cout<<endl; } /* 方法：贪心 设计思路： 本题本质计算数组最远路径和是否大于等于元素个数（下标表示时为n-1）； 每一步可以走的为i+nums[i]，计算最远路径为maxstep=max(maxstep,i+nums[i])，不断更新最长路径， 若在过程中i>maxstep，则表示最终将无法到达。 */ bool canJump(vector<int>& nums) { int n=nums.size(); int maxstep=0; for(int i=0;i<n;i++){ if(i<=maxstep){ maxstep=max(maxstep,i+nums[i]); if(maxstep>=n-1){//当最远可达步数大于等于数组边界，则表示可以到达 return true; } } } return false; } int main(){ vector<int> nums; int number; char chr; cout<<"请输入跳跃步数："; while(cin>>number){ nums.push_back(number); cin.get(chr); if(chr!=',') break; } bool ans=canJump(nums); if(ans){ cout<<"可以到达！"; } else{ cout<<"不可以到达！"; } return 0; }结果展示：
【10】跳跃游戏II（题号：45）
题目描述：
给定一个长度为n的0索引整数数组nums。初始位置为nums[0]。
每个元素nums[i]表示从索引i向前跳转的最大长度。换句话说，如果你在nums[i]处，你可以跳转到任意nums[i+j]处：
- 0 <= j <= nums[i]
- i + j < n
返回到达nums[n - 1]的最小跳跃次数。生成的测试用例可以到达nums[n - 1]。
示例1：
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是2。从下标为0跳到下标为1的位置，跳1步，然后跳3步到达数组的最后一个位置。
示例2：
输入: nums = [2,3,0,1,4]
输出: 2
提示：
1 <= nums.length <= 10^4
0 <= nums[i] <= 1000
题目保证可以到达 nums[n-1]
代码实现：
/* title:45. 跳跃游戏II author:yunyue time:2024/3/1 website:https://leetcode.cn/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-interview-150 */ #include<bits/stdc++.h> using namespace std; void print(vector<int>& vec){ vector<int>::iterator it; for(it=vec.begin();it!=vec.end();it++){ cout<<*it<<" "; } cout<<endl; } /* 方法：贪心 设计思路： 使用maxPos标记当前最远位置，end记录当前路径边界，每次当i=end时即为当前步数等于end路径边界时，step++， 每次跳跃后，更新end为当前maxPos的值（注意：直到下一次跳跃期间，maxPos也会更新），特别的，最后一步的end大于等于n-1（下标表示）， 避免了多计算一次最后一步的结果，设置i<n-1。 */ int jump(vector<int>& nums) { int n=nums.size(),maxPos=0,step=0,end=0; for(int i=0;i<n-1;i++){ if(maxPos>=i){ maxPos=max(maxPos,i+nums[i]); if(i==end){ end=maxPos; step++; } // cout<<"i="<<i<<" maxPos="<<maxPos<<" step="<<step<<" end="<<end<<endl; } } return step; } main(){ vector<int> nums; int number; char chr; cout<<"请输入跳跃步数："; while(cin>>number){ nums.push_back(number); cin.get(chr); if(chr!=',') break; } int step=jump(nums); cout<<"需要的最少步数："<<step<<endl; return 0; }结果展示：
三、小结
上述算法题对应链接在代码部分的最前面，读者可以在leetcode上提交自己的代码进行检验。同时本博客代码参考官方题解，在leetcode中也有其他算法uu的代码设计思路可以进行学习，算法之路道阻且艰，愿一路同行。
PS：代码或解析有误之处，欢迎uu们评论或私信联系。
