面试刷算法,这些api不可不知!

简介: 面试刷算法,这些api不可不知!

   

大家好,我是老三,最近在刷算法,发现有些api记得不熟,所以整理了一波,如果你也在刷题,赶紧收藏吧!

集合

在刷题中,各种数据结构是我们常常用到的,例如栈实现迭代、哈希存储键值对等等,我们来看看常用集合和相关api。

类/接口 描述 方法
String 字符串 charAt toCharArray split substring indexOf lastIndexOf replace length
List 列表 add remove get size subList
Stack push pop peek isEmpty size
Queue 队列 offer poll peek isEmpty size
Deque 双向队列 offerFirst offerLast pollFirst pollLast peekFirst peekLast isEmpty size
PriorityQueue 优先队列 offer poll peek isEmpty size
Set add remove contains isEmpty size first(TreeSet) last(TreeSet)
Map put get getOrDefault containsKey containsValue keySet values isEmpty size

数组

数组就不用多说什么了,大家最熟悉的数据结构。

Arrays

Arrays是比较常用的数组工具类,可以完成排序、拷贝等功能。

  • 从小到大排序:Arrays.sort(int[] arr)Arrays.sort(int[] arr, int fromIndex, int toIndex)
Arrays.sort(int[] arr, int fromIndex, int toIndex, 比较器);   //一定是需要泛型
Arrays.sort(arr, (o1, o2) -> o2 - o1);   //数组全部 从大到小排序 跟Collections.sort()一样
Arrays.sort(arr, 0, 3, (o1, o2) -> o2 - o1);   //从大到小排序,只排序[0, 3)
  • 拷贝:Array.copyOf
int[] a = new int[5];
int[] newA = Array.copyOf(a, 5);

列表

列表主要有两种实现,分别是顺序表链表

image.png

顺序表本质是一个可以动态扩容的数组,在Java中的实现是ArrayList

链表是一个双向链表,Java中链表的实现为LinkedListLinkedList在Java中可谓是非常强大的一个集合类,它还可以作为双向队列、栈来使用。

注意,ArrayList的扩容需要将旧的数组的元素复制到新的数组,时间复杂度为O(n)。

基本方法

  • 构造
List<Integer> array = new ArrayList<>();    // 顺序表
// Set<Integer> a = new HashSet....
List<Integer> b = new ArrayList<>(a);     //接受一个集合容器
  • get
get(int index)    // 返回元素位置在index的元素e --- array O(1), list O(n)
  • size
size()    // 返回数组/链表长度 --- O(1)
  • add
add(E e)    // 在尾部添加一个元素e --- O(1)
add(int index, E e)    // 在index位置插一个元素e --- O(n)
  • remove
.remove(int index)    // 删除位于index的元素,并返回删除元素e --- 删除最后元素为O(1), 其余为O(n)
//删除最后元素 list.remove(list.size() - 1);
  • subList
.subList(int from, int to)    // 相当于返回原数组的一个片段,但不要对其进行改动,改动会影响原数组 --- O(1)
// List<Integer> list, 对原来的list和返回的list做的“非结构性修改”(non-structural changes),
//都会影响到彼此对方. 如果你在调用了sublist返回了子list之后,如果修改了原list的大小,那么之前产生的子list将会失效,变得不可使用

集合工具

Collections是集合工具类,提供了一些操作集合的方法。

  • 排序
Collections.sort(list); 从小到大排序
Collections.sort(list, (o1, o2) -> o2 - o1); 从大到小排序, 第二个参数为一个比较器

两种实现,ArrayList利于查找,LinkedList利于增删。

大概对比如下:

操作 ArrayList LinkedList
get(int index) O(1) O(n),平均 n / 4步
add(E element) 最坏情况(扩容)O(n) ,平均O(1) O(1)
add(int index, E element) O(n) ,平均n / 2步 O(n),平均 n / 4步
remove(int index) O(n) 平均n /2步 O(n),平均 n / 4步

Java中定义了Stack接口,实现类是VectorVector是一个祖传集合类,不推荐使用。

那应该用什么呢?

Deque接口实现了完善堆栈操作集合,它有一个我们熟悉的实现类LinkedList

image.png

  • 构造
Deque<Integer> stack=new LinkedList<>();
  • push
push(E e);    // 入栈元素e, 返回值为元素e --- O(1)
  • pop
