花花酱 LeetCode 830. Positions of Large Groups

By zxi on May 13, 2018

Problem

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:

Input: "abbxxxxzzy"
Output: [[3,6]]
Explanation: "xxxx" is the single large group with starting 3 and ending positions 6.

Example 2:

Input: "abc"
Output: []
Explanation: We have "a","b" and "c" but no large group.

Example 3:

Input: "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]

Note: 1 <= S.length <= 1000

Solution: Brute Force

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 18 ms

class Solution {

public:

vector<vector<int>> largeGroupPositions(string S) {

constexpr int kLargeGroupSize = 3;

const int n = S.size();

vector<vector<int>> ans;

int c = 0;

for (int i = 0; i <= n; ++i, ++c) {

if (i == n || S[i] != S[i - 1]) {

if (c >= kLargeGroupSize) ans.push_back({i - c, i - 1});

c = 0;

}

return ans;

}

};

花花酱 LeetCode 832. Flipping an Image

By zxi on May 13, 2018

Problem

Given a binary matrix A, we want to flip the image horizontally, then invert it, and return the resulting image.

To flip an image horizontally means that each row of the image is reversed. For example, flipping [1, 1, 0] horizontally results in [0, 1, 1].

To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0. For example, inverting [0, 1, 1] results in [1, 0, 0].

Example 1:

Input: [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

Example 2:

Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

Notes:

1 <= A.length = A[0].length <= 20
0 <= A[i][j] <= 1

Solution 1: Brute Force

Time complexity: O(m*n)

Space complexity: O(m*n)

C++

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

vector<vector<int>> flipAndInvertImage(vector<vector<int>>& A) {

auto B = A;

int m = A.size();

int n = A[0].size();

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

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

B[i][j] = 1 - A[i][n - j - 1];

return B;

}

};

花花酱 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;

}

};

Huahua's Tech Road

花花酱 LeetCode 830. Positions of Large Groups

Problem

Solution: Brute Force

花花酱 LeetCode 832. Flipping an Image

Problem

Solution 1: Brute Force

花花酱 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