欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode:996. 正方形数组的数目(图)

程序员文章站 2022-07-15 09:54:11
...

题目:

leetcode:996. 正方形数组的数目(图)

分析:

根据答案的提示,我的想法:
1.首先构造一张图,
2.深搜遍历。
如果有度数为1的点,则从度数为1的点开始遍历,没有,则随便找一个,最后的大难乘以大小。

代码:

class Solution {
public:
int all=0;
void f(set<int> s,vector<vector<int> > g,int c,vector<int> A)
{
 if(s.size()==g.size()){
  all++;
  return;
 }
 int last=-1;
 for(int i=0;i<g[c].size();i++)
 {
  if(s.count(g[c][i])==1) continue;
  if(last==A[g[c][i]]) continue;
  last=A[g[c][i]];
  set<int> ss=s;
  ss.insert(g[c][i]);
  f(ss,g,g[c][i],A);
 }
}
    int numSquarefulPerms(vector<int>& A) {
        sort(A.begin(),A.end());
            if(A.size()==1) return 0;
 vector<vector<int> > g(A.size(),vector<int>());
 //构造相连的图。 
 for(int i=0;i<A.size();i++)
 {
  for(int j=i+1;j<A.size();j++)
  {
   int c=(int)sqrt(A[i]+A[j]);
   if(c*c==A[i]+A[j]) {
    g[i].push_back(j);
    g[j].push_back(i);
   }
  }
 }
 //找开始点 
 int n=0;
 for(int i=0;i<A.size();i++)
 {
  if(g[i].size()==0) return 0;
  if(g.size()==1) n++;
 }
 if(n==1)
 {
  for(int i=0;i<A.size();i++)
  {
   if(g[i].size()==0) return 0;
   if(g.size()==1) {
    set<int> s;
   s.insert(i);
   f(s,g,i,A);
   break;
   }
  }
 }
 else if(n==2)
 {
  int b1=-1;
  for(int i=0;i<A.size();i++)
  {
   if(g[i].size()==0) return 0;
   if(g.size()==1){
    if(b1==i) break;
   }
   b1=i;
   set<int> s;
   s.insert(b1);
   f(s,g,b1,A);
  }
 }
 else if(n>2){
  return 0;
 }
 else{
  set<int> ss;
  for(int i=0;i<A.size();i++)
  {
   if(ss.count(A[i])!=0) continue;
   ss.insert(A[i]);
   set<int> s;
   s.insert(i);
   f(s,g,i,A);
  }
 }
 return all; 
    }
};

总结:1.没有入度为0的点,依次不重复遍历竟然没有超时。2.使用回溯不重复时,如果用这次的不等于上次的,前提是排序了。