章节主要目的

此章主要练习的是沟通能力、学习能力、知识迁移能力、抽象建模能力等。这需要有扎实的数学基础，如果没有，相信，很多人会像我一样，一道题看很久才能看懂，要理解那就要借助视频，还要动手画图才可以理解的了。这是先天不足后天畸形的我们面向业务和搜索编程带来的硬伤。这种题目不会太难，但是很具有动脑的需要，如有必要，建议看原文。

正式开始第六章

面试题38：数字在排序数组中出现的次数

leetcode-cn.com/problems/zai-pai-x...

统计一个数字在排序数组中出现的次数

func search(nums []int, target int) int {
    //start := 0  
    //end := len(nums) - 1  
    //for i := 0; i < len(nums); i++ {  
    //    if nums[i] == target {  
    //        start = i  
    //        break  
    //    }  
    //}  
    //if start == -1 || start == len(nums) || nums[start] != target {  
    //    return 0  
    //}  
    //for i := 0; i < len(nums); i++ {  
    //    if nums[i] > target {  
    //        end = i - 1  
    //    }  
    //}  
    //fmt.Println(start,end)  
    //return end - start + 1

    //count := 0  
    //for i := 0; i < len(nums); i++ {  
    //    if nums[i] == target {  
    //        count++  
    //    }  
    //}  
    //return count

    //效率最高
    leftmost := sort.SearchInts(nums, target)
    if leftmost == len(nums) || nums[leftmost] != target {
        return 0
    }
    rightmost := sort.SearchInts(nums, target+1) - 1 
    return rightmost - leftmost + 1
}

这是课本上原文给的参考代码，C++的改写

func search(nums []int, target int) int {
    count := 0 
    if len(nums) == 0 {
        return count
    }
    first := getFirstTargetIndex(nums, target, 0, len(nums)-1)
    last := getLastTargetIndex(nums, target, 0, len(nums)-1)
    if first > -1 && last > -1 {
        count = last - first + 1
    }
    return count
}

func getFirstTargetIndex(nums []int, target, start, end int) int {
    if start > end {
        return -1
    }
    mid := (start + end) / 2
    fmt.Println(mid, start, end)
    midData := nums[mid]
    if midData > target {
        end = mid - 1
    } else if nums[mid] < target {
        start = mid + 1
    } else {
        if (mid > 0 && nums[mid-1] != target) || mid == 0 {
            return mid
        } else {
            end = mid - 1
        }
    }
    return getFirstTargetIndex(nums, target, start, end)
}
func getLastTargetIndex(nums []int, target, start, end int) int {
    if start > end {
        return -1
    }
    mid := (start + end) / 2
    midData := nums[mid]
    if midData > target {
        end = mid - 1
    } else if nums[mid] < target {
        start = mid + 1
    } else {
        if (mid < len(nums)-1 && nums[mid+1] != target) || mid == len(nums)-1 {
            return mid
        } else {
            start = mid + 1
        }
    }
    return getLastTargetIndex(nums, target, start, end)
}

都是精华吧，值得都看。

面试题39：二叉树的深度

leetcode-cn.com/problems/er-cha-sh...

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    fmt.Println(root.Val)
    left := maxDepth(root.Left)
    right := maxDepth(root.Right)
    if left > right {
        return left + 1
    } else {
        return right + 1
    }
}
//判断是不是一棵平衡二叉树
func isBalanced(root *TreeNode) bool {
   if root == nil {
      return true
  }
   fmt.Println(root.Val)
   left := maxDepth(root.Left)
   right := maxDepth(root.Right)
   diff := left - right
   if diff > 1 || diff < -1 {
      return false
  }
   return isBalanced(root.Left) && isBalanced(root.Right)
}

平衡二叉树是树上给的发散，也可以根据平衡二叉树来进行深度计算，并且会避免重复遍历结点。

面试题40：数组中出现一次的数字

leetcode-cn.com/problems/shu-zu-zh...

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

// 低效的实现方式
func singleNumbers(nums []int) []int {
    if len(nums) == 0 {
        return nil
    }
    sort.Ints(nums)
    fmt.Println(nums)
    result := make([]int, 0)
    if len(nums) == 1 {
        result = append(result, nums[0])
    }
    if nums[0] != nums[1] {
        result = append(result, nums[0])
    }
    if len(nums) > 1 && nums[len(nums)-2] != nums[len(nums)-1] {
        result = append(result, nums[len(nums)-1])
    }
    for i := 1; i < len(nums)-1; i++ {
        if nums[i] != nums[i-1] && nums[i] != nums[i+1] {
            result = append(result, nums[i])
        }
    }
    return result
}

