← Static tasks

679. 24 Game

leetcode hard

#array#csharp#hard#leetcode#math#recursion

Task

Дан массив целых чисел cards длиной 4. У вас есть четыре карты, каждая из которых содержит число в диапазоне от 1 до 9. Вам нужно расположить числа на этих картах в математическом выражении, используя операторы ['+', '-', '*', '/'] и скобки '(' и ')' так, чтобы получить значение 24.

Вы ограничены следующими правилами:

Оператор деления '/' представляет собой реальное деление, а не целочисленное деление.

Например, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.

Каждая операция выполняется между двумя числами. В частности, мы не можем использовать '-' как унарный оператор.

Например, если cards = [1, 1, 1, 1], выражение "-1 - 1 - 1 - 1" не допускается.

Вы не можете объединять числа вместе.

Например, если cards = [1, 2, 1, 2], выражение "12 + 12" недопустимо.

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

Пример:

Input: cards = [4,1,8,7]

Output: true

Explanation: (8-4) * (7-1) = 24

C# solution

matched/original
using System;
using System.Collections.Generic;
public class Solution {
    public List<double> GeneratePossibleResults(double a, double b) {
        var res = new List<double> { a + b, a - b, b - a, a * b };
        if (a != 0) res.Add(b / a);
        if (b != 0) res.Add(a / b);
        return res;
    }
    public bool CheckIfResultReached(List<double> list) {
        if (list.Count == 1) return Math.Abs(list[0] - 24) <= 0.1;
        for (int i = 0; i < list.Count; i++) {
            for (int j = i + 1; j < list.Count; j++) {
                var newList = new List<double>();
                for (int k = 0; k < list.Count; k++) {
                    if (k != i && k != j) newList.Add(list[k]);
                }
                foreach (double res in GeneratePossibleResults(list[i], list[j])) {
                    newList.Add(res);
                    if (CheckIfResultReached(newList)) return true;
                    newList.RemoveAt(newList.Count - 1);
                }
            }
        }
        return false;
    }
    public bool JudgePoint24(int[] cards) {
        var list = new List<double>();
        foreach (int card in cards) list.Add(card);
        return CheckIfResultReached(list);
    }
}

C++ solution

auto-draft, review before submit
#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:
    public List<double> GeneratePossibleResults(double a, double b) {
        var res = new List<double> { a + b, a - b, b - a, a * b };
        if (a != 0) res.push_back(b / a);
        if (b != 0) res.push_back(a / b);
        return res;
    }
    public bool CheckIfResultReached(List<double> list) {
        if (list.size() == 1) return abs(list[0] - 24) <= 0.1;
        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                var newList = new List<double>();
                for (int k = 0; k < list.size(); k++) {
                    if (k != i && k != j) newList.push_back(list[k]);
                }
                foreach (double res in GeneratePossibleResults(list[i], list[j])) {
                    newList.push_back(res);
                    if (CheckIfResultReached(newList)) return true;
                    newList.RemoveAt(newList.size() - 1);
                }
            }
        }
        return false;
    }
    public bool JudgePoint24(vector<int>& cards) {
        var list = new List<double>();
        foreach (int card in cards) list.push_back(card);
        return CheckIfResultReached(list);
    }
}

Java solution

matched/original
import java.util.*;

class Solution {
    public List<Double> generatePossibleResults(double a, double b) {
        List<Double> res = new ArrayList<>(Arrays.asList(a + b, a - b, b - a, a * b));
        if (a != 0) res.add(b / a);
        if (b != 0) res.add(a / b);
        return res;
    }

    public boolean checkIfResultReached(List<Double> list) {
        if (list.size() == 1) return Math.abs(list.get(0) - 24) <= 0.1;

        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                List<Double> newList = new ArrayList<>();
                for (int k = 0; k < list.size(); k++) {
                    if (k != i && k != j) newList.add(list.get(k));
                }
                for (double res : generatePossibleResults(list.get(i), list.get(j))) {
                    newList.add(res);
                    if (checkIfResultReached(newList)) return true;
                    newList.remove(newList.size() - 1);
                }
            }
        }
        return false;
    }

    public boolean judgePoint24(int[] cards) {
        List<Double> list = new ArrayList<>();
        for (int card : cards) {
            list.add((double) card);
        }
        return checkIfResultReached(list);
    }
}

