Posts tagged as “search”

花花酱 LeetCode 967. Numbers With Same Consecutive Differences

By zxi on December 30, 2018

Problem

Return all non-negative integers of length N such that the absolute difference between every two consecutive digits is K.

Note that every number in the answer must not have leading zeros except for the number 0 itself. For example, 01 has one leading zero and is invalid, but 0 is valid.

You may return the answer in any order.

Example 1:

Input: N = 3, K = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.

Example 2:

Input: N = 2, K = 1
Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

Note:

1 <= N <= 9
0 <= K <= 9

Solution: Search

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

C++/DFS

// Author: Huahua, running time: 8ms

class Solution {

public:

vector<int> numsSameConsecDiff(int N, int K) {

vector<int> ans;

if (N == 1) ans.push_back(0);

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

dfs(N - 1, K, i, ans);

return ans;

}

private:

void dfs(int N, int K, int cur, vector<int>& ans) {

if (N == 0) {

ans.push_back(cur);

return;

}

int l = cur % 10;

if (l + K < 10)

dfs(N - 1, K, cur * 10 + l + K, ans);

if (l >= K && K != 0)

dfs(N - 1, K, cur * 10 + l - K, ans);

}

};

C++/BFS

// Author: Huahua, running time: 4 ms

class Solution {

public:

vector<int> numsSameConsecDiff(int N, int K) {

deque<int> q{1,2,3,4,5,6,7,8,9};

if (N == 1) q.push_front(0);

while (--N) {

int size = q.size();

while (size--) {

int num = q.front(); q.pop_front();

int r = num % 10;

if (r + K <= 9)

q.push_back(num * 10 + r + K);

if (r - K >= 0 && K != 0)

q.push_back(num * 10 + r - K);

}

return vector<int>(cbegin(q), cend(q));

}

};

花花酱 LeetCode 78. Subsets

By zxi on December 22, 2018

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:[  [3],  [1],  [2],  [1,2,3],  [1,3],  [2,3],  [1,2],  []]

Solution: Combination

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

Implemention 1: DFS

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

vector<vector<int>> subsets(vector<int>& nums) {

vector<vector<int>> ans;

vector<int> cur;

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

dfs(nums, i, 0, cur, ans);

return ans;

}

private:

void dfs(const vector<int>& nums, int n, int s,

vector<int>& cur, vector<vector<int>>& ans) {

if (n == cur.size()) {

ans.push_back(cur);

return;

}

for (int i = s; i < nums.size(); ++i) {

cur.push_back(nums[i]);

dfs(nums, n, i + 1, cur, ans);

cur.pop_back();

}

};

Python3

# Author: Huahua, running time: 60 ms

class Solution:

def subsets(self, nums):

ans = []

def dfs(n, s, cur):

if n == len(cur):

ans.append(cur.copy())

return

for i in range(s, len(nums)):

cur.append(nums[i])

dfs(n, i + 1, cur)

cur.pop()

for i in range(len(nums) + 1):

dfs(i, 0, [])

return ans

Implementation 2: Binary

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

vector<vector<int>> subsets(vector<int>& nums) {

const int n = nums.size();

vector<vector<int>> ans;

for (int s = 0; s < 1 << n; ++s) {

vector<int> cur;

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

if (s & (1 << i)) cur.push_back(nums[i]);

ans.push_back(cur);

}

return ans;

}

};

Python3

# Author: Huahua, 40 ms

class Solution:

def subsets(self, nums):

n = len(nums)

return [[nums[i] for i in range(n) if s & 1 << i > 0] for s in range(1 << n)]

花花酱 LeetCode 943. Find the Shortest Superstring

By zxi on November 18, 2018

Problem

Given an array A of strings, find any smallest string that contains each string in A as a substring.

We may assume that no string in A is substring of another string in A.

Example 1:

Input: ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
Explanation: All permutations of "alex","loves","leetcode" would also be accepted.

Example 2:

Input: ["catg","ctaagt","gcta","ttca","atgcatc"]
Output: "gctaagttcatgcatc"

