jianzhiOffer第二版难重点记录

04. 二维数组中的查找https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

思路：可以每层用以恶搞二分查找，优化思路：从左下角出发直接用二分。

​​​​​​07. 重建二叉树https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/

思路：根据前序遍历和中序遍历来确定最终的树。

19. 正则表达式匹配https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/

递归或者是动态规划

func isMatch(s string, p string) bool {dp := make([][]bool , len(s) + 1)for i := 0 ; i <= len(s); i++{dp[i] = make([]bool , len(p) + 1)}dp[0][0] = truefor i := 1 ; i <= len(p); i++{ // s的长度为0的时候初始化if (i % 2) == 0 && p[i-1] == '*'{dp[0][i] = dp[0][i-2] }}for i := 1; i <= len(s); i++{for j := 1 ; j <= len(p); j++{// 当前值相等的时候if p[j - 1] == '.' || p[j-1] == s[i - 1]{dp[i][j] = dp[i-1][j-1]}// 若果为*的时候考虑if p[j-1] == '*'{dp[i][j] = dp[i][j-2] // 表示当前x*为空if p[j-2] == '.' || p[j-2] == s[i-1]{ // 如果x等于当前值的话可以取一个x*，这里表示s[i-1]已经被解决了dp[i][j] = dp[i][j] || dp[i-1][j]}}} }return dp[len(s)][len(p)]
}

递归的写法

func isMatch(s string, p string) bool {if len(p) == 0 && len(s) == 0{return true}if len(p) == 0{return false}if len(s) == 0{if len(p) >= 2 && p[1] == '*'{return isMatch(s , p[2:])}return false}if len(p) >= 2 && p[1] == '*'{if p[0] == '.' || s[0] == p[0]{return isMatch(s,p[2:]) || isMatch(s[1:] , p)}else{return isMatch(s , p[2:])}}else {if p[0] == '.' || s[0] == p[0]{return isMatch(s[1:] , p[1:])}}return false
}

30. 包含min函数的栈https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/

如何实现一个包含最小值的栈，要能O（1）的时间获取最小值，有两种思路，第一种可以考虑用一个链表去模拟栈，维护一个最小值的变量，第二种方案可以考虑用一个辅助栈去存储最小的值。

type MinStack struct {a []intb []int
}/** initialize your data structure here. */
func Constructor() MinStack {return MinStack{[]int{}, []int{math.MaxInt32},}
}
func min(i, j int) int {if i < j {return i}return j
}
func (this *MinStack) Push(x int) {this.a = append(this.a, x)this.b = append(this.b, min(x, this.b[len(this.b)-1]))
}func (this *MinStack) Pop() {this.a = this.a[:len(this.a)-1]this.b = this.b[:len(this.b)-1]
}func (this *MinStack) Top() int {return this.a[len(this.a)-1]
}func (this *MinStack) Min() int {return this.b[len(this.b)-1]
}

33.二叉搜索树的后序遍历序列https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/

根据后续遍历：左右根，根的左右小于，根的右边大于

func verifyPostorder(postorder []int) bool {// 思路 找到右节点// 右节点的右边大于右节点的左边var recursion func(left , right int)boolrecursion = func(left , right int)bool{if left >= right {return true}index := left for index <= right && postorder[index] < postorder[right]{index++}index --for i := index + 1 ; i < right ; i++{if postorder[i] < postorder[right]{return false}}return recursion(left , index) && recursion(index + 1 , right - 1)}return recursion(0 , len(postorder)-1)
}

43. 1～n 整数中 1 出现的次数https://leetcode.cn/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/

每个位置进行统计。 

func countDigitOne(n int) int {// 统计每个位置出现的1的次数s := strconv.Itoa(n)clen := len(s)res := 0for i := clen - 1; i >= 0; i-- {base := int(math.Pow(10, float64(clen-i-1))) // 表示当前位置的倍数left := 0 //当前位置左边的数right := 0 // 当前位置右边的数for j := 0; j < i; j++ {left = left*10 + int(s[j]-'0')}for j := i + 1; j < clen; j++ {right = right*10 + int(s[j]-'0')}left++ //包括左边的全0，left++right ++ // 右边包括0，right++switch s[i] {case '0': // 左右有left种可能，为1*base - 19..，有left*base可能i位置为1，因为该位置为0，因此left减少一位。res = res + (left - 1)*basecase '1':res = res + (left - 1)*base + right // left减少一位，补上右边的可能性default:res = res + left*base }}return res
}

44. 数字序列中某一位的数字https://leetcode.cn/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/

func findNthDigit(n int) int {if n == 0 {return 0}start := 1count := 9length := 1for n > count {n -= countstart *= 10length++count = 9 * start * length}index := (n - 1) / length + startyu := (n - 1) % lengthreturn int(strconv.Itoa((index))[yu] - '0')
}
/* 数字范围    数量  位数    占多少位1-9        9      1       910-99      90     2       180100-999    900    3       27001000-9999  9000   4       36000  ...例如 2901 = 9 + 180 + 2700 + 12 即一定是4位数,第12位   n = 12;数据为 = 1000 + (12 - 1)/ 4  = 1000 + 2 = 1002定位1002中的位置 = (n - 1) %  4 = 3    s.charAt(3) = 2;*/

49. 丑数https://leetcode.cn/problems/chou-shu-lcof/

堆的应用

51. 数组中的逆序对https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

归并方法思路

func reversePairs(nums []int) int {res := 0tep := make([]int, len(nums))var mergeSort func(left, right int)merge := func(left, mid, right int) {i := leftj := mid + 1index := leftfor i <= mid && j <= right {if nums[i] > nums[j] {tep[index] = nums[j]// fmt.Println("1111")res = res + (mid - i + 1)j++} else {tep[index] = nums[i]i++}index++}for i <= mid {tep[index] = nums[i]i++index++}for j <= right {tep[index] = nums[j]j++index++}for i := left; i <= right; i++ {nums[i] = tep[i]}}mergeSort = func(left, right int) {if left >= right {return}mid := left + (right-left)/2mergeSort(left, mid)mergeSort(mid+1, right)merge(left, mid, right)}mergeSort(0, len(nums)-1)return res
}

56 - I. 数组中数字出现的次数https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/

数组中所有数字都出现两次，有两个出现一次的数字，找出来，这个就是利用二进制的原理进行分组，先全部异或，取出两数已获结果，在通过(n&-n)取出第一位置不一样的作为分组标志。

60n个骰子的点数https://leetcode.cn/problems/nge-tou-zi-de-dian-shu-lcof/

//浪费空间的写法，但是比较容易理解
func dicesProbability(n int) []float64 {dp := make([][]float64, n+1) // dp[i][j] 表示i个骰子，点数和为j的概率for i := 1; i <= n; i++ {dp[i] = make([]float64, 6*i+1)}for i := 1; i <= 6; i++ {dp[1][i] = float64(1) / 6}for i := 2; i <= n; i++ {for k := i; k <= 6*i; k++ { // 当前的点数for t := 1; t <= 6 && k > t; t++ { // 当前出现的点数if k-t <= 6*(i-1) { // 上一级合法出现的点数dp[i][k] += dp[i-1][k-t] / 6 // 上一级出现的点数}}}}return dp[n][n:]
}

func dicesProbability(n int) []float64 {dp := make([]float64, 6)for i := 0; i < 6; i++ {dp[i] = float64(1) / 6}for i := 1; i < n; i++ {tep := make([]float64, 6*(i+1)-i)for j := 0; j < len(dp); j++ {for t := 0; t < 6; t++ {tep[j+t] = tep[j+t] + dp[j]/6}}dp = tep}return dp
}

62. 圆圈中最后剩下的数字https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/

思路：有三种解法，第一通过数组，第二通过链表，第三，递归去做，定义一个递归函数，f(n , k , i)表示有n个数，当删除第k个数，i表示正在删除第i次。

func lastRemaining(n int, m int) int {var f func(n , m , i int)intf = func (n , m , i int)int{if i == 1{return (n + m - 1) % n}return (f(n - 1 , m , i - 1) + m ) % n}return f(n , m , n)
}

64. 求1+2+…+​​​​​​nhttps://leetcode.cn/problems/qiu-12n-lcof/

思路：不能使用公式、乘除法，for等，等价for得有递归操作。还可以用快速乘来替代普通的乘法。

65. 不用加减乘除做加法https://leetcode.cn/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/

思路：传统思路会直接按位进行计算，优化思路的话，可以考虑用递归的思路，a于b之和可以分为无进位之和和有进位之和，无进位是a^b，有进位的和是（a&b）<<1，对结果进行递归处理，当进位为0的时候，直接返回无进位和就行。

func add(a int, b int) int {if b == 0 {return a}return add(a ^ b , (a & b ) << 1)
}