473. Matchsticks to Square

LeetCode medium original: C# #array #csharp #graph #leetcode #medium #recursion #sort

Der Aufgabentext wird für die gewählte Sprache aus dem Russischen übersetzt. Code bleibt unverändert.

LeetCode Static

given Ganzzahl Array спичек, где matchsticks[i] — это длина i-й спички. Необходимо использовать все спички для создания одного квадрата. Нельзя ломать никакую спичку, но можно соединять их, при этом каждая спичка должна быть использована ровно один раз.

Вернуть true, если можно составить квадрат, и false в противном случае.

Beispiel:

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# Lösung

zugeordnet/original

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++ Lösung

Auto-Entwurf, vor dem Einreichen prüfen

#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 Lösung

zugeordnet/original

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 Lösung

zugeordnet/original

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 Lösung

zugeordnet/original

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 Lösung

zugeordnet/original

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.

😎

Stellen zu dieser Aufgabe

aktive Stellen with overlapping task tags are angezeigt.

Alle Stellen

Es gibt noch keine aktiven Stellen.