前两周一直是一道，都不好意思写了。这周终于题目简单了，刷了三道。
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 <= A.length <= 1001 <= A[i].length <= 100-
A[i][j]is a lowercase letter
题目大意：给你一个字符串数组，让你输出所有字符串都包含的小写字母，都出现了几次就输出几次。
思路：因为只有小写字母，所以可以将所以字符串字母的出现次数统计出来，然后直接遍历输出就好。就是代码有点难写，可能是我还没有领悟到更好的编写方式，浪费了我大量的时间（差不多一个多小时）。
代码：
class Solution {
public List<String> commonChars(String[] A) {
List<String> list = new ArrayList<>();
List<Map<Character, Integer> > maps = new ArrayList<>();
for(String str : A ) {
if( null != str ) {
int len = str.length();
Map<Character, Integer> map = new HashMap<>();
for(int i=0; i<len; i++) {
char ch = str.charAt(i);
Integer cnt = map.get(ch);
if( null == cnt ) cnt = Integer.valueOf(0);
cnt ++;
map.put(ch, cnt);
}
maps.add(map);
}
}
for(char ch = 'a'; ch<='z'; ch ++) {
int last = 105;
for(Map<Character, Integer> m : maps ) {
Integer cnt = m.get(ch);
if( null == cnt ) cnt = Integer.valueOf(0);
if( cnt < last ) last = cnt;
}
while( last != 105 && last > 0 ) {
list.add(""+ch);
last --;
}
}
return 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: true
Explanation:
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: true
Explanation:
"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 <= S.length <= 20000-
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 = 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 <= A.length <= 200000 <= K <= A.length-
A[i]is0or1
题目大意：给出一个只包含 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<len; i++) {
if( A[i] == 0 ) {
if( K == 0 ) {
if( res < end-begin ) res = end-begin;
while( A[begin] == 1 ) begin ++;
begin ++;
} else K --;
}
end ++;
}
return res>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 = 2
Output: 20
Explanation:
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 = 3
Output: -1
Explanation: 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 = 3
Output: 25
Explanation:
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 <= 302 <= K <= 301 <= 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];
}
}