本文题目难度标识：🟩简单，🟨中等，🟥困难。

两数交换

常用写法

中间变量法

1
2
3
4
// 记法：记住变量首尾相接，怎么写都不会错
int t = a;
a = b;
b = t;

这种方法可读性高，但是需要在内存中存放临时变量。

数学运算法

1
2
3
4
5
6
7
8
9
// 加减法
a = a + b;
b = a - b;
a = a - b;

// 异或法
a ^= b;
b ^= a;
a ^= b;

方法评价：

  • 加减法：两个数相加之后，可能其结果超出了变量类型能表达的最大范围，这个时候结果就会出数据溢出，不推荐使用。
  • 异或法：效率是最高的，但是可读性不是很好。

Java 中编写 swap 交换函数

Java 在有参函数调用时，如果参数传递的是基本类型，进行的是值传递，而不是 地址或引用传递。

因此，以下的写法是错误的：

1
2
public static void swap(int a, int b);
public static void swap(Integer a, Integer b);

正确的写法是传入一个数组，在数组的基础上进行交换：

1
2
3
4
5
public static void swap(int[] arr) {
	int temp = arr[0];
	arr[0] = arr[1];
	arr[1] = temp;
}

循环增减

1
2
3
// 循环增减
idx=(idx+1) % SIZE;
idx=(idx + SIZE - 1) % SIZE;

将比较关系整数化

得到 a 和 b 的大小关系，小于是 -1，等于是 0，大于是 1

1
2
// 布尔大小比较转为输出整数
(a>b)-(a<b)

四舍五入

1
2
3
// 四舍五入
double x;
x = (int)((x * 1000) + 0.5) / 1000.0)  // 保留3位小数就乘1000、除以1000.0

向上取整转变为向下取整

对于正整数 mm，有：

⌈nm⌉=⌊n+m−1m⌋=⌊n−1m⌋+1\lceil \frac{n}{m} \rceil = \lfloor \frac{n+m-1}{m} \rfloor= \lfloor \frac{n-1}{m} \rfloor +1

我们可以根据这个性质将一些向上取整操作处理为向下取整。

最大公约数 GCD

辗转相除法数学定理：gcd(a,b) = gcd(b,a mod b)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 迭代版本
public int gcd(int a, int b) {
	while (b != 0) {
		a %= b;
		swap(new int[]{a,b}); // 交换结束 b 是小的那一个
	}
	return a;
}

// 自己写的版本
public int gcd(int a,int b){
	while(a%b!=0){
		a%=b;
		swap(new int[]{a,b});
	}
	return b;
}

递归版本：

1
2
3
4
5
// 递归版本
public static int gcd(int a,int b){
	if (b == 0) return a;
	return gcd(b, a % b);
}

相关题目：

质数的判断

详看：站内文章【刷题日记】判断质数

本文参考