编程语言

单例模式

java版好的解法

  • 懒汉模式，field直接创建实例
  • volatile+双重检查，加volatile是防止其他线程在本线程刚分配内存、还未初始化时就得到instance
  • 静态内部类，内部类中在filed创建实例，实现在使用时才创建

数据结构

数组

  • 找出数组中重复的数字。
    • 最简单的是哈希表，时间O(1)，空间O(n).
    • 如果空间优先，允许修改原数组。遍历数组的过程中，判断值m与下标m的位置的值是否相同，相同，找到；不相同，替换值m与下标m位置的值。时间O(n)，时间O(1).
    • 空间优先，不允许修改原数组。利用二分查找的思想。将数组与n的中值比较，判断出重复的数是小于还是大于中值，继续二分中值。
  • 二维数组中的查找，行从左到右升序，列从上到下升序，判断是否存在给定的数。clue：从右上或左下开始判断。

字符串

注意某些情形下，从后往前处理，可以减少移动的次数。

链表

链表创建、插入、删除。

树

  • 遍历
    • （根节点所在位置）前序，中序，后序
    • 宽度优先：利用队列，存储当前深度的节点
  • 重建二叉树
  • 二叉树的下一个节点

栈和队列

  • 相互实现

算法和数据操作

递归和循环

递归的实现方式代码简洁，但性能不如循环的实现方式

查找和排序

重点掌握二分查找、归并排序和快速排序

回溯法

在二维数组上搜索路径

动态规划与贪婪算法

动态规划：求某个问题的最优解，且问题可以分为多个子问题。（自上而下：递归，自下而上：循环）
贪婪算法：存在特殊的选择，一定能得到最优解。

位运算

与、或、异或、左移、右移。