Computer >> Máy Tính >  >> Lập trình >> C ++

Que diêm thành hình vuông trong C ++

Giả sử có một cô bé bán diêm. Và chúng tôi biết chính xác cô bé bán diêm có que diêm nào, chúng tôi phải tìm ra cách có thể tạo ra một hình vuông bằng cách sử dụng hết những que diêm đó. Chúng ta không nên bẻ bất kỳ que nào, nhưng chúng ta có thể liên kết chúng lại và mỗi que diêm phải được sử dụng đúng một lần. Đầu vào của chúng tôi sẽ là một số que diêm mà cô gái có, được thể hiện bằng chiều dài que của họ. đầu ra của chúng ta sẽ là true hoặc false, để thể hiện liệu chúng ta có thể tạo ra một hình vuông bằng cách sử dụng tất cả các que diêm mà cô gái bán diêm có hay không. Vì vậy, nếu đầu vào là [1,1,2,2,2], thì câu trả lời sẽ là đúng, vì chúng ta có thể tạo một hình vuông có độ dài 2, một cạnh sẽ có hai que tính có độ dài 1.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Định nghĩa một phương thức đệ quy được gọi là giải quyết (). Điều này sẽ lấy chỉ số, mảng tổng, đích và mảng nums. Vì vậy, điều này sẽ hoạt động như sau -
  • if index> =nums size, then
    • trả về true khi các tổng [0], sum [1] và sum [2] đều giống như targer
  • cho tôi trong phạm vi từ 0 đến 3 -
    • nếu tổng [i] + nums [index]> target, thì bỏ qua phần tiếp theo của vòng lặp
    • sums [i]:=sums [i] + nums [index]
    • nếu giải quyết (chỉ mục + 1, tổng, mục tiêu, nums) là true, thì trả về true
    • sums [i]:=sums [i] - nums [index]
  • trả về false
  • Từ phương pháp chính, hãy thực hiện như sau -
  • nếu nums không có phần tử nào, thì trả về false
  • x:=0
  • đối với tôi trong phạm vi 0 đến kích thước là nums, hãy tăng x lên nums [j]
  • nếu x chia hết cho 4 thì trả về false
  • sắp xếp mảng nums
  • tạo tổng mảng có kích thước 4
  • trả về giải quyết (0, sum, x / 4, nums)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ 

#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));
}

Đầu vào 

[1,1,2,2,2]

Đầu ra 

1