Ответы пользователя по тегу JavaScript
  • Предложение алгоритма решения тестового задания?

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

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

    Но в ваше решение еще не рассматривает крайний случай - использованы все 33 буквы алфавита и есть надо что-то менять. Тут ответ 0, потому что замены делать никак не получится - после любой замены 2 разные типа букв станут одинаковыми и перемешаются. Разделить их после этого уже не получится.

    Если вы эти косяки исправите, ваше решение может не пройти по времени, потому что оно у вас за квадрат. Лучшее решение - пройтись по строкам одновременно одним циклом и запоминать в массиве, индексированном символами, (или мапе), какая буква алфавита во втором слове соответствует букве алфавита в первом слове. Если встречаете противоречие (в массиве уже что-то записано не такое как вы видите сейчас), то ответ 0.

    И еще. Не надо разбивать строки через .split(''). В JavaScript можно узнать длину строк и обратиться к i-ому символу не преобразуя в массив.
    Ответ написан
  • Комбинаторика в Java Script, как добавить точку во всех возможных комбинациях массива?

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

    Так для 3 символов "abc" будет вызвана функция для "ab", которая вернет [ab, a.b], дописав "c" и ".c" к каждому элементу мы получим [abc, ab.c, a.bc, a.b.c].
    Ответ написан
  • Есть ли библиотека на javascript, которая может находить сложные интегралы и брать обратную функцию?

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

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Большинство решений, уже предложенных тут, работают за квадрат и уже для n=10000 amount=5000 будут работать заметно долго. Конечно, вряд ли такое большое количество данных будет на клиенте, но даже при n=100, если функция выполняется часто, зачем ее делать в ~50 раз медленнее?

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

    Если хотите без splice(), то надо завести новый массив и потом скопировать в него элементы n-amount..n-1 в начало одним циклом, потом вторым циклом скопировать дальше элементы 0..n-amount-1.

    Зафиксированный вами интерфейс предполагает использование нового массива для результатов каждый раз. Но можно было бы сделать без использования много дополнительной памяти, тусуя сам массив на месте, если допустить изменение интерфейса.

    Правда, splice уже нельзя было бы использовать. Еще надо было бы знать теорию перестановок немного. Короче, вот решение, которое работает за линию и перемешивает массив на месте:

    function gcd(a,b) {
     if (a>b) return gcd(b,a);
     return a == 0? b : gcd(b%a, a);
    }
    
    function next(i, k) {
      return i >= k ? i-k : i+n-k
    }
    
    function moveToStartInPlace(arr, k) {
      n = arr.length;
      num_cycles = gcd(k,n)
      for (i=0; i < num_cycles; ++i) {
       saved_value = arr[i];
       j = i;
       nxt = next(j, k);
       while (nxt != i) { 
         arr[j] = arr[nxt];
         j = nxt;
         nxt = next(j, k);
       }
       arr[j] = saved_value;
      }
    }


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

    Функция next() возвращает, какой элемент должен встать на место i-ого в итоговом массиве.
    Если немного подумать, то станет понятно, что в перестановке ровно gcd(n,k) циклов, потому что в ней все прыжки делаются на +(n-k) или -k. Т,е. фактически делаются только прыжки -k(mod n). А это уже известный факт: если прыгать по массиву на +k, оборачиваясь из конца в начало, то мы вернемся в ту же точку, с которой начали и всего таких циклов будет gcd(n,k).
    Ответ написан
  • Как быстрее получить множество точек, входящих в прямоугольник?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Обычное k-d дерево, как по ссылке у freeExec тут будет работать неплохо и будет потреблять сравнительно мало памяти. Но оно не дает гарантию времени выполнения. Может так получится, что вы обойдете почти все вершины в дереве (то же O(n), n - количество точек), даже если в прямоугольник не попала ни одна точка. Правда для этого нужно иметь весьма специфическую конфигурацию точек и очень прямоугольник с большим периметром. Я думаю, этот вариант вам лучше всего подходит, если точки более менее случайно разбросаны и экран занимает лишь маленькую, более менее квадратную область.

    R-дерево (по той же ссылке) дает гарантию по времени выполнения и знимает сравнительно мало памяти, но его долго пересчитывать, если точки двигаются или добавляются/удаляются.

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

    Дерево отрезков, оно же segment tree - это структура данных, которая делит все пространство координат на половинки, пока не получит в листах по одной координате.

    Дерево поиска - это сбалансированное двоичное дерево поиска. Типа avl, красно-черных или декартовых деревьев. Возможно стандартный Set из JS или его аналог тут подойдет.

    Суть решения такая - вы разбиватете все пространство по одной координате (скажем, y) деревом отрезков. Каждая вершина этого дерева отвечает за некоторую горизонтальную полосу c фиксированными y координатами и ханит в себе Set всех точек, которые в эту полосу попадают. В Set храните какие-то ссылки на точки (допустим, их id в массиве всех точек), упорядоченные по x координате, а потом по y координате, а потом по id.

    Это фактически 2D дерево отрезков, но наивная реализация требовала бы MaxW*MaxH памяти, что слишком много. Замена внутренних деревьев отрезков на Set позволяет сильно сэкономить в памяти.

    При добавлении/удалении точки надо в дереве отрезков найти все вершины, которые покрывают ее y координату (их будет Log MaxH) и в их сетах удалить/добавить вершину с заданными (x,y) координатами.

    Важно, что set упорядочен по x координате, не той же по которой упорядочено дерево отрезков.

    Для получения всех точек в прямоугольнике стандартным обходом дерева отрезков найдите log(MaxH) вершин покрывающих прямоугольник по y координате. Теперь для каждого из найденных Set() найдите upper_bound левой границы. Теперь обойдите точки в Set, начиная с этой, пока не выйдете за правую границу прямоугольника и рисуйте их.

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

    Единственная проблема: похоже стандартный Set в JS не умеет делать upper_bound. Если точки не меняются часто, то можно вместо Set хранить массив точек отсортированный по x и бинарным поиском искать левую границу при обходе прямоугольника. Иначе же используйте вместо Set более продвинутую реализацию дерева поиска, которая поддерживает upper_bound. Возможно даже есть что-то стандартное в JS или есть готовые библиотеки - я не специалист.
    Ответ написан
  • Как обойти граф не зацикливаясь на связи одного узла с другим?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Вам обязательно отвечать на вопрос об электричесвте в конкретном доме по мере добавления ребер/вершин в граф?
    Если вам только тесты надо делать, то можно сначала создать весь мир, а потом поспрашивать его о статусах домов. При чем сами вычисления (обход графа) можно сделать только один раз, получить данные по всем домам и потом их проверить.

    В этом случае надо, как вы и предположили, хранить массив "посещенности" домов. Можно совместить его с массивом-ответом или статусами домов. Ваш метод уже не принимает конкретный дом как параметр, а просто считатет для всех домов. Он изначально заполняет массив для всех домов и электростанций нулями, что значит, что электричества в доме нет. Потом выполняется DFS (обзод в глубину) или BFS (обход в ширину) от электростанций, которые активны. При этом все посещенные вершины помечаются 1 в массиве. В уже помеченные вершины вы не ходите, поэтому алгоритм незациклиться.

    Если же вам обязательно надо узнавать статус домов после каждого изменения графа, то можно делать все тоже самое, но это будет медленно, ведь после каждого изменения вы будете обходить весь граф.

    Можно сделать гораздо быстрее. Если связи между домами только добавляются (но ни в коем случае не удаляются), то можно использовать систему непересекающихся множеств (DSU). Изначально каждый дом и электростанция - сами себе множество. В каждом множестве поддерживайте счетчик активных электростанций (изначально у домов - 0, у электростанций - 1). Это просто в реализации: у вас есть какой-то массив ссылок root, элеметы которого указывают сами на себя только в корне множества. Заведите второй массив, который будет по тем же индексам хранить счетчики для элементов. Точно также в вики по ссылке выше поддерживатеся rank.

    При добавлении провода вы должны слить 2 множества. При этом пересчитайте счетчик (прибавьте счетчик нижнего множества к счетчику верхнего множества).

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

    Это решение будет фактически работать за O(1) при каждом запросе и добавлении ребра (если использовать эвристику сжатия путей).
    Наивное же решение с полным обходом графа каждый раз было бы O(1) при добавлении ребра и O(n) при запросе.
    Ответ написан
  • Как найти все возможные комбинации чисел от 1 до n-1 чтобы их сумма была равна n?

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

    Можно хранить список взятых чисел в глобальном массвие/списке. Но надо аккуратно его откатывать. Перед рекурсивным вызовом, если добавили новое число, то после вызова его из массива/списка удалите. Так будет потребление памяти O(n) вместо O(n^2).

    Что-то типа такого:
    void Generate(int n, int next, int sum, vector<int> taken) {
      if (next > n || sum > n) return;
      if (sum == n) {
       Output(taken);
      }
      Generate(n, next+1, sum, taken);
      taken.push_back(next);
      Generate(n, next+1, sum+next, taken);
    }
    
    ...
    
    Generate(n, 1, 0, {});


    Но это решение будет не самым быстрым - ибо оно будет заходить в длинные "тупики".

    Вариант 2 - оптимизированный перебор, который не перебирает ничего лишнего. Сначала, как в задаче о рюкзаке, при решении динамическим программированием, найдем все варианты набрать каждую сумму.

    Заведите двумерный массив n x (n+1). d[i][j] будет хранить, можно ли собрать сумму j используя числа от 1 до i.

    База - d[0][0] = true (нет чисел - ноль набрать можно), d[i][0] = false (нет чисел. Не ноль набрать нельзя).

    пересчет: d[i][j] = d[i-1][j-i] or d[i-1][j] (или берем текущее число или нет)
    Естественно, первый вариант рассматривается только если i<=j. Можно подсчитать этот массив или рекурсивной функцией с запоминанием или просто тупо двумя вложенными циклами.

    Потом модифицируем нашу рекурсивную функцию из первого варианта. Теперь она будет как бы идти с конца и параметры будут - сколько первых чисел мы можем использовать, какую сумму должны набрать и какие бОльшие числа уже взяли. В функции опять 2 варианта - или берем текущее число или нет. Но при этом смотрим в массиве d[][], а можем ли мы вообще набрать нужную сумму данными нам числами. Если нет - сразу возвращаемся. Когда пришли к оставшейся сумме в 0, выводим набранные числа.

    Оба решения имеют временную сложность O(2^n), но второе будет в несколько раз быстрее, потому что не перебирает никаких тупиков. Возможно, если еще подумать можно избваиться от динамического программирования и вообще вывести формулу, когда из чисел от 1 до i можно собрать заданное число k (может там формула типа i*(i+1)/2 <= k).

    Если у вас задача стоит не вывести все наборы (их много! Порядка 2^n), а подсчитать их количество, то тут не надо рекурсивного перебора, а можно подифицировать динамическое программирование, которое будет вместо true/false считать сколько способов собрать из i чисел сумму j. будет формула вида d[i][j] = d[i-1][j] + d[i-1][j-i]. Тогда все решение будет за O(n^2) по времени и можно сделать его O(n) по памяти, если немного подумать (и хранить только две или одну строку матрицы d).
    Ответ написан
  • Как организовать такое поведение?

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

    Могу лишь дать пару советов по реализации.
    Пишите рекурсивную функцию которой передается оставшиеся не распределенные блюда и список уже готовых наборов (наборы из одного блюда - тоже наборы). Пытайтесь куда-то приспособить первое нераспределенное блюдо.

    Если наборы не большие (скажем, не более четырех типов блюд) и всего блюд в заказе не много, то можно делать в тупую - перебирайте в функции все 2-3 блюда, кроме первого, двумя-тремя вложенными циклами. Потом берете типы этих блюд и смотрите, а есть ли у вас такой набор. Наборы можно хранить как список списков и искать там бинарным поиском или линейно. Или можно завести 4-х мерный массив и дополнить короткие наборы заглушкой вида "" до 4-х блюд. Такой ассоциативный набор для каждой комбинации типов блюд будет хранить есть ли такой набор и сколько он стоит.

    Если же наборы могут быть больше или всего блюд многовато и надо бы побыстрее решать, то делайте следующее:
    Для каждого типа блюд заведите список наборов, в которые такой тип входит.
    В функцию передавайте блюда, сгруппированные по типам, и уже собранные наборы. Потом циклом перебирайте какой тип набора будете собирать с первым блюдом (у вас же есть список всех подходящих наборов) и вызывайте вторую рукурсивную функцию, которой передаются несобранные блюда, уже готовые наборы, какой тип набора собирается, и собранная часть текущего набора. Функция2 будет брать следующий неиспользованный тип в текущем наборе и, если блюда такого типа у вас есть, добавлять в цикле одно такое блюдо к набору и вызываться рекурсивно. Если весь набор собран, то рекурсивно вызывайте первую функцию.
    В первой функции, помимо перебора всех наборов, после цикла, просто берите первое блюдо как само себя.

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

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Нужно строить регрессию.
    Например, сделаейте так:
    Заведите таблицу, где у вас первый столбец - ваши значения. Второй столбец - проценты (p). Третий - константа 1. четвертый - квадрат процентов (p^2). Потом логарифмы (log p), корни разных степеней, обратные (1/p).
    Потом прогоните на этой таблице линейную регрессию методом наименьших квадратов (фактически - решить систему линейных уровнений, например, методом Гаусса), она даст вам коэффициенты перед всеми функциями в аналитической формуле. Если не угадали с функциями, то ошибка будет большая. Фукции с мелкими коэффициентами можно будет отбросить и заменять чем-то другим.
    Возможно стоит добавить логарифмов со здвигом вида c1*log(p+c2), как у Rsa97, но тогда при методе наименьщих квадратов будут не только линейные урванения, придется помучиться аналитически.
    Ответ написан
  • Фибоначчи: Возможно ли найти порядковый номер последовательности Фибоначчи ( x ), исходя из числа ( y )?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Не школьник, но вроде все просто.
    У вас есть y = B^x/A
    Дано y, отсюда x= log_B(A*y) = ln(A*y) / ln(B).

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

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

    1) найти ближайший сверху (слева/снизу/справа) из тех, которые имеют перекрытие.
    2) повторить операцию, найдя следующий сверху. Расстояние между ними взять за d.
    3) продолжить идти вверх. Если следующий ближайший тоже на расстоянии d - нарисовать промежуток. Если нет, то остановится.
    4) Зная ближайший прямоугольник из пункта 1) и расстояние d - можно его отступить вниз и у вас есть точка примагничивания.

    Можно ускорить алгоритм немного. Сначала за один проход выделите все прямоугольники, которые выше данного, но пересекаются с ним по оси X. Отсортируйте их снизу вверх по нижней границе. Теперь в пунктах 1,2,3 надо рассматривать только один следующий прямоугольник из списка.

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

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

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    В вашем решении надо оставить только один цикл. Лучше его заменить на while. i++ и j-- выплняются каждую итерацию.

    var j, i
     while (i < j;) {
          temp = str[i];
          str[i] = str[j];
          str[j] = temp;
          i++; 
          j--;
        }
      }
    Ответ написан
  • Как можно еще решить задачку?

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

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

    Для удобства реализации из второго параметра нужно выделить "открывающие" и "закрывающие" символы. Удобно в массиве из 256 элементов пометить все открывающие как-то (например, -1), Все закрывающие надо пометить номером соответствующего открывающиего символа. Т.е. для второго параметра "()[]". Для всех символов в массиве будет 0, но для '(' и '[' - будет -1. Для ')' будет в массиве хранится '(', а для ']' - '['.

    Тогда, при обработке символа из первой строки, если в массиве для него 0, то просто пропускаем. Если -1 - то кладем в стек. Если что-то другое, то проверяем, что это значение лежит в стеке на вершине.

    Ваше решение по ссылке на работает на тесте "())("
    Ответ написан