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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Author: Huahua
// Running time: 4 ms (<99.21%)
classSolution{
public:
boolcanPartitionKSubsets(vector<int>& nums, int k) {
const int sum = accumulate(nums.begin(), nums.end(), 0);
if(sum%k!=0)returnfalse;
sort(nums.rbegin(),nums.rend());
returndfs(nums,sum/k,0,k,0);
}
private:
booldfs(constvector<int>& nums, int target, int cur, int k, int used) {
if (k == 0) return used == (1 << nums.size()) - 1;
for(inti=0;i<nums.size();++i){
if(used& (1 << i)) continue;
intt=cur+nums[i];
if(t>target)break;// Important
intnew_used=used|(1<<i);
if(t==target&& dfs(nums, target, 0, k - 1, new_used)) return true;
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.
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 = 2Output: [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.
Your car starts at position 0 and speed +1 on an infinite number line. (Your car can go into negative positions.)
Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).
When you get an instruction “A”, your car does the following: position += speed, speed *= 2.
When you get an instruction “R”, your car does the following: if your speed is positive then speed = -1 , otherwise speed = 1. (Your position stays the same.)
For example, after commands “AAR”, your car goes to positions 0->1->3->3, and your speed goes to 1->2->4->-1.
Now for some target position, say the length of the shortest sequence of instructions to get there.
Example 1:Input:
target = 3
Output: 2
Explanation:
The shortest instruction sequence is "AA".
Your position goes from 0->1->3.
Example 2:Input:
target = 6
Output: 5
Explanation:
The shortest instruction sequence is "AAARA".
Your position goes from 0->1->3->7->7->6.
Note:
1 <= target <= 10000.
Visualization of the Solution
Solution 1: BFS
C++/Str
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// Author: Huahua
// Running time: 221 ms
classSolution{
public:
intracecar(inttarget){
queue<pair<int,int>>q;
q.push({0,1});
unordered_set<string>v;
v.insert("0_1");
v.insert("0_-1");
intsteps=0;
while(!q.empty()){
intsize=q.size();
while(size--){
autop=q.front();q.pop();
intpos=p.first;
intspeed=p.second;
{
intpos1=pos+speed;
intspeed1=speed*2;
pair<int,int>p1{pos1,speed1};
if(pos1==target)returnsteps+1;
if(p1.first>0&& p1.first < 2 * target)
q.push(p1);
}
{
intspeed2=speed>0?-1:1;
pair<int,int>p2{pos,speed2};
stringkey2=to_string(pos)+"_"+to_string(speed2);
if(!v.count(key2)){
q.push(p2);
v.insert(key2);
}
}
}
++steps;
}
return-1;
}
};
C++/Int
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Author: Huahua
// Running time: 16 ms
classSolution{
public:
intracecar(inttarget){
queue<pair<int,int>>q;
q.push({0,1});
unordered_set<int>v;
v.insert({0,2});
intsteps=0;
while(!q.empty()){
intsize=q.size();
while(size--){
autop=q.front();q.pop();
intpos=p.first;
intspeed=p.second;
pair<int,int>p1={pos+speed,speed*2};
if(p1.first==target)returnsteps+1;
if(p1.first>0&& p1.first + speed < 2 * target)
q.push(p1);
intspeed2=speed>0?-1:1;
pair<int,int>p2={pos,speed2};
intkey=(pos<<2)|(speed2+1);
if(!v.count(key)&& p2.first >= target / 2) {
q.push(p2);
v.insert(key);
}
}
++steps;
}
return-1;
}
};
Solution 2: DP O(TlogT)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// Author: Huahua
// Running time: 4 ms
classSolution{
public:
intracecar(inttarget){
m_=vector<int>(target+1,0);
returndp(target);
}
private:
vector<int>m_;
intdp(intt){
if(m_[t]>0)returnm_[t];
intn=ceil(log2(t+1));
// AA...A (nA) best case
if(1<<n==t+1)returnm_[t]=n;
// AA...AR (nA + 1R) + dp(left)
m_[t]=n+1+dp((1<<n)-1-t);
for(intm=0;m<n-1;++m){
intcur=(1<<(n-1))-(1<<m);
//AA...ARA...AR (n-1A + 1R + mA + 1R) + dp(left)
m_[t]=min(m_[t],n+m+1+dp(t-cur));
}
returnm_[t];
}
};
Solution 3: DP O(T^2)
m[t][d] : min steps to reach t and facing d (0 = right, 1 = left)