[关闭]
@songhanshi 2021-01-15T16:54:17.000000Z 字数 9169 阅读 509

algorithm

Java学习

algorithm

一、操作

1-method

  1. 函数方法
    • 最小值：Math.min()

2-String

  1. String转数组 | 数组转String
    String str = "abc";

    • 转数组：char[] chars = str.toCharArray();
    • 转字符串：str = new String(chars);|str = String.valueOf(chars);

  2. 初始化char[]

    1. char cha[] = {'a','2','3','f'}; 
    2. char[] cha= new char[]{'a','2','3','f'};
    3. char[] cha= new char[4]；cha[0]='a';

  3. array转list

    1. String[] array = {"string1","string2","string3"};
    2. //Arrays.asList产生一个Arrays内置的类 其中数组用final表示！
    3. List<String> list = Arrays.asList(array);
    4. // list.add("string4");  所以不能往其中添加元素

    不能进行修改操作。 如需修改操作:
    方式1：
    List list= new ArrayList<>(Arrays.asList(array));
    方式2：
    List list = new ArrayList<>(array.length);
    Collections.addAll(list,array);

  4. List转array

    1. List<String> list2 = new ArrayList<>();
    2. list2.add("t1");
    3. list2.add("t2");
    4. list2.add("t3");
    5. //toArray中不指定参数 只能转换为Object类型
    6. String[] strings = list2.toArray(new String[list2.size()]);

3-队列、双端队列、栈

  1. 代码

    1. import java.util.LinkedList;
    2. import java.util.Queue; // 队列，可以存储一组元素，但是存取元素必须遵循先进先出原则 JDK
    3. import java.util.Deque; // 双端队列 两端都可以进出队列 双端队列接口继承自队列接口（Queue）
    4. public class Test {
    5.     public static void main(String[] args) {
    6.     // -----------------------队列--Queue---------------------------
    7.         /**队列，可以存储一组元素，但是存取元素必须遵循先进先出原则 JDK
    8.          */
    9.         Queue<String> queue = new LinkedList<>();
    10.         //入队-- boolean offer(E e):将一个对象添加到队尾，添加成功返回true
    11.         queue.offer("one");
    12.         queue.offer("two");// [one, two]
    13.         //出队-- 从队首获取元素，获取后该元素就从队列中给移除 E poll():从队首删除并返回一个元素
    14.         String str = queue.poll();// [two]
    15.         // 获取队首元素 -- E peek():返回队首元素（但是不删除）
    16.     // -----------------------双端队列--Deque---------------------------
    17.         /**双端队列 两端都可以进出队列 双端队列接口继承自队列接口（Queue）
    18.          */
    19.         // boolean offer(E e):将一个对象添加到队尾，添加成功返回true
    20.         // boolean offerFirst(E e):将一个对象添加到队首，添加成功返回true
    21.         // boolean offerLast(E e):将一个对象添加到队尾，添加成功返回true
    22.         // *
    23.         // E poll():从队首删除并返回一个元素 E
    24.         // pollFirst():从队首删除并返回一个元素 E
    25.         // pollLast():从队尾删除并返回一个元素
    26.         // E peek():返回队首元素（但是不删除）
    28.         Deque<String> deque = new LinkedList<String>();
    29.         deque.offer("a");
    30.         deque.offer("aa");
    31.         deque.offerFirst("b");// 从队首添加
    32.         deque.offerLast("c");// 从队尾添加
    33.         System.out.println(deque);// [b, a, aa, c]
    34.         // -----------------------栈--Deque---------------------------
    35.         /** 栈1
    36.          * 如果将Deque限制为只能从一端进和出，则可以实现 栈（Stack）
    37.          */
    38.         //入栈：push(offerFirst)
    39.         //出栈：pop(pollFirst) 栈遵循先进后出（FILO）原则
    40.         Deque<String> stack = new LinkedList<>();
    41.         stack.push("1");//入栈
    42.         stack.push("2");
    43.         stack.push("3"); // 栈：[3, 2, 1]
    44.         while (stack.size() > 0) {
    45.             System.out.println(stack.pop());//出栈
    46.         }
    47.         // ----------------------栈--Stack---------------------------
    48.         /**Stack类2
    49.          * 栈：桶型或箱型数据类型，后进先出，相对堆Heap为二叉树类型，可以快速定位并操作
    50.          */
    51.         // 栈：桶型或箱型数据类型，后进先出，相对堆Heap为二叉树类型，可以快速定位并操作
    52.         // Stack<E>，支持泛型
    53.         // public class Stack<E> extends Vector<E>
    54.         // Stack的方法调用的Vector的方法，被synchronized修饰，为线程安全(Vector也是)
    55.         // Stack methods：
    56.         // push : 把项压入堆栈顶部 ，并作为此函数的值返回该对象
    57.         // pop : 移除堆栈顶部的对象，并作为此函数的值返回该对象
    58.         // peek : 查看堆栈顶部的对象，，并作为此函数的值返回该对象，但不从堆栈中移除它
    59.         // empty : 测试堆栈是否为空
    60.         // search : 返回对象在堆栈中的位置，以 1 为基数
    61.     }
    62. }

