42.接雨水输入height [0,1,0,2,1,0,1,3,2,1,2,1]输出6解释上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。思路如下首先确定双指针解法因此有left,right两个变量。left,right_max为最大值ans为最终答案left 不大于 right时无限循环二者向中心逼近。height[left]大于right时变动left即短的一边长的一边留下。left_max与height[left]比较如果height[left]大于max则替换max成为新的墙否则为ans加新的left_max - height[left]left 换到下一个柱子right同理可得。class Solution { public int trap(int[] height) { int left 0,right height.length - 1; int left_max 0,right_max 0; int ans 0; while(left right){ if(height[left] height[right]){ if(left_max height[left]){ left_max height[left]; } else{ ans left_max - height[left]; } left; } else{ if(right_max height[right]){ if(right_max height[right]){ right_max height[right]; } else{ ans right_max - height[right]; } } right--; } } return ans; }11.盛水最多的容器给定一个长度为n的整数数组height。有n条垂线第i条线的两个端点是(i, 0)和(i, height[i])。找出其中的两条线使得它们与x轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。求面积宽度为right - left;height 为 left和right中更小的那个。area为两者乘积ans取最大值class Solution { public int maxArea(int[] height) { int left 0,right height.length -1; int ans 0,area 0; int height1 0; while(left right){ int width right - left; height1 Math.min(height[left],height[right]); area height1 * width; ans Math.max(area,ans); if(height[left] height[right]){ left 1; } else{ right - 1; } } return ans; } }3.无重复字符的最长子串示例 1:输入:s abcabcbb输出:3解释:因为无重复字符的最长子串是 abc所以其长度为 3。注意 bca 和 cab 也是正确答案。示例 2:输入:s bbbbb输出:1解释:因为无重复字符的最长子串是 b所以其长度为 1。滑动窗口解法有left right两个指针新建一个HashSet用于存储字符进行比较当right小于 字符串长度时无限循环直到等于即遍历结束当set1中不包含时加入set1 求得ans取max 并且right扩展滑动窗口存在时代表重复remove掉left left即窗口向右缩小一格。class Solution { public int lengthOfLongestSubstring(String s) { int left 0,right 0; int ans 0; SetCharacter set1 new HashSet(); while(right s.length()){ while(set1.contains(s.charAt(right))){ set1.remove(s.charAt(left)); left; } set1.add(s.charAt(right)); ans Math.max(ans,right - left 1); right; } return ans; } }439.找到字符串中所有异位词class Solution { public ListInteger findAnagrams(String s, String p) { ListInteger ans new ArrayList(); int n s.length(),pk p.length(); if(n pk){ return ans; } //初始化 int[] cnts new int[26]; for(int i 0;i pk;i){ cnts[s.charAt(i) - a]; cnts[p.charAt(i) - a]--; } if(allzero(cnts)) ans.add(0); //偏移 for(int i pk;i n;i){ cnts[s.charAt(i) - a]; cnts[s.charAt(i - pk) - a]--; if(allzero(cnts)) ans.add(i- pk 1); } return ans; } private boolean allzero(int[] cnts){ for(int c :cnts ){ if (c ! 0){ return false; } } return true; } }
42.接雨水输入height [0,1,0,2,1,0,1,3,2,1,2,1]输出6解释上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。思路如下首先确定双指针解法因此有left,right两个变量。left,right_max为最大值ans为最终答案left 不大于 right时无限循环二者向中心逼近。height[left]大于right时变动left即短的一边长的一边留下。left_max与height[left]比较如果height[left]大于max则替换max成为新的墙否则为ans加新的left_max - height[left]left 换到下一个柱子right同理可得。class Solution { public int trap(int[] height) { int left 0,right height.length - 1; int left_max 0,right_max 0; int ans 0; while(left right){ if(height[left] height[right]){ if(left_max height[left]){ left_max height[left]; } else{ ans left_max - height[left]; } left; } else{ if(right_max height[right]){ if(right_max height[right]){ right_max height[right]; } else{ ans right_max - height[right]; } } right--; } } return ans; }11.盛水最多的容器给定一个长度为n的整数数组height。有n条垂线第i条线的两个端点是(i, 0)和(i, height[i])。找出其中的两条线使得它们与x轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。求面积宽度为right - left;height 为 left和right中更小的那个。area为两者乘积ans取最大值class Solution { public int maxArea(int[] height) { int left 0,right height.length -1; int ans 0,area 0; int height1 0; while(left right){ int width right - left; height1 Math.min(height[left],height[right]); area height1 * width; ans Math.max(area,ans); if(height[left] height[right]){ left 1; } else{ right - 1; } } return ans; } }3.无重复字符的最长子串示例 1:输入:s abcabcbb输出:3解释:因为无重复字符的最长子串是 abc所以其长度为 3。注意 bca 和 cab 也是正确答案。示例 2:输入:s bbbbb输出:1解释:因为无重复字符的最长子串是 b所以其长度为 1。滑动窗口解法有left right两个指针新建一个HashSet用于存储字符进行比较当right小于 字符串长度时无限循环直到等于即遍历结束当set1中不包含时加入set1 求得ans取max 并且right扩展滑动窗口存在时代表重复remove掉left left即窗口向右缩小一格。class Solution { public int lengthOfLongestSubstring(String s) { int left 0,right 0; int ans 0; SetCharacter set1 new HashSet(); while(right s.length()){ while(set1.contains(s.charAt(right))){ set1.remove(s.charAt(left)); left; } set1.add(s.charAt(right)); ans Math.max(ans,right - left 1); right; } return ans; } }439.找到字符串中所有异位词class Solution { public ListInteger findAnagrams(String s, String p) { ListInteger ans new ArrayList(); int n s.length(),pk p.length(); if(n pk){ return ans; } //初始化 int[] cnts new int[26]; for(int i 0;i pk;i){ cnts[s.charAt(i) - a]; cnts[p.charAt(i) - a]--; } if(allzero(cnts)) ans.add(0); //偏移 for(int i pk;i n;i){ cnts[s.charAt(i) - a]; cnts[s.charAt(i - pk) - a]--; if(allzero(cnts)) ans.add(i- pk 1); } return ans; } private boolean allzero(int[] cnts){ for(int c :cnts ){ if (c ! 0){ return false; } } return true; } }
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
