湘潭网站建设 找磐石网络一流,南京哪家做网站好,网站建设的功能模块,上海软件外包公司名单文章目录前言一、二分查找#xff08;力扣724#xff09;二、移除元素#xff08;力扣27#xff09;【双指针】三、有序数组的平方#xff08;力扣977#xff09;【双指针】四、合并两个有序数组#xff08;力扣88#xff09;五、长度最小的子数组#xff08;力扣209力扣724二、移除元素力扣27【双指针】三、有序数组的平方力扣977【双指针】四、合并两个有序数组力扣88五、长度最小的子数组力扣209【滑动窗口】六、水果成篮力扣904【滑动窗口】****七、最小覆盖子串力扣76【滑动窗口】****八、最大连续1的个数 III力扣1004【滑动窗口】九、无重复字符的最长子串力扣3【滑动窗口】****总结前言
1、二分查找 2、移除元素 3、有序数组的平方 4、合并两个有序数组 5、长度最小的子数组 6、水果成篮 7、最小覆盖字串 8、最大连续1的个数||| 9、无重复字符的最长字串 一、二分查找力扣724
给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。
class Solution {public int search(int[] nums, int target) {int left;int right;int mid;int index -1;left 0;right nums.length-1;while(leftright){mid (leftright)/2;if(nums[mid]target){rightmid-1;}else if(nums[mid]target){leftmid1;}else if (nums[mid]target){return mid;}}return index; }
}二、移除元素力扣27【双指针】
给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。 不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
class Solution {public int removeElement(int[] nums, int val) {int fast;int slow;for(fast0,slow0; fastnums.length;){if(nums[fast]val){fast;}else{nums[slow] nums[fast];}}return slow;}
}三、有序数组的平方力扣977【双指针】
有一个按 非递减顺序 排序的整数数组 nums返回 每个数字的平方 组成的新数组要求也按 非递减顺序 排序。 暴力求解省略 每个数平方之后排个序美滋滋 时间复杂度O(n nlogn)
class Solution {public int[] sortedSquares(int[] nums) {int[] res new int[nums.length];int slow0;int fastnums.length-1;int index nums.length-1;for(slow0,fastnums.length-1;slowfast;){if(nums[slow]*nums[slow]nums[fast]*nums[fast]){res[index--]nums[slow]*nums[slow]; slow;}else{res[index--]nums[fast]*nums[fast];fast--;}}return res;}
}时间复杂度O(n)
四、合并两个有序数组力扣88
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2另有两个整数 m 和 n 分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中使合并后的数组同样按 非递减顺序 排列。
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int i m-1;int j n-1;int index nums1.length-1;for(;j0;){if(i0||nums1[i]nums2[j]){nums1[index--] nums2[j];j--;}else{nums1[index--] nums1[i];i--;}}}
}注意要考虑边界条件
五、长度最小的子数组力扣209【滑动窗口】
给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl1, …, numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。 暴力求解 两个for循环然后不断的寻找符合条件的子序列时间复杂度很明显是O(n^2)。 for (int i 0; i nums.length; i) { // 设置子序列起点为isum 0;for (int j i; j nums.length; j) { // 设置子序列终止位置为jsum nums[j];if (sum s) { // 一旦发现子序列和超过了s更新resultsubLength j - i 1; // 取子序列的长度result result subLength ? result : subLength;break; // 因为我们是找符合条件最短的子序列所以一旦符合条件就break}}滑动窗口 滑动窗口就是不断的调节子序列的起始位置和终止位置从而得出我们要想的结果 在暴力解法中是一个for循环滑动窗口的起始位置一个for循环为滑动窗口的终止位置用两个for循环 完成了一个不断搜索区间的过程。那么滑动窗口用一个for循环来完成这个操作。
滑动窗口问题一如果用一个for循环那么应该表示 滑动窗口的起始位置还是终止位置 滑动窗口问题二如何遍历剩下的终止位置 滑动窗口问题三滑动窗口的起始位置如何移动
class Solution {public int minSubArrayLen(int target, int[] nums) {int left 0;int right;int subLength Integer.MAX_VALUE; int res0;//滑动窗口一个for循环表示滑动窗口终止位置for(right0;rightnums.length;right){resnums[right];while(restarget){subLength Math.min(subLength,right-left1);res - nums[left];}}return subLength Integer.MAX_VALUE? 0:subLength;}
}六、水果成篮力扣904【滑动窗口】****
fruits[i] 是第 i 棵树上的水果 种类 。 想要尽可能多地收集水果。然而农场的主人设定了一些严格的规矩你必须按照要求采摘水果 只有 两个 篮子并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。 你可以选择任意一棵树开始采摘你必须从 每棵 树包括开始采摘的树上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次你将会向右移动到下一棵树并继续采摘。 一旦走到某棵树前但水果不符合篮子的水果类型那么就必须停止采摘。 给你一个整数数组 fruits 返回可以收集的水果的最大数目。
白话题意求满足某个条件数组值最多就两类的连续数组例如[1,2,2,1,2]的最长数组长度
class Solution {public int totalFruit(int[] fruits) {HashMapInteger,Integer map new HashMap();int res 0;int i0;int j0;while(jfruits.length){//判断当前是否满足条件map.put(fruits[j],map.getOrDefault(fruits[j],0)1);while(map.size()2){//不满足条件//把加进来i的都移出去map.put(fruits[i],map.get(fruits[i])-1);if(map.get(fruits[i])0){map.remove(fruits[i]);}i;}//更新结果res Math.max(res,j-i1);j;}return res;}
}For me 比较考验map数组的使用
七、最小覆盖子串力扣76【滑动窗口】****
一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 “” 。
同样是滑动窗口这两题有什么区别区别在于904题求的是最大滑窗而本题求的是最小滑窗
class Solution {public String minWindow(String s, String t) {//最小滑动窗口int[] need new int[128];//记录t中需要字符的个数for(int i 0; it.length();i){need[t.charAt(i)];}int i0;int j0;String res ;int count t.length();int size Integer.MAX_VALUE;int start 0;while(js.length()){//判断是否满足条件if(need[s.charAt(j)]0){count--;}need[s.charAt(j)]--; //把右边字符加入窗口while(count0){ //满足条件 窗口中已经包含所有元素// 一旦满足条件尽可能的压缩i并且不断更新结果//更新结果值while(ij need[s.charAt(i)]0){ //压缩左窗口need[s.charAt(i)];i;}if(j-i1size){size j-i1; //更新结果值start i; //需要记录窗口的起始位置}need[s.charAt(i)];i;count;}j;}return size Integer.MAX_VALUE? :s.substring(start,startsize);}
}窗口扩展时寻找可行解窗口收缩时优化可行解。而且这个题可行解每次都是一个
八、最大连续1的个数 III力扣1004【滑动窗口】
给定一个二进制数组 nums 和一个整数 k如果可以翻转最多 k 个 0 则返回 数组中连续 1 的最大个数 。 最大滑动窗口
class Solution {public int longestOnes(int[] nums, int k) {int i 0;int j 0;int size 0;int zeroCount 0;while(jnums.length){ //滑动窗口终止位置//判断是否满足条件 把k个0翻转为1if(nums[j]0 ){zeroCount;}//不满足条件while(zeroCountk){//缩小左边界一旦左边界满足 就退出循环尽可能取到窗口的最大长度if(nums[i]0){zeroCount--;}i;}//更新结果size Math.max(size,j-i1);j;}return size;}
}九、无重复字符的最长子串力扣3【滑动窗口】****
给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。 取滑动窗口最大值
class Solution {public int lengthOfLongestSubstring(String s) {if(s.length()0) return 0;//最大滑动窗口int i0;int j0;int size 0;HashMapCharacter,Integer map new HashMap();while(js.length()){if(map.containsKey(s.charAt(j))){ //看当前的字符串中是否有重复的i Math.max(i,map.get(s.charAt(j))1);}map.put(s.charAt(j),j);size Math.max(size,j-i1);j;}return size;}
}总结
滑动窗口模板 来源滑动窗口模板参考链接
最小滑窗模板给定数组 nums定义滑窗的左右边界 i, j求满足某个条件的滑窗的最小长度。
while j len(nums):判断[i, j]是否满足条件while 满足条件不断更新结果(注意在while内更新)i 1 最大程度的压缩i使得滑窗尽可能的小j 1最大滑窗模板给定数组 nums定义滑窗的左右边界 i, j求满足某个条件的滑窗的最大长度。
while j len(nums):判断[i, j]是否满足条件while 不满足条件i 1 最保守的压缩i一旦满足条件了就退出压缩i的过程使得滑窗尽可能的大不断更新结果注意在while外更新j 1
