几率大的现场手撕算法面试题（含答案）

清疚 2022-04-25 04:22 224阅读 0赞

其他面试题类型汇总：  
[Java校招极大几率出的面试题（含答案）----汇总][Java_----]  
[几率大的网络安全面试题（含答案）][Link 1]  
[几率大的多线程面试题（含答案）][Link 2]  
[几率大的源码底层原理，杂食面试题（含答案）][Link 3]  
[几率大的Redis面试题（含答案）][Redis]  
[几率大的linux命令面试题（含答案）][linux]  
[几率大的杂乱+操作系统面试题（含答案）][Link 4]  
[几率大的SSM框架面试题（含答案）][SSM]  
[几率大的数据库（MySQL）面试题（含答案）][MySQL]  
[几率大的JVM面试题（含答案）][JVM]  
[几率大的现场手撕算法面试题（含答案）][Link 5]  
[临时抱佛脚必备系列（含答案）][Link 6]  
**注：知识还在积累中，不能保证每个回答都满足各种等级的高手们，若发现有问题的话，本人会尽快完善。  
｡◕‿◕｡**

现场手撕算法面试题个人经历比较少，但会收集网上面经，一般线下要求手撕算法的次数更多，其次就是来个共享链接自己在电脑上写代码。这个系列将会持续更新。

**重点：《剑指Offer》共60道题左右，务必要会编写！！！重点思路要有，因为比较常规的笔试经常能找原题或者思路相同的题，在此就统一在此编写了。建议取牛客网查看，那有个编程平台！！！**

## 先提前了解一些常用的类以及方法： ##

**类 Scanner**：  
从控制台输入：  
方法一：

Scanner sc = new Scanner(System.in); //构造一个Scanner对象实例
    String queue = sc.next(); //接受控制台输入

125000000  
输出  
1

Scanner in = new Scanner(System.in);
     int x0 = in.nextInt();

\*\*next（）\*\*一定要读取到有效字符后才可以结束输入，对输入有效字符之前遇到的空格键、Tab键或Enter键等结束符，next（）方法会自动将其去掉  
\*\*nextLine（）\*\*方法的结束符只是Enter键，即nextLine（）方法返回的是Enter键之前的所有字符，它是可以得到带空格的字符串的。

**方法二：**

//Scanner sc = new Scanner(System.in);
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String p = br.readLine();

String\[\] s1 = p.trim().split(" ");//忽略前导空白和尾部空白，并按空格分割开成多个String数组

String\[\] split(String regex, int limit)  
根据匹配给定的正则表达式来拆分此字符串

ListNode h = new ListNode(0);//定义一个新的链表来存放结果

XXX nextXXX() 输入XXX（基本数据类型）类型的

**使用户能够从 System.in 中读取一个数：**  
Scanner sc = new Scanner(System.in);  
int i = sc.nextInt();  
String next() 查找并返回来自此扫描器的下一个完整标记。  
int nextInt() 将输入信息的下一个标记扫描为一个 int。  
同理nextXXX():

**创建一个ArrayList数组。元素类型为Integer**  
List lists = new ArrayList<>();  
list.add(1); 添加元素  
list.add(2);  
list.add(3);  
list.add(4);  
list.add(5);  
类型为TreeNode  
ArrayList queue = new ArrayList<>()

### ArrayList的基本的增删改查： ###

增：boolean add(E e) ； boolean addAll(Collection<? extends E> c)  
删：E remove(int index) 移除此列表中指定位置上的元素，并返回该删除的元素  
改：E set(int index, E element) 用指定的元素替代此列表中指定位置上的元素。并返回修改前的元素  
查：  
E get(int index)返回此列表中指定位置上的元素  
int size() 返回此列表中的元素数。 不用length  
Object\[\] toArray() 按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组。  
boolean isEmpty()如果此列表中没有元素，则返回 true  
必须掌握的类的常用函数：添加，删除，转换成其他类型

### Integer ###

static int parseInt(String s) 将字符串参数作为有符号的十进制整数进行解析 ‘2’–》 2

把特定的字符串转化成int变量 如：  
String string = “123”  
1）int s = Integer.parseInt(string);  
2）int s = new Integer(string);

### String类 ###

String\[\] split(String regex) 根据给定正则表达式的匹配拆分此字符串,变成String字符串数组

