tips-java

Java刷题技巧

数组相关操作

常见

int arr[] = new int[size], n = arr.length;  // 简化定义方式

Arrays.equals(T[], T[]);  // 比较
System.arraycopy(src, 0, dst, 0, len);  // 复制
Arrays.copyOf(src, len);  // 复制
Arrays.copyOfRange(src, from, to);  // 复制
cnt[nxt] = cnt[cur].clone();  // 复制（克隆）

• sort

Arrays.sort(T[], Comparator);  
int arr[][] = {{1, 3}, {3, 1}};
Arrays.sort(arr, (a,b)->b[1]-a[1]);
int arr2[] = {1,3,2};
Arrays.sort(arr2, (a,b)->b-a);  // 报错，当放入Comparator参数时，T数组不能基本类型数组

• fill 和 setAll

Arrays.fill(arr, 0);  // fill
private List<Integer>[] g;
Arrays.setAll(g, i -> new ArrayList<>());  // setAll

System.out.println(Arrays.toString(num));  // toString

翻转

// IntStream.range方法对于int和Integer都可以
int intArr[] = new int[]{1, 2, 3};
int[] reverse1 = IntStream.range(0, intArr.length).map(i -> intArr[intArr.length - 1 - i]).toArray();
Integer integerArr[] = new Integer[]{1, 2, 3};
int[] reverse2 = IntStream.range(0, integerArr.length).map(i -> integerArr[integerArr.length - 1 - i]).toArray();
// Collections.reverse方法直接修改原数组，且无法适用于int
Collections.reverse(Arrays.asList(integerArr));
Collections.reverse(Arrays.asList(intArr));  // 不生效

Array和List互相转换

• Array->List

// Integer[]->List<Integer>
Arrays.asList(new Integer[]{1, 2, 3});  // 转换成List，注意int类型不可以转化成Integer类型

// int[]->List<Integer>
int nums = new int[]{1, 2, 3};
List<Integer> list = Arrays.stream(nums).mapToObj(i -> Integer.valueOf(i)).collect(Collectors.toList());
// int[]->Set<Integer>
Set<Integer> set = Arrays.stream(nums2).mapToObj(i -> Integer.valueOf(i)).collect(Collectors.toSet());

• List->Array

List<Integer> List = new ArrayList<>();
// List<Integer> -> Integer[]
list.toArray(new Integer[n]);  // 需要引用类型，不能用int（基本类型）
// List<Integer> -> int[]
int[] nums = l.stream().mapToInt(i -> i).toArray();

List<int[]> arrList = new ArrayList<>();  // 元素的大小是int[2]
// List<int[]> -> int[][];
arrList.toArray(new int[n][2]);  // int[]数组是引用类型，
arrList.toArray(new int[0][2]);  // 也可以直接用0，这里并不代表真实长度，只是指明类型

• Array->Stream->Array

Stream s = Arrays.stream(new Person[2]);
Object[] array = s.toArray();
Stream s2 = Arrays.stream(new int[2][2]);
Object[] array2 = s2.toArray();
IntStream s3 = Arrays.stream(new int[2]);
Object[] array3 = s3.toArray();  // 报错，不能是基本类型（和sort同理）

集合

List

List<Integer> index = Arrays.asList(6, 6, 2, 3);  // 快速初始化
list.sort(Comparator);  // 排序
Collections.sort(list, (a,b)->a-b);  // 排序
list.equals();  // 比较  
Collections.reverse(list);  // 反转链表
Collections.shuffle(list);  // 打乱链表

Deque

Map

// computeIfAbsent
for (int i = 0; i < arr.length; i++) {
    map.computeIfAbsent(arr[i], key -> new ArrayList<>()).add(i);
    // 相当于
    // if (map.get(arr[i]) == null) {
    //    map.put(arr[i], new ArrayList<>());
    // }
    // map.get(arr[i]).add(i);
}

// 遍历
for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {}
for (int key : map.keySet()) {}

// 如果key不存在，则put(key, 1)；key存在，则put(key, map.get(key)+1)
// 等价于put(key, map.getOrDefault(key, 0)+1)
map.merge(key, 1, Integer::sum);

有序集合

PriorityQueue

// 为了让comparator识别到pq的T类型，<>不能省略
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[0]-b[0]);
pq.poll(); pq.peek(); // head
pq.offer();

TreeSet/TreeMap

