239. Sliding Window Maximum
根本想不到用Deque做 维护一个Deque 里面存放着每一段最大的元素的下标 【 】 每次向右移动的时候 在加入新元素之前把Deque里所有小于当前要加入的元素的都删除 并且注意移除最左边的元素(通过下标判断！)
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> q = new ArrayDeque<Integer>();
int n = nums.length;
int[] res = new int[n - k + 1];
if(nums == null || k == 0)return new int[0];
for(int i = 0;i < n;i++){
//delete the left element
if(!q.isEmpty() && q.peekFirst() == i - k){
q.pollFirst();
}
//delete the element smaller than the newly added one
while(!q.isEmpty() && nums[q.peekLast()] < nums[i]){
q.pollLast();
}
q.offer(i);
if(i + 1 >= k){
res[i+1-k] = nums[q.peek()];
}
}
return res;
}
}
159. Longest Substring with At Most Two Distinct Characters
缩进窗口 左指针从左向右缩进 外层循环是右指针 区别是这里删除的方法不同是用HashMap 维持hashmap的大小小于2
but how do we decide the move method of the two pointers? Like we keep moving forward the left pointer j here, like keeping a window size 2(count the number of unique element)
/** so we keep a hashmap and count the map's key number,keep two pointer
* if we discover that there are more than two distinct number
* move the left pointer to the last right pointer */
public class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s){
int len = s.length();
if(s == null||len == 0){
return 0;
}
//the map that holds the appearance time of each character
Map<Character, Integer> map = new HashMap<Character, Integer>();
int maxLen = 0;
//the left pointer
int j = 0;
char[] arr = s.toCharArray();
for (int i = 0; i < s.length(); i++) {
char element = arr[i];
if (!map.containsKey(element)) {
map.put(element, 1);
while (j < i && map.size() > 2) {
char cur = s.charAt(j);
//如果当前的元素只有一个的话，直接remove?如果有好几个则逐一删除，更改在map里对应的元素数量
if (map.get(cur) == 1) {
map.remove(cur);
} else {
int tmp = map.get(s.charAt(j)) - 1;
map.put(s.charAt(j), tmp);
}
j++;
}
}
else {
map.put(element, map.get(element) + 1);
}
maxLen = Math.max(maxLen, i - j + 1);
}
return maxLen;
}
}
340. Longest Substring with At Most K Distinct Characters
和上一题思路一样
public class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
if(s == null||s.length() == 0||k == 0){
return 0;
}
int len = s.length();
int left = 0;
int maxresult = 0;
Map<Character, Integer> map = new HashMap<Character, Integer>();
char[] arr = s.toCharArray();
for(int i = 0;i < len;i++){
char c = arr[i];
if(map.containsKey(c)){
map.put(c,map.get(c) + 1);
}
else{
map.put(c,1);
while(map.size() > k){
char cur = s.charAt(left);
if(map.get(cur) == 1){
map.remove(cur);
}
else{
map.put(cur,map.get(cur)-1);
}
left++;
}
}
maxresult = Math.max(maxresult,i - left + 1);
}
return maxresult;
}
}
76. Minimum Window Substring
推进右指针到满足需求 然后在维持需求的情况下缩进左指针
这道题是字符串处理的题目，和
Substring with Concatenation of All Words
思路非常类似，同样是建立一个字典，然后维护一个窗口。区别是在这道题目中，因为可以跳过没在字典里面的字符（也就是这个串不需要包含且仅仅包含字典里面的字符，有一些不在字典的仍然可以满足要求），所以遇到没在字典里面的字符可以继续移动窗口右端，而移动窗口左端的条件是当找到满足条件的串之后，一直移动窗口左端直到有字典里的字符不再在窗口里。在实现中就是维护一个HashMap，一开始key包含字典中所有字符，value就是该字符的数量，然后遇到字典中字符时就将对应字符的数量减一。
算法的时间复杂度是O(n),其中n是字符串的长度，因为每个字符再维护窗口的过程中不会被访问多于两次。空间复杂度则是O(字典的大小)，也就是代码中T的长度。代码如下：
public class Solution {
public String minWindow(String S, String T){
if(S==null || S.length()==0)return "";
//Build the dictionary
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for(int i = 0; i < T.length();i++)
{
if(map.containsKey(T.charAt(i)))
{
map.put(T.charAt(i),map.get(T.charAt(i))+1);
}
else
{
map.put(T.charAt(i),1);
}
}
int left = 0;
int count = 0;
int minLen = S.length() + 1;
int finalLeft = 0;
//Move forward the right pointer
for(int right = 0; right < S.length();right++)
{
if(map.containsKey(S.charAt(right)))
{
map.put(S.charAt(right),map.get(S.charAt(right))-1);
if(map.get(S.charAt(right)) >= 0)
{
count++;
}
//维护基本要求的前提下 推进左指针 并记录最后退出的值
while(count == T.length())
{
if(right - left + 1 < minLen)
{
minLen = right-left+1;
finalLeft = left;
}
//leave out the left element means the mappings is deduced(go back by 1) in the original mapping
if(map.containsKey(S.charAt(left)))
{
map.put(S.charAt(left), map.get(S.charAt(left)) + 1);
if(map.get(S.charAt(left)) > 0)
{
count--;
}
}
left++;
}
}
}
if(minLen > S.length())
{
return "";
}
return S.substring(finalLeft,finalLeft + minLen);
}
}
30. Substring with Concatenation of All Words
思路一样 只是判断的String 在外层循环的设置上 有技巧 i + len i不用是整个字符的长度
public ArrayList<Integer> findSubstring(String S, String[] L) {
// Note: The Solution object is instantiated only once and is reused by each test case.
ArrayList<Integer> res = new ArrayList<Integer>();
if(S==null || S.length()==0 || L==null || L.length==0)
return res;
HashMap<String,Integer> map = new HashMap<String,Integer>();
for(int i=0;i<L.length;i++)
{
if(map.containsKey(L[i]))
{
map.put(L[i],map.get(L[i])+1);
}
else
{
map.put(L[i],1);
}
}
for(int i=0;i<L[0].length();i++)
{
HashMap<String,Integer> curMap = new HashMap<String,Integer>();
int count = 0;
int left = i;
for(int j=i;j<=S.length()-L[0].length();j+=L[0].length())
{
String str = S.substring(j,j+L[0].length());
if(map.containsKey(str))
{
if(curMap.containsKey(str))
curMap.put(str,curMap.get(str)+1);
else
curMap.put(str,1);
if(curMap.get(str)<=map.get(str))
count++;
else
{
while(curMap.get(str)>map.get(str))
{
String temp = S.substring(left,left+L[0].length());
if(curMap.containsKey(temp))
{
curMap.put(temp,curMap.get(temp)-1);
if(curMap.get(temp)<map.get(temp))
count--;
}
left += L[0].length();
}
}
if(count == L.length)
{
res.add(left);
//if(left<)
String temp = S.substring(left,left+L[0].length());
if(curMap.containsKey(temp))
curMap.put(temp,curMap.get(temp)-1);
count--;
left += L[0].length();
}
}
else
{
curMap.clear();
count = 0;
left = j+L[0].length();
}
}
}
return res;
}