Weekly Contest 126

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

1002. Find Common Characters

Given an arrayAof 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<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;
    }
}
View Code

1003. Check If Word Is Valid After Substitutions

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

From any valid stringV, we may splitVinto two piecesXandYsuch thatX + Y(Xconcatenated withY) is equal toV.  (XorYmay be empty.)  Then,X + "abc" + Yis also valid.

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

Returntrueif and only if the given stringSis 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. 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;
    }
}
View Code

1004. Max Consecutive Ones III

Given an arrayAof 0s and 1s, we may change up toKvalues 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]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;
    }
}
View Code

1000. Minimum Cost to Merge Stones

There areNpiles of stones arranged in a row.  Thei-th pile hasstones[i]stones.

A move consists of merging exactlyKconsecutive piles into one pile, and the cost of this move is equal to the total number of stones in theseKpiles.

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 <= 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];
    }
} 
View Code


全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 11:30
仁者伍敌:kpi都懒得刷了属于是
点赞 评论 收藏
分享
06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务