算法做题学习

算法学习

第一遍，草稿

整理的大体流程如下：

• 题目名称（具体题目内容就不写了，可以查看leetcode网站）
• 解法思路
• 涉及到的基础知识点

常用数据结构

1. 字符串
2. 数组
3. 链表

   public class ListNode {
       int val;
       ListNode next;
       ListNode(int x) { val = x; }
   }

   优点：

• 结构简单的动态数据结构
• 创建时，无需知道链表的长度
• 当插入新节点时，只需要为新节点分配内存，然后调整指针的指向来确保新节点被链接到链表中。
• 内存分配不是在创建时一次性分配，（这与数组不同），而是添加节点时，单独给节点分配。（因为没有闲置的内存，所以链表的空间效率比数组高）

缺点：

• 由于内存空间不是一次性分配，导致无法保证链表的内存是连续的，因为如果想在链表中查找第i个节点，无法像数组一样使用下标在O(1)时间内找到，只能从头节点开始，沿着指针遍历，时间效率为O(n)

《剑指Offer2》对应题目：

• 6 从尾到头打印链表
• 18 删除链表的节点
• 22 链表倒数第k个节点
• 24 反转链表
• 25 合并两个排序的链表
• 52 两个链表的第一个公共节点
• 62 圆圈中最后剩下的数字 （把链表的末尾节点的指针指向头结点，从而形成一个环形链表）
• 36 二叉搜索数与双向链表 （链表中的节点还可以指向前一个节点，形成双向链表）
• 35 复杂链表的复制 （链表中的节点，还有指向任意节点的指针）

树，常考的是二叉树

• 每个节点最多只能有两个子节点，叶结点，就是最末端的节点，没有子节点，根节点没有父节点
• 二叉树中最重要的操作是，遍历，按照某一顺序访问树中所有节点
  • 前序遍历： 先访问根节点，再访问左子节点，最后访问右子节点
  • 中序遍历： 先访问左子节点，再访问根节点，最后访问右子节点
  • 后序遍历： 先左子节点，再右子节点，最后根节点
  • 注意：，前，中，后序，是根据 根节点的访问位置来定的
  • 注意：，三种遍历，都有循环和递归，两种不同的访问方式

宽度优先遍历：

• 先访问数的第一层节点，再访问树的第二层节点…一直到访问到最下面一层节点。
• 在同一层节点中，以从左到右的顺序依次访问。

二叉树有很多特例：

• 二叉搜索树
  • 特点：左子节点总<= 根节点
  • 右子节点总>=根节点
  • 我们可以平均在O(logn)的时间内根据数值在二叉搜索树中找到一个节点
• 堆
  • 最大堆 根节点的值最大
  • 最小堆 根节点的值最小
  • 使用场景：在一些需要 快速找到最大值或者最小值的问题中，可以使用堆来处理
• 红黑树
  • 把树中的节点定义为红，黑，两种颜色，并通过规则确保从根节点到叶节点的最长路径的长度<=最短路径的2倍
  • java中hashmap基于红黑树实现的

《剑指Offer2》对应题目：

• 考察遍历的具体代码实现
  • 26 树的子结构
  • 34 二叉树中和为某一值的路径
  • 55 二叉树的深度
• 考察对遍历特点的理解
  • 7 重建二叉树
• 建议：对前序，中序，后序，这三种遍历的6种实现方式掌握到了如指掌的地步
• 考察宽度优先遍历算法
  • 32 从上到下打印二叉树
• 考察二叉搜索树
  • 36 二叉搜索树与双向链表
  • 68 树中两个节点的 最低公共祖先
• 考察堆和红黑树
  • 40 最小的k个数

栈

• 特点：后进先出，即最后一个被压入push栈的元素会第一个被弹出pop

• 不考虑排序的数据结构

• 需要O(n)时间才能找到栈中最大或者最小的元素

• 31 栈的压入，弹出序列

• 30 包含min函数的栈

队列

• 特点：先进先出，即第一个进入队列的元素将会第一个出来

• 队列与栈的元素压入弹出顺序相反

• 32 从上到下打印二叉树

使用java中的Queue方法时的注意事项

