当前位置: 首页 > article >正文

刷题日记:面试经典 150 题 DAY6

刷题日记:面试经典 150 题 DAY6

  • 392. 判断子序列
  • 167. 两数之和 II - 输入有序数组
  • 11. 盛最多水的容器
  • 15. 三数之和
  • 209. 长度最小的子数组

392. 判断子序列

原题链接 392. 判断子序列

双指针,i指向s,j指向t

  • 如果s[i]==t[j],则匹配到一个字母,两个指针都后移
  • 如果s[i]!=t[j],则指针j后移继续寻找
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int i = 0, j = 0;
        if(s.size() == 0) return true;
        while(i < s.size() && j < t.size()) {
            if(s[i] != t[j]) {
                j++;
                if(j >= t.size()) {
                    return false;
                }
            } else {
                i++, j++;
                if(i >= s.size()) {
                    return true;
                }
            }
        }
        return false;
    }
};

167. 两数之和 II - 输入有序数组

原题链接 167. 两数之和 II - 输入有序数组
双指针本质上是对搜索空间进行某种顺序的遍历,一般都会用得上某种单调性
对于题来说,搜索空间如下所示
在这里插入图片描述

  • 选择棕色作为起点,是因为从这里出发可以仅通过(向左,向右)两个动作到达任意一个状态,。这保证了不会有答案被漏,
  • 比起爆搜来说可以提升性能的原因在于,利用单调性进行搜索的剪枝。比如我们得知当前状态比目标状态大时,就可以确定一系列状态都不可能是目标状态了。在这里插入图片描述
    从实现上来说,就是一个指针位于数列头部,一个位于尾部,两个指针逐渐向中间靠拢
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for(int i = 0, j = numbers.size()-1;i < j;) {
            if(numbers[i]+numbers[j] == target) {
                return {i+1 , j+1};
            }
            if(numbers[i]+numbers[j] < target) {
                i++;
            }
            if(numbers[i]+numbers[j] > target) {
                j--;
            }
        }
        return {};
    }
};

11. 盛最多水的容器

原题链接 11. 盛最多水的容器

容积等于 两个板子相差的距离×较矮板子的的高。使用双指针,从最宽的底开始,接下里考虑移动哪个指针

  • 若移动指向较高板子的指针,则底一定变小,高也一定变小(因为高总是较低板子的高)
  • 所以只能移动指向较低板子的指针
class Solution {
public:
    int maxArea(vector<int>& height) {
        int result = 0;
        for(int i = 0, j = height.size()-1;i < j;) {
            result = max(result,(j-i)*min(height[i],height[j]));
            if(height[i] < height[j]) {
                i++;
            } else {
                j--;
            }
        }
        return result;
    }
};

15. 三数之和

爆搜 O ( N 3 ) O(N^3) O(N3),可以比较简单的想到先排序,再固定一个数就可以使用双指针了。
我一开始脑抽,想着固定中间大小的那个(老是想追求对称性导致的),直接处理重复情况处理闷了。
固定最小的数比较好做。把最小数固定其实就回到了167. 两数之和 II - 输入有序数组。注意两点

  • 最外层循环遍历到正数就可以立马停止
  • 每次移动指针时,都尽可能到达连续相同元素的尾部,防止重复的情况发生
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
	    int len = nums.size();
	    sort(nums.begin(), nums.end());
	    vector<vector<int>> result;
	    for(int i = 0;i < len-2;i++) {
            if(nums[i] > 0) break;
            if(i > 0 && nums[i-1] == nums[i]) continue;
            for(int j = i+1, k = len-1;j < k;) {
                int sum = nums[i]+nums[j]+nums[k];
                if(sum < 0) {
                    for(j += 1;j<k && nums[j-1]==nums[j];j++);
                } else if(sum>0) {
                    for(k -= 1;j<k && nums[k+1]==nums[k];k--);
                } else {
                    result.push_back({nums[i],nums[j],nums[k]});
                    for(j += 1;j<k && nums[j-1]==nums[j];j++);
                    for(k -= 1;j<k && nums[k+1]==nums[k];k--);
                }
            }
        }
	    return result;
    }
};

209. 长度最小的子数组

原题链接 209. 长度最小的子数组

想象数组是一组竖杆,杆与杆之间距离不一。有个皮筋,现在是松弛状态,想要找到能让它绷紧时跨越最少的竖杆。
先给皮筋套在最左边,然后抻右端,直到皮筋紧,然后一点点松左端,直到恰好送掉,然后在抻右端,重复这个步骤

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int len = nums.size();
        int ans = len+1;
        int left = 0, right = 0;
        int length = 0;
        int sum = 0;
        while(right < len) {
            sum += nums[right];
            length++;
            while(sum >= target) {
                ans = min(ans,length);
                sum -= nums[left];
                length--;
                left++;
            }
            right++;
        }
        if(ans > len) return 0;
        return ans;
    }
};

http://www.kler.cn/a/274338.html

相关文章:

  • 学工管理系统-职校信息化管理平台
  • RunCam WiFiLink连接手机图传测试
  • 多协议视频监控汇聚/视频安防系统Liveweb搭建智慧园区视频管理平台
  • 【服务器】MyBatis是如何在java中使用并进行分页的?
  • [Python学习日记-73] 面向对象实战1——答题系统
  • C语言进阶(2) ---- 指针的进阶
  • SCI一区 | Matlab实现GWO-TCN-BiGRU-Attention灰狼算法优化时间卷积双向门控循环单元融合注意力机制多变量时间序列预测
  • php前端和java后端数据调用流程
  • F-logic DataCube3 任意文件上传漏洞复现(CVE-2024-25832)
  • 【C++】用红黑树模拟实现set、map
  • 学习笔记--强化学习(1)
  • 使用jQuery的autocomplete实现数据查询一次,联想自动补全
  • Apache Dolphinscheduler - 无需重启 Master-Server 停止疯狂刷日志解决方案
  • Linux下安装Android Studio及创建桌面快捷方式
  • 【论文阅读】Improved Denoising Diffusion Probabilistic Models
  • mysql逗号分隔字段拆成行简述
  • Redis的安装和部署教程(Windows环境)
  • 全球变暖(蓝桥杯,acwing每日一题)
  • 【DL经典回顾】激活函数大汇总(二十五)(GEGLU附代码和详细公式)
  • 金蝶云星空——插件dll重新发布报错:鏃犳硶鏄剧ず椤甸潰锛屽洜涓哄彂鐢熷唴閮ㄦ湇鍔″櫒閿欒銆�
  • tesseract ocr 安装/调用/训练
  • 使用Java JDBC连接数据库
  • c语言指针(二)
  • 概率统计在AI中的作用
  • Java项目利用Redisson实现真正生产可用高并发秒杀功能 支持分布式高并发秒杀
  • 在线教育平台帮助教培机构打造线上