数据结构和算法基础

链表

链表的增，删，改，查，链表反转，复杂链表的复制，检测环

树

树的遍历

  1. 先序： 根-左-右
  2. 中序： 左-根-右 （对搜索树，保序）
  3. 后序： 左-右-根
  4. 层次遍历: 宽度优先遍历

对二叉树，先序和中序，或者后续和中序，都能唯一确定该二叉树，但先序和后序并不能！ 例如，由后序和中序如下确定二叉树结构： 后序遍历的最后一个节点，必是根节点，由该根节点将中序序列分成两个子树，继续递归下去就能重建二叉树的结构

树状数组

Trie 树

自动机

非确定性有限自动机(NFA)

AC 主要解决多模式串的匹配问题。 参考　AC 自动机 Levenshtein 自动机 参考　超酷算法：Levenshtein自动机

哈希表

解决哈希冲突的开放地址法

  1. 线性探测法
  2. 线性补偿探测法

  3. 随机探测法

  4. 布谷鸟哈希(cuckoo hash)

  5. Spatial Hashing

    所谓空间哈希，就是，两个相近的地方，在哈希之后，得到的哈希值也很相近。这在地理位置脱敏中会用到。

排序

首先得有一些基本概念，比如 稳定、原地排序，知道基于比较的排序，其时间复杂度的下界为O(nlgn)等基本事实。

常见的排序算法，如选择排序， 插入排序， 冒泡排序（以及其改进版本）， 快速排序， 堆排序， 归并排序，都应该了解。O(n) 复杂度的排序算法，如计数排序和基数排序也要了解。

动态规划

核心： 分解，找出递归表达式

  • 有面值为1,3,5的纸币若干，用最少的张数凑出给定的数（N）

    提示： d(i) = min{ 1 + d(i-vj)} for j=1,2,3

字符串相关算法

主要的搜索算法包括 KMP 和 Boyer-Moore, 以及 Z algoithm. KMP 的核心在于 next 数组

  • 编辑距离
  • 全排列
  • 变位词

巧用位运算

例如，已知一个数组中除了一个异常元素外，其他元素都出现了两次，找出这个只出现了1次的异常元素。

判断奇偶性: 和1取&，结果为0则为偶数，否则为奇数

判断是否是2的幂次: 只要看 x&(x-1) 是否等于0，是的话，就是2的幂 当然，0例外，因此用 x&& !(x&(x-1)) 即可

求一个整数的二进制表示中的1的个数: 看能做多少次 x&(x-1)，每做一次就少一个1

加密算法

  • 对称加密： 加密和解密用同一个密钥
  • RSA 加密 非对称加密

空间地理算法

涉及空间和地理位置的一些算法 待看这份资料

海量数据算法

  • 蓄水池采样 用数学归纳法证明
  • Bloom Filter

一些经典题目

  • 最长递增子序列

  • 递增二维数组的查找和打印

递增二维数组指的是每行从左到右递增，每列从上往下递增的二维数组。

查找的技巧： 从左下或者右上开始查找，没有岔路。

  • 求一个局部最小值

  • 约瑟夫问题

  • sawp 函数的三种写法

  • 出现次数超过1半的数

  • 最大的二维子矩阵

  • 循环移位

类比线性代数中的转置算子特性： (AB)T=(ATBT)T {(AB)}^{T} = {({A}^{T}{B}^{T})}^{T}

  • 最小周期串
  • 计数压缩
  • 最长公共子串
  • 最长回文子串

资源

  • gitbook: leetcode 题解

  • Craking the Code Interview 问题与解答

    《Cracking the coding interview》是一本被许多人极力推荐的程序员面试书籍， 详情可见：http://www.careercup.com/book。 里面有150道程序员面试题目及相应的解答。书中大部分是编程题目， 并且配有相应的java程序(有些地方有错误或是有更优的方案)。Hawstein 把书中的题目做了一遍， 并且记录下来，包含他对问题的一些思路及看法，许多问题给出了两种以上的解答方案。 所有的代码都托管在Github上。

  • Awesome Interviews

    面试题大全，涵盖各种语言。

results matching ""

    No results matching ""