当前位置: 首页 > news >正文

LeetCode 996.正方形数组的数目

和上一道状压的区别在于我们要去重一下~

思路都是和上一篇博客是一样的,感兴趣的同学可以看一下

const int N = 15;
int dp[1<<N][N];
int n;
vector<int>nums1;bool check(int x){int tem  = sqrt(x);if(tem*tem==x)return 1;return 0;
}int dfs(int u,int id){if(u==0)return 1;if(~dp[u][id])return dp[u][id];int res = 0;for(int i=0;i<n;i++){if(((u>>i)&1) && check(nums1[i]+nums1[id]))res = res + dfs(u&~(1<<i),i);}return dp[u][id] = res;
}class Solution {
public:int numSquarefulPerms(vector<int>& nums) {n = nums.size();nums1 = nums;memset(dp,-1,sizeof dp);int ans = 0;int u = (1<<n)-1;for(int i=0;i<n;i++)ans = ans + dfs(u&~(1<<i),i);map<int,int>mp;for(auto &t:nums)++mp[t];for(auto [_,cnt]:mp){while(cnt){ans/=cnt;cnt--;}}return ans;}
};

http://www.lryc.cn/news/215284.html

相关文章:

  • vue3写nav滚动事件中悬停在顶部
  • 关于qiling->UC_ERR_FETCH_UNMAPPED等执行EXE时内存错误的问题
  • 语言模型和人类的推理都依赖内容
  • 5.1 运输层协议概述
  • Jmeter保存csv数据文件出现乱码
  • 双闭环直流电机调速系统设计
  • [ poi-表格导出 ] java.lang.NoClassDefFoundError: org/apache/poi/POIXMLTypeLoader
  • 基于FPGA的图像差分运算及目标提取实现,包含testbench和MATLAB辅助验证程序
  • 闭环思维笔记
  • JMeter如何开展性能测试
  • 使用logback按天生成日志并按等级进行分类
  • 【Linux】Linux项目部署及更改访问端口号和jdk、tomcat、MySQL环境搭建的配置安装
  • Pytorch 注意力机制解析与代码实现
  • Python上下文管理:with语句执行原理
  • Mac-Java开发环境安装(JDK和Maven)
  • mac下的vscode配置编译环境
  • 洗衣洗鞋柜洗衣洗鞋小程序
  • vi vim 末尾编辑按GA 在最后一行下方新增一行编辑按Go
  • LeetCode热题100 240.搜索二维矩阵||
  • Anaconda安装及使用教程
  • 动态规划算法实现------转换(编辑、变换)问题
  • C#使用Oracle.ManagedDataAccess.dll
  • 分享88个工作总结PPT,总有一款适合您
  • 【华为OD题库-002】最佳植树距离-Java
  • 【python与数据结构】(leetcode算法预备知识)
  • 前端+Python实现Live2D虚拟直播姬
  • 华纳云 宝塔怎么配置香港服务器多ip?
  • 云计算是什么
  • 【POI-EXCEL-下拉框】POI导出excel下拉框数据太多导致下拉框不显示BUG修复
  • 【ES专题】ElasticSearch 高级查询语法Query DSL实战