PHP Backend | YeaHub

#ЛитКод
Задача: 494. Target Sum

Вам дан массив целых чисел nums и целое число target.

Вы хотите создать выражение из nums, добавляя один из символов '+' или '-' перед каждым числом в nums, а затем объединяя все числа.
Например, если nums = [2, 1], вы можете добавить '+' перед 2 и '-' перед 1, а затем объединить их, чтобы получить выражение "+2-1".
Верните количество различных выражений, которые можно построить и которые оцениваются в target.

Пример:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

👨‍💻 Алгоритм:

1⃣Инициализация и вызов рекурсивной функции
Создайте переменную для хранения количества решений (count). Вызовите рекурсивную функцию calculate с начальными параметрами (nums, начальный индекс 0, начальная сумма 0, и target).

2⃣Рекурсивная функция calculate
Если текущий индекс равен длине массива, проверьте, равна ли текущая сумма значению target. Если да, увеличьте счетчик решений. В противном случае, вызовите функцию рекурсивно дважды: добавляя и вычитая текущее значение из суммы.

3⃣Возврат результата
После завершения всех рекурсивных вызовов верните значение счетчика решений.

😎 Решение:

class Solution {
    private $count = 0;

    function findTargetSumWays($nums, $S) {
        $this->calculate($nums, 0, 0, $S);
        return $this->count;
    }

    private function calculate($nums, $i, $sum, $S) {
        if ($i == count($nums)) {
            if ($sum == $S) {
                $this->count++;
            }
        } else {
            $this->calculate($nums, $i + 1, $sum + $nums[$i], $S);
            $this->calculate($nums, $i + 1, $sum - $nums[$i], $S);
        }
    }
}

👉Новости 👉База вопросов

Please open Telegram to view this post

VIEW IN TELEGRAM

LeetCode

Minimum Size Subarray Sum - LeetCode

Can you solve this real interview question? Minimum Size Subarray Sum - Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray…

👍1

www.tgoop.com/yeahub_php_backend/381

133 viewsSep 5 at 08:01

#ЛитКод
Задача: 494. Target Sum

Вам дан массив целых чисел nums и целое число target.

Вы хотите создать выражение из nums, добавляя один из символов '+' или '-' перед каждым числом в nums, а затем объединяя все числа.
Например, если nums = [2, 1], вы можете добавить '+' перед 2 и '-' перед 1, а затем объединить их, чтобы получить выражение "+2-1".
Верните количество различных выражений, которые можно построить и которые оцениваются в target.

Пример:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

class Solution {
    private $count = 0;

    function findTargetSumWays($nums, $S) {
        $this->calculate($nums, 0, 0, $S);
        return $this->count;
    }

    private function calculate($nums, $i, $sum, $S) {
        if ($i == count($nums)) {
            if ($sum == $S) {
                $this->count++;
            }
        } else {
            $this->calculate($nums, $i + 1, $sum + $nums[$i], $S);
            $this->calculate($nums, $i + 1, $sum - $nums[$i], $S);
        }
    }
}