BiWeekly Contest 13

[lihe]

5108. Encode Number

Medium

Given a non-negative integer num, Return its encoding string.

The encoding is done by converting the integer to a string using a secret function that you should deduce from the following table:

Example 1:

Input: num = 23
Output: "1000"

Example 2:

Input: num = 107
Output: "101100"

Constraints:

• 0 <= num <= 10^9

class Solution {
public:
    string encode(int num) {
        num += 1;
        string str = "";
        while(num){
            str += to_string(num % 2);
            num /= 2;
        }
        string result  = "";
        for(int i = str.size() - 2; i > 0; i--){
            result += str[i];
        }
        return result;
    }
};

5109. Smallest Common Region

Medium

You are given some lists of regions where the first region of each list includes all other regions in that list.

Naturally, if a region X contains another region Y then X is bigger than Y.

Given two regions region1, region2, find out the smallest region that contains both of them.

If you are given regions r1, r2 and r3 such that r1 includes r3, it is guaranteed there is no r2 such that r2 includes r3.

It's guaranteed the smallest region exists.

Example 1:

Input:
regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"
Output: "North America"

Constraints:

• 2 <= regions.length <= 10^4
• region1 != region2
• All strings consist of English letters and spaces with at most 20 letters.

5110. Synonymous Sentences

Medium

Given a list of pairs of equivalent words synonymsand a sentencetext .

Example 1:

Input:
synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]],
text = "I am happy today but was sad yesterday"
Output:
["I am cheerful today but was sad yesterday",
"I am cheerful today but was sorrow yesterday",
"I am happy today but was sad yesterday",
"I am happy today but was sorrow yesterday",
"I am joy today but was sad yesterday",
"I am joy today but was sorrow yesterday"]

Constraints:

• 0 <= synonyms.length <= 10
• synonyms[i].length == 2
• synonyms[0] != synonyms[1]
• All words consist of at most 10 English letters only.
• text is a single space separated sentence of at most 10 words.

5125. Handshakes That Don't Cross

Hard

You are given an even number of people num_people that stand around a circle and each person shakes hands with someone else, so that there are num_people / 2 handshakes total.

Return the number of ways these handshakes could occur such that none of the handshakes cross.

Since this number could be very big, return the answer mod 10^9 + 7

Example 1:

Input: num_people = 2
Output: 1

Example 2:

Input: num_people = 4
Output: 2
Explanation: There are two ways to do it, the first way is [(1,2),(3,4)] and the second one is [(2,3),(4,1)].

Example 3:

Input: num_people = 6
Output: 5

Example 4:

Input: num_people = 8
Output: 14

Constraints:

• 2 <= num_people <= 1000
• num_people % 2 == 0