剑指offer（第2版）-go语言实现，适合xx转go程序员参考

2、面试需要的基础知识

2.3 数据结构

2.3.1 数组

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

func findRepeatNumber(nums []int) int {num2cnt := make(map[int]int)for _, num := range nums {_, ok := num2cnt[num]if ok {return num}num2cnt[num] = 1}return -9999
}

剑指 Offer 04. 二维数组中的查找

func findNumberIn2DArray(matrix [][]int, target int) bool {if len(matrix) == 0 {return false}row := 0col := len(matrix[0])-1for (row <= len(matrix)-1) && (col >= 0) {if matrix[row][col] == target {return true}if matrix[row][col] > target {col--} else {row++}}return false
}

2.3.2 字符串

剑指 Offer 05. 替换空格

func replaceSpace(s string) string {items := strings.Split(s, " ")res := strings.Join(items, "%20")return res
}

这也太蠢了，直接调函数，不过应该不会考吧
这个题和语言相关，原题是要求在原数组上修改，现在连数组都没有

剑指 Offer 06. 从尾到头打印链表

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func reversePrint(head *ListNode) []int {res := make([]int, 0, 10)reversePrintCore(head, &res)return res
}func reversePrintCore(head *ListNode, res *[]int) {if head == nil {return}reversePrintCore(head.Next, res)*res = append(*res, head.Val)
}

剑指 Offer 07. 重建二叉树

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func buildTree(preorder []int, inorder []int) *TreeNode {if len(preorder) != len(inorder) || len(preorder) == 0{return nil}root := &TreeNode{preorder[0], nil, nil,}for index, val := range inorder {if preorder[0] == val {root.Left = buildTree(preorder[1:1+index], inorder[0:index])root.Right = buildTree(preorder[1+index:], inorder[index+1:])break}}return root
}

剑指 Offer 10- I. 斐波那契数列

这个题leetcode上要求答案需要取模 1e9+7（1000000007），我不太理解，有什么理论基础可以确定(a+b)%1000000007 == a +b%1000000007
不过这个题可以学到，科学表示法可以这么写**(1e9+7)**

func fib(n int) int {if n <=1 {return n}a,b := 0,1for i := 2;i<=n;i++{a,b = b, (a+b)%(1e9+7)}return b
}

剑指 Offer 10- II. 青蛙跳台阶问题

func numWays(n int) int {if n == 0 || n == 1 {return 1}n1 := 1n2 := 1for i := 2 ; i <= n ; i++ {tmp := n1 + n2n1 = n2n2 = tmp % (1e9+7)}return n2
}

2.4.2 查找和排序

剑指 Offer 11. 旋转数组的最小数字

func minArray(numbers []int) int {left := 0right := len(numbers)-1 // 4mid := left //for numbers[left] >= numbers[right] {if left + 1 == right {return numbers[right]}mid = (left + right) / 2if numbers[left] == numbers[right] && numbers[left] == numbers[mid] {min := numbers[left]for i := left ; i <= right ; i++ {if numbers[i] < min {min = numbers[i] }}return min}// 移动 [0,0,0,-1,0]if numbers[left] <= numbers[mid] {left = mid}if numbers[mid] <= numbers[right] {right = mid}}return numbers[mid]}

2.4.3 回溯法

剑指 Offer 12. 矩阵中的路径

注意，要将used回溯

func exist(board [][]byte, word string) bool {if len(board) == 0 {return false}used := make([][]bool, len(board), len(board))for i := 0 ; i < len(used) ; i++ {used[i] = make([]bool, len(board[0]), len(board[0]))}for i := 0 ; i < len(used) ; i++ {for j := 0 ; j < len(used[0]) ; j++ {if board[i][j] == word[0] {used[i][j] = trueif existCore(board, used, i, j, word[1:]) {return true}else {used[i][j] = false}}}}return false
}func existCore(board [][]byte, used [][]bool, row int, col int, word string) bool { // abc => bcif len(word) == 0 {return true}ch := word[0]if row > 0 && !used[row-1][col] && board[row-1][col] == ch {used[row-1][col] = trueif existCore(board, used, row-1, col, word[1:]) {return true} else {used[row-1][col] = false}}if row < len(board)-1 && !used[row+1][col] && board[row+1][col] == ch {used[row+1][col] = trueif existCore(board, used, row+1, col, word[1:]) {return true} else {used[row+1][col] = false}}if col > 0 && !used[row][col-1] && board[row][col-1] == ch {used[row][col-1] = trueif existCore(board, used, row, col-1, word[1:]) {return true} else {used[row][col-1] = false}}if col < len(board[0])-1 && !used[row][col+1] && board[row][col+1] == ch {used[row][col+1] = trueif existCore(board, used, row, col+1, word[1:]) {return true} else {used[row][col+1] = false}} return false
}

剑指 Offer 14- I. 剪绳子

func cuttingRope(n int) int {if n == 2 {return 1}if n == 3 {return 2}if n == 4 {return 4}size := n+1mul := make([]int, 5, size)mul[2] = 2mul[3] = 3mul[4] = 4for i := 5 ; i <= n ; i++ {mul1 := 2 * mul[i-2]mul2 := 3 * mul[i-3]if mul1 > mul2 {mul = append(mul, mul1)} else {mul = append(mul, mul2)}}return mul[n]
}