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

花花酱 LeetCode 37. Sudoku Solver

By zxi on October 16, 2017

Problem:

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle…

…and its solution numbers marked in red.

Idea:

DFS + backtracking

Solution:

C++

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

void solveSudoku(vector<vector<char>>& board) {

rows_ = vector<vector<int>>(9, vector<int>(10));

cols_ = vector<vector<int>>(9, vector<int>(10));

boxes_ = vector<vector<int>>(9, vector<int>(10));

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

for(int j = 0; j < 9; j++) {

const char c = board[i][j];

if ( c != '.') {

int n = c - '0';

int bx = j / 3;

int by = i / 3;

rows_[i][n] = 1;

cols_[j][n] = 1;

boxes_[by * 3 + bx][n] = 1;

}

fill(board, 0, 0);

}

private:

vector<vector<int>> rows_, cols_, boxes_;

bool fill(vector<vector<char>>& board, int x, int y) {

if (y == 9)

return true;

int nx = (x + 1) % 9;

int ny = (nx == 0) ? y + 1 : y;

if (board[y][x] != '.') return fill(board, nx, ny);

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

int bx = x / 3;

int by = y / 3;

int box_key = by * 3 + bx;

if (!rows_[y][i] && !cols_[x][i] && !boxes_[box_key][i]) {

rows_[y][i] = 1;

cols_[x][i] = 1;

boxes_[box_key][i] = 1;

board[y][x] = i + '0';

if (fill(board, nx, ny)) return true;

board[y][x] = '.';

boxes_[box_key][i] = 0;

cols_[x][i] = 0;

rows_[y][i] = 0;

}

return false;

}

};

Related Problems:

[解题报告] LeetCode 51. N-Queens

Huahua's Tech Road

花花酱 LeetCode 207. Course Schedule

Solution 1: Topological Sort

C++

Java

Solution 2: DFS Finding cycles

C++

Related Pr0blems:

花花酱 LeetCode 149. Max Points on a Line

Solution:

C++ / pair

C++ / long

花花酱 LeetCode 449. Serialize and Deserialize BST

花花酱 LeetCode 124. Binary Tree Maximum Path Sum

Solution: Recursion

C++

Python3

花花酱 LeetCode 37. Sudoku Solver