# hihoCoder 1543-SCI表示法

hihoCoder 1543-SCI表示法

### 输出

2
15
8

5
1

# hihoCoder 1542-无根数变有根树

hihoCoder 1542-无根数变有根树

### 输出

5 4
1 2
3 1
4 3
5 1

3 1 4 0 1

# LeetCode Dota2 Senate

LeetCode Dota2 Senate 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:

1. Ban one senator's right: A senator can make another senator lose all his rights in this and all the following rounds.
2. 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"
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.

Note:
1. The length of the given string will in the range [1, 10,000].

1. DXDRR
2. DXDXR
3. XXDXR
4. XXDXX
Dire胜利；第一个D如果杀其后的第二个R：
1. DRDXR
2. DRXXR
3. XRXXR
Radiant胜利。 这其实很好理解，因为是round-based的投票方式，对于D来说，他必须首先把其后的第一个R杀掉，要不然很快就会轮到这个R杀己方人员了。 round-based的方式是用%n的方式实现，代码如下： [cpp] class Solution { public: string predictPartyVictory(string senate) { int r_cnt = 0, d_cnt = 0, n = senate.size(); for (int i = 0; i < n; ++i) { if (senate[i] == ‘R’) ++r_cnt; else ++d_cnt; } int pos = 0; while (r_cnt > 0 && d_cnt > 0) { if (senate[pos] == ‘X’) { pos = (pos + 1) % n; continue; } int pos_next = (pos + 1) % n; while (senate[pos_next] == senate[pos] || senate[pos_next] == ‘X’) pos_next = (pos_next + 1) % n; if (senate[pos_next] == ‘R’) –r_cnt; else –d_cnt; senate[pos_next] = ‘X’; pos = (pos + 1) % n; } return r_cnt == 0 ? "Dire" : "Radiant"; } }; [/cpp] 本代码提交AC，用时752MS。]]>

# LeetCode 4 Keys Keyboard

LeetCode 4 Keys Keyboard 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. 1 <= N <= 50
2. Answers will be in the range of 32-bit signed integer.

• A: 打印一个字符A
• Ctrl-A: 全选
• Ctrl-C: 复制
• Ctrl-V: 粘贴

# LeetCode 2 Keys Keyboard

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

1. Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
2. 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:
1. The n will be in the range [1, 1000].

# LeetCode Find Duplicate Subtrees

LeetCode Find Duplicate Subtrees 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. Example 1:

        1
/ \
2   3
/   / \
4   2   4
/
4

The following are two duplicate subtrees:
      2
/
4

and
    4

Therefore, you need to return above trees’ root in the form of a list.

  1
/
2

 2
\
1

# LeetCode Replace Words

LeetCode Replace Words

In English, we have a concept called root, which can be followed by some other words to form another longer word – let’s call this word successor. For example, the root an, followed by other, which can form another word another. Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the rootforming it. If a successor has many roots can form it, replace it with the root with the shortest length. You need to output the sentence after the replacement. Example 1:
Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Note:
1. The input will only have lower-case letters.
2. 1 <= dict words number <= 1000
3. 1 <= sentence words number <= 1000
4. 1 <= root length <= 100
5. 1 <= sentence words length <= 1000

# LeetCode Palindromic Substrings

LeetCode Palindromic Substrings Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters. Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:
1. The input string length won’t exceed 1000.

# LeetCode Maximum Length of Pair Chain

LeetCode Maximum Length of Pair Chain You are given n pairs of numbers. In every pair, the first number is always smaller than the second number. Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion. Given a set of pairs, find the length longest chain which can be formed. You needn’t use up all the given pairs. You can select pairs in any order. Example 1:

Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]

Note:
1. The number of given pairs will be in the range [1, 1000].

# LeetCode Set Mismatch

LeetCode Set Mismatch The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number. Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array. Example 1:

Input: nums = [1,2,2,4]
Output: [2,3]

Note:
1. The given array size will in the range [2, 10000].
2. The given array’s numbers won’t have any order.