go编程学习

LC周赛中有些题目涉及到自定义pair类型和自定义排序的用法，因此记录下

LC6351. 标记所有元素后数组的分数

// nums = [2,1,3,4,5,2]
func findScore(nums []int) (ans int64) {
	a := make([]pair, len(nums))
	for i, x := range nums {
		a[i] = pair{x, i + 1} // [{2 1} {1 2} {3 3} {4 4} {5 5} {2 6}]
	}
  
// 自定义排序
	sort.Slice(a, func(i, j int) bool {
		x, y := a[i], a[j]
		return x.v < y.v || x.v == y.v && x.i < y.i
	}) // [{1 2} {2 1} {2 6} {3 3} {4 4} {5 5}]

	vis := make([]bool, len(nums)+2)
	for _, p := range a {
		if !vis[p.i] { // 下标没被访问
			vis[p.i-1] = true
			vis[p.i+1] = true
			ans += int64(p.v)
		}
	}
	return
}

LC周赛2596. 检查骑士巡视方案

https://leetcode.cn/problems/check-knight-tour-configuration/description/

pair用法

func main() {
	checkValidGrid([][]int{{0, 3, 6}, {5, 8, 1}, {2, 7, 4}})
}

type pair struct {
	i, j int
}
func checkValidGrid(grid [][]int) bool {
	n := len(grid)
	m := make([]pair, n*n)
	for i, row := range grid {
		for j, x := range row {
			m[x] = pair{i, j}
		}
	}
	if m[0] != (pair{0, 0}) { // 必须从左上角出发
		return false
	}
	
	for i := 1; i < len(m); i++ {
		x := abs(m[i].i - m[i-1].i)
		y := abs(m[i].j - m[i-1].j)
		if !((x == 1 && y == 2) || x == 2 && y == 1) {
			return false
		}
	}
	return true
}

func abs(i int) int {
	if i < 0 {
		return -i
	}
	return i
}

根据二维数组的差值，从小到大排序

建立一个pair类型的数组a，把二维数组每个元素以kv形式存进去，并排序

1029.两地调度

6364.老鼠和奶酪

func main() {
	twoCitySchedCost([][]int{{10, 20}, {30, 200}, {400, 50}, {30, 20}})
}

type pair struct {
	x, y int
}

func twoCitySchedCost(costs [][]int) (ans int) {
	a := make([]pair, len(costs))
	for i, x := range costs {
		a[i] = pair{x[0], x[1]}
	}

	sort.Slice(a, func(i, j int) bool {
		arr1, arr2 := a[i], a[j]
		return arr1.x-arr1.y < arr2.x-arr2.y
	})
	//[[30 200] [10 20] [30 20] [400 50]]

	n := len(costs) / 2
	for _, p := range a[:n] {
		ans += p.x
	}
	for _, p := range a[n:] {
		ans += p.y
	}

	return
}

FEATURED TAGS

FRIENDS