#hard
Задача: 446. Arithmetic Slices II - Subsequence


Дан целочисленный массив nums, вернуть количество всех арифметических подпоследовательностей nums.

Последовательность чисел называется арифметической, если она состоит как минимум из трех элементов и если разница между любыми двумя последовательными элементами одинаковая.

Например, [1, 3, 5, 7, 9], [7, 7, 7, 7] и [3, -1, -5, -9] являются арифметическими последовательностями.
Например, [1, 1, 2, 5, 7] не является арифметической последовательностью.
Подпоследовательность массива - это последовательность, которая может быть образована путем удаления некоторых элементов (возможно, ни одного) из массива.

Например, [2, 5, 10] является подпоследовательностью [1, 2, 1, 2, 4, 1, 5, 10].
Тестовые случаи сгенерированы таким образом, что ответ помещается в 32-битное целое число.

Пример:

Input: nums = [2,4,6,8,10]
Output: 7
Explanation: All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

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

1⃣Мы можем использовать поиск в глубину (DFS) для генерации всех подпоследовательностей.

2⃣Мы можем проверить, является ли подпоследовательность арифметической, согласно ее определению.

3⃣Возвращаем количество всех арифметических подпоследовательностей.

😎 Решение:

class Solution {
    private $n;
    private $ans;

    private function dfs($dep, $A, $cur) {
        if ($dep == $this->n) {
            if (count($cur) < 3) return;
            for ($i = 1; $i < count($cur); $i++) {
                if ($cur[$i] - $cur[$i - 1] != $cur[1] - $cur[0]) return;
            }
            $this->ans++;
            return;
        }
        $this->dfs($dep + 1, $A, $cur);
        array_push($cur, $A[$dep]);
        $this->dfs($dep + 1, $A, $cur);
    }

    public function numberOfArithmeticSlices($A) {
        $this->n = count($A);
        $this->ans = 0;
        $this->dfs(0, $A, []);
        return $this->ans;
    }
}

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

#hard
Задача: 591. Tag Validator

Дана строка, представляющая фрагмент кода, реализуйте валидатор тегов для разбора кода и определения его корректности.

Фрагмент кода считается корректным, если соблюдаются все следующие правила:
Код должен быть заключен в корректный закрытый тег. В противном случае код некорректен.
Закрытый тег (не обязательно корректный) имеет точно следующий формат: <TAG_NAME>TAG_CONTENT</TAG_NAME>. Среди них <TAG_NAME> — это начальный тег, а </TAG_NAME> — конечный тег. TAG_NAME в начальном и конечном тегах должен быть одинаковым. Закрытый тег корректен, если и только если TAG_NAME и TAG_CONTENT корректны.
Корректное TAG_NAME содержит только заглавные буквы и имеет длину в диапазоне [1, 9]. В противном случае TAG_NAME некорректен.
Корректное TAG_CONTENT может содержать другие корректные закрытые теги, cdata и любые символы (см. примечание 1), КРОМЕ неподходящих <, неподходящих начальных и конечных тегов, и неподходящих или закрытых тегов с некорректным TAG_NAME. В противном случае TAG_CONTENT некорректен.
Начальный тег неподходящий, если нет конечного тега с тем же TAG_NAME, и наоборот. Однако нужно также учитывать проблему несбалансированных тегов, когда они вложены.
< неподходящий, если не удается найти последующий >. И когда вы находите < или </, все последующие символы до следующего > должны быть разобраны как TAG_NAME (не обязательно корректный).
cdata имеет следующий формат: <![CDATA[CDATA_CONTENT]]>. Диапазон CDATA_CONTENT определяется как символы между <![CDATA[ и первым последующим ]]>.
CDATA_CONTENT может содержать любые символы. Функция cdata заключается в том, чтобы запретить валидатору разбирать CDATA_CONTENT, поэтому даже если в нем есть символы, которые могут быть разобраны как тег (корректный или некорректный), вы должны рассматривать их как обычные символы.

Пример:

Input: code = "<DIV>This is the first line <![CDATA[<div>]]></DIV>"
Output: true

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

1⃣Инициализируйте стек для отслеживания открытых тегов и флаг для определения наличия тегов. Используйте регулярное выражение для проверки корректности TAG_NAME, TAG_CONTENT и CDATA.

2⃣Пройдитесь по строке, проверяя каждый символ. Если встретите <, определите тип тега (начальный, конечный или CDATA). Обновите стек и индексы в зависимости от найденного типа.

3⃣В конце проверьте, что стек пуст (все теги корректно закрыты) и верните результат.

😎 Решение:

class Solution {
    private $stack = [];
    private $containsTag = false;

    private function isValidTagName($s, $ending) {
        if ($ending) {
            if (!empty($this->stack) && end($this->stack) === $s) {
                array_pop($this->stack);
            } else {
                return false;
            }
        } else {
            $this->containsTag = true;
            $this->stack[] = $s;
        }
        return true;
    }

    public function isValid($code) {
        $regex = "/<[A-Z]{0,9}>([^<]*(<((\/?[A-Z]{1,9}>)|(!\[CDATA\[.*?\]\]>)))?)*/";
        if (!preg_match($regex, $code)) {
            return false;
        }

        $i = 0;
        while ($i < strlen($code)) {
            $ending = false;
            if (empty($this->stack) && $this->containsTag) {
                return false;
            }
            if ($code[$i] === '<') {
                if ($code[$i + 1] === '!') {
                    $i = strpos($code, "]]>", $i + 1);
                    if ($i === false) {
                        return false;
                    }
                    continue;
                }
                if ($code[$i + 1] === '/') {
                    $i++;
                    $ending = true;
                }
                $closeIndex = strpos($code, '>', $i + 1);
                if ($closeIndex === false || !$this->isValidTagName(substr($code, $i + 1, $closeIndex - $i - 1), $ending)) {
                    return false;
                }
                $i = $closeIndex;
            }
            $i++;
        }
        return empty($this->stack);
    }
}

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