LeetCode Weekly Contest 28解题思路

LeetCode Weekly Contest 28解题思路

赛题

本次周赛主要分为以下4道题：

• 551 Student Attendance Record I (3分)
• 553 Optimal Division (6分)
• 555 Split Assembled Strings (8分)
• 552 Student Attendance Record II (10分)

551 Student Attendance Record I

Problem:

You are given a string representing an attendance record for a student. The record only contains the following three characters: ‘A’ : Absent. ‘L’ : Late. ‘P’ : Present. A student could be rewarded if his attendance record doesn’t contain more than one ‘A’ (absent) or more than two continuous ‘L’ (late). You need to return whether the student could be rewarded according to his attendance record.

Example 1:

Input: “PPALLP” Output: True

Example 2:

Input: “PPALLL” Output: False

注意是连续的L，所以有如下代码：

public boolean checkRecord(String s){
        int[] map = new int[26];
        for (int i = 0; i < s.length(); i++){
            map[s.charAt(i)-'A']++;
        }

        if (map['A'-'A'] > 1) return false;

        int countL = 1;
        for (int i = 1; i < s.length(); i++){
            if (s.charAt(i-1) == 'L' && s.charAt(i) == s.charAt(i-1)){
                countL ++;
            }else{
                if (countL > 2) return false;
                countL = 1;
            }
        }

        if (countL > 2) return false;

        return true;
    }

时间复杂度为O(n)O(n)

553 Optimal Division

Problem:

Given a list of positive integers, the adjacent integers will perform the float division. For example, [2,3,4] -> 2 / 3 / 4. However, you can add any number of parenthesis at any position to change the priority of operations. You should find out how to add parenthesis to get the maximum result, and return the corresponding expression in string format. Your expression should NOT contain redundant parenthesis.

Example:

Input: [1000,100,10,2] Output: “1000/(100/10/2)” Explanation: 1000/(100/10/2) = 1000/((100/10)/2) = 200 However, the bold parenthesis in “1000/((100/10)/2)” are redundant, since they don’t influence the operation priority. So you should return “1000/(100/10/2)”. Other cases: 1000/(100/10)/2 = 50 1000/(100/(10/2)) = 50 1000/100/10/2 = 0.5 1000/100/(10/2) = 2

Note:

• The length of the input array is [1, 10].
• Elements in the given array will be in range [2, 1000].
• There is only one optimal division for each test case.

好吧，不要被这道题的例子给骗了。要求输出的最大，意思就是求除第一个元素之外的其他division最小，而不断连除就是第二部分的最小值，所以有如下代码：

public String optimalDivision(int[] nums) {

        if (nums.length == 1){
            return nums[0]+"";
        }

        if(nums.length == 2){
            return nums[0] + "/" + nums[1];
        }

        String ans = nums[0] + "/(";
        for (int i = 1; i < nums.length; i++) {
            ans += nums[i] + "/";
        }

        ans = ans.substring(0, ans.length()-1) + ")";

        return ans;
    }

555 Split Assembled Strings

Problem:

Given a list of strings, you could assemble these strings together into a loop. Among all the possible loops, you need to find the lexicographically biggest string after cutting and making one breakpoint of the loop, which will make a looped string into a regular one. So, to find the lexicographically biggest string, you need to experience two phases:

• Assemble all the strings into a loop, where you can reverse some strings or not and connect them in the same order as given.
• Cut and make one breakpoint in any place of the loop, which will make a looped string into a regular string starting from the character at the cutting point.

And your job is to find the lexicographically biggest one among all the regular strings.

Example:

Input: “abc”, “xyz” Output: “zyxcba” Explanation: You can get the looped string “-abcxyz-“, “-abczyx-“, “-cbaxyz-“,”-cbazyx-“, where ‘-’ represents the looped status. The answer string came from the fourth looped one, where you could cut from the middle and get “zyxcba”.

Note:

• The input strings will only contain lowercase letters.
• The total length of all the strings will not over 1000.

