剑指offer（专项突破版）-go语言实现，适合Java转go程序员参考

文章目录

  • 2、数组
    • 2.2 双指针
      • 剑指 Offer II 006. 排序数组中两个数字之和
      • 剑指 Offer II 007. 数组中和为 0 的三个数
      • 剑指 Offer II 008. 和大于等于 target 的最短子数组
      • 剑指 Offer II 009. 乘积小于 K 的子数组
    • 2.3 累加数组数字求子数组之和
      • 剑指 Offer II 010. 和为 k 的子数组
      • 剑指 Offer II 011. 0 和 1 个数相同的子数组
      • 剑指 Offer II 012. 左右两边子数组的和相等
      • 剑指 Offer II 013. 二维子矩阵的和
  • 3、字符串
    • 3.2 双指针
      • 剑指 Offer II 014. 字符串中的变位词
    • 3.3 回文字符串
      • 剑指 Offer II 018. 有效的回文
      • 剑指 Offer II 019. 最多删除一个字符得到回文
      • 剑指 Offer II 020. 回文子字符串的个数
  • 4、链表
    • 4.3 双指针
      • 剑指 Offer II 021. 删除链表的倒数第 n 个结点
      • 剑指 Offer II 022. 链表中环的入口节点
      • 剑指 Offer II 023. 两个链表的第一个重合节点
    • 4.4 反转链表
      • 剑指 Offer II 024. 反转链表
      • 剑指 Offer II 025. 链表中的两数相加
      • 剑指 Offer II 026. 重排链表
      • 剑指 Offer II 027. 回文链表
    • 4.5 双向链表和循环链表
      • 剑指 Offer II 028. 展平多级双向链表
      • 剑指 Offer II 029. 排序的循环链表
  • 5、哈希表
    • 5.2 哈希表的设计
      • 剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器
      • 剑指 Offer II 031. 最近最少使用缓存
    • 5.3 哈希表的应用
      • 剑指 Offer II 032. 有效的变位词
      • 剑指 Offer II 034. 外星语言是否排序
  • 7、队列
    • 7.1 基础知识
    • 7.2 队列的应用
      • 剑指 Offer II 041. 滑动窗口的平均值
      • 剑指 Offer II 042. 最近请求次数
  • 8、树
    • 8.3 二叉搜索树
      • 剑指 Offer II 052. 展平二叉搜索树
  • 11、二分查找
    • 11.2 在排序树组中二分查找
      • 剑指 Offer II 068. 查找插入位置
      • 剑指 Offer II 069. 山峰数组的顶部
    • 11.3 在数值范围内二分查找
      • 剑指 Offer II 072. 求平方根
  • 12、排序
    • 12.2 计数排序
      • 剑指 Offer II 075. 数组相对排序
  • 总结

2、数组

2.2 双指针

剑指 Offer II 006. 排序数组中两个数字之和

func twoSum(numbers []int, target int) []int {
    left := 0
    right := len(numbers)-1
    for left < right && numbers[left] + numbers[right] != target {
        if numbers[left] + numbers[right] < target{
            left++
        }else {
            right--
        }
    }
    return []int{left, right}
}

注意：数组的长度是数组类型的一部分，所以[3]int和[4]int是两种不同的数组类型。所以本题中[]int{left, right}中[]里不能加数字，否则会报错，例如[2]int 无法匹配[]int，所以该如何初始化一个int数组呢？如下所示。

    //全局：
    var arr0 [5]int = [5]int{1, 2, 3}
    var arr1 = [5]int{1, 2, 3, 4, 5}
    var arr2 = [...]int{1, 2, 3, 4, 5, 6}
    var str = [5]string{3: "hello world", 4: "tom"}
    //局部：
    a := [3]int{1, 2}           // 未初始化元素值为 0。
    b := [...]int{1, 2, 3, 4}   // 通过初始化值确定数组长度。
    c := [5]int{2: 100, 4: 200} // 使用索引号初始化元素。
    d := [...]struct {
        name string
        age  uint8
    }{
        {"user1", 10}, // 可省略元素类型。
        {"user2", 20}, // 别忘了最后一行的逗号。
    }

剑指 Offer II 007. 数组中和为 0 的三个数

