九转算法蛊
坚持蛊只有7转，因为成功不能只靠坚持
注意这里面都是力扣的核心代码模式，注意去联系 acm 模式，就是全面编程，坑还是很多的，而且题目给的 '0' ,'1' 这种是字符，这种的数组里面类型注意是 byte, 0 ,1 这才是 int,小心这个坑。
感悟
重复刷，做的题是会忘的，刷旧题的收获比新题收获会大
哥，真别减了，这里面的题已经是最少最少的，再偷懒那你还考个蛋
常考算法总结
二叉树
概括
- 二叉树的层序遍历用到 队列，二叉搜索树，红黑树的概念。一般二叉树因为数据结构的特性其题目一般都会伴随着递归。递归注意 终止条件 + 返回的数值如何变化
题目
- 543. 二叉树的直径 - 力扣（LeetCode）
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func diameterOfBinaryTree(root *TreeNode) int {
ans := 0
var dfs func(node *TreeNode) int
dfs = func(node *TreeNode) int {
if node == nil {
return -1
}
l := dfs(node.Left) + 1
r := dfs(node.Right) + 1
ans = max(ans, l+r)
return max(l, r)
}
dfs(root)
return ans
}
两条边确定一条路径 ，node为nil 时候返回 -1，才能保证此算法的正确性，递归过程中向上级返回
时候只返左右子树中最大的那个边长，但是注意这里收集结果是讲两条边相加，思维要清晰。- 98. 验证二叉搜索树 - 力扣（LeetCode） 递归，前置节点 pre
func isValidBST(root *TreeNode) bool {
var pre *TreeNode
var dfs func(node *TreeNode) bool
dfs = func(node *TreeNode) bool {
if node == nil {
return true
}
l := dfs(node.Left)
if pre != nil && pre.Val >= node.Val {
return false
}
pre = node
r := dfs(node.Right)
return l && r
}
return dfs(root)
}
前置节点 pre 这个思维常考，注意 pre 的初始化， & 和 var 声明是完全不同的
前面会开辟空间，地址不再是nil,依据二叉搜索树的特性，中序遍历的结果就是 递增的，以此
来进行判断得出结果。
- 104. 二叉树的最大深度 - 力扣（LeetCode） 递归
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}
注意递归返回的数据+1，处理特殊情况，最大深度。
- 101. 对称二叉树 - 力扣（LeetCode）
func isSymmetric(root *TreeNode) bool {
var dfs func(r1, r2 *TreeNode) bool
dfs = func(r1, r2 *TreeNode) bool {
if r1 == nil || r2 == nil {
return r1 == r2
}
return r1.Val == r2.Val && dfs(r1.Left, r2.Right) &&dfs(r1.Right, r2.Left)
}
return dfs(root.Left,root.Right)
}
哎嘿，下意识就像递归，没错，二叉树90%都是递归的，下意识传 root!,那就错了，对称二叉树的主体就是
比较两个 val 是否相同，再把 左的左和右的右 、左的右和右的左去递归完成。
每个方法都因该注意特殊数据的处理和调用。- 105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder) == 0 {
return nil
}
root := &TreeNode{Val: preorder[0]}
size := 0
for _, c := range inorder {
if c == preorder[0] {
break
}
size++
}
root.Left = buildTree(preorder[1:len(inorder[:size])+1], inorder[:size])
root.Right = buildTree(preorder[len(inorder[:size])+1:], inorder[size+1:])
return root
}
首先要清楚什么是前序、中序、后序遍历，然后才能明白这两者这间的联系。size++ 在 break 之后，因为
下标是从 0 开始的，然后递归去传递左子树和右子树的 前序和中序数组，注意 go 语言的切片特性是，左
闭右开。 13 14 行代码要细细揣摩
- 94. 二叉树的中序遍历 - 力扣（LeetCode）
func inorderTraversal(root *TreeNode) []int {
if root == nil {
return nil
}
ans := make([]int, 0)
var dfs func(node *TreeNode)
dfs = func(node *TreeNode) {
if node == nil {
return
}
dfs(node.Left)
ans = append(ans, node.Val)
dfs(node.Right)
}
dfs(root)
return ans
}
分清楚前、中、后序遍历就OK了，注意这里不是直接去递归原函数！！
因为要考虑结果的收集- 124. 二叉树中的最大路径和 - 力扣（LeetCode）
func maxPathSum(root *TreeNode) int {
ans := math.MinInt
var dfs func(node *TreeNode) int
dfs = func(node *TreeNode) int {
if node == nil {
return 0
}
l := dfs(node.Left)
r := dfs(node.Right)
ans = max(ans, l+r+node.Val)
return max(0, node.Val+max(l, r))
}
dfs(root)
return ans
}
内部结果收集的数据：l+r+node.Val，递归传递给外部数据：node.Val+max(l, r)。
因为你只能选择左边或者右边其中一条边去传递。- 236. 二叉树的最近公共祖先 - 力扣（LeetCode）
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil || root == p || root == q {
return root
}
l := lowestCommonAncestor(root.Left, p, q)
r := lowestCommonAncestor(root.Right, p, q)
if l == nil {
return r
}
if r == nil {
return l
}
return root
}
遇到 p 或者 q 就直接返回，因为不管下面有没有另一个节点，它都是目前情况下最近的公共祖先
如果左边找不到，就返回右边，右边找不到，返回左边；如果全部找到了，就返回root 内部节点。- 102. 二叉树的层序遍历 - 力扣（LeetCode）
func levelOrder(root *TreeNode) [][]int {
if root == nil {
return nil
}
res := make([][]int, 0)
curQ := make([]*TreeNode, 0)
curQ = append(curQ, root)
for len(curQ) > 0 {
nxtQ := make([]*TreeNode, 0)
values := make([]int, 0)
for _, node := range curQ {
values = append(values, node.Val)
if node.Left != nil {
nxtQ = append(nxtQ, node.Left)
}
if node.Right != nil {
nxtQ = append(nxtQ, node.Right)
}
}
curQ = nxtQ
res = append(res, values)
}
return res
}
二叉树的最大宽度会写吗？
也是层序遍历，跟此题解法一样，只是需要一个变量来记录一下最大宽度链表
概括
- 链表这里其实还是比较简单的，唯一值得注意的就是它的 node != nil ,node.Next != nil，这样的条件在什么时候去使用；另一个就是 node = node.Next 与 node.Next = node.Next.Next 这两个很像，但是要注意区分开来。
题目
- 2. 两数相加 - 力扣（LeetCode）
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
var head, tail *ListNode
carry := 0
for l1 != nil || l2 != nil {
n1, n2 := 0, 0
if l1 != nil {
n1 = l1.Val
l1 = l1.Next
}
if l2 != nil {
n2 = l2.Val
l2 = l2.Next
}
sum := n1 + n2+carry
sum, carry = sum%10, sum/10
if head == nil {
head = &ListNode{Val: sum}
tail = head
} else {
tail.Next = &ListNode{Val: sum}
tail = tail.Next
}
}
if carry != 0 {
tail.Next = &ListNode{Val: carry}
}
return head
}
采用模拟的方法，注意这里最后的进制位数，如果不为空要记得加入。
head 的声明方式，注意不要使用 &或者 new- 148. 排序链表 - 力扣（LeetCode）
func nxtl1l2(l, r *ListNode) *ListNode {
dummy := &ListNode{}
cur := dummy
for l != nil && r != nil {
if l.Val <= r.Val {
cur.Next = l
l = l.Next
} else {
cur.Next = r
r = r.Next
}
cur = cur.Next
}
if l != nil {
cur.Next = l
} else {
cur.Next = r
}
return dummy.Next
}
func hebingUse(head, tail *ListNode) *ListNode {
if head == nil {
return head
}
if head.Next == tail {
head.Next = nil
return head
}
slow, fast := head, head
for fast != tail {
slow = slow.Next
fast = fast.Next
if fast != tail {
fast = fast.Next
}
}
return nxtl1l2(hebingUse(head, slow), hebingUse(slow, tail))
}
func sortList(head *ListNode) *ListNode {
return hebingUse(head, nil)
}
类似于归并排序法，快排，将局部变的有序，然后把有序的局部再进行排序，以此往复最后
得到整体链表有序
注意这里的22 和 25 行代码处的条件判断以及对应的处理方式- 19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
func removeNthFromEnd(head *ListNode, n int) *ListNode {
dummy := &ListNode{Next: head}
fast, slow := dummy, dummy
for i := 0; i < n; i++ {
fast = fast.Next
}
for fast.Next != nil {
fast = fast.Next
slow = slow.Next
}
slow.Next = slow.Next.Next
return dummy.Next
}
这块两点容易出错，一点是 fast和 slow 指到的事虚拟节点而不是头结点
第二个是for 循环条件为 fast.Next != nil
删除链表容易错误写成： slow = sow.Next.Next - 142. 环形链表 II - 力扣（LeetCode）
func detectCycle(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if fast == slow {
for head != slow {
slow = slow.Next
head = head.Next
}
return head
}
}
return nil
}
找到环的节点，知道这样做，最好还是能解释清楚为什么让 head == slow 时候就是
入环的第一个节点，学习是延期满足。- 160. 相交链表 - 力扣（LeetCode）
func getIntersectionNode(headA, headB *ListNode) *ListNode {
l, r := headA, headB
for l != r {
if l != nil {
l = l.Next
} else {
l = headB
}
if r != nil {
r = r.Next
} else {
r = headA
}
}
return l
}
简单的易错题目，这个方法巧妙，但是易错，需要勤加练习。- 23. 合并 K 个升序链表 - 力扣（LeetCode）
func mergeKLists(lists []*ListNode) *ListNode {
m := len(lists)
if m == 0 {
return nil
}
if m == 1 {
return lists[0]
}
return usedFuzhu(mergeKLists(lists[0:m/2]), mergeKLists(lists[m/2:]))
}
func usedFuzhu(l, r *ListNode) *ListNode {
dummy := &ListNode{}
cur := dummy
for l != nil && r != nil {
if l.Val < r.Val {
cur.Next = l
l = l.Next
} else {
cur.Next = r
r = r.Next
}
cur = cur.Next
}
if l != nil {
cur.Next = l
} else {
cur.Next = r
}
return dummy.Next
}
这里依旧是归并排序的思想，分割成为一个个小部分，排序每个小部分，再去排序每个大部分，最后
达到整体排序的思想- 141. 环形链表 - 力扣（LeetCode）
func hasCycle(head *ListNode) bool {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
return true
}
}
return false
}
环形链表，这道题简单，勤加练习没什么没什么好说的- 21. 合并两个有序链表 - 力扣（LeetCode）
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
dummy := &ListNode{}
cur := dummy
for list1 != nil && list2 != nil {
if list1.Val < list2.Val {
cur.Next = list1
list1 = list1.Next
}else {
cur.Next = list2
list2 = list2.Next
}
cur = cur.Next
}
if list1 != nil {
cur.Next = list1
}else {
cur.Next = list2
}
return dummy.Next
}
这道简单题，在几个中等、困难题中有使用，需要重视。- 206. 反转链表 - 力扣（LeetCode）
func reverseList(head *ListNode) *ListNode {
var pre *ListNode
for head != nil {
nxt := head.Next
head.Next = pre
pre = head
head = nxt
}
return pre
}
反转链表一个题目，注意两点：一是pre 这个前置节点的声明方式，不要去开辟空间
二是反转最后的 pre 就是此段链表反转的最后一个节点位置，而cur/head 则是此段链表的下一个节点。
有个题是 每k个一组反转链表 需要用到上面这两条经验。二分查找
概括
- 它的条件严格，要想用二分必须是非递减（递增不是非递减）。而且，而且，二分有三种方式：①左闭右闭 ②左闭右开 ③：左开右开。最好是三种方式都掌握，目前我喜欢②。
- 二分的三种方法 ： 34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
题目
- 34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode） 顶级二分法
func searchRange(nums []int, target int) []int {
start := er34Ti(nums, target)
if start == len(nums) || nums[start] != target {
return []int{-1, -1}
}
end := er34Ti(nums, target+1) - 1
return []int{start, end}
}
func er34Ti(nums []int, target int) int {
l, r := 0, len(nums)
for l < r {
mid := l + (r-l)/2
if nums[mid] >= target { 、、二分变种，这里 >= 就是前面的first
r = mid
} else {
l = mid + 1
}
}
return l
}
二分本身不难，难的是它的变种，你选择三种方式中的不同，决定你调用方法时候参数传递的差异。
这里 mid >= target 获取到的就是多个 target 的第一个位置，这很容易理解的。
拿到 start 判断是否存在（不存在，存在但不是target)，毕竟是非递减的。
之后的 end 比较巧妙 获取 target+1 的下标 -1 就是end 的下标，非常 nice.- 33. 搜索旋转排序数组 - 力扣（LeetCode）
func getMinIndex(nums []int) int {
l, r := 0, len(nums)-1
for l < r {
mid := l + (r-l)/2
if nums[mid] > nums[len(nums)-1] {
l = mid + 1
} else {
r = mid
}
}
return l
}
func erfenSearch(nums []int, l, r, target int) int {
for l < r {
mid := l + (r-l)/2
if nums[mid] == target {
return mid
} else if nums[mid] > target {
r = mid
} else {
l = mid + 1
}
}
return -1
}
func search(nums []int, target int) int {
i := getMinIndex(nums)
if target > nums[len(nums)-1] {
return erfenSearch(nums, 0, i, target)
}
return erfenSearch(nums, i, len(nums), target)
}
注意找到二阶段数组中最小值的下标，或者找到它里面的最小值这里，l<r,但是 l 和 r 的
初始化却是左闭右开的初始化。
判断是否大于最后一个数在两处的意义是不同的，nums[mid] > nums[len(nums)-1]是为了确定最小值
在哪个区间内，而 target > nums[len(nums)-1]则是判断二分法的区间双指针
概括
- 两个指针可以在同一个对象上面操作，同时也可以分别在不同的对象上面进行操作。
题目
- 76. 最小覆盖子串 - 力扣（LeetCode）双指针+字符串
func minWindow(s string, t string) string {
countT, countS := make([]int, 128), make([]int, 128)
for _, num := range t {
countT[num]++
}
left, ansLeft, ansRight := 0, -1, len(s)
for right, num := range s {
countS[num]++
for scoverT(countS, countT) {
if right-left < ansRight-ansLeft {
ansLeft, ansRight = left, right // 为什么这里怎么看都感觉会是小于呢？？？
}
countS[s[left]]--
left++
}
}
if ansLeft == -1 {
return ""
}
return s[ansLeft : ansRight+1]
}
func scoverT(s, t []int) bool {
for i := 'A'; i <= 'Z'; i++ { 、、注意这里易错是 <=
if s[i] < t[i] {
return false
}
}
for i := 'a'; i <= 'z'; i++ {
if s[i] < t[i] {
return false
}
}
return true
}
其实更偏向于字符串的题，但是双指针更像是面试时候想要的思维。
通过 left和right 两个指针来不断更新滑动窗口的值，又在这个窗口里面通过，
ansLeft 、 ansRight 来不断收集结果，利用它们的初始化来判断是否被更新过，即是否
存在结果。注意 go 语言里面的数组是 左闭右开。- 31. 下一个排列 - 力扣（LeetCode）
func nextPermutation(nums []int) {
// 下一个排列
i, j, k := len(nums)-2, len(nums)-1, len(nums)-1
for i >= 0 && nums[i] >= nums[j] {
i--
j--
}
if i >= 0 {
for nums[i] >= nums[k] {
k--
}
nums[i], nums[k] = nums[k], nums[i]
}
for i, j = j, len(nums)-1; i < j; i, j = i+1, j-1 {
nums[i], nums[j] = nums[j], nums[i]
}
}
i>=0 ：不是最后一个排列
有点考察思维，此题的详细思路还是要看一下官方题解那边- 42. 接雨水 - 力扣（LeetCode）
func trap(height []int) int {
left, sum, right, ansLeft, ansRight := 0, 0, len(height)-1, height[0], height[len(height)-1]
for left < right {
ansLeft = max(ansLeft, height[left])
ansRight = max(ansRight, height[right])
if ansLeft < ansRight {
sum += ansLeft - height[left]
left++
} else {
sum += ansRight - height[right]
right--
}
}
return sum
}
接到雨水的多少取决于最低的那边柱子和水槽，勤加练习，不难。- 3. 无重复字符的最长子串 - 力扣（LeetCode）
func lengthOfLongestSubstring(s string) int {
if len(s) == 0 {
return 0
}
sUse := make([]bool, 128)
left, ans := 0, 0
for right, c := range s {
for sUse[c] {
sUse[s[left]] = false
left++
}
// sUse[right] = true
sUse[c] = true
ans = max(ans, right-left+1)
}
return ans
}
更像是滑动窗口的题，在进入滑动窗口之前，要先把窗口里面已存在的移除窗口。
注意区分有时候用的是下标，有时候是字符rune，有时候是字符串中的下标所表示的字符。回溯
概括
- 回溯：就是仙尊的春秋蝉，就是吃橙子不吐橙子皮，就是林飞的绝命回溯。我不知道走这条路对不对，我有后悔药，我走了，发现不对，那就赖皮、悔棋，我重新来走。
- 回溯的时间复杂度大，一般剪枝，有的剪枝需要排序。回溯完再去走下一步，或者说你有回溯了，就要走下一步；回溯的目的就是为了走下一步。
题目
- 39. 组合总和 - 力扣（LeetCode）
完全背包，回溯，也可以动归解决，跟“零钱兑换”题型一样
func combinationSum(candidates []int, target int) [][]int {
// 有可能是说无序的
res := make([][]int, 0)
path := make([]int, 0)
sort.Ints(candidates)
var dfs func(cand []int, curIndex, target int)
dfs = func(cand []int, curIndex, target int) {
if target == 0 {
tmp := make([]int, len(path))
copy(tmp, path)
res = append(res, tmp)
return
}
for i := curIndex; i < len(cand); i++ {
target -= cand[i]
if target < 0 {
break
}
path = append(path, cand[i])
dfs(cand, i, target)
target += cand[i]
path = path[:len(path)-1]
}
}
dfs(candidates,0,target)
return res
}
回溯法：注意上面有个排序，用于剪枝，通过 target 是否为 0 时候去收集结果，传入
当前的数组，和开始的下标，递归里面通过循环去在回溯之后走下一步，注意里面传入的是 i，别
传 cueIndex，那样没有意义。
- 78. 子集 - 力扣（LeetCode）
func subsets(nums []int) [][]int {
res := make([][]int, 0)
var dfs func(i int,path []int)
dfs = func(i int,path []int) {
if i == len(nums) {
tmp := make([]int, len(path))
copy(tmp, path)
res = append(res, tmp)
return
}
path = append(path, nums[i])
dfs(i+1,path)
path = path[:len(path)-1]
dfs(i+1,path)
}
dfs(0,[]int{})
return res
}
这里通过传入的 i 来记录是否到达收集条件，此题依据次数是否达到nums 长度，path
对于当前的数值，两种方式，取、不取，其中取之后再不取的时候注意回溯。- 46. 全排列 - 力扣（LeetCode）
func permute(nums []int) [][]int {
res := make([][]int, 0)
visitMap := make(map[int]bool, 0)
var dfs func(path []int)
dfs = func(path []int) {
if len(path) == len(nums) {
tmp := make([]int, len(path))
copy(tmp, path)
res = append(res, tmp)
return
}
for _, num := range nums {
if visitMap[num] {
continue
}
path = append(path, num)
visitMap[num] = true
dfs(path)
path = path[:len(path)-1]
visitMap[num] = false
}
}
dfs([]int{})
return res
}
此题是全排列，要明白什么时候排列，确定入参，出参，return 条件
此种解法需要一个 map记录哪些数被访问过，在dfs内遍历数组动态规划
概括
- 由局部推出全部，贪心这里的边界和他有点像。01、完全背包，有的dp 就是存的结果，但是有的 dp 存的则是结果的辅助结构，用来辅助结果值的获取。
题目
- 64. 最小路径和 - 力扣（LeetCode）
func minPathSum(grid [][]int) int {
、、注意初始化的细节
m := len(grid)
n := len(grid[0])
dp := make([][]int, m)
for i := 0; i < m; i++ {
dp[i] = make([]int, n)
}
dp[0][0] = grid[0][0]
for i := 1; i < m; i++ {
dp[i][0] = dp[i-1][0] + grid[i][0]
}
for j := 1; j < n; j++ {
dp[0][j] = dp[0][j-1] + grid[0][j]
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]
}
}
return dp[m-1][n-1]
}
这里初始化要注意，dp[i-1][0] + grid[i][0] 与 grid[i-1][0] + grid[i][0] 是完全不一样的
而且最后的结果收集注意 -1 - 221. 最大正方形 - 力扣（LeetCode） dp 需要全部初始化
func maximalSquare(matrix [][]byte) int { 、、注意反推回来，反推思维，此题有反推的思想
// 最大正方形
m, n := len(matrix), len(matrix[0])
dp := make([][]int, m)
maxSize := 0
for i := 0; i < m; i++ {
dp[i] = make([]int, n)
for j := 0; j < n; j++ {
dp[i][j] = int(matrix[i][j] - '0')
if dp[i][j] == 1 {
maxSize = 1
}
}
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if dp[i][j] == 1 {
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
}
maxSize = max(maxSize, dp[i][j])
}
}
return maxSize * maxSize
}
反推思维，如果这个正方形边长为3，那么说明它的左上角，它的左边，它的上边都是正方
形，反推回来，此时正方形的边长最大值就是它们三个中最短的那个 +1
这里的整个 dp 都是用于辅助结果的收集；而有的dp 是本身就可以收集到结果。
- 322. 零钱兑换 - 力扣（LeetCode）完全背包，和“组合总和”类似
func coinChange(coins []int, amount int) int {
dp := make([]int, amount+1)
for i := 1; i <= amount; i++ {
dp[i] = math.MaxInt
}
for i := 0; i < len(coins); i++ {
for j := coins[i]; j <= amount; j++ {
if dp[j-coins[i]] != math.MaxInt {
dp[j] = min(dp[j], dp[j-coins[i]]+1)
}
}
}
if dp[amount] == math.MaxInt {
return -1
}
return dp[amount]
}
完全背包，拿硬币凑够零钱.注意这里是由原来的二维dp 变成了一维滚动数组，需要标识符号。初始化时候
的大小要注意，这里跟 爬楼梯的初始化相似。- 70. 爬楼梯 - 力扣（LeetCode） 易错题
func climbStairs(n int) int {
if n == 1 {
return 1
}
dp := make([]int, n+1)
dp[0] = 1
dp[1] = 1
for i := 2; i <= n; i++ {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
特殊条件的判断，遇到n==1直接返回，保证后面算法的正确性。
注意初始化是 n+1- 72. 编辑距离 - 力扣（LeetCode）
func minDistance(word1 string, word2 string) int {
m, n := len(word1), len(word2)
dp := make([][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, n+1)
dp[i][0] = i
}
for j := 0; j <= n; j++ {
dp[0][j] = j
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if word1[i-1] == word2[j-1] {
dp[i][j] = dp[i-1][j-1]
} else {
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
}
}
}
return dp[m][n]
}
这里也是申请 m+1,n+1的空间，这样做是为了方便后面的算法编辑，可以省去很多步骤
要是不明白的话，可以去看代码随想录里面这道题的思路，很详细、清楚
- 300. 最长递增子序列 - 力扣（LeetCode）
func lengthOfLIS(nums []int) int {
dp := make([]int, len(nums))
for i := 0; i < len(nums); i++ {
dp[i] = 1
}
res := dp[0]
for i := 1; i < len(nums); i++ {
for j := 0; j < i; j++ {
if nums[i] > nums[j] {
dp[i] = max(dp[i], dp[j]+1)
}
}
res = max(res, dp[i])
}
return res
}
dp初始化为 1，需要一个 res 变量来记录一下结果，注意第 10 行的判断是哪个数组，不是 dp 去判断- 121. 买卖股票的最佳时机 - 力扣（LeetCode）
func maxProfit(prices []int) int {
dp := make([][]int, len(prices))
for i := 0; i < len(prices); i++ {
dp[i] = make([]int, 2)
}
dp[0][0] = -prices[0]
dp[0][1] = 0
for i := 1; i < len(prices); i++ {
dp[i][0] = max(dp[i-1][0], -prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
}
return dp[len(prices)-1][1]
}
经典中的经典，0 代表持有股票，1 代表不持有股票，这两者需要注意
最后返回的是不持有股票的那一天价格- 5. 最长回文子串 - 力扣（LeetCode）
func longestPalindrome(s string) string {
dp := make([][]bool, len(s))
for i := 0; i < len(s); i++ {
dp[i] = make([]bool, len(s))
dp[i][i] = true
}
result := s[0:1]
for length := 2; length <= len(s); length++ {
for start := 0; start < len(s)+1-length; start++ {
end := start + length - 1
if s[end] != s[start] {
// dp[start][end] = false
continue
} else if length < 3 {
dp[start][end] = true
} else {
dp[start][end] = dp[start+1][end-1]
}
if dp[start][end] && end-start+1 > len(result) {
result = s[start : end+1]
}
}
}
return result
}
上海9k实习生的面试题，害，桑心，当初就是被这道题卡住了
这次我要狠狠地拿下，这种解法的 dp 起到的是辅助性作用，通过result来收集结果，注意 result的
初始化写法，长度不变，不断去移动起始下标，特别注意 下标和长度的区别，下标从0开始，和长度在意义
上面少1 ，在使用两者的时候要格外注意。其他（图，栈，队列，矩阵，字符串，数组，Map，数学，技巧）
- 选择图像（矩阵顺时针旋转90）
func rotate(matrix [][]int) {
// 行 ： 列
// 列：n-1-行
n := len(matrix)
tmp := make([][]int, n)
for i := 0; i < n; i++ {
tmp[i] = make([]int, n)
}
for i, ints := range matrix {
for j, val := range ints {
tmp[j][n-1-i] = val
}
}
copy(matrix,tmp)
}
这里是一个暴力解法，简单
行列的意义转变要注意- 240. 搜索二维矩阵 II - 力扣（LeetCode）
func searchMatrix(matrix [][]int, target int) bool {
m := len(matrix)
n := len(matrix[0])
i, j := 0, n-1
for i < m && j >= 0 {
if matrix[i][j] == target {
return true
}else if matrix[i][j] > target {
j--
}else {
i++
}
}
return false
}
此区间最小的大于它， 此区间最大的小于它
这样便可以很快速的去搜寻到它。- 128. 最长连续序列 - 力扣（LeetCode） 技巧+ map
func longestConsecutive(nums []int) int {
hasMap := make(map[int]bool, 0)
for _, num := range nums {
hasMap[num] = true
}
ans := 0
for key, _ := range hasMap {
if !hasMap[key-1] {
curLen := 0
curNum := key
for hasMap[curNum] {
curNum++
curLen++
}
ans = max(ans, curLen)
}
}
return ans
// n n
}
技巧和思维，找到那个 -1不存在的数，也就是连续序列里面的第一位数，然后每次 +1 去判断是否存在，
来更新结果集。
注意不要与 300.最长递增子序列混淆，递增的不需要连续。而连续则是指1234这样的连续- 32. 最长有效括号 - 力扣（LeetCode） 递归，用栈来代替，栈和递归其实还是不一样的
func longestValidParentheses(s string) int {
stack := make([]int, 0)
stack = append(stack, -1)
ans := 0
for i, c := range s {
if c == '(' {
stack = append(stack, i)
} else {
stack = stack[:len(stack)-1]
if len(stack) > 0 {
cur := stack[len(stack)-1]
ans = max(ans, i-cur)
} else {
stack = append(stack, i)
}
}
}
return ans
// n n
}
这里初始化存的 -1 是为了保证此算法的正确性，当左括号被弹完了再遇到右括号说明这个右括号是
不懂事的，给他丢进去栈里面坐牢。
注意压入的事 下标，结果也是两个下标的距离，说到下标就要注意下标是从 0 开始的。- 239. 滑动窗口最大值 - 力扣（LeetCode）
func maxSlidingWindow(nums []int, k int) []int {
res := make([]int, 0)
q := make([]int, 0)
for i, num := range nums {
for len(q) > 0 && nums[q[len(q)-1]] <= num {
q = q[:len(q)-1]
}
q = append(q, i)
if i-q[0] >= k {
q = q[1:]
}
if i+1 >= k {
res = append(res, nums[q[0]])
}
}
return res
}
>=k >=k-1 分清楚为什么
q里面存的可是下标
需要细致的一思维，收集的事数，不是下标，但是存的是下标，一个区间只有一个高峰- 22. 括号生成 - 力扣（LeetCode）
func generateParenthesis(n int) []string {
res := []string{}
var dfs func(l, r int, str string)
dfs = func(l, r int, str string) {
if len(str) == 2*n {
res = append(res, str)
return
}
if l > 0 {
dfs(l-1, r, str+"(")
}
if r > l {
dfs(l, r-1, str+")")
}
}
dfs(n,n,"")
return res
}
左括号只要不为0，就递归传入左括号
只有在右括号大于左括号的情况下，才会传递进入右括号
递归要注意它的入参和出参- 56. 合并区间 - 力扣（LeetCode）
func merge(intervals [][]int) [][]int {
res := make([][]int, 0)
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
left, right := intervals[0][0], intervals[0][1]
for i := 1; i < len(intervals); i++ {
if intervals[i][0] > right {
res = append(res, []int{left, right})
left = intervals[i][0]
right = intervals[i][1]
} else {
right = max(right,intervals[i][1])
}
}
res = append(res, []int{left, right})
return res
}
注意此方法之前需要排序
如果重叠了就把两个区间合并起来
如果不重叠则更新 right,而不是去更改原本的边界数值
以及最后循环结束也要处理尾部数据，保证算法的正确性- 20. 有效的括号 - 力扣（LeetCode）
func isValid(s string) bool {
sMap := make(map[rune]rune, 0)
sMap[')'] = '('
sMap[']'] = '['
sMap['}'] = '{'
stack := make([]rune, 0)
for _, c := range s {
if c == '(' || c == '{' || c == '[' {
stack = append(stack, c)
} else {
if len(stack) == 0 {
return false
}
if stack[len(stack)-1] != sMap[c] {
return false
}
stack = stack[:len(stack)-1]
}
}
return len(stack) == 0
}
map考察，还有栈，遇到左边就入栈，遇到右边就出栈然后进行配对匹配，注意要先检查栈里面的数据
是否存在，以及最后的结果返回值要判断是否为空，即括号是否全部配对，没有剩余- 200. 岛屿数量 - 力扣（LeetCode）
func numIslands(grid [][]byte) int {
m := len(grid)
n := len(grid[0])
ans := 0
var dfs func(i, j int)
dfs = func(i, j int) {
if i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1' {
return
}
grid[i][j] = '8'
dfs(i-1, j)
dfs(i+1, j)
dfs(i, j+1)
dfs(i, j-1)
}
for i, bytes := range grid {
for j, b := range bytes {
if b == '1' {
dfs(i, j)
ans++
}
}
}
return ans
}
思路简单，但是此方法是暴力的，有时间可以再去看看其他简便算法。
就是遇到一个 ‘1’字符，就把它的周围都打上标记，然后记录一下结果++
- 1. 两数之和 - 力扣（LeetCode）
func twoSum(nums []int, target int) []int {
sMap := make(map[int]int, 0)
for i, num := range nums {
if v, ok := sMap[target-num]; ok {
return []int{i, v}
}
sMap[num] = i
}
return []int{}
}
哎呦喂，面试官最喜欢靠的入门小题，map集合控制- 53. 最大子数组和 - 力扣（LeetCode）
func maxSubArray(nums []int) int {
curS, minS := 0, 0
ans := math.MinInt
for i := 0; i < len(nums); i++ {
curS += nums[i]
ans = max(curS-minS, ans)
minS = min(minS, curS)
// ans = max(curS-minS, ans)
}
return ans
}
这里用的是前缀和思路，前缀和 - 最小的数组之和，就是此次的子数组之和，取最大的- 15. 三数之和 - 力扣（LeetCode）
func threeSum(nums []int) [][]int {
ans := make([][]int, 0)
sort.Ints(nums)
n := len(nums)
for i, num := range nums[:n-2] {
if i > 0 && num == nums[i-1] {
continue
}
if num+nums[i+1]+nums[i+2] > 0 {
break
}
if num+nums[n-1]+nums[n-2] < 0 {
continue
}
l, r := i+1, n-1
for l < r {
sum := num + nums[l] + nums[r]
if sum > 0 {
r--
}else if sum < 0 {
l++
}else {
ans = append(ans,[]int{num,nums[l],nums[r]})
l++
for l < r && nums[l] == nums[l-1] {
l++
}
r--
for l < r && nums[r] == nums[r+1] {
r--
}
}
}
}
return ans
}
此方法注意前提是要给排序，这道题面试也喜欢考，只有排完序后面的这些算法才有效
注意剪枝操作，提高时间复杂度。- 215. 数组中的第K个最大元素 - 力扣（LeetCode）
func findKthLargest(nums []int, k int) int {
var dfs func(nums []int, l, r, k int) int
dfs = func(nums []int, l, r, k int) int {
if l == r {
return nums[k]
}
i, j := l-1, r+1
queNum := nums[l]
for i < j {
for i++; nums[i] < queNum; i++ { // todo i++初始化
}
for j--; nums[j] > queNum; j-- {
}
if i < j {
nums[i], nums[j] = nums[j], nums[i]
}
}
if j >= k {
return dfs(nums, l, j, k)
} else {
return dfs(nums, j+1, r, k) // 注意让j+1
}
}
return dfs(nums, 0, len(nums)-1, len(nums)-k)
}
快速排序法的思想，选取基准，然后快排，直到这个基准是你的第k个最大元素
注意这里的 len(nums)-k 是因为排序之后是由小到大的顺序排列，所以要 len(nums)-k才是
排完序第 K 个最大元素，或许有点抽象，不理解可以去看官方题解。- 146. LRU 缓存 - 力扣（LeetCode）
type lruListNode struct {
key, value int
pre, next *lruListNode
}
func initLruListNode(k, v int) *lruListNode {
return &lruListNode{
key: k,
value: v,
}
}
type LRUCache struct {
size, cacheSize int
lruMap map[int]*lruListNode
head, tail *lruListNode
}
func Constructor(capacity int) LRUCache {
l := LRUCache{
size: 0,
cacheSize: capacity,
lruMap: map[int]*lruListNode{},
head: initLruListNode(0, 0),
tail: initLruListNode(0, 0),
}
l.head.next = l.tail
l.tail.pre = l.head
return l
}
func (this *LRUCache) addToHead(node *lruListNode) {
node.pre = this.head
node.next = this.head.next
this.head.next = node
node.next.pre = node
}
func (this *LRUCache) removeNode(node *lruListNode) {
node.pre.next = node.next
node.next.pre = node.pre
}
func (this *LRUCache) moveToHead(node *lruListNode) {
this.removeNode(node)
this.addToHead(node)
}
func (this *LRUCache) removeTailNode() *lruListNode {
node := this.tail.pre
this.removeNode(node)
return node
}
func (this *LRUCache) Get(key int) int {
if _, ok := this.lruMap[key]; !ok {
return -1
}
node := this.lruMap[key]
this.moveToHead(node)
return node.value
}
func (this *LRUCache) Put(key int, value int) {
if _, ok := this.lruMap[key]; !ok {
node := initLruListNode(key,value)
this.addToHead(node)
this.size++
this.lruMap[key] = node
if this.size > this.cacheSize {
tailNode := this.removeTailNode()
delete(this.lruMap,tailNode.key)
this.size--
}
}else {
node := this.lruMap[key]
node.value = value
this.moveToHead(node)
}
}
这道题，呵呵，我亦无他，唯手熟尔