Huahua’s Tech Road

花花酱 LeetCode 169. Majority Element

By zxi on November 4, 2017

题目大意：给你一个数组，其中一个数出现超过n/2次，问你出现次数最多的那个数是什么？

Problem:

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Ideas:

Solution 1:

Hash table O(n) / O(n)

// Author: Huahua

// Runtime : 23 ms

class Solution {

public:

int majorityElement(vector<int>& nums) {

unordered_map<int, int> count;

const int n = nums.size();

for (const int num : nums)

if (++count[num] > n / 2) return num;

return -1;

}

};

Solution 2:

BST O(nlogk) / O(n)

// Author: Huahua

// Runtime : 19 ms

class Solution {

public:

int majorityElement(vector<int>& nums) {

map<int, int> count;

const int n = nums.size();

for (const int num : nums)

if (++count[num] > n / 2) return num;

return -1;

}

};

Solution 3:

Randomization O(n) / O(1)

// Author: Huahua

// Runtime: 19 ms

class Solution {

public:

int majorityElement(vector<int>& nums) {

srand(time(nullptr));

const int n = nums.size();

while (true) {

const int index = rand() % n;

const int majority = nums[index];

int count = 0;

for (const int num : nums)

if (num == majority && ++count > n/2) return num;

}

return -1;

}

};

Solution 4:

Bit voting O(n) / O(1)

class Solution {

public:

int majorityElement(vector<int>& nums) {

const int n = nums.size();

int majority = 0;

for (int i = 0; i < 32; ++i) {

int mask = 1 << i;

int count = 0;

for (const int num : nums)

if ((num & mask) && (++count > n /2)) {

majority |= mask;

break;

}

return majority;

}

};

Solution 5:

Moore Voting O(n) / O(1)

class Solution {

public:

int majorityElement(vector<int>& nums) {

int majority = nums.front();

int count = 0;

for (const int num : nums) {

if (num == majority) ++count;

else if (--count == 0) {

count = 1;

majority = num;

}

return majority;

}

};

Solution 6:

Full sorting O(nlogn) / O(1)

class Solution {

public:

int majorityElement(vector<int>& nums) {

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

return nums[nums.size()/2];

}

};

Solution 7:

Partial sorting O(n) / O(1)

class Solution {

public:

int majorityElement(vector<int>& nums) {

nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());

return nums[nums.size() / 2];

}

};

Solution 8:

Divide and conquer O(nlogn) / O(logn)

class Solution {

public:

int majorityElement(vector<int>& nums) {

return majorityElement(nums, 0, nums.size() - 1);

}

private:

int majorityElement(const vector<int>& nums, int l, int r) {

if (l == r) return nums[l];

const int m = l + (r - l) / 2;

const int ml = majorityElement(nums, l, m);

const int mr = majorityElement(nums, m + 1, r);

if (ml == mr) return ml;

return count(nums.begin() + l, nums.begin() + r + 1, ml) >

count(nums.begin() + l, nums.begin() + r + 1, mr)

? ml : mr;

}

};

Divide and conquer O(nlogn) / O(logn)

class Solution {

public:

int majorityElement(vector<int>& nums) {

return majorityElement(nums, 0, nums.size() - 1).first;

}

private:

pair<int, int> majorityElement(const vector<int>& nums, int l, int r) {

if (l == r) return {nums[l], 1};

int mid = l + (r - l) / 2;

auto ml = majorityElement(nums, l, mid);

auto mr = majorityElement(nums, mid + 1, r);

if (ml.first == mr.first) return { ml.first, ml.second + mr.second };

if (ml.second > mr.second)

return { ml.first, ml.second + count(nums.begin() + mid + 1, nums.begin() + r + 1, ml.first) };

else

return { mr.first, mr.second + count(nums.begin() + l, nums.begin() + mid + 1, mr.first) };

}

};

花花酱 LeetCode 216. Combination Sum III

By zxi on November 3, 2017

题目大意：输出所有用k个数的和为n的组合。可以使用的元素是1到9。

Problem:

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

1	[[1,2,6], [1,3,5], [2,3,4]]

Idea:

DFS + backtracking

bit

Solution:

C++

// Author: Huahua

// Runtime: 0 ms

class Solution {

public:

vector<vector<int>> combinationSum3(int k, int n) {

vector<vector<int>> ans;

vector<int> cur;

dfs(k, n, 1, cur, ans);

return ans;

}

private:

// Use k numbers (>= s) to sum up to n

void dfs(int k, int n, int s,

vector<int>& cur, vector<vector<int>>& ans) {

if (k == 0) {

if (n == 0) ans.push_back(cur);

return;

}

for (int i = s; i <= 9; ++i) {

if (i > n) return;

cur.push_back(i);

dfs(k - 1, n - i, i + 1, cur, ans);

cur.pop_back();

}

};

C++ / binary

class Solution {

public:

vector<vector<int>> combinationSum3(int k, int n) {

vector<vector<int>> ans;

// 2^9, generate all combinations of [1 .. 9]

for (int i = 0; i < (1 << 9); ++i) {

vector<int> cur;

int sum = 0;

// Use j if (j - 1)-th bit is 1

for (int j = 1; j <= 9; ++j)

if (i & (1 << (j - 1))) {

sum += j;

cur.push_back(j);

}

if (sum == n && cur.size() == k)

ans.push_back(cur);

}

return ans;

}

};

Python

class Solution:

def combinationSum3(self, k, n):

def dfs(k, n, s, cur, ans):

if k == 0 and n == 0:

ans.append(list(cur))

for i in range(s, min(n + 1, 10)):

dfs(k - 1, n - i, i + 1, cur + [i], ans)

ans = []

dfs(k, n, 1, [], ans)

return ans

Related problems:

花花酱 LeetCode 719. Find K-th Smallest Pair Distance

By zxi on October 29, 2017

题目大意：给你一个数组，返回所有数对中，绝对值差第k小的值。

Problem:

Given an integer array, return the k-th smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.

Example 1:

Input:

nums = [1,3,1]

k = 1

Output: 0

Explanation:

Here are all the pairs:

(1,3) -> 2

(1,1) -> 0

(3,1) -> 2

Then the 1st smallest distance pair is (1,1), and its distance is 0.

Note:

2 <= len(nums) <= 10000.
0 <= nums[i] < 1000000.
1 <= k <= len(nums) * (len(nums) - 1) / 2.

Idea

Bucket sort

Binary search / dp

Solution

C++ / binary search

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

int smallestDistancePair(vector<int>& nums, int k) {

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

int n = nums.size();

int l = 0;

int r = nums.back() - nums.front();

while (l <= r) {

int cnt = 0;

int j = 0;

int m = l + (r - l) / 2;

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

while (j < n && nums[j] - nums[i] <= m) ++j;

cnt += j - i - 1;

}

cnt >= k ? r = m - 1 : l = m + 1;

}

return l;

}

};

