Задание 1 ПермПроверка
Решение:
Это хорошее задание для собеседования. У него есть несколько очевидных простых решений, но все они имеют более-менее плохую сложность, есть пара очень элегантных, но неправильных решений, так что у нас есть широкое поле для экспериментов и улучшений.
Наиболее очевидным решением этой задачи является сортировка массива и проверка на наличие в нем недостающих элементов. Но сложность этого решения равна сложности бинарной сортировки, то есть O(N * LogN). Он выглядит слишком большим для такой простой задачи.
Мы можем улучшить решение и использовать дополнительный индекс, где мы будем отмечать все найденные элементы массива, а затем проверять отметки, чтобы определить, являются ли элементы последовательностью или нет. Например, мы знаем, что диапазон элементов равен [1..1 000 000 000], но мы можем игнорировать его, потому что если у нас есть последовательность в массиве, диапазон элементов не может превышать [1..100 000], поэтому мы определяем бит установить с размером [1..100,000] и установить в true все биты этого набора, проиндексированные значениями массива. Затем проверьте, все ли элементы битового массива верны, у нас есть последовательность в данном массиве. Конечно, если мы встречаем в данном массиве значение больше 100 000, это означает, что это тоже не последовательность. См. пример кода C++ в следующем задании FrogRiverOne
Есть несколько элегантных, но неправильных решений. Один основан на том, что мы можем вычислить сумму всех элементов последовательности по формуле (размер * (1 + размер)) / 2, где размер — размер последовательность. Затем мы считаем реальную сумму элементов и, если она равна расчетной, это последовательность. К сожалению, можно создать массив элементов, который не является последовательностью, но имеет ту же сумму, что и последовательность. Например, 1,2,3 — это последовательность с суммой 6, а 1,1,4 — не последовательность с той же суммой.
На сайте Codility есть блестящее решение этой задачи, прошедшее все тесты. Но это неправильно. Он основан на битовой магии. Фактически это своего рода решение задачи 1 OddOccurrencesInArray урока 2, но в данном случае мы будем генерировать пары для каждого числа данного массива. Затем применяем решение из OddOccurrencesInArray к массиву наших пар и проверяем, есть ли у каждого числа своя пара. Если да, это означает, что данные массивы являются перестановкой последовательности. Нам даже не нужно сохранять наши сгенерированные пары. Мы можем использовать счетчик цикла i.
В С++ это выглядит так:
bool is_permutation(vector<int> &v) {
unsigned xorsum = 0;
int v_size = v.size();
for (size_t i = 0; i < v_size; i++) {
xorsum = (i + 1) ^ static_cast<unsigned>(v[i]) ^ xorsum;
}
return xorsum == 0;
}
Для входного массива [1,2,3] у нас будут следующие итерации:
xorsum: 0 ^ (i + 1): 1 ^ v[i]: 1 = 0
xorsum: 0 ^ (i + 1): 2 ^ v[i]: 2 = 0
xorsum: 0 ^ (i + 1): 3 ^ v[i]: 3 = 0
xorsum == 0 - это перестановка
Для входного массива [3,2,1] у нас будут следующие итерации:
xorsum: 0 ^ (я + 1): 1 ^ v [я]: 3 = 2
xorsum: 2 ^ (i + 1): 2 ^ v[i]: 2 = 2
xorsum: 2 ^ (i + 1): 3 ^ v[i]: 1 = 0
xorsum == 0 - это перестановка
Для входного массива [1,2,4] у нас будут следующие итерации:
xorsum: 0 ^ (i + 1): 1 ^ v[i]: 1 = 0
xorsum: 0 ^ (i + 1): 2 ^ v[i]: 2 = 0
xorsum: 0 ^ (i + 1): 3 ^ v[i]: 4 = 7
xorsum == 7 НЕ перестановка
Подробное описание работы этой битовой магии смотрите в решении для OddOccurrencesInArray в уроке 2.
Я был очень взволнован, когда нашел его, но он рассматривает такие массивы, как 1,2,5,2, как последовательность.
Я уже отправил отчет об ошибке в Codility, надеюсь, они исправят его. Но я предполагаю, что если он прошел все тесты, они знают об этом решении и считают его правильным. :)
Реально работающее решение выглядит не столь элегантно и основано на идее индексов, описанной выше. Но мы можем не тратить дополнительную память на индекс, а использовать входной массив для сохранения индексов. Мы будем использовать тот факт, что у нас в массиве только положительные числа, а в качестве индексов будем использовать отрицательные числа. Конечно, исходные данные в массиве будут потеряны, но мы можем добавить небольшой фрагмент кода, который будет восстанавливать исходные данные после использования индекса. Этот алгоритм работает для последовательностей, которые начинаются с любого числа, но задача от Codility требует начинать с 1, поэтому мы должны добавить проверку и вернуть false, если неправильно пройти тесты.
#include <algorithm>
int solution(vector<int> &v) {
int v_size = v.size();
// Find minimum and maximum elements of the array
auto min_max = std::minmax_element(v.begin(), v.end());
int min_element = *min_max.first;
// Check to pass Codility tests
if(min_element != 1) {
return false;
}
int max_element = *min_max.second;
//if this is a sequence then max-min+1 elements must be equal
// to number of given elements
if ( (max_element - min_element + 1) != v_size) {
return false;
}
// pass through the whole array
for (int i = 0; i < v_size; ++i) {
int j; // auxiliary index
if (v[i] < 0) {
j = -v[i] - min_element;
}
else {
j = v[i] - min_element;
}
if (v[j] > 0) {
v[j] = -v[j];
}
else {
// if the value at index j is negative then it is repeated
return false;
}
}
// If we didn't meet a negative element then this is a sequence
return true;
}
Задание 2 FrogRiverOne
Решение:
На самом деле нам нужно проверить, содержит ли данный массив переставленную последовательность элементов от 1 до X. Элементы могут повторяться. Лучший способ здесь — использовать битовый массив для индексации данного массива, как это описано в предыдущем решении, а затем проверить, является ли данный массив последовательностью.
В С++ это выглядит так:
int solution(int x, vector<int> & v) {
auto v_size = v.size();
vector<bool> bitmap(v_size+1, false);
if (v_size >= x) {
auto total = x;
for (int i = 0; i < v_size; i++) {
if (!bitmap[v[i]]) {
bitmap[v[i]] = true; total--;
if (total == 0) { return i; }
}
}
}
return -1;
}
Задание 3 МаксСчетчики
Решение:
В этой задаче нет никаких хитростей. Нам просто нужно составить массив счетчиков, увеличить их по заданному алгоритму и распечатать. Скучная задача.
Код С++ выглядит так:
vector<int> max_counters(int n, vector<int> &v) {
int max_current_counter = 0;
int max_global_counter = 0;
// index of the current counter in the counters array
int counter_index;
vector<int> counters(n, 0);
int v_size = v.size();
for(int i = 0; i < v_size; ++i) {
counter_index = v[i] - 1;
if(v[i] <= n && v[i] >= 1) {
counters[counter_index] =
max(max_global_counter, counters[counter_index]) + 1;
max_current_counter =
max(max_current_counter, counters[counter_index]);
}
else if(v[i] == n + 1) {
max_global_counter = max_current_counter;
}
}
int counters_size = counters.size();
for(int i = 0; i < counters_size; ++i) {
counters[i] = max(counters[i], max_global_counter);
}
return counters;
}
Задача 4 Пропущенное целое
Решение:
Еще одно скучное задание. Мы будем использовать тот же подход с битовым массивом для индексации данного массива. Затем мы проверяем наши индексы и возвращаем первый, который не был помечен. Это недостающий элемент.
int miss_int(vector<int> &v) {
int v_size = v.size();
vector<bool> present(v_size+1, false);
for (int i = 0; i < v_size; ++i) {
if ( (v[i] > 0) && (v[i] <= v_size) ) {
present[v[i]] = true;
}
}
// Find the first element which is not
// appeared in the given array
for (int i = 1; i <= v_size; ++i) {
if (!present[i]) { return i; }
}
// If the given array is a sequence like [1, 2, 3]
return v_size + 1;
}
Вернитесь к оглавлению.
