C++ 中火柴到正方形的转化
c++server side programmingprogramming
假设有一个卖火柴的小女孩。我们知道她确切有多少根火柴，我们需要找到一种方法，用完所有火柴，拼成一个正方形。我们不能折断任何一根火柴，但可以把它们连起来，每根火柴只能使用一次。我们的输入是小女孩拥有的几根火柴，用它们的长度表示。输出为 true 或 false，表示我们能否用她所有的火柴拼成一个正方形。所以，如果输入是 [1,1,2,2,2]，那么答案就是 true，因为我们可以拼成一个长度为 2 的正方形，一边有两根长度为 1 的火柴。
为了解决这个问题，我们将遵循以下步骤 −
- 定义一个名为solve()的递归方法。该方法需要 index、sums 数组、target 和 nums 数组作为参数。因此，这将按如下方式运行 −
- 如果 index >= nums 大小，则
- 当 sums[0]、sum[1] 和 sum[2] 均与目标值相同时返回 true
- 对于 i，范围为 0 到 3 −
- 如果 sums[i] + nums[index] > target，则跳过循环的下一部分
- sums[i] := sums[i] + nums[index]
- 如果solve(index + 1, sums, target, nums)为 true，则返回 true
- sums[i] := sums[i] – nums[index]
- 返回 false
- 在 main 方法中，执行以下操作 −
- 如果 nums 没有元素，则返回 false
- x := 0
- 对于介于 0 到 nums 大小之间的 i，将 x 增加 nums[j]
- 如果 x 能被 4 整除，则返回 false
- 对 nums 数组进行排序
- 创建一个大小为 4 的数组 sums
- 返回 resolve(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
