CS-Wiki CS-Wiki
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
  • 刷题模板汇总
  • 一些刷题小技巧
    • 位运算
      • 左移 <<1 表示 乘以 2,右移 >>1 表示除以 2
      • 获取一个 int 类型整数每个位置上的 2 进制数位
      • 从高位向低位(从左往右)计算两个整数的异或结果
    • 字符串
      • 判断字符串 1 是否以 字符串 2 开头
      • 判断字符串中的某个字符是否是数字或字母
      • 某个字符转小写
    • 集合与数组
      • 数组复制
      • 数组快速求和
      • 数组快速排序
      • 快速判断两个数组是否相同
      • 圆环数组
      • List 快速排序
      • List<String> 转 String[]
      • List<String[]> 转 String[][]
      • String[] 转 List<String>
      • String[] 转 Set<String>
      • List<Integer> 转 int[]
      • int[] 转 List<Integer>
      • Map 中添加元素
  • 整数 and 位运算

  • 数组

  • 链表

  • 哈希表

  • 字符串

  • 栈

  • 队列

  • 二叉树

  • 前缀树

  • 二分查找

  • 双指针法

  • 区间求和问题

  • 排序

  • 回溯算法

  • 贪心算法

  • 动态规划

  • 图

  • 数学

  • 自动机

  • 海量数据和空间限制

  • 05-数据结构与算法
小牛肉
2022-05-04
目录

一些刷题小技巧

# 一些刷题小技巧

# 位运算

# 左移 <<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

🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~

帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10
刷题模板汇总
整数理论基础

← 刷题模板汇总 整数理论基础→

最近更新
01
02
线上环境 CPU 使用率飙升如何快速排查?
03-05
03
面试官再跟你说中国没有根服务器,雪人计划让他了解下
02-23
更多文章>
Theme by Vdoing | Copyright © 2019-2023 飞天小牛肉 | 皖ICP备2022008966号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式