473. Matchsticks to Square
선택한 UI 언어에 맞게 문제 텍스트를 러시아어에서 번역합니다. 코드는 변경하지 않습니다.
given 정수 배열 спичек, где matchsticks[i] — это длина i-й спички. Необходимо использовать все спички для создания одного квадрата. Нельзя ломать никакую спичку, но можно соединять их, при этом каждая спичка должна быть использована ровно один раз.
Вернуть true, если можно составить квадрат, и false в противном случае.
예제:
Input: matchsticks = [1,1,2,2,2]
Output: true
Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.
C# 해법
매칭됨/원본using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
private IList<int> nums;
private int[] sums;
private int possibleSquareSide;
public Solution() {
this.sums = new int[4];
}
private bool Dfs(int index) {
if (index == this.nums.Count) {
return sums[0] == sums[1] && sums[1] == sums[2] && sums[2] == sums[3];
}
int element = this.nums[index];
for (int i = 0; i < 4; i++) {
if (this.sums[i] + element <= this.possibleSquareSide) {
this.sums[i] += element;
if (this.Dfs(index + 1)) {
return true;
}
this.sums[i] -= element;
}
}
return false;
}
public bool Makesquare(int[] nums) {
if (nums == null || nums.Length == 0) {
return false;
}
int perimeter = nums.Sum();
this.possibleSquareSide = perimeter / 4;
if (this.possibleSquareSide * 4 != perimeter) {
return false;
}
this.nums = nums.OrderByDescending(x => x).ToList();
return this.Dfs(0);
}
}C++ 해법
자동 초안, 제출 전 검토#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
private vector<int> nums;
private vector<int>& sums;
private int possibleSquareSide;
public Solution() {
this.sums = new int[4];
}
private bool Dfs(int index) {
if (index == this.nums.size()) {
return sums[0] == sums[1] && sums[1] == sums[2] && sums[2] == sums[3];
}
int element = this.nums[index];
for (int i = 0; i < 4; i++) {
if (this.sums[i] + element <= this.possibleSquareSide) {
this.sums[i] += element;
if (this.Dfs(index + 1)) {
return true;
}
this.sums[i] -= element;
}
}
return false;
}
public bool Makesquare(vector<int>& nums) {
if (nums == null || nums.size() == 0) {
return false;
}
int perimeter = nums.Sum();
this.possibleSquareSide = perimeter / 4;
if (this.possibleSquareSide * 4 != perimeter) {
return false;
}
this.nums = nums.OrderByDescending(x => x).ToList();
return this.Dfs(0);
}
}Java 해법
매칭됨/원본import java.util.HashMap;
import java.util.Collections;
class Solution {
public List<Integer> nums;
public int[] sums;
public int possibleSquareSide;
public Solution() {
this.sums = new int[4];
}
public boolean dfs(int index) {
if (index == this.nums.size()) {
return sums[0] == sums[1] && sums[1] == sums[2] && sums[2] == sums[3];
}
int element = this.nums.get(index);
for(int i = 0; i < 4; i++) {
if (this.sums[i] + element <= this.possibleSquareSide) {
this.sums[i] += element;
if (this.dfs(index + 1)) {
return true;
}
this.sums[i] -= element;
}
}
return false;
}
public boolean makesquare(int[] nums) {
if (nums == null || nums.length == 0) {
return false;
}
int L = nums.length;
int perimeter = 0;
for(int i = 0; i < L; i++) {
perimeter += nums[i];
}
this.possibleSquareSide = perimeter / 4;
if (this.possibleSquareSide * 4 != perimeter) {
return false;
}
this.nums = Arrays.stream(nums).boxed().collect(Collectors.toList());
Collections.sort(this.nums, Collections.reverseOrder());
return this.dfs(0);
}
}JavaScript 해법
매칭됨/원본class Solution {
constructor() {
this.sums = new Array(4).fill(0);
this.possibleSquareSide = 0;
}
dfs(index) {
if (index === this.nums.length) {
return this.sums[0] === this.sums[1] && this.sums[1] === this.sums[2] && this.sums[2] === this.sums[3];
}
const element = this.nums[index];
for (let i = 0; i < 4; i++) {
if (this.sums[i] + element <= this.possibleSquareSide) {
this.sums[i] += element;
if (this.dfs(index + 1)) {
return true;
}
this.sums[i] -= element;
}
}
return false;
}
makesquare(nums) {
if (!nums || nums.length === 0) {
return false;
}
const perimeter = nums.reduce((acc, val) => acc + val, 0);
this.possibleSquareSide = Math.floor(perimeter / 4);
if (this.possibleSquareSide * 4 !== perimeter) {
return false;
}
this.nums = nums.sort((a, b) => b - a);
return this.dfs(0);
}
}Python 해법
매칭됨/원본class Solution:
def __init__(self):
self.sums = [0] * 4
self.possibleSquareSide = 0
def dfs(self, index):
if index == len(self.nums):
return self.sums[0] == self.sums[1] == self.sums[2] == self.sums[3]
element = self.nums[index]
for i in range(4):
if self.sums[i] + element <= self.possibleSquareSide:
self.sums[i] += element
if self.dfs(index + 1):
return True
self.sums[i] -= element
return False
def makesquare(self, nums):
if not nums:
return False
perimeter = sum(nums)
self.possibleSquareSide = perimeter // 4
if self.possibleSquareSide * 4 != perimeter:
return False
self.nums = sorted(nums, reverse=True)
return self.dfs(0)Go 해법
매칭됨/원본package main
import (
"sort"
)
type Solution struct {
nums []int
sums []int
possibleSquareSide int
}
func Constructor() Solution {
return Solution{sums: make([]int, 4)}
}
func (this *Solution) dfs(index int) bool {
if index == len(this.nums) {
return this.sums[0] == this.sums[1] && this.sums[1] == this.sums[2] && this.sums[2] == this.sums[3]
}
element := this.nums[index]
for i := 0; i < 4; i++ {
if this.sums[i]+element <= this.possibleSquareSide {
this.sums[i] += element
if this.dfs(index + 1) {
return true
}
this.sums[i] -= element
}
}
return false
}
func (this *Solution) makesquare(nums []int) bool {
if len(nums) == 0 {
return false
}
perimeter := 0
for _, num := range nums {
perimeter += num
}
this.possibleSquareSide = perimeter / 4
if this.possibleSquareSide*4 != perimeter {
return false
}
this.nums = nums
sort.Sort(sort.Reverse(sort.IntSlice(this.nums)))
return this.dfs(0)
}
func main() {}Algorithm
Определяем рекурсивную функцию, которая принимает текущий индекс обрабатываемой спички и количество сторон квадрата, которые уже полностью сформированы. Базовый случай для рекурсии: если все спички использованы и сформировано 4 стороны, возвращаем True.
Для текущей спички рассматриваем 4 варианта: она может быть частью любой из сторон квадрата. Пробуем каждый из 4 вариантов, вызывая рекурсию для них.
Если какой-либо из рекурсивных вызовов returns True, возвращаем True, в противном случае возвращаем False.
😎
Vacancies for this task
활성 채용 with overlapping task tags are 표시됨.
아직 활성 채용이 없습니다.