花花酱 LeetCode 494. Target Sum

By zxi on January 9, 2018

题目大意：给你一串数字，你可以在每个数字前放置+或-，问有多少种方法可以使得表达式的值等于target。You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3.

Output: 5

Explanation:

-1+1+1+1+1 = 3

+1-1+1+1+1 = 3

+1+1-1+1+1 = 3

+1+1+1-1+1 = 3

+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.

Note:

The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.

Idea: DP

Solution 1: DP

Time complexity: O(n*sum)

Space complexity: O(n*sum)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

const int n = nums.size();

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

if (sum < S) return 0;

const int offset = sum;

// ways[i][j] means total ways to sum up to (j - offset) using nums[0] ~ nums[i - 1].

vector<vector<int>> ways(n + 1, vector<int>(sum + offset + 1, 0));

ways[0][offset] = 1;

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

for (int j = nums[i]; j < 2 * sum + 1 - nums[i]; ++j)

if (ways[i][j]) {

ways[i + 1][j + nums[i]] += ways[i][j];

ways[i + 1][j - nums[i]] += ways[i][j];

}

return ways.back()[S + offset];

}

};

C++ SC O(n)

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

const int n = nums.size();

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

if (sum < std::abs(S)) return 0;

const int kOffset = sum;

const int kMaxN = sum * 2 + 1;

vector<int> ways(kMaxN, 0);

ways[kOffset] = 1;

for (int num : nums) {

vector<int> tmp(kMaxN, 0);

for (int i = num; i < kMaxN - num; ++i)

if (ways[i]) {

tmp[i + num] += ways[i];

tmp[i - num] += ways[i];

}

std::swap(ways, tmp);

}

return ways[S + kOffset];

}

};

Java

// Author: Huahua

// Running time: 28 ms

class Solution {

public int findTargetSumWays(int[] nums, int S) {

int sum = 0;

for (final int num : nums)

sum += num;

if (sum < S) return 0;

final int kOffset = sum;

final int kMaxN = sum * 2 + 1;

int[] ways = new int[kMaxN];

ways[kOffset] = 1;

for (final int num : nums) {

int[] tmp = new int[kMaxN];

for (int i = num; i < kMaxN - num; ++i) {

tmp[i + num] += ways[i];

tmp[i - num] += ways[i];

}

ways = tmp;

}

return ways[S + kOffset];

}

C++ / V2

// Author: Huahua

// Running time: 17 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

const int n = nums.size();

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

if (sum < std::abs(S)) return 0;

const int kOffset = sum;

const int kMaxN = sum * 2 + 1;

vector<int> ways(kMaxN, 0);

ways[kOffset] = 1;

for (int num : nums) {

vector<int> tmp(kMaxN, 0);

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

if (i + num < kMaxN) tmp[i] += ways[i + num];

if (i - num >= 0) tmp[i] += ways[i - num];

}

std::swap(ways, tmp);

}

return ways[S + kOffset];

}

};

Solution 2: DFS

Time complexity: O(2^n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 422 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

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

if (sum < std::abs(S)) return 0;

int ans = 0;

dfs(nums, 0, S, ans);

return ans;

}

private:

void dfs(const vector<int>& nums, int d, int S, int& ans) {

if (d == nums.size()) {

if (S == 0) ++ans;

return;

}

dfs(nums, d + 1, S - nums[d], ans);

dfs(nums, d + 1, S + nums[d], ans);

}

};

Java

// Author: Huahua

// Running time: 615 ms

class Solution {

private int ans;

public int findTargetSumWays(int[] nums, int S) {

int sum = 0;

for (final int num : nums)

sum += num;

if (sum < Math.abs(S)) return 0;

ans = 0;

dfs(nums, 0, S);

return ans;

}

private void dfs(int[] nums, int d, int S) {

if (d == nums.length) {

if (S == 0) ++ans;

return;

}

dfs(nums, d + 1, S - nums[d]);

dfs(nums, d + 1, S + nums[d]);

}

Solution 3: Subset sum

Time complexity: O(n*sum)

Space complexity: O(sum)

C++ w/ copy

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

S = std::abs(S);

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

if (sum < S || (S + sum) % 2 != 0) return 0;

const int target = (S + sum) / 2;

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

dp[0] = 1;

for (int num : nums) {

vector<int> tmp(dp);

for (int j = 0; j <= target - num; ++j)

tmp[j + num] += dp[j];

std::swap(dp, tmp);

}

return dp[target];

}

};

C++ w/o copy

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

S = std::abs(S);

const int n = nums.size();

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

if (sum < S || (S + sum) % 2 != 0) return 0;

const int target = (S + sum) / 2;

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

dp[0] = 1;

for (int num : nums)

for (int j = target; j >= num; --j)

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

return dp[target];

}

};

花花酱 LeetCode 759. Employee Free Time

By zxi on January 8, 2018

题目大意：给你每个员工的日历，让你找出所有员工都有空的时间段。

Problem:

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

Example 1:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]

Output: [[3,4]]

Explanation:

There are a total of three employees, and all common

free time intervals would be [-inf, 1], [3, 4], [10, inf].

We discard any intervals that contain inf as they aren't finite.

Example 2:

1 2	Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]] Output: [[5,6],[7,9]]

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined.)

Also, we wouldn’t include intervals like [5, 5] in our answer, as they have zero length.

Note:

schedule and schedule[i] are lists with lengths in range [1, 50].
0 <= schedule[i].start < schedule[i].end <= 10^8.

Idea:

Merge Intervals (virtually)

Solution:

C++

Time complexity: O(nlogn)

Space complexity: O(n)

n is the total number of intervals, n <= 2500

// Author: Huahua

// Running time: 81 ms

