P4ul
文章
44
分类
14
评论
6

LeetCode 刷题笔记---（三）

| 算法 •
字数总计 10700 | 阅读时长 26分钟 | 阅读量 40

LeetCode刷题笔记---（三）

字节第三弹，看看今天能不能做完

ID：88

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

**注意：**最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

思路历程：相当简单一道题，只要拿一个新的数组然后用归并排序的思想就可以结束

如果不开新空间的话，可以每插入一个元素，后面的元素后移一位。

answer：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> res;
        int i=0;int j=0;
        while(i<m&&j<n){
            if(nums1[i]<nums2[j]){
                res.push_back(nums1[i]);
                i++;
            }else{
                res.push_back(nums2[j]);
                j++;
            }
        }
        while(i<m){
            res.push_back(nums1[i]);
            i++;
        }
        while(j<n){
            res.push_back(nums2[j]);
            j++;
        }
        nums1=res;
    }
};

ID：215

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

思路历程：其实就是快排，唉，我有点忘了，主体思路还记得，细节老是记不住，容易出现越界和超时

回去看了AcWing的笔记，感觉自己手写的时候出了几个问题

  • 每次进入quicksort时，如果l>=r直接return，不然会一直递归调用
  • 交换数据后，记得改下标

唉，AcWing的OJ系统也不是很好，数据比较弱

GPT提供了一份比较标准的

void quickSort(int l, int r, vector<int>& nums) {
    if (l >= r) return;
    int i = l, j = r;
    int pivot = nums[(l + r) / 2]; // 选择中点作为pivot
    while (i <= j) {
        while (nums[i] < pivot) i++;
        while (nums[j] > pivot) j--;
        if (i <= j) {
            swap(nums[i], nums[j]);
            i++;
            j--;
        }
    }
    quickSort(l, j, nums);
    quickSort(i, r, nums);
}

这份模板还是比 那个简洁版更好理解的，至少不用边界往两边扩到越界

然后再do i++ , j--

当然，也可以用堆的方法，不过我这里更想复习快排

也可以根据题目进行变形，将k放在快排里面，去判断选择，会快一点。

ID：92

怎么又是反转链表，第三道了都...

image-20240112142319795

思路历程：就是反转链表加特殊节点，特殊节点一般有逆序前一个节点，逆序中的头尾节点，逆序外的头节点

  • 逆序前的节点和逆序中的头节点可以标记一下
  • 逆序外的节点和逆序中的尾节点一般来说可以在退出循环时获取

answer：


class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(right==1)return head;
        ListNode* cur=head;
        ListNode* pre=nullptr;
        ListNode* tmp=head;
        int count=0,i=0;
        while(tmp->next){
            tmp=tmp->next;
            count++;
        }
        ListNode* knode;
        ListNode* tail;
        ListNode* back;
        while(i<right){
            back=cur->next;
            if(i<left){
                if(i==left-1){
                    knode=pre;
                    tail=cur;
                }
                pre=cur;
                cur=back;
            }else{
                
                cur->next=pre;
                pre=cur;
                cur=back;
            }
            i++;
        }
        if(knode)knode->next=pre;
        if(tail)tail->next=back;
        if(left>1)return head;
        return pre;
    }
};

一般来说都是返回pre的，很少有返回cur的

就算是从开头开始，最后退出循环的pre也是逆序的第一个

ID：852

符合下列属性的数组 arr 称为 山脉数组 ：

  • arr.length >= 3

  • 存在i(0 < i < arr.length - 1)

    使得：

    • arr[0] < arr[1] < ... arr[i-1] < arr[i]

  • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

给你由整数组成的山脉数组 arr ，返回满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。

你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。

思路历程：其实也是二分的变形，跟昨天那道有点像，分类讨论吧

一开始又思路卡住了，还想着用递归来着

其实没必要，跟昨天一样分类讨论就行

如果中间三个递增，移动左指针，递减移动右指针，出现山峰则返回中间坐标，结束

这道题其实挺简单的，花了30分钟不太值

answer：

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int length=arr.size();
        int i=0;int j=length-1;
        while(i<j){
            int mid=(i+j)/2;
            int privot = arr[mid];
            if(mid==0)break;
            if(privot>arr[mid-1]&&privot<arr[mid+1]){
                i=mid;
            }else if(privot<arr[mid-1]&&privot>arr[mid+1]){
                j=mid;
            }else if(privot>arr[mid-1]&&privot>arr[mid+1]){
                return mid;
            }
        }
        return 1;
    }
};

ID：15

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

思路历程：首先排序，

然后判断几种特殊情况，如果全是负数或正数肯定没有结果

其他情况下将数字和下标传入哈希表，然后查看有没有零

有零就可以先把数字分成正负0，判断是否有相反数

没零就得。。。

太麻烦了，我们回顾一下两数之和，三数和为0，是不是相当于两数和为target的相反数