• 队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。
• LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

  Queue<String> queue = new LinkedList<String>();
  //add()和remove()方法在失败的时候会抛出异常(不推荐)
  // 添加元素使用offer
  queue.offer("a");
  // 删除元素，使用poll
  queue.poll(); // 返回第一个元素，并在队列中删除
  //返回第一个元素
  queue.peek()
  
  注意：Queue中，方法offer与add，poll与remove，peek与element这三对的区别
  1. offer与add:
      - 一些队列有大小限制，因此，如果当一个队列容量满了的时候，再添加元素，多出来的元素会被拒绝。这时，如果调用的是add方法，则会抛出unchecked异常，而offer不会抛出异常，只会返回false。
  2. poll与remove：
      - 两者都是从队列中删除第一个元素，当用空集合调用时，remove()的行为与Collection接口的版本相似，会抛出异常，而poll()只会返回null，不会抛出异常
  3. peek()与element()：
      - 两者都用于在队列的头部查询元素。与remove()方法类似，在队列为空时，element()会抛出异常，而peek()返回null。

常用算法

总结：
很多算法都可以使用递归和循环两种不同的方式实现。通常基于递归的实现方法代码会比较简洁，但性能不如基于循环的实现方式。实际使用中，需要根据情况选择合适的方法。

通常排序和查找是面试时考查算法的重点。在准备面试的时候，我们应该重点掌握二分查找、归并排序和快速排序，做到能随时正确、完整地写出代码。

如果面试题要求在二维数组（可能具体表现为迷宫或者棋盘等）上搜索路径，那么我们可以尝试用回溯法。通常回溯法很适合用递归的代码实现。
- 只有当面试官限定不可以使用递归实现的时候，我们再考虑用栈来模拟递归的过程。

1. 查找和排序

排序长度为n的数组，需要O(nlogn)的时间

递归与循环

递归的本质就是一个栈结构，（先进后出）
递归的优点：

缺点：

排序

常用排序算法：

• 冒泡排序，插入排序，选择排序，快速排序，归并排序，计数排序，基数排序，桶排序

复杂度归类

• O(n^2), 冒泡排序，插入排序，选择排序
• O(nlogn), 快速排序，归并排序
• O(n), 计数排序，基数排序，桶排序

关注排序比较和交换的次数

通用排序函数为什么选择快排？

1. 线性排序，时间复杂度为O(n)的三种排序方式，的使用场景特殊，如果要写一个通用的排序函数，不能选择线性排序；
2. 为了兼顾任意规模数据的排序，一般会首选时间复杂度为O(nlogn)的排序算法来实现排序函数；
3. 同为O(nlogn)的快排和归并排序，归并排序不是原地排序算法

• 所以最优的选择是快排

如何优化快速排序？

1. 导致快速排序时间复杂度降为O(n^2)的原因是分区点选择的不合理，最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。

优化分区点的选择：

1. 随机发：每次从要排序的区间中，随机选择一个元素作为分区点；
   • 《剑指Offer》中好像有提到
2. 三数区中法（或N数取中法，取决于数据量）
   • 从区间的首、中、尾分别取一个数，比较大小，取中间值作为分区点
   • 如果要排序的数组较大，可以选择“5数中”，“10数区中”…

警惕快排的递归发生堆栈溢出

1. 限制递归深度，一旦递归超过了设置的阈值就停止递归
2. 在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈过程，这样就没有系统栈大小的限制
   • 方法2更好一些

通用排序函数实现技巧

1. 数据量不大时，O(n^2)排序算法不一定比O(nlogn)排序算法执行的时间长
2. 数据量大时，优化快排区分点的选择
3. 防止堆栈溢出，可以选择在堆上手动模拟调用栈来解决
4. 在排序区间中，当元素个数小于某个常数量时，可以考虑使用O(n^2)的插入排序
5. 用哨兵简化代码，每次排序都减少一次判断，尽可能把性能优化到极致

面试提示

1. 面试中，如果我们打算修改输入的数据或者数据结构，最好先问一下面试官是不是允许修改。

题目的解法积累

1. two sum两数之和

• 解法思路
  1. 暴力两层循环
  2. 利用哈希表来处理
     • 利用hash表处理也有两种方式
       1. 先全部放到HashMap中，然后再通过判断差值是否再HashMap中处理；
       2. 优化1中的方法，减少依次循环，直接边放入HashMap中，边判断差值是否在HashMap中；
     • 利用将数组值和索引放入哈希表的方法来遍历处理
     • 保持数组中的每个元素与其索引相互对应的最好方法是什么？哈希表。key-value
     • 特点：利用空间换取速度，空间复杂度会随着hash表中存储元素的数量线性增加
