简单算法技巧积累 —— 醉翁之意不在题 :-)

1. 序言

最近真的见识到很多的算法大佬,有用算法写出五子棋电脑玩家的,有普通一本某高校获得ACM金奖的…..

感觉写惯了基础的业务代码的我来说,就是一个实实在在码农。但是因为兴趣入这行的我,一直都没有做码农的心。因此,打算好好地学习算法,从最简单的编程题考试,从头开始积累简单算法的一些基础技巧。

这篇博文所记载的题,并不是典型的基础算法题,更多地,是积累其中的技巧。所有的题的源代码都能在Github找到。

2. Let’s go

1-n阶乘之和

题目:

1
2
3
4
5
6
1的阶乘是1
2的阶乘是1*2
3的阶乘是1*2*3
4的阶乘是1*2*3*4

求1-n阶乘之和?

1-n阶乘的和,通过分析可以得出:

  • 3的阶乘的和 = 2阶乘的和 + 3的阶乘
  • 4的阶乘的和 = 3阶乘的和 + 4的阶乘

理解了题目的意思,很容易地写出求出1-n阶乘的代码:

1
2
3
4
5
6
7
8
9
public static void solution(int n) {
double sum = 0; // 记录总和
double factorial = 1; // 记录每一个阶乘的总和
for (int i = 1; i <= n; i++) {
factorial = factorial * i;
sum = (int) (sum + factorial);
}
System.out.println("n - 1 阶乘的和为:" + sum);
}

需要掌握的技巧是:这里没有直接计算每一个n阶乘的和,而是在n-1的阶乘基础上做计算。例如2的阶乘是:factorial = 1 * 2,而3的阶乘直接使用了:factorial = factorial * 3。这样能充分地使用已经计算的值,能有效地降低算法的运行速度。

获取二维数组每列最小的值

题目:

1
2
3
4
5
6
7
8
9
获取给定的二维数组中每列的最小值:

输入:{
{23, 106, 8, 234},
{25, 9, 73, 19},
{56, 25, 67, 137}
}

输出: {8, 9, 25}

该题找出最小值应该比较简单,通过一个min变量来记录某一个列的最小值即可。重点在于通过嵌套循环操作二维数组:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void solution(int[][] arrays) {
int[] minArray = new int[arrays.length];

for (int i = 0; i < arrays.length; i++) { // 遍历列
int min = arrays[i][0]; // 假设每列的第一位数是最小数
for (int j = 0; j < arrays[0].length; j++) { // 遍历每列中的行
if (arrays[i][j] < min) {
min = arrays[i][j];
}
}
minArray[i] = min;
}
// 打印每列的最小数
for (int i = 0; i < minArray.length; i++) {
System.out.println("第" + (i + 1) + "列的最小数为:" + minArray[i]);
}
}

可以看出,遍历二维数组的每个元素的方式是:外层循环控制列数,内层循环控制行数

判断一个数是不是2的某次方

题目:

1
2
3
4
判断一个数是不是2的某次方

输入:8
输出:true

这题需要掌握的是求某个元素是不是某个数的某次方问题。对于该题来说,判断一个数是不是2的某次方,只需要通过while循环让该数一直对2取余数,直到余数不为0时跳出循环。当每次余数为0时,将该数除以2,也就代表次方数 + 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static boolean solution(int num) {
if (num == 0) {
return false;
}
if (num == 1) { // 2的0次方为1
return true;
}

/* 除2取余数,直至余数不为0。然后看是不是等于1就可以判断是不是2的某次方了 */
int m = 0; // 记录几次方
while (num % 2 == 0) {
/* 当这个数可以整数2时,再对这个数进行赋值 => 除以 2。一直到无法整数2时 */
num = num / 2;
m += 1;
}

if (num == 1) { // 如果是2的某次方,打印出次方的倍数
System.out.println(m);
}

return num == 1;
}

通过这个技巧,我们可以解决分解出来的质因数只有某些数的问题:

1
2
3
4
判断一个数字是不是ugly number(分解出来的质因数只有2、3、5这3个数字)

输入:15
输出:true