JavaScript solution

matched/original
class Solution {
    generatePossibleResults(a, b) {
        const res = [a + b, a - b, b - a, a * b];
        if (a !== 0) res.push(b / a);
        if (b !== 0) res.push(a / b);
        return res;
    }

    checkIfResultReached(list) {
        if (list.length === 1) {
            return Math.abs(list[0] - 24) <= 0.1;
        }

        for (let i = 0; i < list.length; i++) {
            for (let j = i + 1; j < list.length; j++) {
                const newList = [];
                for (let k = 0; k < list.length; k++) {
                    if (k !== i && k !== j) newList.push(list[k]);
                }
                for (const res of this.generatePossibleResults(list[i], list[j])) {
                    newList.push(res);
                    if (this.checkIfResultReached(newList)) return true;
                    newList.pop();
                }
            }
        }
        return false;
    }

    judgePoint24(cards) {
        return this.checkIfResultReached(cards.map(card => card));
    }
}

Python solution

matched/original
class Solution:
    def generatePossibleResults(self, a, b):
        res = [a + b, a - b, b - a, a * b]
        if a != 0:
            res.append(b / a)
        if b != 0:
            res.append(a / b)
        return res

    def checkIfResultReached(self, list):
        if len(list) == 1:
            return abs(list[0] - 24) <= 0.1

        for i in range(len(list)):
            for j in range(i + 1, len(list)):
                new_list = [list[k] for k in range(len(list)) if k != i and k != j]
                for res in self.generatePossibleResults(list[i], list[j]):
                    new_list.append(res)
                    if self.checkIfResultReached(new_list):
                        return True
                    new_list.pop()
        return False

    def judgePoint24(self, cards):
        return self.checkIfResultReached(list(map(float, cards)))

Go solution

matched/original
package main

import (
  "math"
)

type Solution struct{}

func (s *Solution) generatePossibleResults(a, b float64) []float64 {
  res := []float64{a + b, a - b, b - a, a * b}
  if a != 0 {
    res = append(res, b/a)
  }
  if b != 0 {
    res = append(res, a/b)
  }
  return res
}

func (s *Solution) checkIfResultReached(list []float64) bool {
  if len(list) == 1 {
    return math.Abs(list[0]-24) <= 0.1
  }

  for i := 0; i < len(list); i++ {
    for j := i + 1; j < len(list); j++ {
      newList := make([]float64, 0, len(list)-1)
      for k := 0; k < len(list); k++ {
        if k != i && k != j {
          newList = append(newList, list[k])
        }
      }
      for _, res := range s.generatePossibleResults(list[i], list[j]) {
        newList = append(newList, res)
        if s.checkIfResultReached(newList) {
          return true
        }
        newList = newList[:len(newList)-1]
      }
    }
  }
  return false
}

func (s *Solution) judgePoint24(cards []int) bool {
  list := make([]float64, len(cards))
  for i, card := range cards {
    list[i] = float64(card)
  }
  return s.checkIfResultReached(list)
}

Explanation

Algorithm

Создайте функцию generatePossibleResults(a, b), которая возвращает массив результатов всех возможных математических операций над двумя числами.

Создайте функцию checkIfResultReached(list), чтобы проверить, можем ли мы достичь результата 24, используя текущий массив list. Сначала проверьте базовые условия: если размер массива равен 1, верните true, если результат равен 24, иначе верните false.

Если размер массива больше 1, выберите любые два числа из списка, выполните все математические операции над ними, создайте новый список с обновленными элементами и снова вызовите рекурсивную функцию с этим новым списком. Если ни одна комбинация не приводит к результату 24, верните false. Вызовите checkIfResultReached с исходным списком карт.

😎