Huahua’s Tech Road

花花酱 LeetCode 322. Coin Change

By zxi on January 2, 2018

题目大意：给你一些不同币值的硬币，问你最少需要多少个硬币才能组成amount，假设每种硬币有无穷多个。

Problem:

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Idea:

DP /knapsack

Solution1:

C++ / DP

Time complexity: O(n*amount^2)

Space complexity: O(amount)

// Author: Huahua

// Running time: 189 ms

class Solution {

public:

int coinChange(vector<int>& coins, int amount) {

vector<int> dp(amount + 1, INT_MAX);

dp[0] = 0;

for (auto coin : coins) {

for (int i = amount - coin; i >= 0; --i)

if (dp[i] != INT_MAX)

for (int k = 1; k * coin + i <= amount; ++k)

dp[i + k * coin] = min(dp[i + k * coin], dp[i] + k);

}

return dp[amount] == INT_MAX ? -1 : dp[amount];

}

};

Solution2:

C++ / DP

Time complexity: O(n*amount)

Space complexity: O(amount)

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int coinChange(vector<int>& coins, int amount) {

// dp[i] = min coins to make up to amount i

vector<int> dp(amount + 1, INT_MAX);

dp[0] = 0;

for (int coin : coins) {

for (int i = coin; i <= amount; ++i)

if (dp[i - coin] != INT_MAX)

dp[i] = min(dp[i], dp[i - coin] + 1);

}

return dp[amount] == INT_MAX ? -1 : dp[amount];

}

};

Python3

"""

Author: Huahua

Running time: 632 ms beats 90.27%

"""

class Solution:

def coinChange(self, coins, amount):

INVALID = 2**32

dp = [INVALID] * (amount + 1)

dp[0] = 0

for coin in coins:

for i in range(coin, amount + 1):

if dp[i - coin] >= dp[i]: continue

dp[i] = dp[i - coin] + 1

return -1 if dp[amount] == INVALID else dp[amount]

Solution3:

C++ / DFS

Time complexity: O(amount^n/(coin_0*coin_1*…*coin_n))

Space complexity: O(n)

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

int coinChange(vector<int>& coins, int amount) {

// Sort coins in desending order

std::sort(coins.rbegin(), coins.rend());

int ans = INT_MAX;

coinChange(coins, 0, amount, 0, ans);

return ans == INT_MAX ? -1 : ans;

}

private:

void coinChange(const vector<int>& coins,

int s, int amount, int count, int& ans) {

if (amount == 0) {

ans = min(ans, count);

return;

}

if (s == coins.size()) return;

const int coin = coins[s];

for (int k = amount / coin; k >= 0 && count + k < ans; k--)

coinChange(coins, s + 1, amount - k * coin, count + k, ans);

}

};

Python3

"""

Author: Huahua

Running time: 200ms

"""

class Solution:

def coinChange(self, coins, amount):

coins.sort(reverse=True)

INVALID = 10**10

self.ans = INVALID

def dfs(s, amount, count):

if amount == 0:

self.ans = count

return

if s == len(coins): return

coin = coins[s]

for k in range(amount // coin, -1, -1):

if count + k >= self.ans: break

dfs(s + 1, amount - k * coin, count + k)

dfs(0, amount, 0)

return -1 if self.ans == INVALID else self.ans

花花酱 LeetCode 754. Reach a Number

By zxi on January 1, 2018

题目大意：第i时刻可以移动+i,-i单位距离。初始在原点，问最少对少时间可以移动到target坐标。

Problem:

You are standing at position 0 on an infinite number line. There is a goal at position target.

On each move, you can either go left or right. During the n-th move (starting from 1), you take n steps.

Return the minimum number of steps required to reach the destination.

Example 1:

Input: target = 3

Output: 2

Explanation:

On the first move we step from 0 to 1.

On the second step we step from 1 to 3.

Example 2:

Input: target = 2

Output: 3

Explanation:

On the first move we step from 0 to 1.

On the second move we step from 1 to -1.

On the third move we step from -1 to 2.

Note:

target will be a non-zero integer in the range [-10^9, 10^9].

Idea:

Math

Time complexity: O(sqrt(target))

Space complexity: O(1)

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

int reachNumber(int target) {

target = std::abs(target);

int k = 0;

int sum = 0;

while (sum < target) sum += (++k);

const int d = sum - target;

if (d % 2 == 0) return k;

return k + 1 + (k % 2);

}

};

O(1)

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

int reachNumber(int target) {

target = std::abs(target);

int k = sqrt(target * 2);

while (sum(k) < target) ++k;

int d = sum(k) - target;

if (d % 2 == 0) return k;

return k + 1 + (k % 2);

}

private:

int sum(int k) {

return k * (k + 1) / 2;

}

};

Wechat 微信公众号

By zxi on January 1, 2018

微信公众号：huahualeetcode

扫码关注

花花酱 LeetCode 652. Find Duplicate Subtrees

By zxi on December 31, 2017

652. Find Duplicate SubtreesMedium730151FavoriteShare

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with same node values.

Example 1:

The following are two duplicate subtrees:

2
/
4

and

Therefore, you need to return above trees’ root in the form of a list.

Solution 1: Serialization

Time complexity: O(n^2)
Space complexity: O(n^2)

C++

// Author: Huahua

// Runtime: 29 ms

class Solution {

public:

vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {

unordered_map<string, int> counts;

vector<TreeNode*> ans;

serialize(root, counts, ans);

return ans;

}

private:

string serialize(TreeNode* root, unordered_map<string, int>& counts, vector<TreeNode*>& ans) {

if (!root) return "#";

string key = to_string(root->val) + ","

+ serialize(root->left, counts, ans) + ","

+ serialize(root->right, counts, ans);

if (++counts[key] == 2)

ans.push_back(root);

return key;

}

};

Solution 2: int id for each unique subtree

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

// Runtime: 8 ms

class Solution {

public:

vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {

unordered_map<long, pair<int,int>> counts;

vector<TreeNode*> ans;

getId(root, counts, ans);

return ans;

}

private:

int getId(TreeNode* root,

unordered_map<long, pair<int,int>>& counts,

vector<TreeNode*>& ans) {

if (!root) return 0;

long key = (static_cast<long>(static_cast<unsigned>(root->val)) << 32) +

(getId(root->left, counts, ans) << 16) +

getId(root->right, counts, ans);

auto& p = counts[key];

if (p.second++ == 0)

p.first = counts.size();

else if (p.second == 2)

ans.push_back(root);

return p.first;

}

};

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

}

};

Huahua's Tech Road

花花酱 LeetCode 322. Coin Change

花花酱 LeetCode 754. Reach a Number

Wechat 微信公众号

花花酱 LeetCode 652. Find Duplicate Subtrees

Solution 1: Serialization

C++

C++

花花酱 LeetCode 416. Partition Equal Subset Sum