同样地,我们可以依次反复对235取余数,直至余数不为0,最后再判断该值为1即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static boolean solution(int num) {
if (num <= 0) {
return false;
}

while (num % 2 == 0) { // 对2取余数,直到余数不为0
num = num / 2;
}
while (num % 3 == 0) { // 对3取余数,直到余数不为0
num = num / 3;
}
while (num % 5 == 0) { // 对5取余数,直到余数不为0
num = num / 5;
}

return num == 1;
}

水仙花数

题目:

1
2
3
打印出所有的"水仙花数"。
所谓"水仙花数"是指一个三位数,其各位数字立方和等于该数本身。
例如:153是一个"水仙花数",因为153 = 1的三次方+5的三次方+3的三次方。

该题解决的思路主要是通过拿到三位数中的个、十、百上的数,然后通过判断每个值的立方值相加是否等于它本身。一开始我通过操作字符串的方式来获取,但是这种方式运行时间较长,不推荐:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void solution0() {
List<Integer> lotusList = new LinkedList<>();

for (int i = 100; i < 999; i++) {
String str = String.valueOf(i);
int sum = 0;
for (int j = 0; j <= 2; j++) {
int number = Integer.parseInt(str.substring(j, j + 1));
sum += (number * number * number);
}
if (sum == i) {
lotusList.add(i);
}
}
}

但是,我们可以通过取余数的技巧(取余数真是无事不能啊!),来获取个、十、百位上的数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void solution1() {
List<Integer> lotusList = new LinkedList<>();

for (int i = 100; i < 999; i++) {
int ones = i % 10; // 取得个位
int tens = (i / 10) % 10; // 取得十位
int hundreds = (i / 100) % 10; // 取得百位

int cubicMetre = (ones * ones * ones) + (tens * tens * tens) + (hundreds * hundreds * hundreds);
if (cubicMetre == i) {
lotusList.add(i);
}
}
}

两种算法的运行时间对比,差距还是蛮大的:

1
2
共花费总时间为:2370900ns   // solution0
共花费总时间为:167800ns // solution1

找出常用的数字

题目:

1
2
3
4
给你一个长度为n的数组,其中有一个数字出现的次数至少为n/2,找出这个数字

输入:[1, 2, 1, 3, 4, 1, 1]
输出:1

这里可以用栈的思维来做,因为这个数出现的次数是大于这个数组长度的 2 /1 的,那么根据代码中的操作,最后留在栈中的肯定是这个数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int solution(int[] array) {
Stack<Integer> stack = new Stack<>();

for (int i = 0; i < array.length; i++) {
if (stack.isEmpty()) { // 如果栈为空,将元素入栈
stack.push(array[i]);
}
else if (stack.peek() == array[i]) { // 如果该元素和栈顶元素相等,则入栈
stack.push(array[i]);
} else {
stack.pop(); // 如果与栈顶元素不相等,则将栈顶元素出栈
}
}

/* 那么剩下来的元素肯定是出现次数最多的(而且肯定出现次数肯定大于 n/2) */
return stack.peek();
}

原理是什么呢?你可以想象为每一个入站的那个最多元素,将其他元素一一抵消了,最后剩下的就是次数最多的那个元素。

找出数组的单个数字

题目:

1
2
3
4
给你一个数组,除了一个数字外,其他的数字都出现了两次,请把这个只出现一次的数字找出来。

输入:{3, 2, 3}
输出:2

本题比较能想到而且相对简单的方法是通过HashMap来建立 元素 — 出现次数的映射关系,然后在遍历Map找到出现次数为1的元素:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int solution(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();

for (int i = 0; i < nums.length; i++) {
Integer value = map.get(nums[i]);
map.put(nums[i], (value == null ? 0 : value) + 1);
}
/* 找到值(出现次数)为1的元素 */
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() == 1) {
return entry.getKey();
}
}

return 0;
}

但是本题需要掌握的技巧是:通过位运算的异或操作算法来解决。我们知道:

1
2
3
0010 0100 & 0010 0100 = 0010 0100  // 36 & 36 = 36
0010 0100 | 0010 0100 = 0010 0100 // 36 | 36 = 36
0010 0100 ^ 0010 0100 = 0000 0000 // 36 ^ 36 = 0

