前两周一直是一道，都不好意思写了。这周终于题目简单了，刷了三道。

1002. Find Common Characters

Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates).  For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer.

You may return the answer in any order.

 

Example 1:

Input: ["bella","label","roller"]Output: ["e","l","l"]

Example 2:

Input: ["cool","lock","cook"]Output: ["c","o"]

 

Note:

1. 1 <= A.length <= 100
2. 1 <= A[i].length <= 100
3. A[i][j] is a lowercase letter

题目大意：给你一个字符串数组，让你输出所有字符串都包含的小写字母，都出现了几次就输出几次。

思路：因为只有小写字母，所以可以将所以字符串字母的出现次数统计出来，然后直接遍历输出就好。就是代码有点难写，可能是我还没有领悟到更好的编写方式，浪费了我大量的时间（差不多一个多小时）。

代码：

class Solution {    public List
      
        commonChars(String[] A) {        List
       
         list = new ArrayList<>();        List
        
       
      

1003. Check If Word Is Valid After Substitutions

We are given that the string "abc" is valid.

From any valid string V, we may split V into two pieces X and Y such that X + Y (X concatenated with Y) is equal to V.  (X or Y may be empty.)  Then, X + "abc" + Y is also valid.

If for example S = "abc", then examples of valid strings are: "abc", "aabcbc", "abcabc", "abcabcababcc".  Examples of invalid strings are: "abccba", "ab", "cababc", "bac".

Return true if and only if the given string S is valid.

 

Example 1:

Input: "aabcbc"Output: trueExplanation: We start with the valid string "abc".Then we can insert another "abc" between "a" and "bc", resulting in "a" + "abc" + "bc" which is "aabcbc".

Example 2:

Input: "abcabcababcc"Output: trueExplanation: "abcabcabc" is valid after consecutive insertings of "abc".Then we can insert "abc" before the last letter, resulting in "abcabcab" + "abc" + "c" which is "abcabcababcc".

Example 3:

Input: "abccba"Output: false

Example 4:

Input: "cababc"Output: false

 

Note:

1. 1 <= S.length <= 20000
2. S[i] is 'a', 'b', or 'c'

题目大意：给出一个基础合法串 abc ，然后不断的将 abc 插入到不同的位置，也就形成了更多的合法串。比如：插入到第二个位置变成 aabcbc  这个也是一个合法串。

思路：最开始想到的就是，按照这么变的话，这些串肯定都是固定的，可以先将这些串都求出来然后再对比。后面一想这样可能耗时更长，于是放弃这个思路。然后仔细一想，如果一个串是合法的，那么我如果一直去掉 abc 串，那么后面肯定就剩下空串了。

代码：

class Solution {    public boolean isValid(String S) {        String valid = "abc";        while( S.lastIndexOf(valid)!=-1 ) {            int begin = S.indexOf(valid);            String s1 = S.substring(0, begin);            String s2 = S.substring(begin+3);            S = s1 + s2;            if( null == S || "".equals(S) ) {                return true;            }        }        return false;    }}

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 = 2Output: 6Explanation: [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 = 3Output: 10Explanation: [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 

题目大意：给出一个只包含 0 和 1的数组，然后给出 一个数字K表示你可以将K个0变成1，让你求最长的连续1字串长度。

题目思路：尺取法，不解释。

class Solution {    public int longestOnes(int[] A, int K) {        int res = 0;        int len = A.length;        int end = 0, begin = 0;        for(int i=0; i
      
       end-begin?res:end-begin;    }}
      

1000. Minimum Cost to Merge Stones

There are N piles of stones arranged in a row.  The i-th pile has stones[i] stones.

A move consists of merging exactly K consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these K piles.

Find the minimum cost to merge all piles of stones into one pile.  If it is impossible, return -1.

 

Example 1:

Input: stones = [3,2,4,1], K = 2Output: 20Explanation: We start with [3, 2, 4, 1].We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].We merge [4, 1] for a cost of 5, and we are left with [5, 5].We merge [5, 5] for a cost of 10, and we are left with [10].The total cost was 20, and this is the minimum possible.

Example 2:

Input: stones = [3,2,4,1], K = 3Output: -1Explanation: After any merge operation, there are 2 piles left, and we can't merge anymore.  So the task is impossible.

Example 3:

Input: stones = [3,5,1,2,6], K = 3Output: 25Explanation: We start with [3, 5, 1, 2, 6].We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6].We merge [3, 8, 6] for a cost of 17, and we are left with [17].The total cost was 25, and this is the minimum possible.

 

Note:

• 1 <= stones.length <= 30
• 2 <= K <= 30
• 1 <= stones[i] <= 100

其实就是石子归并，只不过合并的堆数从2变成了k。还是很简单的，可惜第一题费了我太多时间了，不然应该可以做出来。

class Solution {    public int mergeStones(int[] a, int K) {        int n = a.length;        if(n % (K-1) != 1 % (K-1)){            return -1;        }        int[] cum = new int[n+1];        for(int i = 0;i < n;i++){            cum[i+1] = cum[i] + a[i];        }        int[][] dp = new int[n][n];        for(int len = K;len <= n;len++){            for(int i = 0;i+len-1 < n;i++){                int j = i+len-1;                int cost = Integer.MAX_VALUE;                int ulen = (len-1)/(K-1)*(K-1)+1;                if(ulen % (K-1) == 1 %(K-1)){                    ulen -= K-1;                }                int s = len % (K-1) == 1 % (K-1) ? len-(K-1) : len;                for(int k = i+1;k <= j;k++){                    if((k-i-1)/(K-1) + (j-k+1-1)/(K-1) == (s-1)/(K-1)){                        int c = 0;                        if(i <= k-1)c += dp[i][k-1];                        if(k <= j)c += dp[k][j];                        cost = Math.min(cost, c);                    }                }                if(len % (K-1) == 1 % (K-1)){                    cost += cum[j+1] - cum[i];                }                dp[i][j] = cost;            }        }        return dp[0][n-1];    }}