🌐数组/字符串篇
😎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; } };
