🧩 LeetCode Hardを極める：複雑な7つの解法を徹底解説 🔗

import "fmt"

func getPermutation(n int, k int) string {
	factorial := 1
	digits := []int{}

	// Calculate factorials and populate the digits slice
	for i := 1; i <= n; i++ {
		factorial *= i
		digits = append(digits, i)
	}

	return solvePermutation(n-1, k-1, factorial/n, digits)
}

func solvePermutation(n, k, factorial int, digits []int) string {
	// Find which block of permutations 'k' falls into
	index := k / factorial
	res := fmt.Sprintf("%d", digits[index])

	if n <= 0 {
		return res
	}

	// Update k for the next level: k % factorial
	// Update factorial for the next level: factorial / n
	// Remove the selected digit from the slice
	nextK := k % factorial
	nextFactorial := factorial / n
	remainingDigits := append(digits[:index], digits[index+1:]...)

	res += solvePermutation(n-1, nextK, nextFactorial, remainingDigits)
	return res
}

func isMatch(s string, p string) bool {
	sn, pn := len(s), len(p)
	memo := make([][]int, sn+1)
	for i := range memo {
		memo[i] = make([]int, pn+1)
	}
	return solveRegex(s, p, sn, pn, 0, 0, memo)
}

func solveRegex(s, p string, sn, pn, si, pi int, memo [][]int) bool {
	if memo[si][pi] == 1 { return false }
	if memo[si][pi] == 2 { return true }

	res := false
	if si == sn && pi == pn {
		res = true
	} else if pi+1 < pn && p[pi+1] == '*' {
		// Option A: Zero occurrences
		if solveRegex(s, p, sn, pn, si, pi+2, memo) {
			res = true
		// Option B: One or more occurrences (if current char matches)
		} else if si < sn && (p[pi] == '.' || p[pi] == s[si]) && solveRegex(s, p, sn, pn, si+1, pi, memo) {
			res = true
		}
	} else if si < sn && pi < pn && (p[pi] == '.' || p[pi] == s[si]) {
		// Normal character match
		res = solveRegex(s, p, sn, pn, si+1, pi+1, memo)
	}

	if res {
		memo[si][pi] = 2
	} else {
		memo[si][pi] = 1
	}
	return res
}

import "math"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func maxPathSum(root *TreeNode) int {
	fromRoot, other := solveTree(root)
	if fromRoot > other {
		return fromRoot
	}
	return other
}

func solveTree(root *TreeNode) (int, int) {
	if root == nil {
		return math.MinInt, math.MinInt
	}

	left, otherLeft := solveTree(root.Left)
	right, otherRight := solveTree(root.Right)

	// Extendable path (can only pick one branch or stop at node)
	currentFromRoot := max([]int{
		root.Val,
		sum([]int{root.Val, left}),
		sum([]int{root.Val, right}),
	})

	// Closed path (can arch over the current node, or be completely inside a child)
	currentOther := max([]int{
		left, right, otherLeft, otherRight,
		sum([]int{root.Val, left, right}),
	})

	return currentFromRoot, currentOther
}

func max(s []int) int {
	res := math.MinInt
	for _, v := range s {
		if v > res { res = v }
	}
	return res
}

func sum(s []int) int {
	res := 0
	for _, v := range s {
		if v == math.MinInt { return math.MinInt }
		res += v
	}
	return res
}

func solveSudoku(board [][]byte) {
	var rows, cols [9][9]bool
	var boxes [3][3][9]bool

	// Populate initial state
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if board[i][j] != '.' {
				idx := board[i][j] - '1'
				rows[i][idx], cols[j][idx], boxes[i/3][j/3][idx] = true, true, true
			}
		}
	}
	backtrackSudoku(board, &rows, &cols, &boxes)
}

func backtrackSudoku(board [][]byte, rows, cols *[9][9]bool, boxes *[3][3][9]bool) bool {
	bestI, bestJ := -1, -1
	minOptions := 10 // Start higher than the max possible options (9)

	// Heuristic: Find the cell with the fewest valid options
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if board[i][j] == '.' {
				options := 0
				for val := 0; val < 9; val++ {
					if !rows[i][val] && !cols[j][val] && !boxes[i/3][j/3][val] {
						options++
					}
				}
				if options < minOptions {
					minOptions = options
					bestI, bestJ = i, j
				}
			}
		}
	}

	// Base case: No empty cells left
	if bestI == -1 { return true }

	// Try placing valid numbers in the chosen optimal cell
	for val := 0; val < 9; val++ {
		if !rows[bestI][val] && !cols[bestJ][val] && !boxes[bestI/3][bestJ/3][val] {
			board[bestI][bestJ] = byte(val + '1')
			rows[bestI][val], cols[bestJ][val], boxes[bestI/3][bestJ/3][val] = true, true, true

			if backtrackSudoku(board, rows, cols, boxes) {
				return true
			}

			// Backtrack
			board[bestI][bestJ] = '.'
			rows[bestI][val], cols[bestJ][val], boxes[bestI/3][bestJ/3][val] = false, false, false
		}
	}
	return false
}