func threeSum(nums []int) [][]int {
    res := [][]int{}
    if len(nums) >= 3 {
        sort.Ints(nums)
        i := 0
        for i < len(nums) - 2{
            res = twoSum(nums, i, res)
            temp := nums[i]
            for i < len(nums) && nums[i] == temp{
                i++
            }
        }
    }
    return res
}

func twoSum(nums []int, i int, res [][]int) [][]int {
    j := i+1
    k := len(nums)-1
    for j < k{
        if nums[i] + nums[j] + nums[k] == 0{
            res = append(res, []int{nums[i], nums[j], nums[k]})
            temp := nums[j]
            for nums[j] == temp && j < k {
                j++
            }
        }else if nums[i] + nums[j] + nums[k] < 0{
            j++
        }else{
            k--
        }
    }
    return res
}

这个题目用到了排序，对于goLang排序是sort.Ints(nums)，Java是Arrays.sort(nums)
而且不同于Java，twoSum必须要把res返回，这与Java的传引用不同，go是传值的。但是如果不想返回，可以使用指针。
所以这样也行

func threeSum(nums []int) [][]int {
    res := [][]int{}
    if len(nums) >= 3 {
        sort.Ints(nums)
        i := 0
        for i < len(nums) - 2{
            twoSum(nums, i, &res)
            temp := nums[i]
            for i < len(nums) && nums[i] == temp{
                i++
            }
        }
    }
    return res
}

func twoSum(nums []int, i int, res *[][]int) {
    j := i+1
    k := len(nums)-1
    for j < k{
        if nums[i] + nums[j] + nums[k] == 0{
            *res = append(*res, []int{nums[i], nums[j], nums[k]})
            temp := nums[j]
            for nums[j] == temp && j < k {
                j++
            }
        }else if nums[i] + nums[j] + nums[k] < 0{
            j++
        }else{
            k--
        }
    }
}

剑指 Offer II 008. 和大于等于 target 的最短子数组

func minSubArrayLen(target int, nums []int) int {
    left := 0
    sum := 0
    minlen := math.MaxFloat64
    for right := 0 ; right < len(nums) ; right++{
        sum = sum + nums[right]
        for left <= right && sum >= target {
            minlen = math.Min(minlen, float64(right-left+1))
            sum = sum - nums[left]
            left++
        }
    }
    if minlen == math.MaxFloat64 {
        return 0
    }
    return int(minlen)
}

这里要注意minlen = math.Min(minlen, float64(right-left+1)) 的输入输出都是float64，所以minlen := math.MaxFloat64 取的是float64，最终返回值是int，所以要强转。

剑指 Offer II 009. 乘积小于 K 的子数组

这个不难，由于给定的是正整数，所以只要从左到右乘进去，然后再从左到右除，一个O(n)的时间复杂度就可以搞定。
一个很基础的双指针问题。

func numSubarrayProductLessThanK(nums []int, k int) int {
    product := 1
    left := 0
    count := 0
    for right := 0 ; right < len(nums) ; right++{
        product *= nums[right]
        for left <= right && product >= k{
            product /= nums[left]
            left++// 注意left是跟随向右走的
        }
        if right >= left{
            count += right-left+1
        }else{
            count += 0
        }
    }
    return count
}

2.3 累加数组数字求子数组之和

剑指 Offer II 010. 和为 k 的子数组

这个有个问题，求连续数组的和，那不能排序；整数数组，可能有负数，所以不能用双指针，因为可能越加越少；
所以要用哈希表，存sumToCount，

func subarraySum(nums []int, k int) int {
    sumToCount := make(map[int]int, len(nums))
    sumToCount[0] = 1

    sum := 0
    count := 0
    for _, num := range nums{
        sum += num
        v, ok := sumToCount[sum-k]
        if ok{
            count += v // 存在一个sum-k，就加一个，这里是为了统计结果
        }
        // v, ok = sumToCount[sum]
        // if !ok{
        //     v = 0
        // }
        // 用这一行，代替上边一段，因为如果获取结果失败，刚好把v设为默认值0
        v, _ = sumToCount[sum]
        sumToCount[sum] = v+1 //这里才是统计sum
    }
    return count
}

剑指 Offer II 011. 0 和 1 个数相同的子数组

