Posts published in “Medium”

花花酱 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 347. Top K Frequent Elements

By zxi on October 22, 2017

Problem:

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

Idea:

Solution 2: Priority queue / max heap

Time complexity: O(n) + O(nlogk)

Space complexity: O(n)

C++

// Author: Huahuas

// Running time: 16 ms

class Solution {

public:

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

unordered_map<int, int> count;

for (const int num : nums)

++count[num];

priority_queue<pair<int, int>> q;

for (const auto& pair : count) {

q.emplace(-pair.second, pair.first);

if (q.size() > k) q.pop();

}

vector<int> ans;

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

ans.push_back(q.top().second);

q.pop();

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 56 ms

class Solution {

public List<Integer> topKFrequent(int[] nums, int k) {

Map<Integer, Integer> counts = new HashMap<>();

for (int num : nums)

counts.put(num, counts.getOrDefault(num, 0) + 1);

PriorityQueue<int[]> queue = new PriorityQueue<>((x, y) -> x[0] - y[0]);

for (Integer num : counts.keySet()) {

queue.offer(new int[]{counts.get(num), num});

if (queue.size() > k) queue.poll();

}

List<Integer> ans = new ArrayList<>();

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

ans.add(queue.poll()[1]);

return ans;

}

Python

"""

Author: Huahua

Running time: 56 ms

"""

class Solution:

def topKFrequent(self, nums, k):

counts = collections.Counter(nums)

h = []

for num in counts.keys():

heapq.heappush(h, (counts[num], num))

if len(h) > k: heapq.heappop(h)

return [heapq.heappop(h)[1] for i in range(k)]

Solution 3: Bucket Sort

Time complexity: O(n)

Space complexity: O(n)

C++/hashmap

class Solution {

public:

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

unordered_map<int, int> count;

int max_freq = 1;

for (const int num : nums)

max_freq = max(max_freq, ++count[num]);

map<int, vector<int>> buckets;

for (const auto& kv : count)

buckets[kv.second].push_back(kv.first);

vector<int> ans;

for (int i = max_freq; i >= 1; --i) {

auto it = buckets.find(i);

if (it == buckets.end()) continue;

ans.insert(ans.end(), it->second.begin(), it->second.end());

if (ans.size() == k) return ans;

}

return ans;

}

};

C++/array

class Solution {

public:

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

unordered_map<int, int> count;

for (const int num : nums)

++count[num];

vector<vector<int>> buckets(nums.size() + 1);

for (const auto& kv : count)

buckets[kv.second].push_back(kv.first);

vector<int> ans;

for (auto it = buckets.rbegin(); it != buckets.rend(); ++it) {

const vector<int>& keys = *it;

if (keys.empty()) continue;

ans.insert(ans.begin(), keys.begin(), keys.end());

if (ans.size() == k) return ans;

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 23 ms

class Solution {

public List<Integer> topKFrequent(int[] nums, int k) {

List[] buckets = new List[nums.length + 1];

Map<Integer, Integer> counts = new HashMap<>();

for (int num : nums)

counts.put(num, counts.getOrDefault(num, 0) + 1);

for (int num : counts.keySet()) {

int count = counts.get(num);

if (buckets[count] == null)

buckets[count] = new ArrayList<Integer>();

buckets[count].add(num);

}

List<Integer> ans = new ArrayList<>();

for (int i = buckets.length - 1; i > 0 && ans.size() < k; --i) {

if (buckets[i] != null) ans.addAll(buckets[i]);

}

return ans;

}

Python

"""

Author: Huahua

Running time: 64 ms

"""

class Solution:

def topKFrequent(self, nums, k):

counts = collections.Counter(nums)

buckets = [[] for _ in range(len(nums) + 1)]

for num in counts.keys():

buckets[counts[num]].append(num)

ans = []

for i in range(len(nums), 0, -1):

ans += buckets[i]

if len(ans) == k: return ans

return ans

Related Problems

[解题报告] LeetCode 692. Top K Frequent Words

花花酱 LeetCode 692. Top K Frequent Words

By zxi on October 21, 2017

Problem:

Given a non-empty list of words, return the k most frequent elements.

Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

Example 1:

Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2

Output: ["i", "love"]

Explanation: "i" and "love" are the two most frequent words.

Note that "i" comes before "love" due to a lower alphabetical order.

Example 2:

Input: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4

Output: ["the", "is", "sunny", "day"]

Explanation: "the", "is", "sunny" and "day" are the four most frequent words,

with the number of occurrence being 4, 3, 2 and 1 respectively.

Note:

You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Input words contain only lowercase letters.

Follow up:

Try to solve it in O(n log k) time and O(n) extra space.

Idea:

Priority queue / min heap

Solution

C++ / priority_queue O(n log k) / O(n)

// Author: Huahua

// Runtime: 13 ms (< 90.31 %)

class Solution {

private:

typedef pair<string, int> Node;

typedef function<bool(const Node&, const Node&)> Compare;

public:

vector<string> topKFrequent(vector<string>& words, int k) {

unordered_map<string, int> count;

for (const string& word : words)

++count[word];

Compare comparator = [](const Node& a, const Node& b) {

// order by alphabet ASC

if (a.second == b.second)

return a.first < b.first;

// order by freq DESC

return a.second > b.second;

};

// Min heap by frequency

priority_queue<Node, vector<Node>, Compare> q(comparator);

// O(n*logk)

for (const auto& kv : count) {

q.push(kv);

if (q.size() > k) q.pop();

}

vector<string> ans;

while (!q.empty()) {

ans.push_back(q.top().first);

q.pop();

}

std::reverse(ans.begin(), ans.end());

return ans;

}

};

Related Problems

[解题报告] LeetCode 347. Top K Frequent Elements

花花酱 LeetCode 207. Course Schedule

By zxi on October 20, 2017

Problem:

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

1	2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

1	2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Idea:

Finding cycles O(n^2) -> Topological sort O(n)

Solution 1: Topological Sort

C++

// Author: Huahua

// Time complexity: O(n)

// Runtime: 12 ms

class Solution {

public:

bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {

graph_ = vector<vector<int>>(numCourses);

for(const auto& p : prerequisites)

graph_[p.first].push_back(p.second);

// states: 0 = unkonwn, 1 == visiting, 2 = visited

vector<int> v(numCourses, 0);

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

if(dfs(i, v)) return false;

return true;

}

private:

vector<vector<int>> graph_;

bool dfs(int cur, vector<int>& v) {

if(v[cur] == 1) return true;

if(v[cur] == 2) return false;

v[cur] = 1;

for(const int t : graph_[cur])

if(dfs(t, v)) return true;

v[cur] = 2;

return false;

}

};

Java

// Author: Huahua

// Runtime: 6 ms

// HashMap is slower than ArrayList in this problem.

class Solution {

public boolean canFinish(int numCourses, int[][] prerequisites) {

ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

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

graph.add(new ArrayList<Integer>());

for (int i = 0; i < prerequisites.length; ++i) {

int course = prerequisites[i][0];

int prerequisite = prerequisites[i][1];

graph.get(course).add(prerequisite);

}

int[] visited = new int[numCourses];

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

if (dfs(i, graph, visited)) return false;

return true;

}

private boolean dfs(int curr, ArrayList<ArrayList<Integer>> graph, int[] visited) {

if (visited[curr] == 1) return true;

if (visited[curr] == 2) return false;

visited[curr] = 1;

for (int next : graph.get(curr))

if (dfs(next, graph, visited)) return true;

visited[curr] = 2;

return false;

}

Solution 2: DFS Finding cycles

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Time complexity: O(n^2)

// Runtime: 179 ms

class Solution {

public:

bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {

graph_.clear();

for(const auto& p : prerequisites)

graph_[p.first].insert(p.second);

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

vector<int> visited(numCourses, 0);

if (cycle(i, i, visited)) return false;

}

return true;

}

private:

unordered_map<int, unordered_set<int>> graph_;

bool cycle(int start, int curr, vector<int>& visited) {

if (curr == start && visited[start]) return true;

if (!graph_.count(curr)) return false;

for (const int next : graph_.at(curr)) {

if (visited[next]) continue;

visited[next] = true;

if (cycle(start, next, visited)) return true;

}

return false;

}

};

Related Pr0blems:

花花酱 LeetCode 449. Serialize and Deserialize BST

By zxi on October 19, 2017

Problem:

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Idea:

Binary format

serialized size: 4*n bytes, n is the number of nodes in the BST.

Time complexity: O(n)

Space complexity: O(n)

Solution:

C++

// Author: Huahua

// Runtime: 19 ~ 26 ms (<93.31%)

class Codec {

public:

// Encodes a tree to a single string.

string serialize(TreeNode* root) {

string s;

serialize(root, s);

return s;

}

// Decodes your encoded data to tree.

TreeNode* deserialize(string data) {

int pos = 0;

return deserialize(data, pos, INT_MIN, INT_MAX);

}

private:

void serialize(TreeNode* root, string& s) {

if (!root) return;

s.append(reinterpret_cast<const char*>(&root->val), sizeof(root->val));

serialize(root->left, s);

serialize(root->right, s);

}

TreeNode* deserialize(const string& s, int& pos, int curMin, int curMax) {

if (pos >= s.size()) return nullptr;

int val = *reinterpret_cast<const int*>(s.data() + pos);

if (val < curMin || val > curMax) return nullptr;

pos += sizeof(val);

TreeNode* root = new TreeNode(val);

root->left = deserialize(s, pos, curMin, val);

root->right = deserialize(s, pos, val, curMax);

return root;

}

};

Related Problems

[解题报告] LeetCode 297. Serialize and Deserialize Binary Tree