Divide-Conquer

题目要求Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.Note:A naive algorithm of O(n2) is trivial. You MUST do better than that.Example:Input: nums = [-2,5,-1], lower = -2, upper = 2,Output: 3 Explanation: The three ranges are : [0,0], [2,2], [0,2] and their respective sums are: -2, -1, 2.这道题目是指，现有一个整数数组，并输入上界值upper和下界值lower，问数组中一共有多少组连续的子数组，其子数组中数字的和在上界和下界之内。思路一：暴力循环我们可以首先遍历一遍数组，计算子数组下标[0,i）的所有元素的和。根据该结果可以计算自数组[i,j)中所有元素的和。接着计算所有子数组中元素的和，并判断是否位于数值区间内。代码如下： public int countRangeSum(int[] nums, int lower, int upper) { long[] sums = new long[nums.length+1]; for(int i = 0 ; i<nums.length ; i++) { sums[i+1] = sums[i] + nums[i]; } int count = 0; for(int i = 0 ; i<nums.length ; i++) { for(int j = i+1 ; j<=nums.length ; j++) { if(sums[j] - sums[i] >= lower && sums[j] - sums[i] <= upper) { count++; } } } return count; }思路二：分治法分治法的核心思路在于，将计算整个数组的符合条件的子数组的问题切分为子问题，将数组一分为二，并分别计算左子数组的符合条件的子数组个数，右子数组中符合条件的子数组个数和横穿左右数组的符合条件的子数组个数。计算横穿左右的子数组个数的方法很有趣，这采用了归并排序的思想，即无论左子数组中的元素或是右子数组中的元素如何变动，横穿左右的子数组个数都不会受影响。因此，在对左右子数组进行排序后，以左子数组中的每一位作为开头，在右子数组中找到满足upper和lower区间的第一个值，和超过upper区间的第一个值。则二者的差即为横穿左右的满足条件的子数组个数。 public int countRangeSum3(int[] nums, int lower, int upper) { long[] sums = new long[nums.length + 1]; for(int i = 0 ; i<nums.length ; i++) { sums[i+1] = sums[i] + nums[i]; } long[] sortedSums = new long[nums.length + 1]; return mergeCountRangeSum3(sums, sortedSums, 0, nums.length+1, lower, upper); } public int mergeCountRangeSum3(long[] sums,long[] sortedSums, int start, int end, int lower, int upper) { if(end - start <= 1) return 0; int mid = (start + end) / 2; int count = mergeCountRangeSum3(sums, sortedSums, start, mid, lower, upper) + mergeCountRangeSum3(sums, sortedSums, mid, end, lower, upper); int firstLargerThanUpper = mid, firstLargerThanLower = mid, indexOfRightHalf = mid; for(int i = start, sortedSumsIndex = start; i < mid ; i++, sortedSumsIndex++) { while(firstLargerThanUpper < end && sums[firstLargerThanUpper] - sums[i] <= upper) firstLargerThanUpper++; while(firstLargerThanLower < end && sums[firstLargerThanLower] - sums[i] <lower) firstLargerThanLower++; while(indexOfRightHalf < end && sums[indexOfRightHalf] < sums[i]) sortedSums[sortedSumsIndex++] = sums[indexOfRightHalf++]; sortedSums[sortedSumsIndex] = sums[i]; count += firstLargerThanUpper - firstLargerThanLower; } System.arraycopy(sortedSums, start, sums, start, indexOfRightHalf - start); return count; } ...

题目要求Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.Example 1:Input:s = “aaabb”, k = 3Output:3The longest substring is “aaa”, as ‘a’ is repeated 3 times.Example 2:Input:s = “ababbc”, k = 2Output:5The longest substring is “ababb”, as ‘a’ is repeated 2 times and ‘b’ is repeated 3 times.找出字符串中的最长子字符串，满足该子字符串中任何字符出现的次数都大于k。思路和代码这是一个经典的分治法解决的问题，关键在于我们如何将这个问题分解为更小的子问题。反过来想，这个子字符串一定不包含什么元素呢？当一个元素出现的总次数小于k，那么该元素一定不在子字符串中，只需要将其作为分界点，分别找出左半部分和右半部分的满足条件的最长子字符串。 public int longestSubstring(String s, int k) { return longestSubstring(s, k, 0, s.length()-1); } public int longestSubstring(String s, int k, int left, int right) { if(left > right) { return 0; } int[] count = new int[26]; for(int i = left ; i<=right ; i++) { count[s.charAt(i) - ‘a’]++; } int result = right - left + 1; for(int i = left ; i<=right ; i++) { if(count[s.charAt(i)-‘a’] < k && count[s.charAt(i)-‘a’] > 0) { int leftLongest = longestSubstring(s, k, left, i-1); int rightLongest = longestSubstring(s, k, i+1, right); result = Math.max(leftLongest, rightLongest); break; } } return result; } ...