func findMaxLength(nums []int) int {
    sumToIndex := make(map[int]int, len(nums))
    sumToIndex[0] = -1
    sum := 0
    maxLength := 0
    for i := 0 ; i < len(nums) ; i++{
        if nums[i] == 0{
            sum += -1
        }else{
            sum += 1
        }
        if index, ok := sumToIndex[sum]; ok{
            temp := i - index
            if maxLength < temp {
                maxLength = temp
            }
        }else{
            sumToIndex[sum] = i
        }
    }
    return maxLength
}

关键点，累加到当前位置得到一个sum，判断是否之前已经有过这样一个累加值。如果有，那么到到上一个下标之间这段就是最长子数组。
goLang的一个语法糖，if 可以用;分割，分号之后做判断条件。

剑指 Offer II 012. 左右两边子数组的和相等

func pivotIndex(nums []int) int { 
    total := 0
    for  _, num := range nums {
        total += num
    }
    sum := 0
    for i, length := 0, len(nums); i < length; i++ {
        sum += nums[i]
        if( sum-nums[i] == total - sum){
            return i
        }
    }
    return -1
}

注意Java中求数组和可以用流，例如：

int total = Arrays.stream(nums).sum();

剑指 Offer II 013. 二维子矩阵的和

这个题没有调试出来！！！
后来应该是用chatGPT改出来的，但是不知道为什么csdn没有保存上一次的修改记录

type NumMatrix struct {
    sums [][]int
}


func Constructor(matrix [][]int) NumMatrix {
    rows, cols := len(matrix), len(matrix[0])
    sums := make([][]int, rows+1)
    for i := range sums {
        sums[i] = make([]int, cols+1)
    }

    for i := 1; i <= rows; i++ {
        for j := 1; j <= cols; j++ {
            sums[i][j] = matrix[i-1][j-1] + sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1]
        }
    }

    return NumMatrix{sums: sums}
}


func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
    return this.sums[row2+1][col2+1] - this.sums[row1][col2+1] - this.sums[row2+1][col1] + this.sums[row1][col1]
}


/**
 * Your NumMatrix object will be instantiated and called as such:
 * obj := Constructor(matrix);
 * param_1 := obj.SumRegion(row1,col1,row2,col2);
 */

3、字符串

3.2 双指针

剑指 Offer II 014. 字符串中的变位词

3.3 回文字符串

剑指 Offer II 018. 有效的回文

func isPalindrome(s string) bool {
    left := 0
    right := len(s)-1
    for left < right {
        ch1 := s[left]
        ch2 := s[right]
        if !isLetterOrDigit(ch1) {
            left++
        } else if !isLetterOrDigit(ch2) {
            right--
        }else {
            ch1 = toLowerCase(ch1)
            ch2 = toLowerCase(ch2)
            if ch1 != ch2{
                return false
            }
            left++
            right--
        }
    }
    return true

}
func isLetterOrDigit(ch byte) bool{
    if (byte('A') <= ch && ch <= byte('Z')) || (byte('a') <= ch && ch <= byte('z')) || (byte('0') <= ch && ch <= byte('9')) {
        return true
    }
    return false
}
func toLowerCase(ch byte) byte{
    if byte('A') <= ch && ch <= byte('Z'){
        return ch - byte('A') + byte('a')
    }
    return ch
}

字符处理：
判断是字母或数字
Java
Character.isLetterOrDigit(ch);
goLang
需要自己判断
主要goLang的字符是byte
字符串中取某个值
Java
str.charAt(index);
goLang
ch1 := s[left]

剑指 Offer II 019. 最多删除一个字符得到回文

func validPalindrome(s string) bool {
    left := 0
    right := len(s)-1
    for left < right {
        ch1 := s[left]
        ch2 := s[right]
        if ch1 != ch2 {
            s1 := s[left: right]
            s2 := s[left+1: right+1]
            fmt.Println(s1)
            fmt.Println(s2)
            return (isPalindrome(s1) || isPalindrome(s2))
        }
        left++
        right--
    }
    return true
}
func isPalindrome(s string) bool {
    left := 0
    right := len(s)-1
    for left < right {
        ch1 := s[left]
        ch2 := s[right]
        if !isLetterOrDigit(ch1) {
            left++
        } else if !isLetterOrDigit(ch2) {
            right--
        }else {
            ch1 = toLowerCase(ch1)
            ch2 = toLowerCase(ch2)
            if ch1 != ch2{
                return false
            }
            left++
            right--
        }
    }
    return true

}
func isLetterOrDigit(ch byte) bool{
    if (byte('A') <= ch && ch <= byte('Z')) || (byte('a') <= ch && ch <= byte('z')) || (byte('0') <= ch && ch <= byte('9')) {
        return true
    }
    return false
}
func toLowerCase(ch byte) byte{
    if byte('A') <= ch && ch <= byte('Z'){
        return ch - byte('A') + byte('a')
    }
    return ch
}

