网站建设数据库实验心得,做游戏直播那个网站,荣胜网络 宁波网站建设,网站建设目标 优帮云子数组最大平均数 I
#xff08;非hot100#xff0c;但是滑动窗口的思想可以很好的体现#xff0c;入门滑动窗口很好的题#xff09; 给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。 请你找出平均数最大且 长度为 k 的连续子数组#xff0c;并输出该最大平均数…子数组最大平均数 I
非hot100但是滑动窗口的思想可以很好的体现入门滑动窗口很好的题 给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。 请你找出平均数最大且 长度为 k 的连续子数组并输出该最大平均数。 任何误差小于 10-5 的答案都将被视为正确答案。 输入nums [1,12,-5,-6,50,3], k 4 输出12.75 解释最大平均数 (12-5-650)/4 51/4 12.75 解法1滑动窗口
维持一个滑动窗口窗口大小保持k不变初始化将滑动窗口压满取得第一个滑动窗口的目标值继续滑动窗口每往前滑动一次需要删除一个和添加一个元素
public double findMaxAverage(int[] nums, int k) {double sum 0.0;for(int i0; ik; i){sum nums[i];}double res sum;for(int ik; inums.length; i){sum sumnums[i]-nums[i-k];res Math.max(res,sum);}return res/k;
}无重复字符的最长字串
给定一个字符串 s 请你找出其中不含有重复字符的 最长 子串 的长度。 输入: s “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”所以其长度为 3。 解法1滑动窗口 定义两个指针 start 和 end表示当前处理到的子串是 [start,end]。 [start,end] 始终满足要求无重复字符。 从前往后进行扫描同时维护一个哈希表记录 [start,end] 中每个字符出现的次数。 遍历过程中end 不断自增将第 end 个字符在哈希表中出现的次数加一。 令 right 为 下标 end 对应的字符当满足 map.get(right) 1 时代表此前出现过第 end 位对应的字符。 此时更新 start 的位置使其右移直到不满足 map.get(right) 1 代表 [start,end] 恢复满足无重复字符的条件。同时使用 [start,end] 长度更新答案。
public int lengthOfLongestSubstring(String s) {if(s null || s.length()0) return 0;int[] bit new int[100];int left 0;int res 0;for(int i0; is.length(); i){char c s.charAt(i);//可以用因为bit内维护的是符合要求的子串//符合要求的子串每个元素只能有一个不存在大于1的情况while(bit[c- ]1){bit[s.charAt(left)- ]--;}bit[c- ]1;res Math.max(res,i-left1);}return res;
}func lengthOfLongestSubstring(s string) int {res : 0;charArr : [128]int{}l,r : 0,0lenght : len(s)for rlenght {for charArr[s[r]] ! 0{charArr[s[l]]--l;}charArr[s[r]]if res(r-l1) {res (r-l1)}r}return res
}找到字符串中所有字母异位词
给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串包括相同的字符串。 输入: s “cbaebabacd”, p “abc” 输出: [0,6] 解释: 起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。 起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。 解法1滑动窗口 首先创建一个数组这个数组用来统计两个字符串目标字符串p和当前字串s’之间的差异的 首先将目标字符串p的每个字符统计加入到数组中对于每个字符计算出char-a’之间的差值作为索引将对应索引的值-1. 当统计完目标字符串的数组之后当前数组有若干个索引上的元素为负数表示有多少个相应字符出现在了目标字符串中。 接下来遍历字符串s当当前字串长度和目标字符串长度相同是判断数组是否每个元素都为0为零则说明是异位词否则不是。 判断完之后左侧索引-1相应的索引位置的值-1右侧索引1相应的索引位置的值1
public ListInteger findAnagrams(String s, String p) {ListInteger res new ArrayList();int len p.length();if(lens.length()) return res;int[] charArr new int[26];//首先将目标字符串的所有字符位置变为负数有多少个就变成负多少//后边滑动窗口内维持的字串如果能让数组变为全0则符合要求for(int i0; ilen; i){char c p.charAt(i);charArr[c-a]--;char d s.charAt(i);charArr[d-a];}if(check(charArr)) res.add(0);for(int ilen; is.length(); i){charArr[s.charAt(i-len)-a]--;charArr[s.charAt(i)-a];if(check(charArr)) res.add(i-len1);}return res;
}public boolean check(int[] arr){for(int i0; i26; i){if(arr[i]!0) return false;}return true;
}解法2解法1的优化 解法1中每次对滑动窗口的检查都不可避免需要检查每个词频数组复杂度为 O©。 事实上我们只关心两个数组是否完全一致因而我们能够只维护一个词频数组 cnt 来实现。 起始处理 p 串时只对 cnt 进行词频字符自增操作。当处理 s 的滑动窗口子串时尝试对 cnt 中的词频进行「抵消/恢复」操作 当滑动窗口的右端点右移时增加字符对 cnt 执行右端点字符的「抵消」操作 当滑动窗口的左端点右移时减少字符对 cnt 执行左端点字符的「恢复」操作。 同时使用变量 a 统计 p 中不同字符的数量使用变量 b 统计滑动窗口子串内有多少个字符词频与 p 相等。 当滑动窗口移动 执行「抵消/恢复」时如果「抵消」后该字符词频为 0说明本次右端点右移多产生了一位词频相同的字符如果「恢复」后该字符词频数量为 1说明少了一个为词频相同的字符。当且仅当 ab 时我们找到了一个新的异位组。
class Solution {public ListInteger findAnagrams(String s, String p) {ListInteger ans new ArrayList();int n s.length(), m p.length();int[] cnt new int[26];for (int i 0; i m; i) cnt[p.charAt(i) - a];int a 0;for (int i 0; i 26; i) if (cnt[i] ! 0) a;for (int l 0, r 0, b 0; r n; r) {// 往窗口增加字符进行词频的抵消操作如果抵消后词频为 0说明有一个新的字符词频与 p 完全相等if (--cnt[s.charAt(r) - a] 0) b; // 若窗口长度超过规定将窗口左端点右移执行词频恢复操作如果恢复后词频为 1恢复前为 0说明少了一个词频与 p 完全性相等的字符if (r - l 1 m cnt[s.charAt(l) - a] 1) b--;if (b a) ans.add(l);}return ans;}
}替换后的最长重复字符
给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。 在执行上述操作后返回 包含相同字母的最长子字符串的长度。 输入s “ABAB”, k 2 输出4 解释用两个’A’替换为两个’B’,反之亦然。 解法1滑动窗口 令 l 为符合条件的子串的左端点r 为符合条件的子串的右端点。 使用 count 统计 [l,r] 范围的子串中每个字符串出现的次数。 对于合法的子串而言必然有 sum(所有字符的出现次数) - max(出现次数最多的字符的出现次数 other(其他字符的出现次数) k。 当找到这样的性质之后我们可以对 s 进行遍历每次让 r 右移并计数如果符合条件更新最大值如果不符合条件让 l 右移更新计数直到符合条件。
