[LeetCode] 996. Number of Squareful Arrays

[grandyang]

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. 1 <= A.length <= 12
2. 0 <= A[i] <= 1e9

这道题给了一个非负整数组成的数组A，定义了一种平方数组，即任意两个相邻的数字之和是个完全平方数，现在让找出有多少个A的全排列数组是个平方数组。其实这道题有两个难点，一个是如何求全排列，另一个是如何在生成全排列的过程中验证平方数组。LeetCode 有好几道关于全排列的题，比较基本的就是这两道 Permutations 和 Permutations II，很明显这道题中的数字是有可能重复的，所以跟后者更接近。其实这道题的解法就是基于 Permutations II 来做的，只不过在过程中加入了判断平方数组的步骤。关于求有重复数字的全排列的讲解可以参见上面的帖子，这里就简略的讲讲，首先要给原数组排序，使得重复的数字相邻，便于跳过。在递归数组中，记得要跳过重复数字，然后要判断是否是平方数组，若 out 不为空，则把前一个数字和当前数字相加，求 Double 型的平方根，这里用了一个小 trick，对该平方根求 floor，若跟原平方根相同，则说明数字和是个完全平方数，因为若不是完全平方数的话，平方根会有小数部分，向下取整的话必定和之前不同了。后面就是经典的递归部分了，注意之后需要还原状态，参见代码如下：

解法一：

class Solution {
public:
    int numSquarefulPerms(vector<int>& A) {
        int res = 0;
        vector<int> visited(A.size()), out;
        sort(A.begin(), A.end());
        helper(A, 0, visited, out, res);
        return res;
    }
    void helper(vector<int>& A, int level, vector<int>& visited, vector<int>& out, int& res) {
        if (level >= A.size()) {
            ++res;
            return;
        }
        for (int i = 0; i < A.size(); ++i) {
            if (visited[i] == 1) continue;
            if (i > 0 && A[i] == A[i - 1] && visited[i - 1] == 0) continue;
            if (!out.empty()) {
                double root = sqrt(A[i] + out.back());
                if (root - floor(root) != 0) continue;
            }
            visited[i] = 1;
            out.push_back(A[i]);
            helper(A, level + 1, visited, out, res);
            visited[i] = 0;
            out.pop_back();
        }
    }
};

求全排列还有一种不停的交换两个数字位置的解法，同样，具体讲解可以参见这个帖子 Permutations II。这里用了一个 start 变量，注意和上面的 level 变量区别开来，上面的解法由于是在拼全排列，i每次要从0开始遍历，而这里交换的话，i每次从 start 开始遍历。在去除重复情况后，交换 A[i] 和 A[start]，然后还是要判断平方数组，不过这里用了跟上面不同的验证方法，这里对数字求平方根后去整型值，就会自动舍去小数部分，然后再平方，若跟原数相同，则说明是完全平方数，参见代码如下：

解法二：

class Solution {
public:
    int numSquarefulPerms(vector<int>& A) {
        int res = 0;
        sort(A.begin(), A.end());
        helper(A, 0, res);
        return res;
    }
    void helper(vector<int> A, int start, int& res) {
        if (start >= A.size()) ++res;
        for (int i = start; i < A.size(); ++i) {
            if (i > start && A[i] == A[start]) continue;
            swap(A[i], A[start]);
            if (start == 0 || (start > 0 && isSquare(A[start] + A[start - 1]))) {
                helper(A, start + 1, res);
            }
        }
    }
    bool isSquare(int num) {
        int r = sqrt(num);
        return r * r == num;
    }
};

下面这种解法是论坛上的高分解法，感觉也很巧妙。使用了两个 HashMap，一个用来建立每个数字和其出现次数之间的映射，另一个是建立数字和数组中能跟其能组成完全平方数的所有数字的集合之间映射。首先遍历原数组A，找出每个数字出现的次数，然后遍历这个 numCnt，两个 for 循环，每次取两个数字，验证其和是否是完全平方数，是的话就加入第二个 HashMap 中。之后就要开始构建全排列了，也是遍历 numCnt，对每个数字调用递归函数，这里用个 left 表示还需要的数字的个数。在递归函数中，若 left 等于0了，说明已经凑够全排列数字的个数，结果 res 自增1，并返回。否则当前数字的映射值自减1，然后遍历其在 numMap 中可以组成完全平方数的所有数字，若该数字的映射值大于0，对其调用递归，for 循环结束后记得恢复状态，参见代码如下：

解法三：

class Solution {
public:
    int numSquarefulPerms(vector<int>& A) {
        unordered_map<int, int> numCnt;
        unordered_map<int, unordered_set<int>> numMap;
        int res = 0, n = A.size();
        for (int num : A) ++numCnt[num];
        for (auto &a : numCnt) {
            for (auto &b : numCnt) {
                int x = a.first, y = b.first, r = sqrt(x + y);
                if (r * r == x + y) numMap[x].insert(y);
            }
        }
        for (auto &a : numCnt) {
            helper(a.first, n - 1, numCnt, numMap, res);
        }
        return res;
    }
    void helper(int x, int left, unordered_map<int, int>& numCnt, unordered_map<int, unordered_set<int>>& numMap, int& res) {
        if (left == 0) {
            ++res;
            return;
        }
        --numCnt[x];
        for (int y : numMap[x]) {
            if (numCnt[y] > 0 ) {
                helper(y, left - 1, numCnt, numMap, res);
            }
        }
        ++numCnt[x];
    }
};

Github 同步地址:

#996

类似题目：

Permutations

Permutations II

参考资料：

https://leetcode.com/problems/number-of-squareful-arrays/

https://leetcode.com/problems/number-of-squareful-arrays/discuss/238593/Java-DFS-%2B-Unique-Perms

https://leetcode.com/problems/number-of-squareful-arrays/discuss/238562/C%2B%2BPython-Backtracking

https://leetcode.com/problems/number-of-squareful-arrays/discuss/238612/4msC%2B%2B-Simple-Backtracking-like-Permutations-II

LeetCode All in One 题目讲解汇总(持续更新中...)