剑指 Offer II 020. 回文子字符串的个数

func countSubstrings(s string) int {
    if s == "" || len(s) == 0 {
        return 0
    }

    count := 0
    for i := 0 ; i < len(s) ; i++{
        count += countPalindrome(s, i, i)
        count += countPalindrome(s, i, i+1)
    }
    return count
}

func countPalindrome(s string, start int, end int) int {
    count := 0
    for start >= 0 && end < len(s) && s[start] == s[end] {
        count++
        start--
        end++
    }
    return count
}

书中Java代码第一个边界判断是判断s==null，如果go写s==nil就有问题，因为string不匹配nil，string是有默认值的，如果需要判空，那么就写s==""。

4、链表

4.3 双指针

剑指 Offer II 021. 删除链表的倒数第 n 个结点

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{
        0,
        nil,
    }
    dummy.Next = head

    front := head
    back := dummy

    for i := 0 ; i < n ; i++ {
        front = front.Next // 为什么可以一直next，因为条件是 n <= sz
    }
    for front != nil {
        front = front.Next
        back = back.Next
    }
    back.Next = back.Next.Next
    return dummy.Next
}

最初对dummy初始化的时候写成了

    dummy := ListNode{
        0,
        nil,
    }

这导致了dummy是个ListNode，但是他的Next是指针，在执行back = back.Next的时候失败，利用chatGPT找到了问题。

剑指 Offer II 022. 链表中环的入口节点

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    inLoop := getNodeInLoop(head)
    if inLoop == nil {
        return nil
    }
    node := head
    for node != inLoop {
        node = node.Next
        inLoop = inLoop.Next
    }
    return node
}

func getNodeInLoop(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return nil
    }
    slow := head.Next
    fast := slow.Next
    for slow != nil && fast != nil {
        if slow == fast {
            return slow
        }
        slow = slow.Next
        fast = fast.Next
        if fast != nil {
            fast = fast.Next
        }
    }
    return nil
}

快慢指针判断是否成环，然后一个从头，一个从交汇地往前走，再次交汇就是入口

剑指 Offer II 023. 两个链表的第一个重合节点

这个是第一次涉及到结构体，第一次出错特别多，直接在程序中注释

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    count1 := countList(headA)
	count2 := countList(headB)
	delta := math.Abs(count1-count2) // math.Abs()的入参和返回值都是float64
    var longer *ListNode // 为了要将headA赋给longer，longer也应该是一个指针
    var shorter *ListNode
    if count1 > count2 { longer = headA } else { longer = headB} // goLang没有三元表达式，必须强制使用if
    if count1 > count2 { shorter = headB } else { shorter = headA}
	node1 := longer
	for i := 0.0 ; i < delta; i++{
		node1 = node1.Next
	}
	node2 := shorter
	for node1 != node2 {
		node1 = node1.Next
		node2 = node2.Next
	}
	return node1
    
}
func countList(head *ListNode) float64{
    count := 0.0
    for head != nil {
        count++
        head = head.Next
    }
    return count
}

4.4 反转链表

剑指 Offer II 024. 反转链表

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var prev *ListNode // prev := nil不可以
    cur := head
    for cur != nil {
        next := cur.Next
        cur.Next = prev
        prev = cur
        cur = next
    }
    return prev
}

剑指 Offer II 025. 链表中的两数相加

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    l1 = reverseList(l1)
    l2 = reverseList(l2)
    reversedHead := addReversed(l1, l2)
    return reverseList(reversedHead)
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode // prev := nil不可以
    cur := head
    for cur != nil {
        next := cur.Next
        cur.Next = prev
        prev = cur
        cur = next
    }
    return prev
}

