Press "Enter" to skip to content

Posts published in April 2018

花花酱 LeetCode 827. Making A Large Island

Problem

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 = 1.

Example 3:

Input: [[1, 1], [1, 1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 1.

Notes:

  • 1 <= grid.length = grid[0].length <= 50.
  • 0 <= grid[i][j] <= 1.

Solution

Step 1: give each connected component a unique id and count its ara.

Step 2: for each 0 zero, check its 4 neighbours, sum areas up by unique ids.

Time complexity: O(n*m)

Space complexity: O(n*m)

C++

 

花花酱 LeetCode 826. Most Profit Assigning Work

Problem

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:

Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100 
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get profit of [20,20,30,30] seperately.

Notes:

  • 1 <= difficulty.length = profit.length <= 10000
  • 1 <= worker.length <= 10000
  • difficulty[i], profit[i], worker[i]Ā  are in rangeĀ [1, 10^5]

Solution 1: Sorting + Two pointers

Time complexity: O(nlogn + mlogm)

Space complexity: O(n)

Solution 2: Bucket + Greedy

Key idea: for each difficulty D, find the most profit job whose requirement is <= D.

Three steps:

  1. for each difficulty D,Ā find the most profit job whose requirement is == D, best[D] = max{profit ofĀ difficulty D}.
  2. if difficulty D – 1 can make more profit thanĀ difficulty D, best[D] =Ā max(best[D], best[D – 1]).
  3. The max profit each worker at skill level D can make is best[D].

Time complexity: O(n)

Space complexity: O(10000)

C++

 

C++ using map

 

花花酱 LeetCode 825. Friends Of Appropriate Ages

Problem

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:

Input: [16,16]
Output: 2
Explanation: 2 people friend request each other.

Example 2:

Input: [16,17,18]
Output: 2
Explanation: Friend requests are made 17 -> 16, 18 -> 17.

Example 3:

Input: [20,30,100,110,120]
Output: 
Explanation: Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.

Notes:

  • 1 <= ages.lengthĀ <= 20000.
  • 1 <= ages[i] <= 120.

Solution: Hashtable

Count how many people at each age i.

Time complexity: O(n)

Space complexity: O(120)

C++

 

花花酱 LeetCode 824. Goat Latin

Problem

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:

Input: "I speak Goat Latin"
Output: "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"

Example 2:

Input: "The quick brown fox jumped over the lazy dog"
Output: "heTmaa uickqmaaa rownbmaaaa oxfmaaaaa umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa azylmaaaaaaaaa ogdmaaaaaaaaaa"

 

Notes:

  • SĀ contains only uppercase, lowercase and spaces.Ā Exactly one space between each word.
  • 1 <= S.length <= 100.

Solution: String

C++

 

花花酱 LeetCode 822. Card Flipping Game

Problem

题ē›®å¤§ę„ļ¼šęƏ张ē‰Œēš„ę­£åé¢å„å°ē€äø€äøŖꕰļ¼Œä½ åÆ仄随ä¾æēæ»ē‰Œć€‚ę‰¾å‡ŗäø€äøŖęœ€å°ēš„ę•°ä½æ得其他ē‰Œå½“å‰ę­£é¢ēš„ę•°å€¼éƒ½äøå’Œå®ƒē›øē­‰ć€‚

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:

Input: fronts = [1,2,4,4,7], backs = [1,3,4,1,3]
Output: 2
Explanation: If we flip the second card, the fronts are [1,3,4,4,7] and the backs are [1,2,4,1,3]. We choose the second card, which has number 2 on the back, and it isn't on the front of any card, so 2 is good.

Note:

  1. 1 <= fronts.length == backs.lengthĀ <=Ā 1000.
  2. 1 <=Ā fronts[i]Ā <= 2000.
  3. 1 <= backs[i]Ā <= 2000.

Solution: Hashset

C++