// 题目限定了必须有两个一次的数字，其他的两次
// 分组异或
func singleNumbers(nums []int) []int {
   if len(nums) == 0 {
      return nil
  }
   result := make([]int, 2)
   ret := 0 
  for _, v := range nums {
      ret ^= v
   }
   div := 1 
  for (div & ret) == 0 {
      div <<= 1
  }
   for _, v := range nums {
      if (div & v) != 0 {
         result[0] ^= v
      } else {
         result[1] ^= v
      }
   }

   return result
}

面试题41-1：和为S的两个数字

leetcode-cn.com/problems/he-wei-sd...

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

func twoSum(nums []int, target int) []int {
    if len(nums) == 0 {
        return nil
    }
    result := make([]int, 0)
    left := 0
    right := len(nums) - 1 
    for left <= right {
        if nums[left]+nums[right] == target {
            result = append(result, []int{nums[left], nums[right]}...)
            break
        } else if nums[left]+nums[right] > target {
            right--
        } else {
            left++
        }
    }
    return result
}

面试题41-2：和为s的连续正数序列

leetcode-cn.com/problems/he-wei-sd...

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列.

//双指针
func findContinuousSequence(target int) [][]int {
    result := make([][]int, 0)
    if target < 3 {
        return nil
    }
    small, big, middle := 1, 2, (1+target)/2
    curSum := small + big
    for small < middle {
        if curSum == target {
            result = append(result, addSeq(small, big))
        }
        for curSum > target && small < middle {
            curSum -= small
            small++
            if curSum == target {
                result = append(result, addSeq(small, big))
            }
        }
        big++
        curSum += big
    }

    return result
}

func addSeq(small, big int) (result []int) {
    for i := small; i <= big; i++ {
        result = append(result, i)
    }
    return
}

面试题42-1：翻转单词顺序

leetcode-cn.com/problems/fan-zhuan...

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。

func reverseWords(s string) string {
    split := strings.Split(s, " ")
    var res []string 
    for i := len(split) - 1; i >= 0; i-- {
        if split[i] != ""{
            res = append(res, split[i])
        }
    }
    fmt.Println(res)
    return strings.Join(res, " ")
}

面试题42-2：左旋转字符串

leetcode-cn.com/problems/zuo-xuan-...

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。

请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。

func reverseLeftWords(s string, n int) string {
    //边界条件可以不用判断  
    //res := make([]uint8, len(s), len(s))  
    //for i := 0; i < len(s); i++ {  
    //    res[i] = s[i]  
    //}
    s1 := s[:n]
    s2 := s[n:]
    return s2 + s1
}

面试题43：n个骰子的点数

leetcode-cn.com/problems/nge-tou-z...

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

//参考的Java代码实现的方式写的，这笔课本上的要简便一点，实际上原理是一样的
func dicesProbability(n int) []float64 {
    if n < 1 {
        return nil
    }
    dp := make([][]float64, n)
    for i := range dp {
        dp[i] = make([]float64, (i+1)*6-i)
    }
    for i := range dp[0] {
        dp[0][i] = float64(1) / float64(6)
    }
    for i := 1; i < len(dp); i++ {
        for j := range dp[i-1] {
            for k := range dp[0] {
                dp[i][j+k] += dp[i-1][j] * dp[0][k]
            }
        }
    }
    return dp[n-1]
}

面试题44：扑克牌中的顺子

leetcode-cn.com/problems/bu-ke-pai...

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

func isStraight(nums []int) bool {
    if len(nums) != 5 {
        return false
    }
    //1、先排个序
    sort.Ints(nums)
    //2、记录0的个数
    zeroNum := 0 
    for i := 0; i < len(nums); i++ {
        if nums[i] == 0 {
            zeroNum++
        }
    }
    //fmt.Println(zeroNum)  
    //3、判断是否可以组成顺子  
    for i := zeroNum; i < len(nums)-1; i++ {
        //fmt.Println(nums[i], nums[i+1])  
        if nums[i+1] == nums[i] { //有相等的，直接返回false  
            return false
        } else if nums[i+1]-nums[i] > 1 {
            //fmt.Println(nums[i], nums[i+1])
            zeroNum -= nums[i+1] - nums[i] - 1 
            if zeroNum < 0 {
                return false
            }
        }
    }
    return true
}

面试题45：圆圈中最后剩下的数字

leetcode-cn.com/problems/yuan-quan...

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

规律，看书本的，我没这个水平推出来