str11 = "a,b,c,d";
    String[] strings = str11.split(",");
    for (String s1 : strings){
        System.out.print(s1 + " ");//a b c d
    }

例如输入为数组 \[3, 6, 9, 12\] String\[\] a=str.split(","); ==>\{3,6,9,12\}

char charAt(int index) 从String字符串中返回指定索引处的 char 值 比如：返回字符串的第一个字符  
char\[\] toCharArray() 将此字符串转换为一个新的字符数组。

String的构造函数支持将byte\[\],int\[\]，char\[\]转换成字符串，也可指定范围

boolean contains(CharSequence s)  
当且仅当此字符串包含指定的 char 值序列时，返回 true。 用于判断是否包含某字串（作弊啊）

String concat(String str) 将指定字符串连接到此字符串的结尾。

boolean contentEquals(CharSequence cs) 将此字符串与指定的 CharSequence 比较。 比较两个字符串的内容是否一样  
//CharSequence的实现类CharBuffer, Segment, String, StringBuffer, StringBuilder，即参数可以是它们其中一个  
//当且仅当此 String 与指定序列表示相同的 char 值序列时，结果才为 true。

static String copyValueOf(char\[\] data)返回指定数组中表示该字符序列的 String。也课取某一段的 用于将某个char\[\]数组转换成字符串，或者截取char\[\]数组某个部分变成字符串

System.out.println(String.format("%s\_%s",str9,str10));//abcd\_ABCD 以后中格式输出，如类似C语言的打印时的%d

byte\[\] getBytes() 将字符串转换成byte\[\]数组

int indexOf(String str) 返回指定子字符串在此字符串中第一次出现处的索引。 可以确定字串在指定字符串的位置  
int indexOf(String str, int fromIndex) 从指定的索引开始。

boolean isEmpty() 当且仅当 length() 为 0 时返回 true，

System.out.println("".isEmpty());//true
    String str11 = "";
    System.out.println(str11.isEmpty());//str11为""或者null true

int lastIndexOf(String str) 返回指定子字符串在此字符串中最右边出现处的索引。  
int lastIndexOf(String str, int fromIndex) 从指定的索引开始反向搜索。

String  
replace(char oldChar, char newChar)  
返回一个新的字符串，它是通过用 newChar 替换此字符串中出现的所有 oldChar 得到的。 全部指定替换掉

CharSequence  
subSequence(int beginIndex, int endIndex) 获取一个子字符串。  
String  
substring(int beginIndex, int endIndex)  
返回一个新字符串，它是此字符串的一个子字符串。 区别在于subSequence的对象类型范围更大

String toUpperCase() 所有字符都转换为大写。

static String valueOf(char c)等 valueOf能将基本数据类型及其包装类，char\[\],Object（任意对象类型）转换成String字符串

### Stack: ###

new一个栈，其元素为Integer

Stack stack2 = new Stack<>();  
new一个栈，其元素为String

Stack stack2 = new Stack<>();  
主要函数：  
boolean empty()  
测试堆栈是否为空。  
E peek()  
查看堆栈顶部的对象，但不从堆栈中移除它。  
E pop()  
移除堆栈顶部的对象，并作为此函数的值返回该对象。  
E push(E item)  
把项压入堆栈顶部。  
int search(Object o)  
返回对象在堆栈中的位置，以 1 为基数。

新建一个等长的数组

int[] newArray = new int[array.length];
    
    String[] newArray = new String[array.length];

### LinkedList： ###

boolean add(E e)  
将指定元素添加到此列表的结尾。  
void add(int index, E element)  
在此列表中指定的位置插入指定的元素。  
void addFirst(E e)  
将指定元素插入此列表的开头。  
void addLast(E e)  
将指定元素添加到此列表的结尾。  
void clear()  
从此列表中移除所有元素。  
E get(int index)  
返回此列表中指定位置处的元素。  
E getFirst()  
返回此列表的第一个元素。  
E getLast()  
返回此列表的最后一个元素。  
boolean offer(E e)  
将指定元素添加到此列表的末尾（最后一个元素）。  
E peek()  
获取但不移除此列表的头（第一个元素）。  
E poll()  
获取并移除此列表的头（第一个元素）  
Object\[\] toArray()  
返回以适当顺序（从第一个元素到最后一个元素）包含此列表中所有元素的数组。

