Inno' Blog HomeArchivesTagsCategoriesGalleryAbout
刷题小知识积累（Java）
|Algorithm

OJ Java 环境 ： JDK 1.6

即需注意不要使用只有 JDK1.7 和 JDK1.8 的新特性，为了简便起见，只列出这两个版本的新特性的常用特性，

  • switch 中可以使用字符串
  • “<>”这个玩意儿的运用List tempList = new ArrayList<>(); 即泛型实例化类型自动推断
  • ** 两个 char 间的 equals**

务必注意第二点

做题经验总结

输入输出

使用输入输出时，最好带入缓冲流

1
2
Scanner in = new Scanner(new BufferedInputStream(System.in));
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

注意 使用out输出时，记得在输出之后调用那个flush()函数，否则无法输出
示例：

1
2
out.println(str);
out.flush();

若要使用close()方法也是可以得，但要注意题目要求，若还有多行数据需要输入，则不应该使用close()
同时，好习惯是在程序结束之前将输入输出关闭

在使用in.nextLine()读入一整行时，需注意
如果在读入一整行之前要求输入其他的数，比如整型时，具体情况举例如下：

       输入的第一行为一个正整数n （1<=n<=10）。
　　    接下来n行...

nextLine()会将上一行末尾的\n当作一行，即在输入时会少输一行，这里提出两种解决方式

解决方式一：输入数字时使用nextLine，并用Integer.parseInt()进行转换

1
2
3
4
5
6
7
int a = Integer.parseInt(in.nextLine());
String str = null;
for (int i = 0; i < 3; i++) {
    str = in.nextLine();
    out.println(str);
    out.flush();
}

解决方式二：在输入完整数之后，加一行nextLine()，消除\n防止影响后面的结果

1
2
3
4
5
6
7
8
int a = in.nextInt();
in.nextLine();
String str = null;
for (int i = 0; i < 3; i++) {
    str = in.nextLine();
    out.println(str);
    out.flush();
}

字符串操作

对于需要大量字符串操作的题，最好使用StringBuilder进行操作

这里也可以使用StringBuffer，但是需要注意一点，StringBuffer是线程安全的，StringBuilder是线程不安全的，什么意思？

换句话说，就是StringBuffer为了保证线程安全，在效率上会略低于StringBuilder

而在这种程序设计中，一般是不会出现使用多线程的情况的，所以这里建议使用StringBuilder

关于程序超时

  • 如是多字符串有很多操作，最好使用StringBuilder
  • 如果采用了打表的方式检索数据，最好使用手动创建hashMap，因为hashMap检索很快（ArrayMap）
  • 对于大量数组计算，减少循环使用，采用计算公式，或者做判断，剔除不必要的数据

关于运行错误

  • 除以零
  • 数组越界
  • 指针越界
  • 使用已经释放的空间
  • 数组开得太大，超出了栈的范围，造成栈溢出

其他

  • 比较两个数组是否相等应该用 Arrays.equals( , )
  • 数组的复制 Arrays.copyOf()

提交

  • 类名务必是 Main，否则无法通过
  • 复制代码时，需要将除包名以外所有代码复制，即全部代码除了package语句，其他全部复制
  • 提交之前，务必多测试几组，在思考测试用例时，建议
    • 若题目给出了输入范围，最好测试一下输入最大的情况和输入最小的情况
    • 关于数字操作的题，格外注意0，int的范围（-2^312^31-1，即-2,147,483,6482,147,483,647），long的范围（-263263-1，即-9,223,372,036,854,775,8089,223,372,036,854,775,807）
    • 在使用浮点型计算时，注意浮点数陷阱
    • 测试时，最好注意一下每组测试时是否把上组测试用例的结果清空，不然后导致编译错误

length, size(), length()

在使用编译器时，并不会太注意这个问题，但是在白板编程时，经常会弄混，那么这里总结一下

在 Java 中

  • 数组相关，用 length
  • 集合相关，用 size()
  • 字符串相关，用 length()

BTW，在 kotlin 中

  • 数组、集合相关，用 size
  • 字符串相关，用 length

并且都不需要圆括号

小知识收集

余模定理

(a + b) % mod = (a % mod + b % mod) % mod
(a * b) % mod = ((a % mod) * (b % mod)) % mod

浮点数判断

在 Java 中存在浮点数陷阱，即

1
2
3
double a = 2.0 - 1.9;
double b = 0.1;
System.out.println(a == b); // false

其原因是

1
2
System.out.println(2.0 - 1.9);
// 0.10000000000000009

那么解决这个问题的方法则是做减法，当值小于一个特定的数时，则认为相等

1
System.out.println(a - b < 1e-10); // true

这里差值只要小于 1^-10 则认为相等

使用换底公式判断一个数是否是 3 的 n 次方数

换底公式 : log_3(num) = log10(num) / log10(3.0)

举例如下，输入一个数 num，使用换底公式可以得到它是 3 的几次方

1
double res = Math.log10(num) / Math.log10(3.0)

