章节主要目的

虽说这章节主要的目的是优化时间和空间，但是我们都知道，这才是我们最头痛的优化，因为各种原理和实现方式，是很难让人理解的，也很难做到创新，即使是前人想出来的方案，我们依旧很难用代码实现，甚至理解都很难。上一片文章就说，这一章节是非常困难的，实际证明确实如此，这一章，是异常的艰辛。主要体会时间和空间的优化方案，大多数题都是可以通过二次循环做出来的，但是leetcode会提示超时，这也是一个考察的重点，防止使用双循环，空间方面反倒是限制不大，只要你想得到，基本都是空间换时间的方式。

正式开始第五章

面试题29：数组中出现次数超过一半的数字

leetcode-cn.com/problems/shu-zu-zh...
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
很消耗内存 最好加上验证不存在的情况，因为leetcode已经假设全部存在了，但是课本上的是没有假设的

func majorityElement(nums []int) int {
    cacheTimes := make(map[int]int)
    for i := 0; i < len(nums); i++ {
        times := cacheTimes[nums[i]]
        times++
        cacheTimes[nums[i]] = times
        fmt.Println(times)
        if times > len(nums)/2 {
            return nums[i]
        }
    }
    return 0
}

这是一道找信心的题目。

面试题30：最小的k个数

leetcode-cn.com/problems/zui-xiao-...
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
一个容器存储这k个数

func getLeastNumbers(arr []int, k int) []int {
    //快排
    //sort.Ints(arr)
    //return arr[:k]
    //数组容器
    cacheSlice := make([]int, 0) //排好序的容器
    for i := 0; i < len(arr); i++ {
        if len(cacheSlice) >= k {
            //isChange := false
            for j := k-1; j >0; j-- {
                fmt.Println("cacheSlice[j]",cacheSlice[j],arr[i])
                if cacheSlice[j] > arr[i] {
                    //isChange = true
                    cacheSlice[j] = arr[i]
                    sort.Ints(cacheSlice)//需要重新排序一次，必定超时
                    break
                }
            }
        } else {
            //fmt.Println(arr[i])
            cacheSlice = append(cacheSlice,arr[i])
            sort.Ints(cacheSlice)
        }
    }
    return cacheSlice
}

堆实现的方式

