Ответы пользователя по тегу JavaScript
  • Как вернуть первые 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 поискать, или вот тут посмотреть
    Ответ написан
    Комментировать
  • Как сделать дерево объектов из массива?

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

    Заведите мап объектов, которые будете собирать. Ключи будудт айдишники, а значения - объекты. У объектов заполните uid, parentUID, пустой Map children и пустой список children_list. Так же запомните куда-то id, у которого null отец.

    Потом еще одним проходом по списку всех элементов заполните children_list у всех обхектов в Map из прошлого шага (кладите текущий id в список для parentUID).

    Потом еще одним проходом по всем элементам этого Map соберите дерево: обойдите список детей и в Map children кладите 'id' => объект из внешнего Map'а по данному ключу. После прохода можно children_list удалить.

    Если я правильно понимаю, как работает JS, то у вас будет не копироваться объект а его ссылка. В итоге в Map будут осодержаться вообще все поддеревья ссылыющееся друг на друга. Можно потом вырвать оттуда объект по ключу id корня и Map удалить.
    Ответ написан
    Комментировать
  • Как из массива рандомных натуральных чисел вычислить две равные суммы?

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

    Она NP-полная - тут нет быстрых и простых решений. В общем случае, возможно только решение полным перебором за N*3^N. Что-то вроде того, что предложил Alexandroppolus, только там вообще не рассматривается случай, что текущее число просто пропускается. Еще можно делать это же без рекурсии на основе битовых масок.

    Если есть какие-то дополнительные условия (например, все числа очень маленькие), то может более быстрым быть решение на основе динамического программирования, как в задаче о рюкзаке.
    Ответ написан
    1 комментарий
  • Какой алгоритм лучше использовать для нахождения всех перестановок?

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

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

    Так, для генерации всех перестановок "abc", сначала рекурсивно будет получен массив {"bc", "cb"}, потом для каждого его элемента в ответ будет добавлена перестановка с "a" вставленным в позицию 0, 1 и 2: "abc", "bac", "bca" для первого элемента, и "acb", "cab" и "cba" для второго.

    Или вам не понятно, что делают reduce, slice, substring, concat, join?
    Ответ написан
    Комментировать
  • Какой алгоритм использовать для нахождение уравнения поверхности по 3 точками?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Пусть точка p=(x,y,z) принадлежит плоскости. Пусть 3 точки - p1, p2, p3.

    Тогда вектор (p-p1) должен раскладываться на вектора p2-p1 и p3-p1.

    Т.е. определитель матрицы 3x3 из этих трех векторов должен быть нулевым.

    det {{x-p1x, p2x-p1x, p3x-p1x},
     {y-p1y, p2y-p1y, p3y-p1y},
     {z-p1z, p2z-p1z, p3z-p1z}} = 0


    Раскрываете определитель по первому столбцу и получаете
    A = det({{p2y-p1y, p3y-p1y}, {p2z-p1z, p3z-p1z}})
    И т.д.
    D = -p1x*A-p1y*B-p1z*C
    Ответ написан
  • Какой алгоритм вычисления кратности чисел более эффективен?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Судя по названию функции (sum) вам надо найти сумму чисел. Это делается в одно действие без циклов вообще.

    Если бы были нужны только числа делящееся на 3, то их сумма - f(n, 3)=3*floor(n/3)(floor(n/3)+1)/2. Эта формула получается вынесением 3 за скобки в сумме и дальше применением формулы армфметической прогрессии.

    Чтобы взять сумму делящихся на 3 или 5 надо взять сумму делящихся на 3, прибавить сумму делящихся на 5 и вычесть сумму делящихся на 15. Потому что делящиеся на 15 были подсчитанны 2 раза в первых слагаемых. Т.е. ответ - f(n,3)+f(n,5)-f(n,15)
    Ответ написан
    Комментировать
  • С чего начать изучение алгоритмов?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Почитайте Кнут "искусство программирования" а также Кормен "алгоритмы: построение и анализ".
    Ответ написан
    Комментировать
  • Объявлять переменные внутри или перед циклом?

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

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Координаты центра ромба {x,y} - {130/2*(x-y), 84/2*(x+y)}

    Эту формулу можно вывести, например, не зная вообще ничего. Просто проведите все вертикальные линии через все центры ромбов. Какие ромбы лежат на одной прямой? Немного посмотрев, можно заметить, что это те, у которых разность координат одинаковая. Аналогично, проведя горизонтальные линии - можно заметить, что на одной горизонтали лежат ромбы с равной суммой координат.

    Далее надо найти координаты нескольких прямых и можно вывести формулу.

    Второй вариант - через геометрию векторов (это линейная алгебра, или еще нет - как это в школе-то называется вообще?). Нарисуйте вектор из ромба {0,0} в ромбы {1,0} и {0,1}. Ясно, что ромб с координатами {x,y} можно получить сложив x раз первый вектор и y раз второй. Подставляя координаты получите ту же формулу.
    Ответ написан
    Комментировать
  • Как перемешать массив в псевдослучайной последовательности?

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

    Или можно сортировать хеши, полученные из id тега и id статьи. Например, можно подсчитать tag_id*article_id % n.
    Ответ написан
  • Как найти самую ближайшую точку из массива?

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

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

    Потом пройдитесь по массиву, поддерживая счетчик открытых интервалов. Встретили "from" - увеличили счетчик. встретили "to" - уменьшили.

    Если изменили счетчик с 0 на 1, то в текущей дате начало отрезка в ответе. Если изменили с 1 на 0, то тут конец.

    Наверно, надо будет еще отрезки разбить по месяцам потом.

    Еще надо разобраться с тем, когда даты совпадают. Если в одну и ту же дату есть to и from - это же должно считаться одним отрезком? Тогда при сортировке ставьте "from" перед "to" на одну и ту же дату (В сравнении при равенстве дат сравнивайте еще и тип события).
    Ответ написан
    Комментировать
  • Как реализовать алгоритм Джарвиса для выпуклых оболочек?

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

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

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

    Вот набросок кода на C++, думайте, что это псевдокод.

    vector<int> ConvexHull(vector<double> x, vector<double> y) {
      int first = ...; // Тут поиск самой нижней-левой точки.
      const int n = x.size();
      int cur = first;
      vector<int> ans{first};
      // Текущий вектор стороны может идти вправо от самой нижней точки.
      double side_x = 1;
      double side_y = 0;
      while (true) { 
        int bsti = -1;
        // Вектор на лучшую точку.
        double bst_x = 0;
        double bst_y = 0;
        // Расстояние до нее.
        double bst_dist = 0;
        for (i = 0; i < n; ++i) {
          if (i == cur) continue;
          // Вектор на текущую точку.
          double cur_x = x[i] - x[cur];
          double cur_y = y[i] - y[cur];
          // Отсекаем точки назад вдоль оболочки на той же стороне.
          // Можно заменить пометкой в bool in_hull[],
          // которая ставится при добавлении точки в ответ (ans).
          if (side_x*cur_y-side_y*cur_x == 0 && side_x*cur_x+side_y*cur_y < 0) continue;
          double vec = bst_x*cur_y-bst_y*cur_x;
          double dist = cur_x*cur_x+cur_y*cur_y;
          // Берем точку, если она правее текущего кандидата. Или на той же прямой, но ближе.
          if (bsti == -1 || vec < 0 || (vec == 0 && dist < bst_dist)) {
            bsti = i;
            bst_dist = dist;
            bst_x = cur_x;
            bst_y = cur_y;
          } 
        }
        // Сделали полный оборот.
        if (bsti == first) break;
        side_x = bst_x;
        side_y = bst_y;
        and.push_back(bsti);
        cur = bsti;
      }
      return ans;
    }
    Ответ написан
    Комментировать
  • JavaScript - как проверить, есть ли в объекте циклические ссылки?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Поиск в глубину.

    Надо поддерживать список/множество уже посещенных вершин и пока посещаемых (те, что в стеке). При заходе в вершину в рекурсивной функции помещайте ее в множество пока посещаемых. При возвращении из функции перемещайте вершину в множество уже посещенных. В функции пройдитесь по всем ребрам, если они ведут в пока посещаемую вершину - вы нашли цикл. Если ребро ведет в уже посещенную - игнорируйте его. Если ребро ведет в не посещенную вершину - рекурсивно запускайтесь от нее.
    Ответ написан
    Комментировать
  • Может кто помочь а алгоритмом с сайта codility?

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

    Подсказка: тут отлично зайдет цикл do ... while. Одна переменная должна указывать, кто из людей сейчас активный. Вы должны дописать к ответу его букву и перейти к другому человеку взяв соответствующий элемент из массива A. Цикл должен работать, пока вы не вернетесь к первому человеку. Само решение будет буквально 3 строки, если не считать скобки.
    Ответ написан
    Комментировать
  • Как усовершенствовать алгоритм для уравнения Диофанта?

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

    Там по вашей ссылке в задаче есть подсказка: уравнение можно переписать в виде (x-2y)(x+2y)=n

    Отсюда получается решение: Перебирайте все делители n, не превосходащие корень. Пусть делитель d, тогда второй множитель будет n/d.

    Осталось решить систему линейных уравнений:

    x-2y=d
    x+2y=n/d


    Решается в уме - x=(d+n/d)/2, y=(n/d-d)/4

    Отслось только учесть диофантовость уравнения - ответ должен быть неотрицательные целые числа. Значит, надо чтобы оба делителя d, n/d давали одинаковый остаток от деления на 4 и 2. Ну и d<=n/d, но это учтется перебором делителя до корня.

    Вот и все решение - циклом переберите делитель до корня, убедитесь, что он и оставшийся множитель дают один и тот же остаток по модулю 4, вычислите x и y и выведите их.
    Ответ написан
    Комментировать