刷题记录

Problem: Given two strings  s1  and  s2 , write a function to return true if  s2  contains the permutation of  s1 . In other words, one of the first string's permutations is the  substring  of the second string. Example 1: Input: s1 = "ab" s2 = "eidbaooo" Output: True Explanation: s2 contains one permutation of s1 ("ba"). Example 2: Input: s1= "ab" s2 = "eidboaoo" Output: False Analysis: Find All Anagarms in a String 的马甲题，简化版。。。 Solution: class Solution { public boolean checkInclusion ( String s1, String s2) { if (s1 . length() > s2 . length()) { return false; } int [] map = new int [ 256 ]; for ( char c : s1 . toCharArray()) { map[c] ++ ; } int l = 0 , r = 0 , counter = s1 . length(); while (r < s2 . length()) { if (map[s2 . charAt(r ++ )] -- > 0 ) counter -- ; if (counter == 0 ...

Problem: Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). For example, S  =  "ADOBECODEBANC" T  =  "ABC" Minimum window is  "BANC" . Note: If there is no such window in S that covers all characters in T, return the empty string  "" . If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S. 5/7/2018 update: A more concise solution: class Solution { public String minWindow ( String s, String t) { if (s == null || s . length() == 0 ) return "" ; int l = 0 , r = 0 , start = 0 , len = Integer . MAX_VALUE, count = t . length(); int [] map = new int [ 256 ]; for ( char c : t . toCharArray()) { map[c] ++ ; } while (r < s . length()) { if (map[s . charAt(r ++ )] -- > ...

Problem : Given a string  s  and a  non-empty  string  p , find all the start indices of  p 's anagrams in  s . Strings consists of lowercase English letters only and the length of both strings  s  and  p  will not be larger than 20,100. The order of output does not matter. Example 1: Input: s: "cbaebabacd" p: "abc" Output: [0, 6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc". Example 2: Input: s: "abab" p: "ab" Output: [0, 1, 2] Explanation: The substring with start index = 0 is "ab", which is an anagram of "ab". The substring with start index = 1 is "ba", which is an anagram of "ab". The substring with start index = 2 is "ab", which is an anagram of "ab". Analysis: 这道题用brute force做很简单。如果用sliding window做...

Problem : Given an array of  n  positive integers and a positive integer  s , find the minimal length of a  contiguous  subarray of which the sum ≥  s . If there isn't one, return 0 instead. For example, given the array  [2,3,1,2,4,3]  and  s = 7 , the subarray  [4,3]  has the minimal length under the problem constraint. Analysis: Sliding window problem. update the window when sum >= s. Solution: class Solution { public int minSubArrayLen ( int s, int [] nums) { int res = Integer . MAX_VALUE; if (nums == null || nums . length == 0 ) { return 0 ; } int left = 0 , sum = 0 ; for ( int i = 0 ; i < nums . length; i ++ ) { sum += nums[i]; while (sum >= s) { res = Math . min(res, i - left + 1 ); sum -= nums[left ++ ]; } } return res == Integer . MAX_...

Problem: Given a string, find the length of the longest substring T that contains at most  k  distinct characters. For example, Given s =  “eceba”  and k = 2, T is "ece" which its length is 3. 3/1/2018 update: Solution follow template: class Solution { public int lengthOfLongestSubstringKDistinct ( String s, int k) { if (s == null || s . length() == 0 ) return 0 ; int l = 0 , r = 0 , counter = 0 , res = 0 ; int [] map = new int [ 256 ]; while (r < s . length()) { if (map[s . charAt(r ++ )] ++ == 0 ) counter ++ ; // not satisfy while (counter > k) { // move left pointer if (map[s . charAt(l ++ )] -- == 1 ) counter -- ; } // update result res = Math . max(res, r - l); } return res; } } Analysis: The key point of this sort of problem is t...

Problem: Given a string, find the length of the  longest substring  without repeating characters. Examples: Given  "abcabcbb" , the answer is  "abc" , which the length is 3. Given  "bbbbb" , the answer is  "b" , with the length of 1. Given  "pwwkew" , the answer is  "wke" , with the length of 3. Note that the answer must be a  substring ,  "pwke"  is a  subsequence  and not a substring.