.pop();    // 出栈一个元素,返回出栈元素e --- O(1)
  • peek
peek();    // 查看栈顶元素, 返回值为栈顶元素e --- O(1)
  • isEmpty
isEmpty()    // 若栈空返回true, 否则返回false --- O(1)
  • size
size()    // 返回栈中元素个数 --- O(1)

队列

队列s是一种先进先出的结构,在Java中的接口定义是Queue,具体实现还是我们的老朋友LinkedList

  • 构造
Queue<Integer> q = new LinkedList<>();
  • offer
offer(E e);    // 队尾加入元素e。 若成功入队返回值true,否则返回false --- O(1)
  • poll
poll();    // 出队头,返回出队元素e --- O(1)
  • peek
peek();    // 查看队头元素, 返回值队首元素e --- O(1)
  • isEmpty
isEmpty()    // 若队空返回true, 否则返回false --- O(1)
  • size
size()    // 返回队中元素个数 --- O(1)

双向队列

Queue有一个子接口Dueue,即双向队列,和单向队列不同,它的出队入队可以从两个方向。

image.png

  • 构造
Dueue<Integer> q = new LinkedList<>();
  • offFirst
offFirst(Object e)   // 将指定元素添加到双端队列的头部 --- O(1)
  • offLast
offLast(Object e)   //将指定元素添加到双端队列的尾部 --- O(1)
  • pollFirst
pollFirst()   //获取并删除双端队列的第一个元素 --- O(1)
  • pollLast
pollLast()   //获取并删除双端队列的最后一个元素 --- O(1)
  • peekFirst
peekFirst()   //获取但不删除双端队列的第一个元素 --- O(1)
  • peekLast
peekLast()   //获取但不删除双端队列的最后一个元素 --- O(1)

优先队列

优先队列是一种比较特殊的队列,保存队列元素的顺序不是按照元素添加的顺序来保存的,而是在添加元素的时候对元素的大小排序后再保存。

所以在队头的元素不是按照先后顺序,而是按照大小顺序。

在Java中的实现是PriorityQueue,底层是一棵树, 以小根堆为例。对于任意结点来说,该节点的值比其左右孩子的值都要小。 (就是最上面的结点最小)。 大根堆类似,最上面结点最大

  • 构造    
  • 小根堆
Queue<Integer> minH = new PriorityQueue<>();    // 小根堆,默认大小为11 相当于  new PriorityQueue<>(11)
Queue<Integer> minH = new PriorityQueue<>(100);  // 定义一个默认容量有100的小根堆。在当中增加元素会扩容,只是开始指定大小。不是size,是capacity
  • 大根堆
Queue<Integer> maxH = new PriorityQueue<>((i1, i2) -> i2 - i1);    // 大根堆,默认大小为11 相当于  new PriorityQueue<>(11, (i1, i2) -> i2 - i1)
Queue<Integer> maxH = new PriorityQueue<>(100, (i1, i2) -> i2 - i1);    // 定义一个默认容量有100的大根堆。在当中增加元素会扩容,只是开始指定大小
  • offer
offer(E e);    // 在堆中加入元素e,并调整堆。若成功入堆返回值true,否则返回false --- O(logN)
  • poll
poll();    // 弹出堆顶元素,并重新调整堆,返回出队元素e --- O(logN)
  • peek
peek();    // 查看堆顶元素, 返回值堆顶元素e --- O(1)

散列表

散列表示一种<key,value>型的数据结构,在Java中的实现是HashMap

  • 构造
Map<Characters, Integer> map = new HashMap<>();
  • put
put(K key, V value);    // 在Map中加入键值对<key, value>。返回value值。如果Map中有key,则replace旧的value --- O(1)
  • get
get(K key);    // 返回Map中key对应的value。若Map中没有该key,则返回null --- O(1)
  • getOrDefault
getOrDefault(K key, V defaultValue);    // 返回Map中key对应的value。若Map中没有该key,则返回defaultValue --- O(1)
// For example:
// Map<Character, Integer> map = new HashMap<>();
// if (...)    // 如果发现k,则k在Map中的值加1。没一开始没有k,则从0开始加1。(相当于给了key在Map中的一个初试值)
    map.put('k', map.getOrDefault('k', 0) + 1);
  • containsKey
containsKey(Key key);    // 在Map中若存在key,则返回true,否则返回false --- O(1)
get(x) == null // 可以代替改用法
  • keySet
