LeetCode Weekly Contest 28

发表于   |   分类于   |  

LeetCode Weekly Contest 28
[2017-04-16]

  1. Student Attendance Record I
  2. Optimal Division
  3. Split Assembled Strings
  4. Student Attendance Record II

Student Attendance Record I

You are given a string representing an attendance record for a student. The record only contains the following three characters:

  1. ‘A’ : Absent.
  2. ‘L’ : Late.
  3. ‘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:

1
2
Input: "PPALLP"
Output: True

Example 2:

1
2
Input: "PPALLL"
Output: False

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool checkRecord(string s) {
        multiset<char> ss;
        int continuousL  = 0;
        for(int i = 0; i < s.length(); i++){
            if(continuousL == 2){
                if(s[i] == 'L'){
                    return false;
                }
            }
            if(s[i] == 'L'){
                continuousL++;
            }else{
                continuousL = 0;
            }
            ss.insert(s[i]);        
        }
        return ss.count('A') <= 1;
    }
};

Optimal Division

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:

1
2
3
4
5
6
7
8
9
10
11
12
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:

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

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public String optimalDivision(int[] nums) {
        StringBuilder builder = new StringBuilder();
        builder.append(nums[0]);
        for (int i = 1; i < nums.length; i++) {
            if (i == 1 && nums.length > 2) {
                builder.append("/(").append(nums[i]);
            } else {
                builder.append("/").append(nums[i]);
            }
        }
        
        return nums.length > 2 ? builder.append(")").toString() : builder.toString();
    }
}

Split Assembled Strings

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:

  1. Assemble all the strings into a loop, where you can reverse some strings or not and connect them in the same order as given.
  2. 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:

1
2
3
4
5
6
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:

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

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public String splitLoopedString(String[] strs) {
        for (int i = 0; i < strs.length; i++) {
            String rev = new StringBuilder(strs[i]).reverse().toString();
            if (strs[i].compareTo(rev) < 0)
                strs[i] = rev;
        }
        String res = "";
        for (int i = 0; i < strs.length; i++) {
            String rev = new StringBuilder(strs[i]).reverse().toString();
            for (String st: new String[] {strs[i], rev}) {
                for (int k = 0; k < st.length(); k++) {
                    StringBuilder t = new StringBuilder(st.substring(k));
                    for (int j = i + 1; j < strs.length; j++)
                        t.append(strs[j]);
                    for (int j = 0; j < i; j++)
                        t.append(strs[j]);
                    t.append(st.substring(0, k));
                    if (t.toString().compareTo(res) > 0)
                        res = t.toString();
                }
            }
        }
        return res;
    }
}

Student Attendance Record II

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:

  1. ‘A’ : Absent.
  2. ‘L’ : Late.
  3. ‘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:

1
2
3
4
5
6
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.

Note: The value of n won’t exceed 100,000.

code

dp[i]the number of all possible attendance (without ‘A’) records with length i :

  • end with “P”: dp[i-1]
  • end with “PL”: dp[i-2]
  • end with “PLL”: dp[i-3]
  • end with “LLL”: is not allowed

so dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

the number of all possible attendance (with ‘A’) records with length n:
∑dp[i] *dp[n-1-i] i = 0,1,…,n-1

Time Complexity O(n)
Space Complexity O(n)

(In code nums[i+1] means dp[i])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def checkRecord(self, n):
        if n == 1:
            return 3
        if n == 0:
            return 0
        nums = [1, 1, 2]
        i = 2
        while i < n:
            nums.append((nums[i] + nums[i-1] + nums[i-2])% 1000000007)
            i += 1
        result = (nums[n] + nums[n-1] + nums[n-2]) % 1000000007
        for i in range(n):
            result += nums[i+1] * nums[n-i] % 1000000007
            result %= 1000000007
        return result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static final int M = 1000000007;
public int checkRecord(int n) {
    long[] PorL = new long[n + 1]; // ending with P or L, no A
    long[] P = new long[n + 1]; // ending with P, no A
    PorL[0] = P[0] = 1; PorL[1] = 2; P[1] = 1;
    for (int i = 2; i <= n; i++) {
        P[i] = PorL[i - 1];
        PorL[i] = (P[i] + P[i - 1] + P[i - 2]) % M;
    }
    
    long res = PorL[n];
    for (int i = 0; i < n; i++) { // inserting A into (n-1)-length strings
    	long s = (PorL[i] * PorL[n - i - 1]) % M;
        res = (res + s) % M;
    }
    
    return (int) res;
}