动态规划 #
介绍 #
当最优化问题具有重复子问题和最优子结构的时候，适合使用动态规划算法。动态规划算法的核心就是提供了一个memory来缓存重复子问题的结果，避免了递归的过程中的大量的重复计算。动态规划算法的难点在于怎么将问题转化为能够利用动态规划算法来解决。当重复子问题的数目比较小时，动态规划的效果也会很差。如果问题存在大量的重复子问题的话，动态规划的效率较高。
例题 #
正则表达式匹配 #
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
‘.’ 匹配任意单个字符 ‘*’ 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1：
输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
示例 2:
输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
func isMatch(s string, p string) bool {
m, n := len(s), len(p)
matches := func(i, j int) bool {
if i == 0 {
return false
}
if p[j-1] == '.' {
return true
}
return s[i-1] == p[j-1]
}
f := make([][]bool, m + 1)
for i := 0; i < len(f); i++ {
f[i] = make([]bool, n + 1)
}
f[0][0] = true
for i := 0; i <= m; i++ {
for j := 1; j <= n; j++ {
if p[j-1] == '*' {
f[i][j] = f[i][j] || f[i][j-2]
if matches(i, j - 1) {
f[i][j] = f[i][j] || f[i-1][j]
}
} else if matches(i, j) {
f[i][j] = f[i][j] || f[i-1][j-1]
}
}
}
return f[m][n]
}
回溯法 #
介绍 #
回溯算法也算是遍历算法的一种，回溯算法是对Brute-Force算法的一种改进算法，一个典型的应用是走迷宫问题，当我们走一个迷宫时，如果无路可走了，那么我们就可以退一步，再在其他的路上尝试一步，如果还是无路可走，那么就再退一步，尝试新的路，直到走到终点或者退回到原点。
回溯 ----递归1.递归的下面就是回溯的过程
2.回溯法是一个 纯暴力的 搜索
3.回溯法解决的问题：
3.1组合 如：1234 两两组合
3.2切割问题 如：一个字符串有多少个切割方式 ，或者切割出来是回文
3.3子集 ： 1 2 3 4 的子集
3.4排列问题（顺序）
3.5棋盘问题：n皇后 解数独
4.回溯可抽象成树形结构
5.void backtracking(){
if(终止条件) {
收集结果
return
}
for(集合的元素集，类似子节点的个数)
{
处理结点
递归函数；
回溯操作
（撤销处理结点12， 2撤销 ，13 撤销3， 14）
}
}
例题 #
组合 #
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
//知道要用回溯法 但还是没写出来
var res [][]int
func combine(n int, k int) [][]int {
res=[][]int{}
if n <= 0 || k <= 0 || k > n {
return res
}
backtrack(n, k, 1, []int{})
return res
}
func backtrack(n,k,start int,track []int){
if len(track)==k{
temp:=make([]int,k)
copy(temp,track)
res=append(res,temp)
}
if len(track)+n-start+1 < k {
return
}
for i:=start;i<=n;i++{
track=append(track,i)
backtrack(n,k,i+1,track)
track=track[:len(track)-1]
}
}
括号生成 #
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
有效括号组合需满足：左括号必须以正确的顺序闭合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
func generateParenthesis(n int) []string {
s=make([]string,0) //不能为var s []string append 插不进去
generate(n,0,0,"") //设置一个函数 递归调用
return s
}
func generate(n int,l int ,r int,cur string){
if r==n&&l==n{ //左括号数量=右括号数量=n时 插入数组切片
s=append(s,cur)
return
}
if l<n{ //左括号数量小于n时 cur加入“（”
generate(n,l+1,r,cur+"(")
}
if r<n&&r<l{ //右括号数量小于n切 右括号的数量要小于左括号 cur+")"
generate(n,l,r+1,cur+")")
}
}
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.7 MB, 在所有 Go 提交中击败了71.77%的用户
双指针 #
介绍 #
双指针模式 #
两个指针朝着左右方向移动（双指针分为同向双指针和异向双指针），直到他们有一个或是两个都满足某种条件。双指针通常用在排好序的数组或是链表中寻找对子。比如，你需要去比较数组中每个元素和其他元素的关系时，你就需要用到双指针了。 使用双指针策略的方法： （1）一般来说，数组或是链表是排好序的，你得在里头找一些组合满足某种限制条件 （2）这种组合可能是一对数，三个数，或是一个子数组 对于未排好序的数组，需要先排序
解题步骤 #
2.1 通常左右两个指针分别为left和right，左右指针的初始位置不一定是在0和length-1，还可能为0和1。 2.2 循环结束条件：while(left <= right) 2.3 比如求两数之和、三数之和、四数之和 在三数之和中，先选择一个target目标值，可以遍历整个数组作为两数之和。而left指针从i+1开始，right指针从length-1开始。计算方式与两数之和类似。 去重。在求多数之和中最常见的就是要去重，需要考虑两部。 （1）target去重，去除重复的target目标和 （2）左右指针去重，去除遍历重复的做指针和右指针
滑动窗口 #
介绍 #
滑动窗口法用于解决的问题 #
经常是用来执行数组或是链表上某个区间（窗口）上的操作。比如找最长的全为1的子数组长度。滑动窗口一般从第一个元素开始，一直往右边一个一个元素挪动。当然了，根据题目要求，我们可能有固定窗口大小的情况，也有窗口的大小变化的情况。滑动窗口经常用于寻找连续的子串和数组。
下面是一些我们用来判断我们可能需要上滑动窗口策略的方法： （1）这个问题的输入是一些线性结构：比如链表呀，数组啊，字符串啊之类的 （2）让你去求最长/最短子字符串或是某些特定的长度要求
解题步骤 #
通常需要左右两个指针，left和right 循环结束条件:首先保持左指针不动，移动右指针，右指针遍历整个数组
例题 #
串联所有单词的子串 #
给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。
示例 1：
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
func findblock(s []string, wordsreceive map[string]int) bool {
wordsreceive2 := make(map[string]int, 0)
falge := true
for i := 0; i < len(s); i++ {
if a, ok := wordsreceive[s[i]]; ok { //如果查到的话
if b, ok := wordsreceive2[s[i]]; ok {
if b < a { //如果查到了 但b<a去掉重复掉
wordsreceive2[s[i]] = b + 1
} else {
falge = false
break
}
} else { //第一次肯定查不到
wordsreceive2[s[i]] = 1 //插入进去
}
} else {
falge = false //没查到
break
}
}
return falge
}
func findSubstring(s string, words []string) []int {
c := make([]int, 0)
blocklen := len(words) * len(words[0]) //滑块长度
wordsreceive := make(map[string]int, 0) //创建一个字典，出现相同字典+1
for _, bb := range words {
wordsreceive[bb] = wordsreceive[bb] + 1
println(wordsreceive[bb])
}
for i := 0; i < len(s)-blocklen+1; i++ {
s1 := s[i : i+blocklen] //滑块
s2 := make([]string, 0, len(words))
for j := 0; j < len(s1)-len(words[0])+1; {
s2 = append(s2, s1[j:j+len(words[0])]) //将滑块分块
j += len(words[0])
}
if findblock(s2, wordsreceive) { //匹配函数
c = append(c, i) //匹配成功将i 加入
}
}
return c
}
执行用时：56 ms, 在所有 Go 提交中击败了46.46%的用户
内存消耗：7.2 MB, 在所有 Go 提交中击败了31.31%的用户