LeetCode Weekly Contest 450

package main

import (
	"fmt"
)

func sumOfDigits(num int) int {
	sum := 0
	for num > 0 {
		sum += num % 10
		num /= 10
	}
	return sum
}

func smallestIndex(nums []int) int {
	for i, num := range nums {
		if sumOfDigits(num) == i {
			return i
		}
	}
	return -1
}

func main() {
	fmt.Println(smallestIndex([]int{1, 3, 2}))   // 2
	fmt.Println(smallestIndex([]int{1, 10, 11})) // 1
	fmt.Println(smallestIndex([]int{1, 2, 3}))   // -1
}

package main

import (
	"fmt"
	"sort"
)

func sumOfDigits(num int) int {
	sum := 0
	for num > 0 {
		sum += num % 10
		num /= 10
	}
	return sum
}

func minSwaps(nums []int) int {
	numsLen := len(nums)

	type Pair struct {
		value    int
		index    int // original index
		digitSum int // sum of digits
	}

	original := make([]Pair, numsLen)
	for i := 0; i < numsLen; i++ {
		original[i] = Pair{
			value:    nums[i],
			index:    i,
			digitSum: sumOfDigits(nums[i]),
		}
	}

	sorted := make([]Pair, numsLen)
	copy(sorted, original)

	// 排序目标数组：按 digit sum 升序，若相等按值升序
	sort.Slice(sorted, func(i, j int) bool {
		if sorted[i].digitSum < sorted[j].digitSum {
			return true
		} else if sorted[i].digitSum > sorted[j].digitSum {
			return false
		} else {
			return sorted[i].value < sorted[j].value
		}
	})

	// 构建原 index 到目标 index 的映射
	pos := make([]int, numsLen) // pos[i] 表示原始位置 i 的元素要去的位置
	isAllSame := true           // fast path 如果排序前后下标均相同，那么直接返回 0
	for i := 0; i < numsLen; i++ {
		pos[sorted[i].index] = i
		if isAllSame && sorted[i].index != i {
			isAllSame = false
		}
	}

	if isAllSame {
		return 0
	}

	// 计算最小交换次数（利用置换环）
	visited := make([]bool, numsLen)
	swaps := 0

	for i := 0; i < numsLen; i++ {
		if visited[i] || pos[i] == i {
			continue
		}
		// 找一个环
		cycleLen := 0
		j := i
		for !visited[j] {
			visited[j] = true
			j = pos[j]
			cycleLen++
		}
		if cycleLen > 0 {
			swaps += cycleLen - 1
		}
	}

	return swaps
}

func main() {
	fmt.Println(minSwaps([]int{37, 100}))        // 1
	fmt.Println(minSwaps([]int{22, 14, 33, 7}))  // 0
	fmt.Println(minSwaps([]int{18, 43, 34, 16})) // 2
}

package main

import (
	"container/list"
	"fmt"
)

type Position struct {
	row int
	col int
}

func isPortal(ch byte) bool {
	return ch >= 'A' && ch <= 'Z'
}

func isObstacle(ch byte) bool {
	return ch == '#'
}
func isEmptyCell(ch byte) bool {
	return ch == '.'
}

func minMoves(matrix []string) int {
	rows, cols := len(matrix), len(matrix[0])

	grid := make([][]byte, rows)
	for i := range matrix {
		grid[i] = []byte(matrix[i])
	}

	portals := make(map[byte][]Position)
	// 取出所有的传送门
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			ch := grid[r][c]
			if isPortal(ch) {
				portals[ch] = append(portals[ch], Position{r, c})
			}
		}
	}

	usedPortals := make(map[byte]bool)

	queue := list.New()
	start := grid[0][0]

	// 处理起始位置，初始化 BFS
	if isObstacle(start) {
		return -1
	} else if isEmptyCell(start) {
		queue.PushBack(Position{0, 0})
		grid[0][0] = '#'
	} else if isPortal(start) {
		for _, p := range portals[start] {
			queue.PushBack(p)
			grid[p.row][p.col] = '#'
		}
		usedPortals[start] = true
	} else {
		panic("Invalid chars")
	}

	steps := 0

	// BFS
	for queue.Len() > 0 {
		for i := queue.Len(); i > 0; i-- {
			curr := queue.Remove(queue.Front()).(Position)

			if curr.row == rows-1 && curr.col == cols-1 {
				return steps
			}

			// 尝试四方向移动
			for _, d := range [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}} {
				nextRow, newCol := curr.row+d[0], curr.col+d[1]
				// 越界?
				if nextRow >= 0 && nextRow < rows && newCol >= 0 && newCol < cols {
					ch := grid[nextRow][newCol]
					switch {
					case isEmptyCell(ch):
						queue.PushBack(Position{nextRow, newCol})
						grid[nextRow][newCol] = '#'
					case isPortal(ch) && !usedPortals[ch]:
						for _, p := range portals[ch] {
							queue.PushBack(p)
							grid[p.row][p.col] = '#'
						}
						usedPortals[ch] = true
					}
				}
			}
		}
		steps++
	}

	return -1
}

