Golang | LeetCode

#medium
Задача: 473. Matchsticks to Square

Дано целочисленный массив спичек, где 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.

👨‍💻

Алгоритм:

1⃣Определяем рекурсивную функцию, которая принимает текущий индекс обрабатываемой спички и количество сторон квадрата, которые уже полностью сформированы. Базовый случай для рекурсии: если все спички использованы и сформировано 4 стороны, возвращаем True.

2⃣Для текущей спички рассматриваем 4 варианта: она может быть частью любой из сторон квадрата. Пробуем каждый из 4 вариантов, вызывая рекурсию для них.

3⃣Если какой-либо из рекурсивных вызовов возвращает True, возвращаем True, в противном случае возвращаем False.

😎

Решение:

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() {}

Ставь 👍 и забирай 📚 Базу знаний

Please open Telegram to view this post