五、找出数组的单个数字
给你一个数组，除了一个数字外，其他的数字都出现了两次，请把这个只出现一次的数字找出来。
思路：
- 将该数组遍历一次，记录每个数字出现的次数
- 如果该数字出现的次数只有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; }
结果：
优化：
这个问题最佳的解法是用到了位运算的异或操作：
- 如果
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行，第三行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(); } }
结果：
七、罗马数字倒转成阿拉伯数字
罗马数字倒转成阿拉伯数字
罗马数字我们可能在英语的题目中看得是比较多的，一般常用的我们是阿拉伯数字，那怎么转成阿拉伯数字呢？？我们先来了解一下罗马数字：
ps:来源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; } }
测试一下：
八、啤酒与饮料
啤酒每罐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); } } } }
测试：
九、简单凯撒密码
简单凯撒密码
凯撒密码是啥？简单来说：就是通过移位来进行加密
- 比如，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);
结果：
十、求最大公约数
求一个数的最大公约数
算法：是两个数相余，直到余数为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，就直接得出2*5了
- 删除下标为k的元素
- 后一位往前一位覆盖即可
- 找出常用的数字
- 利用栈的思想，只要该数组出现的次数大于2分之1，那么他肯定是在栈里面
- 丢失的数字
- 实现1：两个数组进行遍历，如果某一个不存在，利用数组的角标就可以找到～
- 实现2：使用等差求和公式，缺失的数字可以减出来！
- 将0放在数组最后
- 实现1：使用变量zero来记住有多少个0，只要不是0就往前面移动，最后将zero补全！
- 实现2：将数组分成3个部分；在j之前的没有0，j到i全是0，i后面还没有遍历，直至i遍历完毕后，j前面都不是0，j-i都是0(这就完成我们的任务了)
- 找出数组的单个数字
- 实现1：遍历数组计算某个元素出现的次数，外层再遍历数组，只要该元素出现的次数是1，那么它就是单个的！
- 实现2：位运算的异或操作，相同的两个数字会抵消掉！
- 画三角形星星
- 找到画星星和空格的规律！星星和空格都与行数有关联！
- 罗马数字倒转成阿拉伯数字
- 将罗马数组和阿拉伯数字对应起来，“查表”进行转换！找到最大的值，左边比右边要小，则右减左。反之右加左！
- 啤酒与饮料
- 使用暴力查询的方式来将具体的值搜索出来！
- 简单凯撒密码
- char本质上就是int，移动时要主要Z，A这些字符～
- 求最大公约数
- 如果余数为0，那么除数就是最大公约数，否则就是除数和余数再继续运算！
