前言
清明不小心就拖了两天没更了～～
这是十道算法题的第二篇了～上一篇回顾：十道简单算法题
最近在回顾以前使用C写过的数据结构和算法的东西，发现自己的算法和数据结构是真的薄弱，现在用Java改写一下，重温一下。
只能说慢慢积累吧～下面的题目难度都是简单的，算法的大佬可直接忽略这篇文章了～入门或者算法薄弱的同学可参考一下～
很多与排序相关的小算法(合并数组、获取数字每位值的和)，我都没有写下来了，因为只要会了归并排序(合并数组)，会了桶排序(获取数字每位的值)，这些都不成问题了。如果还不太熟悉八大基础排序的同学可看:【八大基础排序总结】
由于篇幅问题，每篇写十道吧～
如果有错的地方，或者有更好的实现，更恰当的理解方式希望大家不吝在评论区留言哦～大家多多交流
十道简单算法题
题目的总览
- 删除下标为k的元素
- 找出常用的数字
- 丢失的数字
- 将0放在数组最后
- 找出数组的单个数字
- 画三角形星星
- 罗马数字倒转成阿拉伯数字
- 啤酒与饮料
- 简单凯撒密码
- 求最大公约数
一、删除下标为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); }
二、找出常用的数字
给你一个长度为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); }
三、丢失的数字
给你一个数组{0,1,2,3,….n}，其中有一个数字缺失，请把缺失的数字找出来
思路：
- 创建一个数组(题目数组的长度+1，因为题目的数组缺失了一个)
- 创建的数组元素用特殊的符号(数字)来进行填满
- 将题目给出的数组遍历并填充到创建的数组上，用index(0,1,2,3..)替代
- 最后遍历创建的数组，哪个还是特殊的符号就是缺失的数字，返回index(缺失的数字)即可
/** * 找到缺失的数字 * * @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的，放在数组的最后
思路：
- 使用一个变量zero来记住该数组有多少个0
- 遍历这个数组，如果发现不是0的，就往数组前面移动，如果发现是0就zero++
- 数组移动的位置刚好是
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); }
结果还是一样的：