那就逐个输入-target 然后逐个减去剩下的值，然后在哈希表里find即可

！！！！！！！map.find()返回的是迭代器！！！！！！！

做不出来，不知道为什么，就是很奇怪，一直会重复

破案了，哈希法是有问题的，除非额外进行去重操作（判断sort后判断前后关系、写个记录的指针）

更合适的方法是双指针，详见教程

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        map<int,vector<int>> hash;
        sort(nums.begin(),nums.end());
        if(nums.size()<3)return res;
        for(int i=0;i<nums.size();i++){
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int l=i+1,r=nums.size()-1;
            while(l<r){
                int sum=nums[i]+nums[l]+nums[r];
                if(sum>0)r--;
                if(sum<0)l++;
                if(sum==0){
                    res.push_back({nums[i],nums[l],nums[r]});
                    while(l<r&&nums[r]==nums[r-1])r--;
                    while(l<r&&nums[i]==nums[i+1])i++;
                    l++;
                    r--;
                }
            }
        }
        return res;
    }
};

这个思路真的很简单，简述一下

三个指针对应abc，a指针遍历，b，c指针一个放a后面，一个放最后面

我也来解释一下为什么去重要i>0&&nums[i]==nums[i-1]

其中的nums[i]==nums[i-1]主要是为了保证，nums[i]是第一次出现，这样是能检测到下面的结果的

image-20240112164324710

因为b指针指满足后自己会去重，所以下次a直接到2就行了，这样a不用管后面的是否重复，只要保证自己是新的即可

（花了一个小时，了解一下双指针也不错，其实之前的滑动窗口也是双指针）

滑动窗口主要是检测窗口内的数据是否符合，这里的双指针主要是用来检测窗口上的数据是否符合

ID：121

image-20240112165953183

思路历程：一开始想着暴力，但是随着数据增大，确实效率降得很快，后来想了一下，可以用找一些特殊情况提前pass掉

嘶，还是不行，看到了一些比较恶心的样例。。。（从10000降到1）

得看题解该怎么办了...这问题还真没遇到过，超时确实考虑的比较少

image-20240112172010576

我一直在考虑，如果最小值在最大值前面出现，那是最完美的，这样就可以直接得到结果

但是如果不是呢，如果最大值出现在最小值前面，该怎么办，我会想第二大的值，第二小的值，这样是不对的，你其实站在了一个整体的角度去看问题，所以一眼能看出最优解

但是真正落实到一个迭代的过程时，你每天只能算出，这天之前我能获得的最大利润，这天之前我遇到的最低值

对应的，如果今天比最低值低，那么我更新一下，

如果今天能获得的利润更高，我也更新一下，而不是今天的值更高我去更新一下利润，因为利润不一定是你当前值越高，利润越高，而是差值越高利润越高

总结：递减时更新最低值，递增时更新最大利润

0.0 想明白了是不是感觉很简单

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res=0;
        int fmin=10000;
        for(int i=0;i<prices.size();i++){
                fmin=min(fmin,prices[i]);
                res=max(res,prices[i]-fmin);
        }
        return res;
    }
};

不判断递增递减144ms

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res=0;
        int fmin=10000;
        for(int i=0;i<prices.size();i++){
            if(i>0&&prices[i]>prices[i-1]){
                res=max(res,prices[i]-fmin);
            }else{
                fmin=min(fmin,prices[i]);
            }
        }
        return res;
    }
};

判断递增递减 96ms

ID：2085

给你两个字符串数组 words1 和 words2 ，请你返回在两个字符串数组中 都恰好出现一次 的字符串的数目。

花了25分钟，不应该

思路历程：其实就是两张表，然后遍历其中一张就行

我一开始想歪了，一直在想如果再次出现了就erase掉，其实没必要，这样3个相同还会留下来

计数器++就行，最后判断的时候判断两边次数都是1就结束了

answer：

class Solution {
public:
    int countWords(vector<string>& words1, vector<string>& words2) {
        int res=0;
            map<string,int> hash;
            map<string,int> hash2;
            for(string str:words1){
                if(hash.find(str)==hash.end()){
                    hash[str]=1;
                }else{
                    hash[str]++;
                }
            }
            for(string str:words2){
                if(hash2.find(str)==hash2.end()){
                    hash2[str]=1;
                }else{
                    hash2[str]++;
                }
            }
            for(auto c:hash){
                if(c.second==1&&hash2[c.first]==1)res++;
            }
        return res;
    }
};

还剩3题，可惜

今天先到这吧，接着还有嵌入式作业和OS进程要复习

早起喝杯热水，然后点一杯橙C美式，爽捏

不过冰的好像不太好喝，下次可以买热的

（质疑zbh，理解zbh，成为zbh）哈哈哈

文章作者： P4ul
本文链接：
版权声明： 本站所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 打工人驿站！
算法 c++
喜欢就支持一下吧
打赏
微信 微信
支付宝 支付宝