func addReversed(head1 *ListNode, head2 *ListNode) *ListNode {
    dummy := &ListNode{
        0,
        nil,
    }
    sumNode := dummy
    carry := 0
    for head1 != nil || head2 != nil {
        sum := 0
        if head1 != nil {
            sum += head1.Val
        }
        if head2 != nil {
            sum += head2.Val
        }
        sum += carry
        if sum >= 10 {
            carry = 1
        }else {
            carry = 0
        }
        if sum >= 10 {
            sum = sum - 10
        }
        newNode := &ListNode{
            sum,
            nil,
        }
        sumNode.Next = newNode
        sumNode = sumNode.Next
        if head1 != nil {
            head1 = head1.Next
        }
        if head2 != nil {
            head2 = head2.Next
        }
    }
    if carry > 0 {
        sumNode.Next = &ListNode{
            carry,
            nil,
        }
    }
    return dummy.Next
}

剑指 Offer II 026. 重排链表

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reorderList(head *ListNode)  {
    dummy := &ListNode{
        0,
        head,
    }
    fast, slow := dummy, dummy
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next
        if fast.Next != nil {
            fast = fast.Next
        }
    }
    temp := slow.Next
    slow.Next = nil
    link(head, reverseList(temp), dummy)
}

func link(node1, node2, head *ListNode) {
    prev := head
    for node1 != nil && node2 != nil {
        temp := node1.Next
        prev.Next = node1
        node1.Next = node2
        prev = node2
        node1 = temp
        node2 = node2.Next
    }
    if node1 != nil {
        prev.Next = node1
    }
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode // prev := nil不可以
    cur := head
    for cur != nil {
        next := cur.Next
        cur.Next = prev
        prev = cur
        cur = next
    }
    return prev
}

剑指 Offer II 027. 回文链表

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }
    slow := head
    fast := head.Next
    for fast.Next != nil && fast.Next.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    secondHalf := slow.Next
    if fast.Next != nil{
        secondHalf = slow.Next.Next // 当有奇数个节点，舍弃掉第一条链的最后一个
    }
    slow.Next = nil // 断开第一条和第二条的连接
    return equals(secondHalf, reverseList(head))
}
func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    cur := head;
    for cur != nil {
        next := cur.Next
        cur.Next = prev
        prev = cur
        cur = next
    }
    return prev
}
func equals(head1, head2 *ListNode) bool{
    for head1 != nil && head2 != nil {
        if head1.Val != head2.Val{
            return false
        }
        head1 = head1.Next
        head2 = head2.Next
    }
    return head1 == nil && head2 == nil
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null){
            return true;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode secondHalf = slow.next;
        if (fast.next != null){
            secondHalf = slow.next.next; // 当有奇数个节点，舍弃掉第一条链的最后一个
        }
        slow.next = null; // 断开第一条和第二条的连接
        return equals(secondHalf, reverseList(head));
    }
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;

    }
    private boolean equals(ListNode head1, ListNode head2){
        while (head1 != null && head2 != null){
            if (head1.val != head2.val){
                return false;
            }
            head1 = head1.next;
            head2 = head2.next;
        }
        return head1 == null && head2 == null;
    }
//    class ListNode {
//		int val;
//		ListNode next;
//
//		ListNode(int x) {
//			val = x;
//			next = null;
//		}
//	}
}

思考：为什么这里要判断边界，24题不需要，仅仅是因为返回值不同吗？这里返回boolean，24返回链表
这个题用了快慢指针，快慢指针通常用于解决链表成环的问题，例如22题。

4.5 双向链表和循环链表

剑指 Offer II 028. 展平多级双向链表

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Prev *Node
 *     Next *Node
 *     Child *Node
 * }
 */

func flatten(root *Node) *Node {
    flattenGetTail(root)
    return root
}
func flattenGetTail(head *Node) *Node {
    node := head
    tail := &Node{
        0, nil, nil, nil,
    }
    for node != nil {
        next := node.Next
        if node.Child != nil {
            child := node.Child
            childTail := flattenGetTail(node.Child)
            node.Child = nil
            node.Next = child
            child.Prev = node
            childTail.Next = next
            if next != nil {
                next.Prev = childTail
            }
            tail = childTail
        }else {
            tail = node
        }
        node = next
    }
    return tail
}

剑指 Offer II 029. 排序的循环链表

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 * }
 */

