предисловие
Цинмин случайно задержали на два дня без обновлений~~
Это второй из десяти вопросов алгоритма.～Предыдущий обзор:Десять простых арифметических вопросов
Недавно я просматривал структуры данных и алгоритмы, написанные ранее на C, и обнаружил, что мои алгоритмы и структуры данных очень слабые, теперь переписываю их на Java и пересматриваю.
Можно только сказать, что он накапливается медленно ~ сложность следующих тем проста, старший брат алгоритма может напрямую игнорировать эту статью ~ студенты, которые являются новичками или слабы в алгоритме, могут ссылаться на нее ~
Многие мелкие алгоритмы, связанные с сортировкой (объединение массивов, получение суммы каждого значения числа), я не записал, потому что пока вы умеете сортировать слиянием (объединять массивы), вы будете знать сортировку ведра (получать значение каждый бит числа), это больше не проблема. Если вы не знакомы с восемью основными сортирующими учениками, вы можете прочитать: [Резюме восьми основных рейтингов】
Из-за нехватки места давайте напишем по десять глав~
Если есть неправильное место или есть лучшая реализация, более подходящий способ понимания, я надеюсь, что вы оставите сообщение в области комментариев ~ Давайте общаться больше
Десять простых арифметических вопросов
Обзор тем
- удалить элемент с индексом k
- найти общие числа
- пропущенные номера
- поставить 0 в конце массива
- Найти одно число в массиве
- рисуем треугольные звезды
- Римские цифры перевернуты арабскими цифрами
- Пиво и напитки
- простой шифр Цезаря
- найти наибольший общий делитель
1. Удалить элемент с индексом k
удалить элемент с индексом k
Идеи:Последний бит массива может быть перезаписан вперед~
/**
* 删除下标为k的元素
*/
public static void deleteK() {
//固定的常量(比数组元素的个数要大)
int N = 10;
int[] arrays = new int[N];
//对数组进行初始化
for (int i = 0; i < 8; i++) {
arrays[i] = i;
}
//要删除下标
int k = 7;
for (int i = k; i < N - 1; i++) {
arrays[i] = arrays[i + 1];
}
System.out.println("公众号：Java3y" + arrays);
}
2. Найдите общие числа
дает вам массив длины n,Одно из чисел встречается не менее n/2 раз, найдите число
Этот вопрос можно использоватьстопка идейсделать:
- Если стек пуст, сначала сохраните данные
- Затем продолжайте просматривать другие данные, просто найдите данные в стеке и данные в обходе.Разные, тогдапоп
- еслитакой жеда, тогдаположить в стек
- На самом деле, чтобы начать здесь, нужно поймать количество вхождений числа, превышающее половину длины массива.Если количество вхождений этого числа больше 2/1 длины массива, то это число нужно оставить в конце
/**
* 找出常用的数字：
* 给你一个长度为n的数组，其中有一个数字出现的次数至少为n/2，找出这个数字
*/
public static void findMajorityElement(int[] arrays) {
//构建一个静态栈
int[] stack = new int[arrays.length];
// 栈的front指针
int front = -1;
// 遍历给出的数组
for (int i = 0; i < arrays.length; i++) {
// 判断该栈为空，那么直接将元素入栈
if (front == -1) {
stack[++front] = arrays[i];
} else if (stack[front] == arrays[i]) { // 该元素是否与栈的元素一致-->继续入栈
stack[++front] = arrays[i];
} else {
// 只要不一致，就出栈
front--;
}
}
// 只要该数字出现次数大于数组长度的2/1，那么留下来的数字肯定在栈顶中
System.out.println("关注公众号：Java3y--->" + stack[0]);
}
оптимизация:
- На самом деле нет необходимости использовать весь стек для загрузки массива, потому что мы простоИспользуйте верхний элемент стека (тот, у которого больше всего вхождений), а размер стека также можно определить с помощью переменной
- до тех пор, пока элементто же -> нажать (длина + 1). элементНе то же самое --> поп (длина-1)
- В конце нужно оставить номер, который встречается чаще всего!
public static void findMajorityElement2(int[] arrays) {
// 装载栈的元素
int candidate = -1;
// 栈的大小(长度)
int count = 0;
// 遍历给出的数组
for (int i = 0; i < arrays.length; i++) {
// 判断该栈为空，那么直接将元素入栈
if (count == 0) {
candidate = arrays[i];
count++;
} else if (candidate == arrays[i]) { // 该元素是否与栈的元素一致-->入栈(栈多一个元素)
count++;
} else {
// 只要不一致-->出栈(栈少一个元素)
count--;
}
}
// 只要该数字出现次数大于数组长度的2/1，那么留下来的数字肯定在栈顶中
System.out.println("关注公众号：Java3y--->" + candidate);
}
3. Пропущенные номера
Вам дан массив {0,1,2,3,....n}, один из которых отсутствует, найдите недостающее число
Идеи:
- Создайте массив (длина массива вопросов + 1, потому что в массиве вопросов отсутствует один)
- Создаваемые элементы массива заполняются специальными символами (цифрами)
- Пройдите и заполните массив, указанный в заголовке созданного массива, замените его индексом (0,1,2,3..)
- Наконец, переберите созданный массив,Какой или специальный символ является недостающим числом, возвращаемый индекс (отсутствует число)
/**
* 找到缺失的数字
*
* @param arrays
*/
public static void missingNumber(int[] arrays) {
// 定义要填充到新数组的数字(随意)
int randomNumber = 89898980;
// 创建一个新的数组(比已缺失的数组多一个长度)
int[] newArrays = new int[arrays.length + 1];
// 填充特殊的数字进新数组中
for (int i = 0; i < newArrays.length; i++) {
// 随意填充数组到新数组中
newArrays[i] = randomNumber;
}
// 遍历题目的数组并使用index替代掉新数组的元素
for (int i = 0; i < arrays.length; i++) {
// 题目数组的值[0,1,2,3,4,...n]其中有一个缺失
int index = arrays[i];
// 重新填充到新数组上，index对应着题目数组的值
newArrays[index] = 3333333;
}
// 遍历新数组，只要还有值为89898980，那么那个就是缺失的数字
for (int i = 0; i < newArrays.length; i++) {
if (newArrays[i] == randomNumber) {
System.out.println("关注公众号：Java3y---->缺失的数字是：" + i);
}
}
}
результат:
оптимизация:
- массив, заданный заголовком
{0,1,2,3,4,5,....n}Одного из чисел не хватает, чтобы найти недостающее число... мы можемВспомните формулу арифметической суммы, которую вы выучили в старшей школе:Sn=(a1+an)n/2 - Предполагая, что у нас нет пропущенных чисел, формула арифметической суммы дает быстрый ответ. Например:
{0,1,2,3}--->(0+3)*4/2--->6, если в это время отсутствует 2, это означает, что данный массив заголовка:{0,1,3}, мы используем арифметическую формулу для суммирования и вычитания каждого элемента массива, и последнее оставшееся число — это пропущенное число!6-1-3-0--->2
Итак, мы можем написать такой код:
/**
* 利用等差公式找到缺失的数字
*
* @param arrays
*/
public static void missingNumber2(int[] arrays) {
// 套用等差求和公式
int sum = (arrays[0] + arrays[arrays.length - 1]) * (arrays.length + 1) / 2;
// 遍历数组，得出的sum减去数组每一位元素，最后即是缺失的数字
for (int value : arrays) {
sum = sum - value;
}
System.out.println("关注公众号：Java3y---->缺失的数字是：" + sum);
}
результат:
В-четвертых, поставьте 0 в конце массива
Поместите элементы массива, равные 0, в конец массива
Идеи:
- Используйте переменную ноль, чтобы запомнить, сколько нулей имеет массив
- Пройтись по массиву, если окажется, что он не равен 0, перейти к началу массива, если окажется, что он равен 0, ноль++
- Позиция, в которую перемещается массив, точно
arr[i-zero]из
Код:
/**
* 移动元素0到数组最后
*
* @param arrays
*/
public static void moveZero(int[] arrays) {
// 记录该数组有多少个0元素
int zero = 0;
for (int i = 0; i < arrays.length; i++) {
// 只要元素不为0，那么就往前面移动
if (arrays[i] != 0) {
arrays[i - zero] = arrays[i];
} else {
// 如果为0，那么zero ++
zero++;
}
}
// 1. 前面已经将非0的元素移动到数组的前面了
// 2. 将为0的元素填满数组，填充的位置就从length - zero开始
int j = arrays.length - zero;
while (j < arrays.length) {
arrays[j] = 0;
j++;
}
System.out.println("关注公众号：Java3y---->" + arrays);
}
результат:
Также можно придумать другой способ (не большая разница): разделить массив на несколько частей:Перед j нет 0, от j до i все 0, и нет обхода после i
- Если пройденочисло не 0, затем следуйтеj обменять, j++ (гарантируйте, что перед j нет 0, а от j до i все 0)
- Пока i не пройдено, фронт j не равен 0, а j-i равен 0 (на этом наша задача завершается)
Код:
/**
* 移动元素0到数组最后
*
* @param arrays
*/
public static void moveZero2(int[] arrays) {
// 在j前面的元素都不是0
int j = 0;
for (int i = 0; i < arrays.length; i++) {
if (arrays[i] != 0) {
// 跟j进行交换，保证j的前面都不是0
int temp = arrays[i];
arrays[i] = arrays[j];
arrays[j] = temp;
j++;
}
}
// 直至i遍历完毕后，j前面都不是0，j-i都是0(这就完成我们的任务了)
System.out.println("关注公众号：Java3y---->" + arrays);
}
Результат все тот же:
5. Найдите одно число в массиве
Вам дан массив, кроме одного числа, все остальные числа встречаются дважды, найдите число, которое встречается только один раз.
Идеи:
- Повторите массив один раз и запишите количество вхождений каждого числа.
- Если количество вхождений числа равно только 1, то число является единственным числом~
/**
* 找出数组的单个数字
* @param nums
* @return
*/
public static void singleNumber(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int count = countNumber(nums, nums[i]);
// 如果该元素只出现一次，那么就是它了！
if (count == 1) {
System.out.println("关注公众号：Java3y--->单一的元素是：" + nums[i]);
return ;
}
}
}
/**
* 找出每个元素出现的次数
* @param nums 数组
* @param value 想知道出现次数的元素
*/
public static int countNumber(int[] nums,int value) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (value == nums[i]) {
count++;
}
}
// 返回该元素出现的次数
return count;
}
результат:
оптимизация:
Эта проблемаоптимальныйРешение заключается в использованиипобитовая операция XOR:
- если
5^5=0 - если
5^7^5 = 7 - если
5^6^6^5^7^8^7 = 8
Как видно из приведенного выше примера: куча чисел делает异或运算^, два одинаковых числа будут аннулированы~, поэтому эта функция идеально подходит для этой темы:
/**
* 找出数组的单个数字
* @param nums
* @param numsSize
* @return
*/
public static int singleNumber(int[] nums, int numsSize) {
// 第一个数和数组后面的数做^运算，留下的必然是单个数字
int k = nums[0];
for (int i = 1; i < numsSize; i++) {
k = (k ^ nums[i]);
}
return k;
}
Шесть, нарисуйте треугольные звезды
рисуем треугольные звезды
Просто хочу нарисовать треугольную звезду выше, как ее нарисовать? ?
Идеи:
- Во-первых, мы можем найти: каждая строкаКоличество звезд (2*количество рядов-1), каждый рядколичество местэтоМаксимальное количество строк минус n-я строка(максимум 4 строки, 4-я строка без пробела, максимум 4 строки, 3-я строка с 1 пробелом)
- С приведенными выше правилами цикл for можно использовать для создания треугольных звезд~
Код реализации:
/**
* 画星星
*/
public static void drawStar() {
// 我要画5行的星星
int row = 5;
for (int i = 1; i <= 5; i++) {
// 空格数等于最大行数 - 当前行数
for (int j = 1; j <= row - i; j++) {
System.out.print(" ");
}
// 星星数等于(当前行数*2-1)
for (int j = 1; j <= i * 2 - 1; j++) {
System.out.print("*");
}
// 每画一行就换一次行
System.out.println();
}
}
результат:
7. Перевернуть римские цифры на арабские.
Римские цифры перевернуты арабскими цифрами
Мы можем увидеть больше римских цифр в английских темах.В основном мы используем арабские цифры.Как преобразовать их в арабские цифры? ? Давайте сначала посмотрим на римские цифры:
пс: источник 360 энциклопедия
На схеме правила достаточно понятны, приведу несколько примеров:
- Если число слева меньше числа справа, вычтите число слева из числа справа.
- Если число слева больше числа справа, прибавьте число справа к числу слева.
Глядя на приведенный выше пример, предполагается, что мы будем преобразовывать римские цифры в арабские вручную, так как же записать их в программе? ? ?
Идея такова:
- Сначала найдите самую большую римскую цифру
- Если число слева меньше числа справа, вычтите число слева из числа справа
- Если число слева больше числа справа, прибавьте число справа к числу слева.
- .....Этот цикл, наконец, получит арабские цифры
Во-первых, давайте определим римские цифры и соответствующие арабские цифры (эквивалентные справочным таблицам).
// 定义罗马数字
char digits[] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
// 罗马数字对应的阿拉伯数字
int values[] = { 1, 5, 10, 50, 100, 500, 1000};
Впоследствии мыВы должны найти текущее максимальное значение римских цифр.Прежде чем найти максимальное значение, вы должны преобразовать римские цифры в арабские цифры.
/**
* 将罗马数字转成阿拉伯数字，实际上就是一个查表的过程
*
* @param roman
* @return
*/
public static int digitsToValues(char roman) {
// 定义罗马数字
char digits[] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
// 罗马数字对应的阿拉伯数字
int values[] = {1, 5, 10, 50, 100, 500, 1000};
for (int i = 0; i < digits.length; i++) {
if (digits[i] == roman) {
return values[i];
}
}
return 0;
}
Вышеупомянутый метод уже может преобразовать римские цифры в арабские, и тогда нам нужно найти максимальное значение
/**
* 找到当前罗马数字最大值的角标
*
* @param digits
* @return
*/
public static int findMaxIndex(String digits, int L, int R) {
// 假设第一个是最大的
int max = digitsToValues(digits.charAt(L));
int maxIndex = L;
for (int i = L; i < R; i++) {
// 将罗马数字转成是阿拉伯数字
int num = digitsToValues(digits.charAt(i));
if (max < num) {
max = num;
maxIndex = i;
}
}
return maxIndex;
}
Найдите максимальное значение текущих римских цифр, что делать? ? ?
- Левый меньше правого, затем правый минус левый.
- Левый больше правого, потом правый прибавляется к левому
- ..../// на самом деле рекурсивный процесс
Итак, мы можем написать следующий код:
/**
* 将罗马数字转成阿拉伯数字
*
* @param romanNumber
* @param L
* @param R
*/
public static int romanToNumber(String romanNumber, int L, int R) {
// 如果只有一个罗马数字，那么可以直接返回了(递归出口)
if (L == R) {
return digitsToValues(romanNumber.charAt(L));
} else if (L > R) { // 如果L和R已经越界了，那么说明没有值了
return 0;
} else {
// 找到当前罗马数字最大值的角标
int maxIndex = findMaxIndex(romanNumber, L, R);
// 得到最大值
int max = digitsToValues(romanNumber.charAt(maxIndex));
// 在最大值左边的，则用最大值减去左边的
int left = romanToNumber(romanNumber, L, maxIndex - 1);
// 在最大值右边的，则用最大值加上右边的
int right = romanToNumber(romanNumber, maxIndex + 1, R);
return max - left + right;
}
}
есть тест:
8. Пиво и напитки
Пиво стоит 2,3 юаня за банку, а напитки — 1,9 юаня за банку. Сяо Мин купил немного пива и напитков и потратил в общей сложности 82,3 юаня. Мы также знаем, что он купилменьше пива, чем пить, посчитайте, пожалуйста, сколько банок пива он купил.
Это вопрос из Кубка Голубого моста, который мы можем решить с помощью перебора:
- Если вы покупаете все пиво по 82,3, вы можете купить до 82,3/2,3 = 35 бутылок.
- Если вы покупаете все напитки по 82,3, вы можете купить до 82,3/1,9 = 43 бутылки.
- как условие контроля
/**
* 啤酒与饮料题目
*/
public static void beerAndDrink() {
// 啤酒
for (int i = 0; i < 36; i++) {
// 饮料
for (int j = 0; j < 44; j++) {
// 钱刚好花光了，并且啤酒比饮料少
if (2.3 * i + j * 1.9 == 82.3 && i < j) {
System.out.println("关注公众号：Java3y--------------->啤酒买了" + i);
}
}
}
}
контрольная работа:
9. Простой шифр Цезаря
простой шифр Цезаря
Что такое шифр Цезаря? Проще говоря:шифруется сдвигом
- Например, A-->B,B-->C,C-->D......
Выше приведен самый простой пароль Цезаря, сдвигает все буквы для достижения шифрования
Давай тоже поиграем~
Двигайтесь влево и двигайтесь вправо:
/**
* 右移
*/
public static int rotateRight(int ch) {
if (ch >= 'A' && ch <= 'Y') {
return ch + 1;
} else if (ch >= 'a' && ch <= 'y') {
return ch + 1;
} else if (ch == 'Z') {
return 'A';
} else if (ch == 'z') {
return 'a';
} else {
return ch;
}
}
/**
* 左移
*/
public static int rotateLeft(int ch) {
if (ch >= 'B' && ch <= 'Z') {
return ch - 1;
} else if (ch >= 'b' && ch <= 'z') {
return ch - 1;
} else if (ch == 'A') {
return 'Z';
} else if (ch == 'a') {
return 'z';
} else {
return ch;
}
}
шифрование:
/**
* 加密
* @param ch
* @param shift
* @return
*/
public static int encode(int ch, int shift) {
// 如果没有移动，则直接返回
if (shift == 0) {
return ch;
} else if (shift > 0) {
// 如果shift移动的是正数，那么就向右移动
for (int i = 0; i < shift; i++) {
ch = rotateRight(ch);
}
return ch;
} else {
// 如果shift移动的是负数，那么就向左移动
for (int i = 0; i < -shift; i++) {
ch = rotateLeft(ch);
}
return ch;
}
}
контрольная работа:
String s = "HELLO WORLD";
char[] ch = new char[s.length()];
for (int i = 0; i < s.length(); i++) {
ch[i] = (char) encode(s.charAt(i), 3);
}
System.out.println("关注公众号：Java3y" + ch);
результат:
10. Найдите наибольший общий делитель
Найдите наибольший общий делитель числа
алгоритм:Это сложение двух чисел до тех пор, пока остаток не будет равен 0. Если остаток не равен 0, используйте делитель и остаток, чтобы найти остаток.
- Если остаток равен 0, то текущий делитель является наибольшим общим делителем
/**
* 求最大公约数
*
* @param num1
* @param num2
*/
public static int gcd(int num1, int num2) {
// 求余数
int r = num1 % num2;
// 如果余数为0，那么除数就是最大公约数
if (r == 0) {
return num2;
} else {
// 否则，则用除数和余数来进行运算
return gcd(num2, r);
}
}
результат:
Суммировать
Правильно, вы правильно прочитали, простой маленький алгоритм также должен быть обобщен!
На самом деле, я думаю, что эти относительно простые алгоритмы имеют "подпрограммы", о которых можно говорить. Если вы знаете их подпрограммы, вы можете легко их придумать. Если вы не знаете их подпрограмм, то вы, вероятно, не будете этого делать (нет идеи).
Накопив некую «рутину», мы можемОпытЧтобы сделать вывод, попробуйте выяснить, как решить задачу алгоритма.
Возьмем очень простой пример:
- Умножение основано на сложении, так как же научиться умножению? **Назад (накопление)** вышло,
9*9Кто никогда не запоминал таблицу умножения? например, видеть2+2+2+2+2, После изучения умножения (рутины), кто будет складывать его медленно. Когда вы видите 5 двоек, вы можете получить их напрямую2*5охватывать
- удалить элемент с индексом k
- Последний может быть покрыт предыдущим
- найти общие числа
- Используя идею стека,Пока количество вхождений массива больше 1/2, он должен быть в стеке
- пропущенные номера
- Реализация 1: обходятся два массива, если один из них не существует, его можно найти по индексу массива~
- Реализация 2: Использование формулы арифметической суммы пропущенные номера могут быть вычтены!
- поставить 0 в конце массива
- Реализация 1: Используйте переменную ноль, чтобы запомнить, сколько нулей есть, двигаться вперед, пока она не равна 0, и, наконец, завершить нуль!
- Реализация 2: Разделить массив на 3 части;Перед j нет 0, все от j до i равны 0, и нет обхода после i, пока после i не будет пройдено, передняя часть j не равна 0, а j-i все равны 0(на этом наша задача закончена)
- Найти одно число в массиве
- Реализация 1:Итерация по массиву для подсчета количества вхождений элемента, внешний слой снова проходит через массив, пока количество раз, когда элемент появляется, равно 1, тогда он один!
- Реализация 2:побитовая операция XOR, те же два числа сокращаются!
- рисуем треугольные звезды
- Найдите правила рисования звезд и пространств! И звезды, и пробелы связаны с количеством строк!
- Римские цифры перевернуты арабскими цифрами
- Сопоставьте римский массив с арабскими цифрами и «поищите в таблице», чтобы преобразовать! Найдите наибольшее значение, левое меньше правого, затем правое минус левое. И наоборот, право плюс лево!
- Пиво и напитки
- Используйте грубую силу для поиска конкретных значений!
- простой шифр Цезаря
- char по сути является int.При перемещении нужно ориентироваться на символы Z и A~
- найти наибольший общий делитель
- Если остаток равен 0, то делитель является наибольшим общим делителем, в противном случае делитель и остаток продолжают действовать!
Оглавление Навигация по статьям:Город Чжунфу.bit cron.com/post/hand-just…
Если в статье есть какие-либо ошибки, пожалуйста, поправьте меня, и мы сможем общаться друг с другом. Учащиеся, привыкшие читать технические статьи в WeChat и желающие получить больше ресурсов по Java, могутОбратите внимание на публичный аккаунт WeChat: Java3y