4-无界优先级队列 Heap

  1. PriorityQueue是从JDK1.5开始提供的新的数据结构接口

    • 优先队列不允许空值，而且不支持non-comparable（不可比较）的对象，这样会抛出ClassCastException异常。
    • 元素可按自然排序，也可在创建ProorityQueue实例时指定比较器。

  2. 使用参考：L - 0179】e - x - 最大数

  3. 一般使用

    1. PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>(){
    2.  @Override
    3.  public int compare(Integer o1, Integer o2){
    4.  return o1.compareTo(o2);
    5.  }
    6. });

    具体：https://www.jb51.net/article/181195.htm

    1. // 最小优先队列，直接 return o1.compareTo(o2);
    2. PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>(){
    3.  @Override
    4.  public int compare(Integer o1, Integer o2){
    5.  return o1 < o2 ? -1 : 1; 
    6.  /* e.g., return o1.compareTo(o2); */
    7.  }
    8. });
    10. // 最大优先队列，则反过来 return o2.compareTo(o1);
    11. return o1 > o2 ? -1 : 1;

  4. 自然排序

    1. public class Test {
    2.     private static PriorityQueue<Student> priorityQueue = new PriorityQueue<>();
    3.     public static void main(String[] args) {
    4.         priorityQueue.add(new Student(10));
    5.         priorityQueue.add(new Student(30));
    6.         priorityQueue.add(new Student(26));
    8.         while (true) {
    9.             Object poll = priorityQueue.poll();
    10.             if(poll != null){
    11.                 System.out.println(poll);
    12.             }else{
    13.                 break;
    14.             }
    15.         }
    16.     }
    17. }
    19. class Student implements Comparable<Student>{
    20.     private int age;
    21.     public Student(int age) { this.age = age; }
    22.     @Override
    23.     public String toString() { return "Student{" + "age=" + age + '}'; }
    25.     @Override // 重点
    26.     public int compareTo(Student o) {
    27.         return this.age - o.age;//从小到大
    28.     }
    29. }

  5. 比较器

    1. import java.util.Comparator;
    2. import java.util.PriorityQueue;
    3. public class Test {
    4.     private static PriorityQueue<Student> priorityQueue = new PriorityQueue<>(new Comparator<Student>() {
    5.         @Override
    6.         public int compare(Student o1, Student o2) {
    7.             return o1.getAge() - o2.getAge();//小到大
    8.         }
    9.     });
    10.     public static void main(String[] args) {
    11.         priorityQueue.add(new Student(10));
    12.         priorityQueue.add(new Student(30));
    13.         priorityQueue.add(new Student(26));
    15.         while (true) {
    16.             Object poll = priorityQueue.poll();
    17.             if(poll != null){
    18.                 System.out.println(poll);
    19.             }else{
    20.                 break;
    21.             }
    22.         }
    23.     }
    24. }
    26. class Student {
    27.     private int age;
    28.     public Student(int age) { this.age = age; }
    29.     @Override
    30.     public String toString() { return "Student{" + "age=" + age + '}'; }
    31.     public int getAge() { return age; }
    32. }

二、questions

链接下面有微软面试面经推荐
https://blog.csdn.net/u010712012/article/details/102557452

1.Leetcode103
2.Leetcode25
3.找出第一个缺失的数
https://www.nowcoder.com/practice/8cc4f31432724b1f88201f7b721aa391?tpId=117&&tqId=1001912

楼上扔两个鸡蛋
https://www.nowcoder.com/practice/d1418aaa147a4cb394c3c3efc4302266?tpId=117&&tqId=1067775
岛屿和帽子
https://www.nowcoder.com/practice/0c9664d1554e466aa107d899418e814e?tpId=117&&tqId=1024684

  1. B+树，从原理慢慢深入，问B+树节点存那些东西，（左右指针，父节点数据，当前节点数据，数据存磁盘，只存指针），问还有么？还有？

  2. 堆的结构
    https://blog.csdn.net/qq_36186690/article/details/82505569

