Tag Archives: 回溯

LeetCode Largest Divisible Subset

LeetCode Largest Divisible Subset Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0. If there are multiple solutions, return any subset is fine. Example 1:

nums: [1,2,3]
Result: [1,2] (of course, [1,3] will also be ok)
Example 2:
nums: [1,2,4,8]
Result: [1,2,4,8]

给定一个数组,求满足这样一个条件的最大子集:该子集中的任意两个元素a和b满足a%b==0或者b%a==0。通过样例能够很好的理解这个题意。 这题的解法和最长上升子序列的求法很类似,用DP求解。首先对数组从小到大排序,然后对于第i个数nums[i],定义dp[i]表示包含nums[i]、满足divisible subset条件、且nums[i]在该子集中是最大元素的子集的最大元素个数。其实就是把dp[i]直观的理解为以nums[i]结尾的满足divisible subset条件的最大子集合的大小。 求解dp[i]的递归方法是,遍历比nums[i]小的所有数nums[j],如果nums[i]%nums[j],则说明nums[i]可以扔到nums[j]所在的子集合中,所以dp[i]=dp[j]+1。遍历所有的j,找一个最大的dp[i]。 因为本题要输出具体的解,所以还定义一个数组parent[i]表示dp[i]的最大值是从哪个j来的。最后输出最优解的时候,j不断的递归往前找即可。 完整代码如下: [cpp] class Solution { public: vector<int> largestDivisibleSubset(vector<int>& nums) { if (nums.empty())return{}; sort(nums.begin(), nums.end()); int n = nums.size(), maxLen = 0, maxIdx = 0; vector<int> dp(n, 1), parent(n, -1); for (int i = 0; i < n; ++i) { for (int j = i – 1; j >= 0; –j) { if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) { dp[i] = dp[j] + 1; parent[i] = j; } } if (dp[i] > maxLen) { maxLen = dp[i]; maxIdx = i; } } vector<int> ans; while (maxIdx != -1) { ans.push_back(nums[maxIdx]); maxIdx = parent[maxIdx]; } return ans; } }; [/cpp] 本代码提交AC,用时39MS。 参考:https://www.hrwhisper.me/leetcode-largest-divisible-subset/]]>

LeetCode Beautiful Arrangement

LeetCode Beautiful Arrangement Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 ≤ i ≤ N) in this array:

  1. The number at the ith position is divisible by i.
  2. i is divisible by the number at the ith position.
Now given N, how many beautiful arrangements can you construct? Example 1:
Input: 2
Output: 2
Explanation:
The first beautiful arrangement is [1, 2]:
Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).
Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).
The second beautiful arrangement is [2, 1]:
Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).
Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.
Note:
  1. N is a positive integer and will not exceed 15.

本题要求1~N共有多少个漂亮的排列。一个漂亮的排列A[]需要满足以下两个条件中的一个:
  1. A[i]能整除i
  2. i能整除A[i]
上面的规则中下标从1开始。 本题使用DFS解决,想象数组长度为N,每个位置上都可能填入1~N这N个数。咱们从第一个位置,尝试填入1~N,然后把visited置位;第二个位置,尝试填入除第一个已经填入的其他所有数字。每个位置尝试填入时,都需要至少满足以上两个条件中的一个。当所有位置都填满时,找到一个可行解。回退时,需要把visited相关位复位。 完整代码如下: [cpp] class Solution { void dfs(int step, const int& N, vector<int>& visited, int& ans) { if (step > N) { ++ans; return; } for (int i = 1; i <= N; ++i) { if (visited[i] == 0 && (i%step == 0 || step%i == 0)) { visited[i] = 1; dfs(step + 1, N, visited, ans); visited[i] = 0; } } } public: int countArrangement(int N) { vector<int> visited(N + 1, 0); int ans = 0; dfs(1, N, visited, ans); return ans; } }; [/cpp] 本代码提交AC,用时149MS。]]>