About 3 min

【二分查找】

target在两边还是中间

target < a[m] < target

leftmost和rightmost的标准版返回什么，找到了怎么办

返回candidate.

找到了：candidate = m，外加继续移动

  • leftmost: 左移j = m - 1;
  • rightmost: 右移i = m + 1;

leftmost和rightmost的替身版返回什么、谁是大于等于小于等于

leftmost: 左移if <=；return i

rightmost: if <, 右移else；return i-1

【链表】

链表的遍历条件是什么

当前结点不为空。

遍历时直接打印和更新。

无哨兵头直接开始 cur=head，有哨兵从真头开始，cur=head.next。

链表的插入和删除需要做什么

找到前一个结点。

删除结点

单链表：

  • 删除头结点：判断真头非空 + 更新头 head=head.next。

  • 删除下标：

    通用。找到前一个结点index-1，pre.next = pre.next.next。临界，index超界，要么是index-1本身超界，要么是index-1得到尾结点。

    临界。index=0，对应删除头结点；

插入结点

单链表：

  • 插入头结点：不用判空

    head = new Node(value, head) / head.next = new Node(value, head.next)

删除倒数结点

加哨兵，因为删除

  • 递归：找下一个结点的倒数位置
  • 快慢指针：n+1，+1是因为慢指针找前一个结点

反转链表的方式

  • 遍历，创建新链表
  • 遍历到数组，旧链表重新赋值
  • 递归找最后一个，递归后操作cur和next
  • 让原来头的下一个结点插入到新头前，原头不动，新头更新
  • pre和cur操作链表

【递归】

斐波那契数列的第一项元素是多少，第二项元素是多少？

0,1

爬楼梯是从斐波那契数列的第几项作为开始？

1

汉诺塔的递归规则是什么？用到了几次递归？

123→b，4→c，123→c。

首尾两次

杨辉三角的边界条件是什么

左边、斜边

恰好是 j == 0 和 i == j

【排序】

插入排序的有序部分是头部还是尾部

头部

【树】

树的层序遍历、深度遍历用栈还是队列

树的深度遍历的规则

【图】