不会飞的章鱼

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.

题目

LeetCode
LeetCode-cn

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4

Example 4:
Input: nums = [1,3,5,6], target = 0
Output: 0

Example 5:
Input: nums = [1], target = 0
Output: 0
 
Constraints:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums contains distinct values sorted in ascending order.
-104 <= target <= 104

题解

题目

LeetCode
LeetCode-cn

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Clarification:

题目

LeetCode
LeetCode-cn

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.