当前位置: 代码迷 >> 综合 >> leetcode 996. Number of Squareful Arrays
  详细解决方案

leetcode 996. Number of Squareful Arrays

热度:12   发布时间:2024-01-16 17:58:20.0

leetcode 996. Number of Squareful Arrays

题意:给你一个数组,将数组里的数字顺序互换,求满足条件不同数组的个数。条件是,相邻数的和是完全平方数。

思路:写个DFS,模拟全排列的过程。

但是对于数据{2,2,2,2,2,2,2,2,2,2,2,2},全部搜一遍肯定超时,需要剪枝。

这里考虑用set储存已经搜索过的数组,相同的数组肯定不继续搜索,直接return。

class Solution {
public:int numSquarefulPerms(vector<int>& A) {vector<int> vis(A.size(), 0);vector<int> B;dfs(0, 0, vis, A, B);return ans;}void dfs(int pos, int last, vector<int> vis, vector<int>& A, vector<int> B){if (path.find(B) == path.end())path.insert(B);elsereturn;if (pos == A.size()){ans++;return;}for (int i = 0; i < A.size(); i++){if (vis[i] == 0){if (last == 0 || judge(last,A[i])){vis[i] = 1;B.push_back(A[i]);dfs(pos + 1, A[i], vis, A, B);B.pop_back();vis[i] = 0;}}}}bool judge(long a, long b){long num = sqrtl(a + b);return num * num == a + b;}private:set<vector<int>> path;int ans;
};

 

 

  相关解决方案