func lastRemaining(n int, m int) int {
    if n < 1 || m < 1 {
        return -1
    }
    last := 0 
    for i := 2; i <= n; i++ {
        last = (last + m) % i
    }

    return last
}

面试题46：求1+2+…+n

leetcode-cn.com/problems/qiu-12n-l...

求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

//似乎只能想到递归了
func sumNums(n int) int {
   if n == 0 {
      return 0
  }
   return n + sumNums(n-1)
}

面试题47：不用加减乘除做加法

leetcode-cn.com/problems/bu-yong-j...

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

//除了位运算，别无他法了吧，但是用了其他符号，leetcode也检测不出来
func add(a int, b int) int {
    sum, carry := 0, 0 
    for b != 0 {
        sum = a ^ b
        carry = (a & b) << 1
        a = sum
        b = carry
    }
    return a
}

面试题48：不能被继承的类

不适合Go语言，没有这一说法吧，难道还能实现不能被继承的结构体不成？

小结

从这个时间就可以看出来，最难的就是抽象建模。至于发散思维，很好理解，起码会一种了，看其他的就很好递推了。这一张题目并不是十分难，就几道题，可能没什么思路，需要看答案解析才能写出代码，更多的是靠自觉来按照要求来编写，leetcode的工具检测并没有这么完善。建议，看原文，这里贴出来的知识为了记录一下我是这么分阶段来练习的。分解任务嘛，光是坚持到这里的，我相信已经是很少部分人了。第七章，我建议，强烈建议看原文，因为重点并不在于题目而是在于原文的描述和出题的意图。

章节主要目的

看题目就知道用意是什么，强烈建议看原文，题目并不是重点，题目相信并不难，都是简单的题目，但是，沟通能力和题目的边界情况的考虑以及和面试官的沟通反而显得更加重要，我们要做的就是超过面试官原先对我们的期待那就一定能拿到offer。再次强烈建议看原文，内容并不多。

正式开始第七章

面试题49:把字符串转换成整数

leetcode-cn.com/problems/ba-zi-fu-...

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。在任何情况下，若函数不能进行有效的转换时，请返回 0。

func strToInt(str string) int {
    index := 0 
    for i := 0; i < len(str) && str[i] == ' '; i++ {
        index = i
    }
    str = str[index:] //第一个非空格的字符开始
    ans := 0
    flag := false

    for i, v := range str {
        if v >= '0' && v <= '9' {
            ans = ans*10 + int(v-'0')
        } else if v == '-' && i == 0 {
            flag = true
        } else if v == '+' && i == 0 {
        } else {
            break
        }

        if ans > math.MaxInt32 {
            if flag {
                return math.MinInt32
            }
            return math.MaxInt32
        }
    }
    if flag {
        return -1 * ans
    }
    return ans
}

面试题50：二叉搜索树的最近公共祖先

leetcode-cn.com/problems/er-cha-so...

中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

非常遗憾，不支持GO的语言编写，但是官方提供了Go的例子、

func lowestCommonAncestor(root, p, q *TreeNode) (ancestor *TreeNode) {
    pathP := getPath(root, p)
    pathQ := getPath(root, q)
    for i := 0; i < len(pathP) && i < len(pathQ) && pathP[i] == pathQ[i]; i++ {
        ancestor = pathP[i]
    }
    return
}
func getPath(root, target *TreeNode) (path []*TreeNode) {
    node := root
    for node != target {
        path = append(path, node)
        if target.Val < node.Val {
            node = node.Left
        } else {
            node = node.Right
        }
    }
    path = append(path, node)
    return path
}

小结

我这50道题给出的都是题目和一个参考答案以及多个参考答案，但都不是重点，重点是通过这些题去思考自己的实现方式。联系的重要性不言而喻，有的可能不用敲出来，但是起码要会说出来。作为追求，万年不会过时的算法，我们都应该长久的去做，别让脑袋秀逗了。

好多小伙伴私聊我说怎么这么厉害的，我其实就是个菜鸡，看起来很厉害，我算法真的是很low,不然不会从这本书开始，因为算法是在太难了，找个有针对性的去练习才能找到成就感和方向感，不然太盲目了。最后贴上高频考点，这是我花了一块钱报的培训课程里面给出来的，感觉有点帮助。

有人好奇我在涂鸦做什么岗位，顺便回答一下。我在涂鸦不是做算法的，做的是设备生态，边缘网关相关的。这些词对于没接触过iot的人来说很陌生，没关系，我也很陌生。主要的用到和CURD不同的技术是CGO和mqtt，算是和业务脱钩了，不过技术本身都是一样的，没什么差别。技术栈都是一样的，作为云端后台开发的岗位，基本和你们差不多的。