Note:

1 <= A.length <= 12
1 <= A[i].length <= 20

Solution 1: Search + Pruning

Try all permutations. Pre-process the cost from word[i] to word[j] and store it in g[i][j].

Time complexity: O(n!)

Space complexity: O(n)

C++

// Author: Huahua, running time: 692 ms

class Solution {

public:

string shortestSuperstring(vector<string>& A) {

const int n = A.size();

g_ = vector<vector<int>>(n, vector<int>(n));

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

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

g_[i][j] = A[j].length();

for (int k = 1; k <= min(A[i].length(), A[j].length()); ++k)

if (A[i].substr(A[i].size() - k) == A[j].substr(0, k))

g_[i][j] = A[j].length() - k;

}

vector<int> path(n);

best_len_ = INT_MAX;

dfs(A, 0, 0, 0, path);

string ans = A[best_path_[0]];

for (int k = 1; k < best_path_.size(); ++k) {

int i = best_path_[k - 1];

int j = best_path_[k];

ans += A[j].substr(A[j].length() - g_[i][j]);

}

return ans;

}

private:

vector<vector<int>> g_;

vector<int> best_path_;

int best_len_;

void dfs(const vector<string>& A, int d, int used, int cur_len, vector<int>& path) {

if (cur_len >= best_len_) return;

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

best_len_ = cur_len;

best_path_ = path;

return;

}

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

if (used & (1 << i)) continue;

path[d] = i;

dfs(A,

d + 1,

used | (1 << i),

d == 0 ? A[i].length() : cur_len + g_[path[d - 1]][i],

path);

}

};

Java

// Author: Huahua, 439 ms, 35.8MB

class Solution {

private int n;

private int[][] g;

private String[] a;

private int best_len;

private int[] path;

private int[] best_path;

private void dfs(int d, int used, int cur_len) {

if (cur_len >= best_len) return;

if (d == n) {

best_len = cur_len;

best_path = path.clone();

return;

}

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

if ((used & (1 << i)) != 0) continue;

path[d] = i;

dfs(d + 1,

used | (1 << i),

d == 0 ? a[i].length() : cur_len + g[path[d - 1]][i]);

}

public String shortestSuperstring(String[] A) {

n = A.length;

g = new int[n][n];

a = A;

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

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

g[i][j] = A[j].length();

for (int k = 1; k <= Math.min(A[i].length(), A[j].length()); ++k)

if (A[i].substring(A[i].length() - k).equals(A[j].substring(0, k)))

g[i][j] = A[j].length() - k;

}

path = new int[n];

best_len = Integer.MAX_VALUE;

dfs(0, 0, 0);

String ans = A[best_path[0]];

for (int k = 1; k < n; ++k) {

int i = best_path[k - 1];

int j = best_path[k];

ans += A[j].substring(A[j].length() - g[i][j]);

}

return ans;

}

Solution 2: DP

g[i][j] is the cost of appending word[j] after word[i], or weight of edge[i][j].

We would like find the shortest path to visit each node from 0 to n – 1 once and only once this is called the Travelling sells man’s problem which is NP-Complete.

We can solve it with DP that uses exponential time.

dp[s][i] := min distance to visit nodes (represented as a binary state s) once and only once and the path ends with node i.

e.g. dp[7][1] is the min distance to visit nodes (0, 1, 2) and ends with node 1, the possible paths could be (0, 2, 1), (2, 0, 1).

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

Space complexity: O(n * 2^n)

C++

// Author: Huahua, running time: 20 ms

class Solution {

public:

string shortestSuperstring(vector<string>& A) {

const int n = A.size();

vector<vector<int>> g(n, vector<int>(n));

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

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

g[i][j] = A[j].length();

for (int k = 1; k <= min(A[i].length(), A[j].length()); ++k)

if (A[i].substr(A[i].size() - k) == A[j].substr(0, k))

g[i][j] = A[j].length() - k;

}

vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX / 2));

vector<vector<int>> parent(1 << n, vector<int>(n, -1));

