Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Topic describes

This is 1004 on LeetCode. Maximum number of consecutive 1s III, medium difficulty.

Tag: “Double pointer”, “sliding window”, “bisection”, “prefix and”

Given an array A consisting of A number of 000 and 111, we can change at most KKK values from 000 to 111.

Returns the length of the longest (continuous) subarray containing only 111.

Example 1:

Input: A = [1,1,1,0,0,0,1,1,1, 0], K = 2 Output: 6 Description: [1,1,1, 1,1] The bold digits are flipped from 0 to 1, and the longest subarray length is 6.Copy the code

Example 2:

Input: A =,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1 [0], K = 3 output: 10: ,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1 [0] turn bold Numbers from 0 to 1, the longest length of the subarray to 10.Copy the code

Tip:


  • 1 < = A . l e n g t h < = 20000 1 <= A.length <= 20000

  • 0 < = K < = A . l e n g t h 0 <= K <= A.length
  • A[I]A[I]A[I] is 000 or 111

Dynamic programming (TLE)

So in this case, DP comes to mind first, but DP is O(nk)O(nk)O(NK) algorithm.

We see that the data range is 10410^4104, so the time and space complexity should be 10810^8108.

The space can be optimized to 10410^4104 by “scrolling array”, but the time cannot be optimized and will time out.

PS. When are we going to use DP? If K is of the order of 1000 or less, DP should be the most common practice.

Define f[I,j]f[I,j]f[I,j] to represent the maximum length of continuous 111 when considering the number of first iii (and ending with A[I]A[I]A[I]A[I]).

  • If A [I] A [I] A [I] itself is 1, consume without turning, [I] [j] f = f [I – 1) + 1 f [j] [I] [j] = f] [I – 1 + 1 f [j] [I] [j] = f [I – 1) [j] + 1.
  • If A[I]A[I]A[I]A[I] is not 1, the definition must end with A[I]A[I]A[I]A[I]. [I] [j] f = f [I – 1) + 1 f [j – 1] [I] [j] = f [I – 1]] [j – 1 + 1 f [I] [j] = f [I – 1] [j – 1) + 1.

Code:

class Solution {
    public int longestOnes(int[] nums, int k) {
        int n = nums.length;
        int[][] f = new int[2][k + 1]; 
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                if (nums[i - 1] = =1) {
                    f[i & 1][j] = f[(i - 1) & 1][j] + 1;
                } else {
                    f[i & 1][j] = j == 0 ? 0 : f[(i - 1) & 1][j - 1] + 1;
                }
                ans = Math.max(ans, f[i & 1][j]); }}returnans; }}Copy the code
  • O(nk)O(nk)O(nk)
  • Space complexity: O(k)O(k)O(k)

Prefix and + dichotomy

From the data range analysis, the square level of the algorithm can not pass, the downward optimization should be logarithmic level of the algorithm.

So it’s easy to think of dichotomy.

And, of course, we need to do the equivalent transformation of the problem.

The maximum number of substitutions is not exceededkThe problem can be converted to finding a contiguous interval[l,r], so that the number of occurrences of 0 in the interval does not exceedkTimes.

We can enumerate the left/right endpoints of the interval, and then find the farthest right/furthest left endpoints that satisfy “zero occurs no more than k times”.

To quickly determine the number of zeros between [l,r], we need prefixes and.

Assuming that the interval length of [L,r] is len and the interval sum is tot, then the format of the occurrence of 0 is len-toL and then compared with K.

Since there are no negative weights in the array, the prefix and array are “monotonic”, so it must satisfy that “one of the segments satisfies len−tol<= klen-tol <=klen −tol<=k, Another paragraph does not satisfy len−tol<= klen-tol <=klen −tol<=k.

Therefore, for a certain “left endpoint/right endpoint”, the prefix and number line with “its farthest right endpoint/furthest left endpoint” as the segmentation point have “dichotomy”. You can find the split point by dividing.

Code:

class Solution {
    public int longestOnes(int[] nums, int k) {
        int n = nums.length;
        int ans = 0;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
        for (int i = 0; i < n; i++) {
            int l = 0, r = i;
            while (l < r) {
                int mid = l + r >> 1;
                if (check(sum, mid, i, k)) {
                    r = mid;
                } else {
                    l = mid + 1; }}if (check(sum, r, i, k)) ans = Math.max(ans, i - r + 1);
        }
        return ans;
    }
    boolean check(int[] sum, int l, int r, int k) {
        int tol = sum[r + 1] - sum[l], len = r - l + 1;
        returnlen - tol <= k; }}Copy the code
  • O(nlog⁡n)O(n\log{n})O(nlogn)
  • Space complexity: O(n)O(n)O(n)

About the dichotomy after the end againcheckSince the essence of “dichotomy” is to find a partition point that satisfies a property, usually a property of ours will be “non-equivalent conditions”, not necessarily achieved=.

For example, we are familiar with finding the target value in some non-decrement array, return the subscript if found, otherwise return -1.

When the target value does not exist, binary should find the closest number in the array that is smaller or larger than the target value. So after the end of the dichotomy, proceed firstcheckReuse is a good habit.

Double pointer

Because we’re always comparing Len, tot, and K.

Therefore, we can use the idea of “sliding Windows” to dynamically maintain a left and right interval [j, I] and maintain in-window and TOT.

The right endpoint keeps moving right, and the left endpoint moves right when the window does not meet “Len-tol <= K”, thus the complexity of thread scanning can be achieved.

Code:

class Solution {
    public int longestOnes(int[] nums, int k) {
        int n = nums.length;
        int ans = 0;
        for (int i = 0, j = 0, tot = 0; i < n; i++) {
            tot += nums[i];
            while ((i - j + 1) - tot > k) tot -= nums[j++];
            ans = Math.max(ans, i - j + 1);
        }
        returnans; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

conclusion

In addition to mastering the problem solutions, I want you to understand how these solutions came to be thought of (in particular, how to go from “dynamic programming” to “dichotomy”).

The analytical ability to adapt the algorithm you use to the data range (complexity) is more important than the problem itself.

The last

This is the No.1004 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode by the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.