# Weekly Contest 83

## 830. Positions of Large Groups [AC]

In a string S of lowercase letters, these letters form consecutive groups of the same character.

For example, a string like S = “abbxxxxzyy” has the groups “a”, “bb”, “xxxx”, “z” and “yy”.

Call a group large if it has 3 or more characters. We would like the starting and ending positions of every large group.

The final answer should be in lexicographic order.

Example 1:

1 | Input: "abbxxxxzzy" |

Example 2:

1 | Input: "abc" |

Example 3:

1 | Input: "abcdddeeeeaabbbcd" |

Note: 1 <= S.length <= 1000

1 | class Solution { |

## 831. Masking Personal Information [AC]

We are given a personal information string S, which may represent either an email address or a phone number.

We would like to mask this personal information according to the following rules:

- Email address:

We define a name to be a string of length ≥ 2 consisting of only lowercase letters a-z or uppercase letters A-Z.

An email address starts with a name, followed by the symbol ‘@’, followed by a name, followed by the dot ‘.’ and followed by a name.

All email addresses are guaranteed to be valid and in the format of “name1@name2.name3“.

To mask an email, all names must be converted to lowercase and all letters between the first and last letter of the first name must be replaced by 5 asterisks ‘*’.

- Phone number:

A phone number is a string consisting of only the digits 0-9 or the characters from the set {‘+’, ‘-‘, ‘(‘, ‘)’, ‘ ‘}. You may assume a phone number contains 10 to 13 digits.

The last 10 digits make up the local number, while the digits before those make up the country code. Note that the country code is optional. We want to expose only the last 4 digits and mask all other digits.

The local number should be formatted and masked as “** -**-1111”, where 1 represents the exposed digits.

To mask a phone number with country code like “+111 111 111 1111”, we write it in the form “+** -**-

***-1111”. The ‘+’ sign and the first ‘-‘ sign before the local number should only exist if there is a country code. For example, a 12 digit phone number mask should start with “+**-“.

Note that extraneous characters like “(“, “)”, “ “, as well as extra dashes or plus signs not part of the above formatting scheme should be removed.

Return the correct “mask” of the information provided.

Example 1:

1 | Input: "LeetCode@LeetCode.com" |

Example 2:

1 | Input: "AB@qq.com" |

Example 3:

1 | Input: "1(234)567-890" |

Example 4:

1 | Input: "86-(10)12345678" |

1 | class Solution { |

## 829. Consecutive Numbers Sum [AC]

Given a positive integer N, how many ways can we write it as a sum of consecutive positive integers?

Example 1:

1 | Input: 5 |

Example 2:

1 | Input: 9 |

Example 3:

1 | Input: 15 |

1 | class Solution { |

## 828. Unique Letter String [Unsolved]

A character is unique in string S if it occurs exactly once in it.

For example, in string S = “LETTER”, the only unique characters are “L” and “R”.

Let’s define UNIQ(S) as the number of unique characters in string S.

For example, UNIQ(“LETTER”) = 2.

Given a string S with only uppercases, calculate the sum of UNIQ(substring) over all non-empty substrings of S.

If there are two or more equal substrings at different positions in S, we consider them different.

Since the answer can be very large, return the answer modulo 10 ^ 9 + 7.

Example 1:

1 | Input: "ABC" |

Example 2:

1 | Input: "ABA" |

1 | class Solution { |

# Weekly Contest 82

## 824. Goat Latin [AC]

Leetcode 824

A sentence S is given, composed of words separated by spaces. Each word consists of lowercase and uppercase letters only.

We would like to convert the sentence to “Goat Latin” (a made-up language similar to Pig Latin.)

The rules of Goat Latin are as follows:

If a word begins with a vowel (a, e, i, o, or u), append “ma” to the end of the word.

For example, the word ‘apple’ becomes ‘applema’.

If a word begins with a consonant (i.e. not a vowel), remove the first letter and append it to the end, then add “ma”.

For example, the word “goat” becomes “oatgma”.

Add one letter ‘a’ to the end of each word per its word index in the sentence, starting with 1.

For example, the first word gets “a” added to the end, the second word gets “aa” added to the end and so on.

Return the final sentence representing the conversion from S to Goat Latin.

Example 1:

1 | Input: "I speak Goat Latin" |

Example 2:

1 | Input: "The quick brown fox jumped over the lazy dog" |

1 | class Solution { |

## 825. Friends Of Appropriate Ages [AC]

Some people will make friend requests. The list of their ages is given and ages[i] is the age of the ith person.

Person A will NOT friend request person B (B != A) if any of the following conditions are true:

age[B] <= 0.5 * age[A] + 7

age[B] > age[A]

age[B] > 100 && age[A] < 100

Otherwise, A will friend request B.

Note that if A requests B, B does not necessarily request A. Also, people will not friend request themselves.

How many total friend requests are made?

Example 1:

1 | Input: [16,16] |

Example 2:

1 | Input: [16,17,18] |

Example 3:

1 | Input: [20,30,100,110,120] |

1 | class Solution { |

## 826. Most Profit Assigning Work [AC]

We have jobs: difficulty[i] is the difficulty of the ith job, and profit[i] is the profit of the ith job.

Now we have some workers. worker[i] is the ability of the ith worker, which means that this worker can only complete a job with difficulty at most worker[i].

Every worker can be assigned at most one job, but one job can be completed multiple times.

For example, if 3 people attempt the same job that pays $1, then the total profit will be $3. If a worker cannot complete any job, his profit is $0.

What is the most profit we can make?

Example 1:

1 | Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7] |

1 | class Solution { |

## 827. Making A Large Island [Unsolved]

In a 2D grid of 0s and 1s, we change at most one 0 to a 1.

After, what is the size of the largest island? (An island is a 4-directionally connected group of 1s).

Example 1:

Input: [[1, 0], [0, 1]]

Output: 3

Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Example 2:

Input: [[1, 1], [1, 0]]

Output: 4

Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

Example 3:

Input: [[1, 1], [1, 1]]

Output: 4

Explanation: Can’t change any 0 to 1, only one island with area = 4.

本来思路是并查集加BFS，但是由于并查集写的代码太长导致时间不够用

1 | class Solution { |

# Weekly Contest 81

## 821. Shortest Distance to a Character [AC]

Leetcode 821

Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.

Example 1:

1 | Input: S = "loveleetcode", C = 'e' |

1 | class Solution { |

## 822. 822. Card Flipping Game [AC]

On a table are N cards, with a positive integer printed on the front and back of each card (possibly different).

We flip any number of cards, and after we choose one card.

If the number X on the back of the chosen card is not on the front of any card, then this number X is good.

What is the smallest number that is good? If no number is good, output 0.

Here, fronts[i] and backs[i] represent the number on the front and back of card i.

A flip swaps the front and back numbers, so the value on the front is now on the back and vice versa.

Example:

1 | Input: fronts = [1,2,4,4,7], backs = [1,3,4,1,3] |

1 | class Solution { |

## 820. Short Encoding of Words [AC]

Leetcode 820

Given a list of words, we may encode it by writing a reference string S and a list of indexes A.

For example, if the list of words is [“time”, “me”, “bell”], we can write it as S = “time#bell#” and indexes = [0, 2, 5].

Then for each index, we will recover the word by reading from the reference string from that index until we reach a “#” character.

What is the length of the shortest reference string S possible that encodes the given words?

Example:

1 | Input: words = ["time", "me", "bell"] |

1 | class Solution { |

## 823. Binary Trees With Factors [AC]

Given an array of unique integers, each integer is strictly greater than 1.

We make a binary tree using these integers and each number may be used for any number of times.

Each non-leaf node’s value should be equal to the product of the values of it’s children.

How many binary trees can we make? Return the answer modulo 10 ** 9 + 7.

Example 1:

1 | Input: A = [2, 4] |

Example 2:

1 | Input: A = [2, 4, 5, 10] |

1 | class Solution { |

# Weekly Contest 80

## 819. Most Common Word [AC]

Given a paragraph and a list of banned words, return the most frequent word that is not in the list of banned words. It is guaranteed there is at least one word that isn’t banned, and that the answer is unique.

Words in the list of banned words are given in lowercase, and free of punctuation. Words in the paragraph are not case sensitive. The answer is in lowercase.

Example:

1 | Input: |

1 | class Solution { |

## 817. Linked List Components [AC]

We are given head, the head node of a linked list containing unique integer values.

We are also given the list G, a subset of the values in the linked list.

Return the number of connected components in G, where two values are connected if they appear consecutively in the linked list.

Example 1:

1 | Input: |

Example 2:

1 | Input: |

1 | /** |

## 816. Ambiguous Coordinates [AC]

We had some 2-dimensional coordinates, like “(1, 3)” or “(2, 0.5)”. Then, we removed all commas, decimal points, and spaces, and ended up with the string S. Return a list of strings representing all possibilities for what our original coordinates could have been.

Our original representation never had extraneous zeroes, so we never started with numbers like “00”, “0.0”, “0.00”, “1.0”, “001”, “00.01”, or any other number that can be represented with less digits. Also, a decimal point within a number never occurs without at least one digit occuring before it, so we never started with numbers like “.1”.

The final answer list can be returned in any order. Also note that all coordinates in the final answer have exactly one space between them (occurring after the comma.)

1 | Example 1: |

1 | class Solution { |

## 818. Race Car [AC]

Your car starts at position 0 and speed +1 on an infinite number line. (Your car can go into negative positions.)

Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).

When you get an instruction “A”, your car does the following: position += speed, speed *= 2.

When you get an instruction “R”, your car does the following: if your speed is positive then speed = -1 , otherwise speed = 1. (Your position stays the same.)

For example, after commands “AAR”, your car goes to positions 0->1->3->3, and your speed goes to 1->2->4->-1.

Now for some target position, say the length of the shortest sequence of instructions to get there.

1 | Example 1: |

1 | class Solution { |