keySet();    // 返回一个Set,这个Set中包含Map中所有的Key --- O(1)
// For example:
// We want to get all keys in Map
// Map<Character, Integer> map = new HashMap<>();
for (Character key : map.keySet()) {
    // Operate with each key
}
  • values
values();    // 返回一个Collection<v>,里面全是对应的每一个value --- O(1)
// For example:
// We want to get all values in Map
// Map<Character, Integer> map = new HashMap<>();
for (Integer value : map.values()) {
    // Operate with each values
}
  • isEmpty
isEmpty()    // 若Map为空返回true, 否则返回false --- O(1)
  • size
.size()    // 返回Map中中键值对<K, V>的个数 --- O(1)

Set

Set是一种没有重复元素的集合,常用的实现是HashSet

  • 构造
Set<Integer> set = new HashSet<>();
List<Integer> list = new ArrayList<>....;
Set<Integer> set = new HashSet<>(list);
  • add
.add(E e);    // 在集合中添加元素E e, 若成功添加则返回true,若集合中有元素e则返回false --- O(1)
  • remove
remove(E e);    // 在集合中删除元素e,若删除成功返回true;若集合中没有元素e,返回false --- O(1)
  • contains
contains(E e);    // 若存在元素e,则返回true,否则返回false --- O(1)
  • isEmpty
isEmpty()    // 若集合为空返回true, 否则返回false --- O(1)
• 1
  • size
isEmpty()    // 若集合为空返回true, 否则返回false --- O(1)
  • first
first()    // 返回集合里的最小值(若给了比较器从大到小则是返回最大值)
  • last
last()    // 返回集合里的最大值(若给了比较器从大到小则是返回最小值)

字符串

String

不可变量(相当于只读final修饰),每个位置元素是个char。

  • 初始化

字符串复制初始化

String s = ``"abc"``;

基于另外一个字符串

// s = "abc"``String s2 = ``new` `String(s);

基于char[]

// s = "abc";
// char[] c = s.toCharArray();
String s3 = new String(c);
// 可以偏移
// public String(char value[], int offset, int count)
String s4 = new String(c, 1, 2);    // [offset, offset + count) [)
// 把char[] 变成字符串
char[] ch = {'a', 'b', 'c'};
String.valueOf(ch);
  • charAt
charAt(int index);    // 返回index位置的char --- O(1)
  • length
length();    // 返回字符串长度 --- O(1)
  • substring
substring(int beginIndex, int endIndex);    // 返回字符片段[beginIndex, endIndex) --- O(n)
substring(int beginIndex);    // 返回字符片段[beginIndex, end_of_String) 就是从beginIndex开始后面的 ---- O(n)
  • indexOf
indexOf(String str)    // 返回str第一个出现的位置(int),没找到则返回-1。 --- O(m * n) m为原串长度, n为str长度
// (假如要找一个字符char c,str可以表示成String.valueOf(c),然后作为参数传进去.
s.indexOf(String str, int fromIndex);    // 同上,但从fromIndex开始找 --- O(m * n)
  • lastIndexOf
lastIndexOf(String str);    // 返回str最后出现的位置(int),没找到则返回-1。 --- O(m * n) m为原串长度, n为str长度
// (假如要找一个字符char c,str可以表示成String.valueOf(c),然后作为参数传进去.
lastIndexOf(String str, int fromIndex);    // 同上,
//但从fromIndex开始从后往前找 [0 <- fromIndex] --- O(m * n)
  • replace
replace(char oldChar, char newChar);    // 返回一个新字符串String,其oldChar全部变成newChar --- O(n)
  • toCharArray
toCharArray();   // 返回char[] 数组。 把String编程字符数组 --- O(n)
• 1
  • trim
trim();    // 返回去除前后空格的新字符串 --- O(n)
  • split
split(String regex);    // 返回 String[],以regex(正则表达式)分隔好的字符换数组。 ---- O(n)
// For example
// 从非"/"算起 若"/a/c" -> 会变成"" "a" "c"
String[] date = str.split("/");     // date[0]:1995 date[1]:12 date[2]:18 --- O(n)
  • toLowerCase, toUpperCase
s = s.toLowerCase();    // 返回一个新的字符串全部转成小写 --- O(n)
s = s.toUpperCase();    // 返回一个新的字符串全部转成大写 --- O(n)

StringBuilder