func insert(head *Node, x int) *Node {
    node := &Node{
        x, nil,
    }
    if head == nil {
        head = node
        head.Next = head
    }else if head.Next == head {
        head.Next = node
        node.Next = head
    }else {
        insertCore(head, node)
    }
    return head
}
func insertCore(head, node *Node) {
    cur, next, biggest := head, head.Next, head
    for !(cur.Val <= node.Val && next.Val >= node.Val) && next != head {
        cur = next
        next = next.Next
        if cur.Val >= biggest.Val {
            biggest = cur
        }
    }
    if cur.Val <= node.Val && next.Val >= node.Val {
        cur.Next = node
        node.Next = next
    }else {
        node.Next = biggest.Next
        biggest.Next = node
    }
}

5、哈希表

5.2 哈希表的设计

剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器

先贴chatGPT给的正确答案
这里要特别注意随机数生成的写法，否则很容易报

panic: invalid argument to Intn
math/rand.(*Rand).Intn(0x8?, 0x4b4560?)
rand.go, line 168
math/rand.Intn(...)
rand.go, line 337
main.(*RandomizedSet).GetRandom(0xc00005cd80)
solution.go, line 45
main.(*DriverSolution).Helper_Select_Method(0x4b76e0?, {0xc000014080?, 0x0?}, {0x5ac9f8?, 0x7?, 0x8?}, 0xc00005cd80?)
solution.go, line 74
main.(*DriverSolution).Helper(0xc0000560c0?, {0xc000076120, 0x8, 0x4b3ee0?}, {0xc000084000, 0x8, 0xc000014038?})
solution.go, line 126
main.main()
solution.go, line 171

这个错误和导包没关系，leetcode会自动导包。

type RandomizedSet struct {
    numToLocation map[int]int
    nums []int
}


/** Initialize your data structure here. */
func Constructor() RandomizedSet {
    numToLocation := make(map[int]int)
    nums := make([]int, 0)
    rand.Seed(time.Now().UnixNano())
    return RandomizedSet{numToLocation, nums}
}


/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
func (this *RandomizedSet) Insert(val int) bool {
    _, ok := this.numToLocation[val]
    if ok {
        return false
    }
    this.numToLocation[val] = len(this.nums)
    this.nums = append(this.nums, val)
    return true
}


/** Removes a value from the set. Returns true if the set contained the specified element. */
func (this *RandomizedSet) Remove(val int) bool {
    loc, ok := this.numToLocation[val]
    if !ok {
        return false
    }
    this.numToLocation[this.nums[len(this.nums)-1]] = loc
    delete(this.numToLocation, val)

    this.nums[loc] = this.nums[len(this.nums)-1]
    this.nums = this.nums[:len(this.nums)-1]
    return true
}


/** Get a random element from the set. */
func (this *RandomizedSet) GetRandom() int {
    loc := rand.Intn(len(this.nums))
    return this.nums[loc]
}

剑指 Offer II 031. 最近最少使用缓存

type LRUCache struct {
    head *LRUListNode
    tail *LRUListNode
    lruMap map[int]*LRUListNode
    capacity int
}

type LRUListNode struct {
    Key int
    Val int
    Next *LRUListNode
    Prev *LRUListNode
}

func Constructor(capacity int) LRUCache {
    head := &LRUListNode{-1, -1, nil, nil}
    tail := &LRUListNode{-1, -1, nil, head}
    head.Next = tail
    lruMap := make(map[int]*LRUListNode)
    return LRUCache{head, tail, lruMap, capacity}
}


func (this *LRUCache) Get(key int) int {
    node, ok := this.lruMap[key]
    if !ok {
        return -1
    }
    this.moveToTail(node, node.Val)
    return node.Val
}

func (this *LRUCache) moveToTail(node *LRUListNode, newVal int) {
    this.deleteNode(node)
    node.Val = newVal
    this.insertToTail(node)
}

func (this *LRUCache) deleteNode(node *LRUListNode) {
    node.Prev.Next = node.Next
    node.Next.Prev = node.Prev
}

func (this *LRUCache) insertToTail(node *LRUListNode) {
    this.tail.Prev.Next = node
    node.Prev = this.tail.Prev
    node.Next = this.tail
    this.tail.Prev = node
}


