996. Number of Squareful Arrays

时间：2021-01-29 17:37:39 阅读：33 评论：0 收藏：0 [点我收藏+]

问题：

给定一组数，将其排列

使得相邻两个数的和，正好是一个可被平方的数。

求所有的排列可能个数。

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

解法：Backtracking（回溯算法）

状态：到目前为止，排列好的数列。（余下几个数left，当前选择的数x）
选择：以当前选择的数为标准，下一个能与他之和满足条件，成为平方数的，所有可能数。
- ?? 注意：若数列中存在重复的数字，那么当前为止该数字只能选择一次，作为一个排列。
递归退出条件：
- left==0，所有数用完，找到一个满足条件的解，res++，return
- 尝试完所有可能，未找到，return

对于本问题：

求排列：避免重复元素->使用set:count对不同元素，进行计数。
- 每次递归，用掉一个数，count[x]--
- 递归结束，恢复count[x]++

构造每个元素，下一个可选的所有数：使用map:opt：
- key=当前元素x，value={ 可选元素1，可选元素2...... } y
- 这些可选元素满足：sqrt(x+y)^2 = x+y

?? ?? 技巧：递归函数 debug方法：printf

定义：
- 缩紧记录变量 int countI
- printIndent(int n)函数，打印缩紧
打印位置：
- 递归入口：printIndent(n++) -> 打印参数 + "\n"
- 递归出口：printIndent(n--) -> 打印返回值 return res + "\n"
  - ?? 注意：这里，是在每一个return之前都打印

INPUT：

[1,17,8]

OUTPUT：

打印效果：STDOUT：

x:8
 x:1
  return:0
 x:17
  return:0
 return:0
x:17
 x:8
  x:1
   return 1 (res add)
  return:1
 return:1
x:1
 x:8
  x:17
   return 2 (res add)
  return:2
 return:2

代码参考：

 1 class Solution {
 2 public:
 3     // ** DEBUG method of Recursion
 4    // int countI=0;
 5    // void printIndent(int n) {
 6    //     for(int i=0;i<n;i++)
 7    //         printf(" ");
 8    // }
 9     void dfs(int& res, 
10              unordered_map<int, unordered_set<int>>& opt, unordered_map<int, int>& count, 
11              int left, int x) {
12     //    printIndent(countI++);
13     //    printf("x:%d\n", x);
14         if(left==0) {
15             res++;
16       //      printIndent(countI--);
17       //      printf("return %d (res add)\n",res);
18             return;
19         }
20         count[x]--;
21         for(int op:opt[x]) {
22             if(count[op]>0) {
23                 dfs(res, opt, count, left-1, op);
24             }
25         }
26         count[x]++;
27         //printIndent(countI--);
28         //printf("return:%d\n", res);
29         return;
30     }
31     int numSquarefulPerms(vector<int>& A) {
32         int res=0;
33         unordered_map<int, unordered_set<int>>opt;
34         unordered_map<int, int>count;
35         
36         for(int& a:A){
37             count[a]++;
38         }
39         //create opt list
40         for(auto &a:count) {
41             for(auto &b:count) {
42                 int x = a.first, y = b.first;
43                 int s = sqrt(x+y);
44                 if(s*s==x+y) {
45                     opt[x].insert(y);
46                 }
47             }
48         }
49         for(auto &a:count) {
50             dfs(res, opt, count, A.size()-1, a.first);
51         }
52         
53         return res;
54     }
55 };

996. Number of Squareful Arrays

原文：https://www.cnblogs.com/habibah-chang/p/14345671.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)