Я уже писал одну или две статьи об алгоритмических трюках.
Краткое изложение некоторых часто используемых алгоритмических навыков
[Навыки алгоритма] Руководство по загрузке битовых операций
Сегодняшняя статья является дополнением, в то же время в ней будут перечислены некоторые распространенные алгоритмические проблемы, как использовать эти методы для их решения, и с помощью этих методов можно упростить некоторые алгоритмические задачи.
1. Используйте n & (n - 1), чтобы удалить последнюю 1 из n
В двоичном представлении n, если мы делаем
n = n & (n - 1)
Затем вы можете исключить 1 слева и справа от n, например
n = 1001
n - 1 = 1000
n = n & (n - 1) = (1001) & (1000) = 1000
Какая польза от этой формулы?
На самом деле, есть еще много применений, и вы часто будете сталкиваться с ними при составлении вопросов.Ниже я перечислю несколько классических и часто проверяемых примеров вопросов.
(1), определить, является ли натуральное число n степенью числа 2
Если число является степенью двойки, это означает, что в двоичном представлении n только один бит равен 1, а остальные равны 0. привожу пример вроде
2^0 = 0.....0001
2^1 = 0.....0010
2^2 = 0....0100
2^3 = 0..01000
.....
Итак, нам нужно только судить, есть ли только одна 1 в двоичном представлении в N. В соответствии с обычной практикой мы можем сдвинуть n и затем оценить, сколько единиц в двоичном представлении n. Итак, сделайте следующее
boolean judege(int n) {
int count = 0;
int k = 1;
while (k != 0) {
if ((n & k) != 0) {
count++;
}
k = k << 1;
}
return count == 1;
}
Но если вы используете n & (n - 1), вы можете напрямую исключить 1 из n, а затем определить, равно ли n 0. Код выглядит следующим образом:
boolean judege(int n){
return n & (n - 1) == 0;//
}
И временная сложность этого метода составляет O (1).
(2), число 1 в целом n двоичном
Для такого рода задач мы можем непрерывно выполнять n & (n - 1) и каждый раз удалять 1. Когда n равно 0, мы можем подсчитать, сколько раз он был выполнен в целом. составляет:
public int NumberOf12(int n) {
int count = 0;
int k = 1;
while (n != 0) {
count++;
n = (n - 1) & n;
}
return count;
(3) Сколько двоичных разрядов нужно изменить, чтобы преобразовать целое число n в m?
По сути, этот вопрос почти такой же, как вопрос (2), нам нужно только вычислить, сколько двоичных разрядов двух чисел n и m различаются, тогда мы можем сначала сделать n и m XOR, а затем достаточно для вычисления количества единиц в результате, полученном XOR. Например
Пусть t = n & m
Затем просто подсчитайте, сколько единиц в битах t, и проблема может быть преобразована в задачу (2).
2, применение двойного указателя
В предыдущей статье я также говорил о двойных указателях, здесь я расскажу об этом и, кстати, добавлю несколько примеров.
(1) Приложение в связанном списке
Я думаю, что для двойных указателей наиболее правильно использоватьсвязанный списокВот, например, "судить, есть ли кольцо в односвязном списке", "как найти узел в середине связного списка за один обход", "последний k-й узел в односвязном списке" и т.д. на. Для такого рода задач мы можем использовать двойные указатели, что будет намного удобнее. Кстати, позвольте мне объяснить, как решить эти три проблемы с помощью двойных указателей.
Например, на первый вопрос
Мы можем установить медленный указатель и быстрый указатель для обхода связанного списка. Медленный указатель перемещает по одному узлу за раз, а быстрый указатель перемещает по два узла за раз.Если в связанном списке нет кольца, быстрый указатель будет проходить по списку первым.Если есть кольцо, быстрый указатель будет встречаем медленный указатель во втором обходе. .
на второй вопрос
То же самое для установки быстрого указателя и медленного указателя. Медленный перемещается по одному узлу за раз, а быстрый — по два. При обходе связанного списка, когда обход быстрого указателя завершен, медленный указатель просто достигает средней точки.
на третий вопрос
Установите два указателя, один из которых сначала перемещает k узлов. Затем обе руки двигаются с одинаковой скоростью. Когда обход первого перемещенного указателя завершен, второй указатель находится точно в k-м узле снизу.
Некоторые люди могут сказать, что временная сложность использования двух указателей остается прежней. Да, пространственная сложность и временная сложность не изменятся, однако я думаю, что использование двойных указателей проще для понимания и менее подвержено ошибкам.
(2), применение обхода массива
Также очень полезно использовать указатели "голова" и "хвост" для обхода массива, особенно при задании вопросов.Например, позвольте мне привести пример:
Описание темы: УчитываяаккуратныйМассив целых чисел и целевое значение. Найдите в массиве два числа, сумма которых равна целевому значению. Вы можете предположить, что каждый ввод соответствует только одному ответу и что одни и те же элементы нельзя использовать повторно.
示例：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
На самом деле этот вопрос тоже сумма двух чисел в leetcode, но я тут сделал доработку. Один из способов сделать это:
Проходим по массиву слева направо, при обходе берем элемент а, а из суммы вычитаем а, так что получается b, то есть b = сумма - а. Затем, поскольку массив упорядочен, мы используем двоичный поиск для запроса нижнего индекса b в массиве.
В этом процессе временная сложность бинарного поиска составляет O(logn), а обход сканирования слева направо — O(n), поэтому временная сложность этого метода равна O(nlogn).
Однако мы используемдвойной указательЕсли делать это из головы и хвоста массива в середину метода, временная сложность должна быть только O(n), и код будет более лаконичным, здесь я привожу код, код выглядит следующим образом :
public int[] twoSum1(int[] nums, int target) {
int[] res = new int[2];
int start = 0;
int end = nums.length - 1;
while(end > start){
if(nums[start] + nums[end] > target){
end--;
}else if(nums[start] + nums[end] < target){
start ++;
}else{
res[0] = start;
res[1] = end;
return res;
}
}
return res;
}
Этот пример относительно прост, но этот метод двойных указателей в начале и в конце действительно используется очень часто.
3. Применение a^b^b=a
Результатом операции XOR двух одинаковых чисел является 0, а результатом операции XOR любого числа с 0 является само собой.С помощью этой функции также можно решить массу задач.Я встречал несколько в leetcode.Несколько примеров.
(1) В массиве только одно число встречается один раз, а остальные встречаются дважды, найдите число, которое встречается один раз
Многие люди могут использовать хеш-таблицу для хранения этого вопроса.Каждый раз, когда он сохраняется, записывается количество вхождений определенного числа, и, наконец, хеш-таблица просматривается, чтобы увидеть, какое число встречается только один раз. Временная сложность этого метода составляет O(n), а пространственная сложность также равна O(n).
Как мы только что сказали, результатом операции XOR двух одинаковых чисел является 0, а результатом операции XOR числа и 0 является он сам, поэтому мы выполняем операцию XOR всей этой группы целых чисел, например, эта группа данных: 1 , 2, 3, 4, 5, 1, 2, 3, 4. 5 из них появляются только один раз, остальные появляются дважды, XOR их всех, и результат следующий:
Так как XOR поддерживает коммутативные и ассоциативные законы, то:
1^2^3^4^5^1^2^3^4 = (1^1)^(2^2)^(3^3)^(4^4)^5=0^0^0^ 0^5 = 5.
С помощью этого метода пространственная сложность может быть уменьшена до O (1), в то время как временная сложность остается неизменной, а соответствующий Demi выглядит следующим образом.
int find(int[] arr){
int tmp = arr[0];
for(int i = 1;i < arr.length; i++){
tmp = tmp ^ arr[i];
}
return tmp;
}
Суммировать
Я был занят обзором некоторое время, поэтому я не нашел слишком много примеров.Некоторые из вышеперечисленных вопросов были написаны в предыдущих статьях.Вот, я могу рассмотреть некоторые для тех, кто это читал, а также принять во внимание Может быть много людей, которые его не видели.
Итак, я надеюсь, что после прочтения этой статьи, если вы столкнетесь с некоторыми проблемами в будущем, у вас может появиться больше идей.Если вы сможете использовать эти навыки, это определенно значительно уменьшит сложность проблемы.
Если вы считаете, что этот контент вас очень вдохновляет, чтобы больше людей увидели эту статью:
1,подобно, чтобы больше людей могли увидеть этот контент
2. Подпишитесь на официальный аккаунт »трудолюбивый кодер», в основном пишу статьи по алгоритмам и основам работы с компьютером, и в нем более 100 оригинальных статей