1-base

  1. J02】Singleton模式

  2. dcl（双重验证）单例模式的实现 |2

  3. L - 0146】e - x - LRU缓存机制

    • 设计LRU （基于map，linkedlist）分析时间复杂度，要求优化，说了优先级队列将查找降为对数级别，不满意，叫我回去看linkedhashmap源码

  4. equals()
    两个字符串，按照规则判断相等（重写equals），规则是两个字符串相同字符出现的次数相同，遍判定相等。例（AAB 和 ABA 相等）。

生产者消费者（一对一）

10个多线程保证 i从0加到10 （差点翻车，主线程忙等另外10个线程完结）

手写消费者生产者模式

4、算法题：LRU
https://www.nowcoder.com/practice/e3769a5f49894d49b871c09cadd13a61?tpId=117&&tqId=1006010

两个抛硬币概率题

2-排序

  1. D-快排 |3

    • 讲一下快速排序的思想：思想步骤，时间复杂度，空间复杂度，具体如何计算的

  2. 归并排序 |2

  3. 堆排序 |2

    • 原理及时间复杂度，是否稳定，最坏及最坏场景。

  4. 排序总结

    • 讲一下稳定的排序算法和不稳定的排序算法
      总结

  5. 优缺点

    • 写出你熟悉的排序算法，并说明其优缺点

算法：手写快速排序、插入排序、冒泡排序，并分析时间复杂度和空间复杂度，它们的稳定性。

4.手撕算法，递归二分查找

3-栈|队列

  1. 两个队列实现一个栈 |3

  2. 用数组写一个stack

14.算法题，实现一个有 min() 方法的栈，我没用辅助栈，直接在原栈上操作（将最小值重复入栈即可）

4-链表

  1. L - 0206】e -反转链表 | 3

    • 栈？双指针？

  2. 两两翻转链表

  3. L0021-合并两个有序链表

  4. L - 0023】e - x - 合并K个升序链表 |2

  5. L0237-删除链表中的节点

  6. 判断单链表环 √
    141 https://leetcode-cn.com/problems/linked-list-cycle/

  7. 有序链表去重
    https://www.nowcoder.com/practice/c087914fae584da886a0091e877f2c79?tpId=117&&tqId=664

  8. NC2 重排链表
    https://www.nowcoder.com/practice/3d281dc0b3704347846a110bf561ef6b?tpId=117&&tqId=603

  9. 删除链表中第k大的节点（以为是找第k大的数，听录音才听清是删除第k大的节点）
    删除链表的倒数第n个节点 时间复杂度 O（N）
    空间复杂度O（1）复杂度判断有环

  10. 链表复制-sw

算法：二叉搜索数与双向链表（这个懵了）

5-数

  1. sqrt(x)开个根号，保证小数点后三位精度

  2. L - 0179】e - x - 最大数

1进制转换

2、NC32 求平方根
https://www.nowcoder.com/practice/09fbfb16140b40499951f55113f2166c?tpId=117&&tqId=677

算法：判断是不是有效IP地址。
https://www.nowcoder.com/practice/55fb3c68d08d46119f76ae2df7566880?tpId=117&&tqId=1024725

  1. 算法题
    N个人排队，输入M行，每行两个数字（X, Y），代表X比Y高。（X, Y在0~N-1之间）
    输出N个人的身高的排列，如果不能排列，则输出false。
    图的题目

算法：接雨水：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

设计题 如何实现洗牌算法
算法题 leetcode 166.分数到小数

手写代码：大数相加（用数组模拟）

12.写一个算法实现从100个人中随机抽5个人中奖，要完全随机

算法题：一共有9匹马3条跑道，每次只可以3条马同时跑，问一共需要几轮可以选出前三名

7-数组

  1. 求一天买入股票的最大收益，一开始说了个n^2的，问怎么降到logn

  2. 问邻接表和邻接矩阵，这个没答好。
    https://segmentfault.com/a/1190000002685782

如何判断一个图是否有环？
* 、topk

还有堆的实现，堆中插入一个数据如何保证堆还正常（往上迭代）

15.算法题，一个数组中只有一个数是单独出现，其他都是成对，找出这个值（直接说了异或），又问能不能再简化（又说二分就行了，问了问细节）

算法：一个未排序的数组数据范围1-n，其中更改某个值使得新的值范围仍为1-n，求更改的值和重复的值。进阶：改了2个呢？多个呢？范围为x+1-x+n呢？

