刷题记录

Problem: right corner ( row 2,  col 2). The above rectangle (with the red border) is defined by (row1, col1) =  (2, 1)  and (row2, col2) =  (4, 3) , which contains sum =  8 . Example: Given matrix = [ [3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5] ] sumRegion(2, 1, 4, 3) -> 8 sumRegion(1, 1, 2, 2) -> 11 sumRegion(1, 2, 2, 4) -> 12 Note: You may assume that the matrix does not change. There are many calls to  sumRegion  function. You may assume that  row 1 ≤  row 2 and  col 1 ≤  col 2. Analysis: 和mutable那道思路一样的。只是在算sum的时候用到了dp. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class NumMatrix { int [][] dp ; public NumMatrix ( int [][] matrix ) { if ( matrix . length == 0 || matrix [ 0 ]. length == 0 ) return; int m = matrix . length , n = matrix [ 0 ]. length ; dp = ...

Problem: Given an integer array  nums , find the sum of the elements between indices  i  and  j  ( i  ≤  j ), inclusive. Example: Given nums = [-2, 0, 3, -5, 2, -1] sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3 Note: You may assume that the array does not change. There are many calls to  sumRange  function. Analysis: Easy problem, use prefix sum. Solution: class NumArray { int [] sums; public NumArray ( int [] nums) { if (nums != null && nums . length != 0 ) { sums = new int [nums . length + 1 ]; for ( int i = 0 ; i < nums . length; i ++ ) { sums[i + 1 ] = sums[i] + nums[i]; } } } public int sumRange ( int i, int j) { return sums[j + 1 ] - sums[i]; } }

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 ...

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  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 ; ...

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 ...

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...

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...

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].

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

思路： 一看到求连续sum的就要考虑prefixsum。 代码如下： public class Solution { /* * @param nums: a list of integers. * @param k: length of window. * @return: the sum of the element inside the window at each moving. */ public int[] winSum(int[] nums, int k) { // write your code here int[] preSum = new int[nums.length + 1]; List<Integer> list = new ArrayList<>(); for(int i = 1; i <= nums.length; i++) { preSum[i] = preSum[i-1] + nums[i-1]; if(i >= k) { list.add(preSum[i] - preSum[i - k]); } } int[] res = new int[list.size()]; int i = 0; for(int n: list) { res[i++] = n; } return res; } }

思路： 这道题十分无聊，求non-overlapping 2个sub array加起来最大的和。先把从左往右的max subarray求出来，再求从右往左的。然后遍历数组，打擂台 max = Math.max(max, left[i] + right[i + 1]) 。为什么parameter要用List不用数组，有什么意义？难道是要我们掌握nums.get(i)。 还有一道更无聊的题 Maximum Subarray Difference，真是体力活，一共要求4个数组分别是leftMax[], leftMin[], rightMax[], rightMin[]。如果有公司面试面这种题，那肯定是公司面试官脑子进水了。

Problem: Given an array consisting of  n  integers, find the contiguous subarray whose  length is greater than or equal to   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: when length is 5, maximum average value is 10.8, when length is 6, maximum average value is 9.16667. Thus return 12.75. Note: 1 <=  k  <=  n  <= 10,000. Elements of the given array will be in range [-10,000, 10,000]. The answer with the calculation error less than 10 -5  will be accepted. Analysis: 6/20/2018 update: Use binary search to guess the average value. And make sure the error is within 0.00001. To compare the average, for instance, a1, a2, a3, a4 and b1, b2, b3, b4. If (a1-b1) + (a2-b2)  + (a3-b3) + (a4-b4) > 0, we can tell that a's average is greater than b. preSum is the sum that k away from current...

Problem: Given an integer arrays, find a contiguous subarray which has the largest sum and length should be greater or equal to given length  k . Return the largest sum, return 0 if there are fewer than k elements in the array. Analysis: 2/26/2018 update 这道题的坑真多。 1. corner case include when k > nums.length 2. sliding window problem, maxSum's inital value needs to be sum(0, k). 3. Maintain a minSum that k distance away from the current location. Solution: public class Solution { /** * @param nums: an array of integer * @param k: an integer * @return : the largest sum */ public int maxSubarray4 ( int [] nums, int k) { // write your code here if (nums == null || nums . length == 0 || nums . length < k) { return 0 ; } int minSum = 0 , sum = 0 , min = 0 , max = 0 ; for ( int i = 0 ; i < k; i ++ ) { max += nums[i]; } sum = max; ...

Problem: Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number. 2/23/2018 update Again well explained below. Solution with better format: public class Solution { /* * @param nums: A list of integers * @return: A list of integers includes the index of the first number and the index of the last number */ class Pair { int index; int sum; public Pair ( int index, int sum) { this . index = index; this . sum = sum; } } public int [] subarraySumClosest ( int [] nums) { // write your code here if (nums == null || nums . length == 0 ) return new int []{}; Pair [] pairs = new Pair [nums . length + 1 ]; pairs[ 0 ] = new Pair ( - 1 , 0 ); int sum = 0 ; for ( int i = 0 ; i < nums . length; i ++ ) { sum += nums[i]; pairs[...