TreeSet<Integer> set = new TreeSet<>();
// ceiling value >= target value >= floor value
Integer ceiling = set.ceiling(arr[x]), floor = set.floor(arr[x]);
// higher > taget value > lower
Integer higher = treeSet.higher(tg), lower = treeSet.lower(tg);
// TreeSet和PriorityQueue相比，可以操作两个方向的元素
set.pollFirst(); set.pollLast();
set.first(); set.last();

// 同理获取treeMap的相邻key
treeMap.floorKey(k); 
// 同理获取treeMap的相邻entry
treeMap.floorEntry(k);
// 获取treeMap的首尾key
treeMap.firstKey(); treeMap.lastKey();

数字操作

保留小数

• BigDecimal::setScale(int newScale, RoundingMode roundingMode)

BigDecimal bd = new BigDecimal(ans);
bd = bd.setScale(2, RoundingMode.HALF_UP);
System.out.println(bd);

• DecimalFormat

DecimalFormat df = new DecimalFormat("0.00");
return df.format(value);

• String::format

String.format("%.2f", value).toString();

大数

BigInteger

String res = new BigInteger("2...").subtract(new BigInteger("1")).toString();  
add(); subtract(); multiply(); divide();  // 加减乘除，还支持其它常见的math函数
BigInteger f = BigInteger.ONE;
f.shiftLeft(v); f.or(v); f.and(v);
f.bitLength();  // 返回f的二进制长度

进制转换

Integer.valueOf("2a", 16);
Integer.toString(int i, int radix);
Integer.toBinaryString(int i)  // toString(i, 2)
Integer.toOctalString(int i)  // toString(i, 8)
Integer.toHexString(int i)  // toString(i, 16)

位操作

int i = 41;  // "101001"
Integer.bitCount(i);  // 3 计算1的数量
Integer.highestOneBit(i);  // 32("100000") 计算最高位为1映射的值
Integer.lowestOneBit(i);  // 1("1") 计算最低位为1映射的值
Integer.numberOfLeadingZeros(i);  // 26 计算前缀连续0的数量
Integer.numberOfTrailingZeros(i);  // 0 计算后缀连续0的数量

Bitset

Java util自带BitSet，当然也可以手写，更快

// 相比 java.util.BitSet，去掉了一些边界检查、assert 等
class Bitset {
    private static final int W = Long.SIZE;

    private final long[] bits;

    Bitset(int n) {
        bits = new long[(n + W - 1) / W]; // 需要 ceil(n/W) 个 W 位整数
    }

    void set(int p) {
        bits[p / W] |= 1L << (p % W);
    }

    boolean has(int p) {
        return (bits[p / W] & (1L << (p % W))) != 0;
    }

    void or(Bitset other) {
        for (int i = 0; i < bits.length; i++) {
            bits[i] |= other.bits[i];
        }
    }

    int count() {
        int c = 0;
        for (long x : bits) {
            c += Long.bitCount(x);
        }
        return c;
    }
}

字符串操作

格式化字符串

Pair<Double, Integer> pair = pq.poll();
String s = String.format("%d %.6f\n", pair.getValue(), pair.getKey());

字符串转IntStream流

IntStream stream = s.chars();

字符串替换

text = text.replaceAll(old, new);

StringBuilder

// 如果题目有大量的String拼接操作，直接用String可能会超时，用StringBuilder会好很多
StringBuilder res = new StringBuilder();
res.append(c);
res.toString()

repeat

String t = "0".repeat(n) + s;  // 补前导零（快速构造有规律的字符串）

字符串拼接 join

String splits[] = date.split("-");
return String.join("-", splits);

misc

// 如果题目要求根据比较a和b的值，要求a大于b返回1，a等于b返回0，a小于b返回-1，则可以用Integer的compare方法
int diff = a - b;
return Integer.compare(diff, 0);

int nums[] = Arrays.stream(rewardValues).distinct().sorted().toArray();  // 去重排序
int nums[] = Arrays.stream(rewardValues).toArray();  // 也可以单纯换个名字

语法

类似goto

outer:
for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) {
        if (i * j > 6) {
            break outer;
            // continue outer;
        }
        System.out.println("i = " + i + ", j = " + j);
    }
}

在上述示例中，如果 i * j > 6，则会跳出外层循环。

char的for循环

for (char i = 'a'; i <= c; i++)

静态初始化list

private static ArrayList<Integer> list = new ArrayList<>() {
    {
        boolean[] flag = new boolean[1000000];
        for (int i = 2; i < 1000000; i++) {
            if (!flag[i]) {
                add(i);
                for (int j = 2 * i; j < 1000000; j += i) {
                    flag[j] = true;
                }
            }
        }
    }
};