Posts published in October 2017

花花酱 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 149. Max Points on a Line

By zxi on October 19, 2017

Problem:

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Idea:

count by slope

Time complexity: O(n^2)

Space complexity: O(n)

Solution:

C++ / pair

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

int maxPoints(vector<Point>& points) {

int n = points.size();

int ans = 0;

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

std::map<std::pair<int,int>, int> count;

int same_points = 1;

int max_points = 0;

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

const Point& p1 = points[i];

const Point& p2 = points[j];

if (p1.x == p2.x && p1.y == p2.y)

++same_points;

else

max_points = max(max_points, ++count[getSlope(p1, p2)]);

}

ans = max(ans, same_points + max_points);

}

return ans;

}

private:

// slope dy/dx : <dy, dx>

std::pair<int, int> getSlope(const Point& p1, const Point& p2) {

const int dx = p2.x - p1.x;

const int dy = p2.y - p1.y;

// horizontal line

if (dy == 0) return { p1.y, 0 };

// vertical line

if (dx == 0) return { 0, p1.x };

const int d = gcd(dx, dy);

return { dy / d, dx / d };

}

int gcd(int m, int n) {

return n == 0 ? m : gcd(n, m % n);

}

};

C++ / long

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int maxPoints(vector<Point>& points) {

int n = points.size();

int ans = 0;

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

unordered_map<long, int> count;

int same_points = 1;

int max_points = 0;

const Point& p1 = points[i];

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

const Point& p2 = points[j];

if (p1.x == p2.x && p1.y == p2.y)

++same_points;

else

max_points = max(max_points, ++count[getSlope(p1, p2)]);

}

ans = max(ans, same_points + max_points);

}

return ans;

}

private:

// slope dy/dx : dy << 32 | dx

long getSlope(const Point& p1, const Point& p2) {

const int dx = p2.x - p1.x;

const int dy = p2.y - p1.y;

// horizontal line

if (dy == 0) return static_cast<long>(p1.y) << 32 | 0;

// vertical line

if (dx == 0) return static_cast<long>(0)<< 32 | p1.x;

const int d = __gcd(dx, dy);

return static_cast<long>(dy / d) << 32 | (dx / d);

}

};

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

花花酱 LeetCode 124. Binary Tree Maximum Path Sum

By zxi on October 17, 2017

Problem:

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

/ \

2 3

Return 6.

Idea:

Recursion

Time complexity O(n)

Space complexity O(h)

Solution: Recursion

C++

// Author: Huahua

// Runtime: 19 ms

class Solution {

public:

int maxPathSum(TreeNode* root) {

if (!root) return 0;

int ans = INT_MIN;

maxPathSum(root, ans);

return ans;

}

private:

int maxPathSum(TreeNode* root, int& ans) {

if (!root) return 0;

int l = max(0, maxPathSum(root->left, ans));

int r = max(0, maxPathSum(root->right, ans));

int sum = l + r + root->val;

ans = max(ans, sum);

return max(l, r) + root->val;

}

};

Python3

"""

Author: Huahua

Runtime: 138 ms (< 90.38%)

"""

class Solution(object):

def _maxPathSum(self, root):

if not root: return -sys.maxint

l = max(0, self._maxPathSum(root.left))

r = max(0, self._maxPathSum(root.right))

self.ans = max(self.ans, root.val + l + r)

return root.val + max(l, r)

def maxPathSum(self, root):

self.ans = -sys.maxint

self._maxPathSum(root)

return self.ans

Related Problems: