Posts published in “Medium”

花花酱 LeetCode 416. Partition Equal Subset Sum

By zxi on December 31, 2017

题目大意：

给你一个正整数的数组，问你能否把元素划分成元素和相等的两组。

Problem:

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

Each of the array element will not exceed 100.
The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

Idea:

DP 动态规划

Solution:

Time complexity: O(n*sum)

Space complexity: O(sum)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

bool canPartition(vector<int>& nums) {

const int sum = std::accumulate(nums.begin(), nums.end(), 0);

if (sum % 2 != 0) return false;

vector<int> dp(sum + 1, 0);

dp[0] = 1;

for (const int num : nums) {

for (int i = sum; i >= 0; --i)

if (dp[i]) dp[i + num] = 1;

if (dp[sum / 2]) return true;

}

return false;

}

};

花花酱 LeetCode 377. Combination Sum IV

By zxi on December 15, 2017

Problem:

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]

target = 4

The possible combination ways are:

(1, 1, 1, 1)

(1, 1, 2)

(1, 2, 1)

(1, 3)

(2, 1, 1)

(2, 2)

(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

题目大意：给你一些数和一个目标值，问使用这些数(每个数可以被使用任意次数)加起来等于目标值的组合（其实是不重复的排列）有多少种。

Idea:

Solution:

C++ / Recursion + Memorization

// Author: Huahua

// Runtime: 0 ms

class Solution {

public:

int combinationSum4(vector<int>& nums, int target) {

m_ = vector<int>(target + 1, -1);

m_[0] = 1;

return dp(nums, target);

}

private:

int dp(const vector<int>& nums, int target) {

if (target < 0) return 0;

if (m_[target] != -1) return m_[target];

int ans = 0;

for (const int num : nums)

ans += dp(nums, target - num);

return m_[target] = ans;

}

vector<int> m_;

};

C++ / DP

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

int combinationSum4(vector<int>& nums, int target) {

vector<int> dp(target + 1, 0); // dp[i] # of combinations sum up to i

dp[0] = 1;

for (int i = 1; i <= target; ++i)

for (const int num : nums)

if (i - num >= 0)

dp[i] += dp[i - num];

return dp[target];

}

};

Related Problems:

花花酱 LeetCode 210. Course Schedule II

By zxi on December 13, 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, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

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 the correct course order is [0,1]

1	4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.

题目大意：

给你一些课程和它的先修课程，让你输出修课顺序。如果无法修完所有课程，返回空数组。

Idea

Topological sorting

拓扑排序

Solution 1: Topological Sorting

Time complexity: O(V+E)

Space complexity: O(V+E)

C++

// Author: Huahua

// Runtime: 16 ms

class Solution {

public:

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

vector<vector<int>> graph(numCourses);

for(const auto& p : prerequisites)

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

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

vector<int> v(numCourses, 0);

vector<int> ans;

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

if (dfs(i, graph, v, ans)) return {};

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

return ans;

}

private:

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

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

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

v[cur] = 1;

for (const int t : graph[cur])

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

v[cur] = 2;

ans.push_back(cur);

return false;

}

};

Java

// Author: Huahua

// Runtime: 83 ms

class Solution {

public int[] findOrder(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];

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

Integer index = numCourses;

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

if (dfs(i, graph, visited, ans)) return new int[0];

return ans.stream().mapToInt(i->i).toArray();

}

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

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, ans)) return true;

visited[curr] = 2;

ans.add(curr);

return false;

}

Posts published in “Medium”

花花酱 LeetCode 416. Partition Equal Subset Sum

花花酱 LeetCode 377. Combination Sum IV

花花酱 LeetCode 210. Course Schedule II

Problem

Idea

Solution 1: Topological Sorting

C++

Java

Related Problems:

花花酱 LeetCode 742. Closest Leaf in a Binary Tree

花花酱 LeetCode 743. Network Delay Time