由上面的计算可以总结出:

  • 相同数字做&运算,会得到相同的数字
  • 相同数字做|运算,会得到相同的数字
  • 相同数字做^异或运算,会得到0

因此,这里我们可以遍历数组的所有的数字,让它们以次做异或的操作,那么俩俩相同的数字就会被抵消掉,最后剩下的res就是数组中单一的那个数字:

1
2
3
4
5
6
7
public static int solution1(int[] nums) {
int res = 0;
for (int e : nums) {
res = res ^ e;
}
return res;
}

啤酒与饮料和欧拉与鸡蛋

题目:

1
2
啤酒每罐2.3元,饮料每罐1.9元。小明买了若干啤酒和饮料,一共花了82.3元。
我们还知道他买的啤酒比饮料的数量少,请你计算他买了几罐啤酒。

该题需要掌握的技巧是:暴力搜索。怎么用暴力搜索法解决呢?首先我们假设两种情况:

  • 全部钱都买了啤酒,可以买35瓶啤酒;
  • 全部钱都买了饮料,可以买43瓶饮料。

知道了这两种极端的情况,那么我们可以通过双循环的暴力搜索法的方式来:

1
2
3
4
5
6
7
8
9
10
11
public static int solution() {
for (int i = 0; i < 36; i++) {
for (int j = 0; j < 44; j++) {
/* 满足题中的条件,i代表购买啤酒的数量,j代表购买饮料的数量 */
if (2.3 * i + j * 1.9 == 82.3 && i < j) {
return i;
}
}
}
return 0;
}

在循环中做符合题意中的判断:当酒的价格 x 酒的数量 + 饮料的价格 * 酒的数量,并且满足酒的数量 < 饮料的数量时,得出ij的值,即购买的酒和饮料的数量。

类似的题还有欧拉和鸡蛋:

1
2
3
4
5
6
7
大数学家欧拉在集市上遇到了本村的两个农妇,每人跨着个空篮子。她们和欧拉打招呼说两人刚刚卖完了所有的鸡蛋。
欧拉随便问:“卖了多少鸡蛋呢?”
不料一个说:“我们两人自己卖自己的,一共卖了150个鸡蛋,虽然我们卖的鸡蛋有多有少,但刚好得了同样的钱数。你猜猜看!”
欧拉猜不出。
另一个补充道:“如果我按她那样的价格卖,可以得到32元;如果她按我的价格卖,可以得到24.5元”。
欧拉想了想,说出了正确答案。
我们不是数学家,懒得列出公式来分析。但计算机可以“暴力破解”,就是把所有可能情况都试验一遍,撞上为止!

根据题中的条件,我们可以总结出如下的几个等式,作为暴力破解的“出口”:

  • 俩农妇卖出的鸡蛋数量相加为150i + j = 150
  • 俩农妇卖的钱是相等的:x * p1 = y * p2
  • 农妇A以农妇B的价格能卖32x * p2 = 32;农妇B以农妇A的价格能卖24.5y * p1 = 24.5

得出等式:24.5 * i * i == 32 * j * j,同样通过双循环的暴力求解方式来穷举出俩农妇各自卖出的鸡蛋数量:

1
2
3
4
5
6
7
8
9
10
11
public static void solution() {
for (int i = 0; i < 150; i++) {
for (int j = 0; j < 150; j++) {
/* 暴力求解,i代表A卖的个数,j代表B卖的个数 */
if (i + j == 150 && 24.5 * i * i == 32 * j * j) {
System.out.println(i);
System.out.println(j);
}
}
}
}

求最大公约数

题目:

1
2
3
4
5
6
求一个数的最大公约数。
什么是最大公约数?如果数a能被数b整除,a就叫做b的倍数,b就叫做a的约数。
几个整数中公有的约数,叫做这几个数的公约数;其中最大的一个,叫做这几个数的最大公约数。

输入:a = 108, b = 96
输出:12

首先这题我们要掌握的知识是求最大公约数的方法,即辗转相除法:a、b的最大公约数就是b、a % b 的最大公约数

1
gcd(a, b) = gcd(b, a mod b)  // mod 即取余数的意思

