pc建站网站,外发加工网有哪些,wordpress页面地图,港港网app下载最新版文章目录1. 题目2. 解题1. 题目
给定一个非负整数数组 A#xff0c;如果该数组每对相邻元素之和是一个完全平方数#xff0c;则称这一数组为正方形数组。
返回 A 的正方形排列的数目。两个排列 A1 和 A2 不同的充要条件是存在某个索引 i#xff0c;使得 A1[i] ! A2[i]。
…
文章目录1. 题目2. 解题1. 题目
给定一个非负整数数组 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 A.length 12
0 A[i] 1e9来源力扣LeetCode 链接https://leetcode-cn.com/problems/number-of-squareful-arrays 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目 LeetCode 47. 全排列 II回溯搜索剪枝 LeetCode 46. 全排列回溯
class Solution {int ans 0;
public:int numSquarefulPerms(vectorint A) {vectorbool vis(A.size(), false);sort(A.begin(), A.end());dfs(A, 0, -1, vis);return ans;}void dfs(vectorint A, int count, int prev, vectorbool vis) {if(count A.size()){ans;return;}for(int i 0; i A.size(); i){if(i 0 !vis[i-1] A[i-1]A[i])continue;// 剪枝if(!vis[i] (prev -1 || ok(prev, A[i]))){vis[i] true;dfs(A, count1, A[i], vis);vis[i] false;}}}bool ok(int a, int b){int num sqrt(ab);return num*num ab;}
};4 ms 7.8 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