func main() {
	fmt.Println(minMoves([]string{"A..", ".A.", "..."}))                // Output: 2
	fmt.Println(minMoves([]string{".#...", ".#.#.", ".#.#.", "...#."})) // Output: 13
	fmt.Println(minMoves([]string{".A", "CA"}))                         // Output: 1
}

package main

import (
	"fmt"
)

type Edge struct {
	dest   int
	weight int
}

var (
	LOG int

	tree  [][]Edge // 邻接表
	depth []int    // 每个节点的深度
	dist  []int    // 每个节点到根的距离

	// parent[u][k] 表示：从节点 u 往上跳 2^k 步后的祖先节点。
	// 举例来说：
	//     parent[u][0] 是 u 的直接父亲。
	//     parent[u][1] 是 u 的祖父（跳两步）。
	//     parent[u][2] 是 u 的曾祖父（跳四步）。
	parent [][]int
)

func dfs(u, p, d, w int) {
	depth[u] = d
	parent[u][0] = p
	dist[u] = w
	for _, e := range tree[u] {
		if e.dest != p {
			dfs(e.dest, u, d+1, w+e.weight)
		}
	}
}

func initLCA(n int) {
	for k := 1; k < LOG; k++ {
		for u := 0; u < n; u++ {
			if parent[u][k-1] != -1 {
				parent[u][k] = parent[parent[u][k-1]][k-1]
			} else {
				parent[u][k] = -1
			}
		}
	}
}

func lca(u, v int) int {
	if depth[u] < depth[v] {
		u, v = v, u
	}
	// 把u提升到和v同一深度
	for i := LOG - 1; i >= 0; i-- {
		if parent[u][i] != -1 && depth[parent[u][i]] >= depth[v] {
			u = parent[u][i]
		}
	}
	if u == v {
		return u
	}
	// 同步提升u,v
	for i := LOG - 1; i >= 0; i-- {
		if parent[u][i] != -1 && parent[u][i] != parent[v][i] {
			u = parent[u][i]
			v = parent[v][i]
		}
	}
	return parent[u][0]
}

func minimumWeight(edges [][]int, queries [][]int) []int {
	n := len(edges) + 1
	LOG = 1 // 倍增法中需要的最大层数
	for (1 << LOG) <= n {
		LOG++
	}

	tree = make([][]Edge, n)
	for _, e := range edges {
		src, dest, weight := e[0], e[1], e[2]
		// 无向树
		tree[src] = append(tree[src], Edge{dest, weight})
		tree[dest] = append(tree[dest], Edge{src, weight})
	}

	depth = make([]int, n)
	dist = make([]int, n)

	parent = make([][]int, n)
	for i := range parent {
		parent[i] = make([]int, LOG)
		for j := range parent[i] {
			parent[i][j] = -1
		}
	}

	dfs(0, -1, 0, 0)
	initLCA(n)

	result := make([]int, len(queries))
	for i, q := range queries {
		src1, src2, dest := q[0], q[1], q[2]
		lca1 := lca(src1, src2)
		lca2 := lca(src2, dest)
		lca3 := lca(dest, src1)
		// 三点子树权重和
		result[i] = dist[src1] + dist[src2] + dist[dest] - dist[lca1] - dist[lca2] - dist[lca3]
	}
	return result
}

func main() {
	edges := [][]int{{0, 1, 2}, {1, 2, 3}, {1, 3, 5}, {1, 4, 4}, {2, 5, 6}}
	queries := [][]int{{2, 3, 4}, {0, 2, 5}}
	fmt.Println(minimumWeight(edges, queries)) // [12 11]

	edges2 := [][]int{{1, 0, 8}, {0, 2, 7}}
	queries2 := [][]int{{0, 1, 2}}
	fmt.Println(minimumWeight(edges2, queries2)) // [15]
}

package main

func minSwaps(source, target []int) int {
	n := len(source)
	if n != len(target) {
		panic("")
	}

	posInSource := make(map[int]int, n)
	for i, val := range source {
		posInSource[val] = i
	}

	pos := make([]int, n)
	for i := 0; i < n; i++ {
		pos[i] = posInSource[target[i]]
	}

	visited := make([]bool, n)
	swaps := 0
	for i := 0; i < n; i++ {
		if visited[i] || pos[i] == i {
			continue
		}
		cycleLen := 0
		j := i
		for !visited[j] {
			visited[j] = true
			j = pos[j]
			cycleLen++
		}
		swaps += cycleLen - 1
	}

	return swaps
}

func main() {
	a := []int{0, 1, 2}
	// a := []int{1, 0, 2}
	// a := []int{2, 0, 1}
	b := []int{2, 0, 1}
	println(minSwaps(a, b)) // Output: 2

	a = []int{3, 5, 4, 1, 2, 0}
	// a = []int{1, 5, 4, 3, 2, 0}
	// a = []int{5, 1, 4, 3, 2, 0}
	// a = []int{0, 1, 4, 3, 2, 5}
	// a = []int{0, 1, 2, 3, 4, 5}
	b = []int{0, 1, 2, 3, 4, 5}
	println(minSwaps(a, b)) // Output: 4

	a = []int{0}
	b = []int{0}
	println(minSwaps(a, b)) // Output: 0
}