class Solution {

public:

vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) {

vector<Interval> all;

for (const auto intervals : schedule)

all.insert(all.end(), intervals.begin(), intervals.end());

std::sort(all.begin(), all.end(),

[](const Interval& a, const Interval& b){

return a.start < b.start;

});

vector<Interval> ans;

int end = all.front().end;

for (const Interval& busy : all) {

if (busy.start > end)

ans.emplace_back(end, busy.start);

end = max(end, busy.end);

}

return ans;

}

};

Related Problems:

花花酱 LeetCode 758. Bold Words in String

By zxi on January 8, 2018

题目大意：给你一个字符串和一些要加粗的单词，返回加粗后的HTML代码。

Problem:

Given a set of keywords words and a string S, make all appearances of all keywords in S bold. Any letters between  and  tags become bold.

The returned string should use the least number of tags possible, and of course the tags should form a valid combination.

For example, given that words = ["ab", "bc"] and S = "aabcd", we should return "aabcd". Note that returning "aabcd" would use more tags, so it is incorrect.

Note:

words has length in range [0, 50].
words[i] has length in range [1, 10].
S has length in range [0, 500].
All characters in words[i] and S are lowercase letters.

Solution:

C++

Time complexity: O(nL^2)

Space complexity: O(n + d)

d: size of dictionary

L: max length of the word which is 10.

// Author: Huahua

// Running time: 13 ms

class Solution {

public:

string boldWords(vector<string>& words, string S) {

const int kMaxWordLen = 10;

unordered_set<string> dict(words.begin(), words.end());

int n = S.length();

vector<int> bolded(n, 0);

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

for (int l = 1; l <= min(n - i, kMaxWordLen); ++l)

if (dict.count(S.substr(i, l)))

std::fill(bolded.begin() + i, bolded.begin() + i + l, 1);

string ans;

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

if (bolded[i] && (i == 0 || !bolded[i - 1])) ans += "";

ans += S[i];

if (bolded[i] && (i == n - 1 || !bolded[i + 1])) ans += "";

}

return ans;

}

};

花花酱 LeetCode 760. Find Anagram Mappings

By zxi on January 8, 2018

题目大意：输出数组A中每个元素在数组B中的索引。

Given two lists Aand B, and B is an anagram of A. B is an anagram of A means B is made by randomizing the order of the elements in A.

We want to find an index mapping P, from A to B. A mapping P[i] = j means the ith element in A appears in B at index j.

These lists A and B may contain duplicates. If there are multiple answers, output any of them.

For example, given

1 2	A = [12, 28, 46, 32, 50] B = [50, 12, 32, 46, 28]

We should return

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

as P[0] = 1 because the 0th element of A appears at B[1], and P[1] = 4 because the 1st element of Aappears at B[4], and so on.

Solution:

C++

Time complexity: O(nlogn)

Space complexity: O(n)

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

vector<int> anagramMappings(vector<int>& A, vector<int>& B) {

map<int, int> indices;

for (int i = 0; i < B.size(); ++i)

indices[B[i]] = i;

vector<int> ans;

for (const int a : A)

ans.push_back(indices[a]);

return ans;

}

};

C++ / No duplication

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

vector<int> anagramMappings(vector<int>& A, vector<int>& B) {

map<int, vector<int>> indices;

for (int i = 0; i < B.size(); ++i)

indices[B[i]].push_back(i);

vector<int> ans;

for (const int a : A) {

ans.push_back(indices[a].back());

indices[a].pop_back();

}

return ans;

}

};

花花酱 LeetCode 264. Ugly Number II

By zxi on January 7, 2018

题目大意：让你找到第n个丑数。

Problem:

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number, and n does not exceed 1690.

Solution:

C++ / O(n)

// Author: huahua

// Running time: 6 ms

class Solution {

public:

int nthUglyNumber(int n) {

static vector<int> nums{1};

static int i2 = 0;

static int i3 = 0;

static int i5 = 0;

while (nums.size() < n) {

const int next2 = nums[i2] * 2;

const int next3 = nums[i3] * 3;

const int next5 = nums[i5] * 5;

const int next = min(next2, min(next3, next5));

if (next == next2) ++i2;

if (next == next3) ++i3;

if (next == next5) ++i5;

nums.push_back(next);

}

return nums[n - 1];

}

};

C++ /query * O(NlogN)

// Author: Huahua

// Running time: 89 ms

class Solution {

public:

int nthUglyNumber(int n) {

vector<int> nums;

for (long a = 1; a <= INT_MAX; a *= 2)

for (long b = a; b <= INT_MAX; b *= 3)

for (long c = b; c <= INT_MAX; c *= 5)

nums.push_back(c);

std::sort(nums.begin(), nums.end());

return nums[n - 1];

}

};

C++ / static variables O(NlogN) + query*O(1)

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

int nthUglyNumber(int n) {

static vector<int> nums;

if (nums.empty()) {

for (long a = 1; a <= INT_MAX; a *= 2)

for (long b = a; b <= INT_MAX; b *= 3)

for (long c = b; c <= INT_MAX; c *= 5)

nums.push_back(c);

std::sort(nums.begin(), nums.end());

}

return nums[n - 1];

}

};

C++ / table O(1)
leetcode_264_table.cc

Huahua's Tech Road

花花酱 LeetCode 494. Target Sum

Idea: DP

Solution 1: DP

C++

C++ SC O(n)

Java

C++ / V2

Solution 2: DFS

C++

Java

Solution 3: Subset sum

C++ w/ copy

C++ w/o copy

花花酱 LeetCode 759. Employee Free Time

花花酱 LeetCode 758. Bold Words in String

花花酱 LeetCode 760. Find Anagram Mappings

花花酱 LeetCode 264. Ugly Number II

Related Problems: