娄底工程建设有限公司网站,贴图库wordpress,全能网站建设,海外网络推广服务进阶#xff0c;其他解法
数组
88. 合并两个有序数组 - 力扣#xff08;LeetCode#xff09;
1、按非递减顺序合并两个数组
从末尾开始#xff0c;用while分没到两个数组头#xff0c;到第一个数组头#xff0c;到第二个数组头三种情况
class Solution {
public:voi…进阶其他解法
数组
88. 合并两个有序数组 - 力扣LeetCode
1、按非递减顺序合并两个数组
从末尾开始用while分没到两个数组头到第一个数组头到第二个数组头三种情况
class Solution {
public:void merge(vectorint nums1, int m, vectorint nums2, int n) {int im-1,jn-1,kmn-1;while(i0j0){nums1[k--]nums1[i]nums2[j]?nums1[i--]:nums2[j--];}while(i0){nums1[k--]nums1[i--];}while(j0){nums1[k--]nums2[j--];}}
}; 2、移除掉某个数值的元素无序
27. 移除元素 - 力扣LeetCode
借助一个新标号
class Solution {
public:int removeElement(vectorint nums, int val) {//双指针法int slowIndex0;for(int islowIndex;inums.size();i){if (val!nums[i]){nums[slowIndex]nums[i];//先赋值再}}return slowIndex;}
};
3、删除有序数组中的重复项
26. 删除有序数组中的重复项 - 力扣LeetCode
同样用一个标号在原数组覆盖序列长度有变化且后面的元素不重要同2
class Solution {
public:int removeDuplicates(vectorint nums) {int index1;for(int i1;inums.size();i){if(nums[i]!nums[i-1]){nums[index]nums[i];}}return index;}
};
4、80. 删除有序数组中的重复项 II - 力扣LeetCode
使得出现次数超过两次的元素只出现两次,记录相等的次数
class Solution {
public:int removeDuplicates(vectorint nums) {if(nums.size()2)return nums.size();int index1;int count0;for(int i1;inums.size();i){if(nums[i]nums[i-1]){count; if(count1){nums[index]nums[i];}}else{count0;nums[index]nums[i];} }return index;}
};
5、169. 多数元素 - 力扣LeetCode
数组中出现次数超过一半的数字” 被称为 “众数”
此数字出现次数大于所有其他数字出现次数
class Solution {
public:int majorityElement(vectorint nums) {int x0,votes0;for(int num:nums){if(votes0) xnum;votesxnum?1:-1;}return x;}
};
6、189. 轮转数组 - 力扣LeetCode
(ik)%n,新建数组
class Solution {
public:void rotate(vectorint nums, int k) {int nnums.size();vectorint tmp(n);for(int i0;in;i){tmp[(ik)%n]nums[i];} nums.assign(tmp.begin(),tmp.end());}
};
7、121. 买卖股票的最佳时机 - 力扣LeetCode
某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票
class Solution {
public:int maxProfit(vectorint prices) {int pre prices[0],ans0;for(auto m:prices){premin(pre,m);//pre来选极小值越小越好ansmax(ans,m-pre);//ans来选抛售的极大值}return ans;}
};
8、122. 买卖股票的最佳时机 II - 力扣LeetCode------贪心解法
可购买出售多次策略只要不赔钱就一直买卖
class Solution {
public:int maxProfit(vectorint prices) {int profit0;for(int i1;iprices.size();i){int tmpprices[i]-prices[i-1];if(tmp0) profittmp;}return profit;}
};
9、55. 跳跃游戏 - 力扣LeetCode
数组中的每个元素代表你在该位置可以跳跃的最大长度。
策略看是否可以跳过最大长度为0 的位置
未成清贫难成人不经挫折永天真 人情似纸张张薄世事如棋局局新。
class Solution {
public:bool canJump(vectorint nums) {int step1;int i0;int nnums.size()-1;for(int in-1;i0;i--){if(nums[i]step){step0;}step;}return step1;}
};
贪心解法判断并留下 之前走的最远的策略 和 当前策略 中最好的若最好的去不到循环中下一个位置则失败。
class Solution {
public:bool canJump(vectorint nums) {int rightMost0;int nnums.size();for(int i0;in;i){if(irightMost){rightMostmax(rightMost,inums[i]) ; if(rightMostn-1) return true;}} return false;}
};
10、45. 跳跃游戏 II - 力扣LeetCode
要求返回到达 nums[n - 1] 的最小跳跃次数
//数组[2,3,1,2,4,2,3]
//下标 0 1 2 3 4 5 6
策略先看每个位置能跳的最远的职位级别若看完了当前水平能看的公司跑路一次第一次可能在0可能在1当前水平增加
class Solution {
public:int jump(vectorint nums) {int ans 0; //跳槽次数int curUnlock 0; //当前你的水平能入职的最高公司级别int maxUnlock 0; //当前可选公司最多能帮你提到几级for (int i 0; i nums.size() - 1; i) { //从前向后遍历公司最高级公司(nums.length-1)是目标入职后不再跳槽所以不用看故遍历范围是左闭右开区间[0,nums.length-1)maxUnlock max(maxUnlock, i nums[i]); //计算该公司最多能帮你提到几级(公司级别i成长空间nums[i])与之前的提级最高记录比较打破记录则更新记录if (i curUnlock) { // 把你当前水平级别能选的公司都看完了你选择跳槽到记录中给你提级最多的公司以解锁更高级公司的入职权限curUnlock maxUnlock; // 你跳槽到了该公司你的水平级别被提升了ans; //这里记录你跳槽了一次}if(curUnlocknums.size()-1) break;}return ans; //返回跳槽总次数}
};
11、274. H 指数 - 力扣LeetCode
看引用次数
策略从高往低看
int cmp(int*a,int *b){return *a-*b;
}
int hIndex(int* citations, int citationsSize) {qsort(citations,citationsSize,sizeof(int),cmp);int h0,icitationsSize-1;while(i0citations[i]h){h;i--;}return h;}
12、380. O(1) 时间插入、删除和获取随机元素 - 力扣LeetCode
