医院网站建设要素,免费ip地址网站,网络营销专业背景,站长工具网站推广最后更新 一刷 08-Jan-2017 昨天Amazon group面结束#xff0c;刚回家。 国内以前喜欢的女生结婚了#xff0c;嘿嘿...好开心呀~~ 这次面试感觉自己的做法完爆别人#xff0c;比什么2 greedy好多了 总之表现比想象的好#xff0c;最后一面的面试官真是聪明得一逼#xff…最后更新 一刷 08-Jan-2017 昨天Amazon group面结束刚回家。 国内以前喜欢的女生结婚了嘿嘿...好开心呀~~ 这次面试感觉自己的做法完爆别人比什么2 greedy好多了 总之表现比想象的好最后一面的面试官真是聪明得一逼我的思路稍微说她就明白跪了这也太出色了。 我只能说A家对于背题党直接OA拿VIDEO或者OFFER确实水但是有实力的也有比如给我面试的这个印度姐姐屌屌屌。 总之希望自己能过能过。 开始准备Google吧。 言归正传。 一长一短2个String 在长的String里找最短的substring使得substring包含所有短string的字符。 a在短字符串里出现2次substring里也要出现2次才行 2 pointers来做的固定左边右边往右找直到substring满足要求。 在往右的过程中我们可能添加了很多不必要元素 要满足abc 我们在ab baba cba里找找到C的时候添加了baba这段没用的这个时候尝试左边缩进。 比较通过2个int[256]一个是需要的字符数一个是现有的。 Time: O(n) Space: O(1) public class Solution {public String minWindow(String s, String t) {if (s.length() t.length()) return ;int[] need new int[256];int[] count new int[256];for (char c : t.toCharArray()) {need[c];}int right 0;String res ;int minLength Integer.MAX_VALUE;for (int left 0; left s.length(); left) {while (right s.length() !contains(need, count)) {count[s.charAt(right)] ;}if (right - left minLength contains(need, count)) {minLength right - left;res s.substring(left, right);}count[s.charAt(left)] --;}return res;}public boolean contains(int[] need, int[] count) {for (int i 0; i 256; i) {if (need[i] count[i]) {return false;}}return true;}
} 方法二 也是2 pointers和一的做法差不多唯一不同的就是判断是否包含的方法。 方法一是通过比较int[256]来判断是否包含所有character这里有个别的方法。 比如短string是abcde那么总共需要5个字符才能满足。但也不是随便5个字符就能满足只有某些字符才能满足。 比如 一开始是abcde需要5个才能满足而a,b,c,d,e其中任何一个都是有效字符。 假如我们substring中已经有了a和c需要bde此时的有效字符就变成了b,d,e读到b,d,e才可以让需要数字 同理缩进也要判断比如substring里有3个A缩进最左边缩小了1个A那么当前需要的元素数量是不变的因为我们还有2个A可以使用相反如果缩掉了B而我们substring里没有B了总共需要的元素数量就要 if (--chars[s.charAt(right)] 0) {validRead ;} 这个说的是substring读取一个然后判断是否是有效读取把那些-- 之类的给展开就一目了然了后面的 --一样 展开再看。 public class Solution {public String minWindow(String s, String t) {if (s.length() 0 || s.length() t.length()) return ;String res ;int minLength Integer.MAX_VALUE;int[] chars new int[256];for (char c : t.toCharArray()) {chars[c] ;}int need t.length();int validRead 0;int right 0;for (int left 0; left s.length(); left ) {while (right s.length() validRead need) {if (--chars[s.charAt(right)] 0) {validRead ;}}if (validRead need right - left minLength) {minLength right - left;res s.substring(left, right);}if (chars[s.charAt(left)] 0) validRead --; }return res;}
} 方法二是因为后面的题要用到这个办法。 转载于:https://www.cnblogs.com/reboot329/p/6263861.html