for (int i = 0; i < n; ++i) dp[1 << i][i] = A[i].length();

for (int s = 1; s < (1 << n); ++s) {

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

if (!(s & (1 << j))) continue;

int ps = s & ~(1 << j);

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

if (dp[ps][i] + g[i][j] < dp[s][j]) {

dp[s][j] = dp[ps][i] + g[i][j];

parent[s][j] = i;

}

auto it = min_element(begin(dp.back()), end(dp.back()));

int j = it - begin(dp.back());

int s = (1 << n) - 1;

string ans;

while (s) {

int i = parent[s][j];

if (i < 0) ans = A[j] + ans;

else ans = A[j].substr(A[j].length() - g[i][j]) + ans;

s &= ~(1 << j);

j = i;

}

return ans;

}

};

花花酱 LeetCode 638. Shopping Offers

By zxi on August 6, 2018

Problem

In LeetCode Store, there are some kinds of items to sell. Each item has a price.

However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.

You are given the each item’s price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers.

Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer.

You could use any of special offers as many times as you want.

Example 1:

Input: [2,5], [[3,0,5],[1,2,10]], [3,2]
Output: 14
Explanation: 
There are two kinds of items, A and B. Their prices are $2 and $5 respectively. 
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B. 
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.

Example 2:

Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
Output: 11
Explanation: 
The price of A is $2, and $3 for B, $4 for C. 
You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C. 
You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C. 
You cannot add more items, though only $9 for 2A ,2B and 1C.

Note:

There are at most 6 kinds of items, 100 special offers.
For each item, you need to buy at most 6 of them.
You are not allowed to buy more items than you want, even if that would lower the overall price.

Solution: Search

Try all combinations.

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {

int with_offer = INT_MAX;

for (const auto& offer : special) {

vector<int> new_needs(needs);

bool valid_offer = true;

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

if (!(valid_offer &= ((new_needs[i] -= offer[i]) >= 0)))

break;

if (!valid_offer) continue;

with_offer = min(with_offer, shoppingOffers(price, special, new_needs) + offer.back());

}

int without_offer = inner_product(begin(price), end(price), begin(needs), 0);

return min(with_offer, without_offer);

}

};

花花酱 LeetCode 842. Split Array into Fibonacci Sequence

By zxi on July 26, 2018

Problem

Given a string S of digits, such as S = "123456579", we can split it into a Fibonacci-like sequence [123, 456, 579].

Formally, a Fibonacci-like sequence is a list F of non-negative integers such that:

0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type);
F.length >= 3;
and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2.

Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself.

Return any Fibonacci-like sequence split from S, or return [] if it cannot be done.

Example 1:

Input: "123456579"
Output: [123,456,579]

Example 2:

Input: "11235813"
Output: [1,1,2,3,5,8,13]

Example 3:

Input: "112358130"
Output: []
Explanation: The task is impossible.

Example 4:

Input: "0123"
Output: []
Explanation: Leading zeroes are not allowed, so "01", "2", "3" is not valid.

Example 5:

Input: "1101111"
Output: [110, 1, 111]
Explanation: The output [11, 0, 11, 11] would also be accepted.

Note:

1 <= S.length <= 200
S contains only digits.

Solution: DFS

Time complexity: O(2^n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

vector<int> splitIntoFibonacci(string s) {

const int n = s.length();

vector<int> nums;

function<bool(int)> dfs = [&](int pos) {

if (pos == n) return nums.size() >= 3;

int max_len = s[pos] == '0' ? 1 : 10;

long num = 0;

for (int i = pos; i < min(pos + max_len, n); ++i) {

num = num * 10 + (s[i] - '0');

if (num > INT_MAX) break;

if (nums.size() >= 2) {

long sum = nums.rbegin()[0];

sum += nums.rbegin()[1];

if (num > sum) break;

else if (num < sum) continue;

// num must equaals to sum.

}

nums.push_back(num);

if (dfs(i + 1)) return true;

nums.pop_back();

}

return false;

};

dfs(0);

return nums;

}

};