func (this *LRUCache) Put(key int, value int)  {
    if _, ok := this.lruMap[key]; ok {
        this.moveToTail(this.lruMap[key], value)
    } else {
        if len(this.lruMap) == this.capacity {
            toBeDeleted := this.head.Next
            this.deleteNode(toBeDeleted)
            delete(this.lruMap, toBeDeleted.Key)
        }
        node := &LRUListNode{key, value, nil, nil}
        this.insertToTail(node)
        this.lruMap[key] = node
    }
}


/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

5.3 哈希表的应用

剑指 Offer II 032. 有效的变位词

func isAnagram(s string, t string) bool {
    if len(s) != len(t) || s == t{
        return false
    }
    counts := [26]int{} // 初始化一个数组
    for _, ch := range s { // 遍历一个字符串
        counts[ch-'a']++
    }
    for _, ch := range t {
        if counts[ch-'a'] == 0{
            return false
        }
        counts[ch-'a']--
    }
    return true
}

剑指 Offer II 034. 外星语言是否排序

func isAlienSorted(words []string, order string) bool {
    orderArray := [26]int{}
    for i := 0 ; i < len(order) ; i++{
        orderArray[order[i]-'a'] = i
    }
    for i := 0 ; i < len(words)-1 ; i++{ // 注意边界
        if !isSorted(words[i], words[i+1], orderArray){
            return false
        }
    }
    return true
}

func isSorted(word1,word2 string, order [26]int) bool{
    i := 0
    for ; i < len(word1) && i < len(word2) ; i++{
        ch1 := word1[i];
        ch2 := word2[i];
        if order[ch1-'a'] < order[ch2-'a']{
            return true
        }
        if order[ch1-'a'] > order[ch2-'a']{
            return false
        }
    }
    return i == len(word1) // 前缀相同，长度不同。如果等于第一个的长度，那说明第一个遍历结束，第一个比第二个短，也就是第一个在前
}

7、队列

7.1 基础知识

Queue的方法

操作抛异常不抛异常
插入元素add(e)offer(e)
删除元素removepoll
返回最前面的元素elementpeek

可以看出Java处理队列问题真简单，但是goLang没有队列。。。
goLang处理队列问题通常是切片或者链表，大概相当与ArrayList和LinkedList
参考文章golang的两种队列实现方式

7.2 队列的应用

剑指 Offer II 041. 滑动窗口的平均值

class MovingAverage {

    private Queue<Integer> nums;
    private int capacity;
    private int sum;
    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        nums = new LinkedList<>();
        capacity  = size;
    }
    
    public double next(int val) {
        nums.offer(val);
        sum += val;
        if (nums.size() > capacity){
            sum -= nums.poll();
        }
        return (double) sum / nums.size();
    }
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */

type MovingAverage struct {
    queue []int
	cap int
	sum int
}


/** Initialize your data structure here. */
func Constructor(size int) MovingAverage {
    var ins = MovingAverage{
		make([]int, 0, size+2),
		size,
		0,
	}
	return ins 
}


func (this *MovingAverage) Next(val int) float64 {
    this.queue = append(this.queue, val)
    this.sum += val
    if len(this.queue) > this.cap {
        this.sum -= this.queue[0]
        this.queue = this.queue[1:this.cap+1]
    }
    return float64(this.sum)/float64(len(this.queue))
}


/**
 * Your MovingAverage object will be instantiated and called as such:
 * obj := Constructor(size);
 * param_1 := obj.Next(val);
 */

这真的是一种奇怪的写法，通过切片的截取实现了和队列一样的先进先出效果，我朋友跟我讲切片就是队列，那就先这样吧。
这里要注意几个点：
初始化结构体的时候，最后一个元素后边还要加","，我不知道只是goLand的特性还是就该如此。
切片的截取则是前包后不包，所以cap要+1

剑指 Offer II 042. 最近请求次数

import java.util.LinkedList;
import java.util.Queue;

//leetcode submit region begin(Prohibit modification and deletion)
class RecentCounter {
    private Queue<Integer> times;
    private int windowSize;

    public RecentCounter() {
        times = new LinkedList<>();
        windowSize = 3000;
    }
    
    public int ping(int t) {
        times.offer(t);
        while (times.peek() + windowSize < t){
            times.poll();
        }
        return times.size();
    }
}

/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter obj = new RecentCounter();
 * int param_1 = obj.ping(t);
 */
//leetcode submit region end(Prohibit modification and deletion)

type RecentCounter struct {
    times []int
	windowSize int
}


