Практика Codility Lesson 6~10 с C++

Сортировка, Стеки и очереди, Лидер, Задача максимального среза, Простые и составные числа

Введение

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

Тесты от Codility или Leetcode обычно сосредоточены на правильности и производительности. Попробуйте найти лучшее решение, а не только решать проблемы, когда вы практикуете его.

Это моя заметка. Он охватывает урок с 6 до 10.

• Урок 6 Сортировка: MaxProductOfThree, Distinct, Triangle, NumberOfDiscIntersections
• Урок 7 Стеки и очереди: скобки, рыба, вложение, StoneWall
• Урок 8 Лидер: Dominator, EquiLeader
• Урок 9 Задача максимального среза: MaxProfit, MaxSliceSum, MaxDoubleSliceSum,
• Урок 10 Простые и составные числа: CountFactors, MinPerimeterRectangle, Peaks, Flags

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

Вас также могут заинтересовать главы 1–5.

Или главы 11~15.

Урок 6 Сортировка

6–1. Макспродуктофтри

• Краткое определение проблемы

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

• Ссылка

• Решение

• Производительность и правильность решения

6–2 Отличительные

• Краткое определение проблемы

Вычислить количество различных значений в массиве.

• Ссылка

• Решение

• Производительность и правильность решения

6–3 Треугольник

• Краткое определение проблемы

Определить, можно ли построить треугольник из заданного набора ребер.

• Ссылка

• Решение

• Производительность и правильность решения

6–4 Количество пересечений диска

• Краткое определение проблемы

Вычислите количество пересечений в последовательности дисков.

• Ссылка

• Решение

• Производительность и правильность решения

Урок 7 Стеки и очереди

7–1 скобки

• Краткое определение проблемы

Определите, правильно ли вложена данная строка скобок (несколько типов).

• Ссылка

• Решение

• Производительность и правильность решения

7–2 рыбы

• Краткое определение проблемы

По реке плывут N прожорливых рыб. Подсчитайте, сколько рыб живо.

• Ссылка

• Решение

1. Используйте свойства стека: первый вошел последним, выскочил, когда его съели
2. Используйте стек для хранения рыбы. Счет увеличивается, когда стек пуст.

• Производительность и правильность решения

7–3 Вложение

• Краткое определение проблемы

Определите, правильно ли вложена данная строка скобок (один тип).

• Ссылка

• Решение

• Производительность и правильность решения

7–4 Стоунволл

• Краткое определение проблемы

Накройте «Горизонт Манхэттена», используя минимальное количество прямоугольников.

• Ссылка

• Решение

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

• Производительность и правильность решения

Урок 8 Лидер

8–1 Доминатор

• Краткое определение проблемы

Найдите такой индекс массива, что его значение встречается более чем в половине индексов массива.

• Ссылка

• Решение

• Производительность и правильность решения

8–2 ЭквиЛидер

• Краткое определение проблемы

Найдите индекс S такой, что лидеры последовательностей A[0], A[1], …, A[S] и A[S + 1], A[S + 2], …, A[N — 1] такие же.

• Ссылка

• Плохое решение

• Производительность и правильность плохого решения

Урок 9 Задача о максимальном срезе

9–1 Макс. прибыль

• Краткое определение проблемы

Учитывая журнал цен на акции, рассчитайте максимально возможный доход.

• Ссылка

• Плохое решение

• Производительность и правильность плохого решения

• Хорошее решение

Вычислить локальный минимум и глобальный максимум при обходе списка.

• Производительность и правильность хорошего решения

9–2 MaxSliceSum

• Краткое определение проблемы

Найдите максимальную сумму компактной подпоследовательности элементов массива.

• Ссылка

• Плохое решение

• Производительность и правильность плохого решения

• Хорошее решение

Мы можем решить, включает ли локальное общее значение предыдущее значение или нет.

• Производительность и правильность хорошего решения

9–3 MaxDoubleSliceSum

• Краткое определение проблемы

Найдите максимальную сумму любого двойного среза.

• Ссылка

• Хорошее решение

1. Сохраните общее значение для левой и правой сторон в двух массивах.
2. Вычислите максимальное значение общей суммы.

• Производительность и правильность хорошего решения

• Ссылки

1. [Алгоритмы] MaxDoubleSliceSum

Урок 10 Простые и составные числа

10–1 CountFactors

• Краткое определение проблемы

Подсчитайте множители заданного числа n.

• Ссылка

• Хорошее решение

Используйте набор для хранения всех факторов.

• Производительность и правильность хорошего решения

10–2 минПериметрПрямоугольник

• Краткое определение проблемы

Найдите минимальный периметр любого прямоугольника, площадь которого равна N.

• Ссылка

• Хорошее решение

• Производительность и правильность хорошего решения

10–3 пика

• Краткое определение проблемы

Разделите массив на максимальное количество блоков одинакового размера, каждый из которых должен содержать такой индекс P, что A[P — 1] ‹ A[P] › A[P + 1].

• Ссылка

• Плохое решение

• Производительность и правильность плохого решения

10–4 флага

• Краткое определение проблемы

Найдите максимальное количество флагов, которые можно установить на горных вершинах.

• Ссылка

• Плохое решение

• Производительность и правильность плохого решения

Резюме

Спасибо за вашего пациента. Я Шон. Я работаю инженером-программистом.

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

Похлопайте, если эта статья поможет вам. Спасибо.

Другие темы

Вы также можете подписаться на мою страницу в Facebook.

похожие темы

Как использовать двустороннюю привязку в Knout.js и ReactJS?

Узнайте, как использовать SignalR для создания приложения для чата

Мое отражение «Эффективного SQL»:

Службы APM и ведения журналов:

ИТ и сеть:

База данных:

Тестирование программного обеспечения:

Отладка:

DevOps: