資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告