借助这个特性,我们通过递归来实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class GreatestCommonDivisor {

public static int solution1(int num1, int num2) {
if (num1 < 0 || num2 < 0) { // 数学上不考虑负数的约数
return -1;
}
return euclidean(num2, num1 % num2);
}

public static int euclidean(int num1, int num2) {
/* 递归的出口, 如果余数为0,那么该除数就是最大公约数 */
if (num2 == 0) {
return num1;
} else {
return solution(num2, num1 % num2);
}
}

public static void main(String[] args) {
int a = 108;
int b = 96;
int result = GreatestCommonDivisor.solution1(a, b);
System.out.println(result);
}

}

该题还需要掌握的另一个技巧是:递归可以被迭代替代:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int solution(int num1, int num2) {
if (num1 < 0 || num2 < 0) { // 数学上不考虑负数的约数
return -1;
}
if (num2 == 0) {
return num1;
}
while (num1 % num2 != 0) {
int temp = num1 % num2;
num1 = num2;
num2 = temp;
}
return num2;
}

猴子吃桃

题目:

1
2
3
4
猴子第一天摘下若干个桃子,当即吃了一半,还不瘾,又多吃了一个。
第二天早上又将剩下的桃子吃掉一半,又多吃了一个。
以后每天早上都吃了前一天剩下的一半零一个。
到第10天早上想再吃时,见只剩下一个桃子了。求第一天共摘了多少。

本题需要掌握的技巧是运用逆向思维,从后往前推断

1
2
3
4
5
6
7
8
public static int solution1(int day) {
int x = 1; // 最后一天的桃子个数
for (int i = 1; i <= (day - 1); i++) {
/* 一半多一个的逆向思维即: 两倍加1 */
x = (x + 1) * 2;
}
return x;
}

当然,用迭代来实现的算法,同样可以用递归来实现:

1
2
3
4
5
6
7
public static int solution(int x) {
if (x == 1) {
return 1;
} else {
return 2 * solution(x - 1) + 2;
}
}

排列组合

题目:

1
有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少?

本题需要掌握的技巧是:通过嵌套循环来实现排列组合的算法。通过三个嵌套循环分别来表示百、十、个位上的排列组合情况:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static List<Integer> solution() {
List<Integer> res = new LinkedList<>();

for (int i = 1; i < 5; i++) { // 百
for (int j = 1; j < 5; j++) { // 十
if (i == j) {
/* 如果百位和十位相等,则该数无效 */
continue;
}
for (int k = 1; k < 5; k++) { // 个
/* 如果个位与十位或者与百位相等,则该数无效 */
if (k == j || k == i) {
continue;
}
int number = i * 100 + j * 10 + k; // 计算出三位数
res.add(number);
}
}
}
return res;
}

回文数

题目:

1
2
判断一个整数是不是回文数。
回文数即:正读倒读都一样的整数,如12321是回文数,个位与万位相同,十位与千位相同。

本题需要掌握的技巧是获取并处理整数上各个位上的数。在下面的算法中,通过取余数的方式获取到个位上的数值,然后将num值除以10,去掉个位上的数,将小数点向前移动一位。那么当下一次迭代时,获取到的个位上的数值即这次的百位上的数值:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static boolean solution(int num) {
int length = getNumberLength(num);
int[] nums = new int[length];

/* 将整数拆分为个数按照个十百...的顺序存放到数组中 */
for (int i = 0; i < length; i++) {
nums[i] = num % 10;
num /= 10;
}
/* 比较数组,判断是不是回文数 */
for (int j = 0; j < length / 2; j++) {
if (nums[j] != nums[length - 1 - j]) {
return false;
}
}
return true;
}

/**
* 获取某个数的长度
*/
private static int getNumberLength(int num) {
return String.valueOf(num).length();
}

如果我们无法或者不想获取整数的长度,可以通过do-while循环来实现,例如下题:

1
2
给一个不多于5位的正整数。
要求:一、求它是几位数,二、逆序打印出各位数字。

算法实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void solution1(int num) {
int i = 0; // 记录整数的个数
List<Integer> res = new ArrayList<>();

do {
res.add(num % 10);
num /= 10;
++i;
} while (num != 0);

System.out.print("这是一个" + i + "位数,反向打印的为:");
for (Integer n : res) {
System.out.print(n + " ");
}
}
Pushy wechat
欢迎订阅我的微信公众号