Ряд вопросов по техническому программированию, с которыми я столкнулся. Это исходит от HackerRank.
Проблема
Вам будет предоставлено строковое представление числа и максимальное количество изменений, которые вы можете внести. Измените строку, по одной цифре за раз, чтобы создать строковое представление как можно большего числа с учетом ограничения на количество изменений. Длина строки не может быть изменена, поэтому вы должны учитывать 0 слева от всех старших цифр в ваших тестах. Например, 0011 правильно, 0011 нет.
Учитывая строку, представляющую начальный номер и максимальное количество разрешенных изменений, создайте самую большую возможную палиндромную строку цифр или строку -1, если невозможно создать палиндром в соответствии с ограничениями.
s: a string representation of an integer; n: an integer that represents the length of the integer string; k: an integer that represents the maximum number of changes allowed Input Format
Ограничения
0 <= n <= 10⁵ 0 <= k <= 10⁵
Пример:
Вход:
4 1
3943Вывод:
3993Дальнейшие тестовые примеры:
s, n, k
("3943", 4, 1); //3993
("092282", 6, 3); //992299
("0011", 4, 1); //-1
("10011", 5, 1); //11011
("10011", 5, 3); //91019
("1111911", 7, 4); //9199919
("329", 3, 2); //999
("932239", 6, 2); //992299
("11119111", 8, 4); //91199119
("11117111", 8, 3); //91177119
("11117111", 8, 3); //91177119
("9711319", 7, 4); //9991999
("1111111", 7, 4); //9911199
("128392759430124", 15, 8); //929394959493929Решение
Первое, что нужно учитывать, - это свойства палиндрома. Палиндром - это любое представление текста; буквы, цифры или их комбинация, при чтении вперед или назад получается одна и та же строка. Написание функции для определения того, является ли строка палиндромом, определенно поможет нам немного лучше понять эту проблему.
Палиндром имеет такие свойства, что при прямом или обратном чтении получается одна и та же строка. Учитывая это, можно утверждать, что с функцией, если мы сравним первую и последнюю позиции строки, они должны быть одинаковыми. Потом второй и предпоследний и так далее. Для некоторого массива a размера n от x до n-1,
x, x +1, x + 2…. m = n - n ,…, n -3, n -2, n -1, где m = n
Учитывая это, мы можем написать
static boolean isPalindrome(String s){
int i = 0;
int j = s.length()-1;
while(j > i){
if (s.charAt(i) == s.charAt(j)){
i++; j--;
} else {
return false;
}
}
return true;
}
Это также относится к случаям нечетной и четной длины.
С учетом перечисленных выше свойств строка s будет иметь ряд различий по своим индексам. Нам нужно определить количество различий, которые присутствуют в строке, например, для строки 3943 есть одно различие, средние значения 9 и 4. Если количество различий превышает количество доступные изменения, k, то строка не может быть исправлена, и мы возвращаем -1.
Это один из первых наших крайних случаев. При написании функций / методов мы всегда должны учитывать, какие условия сделают наш алгоритм нефункциональным и каким должно быть возвращаемое значение.
Если мы следуем той же схеме проверки, является ли строка палиндромом, нам нужно сравнить конечные индексы.
Теперь у нас есть два соображения:
Что делать, если индексы равны?
Что делать, если показатели не равны?
Равно
Если индексы равны, например, в случае 3943, индексы 0 и 3 равны. нам нужно проверить, есть ли у нас какие-либо доступные изменения. Если у нас осталось более k = 2 изменений, мы можем изменить эти значения на максимальное значение, 9. Помните, мы пытаемся найти палиндром наивысшего возможного значения. Кроме того, мы должны гарантировать, что вычитание 2 изменений, необходимых для переключения значений на 9, не оставит нам меньше изменений, чем оставшихся различий.
Это важно, потому что, если мы потратим изменения на два уже равных индекса, тогда другие неравные индексы потеряют возможность изменения.
Мы также не хотим тратить время на внесение изменений, если значение индекса уже равно 9.
Если мы выполняем эти условия, мы меняем значения индекса на 9 и вычитаем 2 из k. Мы не вычитаем из переменной разницы, так как здесь не было никакой разницы.
Не равно
Если значения не равны, мы, конечно, можем изменить их, если у нас есть изменения, k,.
Дело 1:
Если у нас доступно более двух изменений, и использование этих изменений не приведет к тому, что доступные изменения опустятся ниже sizes-1, примените изменение. Мы уменьшили разницу, потому что мы только что устранили разницу.
Применение изменения включает замену значения на 9, , если значение еще не равно 9.
Случай 2:
Если у нас не более двух доступных изменений, то мы меняем индекс с наименьшим значением на более высокое. Затем мы уменьшаем количество доступных изменений.
Последнее рассмотрение
Помните, что строка может иметь нечетную длину, в этом случае индексы сходятся в середине. С палиндромом это нормально, так как среднее значение может быть любым. Однако мы пытаемся создать палиндром максимальной ценности. Поэтому, если у нас остались изменения, мы используем это и меняем среднее значение на 9.
Специальное примечание. Вы можете перебирать строку, используя цикл while с переменными lo и hi, проверяя наличие их сходимость, или вы можете использовать цикл for, ограничив его n / 2 (нам нужно выполнить итерацию только на половину длины).
Алгоритм
static String highestValuePalindrome(String s, int n, int k) {
int lo = 0;
int hi = n-1;;
char[] string = s.toCharArray();
int diff = 0;
for(int i=0, j=n-1; i<n/2; i++, j--){
if (string[i] != string[j]){
diff++;
}
}
if (diff > k){
return "-1";
}
while(hi >= lo){
if (k <= 0){
break;
}
if (string[lo] == string[hi]){
if (k > 1 && (k-2) >= diff && string[lo] != '9'){
string[lo] = '9';
string[hi] = '9';
k-=2;
}
}
else {
if (k > 1 && (k-2) >= diff-1){
if (string[lo] != '9'){
string[lo] = '9';
k--;
}
if (string[hi] != '9'){
string[hi] = '9';
k--;
}
} else {
if (string[lo] > string[hi]){
string[hi] = string[lo];
} else {
string[lo] = string[hi];
}
k--;
}
diff--;
}
if (lo == hi && k > 0){
string[lo] = '9';
k--;
}
lo++;
hi--;
}
s = String.valueOf(string);
return isPalindrome(s) ? s : "-1";
}
