Alexandroppolus

Rsa97 правильно написал про геометрический смысл. Но есть более быстрое решение за O(n log n), использующее метод заметающей прямой.

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

Если числа в задаче большие или нецелые, то сначала через бинпоиск или хешмап замените все координаты по X и по Y на их порядковый номер в отсортированном массиве (отдельно по каждой оси). Эта операция называется "сжатие координат". Теперь у вас все координаты целые числа от 0 до 2*n.

Потом примените алгоритм "заметающей прямой". Представьте, что вертикальная линия двигается слева-направо и "заметает" картинку. Вам надо отслеживать, какие прямоугольники ее пересекают в каждый момент времени и проверить, что вся прямая покрыта в каждый момент.

Для этого каждый прямоугольник (X1, Y1, X2, Y2) создаст 2 события "открылся отрезок с Y1 до Y2 во время X1" и "закрылся отрезок с Y1 до Y2 во время X2". Эти все события вы сортируете по X и в таком порядке обрабатываете.

Для отслеживания состояния прямой используйте дерево отрезков на минимум с отложенной суммой. Эта структура данных потребует массив на примерно 4n элементов для дерева с 2n листами. Каждая вершина будет хранить минимум на соответсвующем ей отрезке. При открытии прямоугольника вы должны добавить +1 на его отрезок. При закрытии - вычесть 1. Сначала открывайте прямоугольники, если время у событий одинаковое. Учитывайте это при сортировке. Так касающиеся по вертикали прямоугольники не создадут пустых мест.
Если после обработки какого-либо события вы получили минимум в дереве отрезков 0 и следующее событие имеет большую координату по X - то какая-то часть оказалась не покрыта. Еще есть случай, если первое событие не X1=левая граница покрываемого прямоугольника, или последнее событие - не X2=правая граница всего прямоугольника. Тут тоже покрытия нет.

Еще, аккуратно с целыми числами, чтобы если у вас 2 прямоугольника касаются горизонтальными сторонами - там пустое место не подсчиталось. Например, каждый лист дерева отвечает за единичный отрезок координат. Тогда изменяйте в дереве всегда отрезок от Y1 до Y2-1 для события с координатам Y1..Y2.

Решение за один проход с поддержкой массивов и таплов. Глубина любая.

https://www.typescriptlang.org/play/?#code/C4TwDgp...

Основное отличие от решения Alexandroppolus, ключи собираются последовательно и не парсятся, но результат, понятное дело, одинаковый.

type JoinKeys<T extends object> = JoinKeysDeep<T> extends infer J extends Record<
  string,
  unknown
>
  ? { [Key in J extends J ? keyof J : never]: J extends J ? J[Key] : never }
  : never;

type JoinKeysDeep<
  T extends object,
  K extends keyof T = JoinKeysDeep.GetKeys<T> & keyof T,
> = K extends K & (string | number)
  ? T[K] extends object
    ? JoinKeysDeep<T[K]> extends infer J extends Record<string, unknown>
      ? J extends J
        ? Record<`${K | '*'}.${keyof J & (string | number)}`, J[keyof J]>
        : never
      : never
    : Record<K | '*', T[K]>
  : never;
namespace JoinKeysDeep {
  export type GetKeys<T> = T extends unknown[]
    ? keyof T &
        (number extends T['length']
          ? // array
            number
          : // tuple
            `${number}`)
    : keyof T;
}

Два наблюдения:
1) изначальная формула имеет вид (a=>b)*(b=>a).
2) b = !a

Отсюда в одно действие видно, что она вырождается в ложь: (a=>!a)*(!a=>a)

Для второго наблюдения надо применить какой-то там закон, что !x+xy=!x+y

https://www.typescriptlang.org/play?#code/C4TwDgpg...

type ExtractValuesFromSubKeys<T extends object, SK extends string, K extends keyof T & string = keyof T & string> = K extends `${string}${SK}${string}` ? T[K] : never