8.LeetCode 74 矩阵查找
一开始我说从右上角或左下角开始查找，面试官让我讲解思路和时间复杂度，之后他说这不是最优解
最后在面试官的引导下写出来了最优的二分查找

算法：给定一个数组，找出等于目标值的两个下标；单链表的添加和删除。

4.二维求组，由a【0】【0】到a【n】【n】会有多少种情况，只考虑从左到右，从上到下

一个数组找出出现次数最多的一个数，如果多个数出现的次数相同则输出第一个

  1. 二维矩阵，每一列从上到下是从小到大排序的，请按顺序输出？
    一个数组里面出现第一多的数据

  2. 输入: 一个数组。
    输出: 判断它是否「几乎有序」。
    「几乎有序」指两种情况: 1.交换两个元素后有序 2. 交换一个子串后有序 。
    此外要求O(1)空间。

3.输入: 一个长为n的数组。把长为k的窗口从数组头滑动到数组尾。
输出: 每次滑动时窗口内的最大值，即一个长为(n-k+1)的数组。

怎么把一个有序的列表变为无序的

1 矩阵顺时针旋转90度

9.LeetCode 54 螺旋矩阵，做完提问怎样保证不会重复输出

  1. 旋转过的有序数组中查找目标数字是否存在，说一个复杂的解法，面试官提示我更优解法，但是自己没做出来。
    33 https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

算法：连续子数组的最大和

  1. 股票买卖问题

6-String

  1. 48】最长不含重复字符的子字符串
  2. L - 1143】e -最长公共子序列
  3. 最长公共子串

  4. L - 0005】e -最长回文子串

  5. 有主字符串A，子字符串B，在A中查找B

  6. LC 22，Generate Parentheses，给定 n 对括号，请写一个函数以将其生成新的括号组合，并返回所有组合结果。

算法：最长不含重复字符的子字符串

8.编程题：查找字符串的子字符串第一个字母的索引
算法：找一个字符串中第一个只出现一次的字符下标

3、NC121 字符串的排列

1、NC113 验证IP地址

上来先手撕算法，字符串中的最大回文子串

算法：给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

  1. 最长连续序列
    128：https://leetcode-cn.com/problems/longest-consecutive-sequence/
  2. 给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
    输入:
    "tree"
    输出:
    "eert"
    解释:
    'e'出现两次，'r'和't'都只出现一次。
    因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

2 最长回文子串

  1. 最长公共字串
    https://leetcode-cn.com/problems/longest-common-prefix/

  2. 返回字符串最长重复子串?

  3. 全排列，回溯法使用字典->follow up 更小开销 回溯法不使用字典
    https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=117&&tqId=23291

8-树

  1. 非递归实现的中序遍历
    94 https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

  2. 树打印-之打印

  3. 验证二叉树是不是合法，用递归的方法做出来。
    搜索二叉树98 https://leetcode-cn.com/problems/validate-binary-search-tree/

  4. 二叉搜索树的实现，

法：给前序和中序遍历，重建二叉树

  1. 算法：二叉树中的最大路径和

算法：二叉树的镜像

算法：从上到下打印二叉树

leetcode 103. 二叉树的锯齿形层次遍历

  1. 二叉树中序遍历非递归

  2. 中序非递归
    https://www.nowcoder.com/practice/a9fec6c46a684ad5a3abd4e365a9d362?tpId=117&&tqId=1008937

  3. 给定数值求二叉树根节点到叶子结点之和等于该数值的路径。

  4. 二叉树p、q节点的的最近祖先
    https://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116?tpId=117&&tqId=1024325

  5. NC16 判断二叉树是否对称
    https://www.nowcoder.com/practice/1b0b7f371eae4204bc4a7570c84c2de1?tpId=117&&tqId=645

  6. 树的镜像交换
    比较简单，写了递归，又写了基于层序遍历的非递归版本

  7. 二叉树中序遍历非递归1、 NC16 判断二叉树是否对称
    https://www.nowcoder.com/practice/1b0b7f371eae4204bc4a7570c84c2de1?tpId=117&&tqId=645

9-动态规划

  1. 斐波那契数列，优化空间复杂度

算法：N皇后
算法：剪绳子（贪心或递归解决）

  1. 跳台阶
    70
    JZ-10
    •f(0)=0;f(1)=1;
    f(n)=f(n-1)+f(n-2)
    求f（n）

  2. 斐波那契数列
    509

背包问题

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注