这里需要判断 res 是否为整数即可，方法就是做浮点数减法

1
(res - (int)res) < 1e-10

刚发对判断 2^n 数、4^n 数都可行

使用异或找到每个元素都出现2次除了其中的一个的数组中唯一不重复的元素

比如数组 [6,4,3,3,4,4]，根据要找到数组中唯一不重复的那个元素

这里的小技巧是使用异或

原理是 a ^ b = b ^ a，即异或满足交换律
同时

1
2
0 ^ a = a
a ^ a = 0

所以当重复的元素取异或时会变为 0，而 0 异或任何一个数都是他本身。方法如下

1
2
3
4
5
int res = 0;
for (int i = 0; i < nums.length; i++) {
    res = res ^ nums[i];
}
System.out.println(res);

佛洛依德判环判断循环内是否出现循环数字

原理解释如下

两个人同时跑步，第二个人的速度是第一个人的两倍，那么第二个人能在下一圈的同一个位置遇到第一个人

比如现在有个方法 public int calc(int n) 用于对数字 n 转化为另一个数字，通过如下方法可以判断在循环中该数是否会循环出现

1
2
3
4
5
6
7
8
9
10
11
public boolean check(int n) {
	int one = n;
	int two = n;
	while (1) {
		one = calc(one);	   		 // 相当于第一个人的速度
		two = calc(calc(two));		 // 相当于第二个人的速度，是第一个人的两倍
		// if (one 为何值）有什么结果
		// if (two 为何值) 有什么结果
		if (one == two) return true; // 表示会出现循环
	}
}

拿到数字的最高位为 1 的二进制数

比如数字 5，对应的二进制码为 101
那么就可以拿到对应最高位为一 100

在 Java 的 Integer 类中，有一个 highestOneBit 方法，具体实现如下

1
2
3
4
5
6
7
8
public static int highestOneBit(int i) {
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    return i - (i >>> 1);
}

这里解释一下中间的实现部分

1
2
3
4
5
i |= (i >>  1);
i |= (i >>  2);
i |= (i >>  4);
i |= (i >>  8);
i |= (i >> 16);

比如数字 5，二进制为 101，经过这一步骤后，可以得到 111

解释如下：

i |= (i >> 1);

即 i 本身和向右移一位的 i 取位或运算，相当于

    101 | 010

此时 i 等于 111

再比如 16，二进制为 10000，经过这一步骤过后，可以得到 11111

解释如下

i |= (i >> 1); // =》 10000 | 01000 = 11000
i |= (i >> 2); // =》 11000 | 00110 = 11110
i |= (i >> 4); // =》 11110 | 00001 = 11111
i |= (i >> 8); // =》 11111 | 11111 = 11111
i |= (i >> 16); // =》 11111 | 11111 = 11111

这个方式的运用可以算出一个正数的反码

当我用 10000 与 11111 异或时，可以得到 10000 的反码 01111

关于 n 阶矩阵的规律

以 4 阶矩阵的正对角线 ‘/‘ 为例

对于 4 阶矩阵，对角线个数为 2 x 4 - 1 = 7 条
对于 n 阶矩阵，对角线个数为 2 x n - 1 条

若用 i 表示行元素，j 表示列元素，那么每条对角线上的元素的 行下标 + 列下标 可得，从第一条正对角线开始，i + j 的值分别为
0, 1, 2 .. 2*n-2

以 4 阶矩阵的反对角线 ‘' 为例

反对角线个数同上：2 * n + 1

若用 i 表示行元素，j 表示列元素，那么每条对角线上的元素的 行下标 - 列下标 可得，从第一条反对角线开始，i + j 的值分别为
-(n-1), -(n-2), -(n-3), ..., -1, 0, 1, ..., n-3, n-2, n-1

在二维数组中，尝试对四个方向进行遍历

假如现在的坐标为 (x, y)，那么要对四个方向进行遍历的话，可以先定义一个二维方向数组，用来存储 x 轴方向和 y 轴方向可移动的

1
2
3
4
5
6
7
8
 // 顺时针方向
int[][] direct = {
			{1, 0}, // 右
			{0, 1}, // 下
			{-1, 0},// 左
			{0, -1} // 上
		}
}

这四个方向可以颠倒顺序，具体是怎样的应该根据具体情况分析

那么在对四个方向进行遍历时，就可以用循环操作了，这样代码会显得更加紧凑

1
2
3
4
5
6
7
8
for ( int i = 0; i < 4; i ++ ) {
	int newX = x + direct[i][0];
	int newY = y + direct[i][1];

	if (newX >= 0 && newX < rows && newY >= 0 && newY < cols) {
		// 只要新坐标没越界就继续操作，rows 为行数，cols 为列数
	}
}

Author: Inno Fang
Link: http://innofang.github.io/2017/12/07/%E5%88%B7%E9%A2%98%E5%B0%8F%E7%9F%A5%E8%AF%86%E7%A7%AF%E7%B4%AF%EF%BC%88Java%EF%BC%89/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-ND 4.0 unless stating additionally.
Algorithm