常见的DP题目和状态转移方程

爬楼梯

不同路径

布隆过滤器-Bloom filter

Bloom filter vs Hash Table

一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。

优点：空间效率和查询时间都远远超过一般的算法。

题目

力扣-剑指 Offer 03. 数组中重复的数字

我的复述：
假设一个名为nums的数组里[2,3,1,0,2,5,3]，只需要写代码，找出重复的数字2或者3即可。

题解

Map

AVL树

• 发明者：Adelson-Velsky and Landis Tree
• Blance Factor(平衡因子)：是它的左子树的高度减去它的右子树的高度（有时相反）。balance factor= {-1,0,1}
• 通过旋转操作来进行平衡（四种）
• Self-balancing binary search tree
• 不足：结点需要存储额外信息、且调整次数频繁

记录左右子树高度

例如F点，右子树高度1 - 左子树高度2 = -1

剪枝的实现和特性

初级搜索

• 1，朴素搜索：暴力搜索；
• 2，优化方式：不重复(fibonacci)、剪枝(生成括号问题)；
• 3，搜索方向：深度优先搜索、广度优先搜索、双向搜索、启发式搜索。

双向BFS的实现、特性

单向BFS

字符串匹配算法

练习题目

字符串基础问题

• https://leetcode-cn.com/problems/to-lower-case/
• https://leetcode-cn.com/problems/length-of-last-word/
• https://leetcode-cn.com/problems/jewels-and-stones/
• https://leetcode-cn.com/problems/first-unique-character-in-a-string/
• https://leetcode-cn.com/problems/string-to-integer-atoi/

字符串操作问题

排序算法

1，比较类排序

通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。

2，非比较类排序

不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

二分查找的前提

1，目标函数单调性（单调递增或者递减）——在有序的里面查找
2，存在上下界（bounded）
3，能够通过索引访问（index accessible）

代码模板

(一定要写的非常熟练)

1
2
3
4
5
6
7
8
9
10

left,right := 0,len(array) - 1
while left <= right:
    mid := (left + right) / 2
    if array[mid] == target:
        # find the target
        break or return result
    elif array[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

贪心算法-Greedy

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

• 贪心：当下做局部最优判断
• 回溯：能够回退
• 动态规划：最优判断 + 回溯

可以解决的最优化问题

题目

LeetCode
LeetCode-cn

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

• countAndSay(1) = “1”
• countAndSay(n) is the way you would “say” the digit string from countAndSay(n-1), which is then converted into a different digit string.

To determine how you “say” a digit string, split it into the minimal number of groups so that each group is a contiguous section all of the same character. Then for each group, say the number of characters, then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.