一些刷题小技巧

位运算

左移 <<1 表示 乘以 2，右移 >>1 表示除以 2

获取一个 int 类型整数每个位置上的 2 进制数位

ex：剑指 Offer II 067. 最大的异或 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

（下面代码为从高位向低位、从左往右）

for (int i = 31; i >= 0; i --) {
	// 获取当前数位上的 2 进制数值
	int bit = (num >> i) & 1;
	......
}

从高位向低位（从左往右）计算两个整数的异或结果

ex：剑指 Offer II 067. 最大的异或 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

// 存储两数（`int nums1` 和 `int nums2`）的异或结果
int xor = 0;

for (int i = 31; i >= 0; i --) {
    // 获取当前数位上的 2 进制数值
    int bit1 = (num1 >> i) & 1;
	int bit2 = (num2 >> i) & 1;
    
    // 两数位不相等
    if (bit1 != bit2) {
        xor = xor * 2 + 1;
    }
    // 两数位相等
    else {
        xor = xor * 2;
    }
}

return xor;

字符串

判断字符串 1 是否以 字符串 2 开头

ex：剑指 Offer II 114. 外星文字典 (opens new window)

// String word1 = "abc";
// String word2 = "ab";
word1.startsWith(word2); // true

判断字符串中的某个字符是否是数字或字母

ex：剑指 Offer II 018. 有效的回文 (opens new window)

// String s;
char ch1 = s.charAt(left);
boolean res = Character.isLetterOrDigit(ch1);

某个字符转小写

ex：剑指 Offer II 018. 有效的回文 (opens new window)

// char ch1;
ch1 = Character.toLowerCase(ch1);

集合与数组

数组复制

ex：面试题 17.05. 字母与数字 (opens new window)

// int[] nums1
// 左闭右开
int nums2 = Arrays.copyOfRange(nums1, leftIndex, rightIndex);

数组快速求和

ex：剑指 Offer II 012. 左右两边子数组的和相等 - 力扣（LeetCode） (opens new window)

// int[] nums;
int sum = Arrays.stream(nums).sum();

数组快速排序

// int[] nums
Arrays.sort(nums); // 该方法返回值是 void

快速判断两个数组是否相同

ex：剑指 Offer II 115. 重建序列 - 力扣（LeetCode） (opens new window)

// int[] arr1;
// int[] arr2;
boolean res = Arrays.equals(arr1, arr2);

圆环数组

如果这个数组是一个圆环，那么我们在取下标的时候，假设当前下标是 i：

• 前一个下标：(i - 1 + len) % len
• 后一个下标：(i + 1 + len) % len，或者 (i + 1) % len

List 快速排序

// List<Integer> list
Collections.sort(list); // 该方法返回值是 void

List<String> 转 String[]

ex：剑指 Offer II 086. 分割回文子字符串 - 力扣（LeetCode） (opens new window)

// List<String> list
list.toArray(new String[list.size()]);

List<String[]> 转 String[][]

ex：剑指 Offer II 086. 分割回文子字符串 - 力扣（LeetCode） (opens new window)

// List<String> list
list.toArray(new String[list.size()][]);

String[] 转 List<String>

ex：剑指 Offer II 109. 开密码锁 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

// String[] str;
List<String> list = Arrays.asList(str);

// 等价于
List<String> list = new ArrayList<>(str);
// Arrays.asList 底层就是调用的 new ArrayList<>()

String[] 转 Set<String>

Set 的构造函数只接受 Collection 集合对象

所以不能直接用下面代码：

// String[] str
Set<String> set = new HashSet<>(str); // false

得把数组转成 list 集合再调用 set 构造函数

// String[] str
Set<String> set = new HashSet<>(Arrays.asList(str)); // true

List<Integer> 转 int[]

ex: 剑指 Offer II 113. 课程顺序 - 力扣（LeetCode） (opens new window)

// List<integer> list;
int[] arr = list.stream().mapToInt(Integer::intValue).toArray();

先转成 IntStream，再转成 int[]

等同于：

// List<Integer> list;
IntStream intStream = list.stream().mapToInt(Integer::intValue);
int[] num = intStream.toArray();

如下面这样写会报错，List<Integer> 调用 toArray 生成的是 Integer[] 而不是 int[]

int[] 转 List<Integer>

ex：349. 两个数组的交集 - 力扣（LeetCode） (opens new window)

注意不能像 String[] 转 List<String> 这样转换：

// int[] arr;
List<Integer> list = new ArrayList<>(Arrays.asList<>(arr));

ArrayList 的构造函数需要接收形如 List<Integer> 的构造参数，而不能是 List<int> 这样的

所以我们需要先把 int[] 转成 Integer[]

// int[] arr
Integer[] arrInteger = Arrays.stream(arr).boxed().toArray(Integer[]::new);
List<Integer> list = Arrays.asList(arrInteger);
// Set<Integer> set = new HashSet<>(Arrays.asList(arrInteger));

记不住就直接 for-each 遍历添加吧，还简单点：

// int[] arr
List<Integer> list = new ArrayList<>();
for (int num : arr) {
    list.add(num);
}

Map 中添加元素

ex: 剑指 Offer II 113. 课程顺序 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

// Map<String, List<String>> map;
map.putIfAbsent("xxx", new ArrayList<>()); // 若 key 不存在，则添加 key
map.get("xxx").append("111"); // 为 key 对应的 value 赋值

// Map<String, Integer> map;
map.putIfAbsent("xxx", 0); // 若 key 不存在，则添加 key
map.put("xxx", map.get("xxx") + 1); // 将 key 对应的 value 值 + 1