func minNumberOfSemesters(n int, relations [][]int, k int) int {
	// prerequisites[i] is a bitmask of courses that must be taken before course i
	prerequisites := make([]int, n)
	for _, relation := range relations {
		prevCourse := relation[0] - 1
		nextCourse := relation[1] - 1
		prerequisites[nextCourse] |= 1 << prevCourse
	}

	// states and costs act as a BFS queue
	states := []int{0}
	costs := []int{0}
	added := map[int]bool{0: true}

	for cur := 0; ; cur++ {
		state := states[cur]
		cost := costs[cur]

		// Base case: All courses have been taken
		if state == (1<<n)-1 {
			return cost
		}

		// Find all courses available to take this semester
		courses := []int{}
		next := state
		for course := 0; course < n; course++ {
			bit := 1 << course
			if (state&bit) == 0 && (prerequisites[course]|state) == state {
				courses = append(courses, course)
				next |= bit
			}
		}

		add := func(next int) {
			if added[next] {
				return
			}
			added[next] = true
			states = append(states, next)
			costs = append(costs, cost+1)
		}

		// If we can take all available courses in one semester, do so
		if len(courses) <= k {
			add(next)
			continue
		}

		// Otherwise, explore all combinations of size k
		var addStates func(next, k, from int)
		addStates = func(next, k, from int) {
			if k == 0 {
				add(next)
				return
			}
			for i := from; i < len(courses); i++ {
				addStates(next|(1<<courses[i]), k-1, i+1)
			}
		}
		addStates(state, k, 0)
	}
}

import "math"

func maxSumSubmatrix(matrix [][]int, k int) int {
	n := len(matrix)
	m := len(matrix[0])
	res := math.MinInt
	sums := make([][]int, n)
	for i := 0; i < n; i++ {
		sums[i] = make([]int, m)
	}

	// Precompute 2D prefix sums
	sums[0][0] = matrix[0][0]
	for i := 1; i < n; i++ {
		sums[i][0] = matrix[i][0] + sums[i-1][0]
	}
	for j := 1; j < m; j++ {
		sums[0][j] = matrix[0][j] + sums[0][j-1]
	}
	for i := 1; i < n; i++ {
		for j := 1; j < m; j++ {
			sums[i][j] = matrix[i][j] + sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1]
		}
	}

	// Evaluate all possible subrectangles using inclusion-exclusion
	for starti := 0; starti < n; starti++ {
		for startj := 0; startj < m; startj++ {
			for endi := starti; endi < n; endi++ {
				for endj := startj; endj < m; endj++ {
					sum := sums[endi][endj]
					if starti > 0 {
						sum -= sums[starti-1][endj]
					}
					if startj > 0 {
						sum -= sums[endi][startj-1]
					}
					if starti > 0 && startj > 0 {
						sum += sums[starti-1][startj-1]
					}
					if sum <= k && sum > res {
						res = sum
					}
				}
			}
		}
	}
	return res
}

func findRedundantDirectedConnection(edges [][]int) []int {
	n := len(edges)
	parents := map[int][]int{}
	outs := map[int][]int{}
	for _, edge := range edges {
		src := edge[0] - 1
		dst := edge[1] - 1
		parents[dst] = append(parents[dst], src)
		outs[src] = append(outs[src], dst)
	}

	roots := map[int]bool{}
	bad := -1
	for i := 0; i < n; i++ {
		if len(parents[i]) == 0 {
			roots[i] = true
		}
		if len(parents[i]) > 1 {
			bad = i
		}
	}

	if len(roots) == 0 {
		for i := 0; i < n; i++ {
			if check(n, outs, i, -1, -1, map[int]bool{}) {
				roots[i] = true
			}
		}
	}

	if len(roots) > 1 {
		for i := len(edges) - 1; i >= 0; i-- {
			edge := edges[i]
			src := edge[0] - 1
			dst := edge[1] - 1
			if roots[dst] {
				return []int{src + 1, dst + 1}
			}
		}
	}

	for root := range roots {
		if len(parents[root]) > 0 {
			return []int{parents[root][0] + 1, root + 1}
		}
		for from := len(parents[bad]) - 1; from >= 0; from-- {
			if check(n, outs, root, parents[bad][from], bad, map[int]bool{}) {
				return []int{parents[bad][from] + 1, bad + 1}
			}
		}
	}
	return []int{-1, -1}
}

func check(n int, outs map[int][]int, from, badfrom, badto int, visited map[int]bool) bool {
	if visited[from] {
		return false
	}
	visited[from] = true
	if len(visited) == n {
		return true
	}
	for _, to := range outs[from] {
		if from == badfrom && to == badto {
			continue
		}
		if check(n, outs, to, badfrom, badto, visited) {
			return true
		}
	}
	return false
}