【Leetcode：面试经典150题】（1-10题）解析
目录
一、内容描述
二、算法之路
【1】合并两个有序数组（题号：88）
【2】移除元素（题号：27）
【3】删除有序数组中的重复项（题号：26）
【4】删除有序数组中的重复项 II（题号：80）
【5】多数元素（题号：169）
【6】轮转数组（题号：189）
【7】买卖股票的最佳时机（题号：121）
【8】买卖股票的最佳时机II（题号：122）
【9】跳跃游戏（题号：55）
【10】跳跃游戏II（题号：45）
三、小结
一、内容描述
该部分内容主要讲解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 #include using namespace std; //列表遍历 void print(vector& vec){ vector::iterator it; for(it = vec.begin(); it != vec.end(); ++it) { cout << *it << " "; } } //列表合并方法1 //设计思路：数组升序合并，实质上可以看做，从nums1和nums2两个数组逐个比较最大位数字，选择其中更大值从后往前添加至合并后数组 void merge(vector& nums1, int m, vector& 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& nums1, int m, vector& 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 nums1; vector nums2; int m,n,num; cin>>m>>n; //输入nums1和nums2的元素个数 for(int i=0;i>num; nums1.push_back(num); } nums1.insert(nums1.end(),n,0);//按合并后元素个数填充0 for(int i=0;i>num; nums2.push_back(num); } // cout<<"方法1排序："< 结果展示：
【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 using namespace std; //数组遍历 void print(vector& vec){ vector::iterator it; for(it = vec.begin(); it != vec.end(); ++it) { cout << *it << " "; } cout<& nums, int val){ vector::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& 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& 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 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<<"剩余元素个数："< 结果展示：
【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 using namespace std; void print(vector& vec){ vector::iterator it; for(it=vec.begin();it!=vec.end();it++){ cout<<*it<<" "; } cout<& nums) { int count=nums.size(); if(count==0) return 0; int left=1,right=1;//从下标为1开始，left指向代替换元素，right快速向后遍历 while(right 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<<"删除重复元素后元素个数："< 结果展示：
【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 using namespace std; void print(vector& vec){ vector::iterator it; for(it=vec.begin();it!=vec.end();it++){ cout<<*it<<" "; } cout<& nums) { int count=nums.size(); if(count<=2) return count;//当序列小于等于2时，无需删除 int slow=2,fast=2;//快慢指针 while(fast 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<<"删除重复元素后元素个数："< 结果展示：
【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 using namespace std; void print(vector& vec){ vector::iterator it; for(it=vec.begin();it!=vec.end();it++){ cout<<*it<<" "; } cout<& nums) { map counts; int majority=0,count=0; vector::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& nums){ sort(nums.begin(),nums.end()); return nums[nums.size()/2]; } int main(){ vector nums; int number; char chr; cout<<"请输入数组元素："; while(cin>>number){ nums.push_back(number); cin.get(chr); if(chr!=',') break; } int majority=majorityElement(nums); cout<<"多数元素："< 结果展示：
【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 #include using namespace std; void print(vector& vec){ vector::iterator it; for(it=vec.begin();it!=vec.end();it++){ cout<<*it<<" "; } cout<& nums, int k) { vector vec; vec.assign(nums.begin(),nums.end());//复制原数组 for(int i=0;i& nums,int k){ int n=nums.size(); k=k%n; int count=__gcd(k, n);//计算组数 for(int start=0;start 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 using namespace std; void print(vector& vec){ vector::iterator it; for(it=vec.begin();it!=vec.end();it++){ cout<<*it<<" "; } cout<& prices){ int minprice=1e9;//存放历史最低价格 int maxprofit=0;//存放历史最大获利 for(int i=0;iprices[i]){//若历史最低价格大于当前价格，更新minprice minprice=prices[i]; } else{//若历史最低价格未更新，则比较 历史最大获利 和 当前价格 - 历史最低价，较大值存于maxprofit maxprofit=maxprofit>(prices[i]-minprice)?maxprofit:prices[i]-minprice; } } return maxprofit; } int main(){ vector nums; int number; char chr; cout<<"输入价格："; while(cin>>number){ nums.push_back(number); cin.get(chr); if(chr!=',') break; } int maxprofit=maxProfit(nums); cout<<"最大获利为："< 结果展示：
【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 #include using namespace std; void print(int vec[][2]){ for(int i=0;i<6;i++){ cout<& prices) { int n=prices.size(); int dp[n][2]; dp[0][0]=0;//初始化 dp[0][1]=-prices[0]; for(int i=1;i& prices){ int profit=0; for(int i=1;i prices; int number; char chr; cout<<"请输入价格："; while(cin>>number){ prices.push_back(number); cin.get(chr); if(chr!=',') break; } int profit=maxProfit(prices); cout<<"最大获利："< 结果展示：
【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 #include using namespace std; void print(vector& vec){ vector::iterator it; for(it=vec.begin();it!=vec.end();it++){ cout<<*it<<" "; } cout<maxstep，则表示最终将无法到达。 */ bool canJump(vector& nums) { int n=nums.size(); int maxstep=0; for(int i=0;i=n-1){//当最远可达步数大于等于数组边界，则表示可以到达 return true; } } } return false; } int main(){ vector 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 using namespace std; void print(vector& vec){ vector::iterator it; for(it=vec.begin();it!=vec.end();it++){ cout<<*it<<" "; } cout<& nums) { int n=nums.size(),maxPos=0,step=0,end=0; for(int i=0;i=i){ maxPos=max(maxPos,i+nums[i]); if(i==end){ end=maxPos; step++; } // cout<<"i="< nums; int number; char chr; cout<<"请输入跳跃步数："; while(cin>>number){ nums.push_back(number); cin.get(chr); if(chr!=',') break; } int step=jump(nums); cout<<"需要的最少步数："< 结果展示：
三、小结
上述算法题对应链接在代码部分的最前面，读者可以在leetcode上提交自己的代码进行检验。同时本博客代码参考官方题解，在leetcode中也有其他算法uu的代码设计思路可以进行学习，算法之路道阻且艰，愿一路同行。
PS：代码或解析有误之处，欢迎uu们评论或私信联系。