array[i]&1相当于取余；注意，要加（），优先级问题！！
    
    （array[i]&1） != 0  false奇数    true偶数
    
    或者（array[i]&1）==1表示奇数
    ListNode p, q;新建两个结点
    p = q = head;让他们都指向头指针，也就是相当于拷贝了两个链表

**递归树时常用的判断**

if(root == null)
            return;
        if(root.left == null && root.right == null)
            return;

**返回String类型的边界判断**

if(numbers==null || numbers.length==0) {
                return "";
            }

**返回的是字符串链表，因为要求返回所有可能满足条件的**  
public ArrayList Permutation(String str)  
<>里面装的是一个ArrayList元素的类型，此为一个ArrayListstring数组作为元素  
public ArrayList<public ArrayList>

**字符串转换成字符数组**：  
char\[\] chars = str.toCharArray() ;

### HashMap<K,V> ###

boolean containsKey(Object key) 判断是否存在该键，则返回 true。  
boolean containsValue(Object value) 判断是否存在该值，则返回 true。  
V get(Object key) 返回key对应的value值；如果对于该键来说，此映射不包含任何映射关系，则返回 null。  
boolean isEmpty() 是否为null，则返回 true。  
V put(K key, V value) 增加一个键值对  
V remove(Object key) 移除key对应的value（如果存在）。  
int size() key-value键值对的个数

## 二叉树 ##

### 层次遍历 ###

public static void BFSOrder(BinTree t)
        {
            if(t==null) return ;
            Queue<BinTree> queue = new ArrayDeque<BinTree>();    
            //队列小知识：使用offer和poll优于add和remove之处在于它们返回值可以判断成功与否，而不抛出异常
            queue.offer(t);              //进入队列
            while(!queue.isEmpty())
            {
                t=queue.poll ();           //当前节点出队列            System.out.print(t.date);
                if(t.lchild!=null)              //当前节点左孩子去排队，在前面哦                queue.offer(t.lchild);
                if(t.rchild!=null)            //右孩子排第二                queue.offer(t.rchild);    
            }
        }

### 前序遍历 ###

public void theFirstTraversal(Node root) {  //先序遍历          
            printNode(root);  
            if (root.getLeftNode() != null) {  //使用递归进行遍历左孩子              
                theFirstTraversal(root.getLeftNode());  
            }  
            if (root.getRightNode() != null) {  //递归遍历右孩子              
                theFirstTraversal(root.getRightNode());  
            }  
        }  
    
    
        public void theInOrderTraversal(Node root) {  //中序遍历  
            if (root.getLeftNode() != null) {  
                theInOrderTraversal(root.getLeftNode());  
            }  
            printNode(root);  
            if (root.getRightNode() != null) {  
                theInOrderTraversal(root.getRightNode());  
            }  
        }
    
        public void thePostOrderTraversal(Node root) {  //后序遍历  
            if (root.getLeftNode() != null) {  
                thePostOrderTraversal(root.getLeftNode());  
            }  
            if(root.getRightNode() != null) {  
                thePostOrderTraversal(root.getRightNode());  
            }  
            printNode(root);  
        }

## 单例模式 ##

手写常用的几个单例模式（懒汉模式和饿汉模式，线程安全等）  
构造方法定义为私有方法  
提供一个静态方法，  
**饿汉式（静态常量）**:在类装载的时候就完成实例化。避免了线程同步问题

public class Singleton {
    
        private final static Singleton INSTANCE = new Singleton();final修饰的静态实例
    
        private Singleton(){}  私有化构造器
    
        public static Singleton getInstance(){   提供一个静态的方法返回实例
            return INSTANCE;
        }
    }

**饿汉式（静态代码块）**

public class Singleton {
    
        private static Singleton instance;
    
        static {
            instance = new Singleton();
        }
    
        private Singleton() {}
    
        public static Singleton getInstance() {
            return instance;
        }
    }

**双重检查**： 优点：线程安全；延迟加载；效率较高。

public class Singleton {
    
        private static volatile Singleton singleton;   volatile类型的
    
        private Singleton() {}
    
        public static Singleton getInstance() {
            if (singleton == null) {
                synchronized (Singleton.class) {
                    if (singleton == null) {
                        singleton = new Singleton();
                    }
                }
            }
            return singleton;
        }
    }

**静态内部类**： JVM帮助我们保证了线程的安全性

