做感恩网站的图片素材,论坛网站建设模板,青岛网站建设报价,ui设计 接单网站刷题日记#xff1a;面试经典 150 题 DAY6 392. 判断子序列167. 两数之和 II - 输入有序数组11. 盛最多水的容器15. 三数之和209. 长度最小的子数组 392. 判断子序列
原题链接 392. 判断子序列
双指针#xff0c;i指向s#xff0c;j指向t
如果s[i]t[j]#xff0c;则匹配… 刷题日记面试经典 150 题 DAY6 392. 判断子序列167. 两数之和 II - 输入有序数组11. 盛最多水的容器15. 三数之和209. 长度最小的子数组 392. 判断子序列
原题链接 392. 判断子序列
双指针i指向sj指向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:vectorint twoSum(vectorint numbers, int target) {for(int i 0, j numbers.size()-1;i j;) {if(numbers[i]numbers[j] target) {return {i1 , j1};}if(numbers[i]numbers[j] target) {i;}if(numbers[i]numbers[j] target) {j--;}}return {};}
};11. 盛最多水的容器
原题链接 11. 盛最多水的容器
容积等于 两个板子相差的距离×较矮板子的的高。使用双指针从最宽的底开始接下里考虑移动哪个指针
若移动指向较高板子的指针则底一定变小高也一定变小因为高总是较低板子的高所以只能移动指向较低板子的指针
class Solution {
public:int maxArea(vectorint 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:vectorvectorint threeSum(vectorint nums) {int len nums.size();sort(nums.begin(), nums.end());vectorvectorint 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 i1, k len-1;j k;) {int sum nums[i]nums[j]nums[k];if(sum 0) {for(j 1;jk nums[j-1]nums[j];j);} else if(sum0) {for(k - 1;jk nums[k1]nums[k];k--);} else {result.push_back({nums[i],nums[j],nums[k]});for(j 1;jk nums[j-1]nums[j];j);for(k - 1;jk nums[k1]nums[k];k--);}}}return result;}
};209. 长度最小的子数组
原题链接 209. 长度最小的子数组
想象数组是一组竖杆杆与杆之间距离不一。有个皮筋现在是松弛状态想要找到能让它绷紧时跨越最少的竖杆。 先给皮筋套在最左边然后抻右端直到皮筋紧然后一点点松左端直到恰好送掉然后在抻右端重复这个步骤
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int len nums.size();int ans len1;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;}
};