func Constructor() RecentCounter {
    var ins = RecentCounter{
        make([]int, 0, 10000),
        3000,
    }
    return ins
}


func (this *RecentCounter) Ping(t int) int {
    this.times = append(this.times, t)
    for this.times[0] + this.windowSize < t {
        this.times = this.times[1:]
    }
    return len(this.times)
}


/**
 * Your RecentCounter object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Ping(t);
 */

搞明白了41题，42题就很容易做了，就是个用切片代替Java-Queue的做法。

8、树

8.3 二叉搜索树

剑指 Offer II 052. 展平二叉搜索树

class Solution {
	public TreeNode increasingBST(TreeNode root) {
		Stack<TreeNode> stack = new Stack<>();
		TreeNode cur = root;
		TreeNode prev = null;
		TreeNode first = null;
		while (cur != null || !stack.isEmpty()) {
			// 已示例1为例，从栈底到栈顶依次是5321
			while (cur != null) {
				stack.push(cur);
				cur = cur.left;
			}
			cur = stack.pop();
			if (prev != null) {
				// 只有初始化的时候prev才是null，之后总是有值的
				prev.right = cur;
			} else {
				// 这里只会进来一次，然后指向最左子节点
				first = cur;
			}
			prev = cur;
			cur.left = null;
			cur = cur.right;
		}
		return first;
	}

	class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func increasingBST(root *TreeNode) *TreeNode {
    stack := make([]*TreeNode, 0, 0)
    cur := root
    var prev *TreeNode
    var first *TreeNode
    for cur != nil || len(stack) != 0{
        for cur != nil{
            stack = append(stack, cur)
            cur = cur.Left
        }
        cur = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if prev != nil{
            prev.Right = cur
        }else{
            first = cur
        }
        prev = cur
        cur.Left = nil
        cur = cur.Right
    }
    return first
}

这是第一次用切片来模拟栈，也是第一次使用指针。
用切片当栈用倒不复杂，出栈的时候len-1把最后一个舍弃掉就可以了。
指针初始化要记住形式 var first * TreeNode。

11、二分查找

11.2 在排序树组中二分查找

剑指 Offer II 068. 查找插入位置

func searchInsert(nums []int, target int) int {
    left := 0
    right := len(nums)-1
    for left <= right{
        mid := (left+right)/2
        if nums[mid] >= target && (mid == 0 || nums[mid-1] < target){
            return mid
        }
        if nums[mid] >= target {
            right = mid - 1
        }else{
            left = mid + 1
        }
    }
    return len(nums)
}

很基础的二分查找

剑指 Offer II 069. 山峰数组的顶部

func peakIndexInMountainArray(arr []int) int {
    left := 1
    right := len(arr) - 2
    for left <= right{
        mid := (left + right)/2
        if arr[mid] > arr[mid+1] && arr[mid] > arr[mid-1]{
            return mid
        }
        if arr[mid] > arr[mid-1]{
            left = mid+1
        } else {
            right = mid-1
        }
    }
    return -1
}

很基础的二分查找

11.3 在数值范围内二分查找

剑指 Offer II 072. 求平方根

func mySqrt(x int) int {
    left := 1
    right := x
    for left <= right {
        mid := (left + right)/2
        if mid <= x / mid && (mid+1) > x / (mid+1) { // 注意：mid*mid <= x 数学上等价，但是会溢出
            return mid
        }
        if mid <= x / mid{
            left = mid + 1
        }else{
            right = mid - 1
        }
    }
    return 0
}
}

12、排序

12.2 计数排序

剑指 Offer II 075. 数组相对排序

func relativeSortArray(arr1 []int, arr2 []int) []int {
    var counts [1001]int
    for _, num := range arr1 {
        counts[num]++
    }

    i := 0
    for _, num := range arr2{
        for counts[num] > 0{
            arr1[i] = num
            i++
            counts[num]--
        }
    }

    for num := 0 ; num < len(counts) ; num++{
        for counts[num] > 0 {
            arr1[i] = num
            i++
            counts[num]--
        }
    }
    return arr1
}

注意range的写法， 是:= range
并且，arr1[i++]的写法也是错误的

总结

提示：这里对文章进行总结：
例如：以上就是今天要讲的内容，本文仅仅简单介绍了pandas的使用，而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。

更多推荐

leetcode-剑指offer（专项突破版）-go语言实现