当前位置：首页 > news >正文

力扣面试经典100题

news 来源：原创 2024/9/21 8:26:49

进阶，其他解法

数组

88. 合并两个有序数组 - 力扣（LeetCode）

1、按非递减顺序合并两个数组

从末尾开始，用while分没到两个数组头，到第一个数组头，到第二个数组头三种情况

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int i=m-1,j=n-1,k=m+n-1;while(i>=0&&j>=0){nums1[k--]=nums1[i]>nums2[j]?nums1[i--]:nums2[j--];}while(i>=0){nums1[k--]=nums1[i--];}while(j>=0){nums1[k--]=nums2[j--];}}
};

2、移除掉某个数值的元素，无序

27. 移除元素 - 力扣（LeetCode）

借助一个新标号

class Solution {
public:int removeElement(vector<int>& nums, int val) {//双指针法int slowIndex=0;for(int i=slowIndex;i<nums.size();i++){if (val!=nums[i]){nums[slowIndex++]=nums[i];//先赋值，再++}}return slowIndex;}
};

3、删除有序数组中的重复项

26. 删除有序数组中的重复项 - 力扣（LeetCode）

同样用一个标号，在原数组覆盖（序列长度有变化，且后面的元素不重要）同2

class Solution {
public:int removeDuplicates(vector<int>& nums) {int index=1;for(int i=1;i<nums.size();i++){if(nums[i]!=nums[i-1]){nums[index++]=nums[i];}}return index;}
};

4、80. 删除有序数组中的重复项 II - 力扣（LeetCode）

使得出现次数超过两次的元素只出现两次,记录相等的次数

class Solution {
public:int removeDuplicates(vector<int>& nums) {if(nums.size()<=2)return nums.size();int index=1;int count=0;for(int i=1;i<nums.size();i++){if(nums[i]==nums[i-1]){count++;          if(count<=1){nums[index++]=nums[i];}}else{count=0;nums[index++]=nums[i];} }return index;}
};

5、169. 多数元素 - 力扣（LeetCode）

数组中出现次数超过一半的数字” 被称为 “众数”

此数字出现次数大于所有其他数字出现次数

class Solution {
public:int majorityElement(vector<int>& nums) {int x=0,votes=0;for(int num:nums){if(votes==0) x=num;votes+=x==num?1:-1;}return x;}
};

6、189. 轮转数组 - 力扣（LeetCode）

(i+k)%n,新建数组

class Solution {
public:void rotate(vector<int>& nums, int k) {int n=nums.size();vector<int> tmp(n);for(int i=0;i<n;i++){tmp[(i+k)%n]=nums[i];}   nums.assign(tmp.begin(),tmp.end());}
};

7、121. 买卖股票的最佳时机 - 力扣（LeetCode）

某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票

class Solution {
public:int maxProfit(vector<int>& prices) {int pre =prices[0],ans=0;for(auto &m:prices){pre=min(pre,m);//pre来选极小值，越小越好ans=max(ans,m-pre);//ans来选抛售的极大值}return ans;}
};

8、122. 买卖股票的最佳时机 II - 力扣（LeetCode）------贪心解法

可购买出售多次，策略：只要不赔钱就一直买卖

class Solution {
public:int maxProfit(vector<int>& prices) {int profit=0;for(int i=1;i<prices.size();i++){int tmp=prices[i]-prices[i-1];if(tmp>0) profit+=tmp;}return profit;}
};

9、55. 跳跃游戏 - 力扣（LeetCode）

数组中的每个元素代表你在该位置可以跳跃的最大长度。

策略：看是否可以跳过最大长度为0 的位置

未成清贫难成人，不经挫折永天真；人情似纸张张薄，世事如棋局局新。

class Solution {
public:bool canJump(vector<int>& nums) {int step=1;int i=0;int n=nums.size()-1;for(int i=n-1;i>=0;i--){if(nums[i]>=step){step=0;}step++;}return step==1;}
};

贪心解法：判断并留下之前走的最远的策略和当前策略中最好的，若最好的去不到循环中下一个位置，则失败。

class Solution {
public:bool canJump(vector<int>& nums) {int rightMost=0;int n=nums.size();for(int i=0;i<n;i++){if(i<=rightMost){rightMost=max(rightMost,i+nums[i]) ;         if(rightMost>=n-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(vector<int>& 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(curUnlock>=nums.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 h=0,i=citationsSize-1;while(i>=0&&citations[i]>h){h++;i--;}return h;}

12、380. O(1) 时间插入、删除和获取随机元素 - 力扣（LeetCode）