Ответы пользователя по тегу JavaScript
  • Как правильно рассчитать коэффициент полезного использования пространства?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Обход в ширину, он же алгоритм заливки: закрасьте на невидимом канвазе или в массиве все блоки, пройдитесь по всей границе канваза/массива, если там непокрашенная точка, то красьте ее и добавляйте ее в очередь. Потом берите из очереди точки и добавляйте в нее 4 соседа, если они еще не покрашены. В конце все непокрашенные пиксели - ваши полости.

    Можно ускорить алгоритм сжатием координат: вввпишите все x и y координаты всех углов блоков, отсортируйте и унифицируйте (отдельно по каждой оси). Потом замените все координаты в блоках на порядковый номер в массиве уникальных координат. Примените алгоритм выше, но в конце надо помнить, что каждая ячейка теперь не 1x1, а сколько-то больше по вертикали и горизонтали.
    Ответ написан
  • Почему не отсеиваются нули при сравнении 0 < 0?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    array[index + 1] ? item < array[index + 1] : true Что эта конструкция делает, можете объяснить? Ошибка в ней.
    Ответ написан
    5 комментариев
  • Какая временная сложность у этого алгоритма?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Линейная. O(N+M). Ибо там цикл по i от 0 до startMedianIndex и вся остальная мишура на i вообще никак не влияет. Больше циклов в программе нет. Не понимаю, что тут может быть непонятного.
    Ответ написан
    Комментировать
  • Как лучше развернуть двумерный массив?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Если не обязательно делать поворт на месте, то вся суть алгоритма вот в этой одной строке:
    result[i][j] = arr[n-1-j][i];
    Надо только циклы прогнать по нужным границам, да массив нужного размера создать.

    Если матрица квадратная, то элементы сдвигаются по кругу в четверках - и это можно сделать без дополнительного массива . Можно делать сдвиг по кругу со временной переменной. Что-то вроде этого:
    tmp = arr[i][j];
    arr[i][j] = arr[n-1-j][i];
    arr[n-1-j][i] = arr[n-1-i][n-1-j];
    arr[n-1-i][n-1-j] = arr[j][n-1-i];
    arr[j][n-1-i] = tmp;


    И надо аккуратно границы цикла подобрать, чтобы там только левый верхний угол обработался. Иначе вы 4 раза в каждом круге сдвините, и ничего не поменяется.
    Ответ написан
    Комментировать
  • Как правильно реализовать алгоритм бинарного поиска?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Во-первых, лучшее решение тут - это использовать структуру данных "бор", а не запускать бинарный поиск по сортированным строкам. Да, в конце-концов, какой-нибудь встроенный ассоциативный массив или словарь в вашем языке программирования может быть эффективнее вашего ручного бинарного поиска.

    Но если вам по заданию надо бинпоиск использовать, то у вас там следующие ошибки в реализации:
    - постоянное преобразование к toLowerCase - это ОЧЕНЬ неэффективно. Один раз все приведите к lowerCase и работайте только с этим. Можно эти ключи схоранить в новых полях.
    - когда вы нашли совпадение, можно делать из цикла break.

    Вы не сможете бинпоиском найти все объекты. Он может найти только один. Самый левый, самый правый, или как повезет - зависит от реализации.
    Вам надо запустить два бинпоиска последовательно. Один будет искать минимальный элемент, больше равный искомому (lower_bound), а второй бинпоиск будет искать максимальный элемент строго больший искомому (upper_bound). Пусть ваши бинпоиски возвращают индекс в массиве list. Эти две функции будут отличаться только в одном месте - там будет < и <= соответсственно.
    Ответ к задаче будет в массиве list по индексам от lower_bound (включительно) до upper_bound (не включительно). Может быть и так, что lower_bound == upper_bound, если искомого элемента в массиве нет и ответ будет пустым.
    Ответ написан
    2 комментария
  • Min max алгоритм или как сделать ползунок сложности в игре?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Можно при просчете вершины дерева игры выбирать не максимальное/минимальное значение из всех детей, а второе с конца с некоторой вероятностью. Значение вероятности задаётся уровнем сложности.
    Ответ написан
    Комментировать
  • Как из массива целых чисел найти все возможные комбинации (не только двух чисел, а и более) дающие искомую сумму?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Во-первых, таких комбинаций может быть до 2^n, где n - количество чисел в массиве.

    Можно рекурсивно перебрать числа: функция принимает список уже выбранных чисел, их сумму и сколько первых чисел массива обработаны. Если все числа обработаны, функция сравнивает сумму с искомой и, если надо, выводит список. Потом завершается. Если еще не все числа обработанны, то функция два раза рекурсивно вызвается с параметрами: Текущее число добавлено или нет в список, обработано на одно чисел больше.

    Другой вариант, через битовые маски, без рекурсии. Перебирайте число от 0 до 2^n-1. Потом смотрите на него, как на битовую маску. Так вы переберете все подмножества из n элементов. Если i-ый бит установлен, то берите i-ое число в сумму. Если сумма совпала с искомой - вы нашли вариант.

    Ну и самый быстрый вариант: с использованием динамического программирования. Как в задаче о рюкзаке вам надо подсчитать F(i,j) - можно ли числами с i-ого по последнее собрать сумму равную j. Потом рекурсивый перебор оптимизируется с этой информацией. Вы текущее число берете или нет и запускаетесь рекурсивно, если оставшимеся числами можно набрать оставшуюся сумму до ответа.

    В общем случае это решение будет работать все так же экспоненциально. Но, если ответ не большой, т.е. вариантов набрать нужную сумму не много, то это будет сильно быстрее первых двух решений, потому что тупиковые ветки не перебираются.
    Ответ написан
    Комментировать
  • Какой алгоритм быстрее и почему?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Ваш алгоритм быстрее. Но в задаче часто бывает сработает не только самый быстрый код. Например, если там чисел всего 10 в массиве, то вы никакими измерениями разницу между сортировкой и вашим решением не намеряете (если только не запустите оба решения миллионы раз. Но это же уже другая задача. Ваша задача - найти минимальные 2 числа в одном массиве и ограничение по времени, если и есть, будет считаться по одному массиву)

    Поэтому иногда имеет смысл написать не самый быстрый алгоритм, но зато гораздо более простой. Если он проходит, то зачем кодить больше?

    В вашем алгоритме еще проблема, что не очевидно, почему он работает. Надо аккуратно рассматреть все 6 случев расположения arr[0], arr[1] и numbers[i] и убедиться, что инваринат "2 минмальных числа лежат в arr" поддерживается. Тут легко накосячить, перепутать 0 и 1, не там проверку поставить и все.

    Обычно, когда такой алгортм реализуют, поддерживают более строгий инвариант "минимальное число в arr[0], следующее минимальное число в arr[1]". Тогда проверки чуть чуть упрощаются и за логикой решения следить проще.
    Ответ написан
    1 комментарий
  • Какой алгоритм использовать для нахождения точки?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Вам уже подсказали: Триангуляция по 4 точкам.

    При чем не надо решать систему в общем виде. Если вы возьмете ваши 4 точки как (0,0,0) и (0,0,1), (0,1,0) и (1, 0, 0) то вы уже можете найти координаты искомой точки, не решая даже квадратных уравнений или систем.

    Например, для первых двух точек:
    x^2+y^2+z^2 = d1^2
    x^2+y^2+(z-1)^2 = d2^2


    Вычтите одно уравнение из другого, сократите все сокращаемое, поделите на 2 и в одно арифмитическое действие найдете z.

    Точно также можно найти x и y, рассматривая другие пары уравнений.
    Ответ написан
    Комментировать
  • Как правильно решить задачу, используя формулу комбинаторики?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Размещение тут не лучшая идея, потому что придется перебирать, сколько же двоек будет в пути.

    Тут вообще-то ответ - числа фиббоначи. Подумайте, почему.
    Ответ написан
    Комментировать
  • Обход Dom дерева как то относится к дискретной математике?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Просто при обходе - нет ничего не даст.
    Ответ написан
    Комментировать
  • Кто знает решение?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Вы умножаете на 2. А надо возводить в квадрат, т.е. в степень 2 ("power").
    Ответ написан
    2 комментария
  • Как в js равномерно распределить комбинации пунктов в массиве, который был создан с помощью рекурсивного размещения?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Если вам не надо чтобы каждый человек одинаково часто работал с каждым другим, то подойдет обощение решения, предложенного в комментариях Alexandroppolus и Сергей Сергей.

    Допустим количество работ (N) и количество людей (M) взаимно просты.

    Тогда сгенерируйте M строчек беря людей подряд:
    1, 2, 3
    4, 5, 1
    2, 3, 4
    5, 1, 2
    3, 4, 5

    Тут каждый человек одинаковое количество раз (по одному разу) будет на каждой работе. И дни, когда он будет работать будут максимально равномерно распределены (минимальное расстояние и максимальное между соседними работами будут различаться максимум на 1 и равны floor(N/M) и ceil(N/M)). Это идеальное с точки зрения равенства расписание. Но у него минус - частоты пар работников будут не одинаковыми. 1 гораздо чаще будет работать с 2 и 5, чем с 3 и 4.

    Теперь, если N и M не взяимно просты. Пусть D = GCD(N,M) - наибольший общий делитель.

    Разбейте всех людей на D групп по N'=N/D человек. N' и M взяимно просты, поэтому можно применить алгоритм выше к каждой группе.

    Дальше эти D расписаний надо перемешать. Для максимальной равномерности - сначала взять все первые строки всех расписаний, потом все вторые, и т.д.

    На i-ом месте будет день i / N' из расписания i % N' (если индексация с 0).

    Так, например, решение для 2 работ и 6 людей:

    N' = 3. 2 группы.
    В первой:
    1 2
    3 1
    2 3

    Во второй:
    4 5
    6 4
    5 6

    В итоге:
    1 2
    4 5
    3 1
    6 4
    2 3
    5 6
    Ответ написан
    Комментировать
  • Какова сложность алгоритма?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Квадратичная сложность.

    Решение со стеком будет линейным.
    Ответ написан
    Комментировать
  • На сколько критичен сдвиг в массиве для алгоритмов?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Удаление из массива - медленно в общем случае. Если удалять хитро - поменяв элемент с последним и удалить с конца, то будет гораздо быстрее. Но это не во всех алгоритмах возможно.

    Но самое быстрое решение вашей задачи будет положить один массив в хеш таблицу, и при проходе по второму проверять, есть ли текущий элемент в таблице. Для борьбы с повторяющимеся элементами вв таблице по ключу храните счётчик одинаковых элементов и уменьшайте его при нахождении совпадения.
    Ответ написан
    4 комментария
  • Как составить функцию, которая отдала бы вероятность в зависимости от текущего времени?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Соберите вашу функцию из квдаратичных или кубических сплайнов.

    Когда подберете параметры, функция будет вычислятся кусочно. Сначала найдите к какому отрезку относится текущее время (или тупо циклом или набором if-else, или, если сделаете отрезки одинаковым количеством часов, то можно поделить время на длину отрезка и округлить вниз, чтобы получить номер отрезка). Потом вычислите значение нужного сплайна, что будет просто вычислением полинома второй или третьей степени.

    Ну, или можете просто задать нексолько ключевых значений, и проинтерполировать полиномом лагранжа. Правда тут сложно будет заставить его идти именно как вам хочется. Через точки-то он точно пройдет, но вот между ними может иметь какие-то левые пики и изгибы. Так что придется поэксперементировать. Можно поиграться, например, в wolframalpha.com (введите "interpolating polynomial calculator", потом задайте значения функции в точках и получите и график и формулу. Ссылку дать не могу, qna ссылки на wolfram банит за одно со спамерскими ссылками по ошибке).
    Ответ написан
    Комментировать
  • Как вернуть первые N максимальных элементов из массива без сортировки массива?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Есть такой алгоритм. Называется quickSelect. Фактически, это обрезанный quickSort, где после выбора ведущего элемента и разбивки массива работа продолжается только в той половине, где находится раздел между первыми K элементами и остальными N-K.

    Пусть у вас N элементов в массиве и надо вернуть K минимальных. Тогда сортировка будет работать за O(N log N), а quickselect за O(N) в среднем*. В худшем случае может быть и квадратичное время работы, но этот случай практически невозможен, если реализация испольует случайные числа для выбора ведущего элемента.

    Если же вы боитесь этого худшего случая, или считаете себя самим невезучим человеком за всю историю человечества (или боитесь, что злой хакер взломает генератор случайных чисел и передаст вашей программе специально составленный массив, чтобы ее подвесить), то есть другой алгоритм, всегда работающий за O(n log k). При маленьких k - может быть даже быстрее первого алгоритма.

    Суть его в том, чтобы в куче (heap aka priority queue) поддерживать пока найденные K минимальных элементов. При этом куча будет на максимум. Сначала туда кладутся первые k элементов массива, а потом каждый следующий вытесняет максимальный элемент в куче, если он его меньше.

    * Вообще говоря, можно заставить quickselect и quicksort работать идеально всегда, если использовать алгоритм Блюма-Флойда-Пратта-Ривеста-Тарьяна, который ищет медиану за O(n). Но на практике этот алгоритм не применятеся, потому что у него такая константа, что там на логарифм хватит и еще на квадрат останется.
    Ответ написан
    2 комментария
  • Как написать кастомный findIndex с бинарным поиском?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Есть два варианта. Первый - функция возвращает -1, 0 или 1 сравнивая 2 элемента в зависимости от того, какой меньше или если они равны.

    Второй вариант - функция должна возвращать 1, если первый элемент строго меньше второго.

    Тогда равнество можно сделать так: !f(a,b) && !f(b,a). А второе условие просто заменяется на один вызов функции.
    Ответ написан
    7 комментариев
  • Нужно ли строго проверять if?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    А почему не рассматривается третий вариант? Что-нибудь вроде
    if (ToString(exampleVar)[0].length() == 4) alert(1)


    Умышленно писать === true, конечно может быть иногда оправданно в языках без строгой типизации, но в целом это довольно редко оправданная вещь.
    Ответ написан
    Комментировать
  • Фибоначчи без использования BigInt на javascript?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Без BigInt - никак. Числа-то большие получаются. Если нет библиотеки, придется самостоятельно писать длинную арифметику. Просто храните цифры числа в массиве и длину рядом. Вам надо будет только сложение реализовывать, ну это делается столбиком одним циклом. Храните перенос с младших разрядов в переменной. Можно или исходники BigInt поискать, или вот тут посмотреть
    Ответ написан
    Комментировать