笔试题五道
只能说自己抗压能力实在是太一般了。。
反转链表：
代码语言：javascript复制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
}合并数组
代码语言：javascript复制//输入:
//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
}橘子腐烂：
代码语言：javascript复制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
}能获取最大值的队列
代码语言：javascript复制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
}第五题，树的深度
代码语言：javascript复制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
}