public class Singleton {
    
        private Singleton() {}
    
        private static class SingletonInstance {
            private static final Singleton INSTANCE = new Singleton();
        }
    
        public static Singleton getInstance() {
            return SingletonInstance.INSTANCE;
        }
    }

**枚举\[推荐用\]**： 避免多线程同步问题， 还能防止反序列化重新创建新的对象。`public enum Singleton { INSTANCE; public void whateverMethod() {} }`

## 二分查找 ##

## 快速排序 ##

时间复杂度O(N^2)， 额外空间复杂度O(1)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0J1dHRlcmZseV9yZXN0aW5n_size_16_color_FFFFFF_t_70]

## 冒泡排序 ##

## 堆排序 ##

时间复杂度O(N\*logN)， 额外空间复杂度O(1)

堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值 （其父结点的值） 均 不大于（或不小于）其左孩子和右孩子节点的值。  
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。  
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。  
可以解决中位数（大根堆+小根堆） 可以解决贪心问题堆结构非常重要：1， 堆结构的heapInsert与heapify2， 堆结构的增大和减少3， 如果只是建立堆的过程， 时间复杂度为O(N)4， 优先级队列结构， 就是堆结构  
堆排序：  
1.先形成大根堆  
2.没排好的最后一个数与0（根）上的数交换  
3，重复的进行heapify  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0J1dHRlcmZseV9yZXN0aW5n_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0J1dHRlcmZseV9yZXN0aW5n_size_16_color_FFFFFF_t_70 3]

## 斐波那契青蛙跳系列 ##

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。时间复杂度O(n)

public class Solution {
        public int JumpFloor(int target) {
            if(target <= 0) return 0;
            if(target == 1) return 1;
            if(target == 2) return 2;
            int one = 1;
            int two = 2;
            int result = 0;
            for(int i = 2; i < target; i++){
                result = one+ two;
                one = two;
                two = result;
            }
            return result;
        }
    }

递归版：

public class Solution {
        public int JumpFloor(int target) {
            if (target <= 0) {
                return -1;
            } else if (target == 1) {
                return 1;
            } else if (target ==2) {
                return 2;
            } else {
                return  JumpFloor(target-1)+JumpFloor(target-2);
            }
        }
    }

**变形：**  
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

public class Solution {
        public int JumpFloorII(int target) {
            if (target <= 0) {
                return -1;
            } else if (target == 1) {
                return 1;
            } else {
                return 2 * JumpFloorII(target - 1);
            }
        }
    
    }

还有很多变形题，大家多算算前几次找找规律。

[Java_----]: https://blog.csdn.net/Butterfly_resting/article/details/89637697
[Link 1]: https://blog.csdn.net/Butterfly_resting/article/details/89638424
[Link 2]: https://blog.csdn.net/Butterfly_resting/article/details/89639414
[Link 3]: https://blog.csdn.net/Butterfly_resting/article/details/89668402
[Redis]: https://blog.csdn.net/Butterfly_resting/article/details/89668661
[linux]: https://blog.csdn.net/Butterfly_resting/article/details/89668744
[Link 4]: https://blog.csdn.net/Butterfly_resting/article/details/89669490
[SSM]: https://blog.csdn.net/Butterfly_resting/article/details/89670153
[MySQL]: https://blog.csdn.net/Butterfly_resting/article/details/89704636
[JVM]: https://blog.csdn.net/Butterfly_resting/article/details/89705057
[Link 5]: https://blog.csdn.net/Butterfly_resting/article/details/89736042
[Link 6]: https://blog.csdn.net/Butterfly_resting/article/details/89735792
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0J1dHRlcmZseV9yZXN0aW5n_size_16_color_FFFFFF_t_70]: /images/20220210/c15226fba3a849b9bd9011392886e097.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0J1dHRlcmZseV9yZXN0aW5n_size_16_color_FFFFFF_t_70 1]: /images/20220210/03762b247c474e688c91e46d10b0e5ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0J1dHRlcmZseV9yZXN0aW5n_size_16_color_FFFFFF_t_70 2]: /images/20220210/96223b9fda124f24ad7520e0dc6cf813.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0J1dHRlcmZseV9yZXN0aW5n_size_16_color_FFFFFF_t_70 3]: /images/20220210/00b176d557714209b9e049e40551f179.png