func (h IHeap) Len() int           { return len(h) }
func (h IHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

// 时间和内存都消耗很大，重点是实现方式了，不要在意这些细节
func getLeastNumbers(arr []int, k int) []int {
    cacheHeap := &IHeap{}
    heap.Init(cacheHeap)
    for i := 0; i < len(arr); i++ {
        heap.Push(cacheHeap, arr[i])
        if cacheHeap.Len() > k {
            heap.Pop(cacheHeap)
        }
    }
    cacheSlice := make([]int, k, k)
    for i := 0; i < k; i++ {
        cacheSlice[i] = heap.Pop(cacheHeap).(int)
    }
    return cacheSlice
}

面试题31：连续子数组的最大和

leetcode-cn.com/problems/lian-xu-z...
动态规划

func maxSubArray(nums []int) int {
    length := len(nums)
    if length == 0 {
        return 0
    }
    dp := make([]int, length, length)
    dp[0] = nums[0]
    maxSum := dp[0]
    for i := 1; i < len(nums); i++ {
        if dp[i-1] < 0 {
            dp[i] = nums[i]
        } else {
            dp[i] = dp[i-1] + nums[i]
        }
        if maxSum < dp[i] {
            maxSum = dp[i]
        }
    }
    return maxSum
}

面试题32：1～n 整数中 1 出现的次数

leetcode-cn.com/problems/1nzheng-s...
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
困难级别的题

// 超时，起码可以实现，用字符串的方式
func countDigitOne(n int) int {
    count := 0
    for i := 0; i <= n; i++ {
        intStr := fmt.Sprintf("%s",i)
        for _,v := range intStr{
            if v == '1' {
                count++
            }
        }
    }
    return count
}

看官方的解答，我表示不懂，水平太差了，之所以分享出来是因为为了凑整😄

func countDigitOne(n int) (ans int) {
    // mulk 表示 10^k
    // 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）
    // 但为了让代码看起来更加直观，这里保留了 k
    for k, mulk := 0, 1; n >= mulk; k++ {
        ans += (n/(mulk*10))*mulk + min(max(n%(mulk*10)-mulk+1, 0), mulk)
        mulk *= 10
    }
    return
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

面试题33：把数组排成最小的数

leetcode-cn.com/problems/ba-shu-zu...
输出结果可能非常大，所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
并非单纯的比较两个数的大小，而是两个数拼接后的大小比较
思路：转换成字符串的数组比较，按从小到大的顺序直接拼接就是，至于为什么是这样，我也表示看了答案才知道这么做的。

func minNumber(nums []int) string {
    sort.Slice(nums, func(i, j int) bool {
        x := fmt.Sprintf("%d%d", nums[i], nums[j])
        y := fmt.Sprintf("%d%d", nums[j], nums[i])
        return x < y
    })
    //fmt.Println(nums)
    res := ""
    for i := 0; i < len(nums); i++ {
        res += fmt.Sprintf("%d", nums[i])
        //fmt.Println(res)
    }
    return res
}

面试题34：丑数

leetcode-cn.com/problems/chou-shu-...
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。习惯上，我们把1当作第一个丑数
n 不超过1690

// 超时版本
func nthUglyNumber(n int) int {
    count := 0
    res := 1
    for i := 1; count < n; i++ {
        if isUglyNumber(i) {
            count++
            //fmt.Println("count-> ",count,"i->",i)
            res = i
        }
    }
    return res
}
func isUglyNumber(n int) bool {
    for n%2 == 0 {
        n /= 2
    }
    for n%3 == 0 {
        n /= 3
    }
    for n%5 == 0 {
        n /= 5
    }
    return n == 1
}

//动态规划 空间换时间版本

func nthUglyNumber(n int) int {
    uglyNumbers := make([]int, n)
    uglyNumbers[0] = 1
    mult2, mult3, mult5 := 0,0,0
    for i := 1; i < n; i++ {
        temp2, temp3, temp5 := uglyNumbers[mult2]*2, uglyNumbers[mult3]*3, uglyNumbers[mult5]*5
        uglyNumbers[i] = min(min(temp2, temp3), temp5)
        if uglyNumbers[i] == temp2 {
            mult2++
        }
        if uglyNumbers[i] == temp3 {
            mult3++
        }
        if uglyNumbers[i] == temp5 {
            mult5++
        }
    }
    return uglyNumbers[n-1]
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

面试题35：第一个只出现一次的字符

leetcode-cn.com/problems/di-yi-ge-...
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

func firstUniqChar(s string) byte {
    cacheByte := make(map[byte]int)
    for i := 0; i < len(s); i++ {
        cacheByte[s[i]] = cacheByte[s[i]] + 1
    }
    for i := 0; i < len(s); i++ {
        if cacheByte[s[i]] == 1 {
            return s[i]
        }
    }
    return ' '
}

面试题36：数组中的逆序对

leetcode-cn.com/problems/shu-zu-zh...
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
毫无疑问，双循环一定会超时，代码不贴了，没意义

// 抄袭官网，归并排序，我也不会，也要加强练习练习
func reversePairs(nums []int) int {
    return mergeSort(nums, 0, len(nums)-1)
}

func mergeSort(nums []int, start, end int) int {
    if start >= end {
        return 0
    }
    mid := start + (end-start)/2
    cnt := mergeSort(nums, start, mid) + mergeSort(nums, mid+1, end)
    tmp := []int{}
    i, j := start, mid+1
    for i <= mid && j <= end {
        if nums[i] <= nums[j] {
            tmp = append(tmp, nums[i])
            cnt += j - (mid + 1)
            i++
        } else {
            tmp = append(tmp, nums[j])
            j++
        }
    }
    for ; i <= mid; i++ {
        tmp = append(tmp, nums[i])
        cnt += end - (mid + 1) + 1
    }
    for ; j <= end; j++ {
        tmp = append(tmp, nums[j])
    }
    for i := start; i <= end; i++ {
        nums[i] = tmp[i-start]
    }
    return cnt
}

面试题37：两个链表的第一个公共结点

leetcode-cn.com/problems/liang-ge-...
输入两个链表，找出它们的第一个公共节点。

//Definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    lenA := getNodeLength(headA)
    lenB := getNodeLength(headB)
    longNode := headA
    shotNode := headB
    kipSteps := lenA - lenB
    if lenB > lenA {
        kipSteps = lenB - lenA
        longNode = headB
        shotNode = headA
    }
    //长链表先走kipSteps，之后和短的一起走N步共同达到相同节点
    for i := 0; i < kipSteps; i++ {
        longNode = longNode.Next
    }

    for longNode != nil {
        if longNode == shotNode {
            return longNode
        }
        longNode = longNode.Next
        shotNode = shotNode.Next
    }
    return nil
}
// 获取链表长度
func getNodeLength(root *ListNode) (length int) {
    tail := root
    for tail != nil {
        length++
        tail = tail.Next
    }
    return length
}

小结

这里涉及到两道困难级别，可想而知，我也有几道题是看官方解答才知道的，象征性的贴了下代码，我自己也要多练习了，有时间还要review一下这些题，都是经典且难的题，就算不为面试，实际业务上也有用得着的地方。算法之所以难，是因为我们想不到实现方案，业务简单是因为有人把业务的实现方式一步一步怎么操作的详细的告诉我们了。都是动脑吧，多练习，不会错。后面的两章是道题，我估计起码要两周，春节前能吃透已经很不错了。好在年底了，工作不会太忙，空闲时间会比较多。有人说，看不下去，没心情也没动力。只能说，当作面试跳槽的八股文，那肯定没心情也没精力，当作兴趣爱好吧，权当大学老师给你多布置了题目，总之找个能坚持的理由吧，毕竟脑袋不用就会生锈的。

本作品采用《CC 协议》，转载必须注明作者和本文链接