刷题小知识积累(Java)

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^31~2^31-1,即-2,147,483,648~2,147,483,647),long的范围(-263~263-1,即-9,223,372,036,854,775,808~9,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 为列数
}
}

文章作者: Inno Fang
文章链接: https://innofang.github.io/2017/12/07/刷题小知识积累(Java)/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来自 Inno's Blog