• 涉及到的基础知识点：
  • hash表
    • 能很好处理key-value对应，
    • hash表的取值速度较快，在没有hash冲突的情况下，hash的查找时间为O(1)，（有hash冲突时为O(n)）
    • 利用空间换取速度，空间复杂度会随着hash表中存储元素的数量线性增加
    • 扩展：看jdk中关于HashMap的实现，和其常用的api，（可以直接看极客时间中订阅的java面试中的HashMap的分析）

2. 整数反转

这题主要利用，数学方法中弹出和推入数字，同时进行溢出前检查
注意理解一下解法中7，-8的由来，

35. 搜索插入位置

关键词：排序数组

主体思想：排除法（减治思想）

应用场景：二分查找相关问题

注意点：

1. 无条件写上while(left < right) ，表示退出循环的条件时left==right，这时不需要考虑返回的左右边界的问题

2. 先写下取中间数取法，然后从如何把mid值排除掉的角度考虑如何写if和else语句

   写的时候把注释写上，1. 把“什么时候不是目标元素”作为注释写下来，提醒自己要判断正确，2. 判读mid分到左边还是右边，写下“下一轮搜索区间范围”作为注释写进代码

3. 当分支逻辑出现left = mid的时候，要修改取中间数的行为，使其上取整。

4. 理解取中间数的方式

   • 普通方式：(a + b)/2
   • 利用数学方式变形防止溢出： a + (b - a)/2

     这样可以防止a+b整形溢出

   • 利用java中的无符号右移： (a + b) >>> 1

     注意这里是>>>(无符号右移) 而不是>>(有符号右移),java中二者有区别，涉及到补码的知识点，具体看5

5. 借鉴java中的无符号右移>>>的特殊语法

   无符号右移 >>> 在对操作数右移以后，不论这个数是正数还是负数，高位一律补 0。使用无符号右移的好处是：即使在 left + right 整形溢出以后，得到的结果依然正确。
   (从JDK的源码中借鉴来的Arrays.binarySearch() 方法)

二叉树

• 二叉树，

• 二叉搜索树

  遍历方法：

  三种遍历方法，分别有什么特殊作用？

  • 前序
  • 中序
  • 后序

二叉搜索树的中序遍历，刚好可以输出一个升序数组
- leetcode 98，99

给出一个升序数据，可以还原二叉搜索树

根据中序遍历+前序/后序遍历 可以还原一课二叉树

前序/后序遍历的作用？提供根节点，根据根节点可以递归生成左右子树

• 递归处理
• 迭代处理

TODO

1.

这个内容要验证一下：

一、取余运算和取模运算的异同

这个题目最开始，我还是分正负数来考虑的，因为我印象里记得 %
对正数和负数的运算好像有区别。最后去查了一下，补充在这里。
C/C++ 和 Java 一样，% 是取余运算；而 Python 的 % 是取模运算。
取余运算和取模运算的区别：
对于整型数 a，b

a，b 来说，取余运算或者取模运算的方法都是下面两步：

    求整数商： c=a/b

c=a/b
计算余数或者模： r=a−c⋅b

    r=a−c⋅b

而两者的区别就在于第一步不同：取余运算在取c
c的值时，向 00 方向舍入，而取模运算在计算cc的值时，则是向负无穷方向舍入。
例如计算：−7%4−7%4
第一步：求整数商，取余运算算出的整数商为c=⌈−74⌉=−1c=⌈4−7​⌉=−1，而取模运算算出的整数商为c=⌊−74⌋=−2c=⌊4−7​⌋=−2
第二步：计算余数和模的公式相同，但因cc的值不同，取余的结果为−7−(−1×4)=−3−7−(−1×4)=−3，取模的结果为−7−(−2×4)=1−7−(−2×4)=1。
归纳：当aa和bb符号一致时，取余运算和取模运算的结果一样。
当符号不一致时，结果不一样。取余运算结果的符号和aa一致，取模运算结果的符号和bb一致。

2.

数学计算中，遇到

区间 [a,b]的集合，

b-a+1,  当计算集合中元素的个数时使用
    类似于，有5个点，当计算有几个点时是，b-a+1,
                    当计算这5个点之间有几个段落时，b-a

b-a，   当计算集合的长度/间隔，时使用

3. 什么时候用双指针？什么时候用单指针？