Posts tagged as “search”

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

}

};

花花酱 LeetCode 22. Generate Parentheses

By zxi on July 26, 2018

Problem

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solution: DFS

Time complexity: O(2^n)

Space complexity: O(k + n)

C++

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

vector<string> generateParenthesis(int n) {

vector<string> ans;

string cur;

if (n > 0) dfs(n, n, cur, ans);

return ans;

}

private:

void dfs(int l, int r, string& s, vector<string>& ans) {

if (l + r == 0) {

ans.push_back(s);

return;

}

if (r < l) return;

if (l > 0) {

dfs(l - 1, r, s += "(", ans);

s.pop_back();

}

if (r > 0) {

dfs(l, r - 1, s += ")", ans);

s.pop_back();

}

};

Problem

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into knon-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Note:

1 <= k <= len(nums) <= 16.
0 < nums[i] < 10000.

Solution: Search

Time complexity: O(n!)

Space complexity: O(n)

// Author: Huahua

// Running time: 4 ms (<99.21%)

class Solution {

public:

bool canPartitionKSubsets(vector<int>& nums, int k) {

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

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

sort(nums.rbegin(), nums.rend());

return dfs(nums, sum / k, 0, k, 0);

}

private:

bool dfs(const vector<int>& nums, int target, int cur, int k, int used) {

if (k == 0) return used == (1 << nums.size()) - 1;

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

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

int t = cur + nums[i];

if (t > target) break; // Important

int new_used = used | (1 << i);

if (t == target && dfs(nums, target, 0, k - 1, new_used)) return true;

else if (dfs(nums, target, t, k, new_used)) return true;

}

return false;

}

};

花花酱 LeetCode 700. Search in a Binary Search Tree

By zxi on July 12, 2018

Problem

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node’s value equals the given value. Return the subtree rooted with that node. If such node doesn’t exist, you should return NULL.

For example,

Given the tree:
        4
       / \
      2   7
     / \
    1   3

And the value to search: 2

You should return this subtree:

      2     
     / \   
    1   3

In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.

Solution: Recursion

Time complexity: O(logn ~ n)

Space complexity: O(logn ~ n)

// Author: Huahua

// Running time: 24 ms

class Solution {

public:

TreeNode* searchBST(TreeNode* root, int val) {

if (root == nullptr) return nullptr;

if (val == root->val)

return root;

else if (val > root->val)

return searchBST(root->right, val);

return searchBST(root->left, val);

}

};

花花酱 LeetCode 863. All Nodes Distance K in Binary Tree

By zxi on June 30, 2018

Problem

题目大意：给你一棵二叉树（根结点root）和一个target节点。返回所有到target的距离为K的节点。

We are given a binary tree (with root node root), a target node, and an integer value K.

Return a list of the values of all nodes that have a distance K from the target node. The answer can be returned in any order.

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
Output: [7,4,1]
Explanation: 
The nodes that are a distance 2 from the target node (with value 5)
have values 7, 4, and 1.

Note that the inputs "root" and "target" are actually TreeNodes.
The descriptions of the inputs above are just serializations of these objects.

Note:

The given tree is non-empty.
Each node in the tree has unique values 0 <= node.val <= 500.
The target node is a node in the tree.
0 <= K <= 1000.

Solution1: DFS + BFS

Use DFS to build the graph, and use BFS to find all the nodes that are exact K steps from target.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {

buildGraph(nullptr, root);

vector<int> ans;

unordered_set<TreeNode*> seen;

queue<TreeNode*> q;

seen.insert(target);

q.push(target);

int k = 0;

while (!q.empty() && k <= K) {

int s = q.size();

while (s--) {

TreeNode* node = q.front(); q.pop();

if (k == K) ans.push_back(node->val);

for (TreeNode* child : g[node]) {

if (seen.count(child)) continue;

q.push(child);

seen.insert(child);

}

++k;

}

return ans;

}

private:

unordered_map<TreeNode*, vector<TreeNode*>> g;

void buildGraph(TreeNode* parent, TreeNode* child) {

if (parent) {

g[parent].push_back(child);

g[child].push_back(parent);

}

if (child->left) buildGraph(child, child->left);

if (child->right) buildGraph(child, child->right);

}

};

Array version

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {

constexpr int kMaxN = 500 + 1;

g = vector<vector<int>>(kMaxN);

buildGraph(nullptr, root);

vector<int> ans;

vector<int> seen(kMaxN);

queue<int> q;

seen[target->val] = 1;

q.push(target->val);

int k = 0;

while (!q.empty() && k <= K) {

int s = q.size();

while (s--) {

int node = q.front(); q.pop();

if (k == K) ans.push_back(node);

for (int child : g[node]) {

if (seen[child]) continue;

q.push(child);

seen[child] = 1;

}

++k;

}

return ans;

}

private:

vector<vector<int>> g;

void buildGraph(TreeNode* parent, TreeNode* child) {

if (parent) {

g[parent->val].push_back(child->val);

g[child->val].push_back(parent->val);

}

if (child->left) buildGraph(child, child->left);

if (child->right) buildGraph(child, child->right);

}

};

Solution 2: Recursion

Recursively compute the distance from root to target, and collect nodes accordingly.

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 5 ms

class Solution {

public:

vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {

ans.clear();

dis(root, target, K);

return ans;

}

private:

vector<int> ans;

// Returns the distance from root to target.

// Returns -1 if target does not in the tree.

int dis(TreeNode* root, TreeNode* target, int K) {

if (root == nullptr) return -1;

if (root == target) {

collect(target, K);

return 0;

}

int l = dis(root->left, target, K);

int r = dis(root->right, target, K);

// Target in the left subtree

if (l >= 0) {

if (l == K - 1) ans.push_back(root->val);

// Collect nodes in right subtree with depth K - l - 2

collect(root->right, K - l - 2);

return l + 1;

}

// Target in the right subtree

if (r >= 0) {

if (r == K - 1) ans.push_back(root->val);

// Collect nodes in left subtree with depth K - r - 2

collect(root->left, K - r - 2);

return r + 1;

}

return -1;

}

// Collect nodes that are d steps from root.

void collect(TreeNode* root, int d) {

if (root == nullptr || d < 0) return;

if (d == 0) ans.push_back(root->val);

collect(root->left, d - 1);

collect(root->right, d - 1);

}

};

Posts tagged as “search”

花花酱 LeetCode 842. Split Array into Fibonacci Sequence

Problem

Solution: DFS

花花酱 LeetCode 22. Generate Parentheses

Problem

Solution: DFS

Related Problems

花花酱 LeetCode 698. Partition to K Equal Sum Subsets

Problem

Solution: Search

花花酱 LeetCode 700. Search in a Binary Search Tree

Problem

Solution: Recursion

花花酱 LeetCode 863. All Nodes Distance K in Binary Tree

Problem

Solution1: DFS + BFS

Solution 2: Recursion