go 聲明二維數組_邊做題邊更新Go 語言常見資料結構詳解 + 面試題集合！

Go 語言誕生于谷歌，由計算機領域的三位宗師級大牛 Rob Pike、Ken Thompson 和 Robert Griesemer 寫成。誕生十年以來，Go 的發展勢頭相當迅猛，容器界的扛把子 Docker 就是用 Go 寫的，國内也有不少團隊把項目移植到了 Go 語言。

同時，據美國招聘網站 Hired 統計，Go 語言是 2019 年最受企業歡迎的語言，平均每位 Go 語言求職者會收到 9 份面試邀請，而面試中什麼最重要？自然是算法。 今天給大家帶來一個 Go 語言常見資料結構算法 + 面試題講解的教程，特别适合：

• 剛入門 Go 語言，想要更熟悉 Go 語言的特性，同時想更深入練習資料結構的同學；
• 正在準備 Go 語言面試和求職，急需強化資料結構、算法以及常見面試題的同學。

課程位址： https://www.shiyanlou.com/courses/1526 下面是課程的第一節内容，歡迎打開浏覽器進入實驗樓，使用免費的學習環境，邊敲代碼邊學習！

第一節：Golang 數組與切片

實驗介紹

從本實作開始我們将進入到 Golang 的學習之旅，Golang 的許多初學者都會對數組 (Array) 與切片 (Slice) 感到困惑。他們雖然同屬于集合類的類型，但是用起來卻十分不同。在本節實驗中，你将學習到數組與切片到底是哪裡不同，這裡也是 Golang 面試中的一個常考知識點。

知識點

• 數組的資料類型
• 數組的建立
• 數組的周遊
• Golang 數組與切片的差別
• 切片的擴容規律

Golang 數組基本操作

這一節開始，我們将學習 Golang 數組與切片的常用方法以及他們在具體面試中的常考知識點。

數組的聲明

Golang 中一個數組的聲明方式主要有以下幾種。

