LeetCode Weekly Contest 43解题思路

详细代码可以fork下Github上leetcode项目，不定期更新。

赛题

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

• Leetcode 652. Find Duplicate Subtrees
• Leetcode 650. 2 Keys Keyboard
• Leetcode 649. Dota2 Senate
• Leetcode 651. 4 Keys Keyboard

Leetcode 652. Find Duplicate Subtrees

Problem:

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with same node values.

思路：访问每个结点，对该结点之后的所有元素进行序列化，用map对序列化后的值计数，取出大于2的元素结点即可。

代码如下：

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> res = new ArrayList<>();
        Map<String, Integer> mem = new HashMap<>();
        if(root == null) return res;
        seriazle(root, mem, res);
        return res;
    }

    public String seriazle(TreeNode root, Map<String, Integer> mem, List<TreeNode> res){
        if (root == null) return "";
        String ans = "";
        ans += root.val + ",";
        ans += root.left != null ? seriazle(root.left, mem, res) : "#";
        ans += root.right != null ? seriazle(root.right, mem, res) : "#";
        mem.put(ans, mem.getOrDefault(ans, 0) + 1);
        if (mem.get(ans) == 2) res.add(root);
        return ans;
    }

取出重复子集的方法总结：计数，超过2的拿出来即可，接着就想办法如何标识出子集即可，此处用序列化完美解决。

Leetcode 650. 2 Keys Keyboard

Problem:

Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:

• Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
• Paste: You can paste the characters which are copied last time.

Given a number n. You have to get exactly n ‘A’ on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n ‘A’.

Example 1:

Input: 3
Output: 3
Explanation:
Intitally, we have one character ‘A’.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get ‘AA’.
In step 3, we use Paste operation to get ‘AAA’.

Note:

• The n will be in the range [1, 1000].

思路：
注意copy all的特性，一旦它到达了某个状态就不能再选取之前状态，所以可以采用DP，记录以每种copy长度的方式向后更新指定长度的最小值。

dp[i] 表示在长度i，所需要的最少步数

dp[i * (j + 1)] = min{dp[i * (j + 1)], dp[i] + j + 1}

表示当前copy长度为i时，后续长度更新所需要的最少步数，因为我们并不知道到底在哪个copy长度下取最小，于是枚举i。

代码如下：

final int INF = 1 << 29;
    public int minSteps(int n) {
        int[] dp = new int[n + 16];
        Arrays.fill(dp, INF);
        dp[1] = 0;
        for (int i = 1; i < n; ++i){
            for (int j = 2 * i; j <= n; j += i){
                dp[j] = Math.min(dp[j], dp[i] + j / i);
            }
        }
        return dp[n];
    }

Leetcode 651. 4 Keys Keyboard

Problem:

Imagine you have a special keyboard with the following keys:

Key 1: (A): Prints one ‘A’ on screen.

Key 2: (Ctrl-A): Select the whole screen.

Key 3: (Ctrl-C): Copy selection to buffer.

Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed.

Now, you can only press the keyboard for N times (with the above four keys), find out the maximum numbers of ‘A’ you can print on screen.

Example 1:

Input: N = 3
Output: 3
Explanation:
We can at most get 3 A’s on screen by pressing following key sequence:
A, A, A

Example 2:

Input: N = 7
Output: 9
Explanation:
We can at most get 9 A’s on screen by pressing following key sequence:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

Note:

• 1 <= N <= 50
• Answers will be in the range of 32-bit signed integer.

和上题思路一致，现在无非就是根据步数来更新最大的A，依旧采用向后构造的方法。

dp[i]表示当前步数下，A的最大长度

因为我们知道，每次key A，至少耗费一个步骤，所以至少dp[i] >= i

此时，我们以最少步数来构造后面的值：进行ctr A, ctr C, ctr V至少需要耗费三个步骤，所以
dp[i] -> dp[i + 3] 才有意义
因为：
dp[i + 3] = 2 * dp[i]
dp[i + 4] = 3 * dp[i] 此时只要ctr V即可
...
...

现在无非根据不同的切割点，进行最优化即可，遍历所有i。

代码如下：

    public int maxA(int N) {
        int[] dp = new int[N + 16];
        for (int i = 0; i <= N; ++i) dp[i] = i;
        for (int i = 1; i <= N; ++i){
            for (int j = i + 3; j <= N; ++j){
                dp[j] = Math.max(dp[j], (j - i - 1) * dp[i]);
            }
        }
        return dp[N];
    }

Leetcode 649. Dota2 Senate

Problem:

In the world of Dota2, there are two parties: the Radiant and the Dire.

The Dota2 senate consists of senators coming from two parties. Now the senate wants to make a decision about a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:

Ban one senator’s right:
A senator can make another senator lose all his rights in this and all the following rounds.
Announce the victory:
If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and make the decision about the change in the game.
Given a string representing each senator’s party belonging. The character ‘R’ and ‘D’ represent the Radiant party and the Dire party respectively. Then if there are n senators, the size of the given string will be n.

The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.

Suppose every senator is smart enough and will play the best strategy for his own party, you need to predict which party will finally announce the victory and make the change in the Dota2 game. The output should be Radiant or Dire.

Example 1:

Input: “RD”
Output: “Radiant”
Explanation: The first senator comes from Radiant and he can just ban the next senator’s right in the round 1.
And the second senator can’t exercise any rights any more since his right has been banned.
And in the round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.

Example 2:

Input: “RDD”
Output: “Dire”
Explanation:
The first senator comes from Radiant and he can just ban the next senator’s right in the round 1.
And the second senator can’t exercise any rights anymore since his right has been banned.
And the third senator comes from Dire and he can ban the first senator’s right in the round 1.
And in the round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.

思路：
每个帮派有投票权和禁止权，对于当前轮的当前顺位到底选择投票权还是禁止权？分析一下，如果不使用禁止权，那么自然就投票了，如果存在另一帮派的情况下，它一定把你先前的投票权给禁止了，所以对于自己而言存在其他帮派的情况下，一定优先使用禁止权，否则白白丧失一次机会。

那么这个问题就可以采用模拟的方法来实现了，不管如何都选择禁止权，我们要做的就是计数，并且把被禁止的帮派踢出队列。

代码如下：

    public String predictPartyVictory(String senate) {
        Queue<Character> queue = new LinkedList<>();
        int R = 0;
        int D = 0;
        for (char c : senate.toCharArray()){
            queue.offer(c);
            if (c == 'R') R++;
            else D++;
        }

        String ans = "";
        int ban = 0;
        while (true){
            if (R == 0 || D == 0){
                char winner = queue.poll();
                ans = winner == 'R' ? "Radiant" : "Dire";
                break;
            }
            char candicate = queue.poll();
            ban++;
            queue.offer(candicate);
            while (!queue.isEmpty() && candicate == queue.peek()){
                ban ++;
                queue.offer(queue.poll());
            }
            while (!queue.isEmpty() && candicate != queue.peek()){
                ban --;
                char loser = queue.poll();
                if (loser == 'R') R--;
                else D--;
                if (ban == 0) {
                    ban = 0;
                    break;
                }
            }
        }
        return ans;
    }