Welcome to Subscribe On Youtube
Java
-
/** 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: The number at the ith position is divisible by i. 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: N is a positive integer and will not exceed 15. */ public class Beautiful_Arrangement { public class Solution_trim { int count = 0; public int countArrangement(int N) { int[] nums = new int[N]; for (int i = 1; i <= N; i++) nums[i - 1] = i; permute(nums, 0); return count; } public void permute(int[] nums, int l) { if (l == nums.length) { count++; } for (int i = l; i < nums.length; i++) { swap(nums, i, l); // @note: only the current index is ok, then add it if (nums[l] % (l + 1) == 0 || (l + 1) % nums[l] == 0) { permute(nums, l + 1); } swap(nums, i, l); } } public void swap(int[] nums, int x, int y) { int temp = nums[x]; nums[x] = nums[y]; nums[y] = temp; } } public class Solution { int count = 0; public int countArrangement(int N) { if (N < 0) { return count; } int[] nums = new int[N]; for (int i = 1; i <= N; i++) { nums[i - 1] = i; } permute(nums, 0); return count; } public void permute(int[] nums, int l) { if (l == nums.length - 1) { isBeautiful(nums); } for (int i = l; i < nums.length; i++) { swap(nums, i, l); permute(nums, l + 1); swap(nums, i, l); } } public void swap(int[] nums, int x, int y) { int temp = nums[x]; nums[x] = nums[y]; nums[y] = temp; } private void isBeautiful (int[] nums) { int i; for (i = 1; i <= nums.length; i++) { if (nums[i - 1] % i != 0 && i % nums[i - 1] != 0) break; } if (i == nums.length + 1) { count++; } } } }
-
// OJ: https://leetcode.com/problems/beautiful-arrangement/ // Time: O(K) where K is the number of valid permuataions // Space: O(N) class Solution { int dfs(vector<int> &v, int start) { if (start == v.size()) return 1; int ans = 0; for (int i = start; i < v.size(); ++i) { if (v[i] % (start + 1) && (start + 1) % v[i]) continue; swap(v[i], v[start]); ans += dfs(v, start + 1); swap(v[i], v[start]); } return ans; } public: int countArrangement(int n) { vector<int> v(n); iota(begin(v), end(v), 1); return dfs(v, 0); } };
-
class Solution: def countArrangement(self, n: int) -> int: def dfs(i): nonlocal ans, n if i == n + 1: ans += 1 return for j in match[i]: if not vis[j]: vis[j] = True dfs(i + 1) vis[j] = False ans = 0 vis = [False] * (n + 1) match = defaultdict(list) for i in range(1, n + 1): for j in range(1, n + 1): if j % i == 0 or i % j == 0: match[i].append(j) dfs(1) return ans ############ class Solution(object): def countArrangement(self, N): """ :type N: int :rtype: int """ def dfs(pos, unused): if len(unused) == 0: return 1 ret = 0 for num in list(unused): if pos % num == 0 or num % pos == 0: unused -= {num} ret += dfs(pos + 1, unused) unused |= {num} return ret return dfs(1, set([i for i in range(1, N + 1)]))
Java
-
class Solution { int count = 0; public int countArrangement(int N) { if (N == 0) return 0; boolean[] used = new boolean[N + 1]; backtrack(N, 1, used); return count; } public void backtrack(int N, int position, boolean[] used) { if (position > N) count++; else { for (int i = 1; i <= N; i++) { if (!used[i] && (i % position == 0 || position % i == 0)) { used[i] = true; backtrack(N, position + 1, used); used[i] = false; } } } } }
-
// OJ: https://leetcode.com/problems/beautiful-arrangement/ // Time: O(K) where K is the number of valid permuataions // Space: O(N) class Solution { int dfs(vector<int> &v, int start) { if (start == v.size()) return 1; int ans = 0; for (int i = start; i < v.size(); ++i) { if (v[i] % (start + 1) && (start + 1) % v[i]) continue; swap(v[i], v[start]); ans += dfs(v, start + 1); swap(v[i], v[start]); } return ans; } public: int countArrangement(int n) { vector<int> v(n); iota(begin(v), end(v), 1); return dfs(v, 0); } };
-
class Solution: def countArrangement(self, n: int) -> int: def dfs(i): nonlocal ans, n if i == n + 1: ans += 1 return for j in match[i]: if not vis[j]: vis[j] = True dfs(i + 1) vis[j] = False ans = 0 vis = [False] * (n + 1) match = defaultdict(list) for i in range(1, n + 1): for j in range(1, n + 1): if j % i == 0 or i % j == 0: match[i].append(j) dfs(1) return ans ############ class Solution(object): def countArrangement(self, N): """ :type N: int :rtype: int """ def dfs(pos, unused): if len(unused) == 0: return 1 ret = 0 for num in list(unused): if pos % num == 0 or num % pos == 0: unused -= {num} ret += dfs(pos + 1, unused) unused |= {num} return ret return dfs(1, set([i for i in range(1, N + 1)]))