# 正式开始第五章

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

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

``````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-...

``````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：连续子数组的最大和

``````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...

``````// 超时，起码可以实现，用字符串的方式
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...

``````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-...

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-...

``````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
}

kipSteps := lenA - lenB
if lenB > lenA {
kipSteps = lenB - lenA
}
//长链表先走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
}``````

(=￣ω￣=)··· 暂无内容！

Go开发 @ 涂鸦智能

16

15

88

103