Задание 1 Отличное
Решение:
Это классическая простая задача для использования хеш-набора или другой структуры данных, которая позволяет быстро добавлять и находить значения. Никаких уловок нет.
В C ++ это выглядит так:
int count_distinct(vector<int> &v) {
return std::unordered_set<int>(v.begin(), v.end()).size();
}
Задача 2 MaxProductOfThree
Решение:
Здесь нам не нужно сортировать массив или делать что-то сложное. Нам просто нужно просканировать данный массив, чтобы найти 3 наибольших числа (неважно положительные или отрицательные) и два наименьших отрицательных числа. Затем мы сравниваем, какой продукт больше - произведение трех наибольших чисел или произведение наибольшего числа и двух наименьших отрицательных чисел.
Как вы помните, результат умножения двух отрицательных чисел положительный, а результат умножения отрицательных и положительных чисел отрицательный. Значит должно быть как минимум два отрицательных множителя для увеличения произведения. Единственный отрицательный множитель уменьшит результат умножения. Но если у нас тоже самое большое отрицательное число, это меньше всего повлияет на результат.
Я использовал здесь 3 переменные вместо очереди, потому что она короче и выглядит более очевидной. В случае, если вам нужно будет найти произведение, состоящее из более чем трех чисел, удобнее будет использовать std :: deque.
Мы начинаем поиск наименьших отрицательных чисел с нуля и переходим к меньшим числам, но мы начинаем поиск наибольших чисел с -1000 и переходим к большим числам, потому что наибольшее число также может быть отрицательным.
В C ++ это выглядит так:
int max_product_of_three(vector<int> &v) {
vector<int> max_num(3,-1000);
vector<int> min_neg(2,0);
const int v_size = v.size();
for (auto i = 0; i < v_size; ++i) {
if (v[i] < min_neg[0] ) {
min_neg[1]=min_neg[0];
min_neg[0]=v[i];
}
else if (v[i] < min_neg[1]) {
min_neg[1]=v[i];
}
if (v[i] > max_num[0]) {
max_num[2]=max_num[1];
max_num[1]=max_num[0];
max_num[0]=v[i];
}
else if (v[i] > max_num[1]) {
max_num[2]=max_num[1];
max_num[1]=v[i];
}
else if (v[i] > max_num[2]) {
max_num[2]=v[i];
}
}
auto res_neg = max_num[0] * min_neg[0] * min_neg[1];
auto res_pos = max_num[0] * max_num[1] * max_num[2];
return max (res_pos, res_neg);
}
Задание 3 NumberOfDiscIntersections
Решение:
Вообще в этой задаче лучше думать не о дисках, а о отрезках на оси координат.
Поскольку эта задача находится в уроке о сортировке, классический алгоритм этого решения должен выглядеть так:
1. Создайте массив пар, каждая пара содержит начальный и конечный индексы диска. Другими словами, массив состоит из сегментов, покрывающих диаметры дисков.
2. Отсортируйте массив по первой записи каждой пары: индексам начала диска. Другими словами, отсортируйте массив по первым точкам отрезков, охватывающих диаметры дисков.
3. Подсчитайте количество пересечений на «активном» участке. Для этого обхода по массиву, начиная с крайнего левого интервала (то есть с наименьшего i-A [i]). Для текущего сегмента выполните двоичный поиск, чтобы увидеть, куда пойдет правая конечная точка сегмента (т.е. i + A [i]). Теперь вы знаете, что он пересекает все элементы слева.
Увеличьте счетчик с правой конечной точкой текущего сегмента и вычтите текущую позицию, так как мы не хотим дублировать интервалы и самопересечения.
Сложность O (NlogN) раз, O (N) пробела.
Решение на C ++ выглядит так:
Но есть намного лучшее, короче и понятное решение со сложностью Log (N)
1. Создайте массив пар, как в предыдущем решении.
2. Затем пройдите мимо массива и подсчитайте сегменты, которые содержат текущую точку «i» на оси.
Каждый раз, когда новый сегмент начинается в позиции «i», он пересекается со всеми существующими сегментами (дисками) в этом месте. Вот почему у нас есть часть «active * start [i]» в формуле. Нам также необходимо добавить количество пересечений для всех сегментов, которые только что начались в местоположении «i», т. Е. Количество пересечений внутри самих себя, за исключением того, что уже существует »(start [i] * (start [i] - 1)) / 2 ”. Например, если началось 5 сегментов (дисков) в одной точке, она увеличится на 1 + 2 + 3 + 4 пересечения, или 5 * (5–1) / 2.
Решение на C ++ выглядит так:
Задание 4 Треугольник
Решение:
Данный массив содержит отрезки длины. Вопрос в том, чтобы найти отрезки такой длины, чтобы из них можно было построить треугольник. По определению из описания задачи стороны треугольника всегда P ‹Q‹ R.
В этой задаче, кажется, нет простого решения без сортировки. Таким образом, если мы отсортируем данный массив, будет легко найти все сегменты, которые могут построить треугольник. После сортировки массива A [R] всегда больше, чем A [Q] и A [P], поэтому A [Q] + A [R] ›A [P] и A [R] + A [P]› A [ Q] всегда истинны, поэтому нам нужно проверить только A [P] + A [Q] ›A [R].
По определению задачи элементы массива могут быть достаточно большими, чтобы переполнять переменную int во время добавления. Чтобы избежать этой проблемы, мы можем сравнить A [P] ›A [R] - A [Q] вместо A [P] + A [Q]› A [R]
Таким образом, решение на C ++ выглядит так:
int find_triangle(vector<int> &v) {
const int v_size = v.size();
if(v_size < 3) { return 0; }
std::sort(v.begin(), v.end());
for (auto i = 2; i < v_size; ++i) {
if (v[i - 2] > v[i] - v[i - 1]) {
return 1;
}
}
return 0;
}
Вернитесь к оглавлению.