C++ / bucket sort w/ vector O(n^2)

// Author: Huahua

// Runtime: 549 ms

class Solution {

public:

int smallestDistancePair(vector<int>& nums, int k) {

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

const int N = nums.back();

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

const int n = nums.size();

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

for (int j = i + 1; j < n; ++j)

++count[nums[j] - nums[i]];

for (int i = 0; i <= N; ++i) {

k -= count[i];

if (k <= 0) return i;

}

return 0;

}

};

Related Problems:

花花酱 LeetCode 621. Task Scheduler

By zxi on October 28, 2017

题目大意：给你一些用字母表示的任务，执行每个任务需要单位时间的CPU。对于相同的任务，CPU需要n个单位时间的冷却时间，期间可以执行其他不相同的任务。问最少多少时间可以完成所有任务。

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the least number of intervals the CPU will take to finish all the given tasks.

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2

Output: 8

Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

Note:

The number of tasks is in the range [1, 10000].
The integer n is in the range [0, 100].

Idea:

Counting

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Runtime: 56 ms

class Solution {

public:

int leastInterval(vector<char>& tasks, int n) {

vector<int> count(26, 0);

for (const char task : tasks)

++count[task - 'A'];

const int max_count = *max_element(count.begin(), count.end());

size_t ans = (max_count - 1) * (n + 1);

ans += count_if(count.begin(), count.end(),

[max_count](int c){ return c == max_count; });

return max(tasks.size(), ans);

}

};

花花酱 LeetCode 699. Falling Squares

By zxi on October 24, 2017

题目大意：方块落下后会堆叠在重叠的方块之上，问每一块方块落下之后最高的方块的高度是多少？

Problem:

On an infinite number line (x-axis), we drop given squares in the order they are given.

The i-th square dropped (positions[i] = (left, side_length)) is a square with the left-most point being positions[i][0] and sidelength positions[i][1].

The square is dropped with the bottom edge parallel to the number line, and from a higher height than all currently landed squares. We wait for each square to stick before dropping the next.

The squares are infinitely sticky on their bottom edge, and will remain fixed to any positive length surface they touch (either the number line or another square). Squares dropped adjacent to each other will not stick together prematurely.

Return a list ans of heights. Each height ans[i] represents the current highest height of any square we have dropped, after dropping squares represented by positions[0], positions[1], ..., positions[i].

Example 1:

