leetcode contest 126

#1027

Summary by bigelephant29 (Chinese)

1000. Minimum Cost to Merge Stones (Hard - 9 points)

• see lee215's solution [Java/C++/Python] DP

1003. Check If Word Is Valid After Substitutions

•  string "abc" is valid.
•  (X or Y may be empty.)  Then, X + "abc" + Y is also valid.
• E.g. "abc", "aabcbc" is valid
  "cababc" is invalid

by lee215 [Java/Python/C++] Stack Solution O(N)

    bool isValid(string S) {
        vector<char> stack;
        for (char c : S) {
            if (c == 'c') {
                int n = stack.size();
                if (n < 2 || stack[n - 1] != 'b' || stack[n - 2] != 'a') return false;
                stack.pop_back(), stack.pop_back();
            } else {
                stack.push_back(c);
            }
        }
        return stack.size() == 0;
    }

My first attempt in the contest O(n^2)

  bool isValid(string S) {
    const string k = "abc";
    while (!S.empty()) {
      size_t p = S.find(k);
      if (p == string::npos)
        return false;
      S.erase(p, k.size());
    }
    return true;
  }

1004. Max Consecutive Ones III

Given an array A of 0s and 1s, we may change up to K values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s. 

Example 1:

Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
Output: 6
Explanation: 
[1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

Example 2:

Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
Output: 10
Explanation: 
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

Note:

1. 1 <= A.length <= 20000
2. 0 <= K <= A.length
3. A[i] is 0 or 1 

by lee215 [Java/C++/Python] Sliding Window

  // lee215's solution
  // 60 ms
  int longestOnes(vector<int>& A, int K) {
    const unsigned n = A.size();
    unsigned i = 0, j = 0;
    //    [11000000], k = 2
    // => [11110000], k = -4, i = 4
    //
    //    [10000110], k = 2
    // => [1111]  k = -1, i = 1
    // => [10111] k = -1, i = 2
    // => [1001111] k = 0, i = 3
    // => [10001111] k = 0, i = 4
    for (; j < n; ++j) {
      if (A[j] == 0) --K;
      if (K < 0 && A[i++] == 0) ++K;
    }
    return n - i;
  }

  // my first attempt in the contest
  // 60 ms.
  int longestOnes(vector<int>& A, int K) {
    // [1,1,1,0,0,0,1,1,1,1,0]
    // [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
    const unsigned n = A.size();
    int maxl = 0, curmax = 0;
    int curk = K, j = 0;
    for (int i = 0; i < n; ++i) {
      if (A[i]) {
        ++curmax;
      } else {
        if (curk) {
          --curk;
          ++curmax;
        } else {
          // curk = 0
          maxl = max(curmax, maxl);
          if (curk < K) {
            for (int k = j; k < i; ++k) {
              if (A[k] == 0) {
                j = k + 1;
                break;
              }
              --curmax;
            }              
            //cout << curmax << " " << j << endl;
          } else {
            curmax = 0;
          }
        }
      }
    }
    return max(curmax, maxl);
  }