刷题记录

Dynamic progarmming design binary tree linked list 括号问题 DFS

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 two strings  s  and  t , write a function to determine if  t  is an anagram of  s . For example, s  = "anagram",  t  = "nagaram", return true. s  = "rat",  t  = "car", return false. Note: You may assume the string contains only lowercase alphabets. Analysis: Use int[26] to store the word. First round add, second round minus. Then check if there is 0 in int[26]. Solution: class Solution { public boolean isAnagram ( String s, String t) { int [] map = new int [ 26 ]; for ( char c : s . toCharArray()) { map[c - 'a' ] ++ ; } for ( char c : t . toCharArray()) { map[c - 'a' ] -- ; } for ( int n : map) { if (n != 0 ) return false; } return true; } }

Problem: Given an array of  n  integers where  n  > 1,  nums , return an array  output  such that  output[i]  is equal to the product of all the elements of  nums  except  nums[i] . Solve it  without division  and in O( n ). For example, given  [1,2,3,4] , return  [24,12,8,6] . Follow up: Could you solve it with constant space complexity? (Note: The output array  does not  count as extra space for the purpose of space complexity analysis.) Analysis: The single result can be achieved by preProduct left X preProduct right.  [1, 2, 3, 4], the left product array is [1, 1, 2, 6]. Remember the left[i] is the product from nums[0] to nums[i - 1].  Solution: class Solution { public int [] productExceptSelf ( int [] nums) { if (nums == null || nums . length == 0 ) return nums; int [] left = new int [nums . length]; left[ 0 ] = 1 ; int right = 1 ; for ( int i = 1 ; i < nums . length; i +

Problem: Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1. Example 1: Input: [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1. Example 2: Input: [0,1,0] Output: 2 Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1. Analysis: Mirror problem of  Maximum size subarray sum equals k . When encounter 0, presum minus 1, when encounter 1, presum add 1. Solution: class Solution { public int findMaxLength ( int [] nums) { int max = 0 ; Map< Integer , Integer > preSum = new HashMap<> (); int sum = 0 ; preSum . put( 0 , - 1 ); for ( int i = 0 ; i < nums . length; i ++ ) { sum += nums[i] == 1 ? 1 : - 1 ; if (preSum . containsKey(sum)) { max = Math . max(max, i - preSum . get(sum)); } if ( !

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_VALUE ? 0 : res; } }

Problem: Given an array  nums  and a target value  k , find the maximum length of a subarray that sums to  k . If there isn't one, return 0 instead. Note: The sum of the entire  nums  array is guaranteed to fit within the 32-bit signed integer range. Example 1: Given  nums  =  [1, -1, 5, -2, 3] ,  k  =  3 , return  4 . (because the subarray  [1, -1, 5, -2]  sums to 3 and is the longest) Example 2: Given  nums  =  [-2, -1, 2, 1] ,  k  =  1 , return  2 . (because the subarray  [-1, 2]  sums to 1 and is the longest) Analysis: Typical presum and hashmap problem. Note that if we found current sum in hashmap don't update the index, since the existing one is further.  Solution: class Solution { public int maxSubArrayLen ( int [] nums, int k) { int max = 0 ; if (nums == null || nums . length == 0 ) return 0 ; Map< Integer , Integer > preSum = new HashMap<> (); int sum = 0 ; preSum . put(

Problem: Given an array consisting of  n  integers, find the contiguous subarray of given length  k  that has the maximum average value. And you need to output the maximum average value. Example 1: Input: [1,12,-5,-6,50,3], k = 4 Output: 12.75 Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75 Note: 1 <=  k  <=  n  <= 30,000. Elements of the given array will be in the range [-10,000, 10,000]. Analysis: Simplified version of Maximum Subarray IV. Keep a window without updating minSum.  Solution: class Solution { public double findMaxAverage ( int [] nums, int k) { int slowSum = 0 , fastSum = 0 , max = 0 ; for ( int i = 0 ; i < k; i ++ ) { fastSum += nums[i]; } max = fastSum; for ( int i = k; i < nums . length; i ++ ) { slowSum += nums[i - k]; fastSum += nums[i]; max = Math . max(fastSum - slowSum, max); }

Problem: Given an array of integers  nums , write a method that returns the "pivot" index of this array. We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index. If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index. Example 1: Input: nums = [1, 7, 3, 6, 5, 6] Output: 3 Explanation: The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3. Also, 3 is the first index where this occurs. Example 2: Input: nums = [1, 2, 3] Output: -1 Explanation: There is no index that satisfies the conditions in the problem statement. Note: The length of  nums  will be in the range  [0, 10000] . Each element  nums[i]  will be an integer in the range  [-1000, 1000] . Analysis: No need to maintain a perSum array, just get the total, an

Problem: Given a list of  non-negative  numbers and a target  integer  k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of  k , that is, sums up to n*k where n is also an  integer . Example 1: Input: [23, 2, 4, 6, 7], k=6 Output: True Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6. Example 2: Input: [23, 2, 6, 4, 7], k=6 Output: True Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42. Note: The length of the array won't exceed 10,000. You may assume the sum of all the numbers is in the range of a signed 32-bit integer. Analysis: 这道踢的通用价值非常低。面试的时候根本想不出来判断条件。 Solution: Note 0 can not be %.  class Solution { public boolean checkSubarraySum ( int [] nums, int k) { Map< Integer , Integer > map = new HashMap<> (); int sum = 0 ; map . put( 0 , - 1 ); for

Problem: Given an array of integers and an integer  k , you need to find the total number of continuous subarrays whose sum equals to  k . Example 1: Input: nums = [1,1,1], k = 2 Output: 2 Note: The length of the array is in range [1, 20,000]. The range of numbers in the array is [-1000, 1000] and the range of the integer  k  is [-1e7, 1e7].

返回结果不是最终结果 Bianry Tree Maximum Path Sum Balanced Binary Tree 改结构类型 binary tree upside down 114. Flatten Binary Tree to Linked List Divide and conquer 本质上是post order,因为是先知道了左子树和右子树的结果再结合到root。 104. Maximum Depth of Binary Tree Binary Tree Longest Consecutive Sequence Path相关的，传target, 直接比较 binary-tree-longest-consecutive-sequence

Problem: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes). The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000. Example: root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1 Return 3. The paths that sum to 8 are: 1. 5 -> 3 2. 5 -> 2 -> 1 3. -3 -> 11 Analysis: 4/23/2018 update: 用presum的方法更好啊，递归套递归，把自己套晕了。 This problem is underrated, can category to medium. Solution 1 (Top down recursion) : The path sum of root = pathSumFrom(root) + pathSum(root.left) + pathSum(root.right). When implementing pathSumFrom,   when found root.val == sum, don't stop. Cuz' there are cases when the following path's sum would be 0.

用途 ：用来解决sub array sum问题。 构造 ： prefixSum[i] = nums[0] + nums[1] + ....+nums[i - 1] 1 based 用法 ： sum(i ~ j) = prefixSum[j + 1] - prefixSum[i], 其中upperbound is inclusive and lowerbound               is exclusive.  FAQ  为什么要有prefixSum[0] 因为在求sum(0 ~ j)时，为了保证不越界，index 0对应的是prefixSum[1], 否则根据lowerbound exclusive 特性，会出现prefixSum[-1]的情况。 有时候不一定需要构建preSum数组，直接用动态的sum就可以解决问题。比如：            Find Pivot Index  和hashtable合用的时候记住初始化(0 , -1)，得到的subarray length就是i - get(sum)。如果是求maximum subarray, 第二次出现sum就不更新，让sum离现在的位置远些。如果是求方案数，就需要更新hashtable value。             contiguous-array             maximum-size-subarray-sum-equals-k             subarray-sum-equals-k

Problem: Follow up for "Remove Duplicates": What if duplicates are allowed at most  twice ? For example, Given sorted array  nums  =  [1,1,1,2,2,3] , Your function should return length =  5 , with the first five elements of  nums  being  1 ,  1 ,  2 ,  2  and  3 . It doesn't matter what you leave beyond the new length. Analysis: Similar to  Remove Duplicates from Sorted Array  They can have template for allowing k duplicates for each number.  这种题在面试中死都想不出来。。。。太特殊了，得背。而且这么短的题 不太可能出现在on site。 Solution: class Solution { public int removeDuplicates ( int [] nums, int k) { int i = 0 ; for ( int n : nums) { if (i < k || n != nums[i - k]) { nums[i ++ ] = n; } } return i; } }

用l + 1 < r再二次检查的模板。二次检查要遵循mid check。

Problem: Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle. Example 1: Input: [2,2,3,4] Output: 3 Explanation: Valid combinations are: 2,3,4 (using the first 2) 2,3,4 (using the second 2) 2,2,3 Note: The length of the given array won't exceed 1000. The integers in the given array are in the range of [0, 1000]. Analysis: 2sum related problem. Duplicate is allowed. Triangle qualifies the rule that a + b > c, where c > b > a. So that we can check from array's end to start.  Solution: class Solution { public int triangleNumber ( int [] nums) { int res = 0 ; Arrays . sort(nums); for ( int i = nums . length - 1 ; i >= 2 ; i -- ) { int l = 0 , r = i - 1 ; while (l < r) { if (nums[l] + nums[r] > nums[i]) {

Problem: Given an array of  n  integers  nums  and a  target , find the number of index triplets  i, j, k  with  0 <= i < j < k < n  that satisfy the condition  nums[i] + nums[j] + nums[k] < target . For example, given  nums  =  [-2, 0, 1, 3] , and  target  = 2. Return 2. Because there are two triplets which sums are less than 2: [-2, 0, 1] [-2, 0, 3] Analysis: 题意又理解错了，人家并没有要求去重复。If found current sum < target, then from l to r all sums are smaller than target. Similar to  Valid Triangle Number . Solution: class Solution { public int threeSumSmaller ( int [] nums, int target) { int res = 0 ; if (nums == null || nums . length == 0 ) return res; Arrays . sort(nums); for ( int i = 0 ; i < nums . length - 2 ; i ++ ) { int l = i + 1 , r = nums . length - 1 ; while (l < r) { int sum = nums[l] + nums[r] + nums[i]; if (sum < target) {

5/22/2018 update 这次把在外层循环的去重搞忘了。但是自己想到了如何在内层循环去重的l < r这个控制条件。 ----------------------- ----------------------- ----------------------- ----------------------- ----------------------- 2/20/2018 update 幸亏做了第二遍，彻底地把这道题搞懂了。之前的总结还算到位。说一下去除内层循环重复。当找到答案的时候才去重复，没有找到答案重复会自然跳过。比如数组 1,1,3,4,5,5，如果找target 7, 那么l会一直增大知道3，r会一直减小直到5。调整l, r位置应该在去除重复之后，去寻找额外的解。 Solution: class Solution { public List< List< Integer > > threeSum ( int [] nums) { List< List< Integer > > res = new ArrayList<> (); if (nums == null || nums . length == 0 ) return res; Arrays . sort(nums); for ( int i = 0 ; i < nums . length - 2 ; i ++ ) { // remove duplicate if (i > 0 && nums[i] == nums[i - 1 ]) { continue ; } int l = i + 1 , r = nums . length - 1 , sum = 0 - nums[i]; while (l < r) { if (nums[l] + nums[r] ==