每日一题：正方形数组的数目

赞

题目996：正方形数组的数目

给定一个非负整数数组 A，如果该数组每对相邻元素之和是一个完全平方数，则称这一数组为正方形数组。

返回 A 的正方形排列的数目。两个排列 A1 和 A2 不同的充要条件是存在某个索引 i，使得 A1[i] != A2[i]。

示例1：

输入：[1,17,8]输出：2解释：[1,8,17] 和 [17,8,1] 都是有效的排列。
示例2：
输入：[2,2,2]输出：1
提示：

  1. 1 <= A.length <= 12

  2. 0 <= A[i] <= 1e9

分析

依旧回溯算法，在全排列的基础上加一些剪枝策略，否则会超时。

  1. 首先排序，相同的数字在相邻位置

  2. 对于相邻位置相同的数字，遍历时候可以只用一次，相同的数字跳过，因为会重复

  3. 不满足"正方形数组"条件的数字跳过，不进行下一步操作

代码

class Solution {public:    int numSquarefulPerms(vector<int>& A) {        std::sort(A.begin(), A.end());        used.resize(A.size(), false);        vector<int> tem;        for (int i = 0, size = A.size(); i < size; ++i) {            tem.push_back(A[i]);            used[i] = true;            BackTrace(A, tem);            used[i] = false;            tem.pop_back();        }        return sets.size();    }
    set<vector<int>> sets;    vector<bool> used;
    void BackTrace(vector<int>& A, vector<int> &tem) {        if (tem.size() == A.size()) {            sets.emplace(tem);            return;        }        for (int i = 0, size = A.size(); i < size; ++i) {            // 过滤掉相同的数字            if (i > 0 && A[i] == A[i-1] && !used[i-1]) { continue; }            if (!tem.empty()) {                if (used[i]) { continue; }                // 不满足条件的直接跳过                if (!IsPerfectSquare(A[i] + tem.back())) { continue; }                tem.push_back(A[i]);                used[i] = true;                BackTrace(A, tem);                used[i] = false;                tem.pop_back();            }        }    }
    bool IsPerfectSquare(int num) { // 判断一个数是否是完全平方数        int sqrt_n = static_cast<int>(sqrt(num));        return pow(sqrt_n, 2) == num;    }
};