由于String是所谓的不可变类,使用 str+这种形式拼接字符串实际上,是JVM帮助循环创建StringBuilder来拼接,所以拼接字符串最好用StringBuilder。

  • 构造
StringBuilder sb = new StringBuilder();
  • charAt
charAt(int index);    // 返回index位置的char --- O(1)
  • length
length();    // 返回缓冲字符串长度 --- O(1)
  • apped
append(String str)   // 拼接字符串 --- O(n)
  • toString
toString();    // 返回一个与构建起或缓冲器内容相同的字符串 --- O(n)

数学

最大最小值

在一些题目里,需要用到最大,最小值,Java中各个数据类型的最大最小值定义如下:

fmax = Float.MAX_VALUE;
fmin = Float.MIN_VALUE;
dmax = Double.MAX_VALUE;
dmin = Double.MIN_VALUE;
bmax = Byte.MAX_VALUE;
bmin = Byte.MIN_VALUE;
cmax = Character.MAX_VALUE;
cmin = Character.MIN_VALUE;
shmax = Short.MAX_VALUE;
shmin = Short.MIN_VALUE;
imax = Integer.MAX_VALUE;
imin = Integer.MIN_VALUE;
lmax = Long.MAX_VALUE;
lmin = Long.MIN_VALUE;

Math

  • max
Math.max(long a, long b);    //返回两个参数中较大的值
  • sqrt
Math.sqrt(double a);    //求参数的算术平方根
  • abs
Math.abs(double a);  //返回一个类型和参数类型一致的绝对值
  • pow
Math.pow(double a, double b);  //返回第一个参数的第二个参数次方。
  • ceil
Math.ceil(double x);   //向上取整
  • floor
Math.floor(double x);  //向下取整
  • round
Math.round(double x);   //四舍五入


“简单的事情重复做,重复的事情认真做,认真的事情有创造性地做!”——

我是三分恶,一个能文能武的全栈开发。

点赞关注不迷路,咱们下期见!



目录
相关文章
|
3月前
|
负载均衡 NoSQL 算法
一天五道Java面试题----第十天(简述Redis事务实现--------->负载均衡算法、类型)
这篇文章是关于Java面试中Redis相关问题的笔记,包括Redis事务实现、集群方案、主从复制原理、CAP和BASE理论以及负载均衡算法和类型。
一天五道Java面试题----第十天(简述Redis事务实现--------->负载均衡算法、类型)
|
19天前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩分享分库分表的基因算法设计,涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容,助力面试者应对大厂技术面试,提高架构设计能力。
美团面试:百亿级分片,如何设计基因算法?
|
25天前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
28 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
13天前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
19天前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩在读者群中分享了关于分库分表的基因算法设计,旨在帮助大家应对一线互联网企业的面试题。文章详细介绍了分库分表的背景、分片键的设计目标和建议,以及基因法的具体应用和优缺点。通过系统化的梳理,帮助读者提升架构、设计和开发水平,顺利通过面试。
美团面试:百亿级分片,如何设计基因算法?
|
27天前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
59 2
|
30天前
|
机器学习/深度学习 算法 API
机器学习入门(五):KNN概述 | K 近邻算法 API,K值选择问题
机器学习入门(五):KNN概述 | K 近邻算法 API,K值选择问题
|
2月前
|
机器学习/深度学习 JavaScript 算法
面试中的网红虚拟DOM,你知多少呢?深入解读diff算法
该文章深入探讨了虚拟DOM的概念及其diff算法,解释了虚拟DOM如何最小化实际DOM的更新,以此提升web应用的性能,并详细分析了diff算法的实现机制。
|
3月前
|
消息中间件 存储 算法
这些年背过的面试题——实战算法篇
本文是技术人面试系列实战算法篇,面试中关于实战算法都需要了解哪些内容?一文带你详细了解,欢迎收藏!
|
3月前
|
JavaScript 算法 索引
【Vue面试题二十三】、你了解vue的diff算法吗?说说看
这篇文章深入分析了Vue中的diff算法,解释了其在新旧虚拟DOM节点比较中的工作机制,包括同层节点比较、循环向中间收拢的策略,并通过实例演示了diff算法的执行过程,同时提供了源码层面的解析,说明了当数据变化时,如何通过Watcher触发patch函数来更新DOM。
【Vue面试题二十三】、你了解vue的diff算法吗?说说看