This is the 16th day of my participation in the August More Text Challenge. For details, see: August More Text Challenge

Leetcode -526- Elegant arrangement

[Blog link]

The way to study 🐔

The nuggets home page

[Topic description]

Suppose we have N integers from 1 to N, and if we successfully construct an array from these N numbers such that the ith bit of the array (1 <= I <= N) satisfies one of the following two conditions, the array is said to be beautifully arranged. Condition:

The i-th digit is divisible by I and I is divisible by the i-th digit

Now, given an integer N, how many graceful permutations can be constructed?

Example 1: Input: 2 Output: 2 Explanation: The first elegant arrangement is [1, 2]: The number in the first position (I =1) is 1, 1 is divisible by I (I =1), and the number in the second position (I =2) is 2, 2 is divisible by I (I =2), and the second neat arrangement is [2, 1]: The number in the first position (I =1) is 2, 2 is divisible by I (I =1), and the number in the second position (I =2) is 1, and I (I =2) is divisible by 1Copy the code

Description:

N is a positive integer and does not exceed 15.

Related Topics

• An operation
• An array of
• Dynamic programming
• back
• State of compression
• 👍 👎 0 174

[Topic link]

Leetcode title link

[making address]

Code link

[思路介绍]

Idea 1: Source analysis of violent DFS + DP equation

• Define elements that satisfy the conditions to be placed at position I
• Define a match array to simplify the search for elements to put in
• The DFS breakout recursion condition is that all elements have been placed
• k % i == 0 ||i % k == 0

class Solution{
int res = 0;
        List<Integer>[] match;

        public int countArrangement(int n) {
            match = new List[n + 1];
            for (int i = 1; i <= n; i++) {
                int idx = 1;
                match[i] = new ArrayList<>();
                while (idx <= n) {
                    if (idx % i == 0 || i % idx == 0) { match[i].add(idx); } idx++; }}boolean[] vis = new boolean[n + 1];
            dfs(1, n, vis);
            return res;
        }

        public void dfs(int index, int n, boolean[] vis) {
            if (index == n + 1) {
                res += 1;
                return;
            }
            for (int num : match[index]
            ) {
               if(! vis[num]){ vis[num] =true;
                   dfs(index + 1, n, vis);
                   vis[num] = false; }}}}Copy the code

• Time complexity O(
  $n!$)
• Space complexity O(
  $n^{2}$)

Idea 2: Dynamic programming

• According to the first idea, it is not difficult to find that the DFS recursive equation has three variables
• We can see that we can define a two dimensional DP equation (the above recursive idea n is fixed can not be put in the recursive equation, so define a two dimensional DP equation)
• f[i][j]
• The next thing to think about is how do I define a VIS array as one of these dimensions
• A maximum of 15 can be found according to the topic input limit
• All elements must be entered
• So we can define a binary number. A total of 15
• If the corresponding digit is 1, the element is already in use
• Therefore, the definition of f[I][j] is clear, indicating the number of schemes in state J used by all letters when I elements are used
• J is the number and state of elements used in binary representation
• Initialization f[0][0] is fixed to 1, indicating that 0 elements are used. There is one scheme in which each element is not used
• 
  $f[i][j] = \sum_{k=1}^{n}f[n-1][state\land(\lnot(1 << (k-1))]$

public int countArrangement(int n) {
            int mask = 1 << n;
            int[][] dp = new int[n + 1][mask];
            dp[0] [0] = 1;
            for (int i = 1; i <= n; i++) {
                for (int state = 0; state < mask; state++) {
                    for (int k = 1; k <= n; k++) {
                        if ((state >> (k - 1) & 1) = =0) {
                            continue;
                        }
                        if(k % i ! =0&& i % k ! =0) {
                            continue;
                        }
                        dp[i][state] += dp[i - 1][state & ~(1 << (k - 1))]; }}}return dp[n][mask - 1];
        }
Copy the code

• Time complexity
  $O(n * 2^{n})$
• Spatial complexity
  $O(n * 2^{n})$

Idea 3: Compression optimization

• This is true is not expected
• Three leaf big guy YYds
• Define f[state] to indicate the number of all schemes when the current value is state
• Initialize the f [0] = 1
• F [state] + = f [state Sunday afternoon (rope (1 < < I))] [state] + f = f (\ [state \ land lnot < < I) (1)] f [state] + = f [state Sunday afternoon (rope (1 < < I))];

public int countArrangement(int n) { int mask = 1 << n; int[] f = new int[mask]; f[0] = 1; For (int state = 1; state < mask; State ++) {// calculate the number of 1's in state (that is, the current sort length) int CNT = integ.bitcount (state); For (int I = 0; i < n; If (((state >> I) &1) == 0) continue; If ((I + 1) % CNT! = 0 && cnt % (i + 1) ! = 0) continue; / / state & (~ 1 < < (I)) on behalf of the state in the location of the selected numerical zero f [state] + = f [state & (~ 1 < < (I))]; } } return f[mask - 1]; }Copy the code

• Time complexity
  $O(n * 2^{n})$
• Spatial complexity
  $O(2^{n})$