function getValue<T extends object>(obj: T, isIncludeKey?: false): <K extends keyof T>(key: K) => T[K]
function getValue<T extends object>(obj: T, isIncludeKey: true): <SK extends string>(subKey: SK) => ExtractValuesFromSubKeys<T, SK>[]
function getValue<T extends object>(obj: T, isIncludeKey?: boolean) {
  return (keyOrSubKey: string) => {
    if (!isIncludeKey) {
      const key = keyOrSubKey as keyof T

      return obj[key];
    }

    const subKey = keyOrSubKey

    return Object.keys(obj).filter(key => key.includes(subKey)).map(key => obj[key as keyof T])
  }
}

const getter = getValue({ aaa: 1, bbb: '2', ccc: [3], abc: null }, true);

const ttt1 = getter("a") // (number | null)[]
const ttt2 = getter("bb") // string[]
const ttt3 = getter("ccc") // number[][]
const ttt4 = getter("unknown") // never[]

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

Тогда постройте граф на n*m*l вершин. Каждая вершина соответствует тройке (x, y, k) и означает, что мы как-то походили по полю и оказались в координате (x, y), при этом набрав первые k символов искомой строки. Переходы в графе тут такие: от каждой вершины можно пойти в 4 соседние по координатам, а количество символов увеличивается на 1, если в следующей вершине читается следующая буква строки. Т.е. переходы вида (x, y, k) -> (x+1, y, k + (s[k] == grid[x+1][y] ? 1 : 0)); (x, y, k) -> (x, y+1, k + (s[k] == grid[x][y+1] ? 1 : 0)) и еще 2 на минус (если x,y не у стенки поля, естественно - некоторые переходы могут отсутствовать).

Ищите кратчайшее расстояние из вершины (x0, y0, s[0] == grid[x0][y0] ? 1 : 0) в любую вершину с третим индексом равным l (т.е. любое место, где вы прочтете всю искомую строку). Поскольку в графе все ребра длины 1, можно запускать bfs. Граф строить и охранить не надо, можно эти 4 перехода вычислять неявно. Кладите в очередь тройки чисел, вынимайте их оттуда и вычисляйте до 4 соседних троек, которые гужно тоже сложить в очередь обхода в ширину. Удобно завести 2 костантных массива на 4 элемента, которые будут хранить приращения по x и по y в каждую их четрех сторон. Тогда не будет много дублируемого кода.

Еще понадобится, таки, массив на n*m*l для хранения расстояния, или хотя бы пометок о том, что вершина уже в очередь была положена.

Ваш алгоритм работает за O(n^2). Вы для каждого числа в массиве считатете, сколько раз оно туда входит проходя по массиву через nums.count(i). Оптимальное же решение работает O(n). Надо в хеш-таблице подсчитать, сколько раз каждое число встречается, потом через алгоритм QuickSelect выбрать k-ый c конца элемент.

Ну, или можно за O(n log n) отсортировать массив и потом за один проход подсчитать сколько раз каждое число встречается. Дальше можно второй раз отсортировать по количеству вхождений и выдать k-ый элемент. Это решение тоже пройдет.

Каждый вызов createCounter() создаёт и возвращает новую функцию. С которой в комплекте идёт свой новый «чемодан» замыкания, в котором лежит своя переменная counter.
Каждый раз отдельная-новая.

откуда берется counter при втором вызове console.log(z())

Из того же «чемодана» от первого вызова createCounter()

Если обработчик должен отрабатывать ровно 1 раз, то лучше передавать опцию once:

box.addEventListener('mousemove', move, { once: true });

https://developer.mozilla.org/en-US/docs/Web/API/E...

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

type SomeType1 = { [index: string]: SomeType1 | null }
type SomeType2 = Record<string, SomeType2 | null> // Type alias 'SomeType2' circularly references itself.

Раз тут уже посчитаны приоритеты вычисления - просто рекурсивно проходишься по каждому узлу, вычисляя его.

Всё намного проще. Вам нужно решить тривиальное уравнение вида y=kx. Ответ вас удивит...

Я долго изучал высшую математику и теперь наконец готов поделиться с вами наибыстрейшим способом получить нуль: x=0. Это даже быстрее Saboteur .