笔试题五道

笔试题五道

只能说自己抗压能力实在是太一般了。。

反转链表：

import "fmt"

//输入: 1->2->3->4->5->NULL
//输出: 5->4->3->2->1->NULL

type ListNode struct {
    Val  int
    Next *ListNode
}

func main() {
    fmt.Printf("%+v",ReversalList(&ListNode{
        Val:  1,
        Next: &ListNode{
            Val:  2,
            Next: &ListNode{
                Val:  3,
                Next: nil,
            },
        },
    }))
}
func ReversalList(listNode *ListNode) *ListNode {
   if listNode == nil {
      return nil
   }
   preNode := new(ListNode)
   nowNode := listNode
   nextNode := new(ListNode)
   for nowNode != nil {
      nextNode = nowNode.Next
      nowNode.Next = preNode
      preNode = nowNode
      nowNode = nextNode
   }
   return preNode
}

合并数组

//输入:
//A = [1,2,3,0,0,0], m = 3
//B = [2,5,6],       n = 3
//输出: [1,2,2,3,5,6]

func main() {
   fmt.Printf("%+v", getNewArray([]int{1, 2, 3, 0, 0, 0}, 3, []int{2, 5, 6}, 3))
}

//从尾往前排序
func getNewArray(a []int, m int, b []int, n int) []int {
   if len(a) < m+n {
      return make([]int, 0)
   }
   nowIndex := m + n -1
   for n-1 >= 0 {
      if b[n-1] >= a[m-1] {
         a[nowIndex] = b[n-1]
         n--
      } else {
         //将a往后移动到指定位置
         a[m-1], a[nowIndex] = a[nowIndex], a[m-1]
         m--
      }
      nowIndex--
   }
   return a
}

橘子腐烂：

package main

import "fmt"

func main() {

    fmt.Printf("%d",orangesRotting([][]int{
        {2, 1, 0}, {1, 1, 0}, {0, 1, 1},
    }))
}

func orangesRotting(grid [][]int) int {
    if len(grid) <= 0 || len(grid[0]) <= 0 {
        return 0
    }
    listRotting := make([]int, 0)
    rottingMap := make(map[int]int)
    row := len(grid)
    col := len(grid[0])
    //遍历数组，找出那些腐烂的橘子,入队列进行广度搜索
    for i := 0; i < row; i++ {
        for j := 0; j < col; j++ {
            if grid[i][j] == 2 {
                listRotting = append(listRotting, i*col+j)
                rottingMap[i*col+j] = 0
            }
        }
    }
    //用来定位上下左右
    dc := []int{-1, 0, 1, 0}
    dr := []int{0, 1, 0, -1}
    walk := -1
    for len(listRotting) > 0 {
        rot := listRotting[0]
        listRotting = listRotting[1:]
        i := rot / col
        j := rot % col
        for k := 0; k < 4; k++ {
            checkI := i + dr[k]
            checkJ := j + dc[k]
            if checkI >= 0 && checkJ >= 0 && checkI < row && checkJ < col && grid[checkI][checkJ] == 1 {
                grid[checkI][checkJ] = 2
                checkRoute := checkI*col + checkJ
                listRotting = append(listRotting, checkRoute)
                rottingMap[checkRoute] = rottingMap[rot] + 1
                if walk < rottingMap[checkRoute] {
                    walk = rottingMap[checkRoute]
                }
            }
        }
    }
    for i := 0; i < row; i++ {
        for j := 0; j < col; j++ {
            if grid[i][j] == 1 {
                return -1
            }
        }
    }
    return walk
}

能获取最大值的队列

type MaxQueue struct {
    MaxList []int
    List    []int
}

func Constructor() MaxQueue {
    return MaxQueue{
        MaxList: make([]int, 0),
        List:    make([]int, 0),
    }
}

func (this *MaxQueue) MaxValue() int {
    if len(this.MaxList) <= 0 {
        return -1
    }
    return this.MaxList[0]
}

func (this *MaxQueue) PushBack(value int) {
    for len(this.MaxList) > 0 && this.MaxList[len(this.MaxList)-1] < value {
        this.MaxList = this.MaxList[:len(this.MaxList)-1]
    }
    this.MaxList = append(this.MaxList, value)
    this.List = append(this.List, value)
}

func (this *MaxQueue) PopFront() int {
    if len(this.List) <= 0 {
        return -1
    }
    front := this.List[0]
    this.List = this.List[1:]
    if front == this.MaxList[0] {
        this.MaxList = this.MaxList[1:]
    }
    return front
}

第五题，树的深度

func MaxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return maxDepth(root,1)
}

func maxDepth(root *TreeNode, nowDepth int) int {
    if root == nil {
        return nowDepth
    }
    return max(maxDepth(root.Left, nowDepth+1), maxDepth(root.Right, nowDepth+1))
}

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