package mainfunc main() {// 第一種，在初始化時隻聲明數組長度，不聲明數組内容var arr1 [5]int// 第二種，知道資料很多，不想自己寫長度的時候可以用這種方式// 聲明之後由編譯器自己推算數組長度arr2 :=  [...]int{1,3,5,7,9}// 第三種，聲明的時候長度和初值一起聲明arr3 := [3]int{2,4,6}// 二維數組的聲明，其意義是三行五列var Block [3][5]int}
           

這裡值得一提的是 Golang 中的數組的初始值如果你不做聲明的話預設是全部有初值的。比如 

arr1

 這個數組雖然隻聲明了長度為 5，但是 Go 的編譯器也會把這 5 個元素全都初始化為 0。而對于 

bool

 值類型的數組，如果不做指派操作，則初始值全為 

false

。在接下來的數組周遊中我們會實際的驗證它。

數組的周遊

我們先在實驗樓線上實驗環境中建立建立一個名叫 

array

 的檔案夾。如下圖所示，先點選 File，然後點選 New Folder 建立名為 

array

 的檔案夾。

然後我們右鍵點選 

array

 檔案夾，選擇 New File，建立一個叫 

main.go

 的檔案，如下圖所示。

Go 的數組周遊主要有以下兩種方式。首先鍵入以下代碼：

package mainimport "fmt"func main() {// 第一種，在初始化時隻聲明數組長度，不聲明數組内容var arr1 [5]int// 第二種，知道資料很多，不想自己寫長度的時候可以用這種方式// 聲明之後由編譯器自己推算數組長度//arr2 :=  [...]int{1,3,5,7,9} 第三種，聲明的時候長度和初值一起聲明//arr3 := [3]int{2,4,6} 二維數組的聲明，其意義是三行五列var Block [3][5]bool// 第一種for i := 0 ; i<len(arr1); i++{fmt.Printf("%d\n",arr1[i])}// 第二種for index, value := range arr1 {fmt.Printf("索引：%d, 值：%d\n",index,value)}// 以第二種方式周遊二維數組,隻取值，也就是取出一個數組for _,v := range Block {// 再對這個數組取值for _,value := range v {fmt.Printf("%v ",value)}fmt.Printf("\n")}}
           

接下來，在終端執行：

cd array
go run main.go
           

結果如下：

其中 Go 語言官方更加提倡的是第二種以 

range

 的方式進行周遊，這樣寫會讓代碼更加優雅，而且絕對不會越界。那麼，如果我隻想要數組裡的 index 不想要 value 時怎麼 range 呢？答案其實很簡單，

i := range arr

 就可以了。如果你隻想要 value 不想要索引的時候就可以這樣寫 

_, value := range arr

, 注意這裡的下劃線不能省略。

封裝一個數組列印函數

現在咱們封裝一個用來列印數組的函數并對其進行測試，代碼如下:

func PrintArr(arr [5]int) {// 第二種for index, value := range arr {fmt.Printf("索引：%d, 值：%d\n",index,value)}}
           

我們分别将 arr1,2,3 傳入列印，先猜測一下會發生什麼結果呢？

package mainimport "fmt"func main() {// 第一種，在初始化時隻聲明數組長度，不聲明數組内容var arr1 [5]int// 第二種，知道資料很多，不想自己寫長度的時候可以用這種方式// 聲明之後由編譯器自己推算數組長度arr2 :=  [...]int{1,3,5,7,9} 第三種，聲明的時候長度和初值一起聲明arr3 := [3]int{2,4,6}PrintArr(arr1)PrintArr(arr2)PrintArr(arr3)}func PrintArr(arr [5]int) {// 第二種for index, value := range arr {fmt.Printf("索引：%d, 值：%d\n",index,value)}}
           

結果是程式在列印 arr3 時抛出了如下異常。

這個就要牽扯出一個概念了，Go 語言中數組是值類型。也就是說[3]int，和[5]int 在 go 中會認為是兩個不同的資料類型。同樣地，你在 PrintArr 中改變數組中的值也不會改變原數組的值。到了這裡你肯定覺得 go 的數組太難用了，又要資料類型統一又要長度統一才能傳遞。确實是這樣的，在 go 中我們一般不直接使用數組。而是使用我們今天的主角，切片。

Golang 切片的基本操作

一般而言，Go 語言的切片比數組更加靈活，強大而且友善。數組是按值傳遞的(即是傳遞的副本)，而切片是引用類型，傳遞切片的成本非常小，而且是不定長的。而且數組是定長的，而切片可以調整長度。建立切片的文法如下：

• _make([ ]Type, length, capacity)_
• _make([ ]Type, length)_
• _[ ]Type{}_
• _[ ]Type{value1, value2, ..., valueN}_

内置函數 

make()

 用于建立切片、映射和通道。當用于建立一個切片時，它會建立一個隐藏的初始化為零值的數組，然後傳回一個引用該隐藏數組的切片。該隐藏的數組與 Go 語言中的所有數組一樣，都是固定長度，如果使用第一種文法建立，那麼其長度為切片的容量 

capacity

 ；如果是第二種文法，那麼其長度記為切片的長度

length

 。一個切片的容量即為隐藏數組的長度，而其長度則為不超過該容量的任意值。另外可以通過内置的函數 

append()

 來增加切片的容量。我們來執行一下下面的程式：

package mainimport "fmt"func main() {slice := make([]int,0)for i := 0 ;i < 10; i++ {// 動态的對切片進行擴容slice = append(slice, i)}fmt.Println(slice)// 調用PrintArrPrintArr(slice)// 看看是否切片的第一個元素改變了?fmt.Println(slice)}func PrintArr(arr []int) {arr[0] = 100for index, value := range arr {fmt.Printf("索引：%d, 值：%d\n",index,value)}}
           

執行結果:

執行之後我們會發現 

slice[0]

 的值确實被改變了。因為切片是引用傳遞，也就是直接把切片在記憶體中的位址傳遞過去。這樣我們在其他函數中對其進行修改也會影響原來的切片的資料。這樣做的好處是傳引用因為不用把原資料拷貝一份，是以對系統的開銷比較小。

切片的切割

切片最大的特色就是可以靈活的進行切分，比如下面的例子。

package mainimport "fmt"func main() {slice := make([]int,0)for i := 0 ;i < 10; i++ {slice = append(slice, i)}fmt.Println(slice)s2 := slice[2:4]fmt.Println(s2)}
           

執行結果:

這裡的 2 可被稱為起始索引，4 可被稱為結束索引。那麼 s2 的長度就是 4 減去 2，即 2。是以可以說，s2 中的索引從 0 到 1 指向的元素對應的是 slice 及其底層數組中索引從 2 到 3 的那 2 個元素。到這裡我們就可以推出 

[n:m]

 的意思是取區間 

[n,m)

 的資料指派給新的切片。

關于數組與切片兩道常見面試題

一、Golang 切片的擴容規則。 一旦一個切片無法容納更多的元素，Go 語言就會想辦法擴容。但它并不會改變原來的切片，而是會生成一個容量更大的切片，然後将把原有的元素和新元素一并拷貝到新切片中。在一般的情況下，你可以簡單地認為新切片的容量将會是原切片容量的 2 倍。 但是，當原切片的長度大于或等于 1024 時，Go 語言将會以原容量的 1.25 倍作為新容量的基準。因為繼續再乘以 2 的話切片容量增加的太快，很容易産生大量的浪費無意義的空間。 不過，如果我們一次追加的元素過多，以至于使新長度比原容量的 2 倍還要大，那麼新容量就會以新長度為基準。比如你現在的切片長度為 10，現在一下往裡面添加了 30 個元素，那麼 Golang 會直接建立一個新的長度為 40 的底層數組，然後把所有的資料拷貝進去。 二、Golang 切片的底層數組在什麼情況下會改變？ 其實這裡的典型回答應該是永遠不會改變。因為當切片需要擴容時，新的切片誕生的同時也會建立出新的底層數組，它隻是把原數組的資料拷貝了進來，并未對其做任何的修改。

一道思考題

現在我們已經學習了如何對數組進行“擴容”，那麼你能否使用“擴容”的方式，把原切片進行縮容呢？請嘗試寫出代碼，或查閱相關資料。

程式設計實驗兩道

現在有兩個排序問題，第一道題目是假設試卷的成績隻有 0-100 的整數分布，你能否想出對試卷最速進行排序的方法呢？第二道題：對初學者不太友好，但是是各類比賽，面試中常見的一種問題。請嘗試實作快速排序，這一道題比較的困難，建議先查閱相關資料。其相關實作步驟如下。

• 從數列中随機挑出一個元素，稱為 “基準”(pivot)；
• 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面(相同的數可以到任一邊)。在這個分區退出之後，該基準就處于數列的中間位置。這個稱為分區(partition)操作；
• 遞歸地(recursive)把小于基準值元素的子數列和大于基準值元素的子數列排序。

成績排序

我們現在已知試卷的成績隻有 0-100 的整數分布，然後就能聯想到一個數組的索引也可以表示從 0-100 不間斷的分布。那麼對成績排序隻需要對每一個成績往對應的索引裡面裝就行了(比如找到一個成績為 100 的，那麼就隻需要讓

arr[100]++

)，也就是說對成績排序隻需要周遊一次成績數組就可以了。這種方法就叫做桶排序，它巧妙的利用了數組索引表示資料的方式進行排序。也是在滿足應用條件時世界上最快的排序方法。代碼如下:

package mainimport "fmt"func GradeSort(grade []int) {// 初始化出試卷範圍[0-100]arr := make([]int,101)for _,v := range grade {// 每一個成績裝到對應的桶中arr[v]++}// 把成績裝回去index := 0for i,v := range arr {// 桶空了就繼續下一個if v == 0 {continue}else {// 如果桶不為空,也就是說arr[i]不為空// 意思就是成績為 i 的人有多少個// 是以我們把這些成績裝回grade數組中去for v != 0 {v--grade[index] = iindex++}}}}func main() {grade := []int{4,66,66,67,55,55,66,99,100,4,67}GradeSort(grade)fmt.Println(grade)}
           

執行結果:

快速排序

将下面的代碼與上文中的三個步驟進行對照，嘗試自己用注釋的方式将代碼段與上述步驟一一對照的标注出來吧。

package mainimport ("fmt""math/rand""time")// 對arr[l...r]部分進行partition操作// 傳回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]func partition (arr []int,l,r int) int {// 随機在arr[l...r]的範圍中, 選擇一個數值作為标定點pivotrand.Seed(time.Now().Unix())randIndex := rand.Int()%(r-l+1)+larr[l],arr[randIndex] = arr[randIndex],arr[l]v := arr[l]j := lfor i := l+1; i<=r; i++ {if arr[i] < v {j++arr[j],arr[i] = arr[i],arr[j]}}arr[l],arr[j] = arr[j],arr[l]return j}func QuickSort(arr []int,l,r int)  {if l >= r {return}p := partition(arr,l,r)QuickSort(arr,l,p-1)QuickSort(arr,p+1,r)}func main() {var arr []intfor i:=9 ; i>=0;i--{arr = append(arr,i)}fmt.Println(arr)QuickSort(arr,0,len(arr)-1)fmt.Println(arr)}
           

執行結果：

實驗總結

在本節實驗中，我們體會到了數組的聲明，周遊，數組和切片的不同，以及幾道常考的面試題。這裡附上思維導圖以便大家記憶。

第一節課程到此結束，後面會陸續介紹：堆棧、隊列、連結清單、二叉樹、字典、圖、紅黑樹、線段樹等常見面試内容。

???點選