Публикации по теме 'competitive-programming'
Преобразование строки в целое число (atoi)
Вопрос:
Реализуйте atoi , который преобразует строку в целое число.
Сначала функция отбрасывает столько пробельных символов, сколько необходимо, пока не будет найден первый непробельный символ. Затем, начиная с этого символа, принимает необязательный начальный знак плюс или минус, за которым следует как можно больше числовых цифр, и интерпретирует их как числовое значение.
Строка может содержать дополнительные символы после тех, которые образуют целое число, которые игнорируются и..
GCDEX — GCD Extreme
Заявление
Учитывая значение N, вам нужно будет найти значение G. Значение G дано в следующем коде.
G = 0;
for (i = 1; i < N; i++)
for (j = i+1; j <= N; j++)
G += gcd(i, j);
Здесь gcd() — это функция, которая находит наибольший общий делитель двух входных чисел.
Первое решение
По функции Мёбиуса:
Временная сложность: O ( Q n log( n ))
Оптимизация 1 Определите набор возможных значений N/k:
Итак, можно перебрать S :..
Алгоритм голосования Бойера Мура
Для массива A, содержащего некоторое число, вам нужно найти элемент, вхождение которого в массиве больше, чем A.size () / 2.
Итак, подход грубой силы , примените два цикла: первый указатель, указывающий на элемент, и другой указатель, чтобы узнать, сколько раз этот элемент входил в массив.
Сложность времени O (n * n) Сложность пространства O (1)
Второй подход : использование сортировки
Отсортируйте массив, чтобы узнать, сколько раз элемент повторяется в массиве, здесь..
Leetcode[987] Вертикальный обход бинарного дерева
Сегодня мы рассмотрим следующую задачу, указанную как сложная , с степенью приемлемости 38,6% на момент написания.
Проблема выглядит следующим образом:
Учитывая root бинарного дерева, вычислите вертикальный обход бинарного дерева.
Для каждого узла в позиции (row, col) его левый и правый потомки будут в позициях (row + 1, col - 1) и (row + 1, col + 1) соответственно. Корень дерева находится в (0, 0) .
Обход по вертикали бинарного дерева представляет собой..
Битовые манипуляции для соревновательного программирования
Что такое битовая манипуляция?
Мы работаем с языками высокого уровня, имея дело с компьютерами. Все дело в 0 и 1. скажем, вы конвертируете 5 в его двоичную форму 0101. Это не что иное, как битовая манипуляция, то есть преобразование целого числа в двоичную форму и выполнение всех операций только с использованием битов.
Основные операции:
И & OR | НЕ ~ Левый "шифт Сдвиг вправо ›› Исключающее ИЛИ ^
Итак, мы хорошо знакомы с операциями AND, OR, NOT, XOR, они почти..
Что я узнал сегодня — СМЕСИ
Я занимаюсь соревновательным кодированием несколько месяцев. В настоящее время я решаю проблемы SPOJ.
Сегодня я столкнулся с интересной задачей под названием СМЕСИ . В основном в постановке задачи говорится, что
Имеются n смесей, расположенных в ряд. Каждая смесь имеет один из 100 различных цветов (цвета имеют номера от 0 до 99). Нужно смешать все эти смеси вместе. На каждом шаге мы можем взять две смеси, стоящие рядом, и смешать их между собой, а полученную смесь поставить на их..
Руководство для учащихся по динамическому программированию №2
Динамическое программирование — это алгоритмическая парадигма решения задач, ориентированная на распознавание и устранение повторяющихся вычислений. Ранее на этой неделе у меня была еще одна статья, посвященная динамическому программированию, и перспектива, которую я нашел полезной. Я оставляю ссылку на это ниже.
Руководство для учащихся по динамическому программированию №1 Динамическое программирование — это алгоритмическая парадигма решения задач,..
