Skip to content

Latest commit

 

History

History
141 lines (86 loc) · 3.49 KB

0996._Number_of_Squareful_Arrays.md

File metadata and controls

141 lines (86 loc) · 3.49 KB

996. Number of Squareful Arrays

难度: Hard

刷题内容

原题连接

内容描述

Given an array A of non-negative integers, the array is squareful if for every pair of adjacent elements, their sum is a perfect square.

Return the number of permutations of A that are squareful.  Two permutations A1 and A2 differ if and only if there is some index i such that A1[i] != A2[i].

 

Example 1:

Input: [1,17,8]
Output: 2
Explanation: 
[1,8,17] and [17,8,1] are the valid permutations.
Example 2:

Input: [2,2,2]
Output: 1
 

Note:

1 <= A.length <= 12
0 <= A[i] <= 1e9

解题方案

思路 1 - 时间复杂度: O(2^N * N^2)- 空间复杂度: O(2^N)******

直接抄C++ fast DP solution O(2^n * n^2)

  1. We first ignore the reptition number, only consider the number of index permutation. f[S, i] represents that the number of permuatations when S contains the numbers that we've already used, and the last number is A[i]. S is a binary number where each bit indicates whether i exists or not.
  2. The initial state will be f[1 << i, i] = 1. Other states are all 0. We need to enumerate j at each time. If j is not in S, and A[i] + A[j] is a perfect square, we can do f[S | 1 << j, j] += f[S, i].
  3. The number of answer would be for i from 1 to n, ans += f[(1 << n) - 1, i].
  4. Now, we can use the knowledge of permuataion and combination to reduce the repetition answer. In genereal, we only need to count the number of each kind of number in A, and divide its factorial.
from math import factorial

class Solution:
    def numSquarefulPerms(self, A: 'List[int]') -> 'int':
        def isPerfectSquare(n):
            return int(math.sqrt(n+0.5)) ** 2 == n

        n = len(A)
        A.sort()
        s, cnt = [], 1
        for i in range(1, n):
            if A[i] != A[i-1]:
                s.append(cnt)
                cnt = 0
            cnt += 1
        s.append(cnt)
        f = [[0] * n for i in range(1 << n)]
        for i in range(n):
            f[1 << i][i] = 1
        for S in range(1, 1<<n):
            for i in range(n):
                if S & (1 << i):
                    for j in range(n):
                        if not (S & (1 << j)) and isPerfectSquare(A[i]+A[j]):
                            f[S | (1 << j)][j] += f[S][i]
        
        res = 0
        for i in range(n):
            res += f[(1 << n) - 1][i]
        for i in range(len(s)):
            res //= factorial(s[i])
        return res

思路 2 - 时间复杂度: O(2^N)- 空间复杂度: O(N)******

直接抄[C++/Python] Backtracking，dfs + backtracking

class Solution:
    def numSquarefulPerms(self, A: 'List[int]') -> 'int':
        def isPerfectSquare(n):
            return int(math.sqrt(n+0.5)) ** 2 == n
        
        count = collections.Counter(A)
        cand = {i: {j for j in count if isPerfectSquare(i+j)} for i in count}
        self.res = 0
        def dfs(x, left):
            count[x] -= 1
            if left == 0: 
                self.res += 1
            for y in cand[x]:
                if count[y]: 
                    dfs(y, left - 1)
            count[x] += 1
        for x in count:
            dfs(x, len(A)-1)
        return self.res