数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的火柴拼正方形
假设有一个小女孩，我们知道她拥有哪些火柴棒，我们需要找到一种方法，使用所有这些火柴棒拼成一个正方形。我们不能折断任何火柴棒，但可以将它们连接起来，并且每根火柴棒必须且只能使用一次。我们的输入将是女孩拥有的几根火柴棒，用它们的长度表示。我们的输出将是真或假，表示我们是否可以使用女孩拥有的所有火柴棒拼成一个正方形。所以，如果输入类似于 [1,1,2,2,2]，那么答案将是真，因为我们可以做一个边长为 2 的正方形，其中一边有两根长度为 1 的火柴棒。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个名为 solve() 的递归方法。它将接收索引、sums 数组、目标值和 nums 数组。它的工作原理如下：
- 如果索引 >= nums 的大小，则
- 当 sums[0]、sum[1] 和 sum[2] 都与目标值相同时，返回真
- 对于 i 从 0 到 3 的范围：
- 如果 sums[i] + nums[index] > 目标值，则跳过循环的下一部分
- sums[i] := sums[i] + nums[index]
- 如果 solve(index + 1, sums, target, nums) 为真，则返回真
- sums[i] := sums[i] – nums[index]
- 返回假
- 从主方法中，执行以下操作：
- 如果 nums 没有元素，则返回假
- x := 0
- 对于 i 从 0 到 nums 大小的范围，将 x 增加 nums[j]
- 如果 x 可以被 4 整除，则返回假
- 对 nums 数组进行排序
- 创建一个大小为 4 的 sums 数组
- 返回 solve(0, sum, x/4, nums)
让我们看看下面的实现，以获得更好的理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool solve(int idx, vector <int>& sums, int target, vector <int>& nums){
if(idx >= nums.size()){
return sums[0] == sums[1] && sums[1] == sums[2] && sums[2] == target;
}
for(int i = 0; i < 4; i++){
if(sums[i] + nums[idx] > target)continue;
sums[i] += nums[idx];
if(solve(idx + 1, sums, target, nums)) return true;
sums[i] -= nums[idx];
}
return false;
}
bool makesquare(vector<int>& nums) {
if(nums.size() == 0) return false;
int x = 0;
for(int i = 0; i < nums.size(); i++){
x += nums[i];
}
if(x % 4) return false;
sort(nums.rbegin(), nums.rend());
vector <int> sum(4);
return solve(0, sum,x / 4, nums);
}
};
main(){
vector<int> v = {1,1,2,2,2};
Solution ob;
cout << (ob.makesquare(v));
}输入
[1,1,2,2,2]
输出
1
更新于： 2020年5月2日
272 次查看
广告