Input: [[1, 2], [2, 3], [6, 1]]

Output: [2, 5, 5]

Explanation:

After the first drop of

positions[0] = [1, 2]:

_aa

-------

The maximum height of any square is 2.

After the second drop of

positions[1] = [2, 3]:

__aaa

_aa__

--------------

The maximum height of any square is 5.

The larger square stays on top of the smaller square despite where its center

of gravity is, because squares are infinitely sticky on their bottom edge.

After the third drop of

positions[1] = [6, 1]:

__aaa

_aa

_aa___a

--------------

The maximum height of any square is still 5.

Thus, we return an answer of

[2, 5, 5]

Example 2:

Input: [[100, 100], [200, 100]]

Output: [100, 100]

Explanation: Adjacent squares don't get stuck prematurely - only their bottom edge can stick to surfaces.

Note:

1 <= positions.length <= 1000.
1 <= positions[i][0] <= 10^8.
1 <= positions[i][1] <= 10^6.

Idea:

Range query with map

Solution:

C++ map

// Author: Huahua

// Runtime: 29 ms

class Solution {

public:

vector<int> fallingSquares(vector<pair<int, int>>& positions) {

vector<int> ans;

map<pair<int, int>, int> b; // {{start, end}, height}

int maxHeight = INT_MIN;

for (const auto& kv: positions) {

int start = kv.first;

int size = kv.second;

int end = start + size;

// first range intersect with new_interval

auto it = b.upper_bound({start, end});

if (it != b.begin()) {

auto it2 = it;

if ((--it2)->first.second > start) it = it2;

}

int baseHeight = 0;

vector<tuple<int, int, int>> ranges;

while (it != b.end() && it->first.first < end) {

const int s = it->first.first;

const int e = it->first.second;

const int h = it->second;

if (s < start) ranges.emplace_back(s, start, h);

if (e > end) ranges.emplace_back(end, e, h);

// max height of intesected ranges

baseHeight = max(baseHeight, h);

it = b.erase(it);

}

int newHeight = size + baseHeight;

b[{start, end}] = newHeight;

for (const auto& range: ranges)

b[{get<0>(range), get<1>(range)}] = get<2>(range);

maxHeight = max(maxHeight, newHeight);

ans.push_back(maxHeight);

}

return ans;

}

};

C++ vector without merge

// Author: Huahua

// Runtime: 46 ms

class Solution {

public:

vector<int> fallingSquares(vector<pair<int, int>>& positions) {

vector<int> ans;

vector<Interval> intervals;

int maxHeight = INT_MIN;

for (const auto& kv: positions) {

int start = kv.first;

int end = start + kv.second;

int baseHeight = 0;

for (const Interval& interval : intervals) {

if (interval.start >= end || interval.end <= start)

continue;

baseHeight = max(baseHeight, interval.height);

}

int height = kv.second + baseHeight;

intervals.push_back(Interval(start, end, height));

maxHeight = max(maxHeight, height);

ans.push_back(maxHeight);

}

return ans;

}

private:

struct Interval {

int start;

int end;

int height;

Interval(int start, int end, int height)

: start(start), end(end), height(height) {}

};

C++ / vector with merge (slower)

// Author: Huahua

// Runtime: 86 ms

class Solution {

public:

vector<int> fallingSquares(vector<pair<int, int>>& positions) {

vector<int> ans;

vector<Interval> intervals;

int maxHeight = INT_MIN;

for (const auto& kv: positions) {

vector<Interval> tmp;

int start = kv.first;

int end = start + kv.second;

int baseHeight = 0;

for (const Interval& interval : intervals) {

if (interval.start >= end || interval.end <= start) {

tmp.push_back(interval);

continue;

}

baseHeight = max(baseHeight, interval.height);

if (interval.start < start || interval.end > end)

tmp.push_back(interval);

}

int height = kv.second + baseHeight;

tmp.push_back(Interval(start, end, height));

intervals.swap(tmp);

maxHeight = max(maxHeight, height);

ans.push_back(maxHeight);

}

return ans;

}

private:

struct Interval {

int start;

int end;

int height;

Interval(int start, int end, int height)

: start(start), end(end), height(height) {}

};

Related Problems:

[解题报告] LeetCode 715. Range Module
[解题报告] LeetCode 218. The Skyline Problem
[解题报告] LeetCode 57. Insert Interval

Huahua's Tech Road

花花酱 LeetCode 169. Majority Element

花花酱 LeetCode 216. Combination Sum III

花花酱 LeetCode 719. Find K-th Smallest Pair Distance

花花酱 LeetCode 621. Task Scheduler

花花酱 LeetCode 699. Falling Squares