📋 前言
🌈 个人主页：Sarapines Programmer
🔥 系列专栏：本期文章收录在《C语言闯关笔记》，大家有兴趣可以浏览和关注，后面将会有更多精彩内容！
⏰翰墨致赠：翩翩风华激彩虹，豪情壮志醉长空。 剑指星河舞红尘，梦驰烈马向未来。
🎉欢迎大家关注🔍点赞👍收藏⭐️留言📝
🔔作者留言：欢迎来到我的编程学习笔记！这里是一个探索编程世界的秘境，我的学习笔记为你揭开C/C++语言的神秘面纱。在这个学习笔记中，我不仅分享C/C++的基础知识和高级技巧，还包含实用技术和项目经验的宝贵经验。无论你是初学者还是经验丰富的程序员，这个学习笔记将为你呈现出奇妙的编程魔法，帮助你在C/C++的编程森林中展开一场精彩的学习之旅。你准备好了吗？跟着我，一起编织属于我们自己的编程魔法吧！
题库地址:学习计划 – 力扣（LeetCode）
目录
🌐数组/字符串篇
😎1 合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 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] 。代码模板：
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { } };
💡解决如下：
/*思路1*/
//先将nums2加到nums末尾，再排序（升序）即可
/*思路2*/
//遍历nums1和nums2，
//若nums1[i]>num2[j],num2[j]插入nums1[i]前
//若nums1[i]==num2[j],num2[j]插入nums1[i]后
//若nums1[i]<num2[j],则继续遍历num1,直到找到最小的nums[k]>=num2[j],num2[j]插入nums1[k]前，找不到则直接插入nums1末尾
/*思路一求解*/
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
//去除nums1多余的元素0
//for(int i=m;i<nums1.size();i++){ //循环删除导致迭代器失效
// nums1.erase(nums1.begin()+i);
//}
nums1.erase(nums1.begin()+m,nums1.end());
//合并nums2==>nums1
for(int i=0;i<n;i++){
nums1.push_back(nums2[i]);
}
//整体排序
sort(nums1);
}
void sort(vector<int> &v){
for(int i=0;i<v.size()-1;i++){
int k=i;
for(int j=i+1;j<v.size();j++){
if(v[k]>v[j]){
int t=v[k];
v[k]=v[j];
v[j]=t;
}
}
}
}
};😎2 移除元素
给你一个数组 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。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。代码模板：
class Solution { public: int removeElement(vector<int>& nums, int val) { } };
💡解决如下：
//思路：遍历找到val值相等元素，删除即可
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
for(int i=0;i<nums.size();){
if(nums[i]==val) nums.erase(nums.begin()+i);
else i++;
}
return int(nums.size());
}
};😎3 删除有序数组中的重复项
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。
判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = […]; // 输入数组
int[] expectedNums = […]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过，那么您的题解将被 通过。示例 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 。不需要考虑数组中超出新长度后面的元素。代码模板：
class Solution { public: int removeDuplicates(vector<int>& nums) { } };
💡解决如下：
//思路：新建一个集合set存储出现过的元素【边初始化边查找】，对于每个元素都进行find，未找到则插入，找到则删除该向量元素
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
set<int> s;
for(int i=0;i<nums.size();){
if(i!=0){//对于向量非首项
if(s.find(nums[i]) !=s.end()){//如果集合s中已经有出现nums[i]
nums.erase(nums.begin()+i);
}
else{
s.insert(nums[i]);
i++;
}
}
else {//对于向量首项
s.insert(nums[i]);
i++;
}
}
return nums.size();
}
};
😎4 删除有序数组中的重复项Ⅱ
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
说明：
为什么返回数值是整数，但输出的答案是数组呢？
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}示例 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。不需要考虑数组中超出新长度后面的元素。代码模板：
class Solution { public: int removeDuplicates(vector<int>& nums) { } };
💡解决如下：
//思路：遍历，flag标志出现次数,[flag=0初始值]
//当前元素和前一元素不相等 | 首项，继续循环下一个
//else 当前元素和前一元素相等则flag++
//当flag=1表示出现两次，后续和前一字符相等的删去
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int flag=0;
for(int i=0;i<nums.size();){
if(i==0 || nums[i]!=nums[i-1]){
i++;
flag=0;
}
else{
if(flag ==1){
nums.erase(nums.begin()+i);
}
else {
flag++;
i++;
}
}
}
return nums.size();
}
};😎5 多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1： 输入：nums = [3,2,3] 输出：3 示例 2： 输入：nums = [2,2,1,1,1,2,2] 输出：2代码模板：
class Solution { public: int majorityElement(vector<int>& nums) { } };
💡解决如下：
//思路：摩尔投票法
class Solution {
public:
int majorityElement(vector<int>& nums) {
int n=nums[0],count=0;
for(int i=0;i<nums.size();i++){
if(i==0 || nums[i]==n){
count++;
}
else{
if(count==0){
n=nums[i];
count=1;
}
count--;
}
}
return n;
}
};😎6 轮转数组
给定一个整数数组 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]代码模板：
class Solution { public: void rotate(vector<int>& nums, int k) { } };
💡解决如下：
//思路1：按照逻辑顺序：存储向量尾元素，然后尾部向前 逐一向前赋值。
//超出时间复杂度
/*
class Solution {
public:
void rotate(vector<int>& nums, int k) {
for(int i=0;i<k;i++){
int m=nums[nums.size()-1];
for(int j=nums.size()-1;j>0;j--){
nums[j]=nums[j-1];
}
nums[0]=m;
}
}
};*/
//优化思路2：存储向量尾元素，去除向量尾元素，向首元素插入尾元素.
//超出时间复杂度
/*class Solution {
public:
void rotate(vector<int>& nums, int k) {
for(int i=0;i<k;i++){
int m=nums[nums.size()-1];
nums.erase(nums.begin()+nums.size()-1);
nums.insert(nums.begin(),m);
}
}
};*/
//优化思路3：直接新建一个向量，然后直接计算最终顺序解答！
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n=nums.size();
//k超过向量长度
k=k%n;
vector<int> v(n);
for(int i=0;i<n;i++){
v[(i+k)%n]=nums[i];
}
nums=v;
}
};😎7 买卖股票的最佳时机
给定一个数组 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。代码模板：
class Solution { public: int maxProfit(vector<int>& prices) { } };
💡解决如下：
//思路1：两次遍历，外层遍历买入，内层统计每次的利润，大则更新
//超出时间复杂度
/*class Solution {
public:
int maxProfit(vector<int>& prices) {
int max=0;
int input=0,out=0;
for(int i=0;i<prices.size()-1;i++){
for(int j=i+1;j<prices.size();j++){
int sub=prices[j]-prices[i];
if(sub<=0) continue;
else{
if(sub>max){
max=sub;
out=j+1;
input=i+1;
}
}
}
}
return max;
}
};*/
//优化思路：一次遍历
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.empty()) {
return 0;
}
int maxProfit = 0;
int minPrice = prices[0];
for (int i = 1; i < prices.size(); ++i) {
int currentProfit = prices[i] - minPrice;//当前利润
maxProfit = max(maxProfit, currentProfit);//更新最大利润
minPrice = min(minPrice, prices[i]);//更新最低买入价格
}
return maxProfit;
}
};
😎8 买卖股票的最佳时机 II
给你一个整数数组 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 。代码模板：
class Solution { public: int maxProfit(vector<int>& prices) { } };
💡解决如下：
//思路1：两次遍历，外层遍历买入，内层统计每次的利润，大则更新
//当天赚，还可以当天买max1
//当天赚，隔一天买max2
//超出时间复杂度
/*
class Solution {
public:
int maxProfit(vector<int>& prices) {
int max=0,max1=0,max2=0;
for(int i=0;i<prices.size()-1;i++){//当天赚，还可以当天买max1
for(int j=i+1;j<prices.size();j++){
int sub=prices[j]-prices[i];
if(sub<=0) {
continue;
}
else{
max1+=sub;
i=j-1;
break;
}
}
}
for(int i=0;i<prices.size()-1;i++){//当天赚，隔一天买max2
for(int j=i+1;j<prices.size();j++){
int sub=prices[j]-prices[i];
if(sub<=0) {
continue;
}
else{
max2+=sub;
i=j;
break;
}
}
}
max=max1>max2?max1:max2;
return max;
}
};*/
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (n <= 1) {
return 0;
}
// 定义两个状态数组
vector<int> buy(n, 0);
vector<int> sell(n, 0);
// 初始化第一天的状态
buy[0] = -prices[0];
sell[0] = 0;
// 状态转移
for (int i = 1; i < n; ++i) {
buy[i] = max(buy[i-1], sell[i-1] - prices[i]);
sell[i] = max(sell[i-1], buy[i-1] + prices[i]);
}
// 最终的答案是最后一天不持有股票的状态
return sell[n-1];
}
};
😎9 罗马数字转整数
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。示例 1: 输入: s = "III" 输出: 3 示例 2: 输入: s = "IV" 输出: 4 示例 3: 输入: s = "IX" 输出: 9 示例 4: 输入: s = "LVIII" 输出: 58 解释: L = 50, V= 5, III = 3. 示例 5: 输入: s = "MCMXCIV" 输出: 1994 解释: M = 1000, CM = 900, XC = 90, IV = 4.代码模板：
class Solution { public: int romanToInt(string s) { } };
💡解决如下：
class Solution {
public:
int romanToInt(string s) {
map<char,long> m;
m['I']=1;
m['V']=5;
m['X']=10;
m['L']=50;
m['C']=100;
m['D']=500;
m['M']=1000;
long sum=0,slen=s.length();
for(int i=0;i<slen;i++){
if(s[i]=='I'){
if(s[i+1]=='V') {sum+=4;i++;}
else if(s[i+1]=='X') {sum+=9;i++;}
else sum+=m[s[i]];
}
else if(s[i]=='X'){
if(s[i+1]=='L') {sum+=40;i++;}
else if(s[i+1]=='C') {sum+=90;i++;}
else sum+=m[s[i]];
}
else if(s[i]=='C'){
if(s[i+1]=='D') {sum+=400;i++;}
else if(s[i+1]=='M') {sum+=900;i++;}
else sum+=m[s[i]];
}
else sum+=m[s[i]];
}
return sum;
}
};😎10 最后一个单词的长
给你一个字符串
s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
示例 1： 输入：s = "Hello World" 输出：5 解释：最后一个单词是“World”，长度为5。 示例 2： 输入：s = " fly me to the moon " 输出：4 解释：最后一个单词是“moon”，长度为4。 示例 3： 输入：s = "luffy is still joyboy" 输出：6 解释：最后一个单词是长度为6的“joyboy”。代码模板：
class Solution { public: int lengthOfLastWord(string s) { } };
💡解决如下：
//思路：从后往前，先定位到最后一个字母开始计数，向前找到第一个空格计数结束
class Solution {
public:
int lengthOfLastWord(string s) {
int slen=s.length();
if(slen==1) return 1;
int i=slen-1;
int count=0;
while(i>=0 && s[i]==' '){//跳过尾部的空格，定位到单词的尾字母
i--;
}
while(i>=0 && s[i]!=' '){
count++;
i--;
}
return count;
}
};
文章出处登录后可见！