简单的一个想法，对所用情况进行遍历，总共有2n2^n种情况，然后依次对每种可能的loop求一个lexicographically biggest string，这显然会超时，看看AC解。

    public String splitLoopedString(String[] strs) {

        int n = strs.length;

        String max = "";

        for (int i = 0; i < n; i++){
            StringBuilder ans = new StringBuilder();
            for (int j = i + 1; j < n; j++) ans.append(bigger(strs[j]));
            for (int j = 0; j < i; j++) ans.append(bigger(strs[j]));

            int is = strs[i].length();
            for (int j = 0; j < is; j++){
                String c = strs[i].substring(j, is)+ ans.toString() + strs[i].substring(0, j);
                if (c.compareTo(max) > 0) max = c;
            }

            for (int j = 0; j < is; j++){
                String c = reverse(strs[i]).substring(j,is) + ans.toString() + reverse(strs[i]).substring(0,j);
                if (c.compareTo(max) > 0) max = c;
            }

        }

        return max;
    }

    private String reverse(String x){
        return new StringBuilder(x).reverse().toString();
    }

    private String bigger(String x){
        return reverse(x).compareTo(x) > 0 ? reverse(x) : x;
    }

总结两点： 1. 字典序的循环比较放在了局部范围，在单个字符串上进行字典序比较时，需同时考虑正序和逆序。 2. 其他字符串，全部已lexicographically最大输出，因为在链接时，一定只会出现和头或者尾相连，而不可能出现其他情况。

所以时间复杂度控制在了O(n⋅min(n,m))O(n \cdot min(n,m))，其中m表示为字符串的最大长度。实际提交代码时，用了StringBuilder去拼接字符串，而用String直接进行字符串拼接时超时，这需要注意下。

552 Student Attendance Record II

Problem:

Given a positive integer n, return the number of all possible attendance records with length n, which will be regarded as rewardable. The answer may be very large, return it after mod 109 + 7. A student attendance record is a string that only contains the following three characters: ‘A’ : Absent. ‘L’ : Late. ‘P’ : Present. A record is regarded as rewardable if it doesn’t contain more than one ‘A’ (absent) or more than two continuous ‘L’ (late).

Example 1:

Input: n = 2 Output: 8 Explanation: There are 8 records with length 2 will be regarded as rewardable: “PP” , “AP”, “PA”, “LP”, “PL”, “AL”, “LA”, “LL” Only “AA” won’t be regarded as rewardable owing to more than one absent times.

我的想法：遍历所有”A”,”L”,”P”出现的情况，在它的生成路径上，去除不必要的子树分支，所以代码如下：

    public int checkRecord(int n) {
        build(n, 1, "");
        return count;
    }

    int count = 0;
    private void build(int n, int start, String ans){

        if (!checkRecord(ans) && !ans.isEmpty()){
            return;
        }

        if (start == n + 1){
            count ++;
            return;
        }

        build(n, start+1, ans + "A");
        build(n, start+1, ans + "L");
        build(n, start+1, ans + "P");
    }


    public boolean checkRecord(String s){
        int[] map = new int[26];
        for (int i = 0; i < s.length(); i++){
            map[s.charAt(i)-'A']++;
        }

        if (map['A'-'A'] > 1) return false;

        int countL = 1;
        for (int i = 1; i < s.length(); i++){
            if (s.charAt(i-1) == 'L' && s.charAt(i) == s.charAt(i-1)){
                countL ++;
            }else{
                if (countL > 2) return false;
                countL = 1;
            }
        }

        if (countL > 2) return false;

        return true;
    }

最navie的想法，但很明显这种做法必将超时，它是一道动态规划的题，刚好最近在总结动态规划，所以这里直接贴出此题答案，在动态规划系列中详细分析它。

public int checkRecord(int n){
        int MOD = 1000000007;

        int[][][] dp = new int[n+1][2][3];

        dp[0] = new int[][]{{1,1,1},{1,1,1}};

        for (int i = 1; i <= n; i++){
            for (int j = 0; j < 2; j++){
                for (int k = 0; k < 3; k ++){
                    int val = dp[i-1][j][2];
                    if (j > 0) val = (val + dp[i-1][j-1][2]) % MOD;
                    if (k > 0) val = (val + dp[i-1][j][k-1]) % MOD;
                    dp[i][j][k] = val;
                }
            }
        }

        return dp[n][1][2];
    }