Welcome to Subscribe On Youtube
-
/** 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++; } } } } ############ class Solution { public int countArrangement(int N) { int maxn = 1 << N; int[] f = new int[maxn]; f[0] = 1; for (int i = 0; i < maxn; ++i) { int s = 1; for (int j = 0; j < N; ++j) { s += (i >> j) & 1; } for (int j = 1; j <= N; ++j) { if (((i >> (j - 1) & 1) == 0) && (s % j == 0 || j % s == 0)) { f[i | (1 << (j - 1))] += f[i]; } } } return f[maxn - 1]; } }
-
// 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)]))
-
func countArrangement(n int) int { ans := 0 match := make(map[int][]int) for i := 1; i <= n; i++ { for j := 1; j <= n; j++ { if i%j == 0 || j%i == 0 { match[i] = append(match[i], j) } } } vis := make([]bool, n+1) var dfs func(i int) dfs = func(i int) { if i == n+1 { ans++ return } for _, j := range match[i] { if !vis[j] { vis[j] = true dfs(i + 1) vis[j] = false } } } dfs(1) return ans }
-
function countArrangement(n: number): number { const vis = new Array(n + 1).fill(0); const match = Array.from({ length: n + 1 }, () => []); for (let i = 1; i <= n; i++) { for (let j = 1; j <= n; j++) { if (i % j === 0 || j % i === 0) { match[i].push(j); } } } let res = 0; const dfs = (i: number, n: number) => { if (i === n + 1) { res++; return; } for (const j of match[i]) { if (!vis[j]) { vis[j] = true; dfs(i + 1, n); vis[j] = false; } } }; dfs(1, n); return res; }
-
impl Solution { fn dfs(i: usize, n: usize, mat: &Vec<Vec<usize>>, vis: &mut Vec<bool>, res: &mut i32) { if i == n + 1 { *res += 1; return; } for &j in mat[i].iter() { if !vis[j] { vis[j] = true; Self::dfs(i + 1, n, mat, vis, res); vis[j] = false; } } } pub fn count_arrangement(n: i32) -> i32 { let n = n as usize; let mut vis = vec![false; n + 1]; let mut mat = vec![Vec::new(); n + 1]; for i in 1..=n { for j in 1..=n { if i % j == 0 || j % i == 0 { mat[i].push(j); } } } let mut res = 0; Self::dfs(1, n, &mat, &mut vis, &mut res); res } }
-
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; } } } } } ############ class Solution { public int countArrangement(int N) { int maxn = 1 << N; int[] f = new int[maxn]; f[0] = 1; for (int i = 0; i < maxn; ++i) { int s = 1; for (int j = 0; j < N; ++j) { s += (i >> j) & 1; } for (int j = 1; j <= N; ++j) { if (((i >> (j - 1) & 1) == 0) && (s % j == 0 || j % s == 0)) { f[i | (1 << (j - 1))] += f[i]; } } } return f[maxn - 1]; } }
-
// 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)]))
-
func countArrangement(n int) int { ans := 0 match := make(map[int][]int) for i := 1; i <= n; i++ { for j := 1; j <= n; j++ { if i%j == 0 || j%i == 0 { match[i] = append(match[i], j) } } } vis := make([]bool, n+1) var dfs func(i int) dfs = func(i int) { if i == n+1 { ans++ return } for _, j := range match[i] { if !vis[j] { vis[j] = true dfs(i + 1) vis[j] = false } } } dfs(1) return ans }
-
function countArrangement(n: number): number { const vis = new Array(n + 1).fill(0); const match = Array.from({ length: n + 1 }, () => []); for (let i = 1; i <= n; i++) { for (let j = 1; j <= n; j++) { if (i % j === 0 || j % i === 0) { match[i].push(j); } } } let res = 0; const dfs = (i: number, n: number) => { if (i === n + 1) { res++; return; } for (const j of match[i]) { if (!vis[j]) { vis[j] = true; dfs(i + 1, n); vis[j] = false; } } }; dfs(1, n); return res; }
-
impl Solution { fn dfs(i: usize, n: usize, mat: &Vec<Vec<usize>>, vis: &mut Vec<bool>, res: &mut i32) { if i == n + 1 { *res += 1; return; } for &j in mat[i].iter() { if !vis[j] { vis[j] = true; Self::dfs(i + 1, n, mat, vis, res); vis[j] = false; } } } pub fn count_arrangement(n: i32) -> i32 { let n = n as usize; let mut vis = vec![false; n + 1]; let mut mat = vec![Vec::new(); n + 1]; for i in 1..=n { for j in 1..=n { if i % j == 0 || j % i == 0 { mat[i].push(j); } } } let mut res = 0; Self::dfs(1, n, &mat, &mut vis, &mut res); res } }