企业官网建设流程全解析

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; Set<Character> 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 List<Integer> findAnagrams(String s, String p) { List<Integer> 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; } }