By

Contents
  1. 1. 常见面试数据类型
  2. 2. 固定大小数组类移动和插入
  3. 3. 链表
    1. 3.1. O(1)时间内删除单向链表的某节点，条件：知道head的指针和要删除节点的指针Node target
    2. 3.2. 单向链表中一次遍历找到倒数第K个节点
    3. 3.3. 单向链表中一次遍历找到位置中间的节点
    4. 3.4. 单向链表环的入口节点
    5. 3.5. 有序单向链表的去重复结点
    6. 3.6. 两个相交链表求相交节点
    7. 3.7. 反转单向链表
  4. 4. 数组
    1. 4.1. 无序数组，但是长度为N的数组，里面的数都0- N-1之间，求任意重复的数字
    2. 4.2. 不修改数组的情况下，N+1长度的无序数组，值1到N之间，找到一个重复值
    3. 4.3. 无序数组中第K大的数、中位数
    4. 4.4. 有序数组中查询某数字出现的次数
    5. 4.5. 0 至 n-1递增数组中仅缺失了一个数字，求是多少
    6. 4.6. 递增数组找出和下标相同的数组元素
  5. 5. 树

常见面试数据类型

  • 数组
  • 链表
  • 树（堆、二叉搜索树、平衡二叉树)
  • 字符串
  • 栈
  • 排序（快排、堆排、归并，各种复杂度和变种）
  • 二分查找

固定大小数组类移动和插入

  • 空白字符串替换
    ‘we are happy.’ 空白替换为%20，如果原数组有足够的内存的话，先遍历空格的个数和原数组的长度，再从末位开始移动到最终位置，这样大大减少字母移动的次数

  • 两个有序数组A1、A2 有序归并
    应该先遍历size，再从末位比较末位，直接插入到最终位置，而不是从最小数 最小数开始盲目比较。

链表

  • 区分游标（Node node=head）和指针（link.head）的区别，游标改变只是修改指向，指针改变会改变link。

O(1)时间内删除单向链表的某节点，条件：知道head的指针和要删除节点的指针Node target

  • target=target.next
  • 如果target等于head，那么还需要设置 head=target.next
  • 如果target等于tail，且有tail这个指针的话，记得tail=target.next

单向链表中一次遍历找到倒数第K个节点

两个游标，第一个游标先往后走，走到第K个节点的时候，第二个游标开始移动，第一个游标到tail时，第二个游标的位置就是倒数第K个节点
考虑的特殊情况：

  • head为null
  • K>N
  • K=0

单向链表中一次遍历找到位置中间的节点

两个游标一起游动，一个一次移动1，一个一次移动2

单向链表环的入口节点

  • 确认是否要确认是环形，要求单向是大小有序的，一个游标一次走2步，一个游标一次走一步，每次走完比较是否相等，如果有相同，表示闭环，如果node.next=null表示非闭环，
  • 确认闭环后，记录当前节点，一次走一步的游标继续走，直到再次走到这个节点，记录步数，就是环的节数
  • 然后两个游标，第一个游标走了n-1(节数)的时候，第二个游标开始走，相遇点就是环的入口
  • 哈希表法：所有元素插入hashmap中，value为1，当有contains时，就是入口，或者node.next=null，表示非环

有序单向链表的去重复结点

设置一个preNode，遍历indexNode和next的值，相同则next在往后，一直到不相同，preNode.next=next；indexNode=next。

两个相交链表求相交节点

分别遍历求长度m,n， 然后长链表走m-n次之后，两个游标再一起走，相同时就是交点

反转单向链表

  1. 创建一个新链表用addHead的方式遍历从原链表当中取数据
  2. 遍历节点，每次都把当前节点变成head，当前节点的前一个节点.next。 12345 –>21345 这样

数组

数组的查找：

  • 有序数组套用二分法来缩小范围，最差的情况是logN定位元素。比如有序且连续数组中找缺失的一个数据；
  • 无序数组套用快排法来缩小范围，但是最差情况为N的平方，比如定位无序数组的中位数或者第K大的值
  • 无序N个数组，0-n值的话，考虑就地排序

无序数组，但是长度为N的数组，里面的数都0- N-1之间，求任意重复的数字

  • 差的方法：数组排序，NlogN 后再比较
  • 一般的方法：牺牲O（N）的哈希表，当contains时，就是重复数字，时间复杂度O（N）
  • 好的方法：遍历，当arr[i]=i的时候，i++，否则就把 arr[i] 归位到正确的位置上。直到arr[i]！=i 但是arr[i]=arr[m]，所以时间复杂度为O(N)，也就是每次比较一次就归位了一个，最多归位N次，此时不依赖额外的空间

    不修改数组的情况下，N+1长度的无序数组，值1到N之间，找到一个重复值

  • 空间充裕的情况下：插入到hashmap中，牺牲O（N+1）的空间复杂度，实现O（N）的时间复杂度
  • 把范围划分为 1 – N/2 和 N/2+1 N，均分划分范围，每次都要扫描全数组的频率，比如N为10的数组，1-5 之间的次数，6-10之间的频率，哪个大就再均分扫范围，最后确定1，扫logN次，每次扫全数组N+1个，用时间换空间

无序数组中第K大的数、中位数

采用快排的思想缩小搜索范围，但是复杂度还是 N*logN，最差还是N平方

二分查找的运用：

有序数组中查询某数字出现的次数

  • 最差的方法：遍历数组，找到数字K，并且遍历到不是K为止，就是次数，时间复杂度为N
  • 一般差的方法：二分查找到某一个该数字，然后再左右遍历，因为K的个数不确定，所以复杂度还是N
  • 最优解：二分查找找到K，再二分查找到K的左右边界，时间复杂度 logN

0 至 n-1递增数组中仅缺失了一个数字，求是多少

二分查找是左边少了 还是右边少了，缩小范围

递增数组找出和下标相同的数组元素

树

根也指的父节点Or根节点

  • 前序遍历：根左右
  • 中序遍历：左根右
  • 后序遍历：左右根

树的分类：二叉搜索树、堆、红黑树，其中二叉搜索树的中序遍历是一个递增的数组

Contents
  1. 1. 常见面试数据类型
  2. 2. 固定大小数组类移动和插入
  3. 3. 链表
    1. 3.1. O(1)时间内删除单向链表的某节点，条件：知道head的指针和要删除节点的指针Node target
    2. 3.2. 单向链表中一次遍历找到倒数第K个节点
    3. 3.3. 单向链表中一次遍历找到位置中间的节点
    4. 3.4. 单向链表环的入口节点
    5. 3.5. 有序单向链表的去重复结点
    6. 3.6. 两个相交链表求相交节点
    7. 3.7. 反转单向链表
  4. 4. 数组
    1. 4.1. 无序数组，但是长度为N的数组，里面的数都0- N-1之间，求任意重复的数字
    2. 4.2. 不修改数组的情况下，N+1长度的无序数组，值1到N之间，找到一个重复值
    3. 4.3. 无序数组中第K大的数、中位数
    4. 4.4. 有序数组中查询某数字出现的次数
    5. 4.5. 0 至 n-1递增数组中仅缺失了一个数字，求是多少
    6. 4.6. 递增数组找出和下标相同的数组元素
  5. 5. 树