花花酱 LeetCode 810. Chalkboard XOR Game

By zxi on May 2, 2018

Problem

We are given non-negative integers nums[i] which are written on a chalkboard. Alice and Bob take turns erasing exactly one number from the chalkboard, with Alice starting first. If erasing a number causes the bitwise XOR of all the elements of the chalkboard to become 0, then that player loses. (Also, we’ll say the bitwise XOR of one element is that element itself, and the bitwise XOR of no elements is 0.)

Also, if any player starts their turn with the bitwise XOR of all the elements of the chalkboard equal to 0, then that player wins.

Return True if and only if Alice wins the game, assuming both players play optimally.

Example:
Input: nums = [1, 1, 2]
Output: false
Explanation: 
Alice has two choices: erase 1 or erase 2. 
If she erases 1, the nums array becomes [1, 2]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 2 = 3. Now Bob can remove any element he wants, because Alice will be the one to erase the last element and she will lose. 
If Alice erases 2 first, now nums becomes [1, 1]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 1 = 0. Alice will lose.

Notes:

1 <= N <= 1000.
0 <= nums[i] <= 2^16.

Solution: Math

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

bool xorGame(vector<int>& nums) {

if (nums.size() % 2 == 0) return true;

int x = 0;

for (int num : nums) x ^= num;

return x == 0;

}

};

花花酱 LeetCode 827. Making A Large Island

By zxi on April 30, 2018

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++

// Author: Huahua

// Running time: 14 ms

class Solution {

public:

int largestIsland(vector<vector<int>>& grid) {

color_ = 1;

g_ = &grid;

m_ = grid.size();

n_ = grid[0].size();

unordered_map<int, int> areas; // color -> area

int ans = 0;

for (int i = 0; i < m_; ++i)

for (int j = 0; j < n_; ++j)

if (grid[i][j] == 1) {

++color_;

areas[color_] = getArea(j, i);

ans = max(ans, areas[color_]);

}

for (int i = 0; i < m_; ++i)

for (int j = 0; j < n_; ++j)

if (grid[i][j] == 0) {

int area = 1;

for (int color : set<int>{getColor(j, i - 1), getColor(j, i + 1),

getColor(j - 1, i), getColor(j + 1, i)})

area += areas[color];

ans = max(ans, area);

}

return ans;

}

private:

int m_;

int n_;

int color_;

vector<vector<int>>* g_; // does not own the object.

int getColor(int x, int y) {

return (x < 0 || x >= n_ || y < 0 || y >= m_) ? 0 : (*g_)[y][x];

}

// Return the area of a connected component, set all elements to color_.

int getArea(int x, int y) {

if (x < 0 || x >= n_ || y < 0 || y >= m_ || (*g_)[y][x] != 1) return 0;

(*g_)[y][x] = color_;

return 1 + getArea(x - 1, y) + getArea(x + 1, y)

+ getArea(x, y - 1) + getArea(x, y + 1);

}

};

花花酱 LeetCode 826. Most Profit Assigning Work

By zxi on April 29, 2018

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)

// Author: Huahua

// Running time: 90 ms

class Solution {

public:

int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {

const int n = difficulty.size();

vector<pair<int, int>> jobs; // difficulty, profit

for (int i = 0; i < n; ++i)

jobs.emplace_back(difficulty[i], profit[i]);

std::sort(jobs.begin(), jobs.end());

std::sort(worker.begin(), worker.end());

int ans = 0;

int i = 0;

int best = 0;

for (int level : worker) {

while (i < n && level >= jobs[i].first)

best = max(best, jobs[i++].second);

ans += best;

}

return ans;

}

};

Solution 2: Bucket + Greedy

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

Three steps:

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

Time complexity: O(n)

Space complexity: O(10000)

C++

// Author: Huahua

// Running time: 112 ms

class Solution {

public:

int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {

const int N = 100000;

// max profit at difficulty i

vector<int> max_profit(N + 1, 0);

for (int i = 0; i < difficulty.size(); ++i)

max_profit[difficulty[i]] = max(max_profit[difficulty[i]], profit[i]);

for (int i = 2; i <= N; ++i)

max_profit[i] = max(max_profit[i], max_profit[i - 1]);

int ans = 0;

for (int level : worker)

ans += max_profit[level];

return ans;

}

};

C++ using map

// Author: Huahua

// Running time: 112 ms

class Solution {

public:

int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {

map<int, int> bests;

for (int i = 0; i < difficulty.size(); ++i)

bests[difficulty[i]] = max(bests[difficulty[i]], profit[i]);

int best = 0;

for (auto it = bests.begin(); it != bests.end(); ++it)

it->second = best = max(it->second, best);

int ans = 0;

for (int level : worker)

ans += prev(bests.upper_bound(level))->second;

return ans;

}

};

花花酱 LeetCode 825. Friends Of Appropriate Ages

By zxi on April 29, 2018

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++

// Author: Huahua

// Running time: 39 ms

class Solution {

public:

int numFriendRequests(vector<int>& ages) {

const int kMaxAge = 120;

vector<int> counts(kMaxAge + 1, 0);

for (const int age : ages)

++counts[age];

int ans = 0;

for (int A = 1; A <= kMaxAge; ++A) {

for (int B = 0.5 * A + 7 + 1; B <= A; ++B)

ans += counts[A] * (counts[B] - (A == B));

}

return ans;

}

};

花花酱 LeetCode 824. Goat Latin

By zxi on April 29, 2018

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++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

string toGoatLatin(string S) {

const string vowls = "aeiouAEIOU";

string ans;

string word;

int index = 0;

istringstream s(S);

while (s >> word) {

if (vowls.find(word[0]) == string::npos)

word = word.substr(1) + word[0];

ans += " " + word + "ma" + string(++index, 'a');

}

return ans.substr(1);

}

};

Huahua's Tech Road

花花酱 LeetCode 810. Chalkboard XOR Game

Problem

Solution: Math

花花酱 LeetCode 827. Making A Large Island

Problem

Solution

花花酱 LeetCode 826. Most Profit Assigning Work

Problem

Solution 1: Sorting + Two pointers

Solution 2: Bucket + Greedy

花花酱 LeetCode 825. Friends Of Appropriate Ages

Problem

Solution: Hashtable

花花酱 LeetCode 824. Goat Latin

Problem

Solution: String