【根據身高重建佇列】
學習博客： https://blog.csdn.net/qq_45190523/article/details/109751831
實戰
假設有打亂順序的一群人站成一個佇列， 每個人由一個整數對 (h, k) 表示，其中 h 是這個人的身高，k 是應該排在這個人前面且身高大于或等于 h 的人數， 例如：[5,2] 表示前面應該有2 個身高大于等于 5 的人，而 [5,0] 表示前面不應該存在身高大于等于 5 的人，
撰寫一個演算法，根據每個人的身高 h 重建這個佇列，使之滿足每個整數對 (h, k) 中對人數 k 的要求
示列：
輸入：[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
輸出：[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
解題思路
首先對陣列進行排序，第一個元素從高到低，如果第一個元素相同，第二個元素從高到低排序，即高個子先站前面，低個子再根據切片第二個值來插入到正確的位置，
接著進行如下操作來將低個子插入正確位置
package main
import “fmt”
import “sort”
type S [][]int
func sortS(s S){
sort.Sort(s)
}
func (s S) Swap(i,j int) {
s[i],s[j]=s[j],s[i]
}
func (s S) Len() int{
return len(s)
}
func (s S) Less(i,j int) bool{
// 高的人先排，同樣高的k值小的在前面
return s[i][0]>s[j][0] || (s[i][0]==s[j][0] && s[i][1]<s[j][1])
}
func reconstructQueue(people [][]int) [][]int {
var res [][]int
sortS(people)//先排序
for key,value:=range people {
if value[1] < key {
// 插入index位置
index:=value[1]
// append支持兩個切片，第二個切片后面要加 …
temp:=append([][]int{},res[index:]…)
res=append(res[0:index],value)
res=append(res,temp…)
} else {
res=append(res,value) //直接插入res尾部
}
}
return res
}
func main() {
people := [][]int{{9, 0}, {7, 0}, {1, 9}, {3, 0}, {2, 7}, {5, 3}, {6, 0}, {3, 4}, {6, 2}, {5, 2}}
fmt.Println(“Hello, World!”, reconstructQueue(people))
}
著作權宣告：本文為CSDN博主「某只沉迷游戲的廢人.」的原創文章，遵循CC 4.0 BY-SA著作權協議，轉載請附上原文出處鏈接及本宣告，
原文鏈接：https://blog.csdn.net/qq_45190523/article/details/109751831
問題一、append的問題
append 一個空成員，會讓切片變化不？ （切片不能比較 == ）
把 []int{} 當做一個空切片來對待，并不是一個切片的空成員
前面append一個空切片只能產生如下變化
后面append一個空切片不產生變化
func main() {
test := []int{1, 2, 3}
fmt.Println(test, len(test), cap(test))
test = append([]int{}, test...)
fmt.Println(test, len(test), cap(test))
test = append([]int{}, test...)
fmt.Println(test, len(test), cap(test))
test1 := []int{1, 2, 3, 4}
fmt.Println(test, len(test1), cap(test1))
test1 = append([]int{}, test1...)
fmt.Println(test1, len(test1), cap(test1))
}
[1 2 3] 3 3
[1 2 3] 3 4
[1 2 3] 3 4
[1 2 3 4] 4 4
[1 2 3 4] 4 4
func main() {
test := []int{1, 2, 3}
fmt.Println(test, len(test), cap(test))
test = append(test, []int{}...)
fmt.Println(test, len(test), cap(test))
}
[1 2 3] 3 3
[1 2 3] 3 3
問題二、二維切片的問題
初始化：
res := make([][length]int, length)
例如：
res := make([][2]int, 10)
fmt.Println(res)
輸出：
[[0 0] [0 0] [0 0] [0 0] [0 0] [0 0] [0 0] [0 0] [0 0] [0 0]]
或者
a := [][]float64{
{1, 2, 3, 4},
{12, 21, 3, 14},
{1, 1, 2, 3},
{2, 3, 1, 6},
{2, 2, 3, 3},
{1, 1, 1, 1}}
問題三、排序
func main() {
people := [][]int{{9, 0}, {7, 0}, {1, 9}, {3, 0}, {2, 7}, {5, 3}, {6, 0}, {3, 4}, {6, 2}, {5, 2}}
less := func(i, j int) bool {
if people[i][0] == people[j][0] {
return people[i][1] >= people[j][1]
}
return people[i][0] > people[j][0]
}
greater := func(i, j int) bool {
if people[i][0] == people[j][0] {
return people[i][1] <= people[j][1]
}
return people[i][0] < people[j][0]
}
sort.Slice(people, less)
fmt.Println(people)
sort.Slice(people, greater)
fmt.Println(people)
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/335312.html
標籤：其他
上一篇：【Visual c++】+【EasyX】游戲組件1 移動的小人
下一篇：外星人入侵(二.外星人來了)