🧮 Algorithm Notebook
1、算法准备
1.1 牛客网编程OJ的典型输入输出
2、算法框架
2.1 动态规划
2.1.1 斐波那契数列
2.1.2 背包问题
2.1.3 贪心算法
2.1.4 序列和数组类问题
2.1.5 编辑距离
2.1.6 高楼扔鸡蛋
2.1.7 股票问题系列通解
2.1.8 最长有效括号
2.1.9 剪绳子
2.1.10 正则表达式匹配
2.2 二分查找
2.2.1 二分查找框架
2.2.2 搜索旋转排序数组
2.3 链表
2.3.1 反转链表
2.3.2 相交链表
2.3.3 合并链表
2.3.4 链表中倒数第k个节点
2.3.5 复制带随机指针的链表
2.4 排序算法
2.4.1 常见排序算法
2.5 二叉树
2.5.1 二叉树遍历
2.5.2 岛屿问题
2.5.3 二叉树路径问题
2.5.4 构造二叉树
2.6 回溯算法
2.6.1 回溯算法解题框架
2.6.2 N皇后
2.7 数组
2.7.1 删除有序数组中的重复项
2.7.2 滑动窗口最大值
2.7.3 调整数组顺序使奇数位于偶数前面
2.7.4 螺旋矩阵
2.7.5 多数元素
2.7.6 最大数
2.7.7 和为s的两个数字
2.7.8 构建乘积数组
2.7.9 两数之和
2.8 字符串
2.8.1 最小覆盖子串
2.8.2 比较版本号
2.8.3 验证IP地址
2.8.4 基本计算器 II
2.8.5 字符串解码
2.8.6 移掉 K 位数字
2.8.7 无重复字符的最长子串
2.8.8 第一个只出现一次的字符
2.8.9 翻转字符串里的单词
2.8.10 字符串转换整数 (atoi)
2.8.11 字符串四则运算
2.9 栈
2.9.1 最小栈
2.9.2 弹出序列
2.10 数学
2.10.1 用 Rand7() 实现 Rand10()
2.10.2 只出现一次的数字
2.10.3 整数反转
2.10.4 求1+2+…+n
2.10.5 二进制中1的个数
2.10.6 幂运算
2.10.7 1~n 整数中 1 出现的次数
2.10.8 数字序列中某一位的数字
2.10.9 丑数
2.10.10 n个骰子的点数
2.10.11 圆圈中最后剩下的数字
2.10.12 不用加减乘除做加法
2.10.13 x 的平方根
2.11 设计
2.11.1 LRU 缓存机制
-
+
游客
注册
登录
牛客网编程OJ的典型输入输出
> 记得自己以前一直在[Leetcode](https://leetcode-cn.com)上刷题,只需要自己写方法的具体逻辑,不用考虑输入输出的问题,直到第一次面试字节的时候才知道原来有的面试是使用的一块白板,程序的输入、输出,甚至导包都需要自己来写,因此结果可想而知 😭,因此决定对[牛客网](https://www.nowcoder.com)上常见的输入输出进行总结,避免在面试的时候再次踩雷 💣,让自己可以更加专注于具体的逻辑,提升自己面试通过的概率 😉。 > 大家在熟悉了下面的输入输出模板后可以使用[OJ 在线编程常见输入输出练习场](https://ac.nowcoder.com/acm/contest/5652)来进行练习。 ## 刷题平台 - [LeetCode](https://leetcode.cn) - [牛客网](https://www.nowcoder.com) - [AcWing](www.acwing.com) - [炼码](www.lintcode.com) - [GeeksforGeeks](practice.geeksforgeeks.org) - [InterviewBit](www.interviewbit.com) ## 编辑器 ### 包导入 - 一般的 `Scanner`、`List`、`Map` 等直接使用 `import java.util.*` 即可。 - 其它的特殊类,如并发相关的 `ConcurrentHashMap` 等则需要单独导入。 - 常见的包导入方法如下: ~~~java import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.locks.Lock; import java.util.concurrent.locks.ReentrantReadWriteLock; import java.util.concurrent.locks.ReentrantReadWriteLock.ReadLock; import java.util.concurrent.locks.ReentrantReadWriteLock.WriteLock; import java.util.concurrent.Executors; import java.util.concurrent.ScheduledExecutorService; import java.util.concurrent.TimeUnit; ~~~ ### 数据结构 #### PriorityQueue - 构造一个逆序队列:`PriorityQueue<Integer> secondQueue = new PriorityQueue<>((a, b) -> b - a);` - 添加元素:`offer(E)` - 移除队头元素:`poll()` - 获取队头元素:`peek()` - 删除指定元素:`remove(Object)` #### ArrayDeque - 添加队头/队尾元素:`offerFirst(E)/offerLast(E)` - 移除队头/队尾元素:`removeFirst()/removeLast()` - 获取队头/队尾元素:`peekFirst()/peekLast()` #### String - 拆分元素:`split(regex, limit)`,`limit` 参数控制模式应用的次数,会影响所得数组的长度: - 如果 n > 0,则模式将被最多应用 n - 1 次,数组的长度将不会大于 n,而且数组的最后一项将包含所有超出最后匹配的定界符的输入。 - 如果 n < 0,那么模式将被应用尽可能多的次数,而且数组可以是任何长度。 - 如果 n = 0,那么模式将被应用尽可能多的次数,数组可以是任何长度,并且结尾**空字符串**将被丢弃。 - 将字符串转换为字符数组:`toCharArray()` - 去除数字字符串的前导 0:`replaceFirst("^0*", "")` - 将元素按照指定分隔符拼接:`join(delimiter, elements)` > `elements` 需要为 `Iterable`,比如 `List`、`Set`。 #### Character - 判断字符是否为数字:`Character.isDigit(c)` - 将字符转换为大写/小写:`Character.toUpperCase(c)/Character.toLowerCase(c)` #### LinkedList > 可以当做栈来使用。 - 添加栈底元素:`addLast(E)` - 移除栈底元素:`removeLast()` #### LinkedHashMap > 有序哈希表。 - `key` 是 **按照插入顺序排列** 的,这样当需要查找序列中较为靠前的 `key` 时,相比于直接遍历原来的序列可以减少遍历的次数。 #### Collections - 获取一个集合中的最小值:`min( Collection<? extends T> coll)` #### Map - 获取键对应的值(不存在该键时带一个默认值):`getOrDefault(key, defaultValue)` - 遍历: ```java for (Map.Entry<Integer, DLinkNode> entry: map.entrySet()) { if (entry.getValue() == node) {map.remove(entry.getKey());break;} } ``` #### Lock - 获取读写锁: ```java ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock(); ReadLock readLock = readWriteLock.readLock(); WriteLock writeLock = readWriteLock.writeLock(); readLock.lock(); try { // ... } finally { // release read lock readLock.unlock(); } ``` #### TimeUnit - 秒:`TimeUnit.SECONDS` #### ScheduledExecutorService - 初始化: ```java ScheduledExecutorService scheduledExecutorService = Executors.newScheduledThreadPool(capacity); ``` - 创建定时任务: ```java scheduledExecutorService.schedule(new Runnable() { public void run() { // ... } }, expireTime, TimeUnit.SECONDS); ``` ## 典型实例 ### 输入是已知大小的数组 > 第一行是一个整数 $n$,表示二维数组有 $n$ 行 $n$ 列。 **Java**: ```java import java.util.Scanner; Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int[][] arr = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { arr[i][j] = scan.nextInt(); } } ``` ### 输入的每组测试数据有多行的情况 > 第一行是一个正整数 $m$,表示有 $m$ 组测试数据,之后每组数据有三行,第一行为 $n$($ 1 \le n \le 10000 $),第二行有 $n$ 个正整数,第三行也有 $n$ 个正整数,都在整数范围内。 > 示例: > 3 > 3 > 1 2 3 > 1 2 3 > 4 > 4 3 2 1 > 1 1 1 1 > 2 > 1 2 > 10 20 ```java import java.util.Arrays; import java.util.Scanner; Scanner scan = new Scanner(System.in); int m = scan.nextInt(); while (m > 0) { m--; int n = scan.nextInt();; int[] a = new int[n]; int[] b = new int[n]; for (int i = 0; i < n; i++) { a[i] = scan.nextInt(); } for (int i = 0; i < n; i++) { b[i] = scan.nextInt(); } System.out.println(Arrays.toString(a)); System.out.println(Arrays.toString(b)); } ``` ### 每行测试数据的数量在该行开头给出 > 第一行是一个正整数 $m$,表示有 $m$ 组测试数据,之后每组数据第一个数为 $n$($ 1 \le n \le 10000 $),紧接着有 $n$ 个正整数(注意在一行)。 > 示例: > 2 > 3123 > 41234 ```java import java.util.Arrays; import java.util.Scanner; Scanner scan = new Scanner(System.in); int m = scan.nextInt(); while (m > 0) { m--; String s = scan.next(); int n = s.charAt(0) - '0'; int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = s.charAt(i + 1) - '0'; } System.out.println(Arrays.toString(arr)); } ``` ### 测试数据组数未知 > 输入数据有多组,每行表示一组输入数据,每行不定有 $n$ 个整数,用空格隔开。 ```java import java.util.Scanner; Scanner scan = new Scanner(System.in); while (scan.hasNextLine()) { String s = scan.nextLine(); String[] arr = s.split(" "); int sum = 0; for (int i = 0; i < arr.length; i++) { sum += Integer.parseInt(arr[i]); } System.out.println(sum); } ``` ## 注意事项 ### Java 中 next()、nextInt()和 nextLine()的用法及区别 1. `next()`、`nextInt()` 和 `nextLine()` 都是 Scanner 内置的方法,他们的区别主要在于对于**空格的处理方式**及**返回值**的不同: 1. **空格的处理方式**: 1. `next()` 和 `nextInt()`**遇到空格时会停止读取**,返回的结果为**空格前读取的部分**。 2. `nextLine()`**从指针的当前位置开始读取**,**遇到换行符时会停止读取**,返回**换行符前读取的部分**。 2. **返回值**: 1. `next()` 和 `nextLine()` 的返回值为 `String` 类型。 2. `nextInt()` 的返回值为 `int` 类型。 ## 参考文献 - [牛客网编程 OJ 的典型输入 Java 模板](https://www.cnblogs.com/treasury/p/13285997.html) - [java 中 next(),nextInt(),nextLine()的用法及区别](https://blog.csdn.net/qq_45445841/article/details/104824176)
ricear
2023年5月31日 16:16
©
BY-NC-ND(4.0)
转发文档
收藏文档
上一篇
下一篇
手机扫码
复制链接
手机扫一扫转发分享
复制链接
Markdown文件
分享
链接
类型
密码
更新密码