|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
题目描述:
- 还记得童话《卖火柴的小女孩》吗?现在,你知道小女孩有多少根火柴,请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴,可以把火柴连接起来,并且每根火柴都要用到。
- 输入为小女孩拥有火柴的数目,每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。
- 示例 1:
- 输入: [1,1,2,2,2]
- 输出: true
- 解释: 能拼成一个边长为2的正方形,每边两根火柴。
- 示例 2:
- 输入: [3,3,3,3,4]
- 输出: false
- 解释: 不能用所有火柴拼成一个正方形。
- 注意:
- 给定的火柴长度和在 0 到 10^9之间。
- 火柴数组的长度不超过15。
- 来源:力扣(LeetCode)
- 链接:https://leetcode-cn.com/problems/matchsticks-to-square
- 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码
- class Solution {
- public:
-
- vector<bool>st;
- bool makesquare(vector<int>& nums) {
- int sum = 0;
- for(auto u : nums) sum += u;
- if(sum % 4 != 0) return false;
- sort(nums.rbegin(),nums.rend());
- st = vector<bool>(nums.size());
- return dfs(nums,0,0,sum / 4);
- }
- bool dfs(vector<int>&nums,int u , int cur, int length)
- {
- if(cur == length) u++, cur = 0;
- if(u == 4)return true;
- for(int i = 0; i < nums.size(); i++)
- {
- if(!st[i] && cur + nums[i] <= length)
- {
- st[i] = true;
- if(dfs(nums,u , cur + nums[i], length))return true;
- st[i] = false;
- if(cur == 0)return false;//如果cur = 0 ,第一个失败了,直接剪掉
- if(cur + nums[i] == length) return false;//虽然等于length但是没有达到u==4或没有用完全部数据
- while(i + 1 < nums.size() && nums[i + 1] == nums[i]) i++;//当前失败,跳过相同大小木棒
- }
- }
- return false;
- }
- };
复制代码
参考链接:https://leetcode-cn.com/problems ... n-by-cuiwanxin1998/ |
|