Hoot100

package one

func twoSum(nums []int, target int) []int {
	m := map[int]int{} // 元素：下标

	for i := 0; i < len(nums); i++ {
		other := target - nums[i]
		if index, ok := m[other]; ok {
			return []int{i, index}
		}
		m[nums[i]] = i
	}

	return nil
}

package two

type ListNode struct {
	Val  int
	Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	dummy := &ListNode{}
	cur := dummy
	carry := 0 // 进位

	for l1 != nil || l2 != nil {
		v1, v2 := 0, 0
		if l1 != nil {
			v1 = l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			v2 = l2.Val
			l2 = l2.Next
		}

		sum := (v1 + v2 + carry) % 10
		carry = (v1 + v2 + carry) / 10

		newNode := &ListNode{Val: sum}
		cur.Next = newNode
		cur = cur.Next
	}

	if carry > 0 {
		newNode := &ListNode{Val: carry}
		cur.Next = newNode
	}

	return dummy.Next
}

package three

func lengthOfLongestSubstring(s string) int {
	if len(s) == 0 {
		return 0
	}

	temp := map[byte]int{}
	left, right := 0, 0
	res := 0

	for ; right < len(s); right++ {
		temp[s[right]]++

		for temp[s[right]] > 1 {
			temp[s[left]]--
			left++
		}

		res = max(res, right-left+1)
	}

	return res
}

package oneone

func maxArea(height []int) int {
	res := 0
	left, right := 0, len(height)-1

	for left <= right {
		area := (right - left) * min(height[left], height[right])
		res = max(res, area)

		if height[left] < height[right] {
			left++
		} else {
			right--
		}
	}

	return res
}

package onefive

import "sort"

func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	res := [][]int{}

	for i := 0; i < len(nums)-2; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}

		// 两数之和（有序）
		v1 := nums[i]
		left, right := i+1, len(nums)-1

		for left < right {
			sum := v1 + nums[left] + nums[right]
			if sum == 0 {
				res = append(res, []int{v1, nums[left], nums[right]})
				// 这里需要内部去重
				left++
				right--
				for left < right && nums[left] == nums[left-1] {
					left++
				}
				for left < right && nums[right] == nums[right+1] {
					right--
				}
			} else if sum > 0 {
				right--
			} else {
				left++
			}
		}
	}

	return res
}

package onenine

type ListNode struct {
	Val  int
	Next *ListNode
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	if head == nil || head.Next == nil {
		return nil
	}

	// 快慢指针，快指针先走n步
	fast, slow := head, head
	for n > 0 {
		fast = fast.Next
		n--
	}

	// 是否要删除头节点
	if fast == nil {
		return head.Next
	}

	// 再同时走
	for fast.Next != nil {
		fast = fast.Next
		slow = slow.Next
	}

	// slow的下一个节点就是要删除的节点
	slow.Next = slow.Next.Next

	return head
}

package twozero

func isValid(s string) bool {
	if len(s)%2 == 1 {
		return false
	}

	m := map[rune]rune{
		')': '(',
		']': '[',
		'}': '{',
	}
	stack := []rune{}

	for _, v := range s {
		if other, ok := m[v]; ok {
			if len(stack) > 0 && stack[len(stack)-1] == other {
				stack = stack[:len(stack)-1]
			} else {
				return false
			}
		} else {
			stack = append(stack, v)
		}
	}

	if len(stack) > 0 {
		return false
	}
	return true
}

package twoone

type ListNode struct {
	Val  int
	Next *ListNode
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	}
	if list2 == nil {
		return list1
	}

	// 递归
	if list1.Val < list2.Val {
		list1.Next = mergeTwoLists(list1.Next, list2)
		return list1
	} else {
		list2.Next = mergeTwoLists(list1, list2.Next)
		return list2
	}
}

package twothree

type ListNode struct {
	Val  int
	Next *ListNode
}

// // 递归合并
// func mergeKLists(lists []*ListNode) *ListNode {
// 	if len(lists) == 0 {
// 		return nil
// 	}

// 	return mergeTwoLists(lists[0], mergeKLists(lists[1:]))
// }

// 两两迭代合并
func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	}

	for len(lists) > 1 {
		temp := []*ListNode{}

		for i := 0; i < len(lists); i += 2 {
			var l1, l2 *ListNode
			l1 = lists[i]
			if i+1 < len(lists) {
				l2 = lists[i+1]
			}
			temp = append(temp, mergeTwoLists(l1, l2))
		}

		lists = temp
	}

	return lists[0]
}

// 合并两个有序链表
func mergeTwoLists(l1, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}

	if l1.Val < l2.Val {
		l1.Next = mergeTwoLists(l1.Next, l2)
		return l1
	} else {
		l2.Next = mergeTwoLists(l1, l2.Next)
		return l2
	}
}

package twofour

type ListNode struct {
	Val  int
	Next *ListNode
}

func swapPairs(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	// 递归
	newHead := head.Next
	head.Next = swapPairs(newHead.Next)
	newHead.Next = head

	return newHead
}

package twofive

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseKGroup(head *ListNode, k int) *ListNode {
	// 递归

	// 终止条件：不足 k 个
	cur := head
	for i := 0; i < k; i++ {
		if cur == nil {
			return head
		}
		cur = cur.Next
	}
	// 此时 cur 已经指向了第 k+1 个节点

	// 反转前 k 个节点：[head, cur)
	newHead := reverse(head, cur)

	// 反转后 head 已经变成了尾节点，连接后续节点
	head.Next = reverseKGroup(cur, k)
	
	return newHead
}

func reverse(head, tail *ListNode) *ListNode {
	if head.Next == tail {
		return head // 不能超出区间
	}

	newHead := reverse(head.Next, tail)
	head.Next.Next = head
	head.Next = nil

	return newHead
}

package threeone

func nextPermutation(nums []int) {
	// 从后遍历比大小（回溯思路）
	i := 0
	for i = len(nums) - 1; i >= 0; i-- {
		if i+1 < len(nums) && nums[i+1] > nums[i] {
			for j := len(nums) - 1; j > i; j-- {
				if nums[j] > nums[i] {
					nums[i], nums[j] = nums[j], nums[i]
					break
				}
			}
			break
		}
	}

	// 翻转候选集合
	left, right := i+1, len(nums)-1
	for left < right {
		nums[left], nums[right] = nums[right], nums[left]
		left++
		right--
	}
}

package threethree

func search(nums []int, target int) int {
	maxIndex := 0
	for i := 1; i < len(nums); i++ {
		if nums[i] < nums[i-1] {
			break
		} else {
			maxIndex = i
		}
	}

	res := -1
	if target < nums[0] {
		res = twoSearch(nums, target, maxIndex+1, len(nums)-1)
	} else {
		res = twoSearch(nums, target, 0, maxIndex)
	}
	return res
}

// 区间二分
func twoSearch(nums []int, target, left, right int) int {
	for left <= right {
		mid := (right-left)/2 + left
		if nums[mid] == target {
			return mid
		} else if nums[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return -1
}

package threefour

func searchRange(nums []int, target int) []int {
	n := len(nums)
	if n == 0 {
		return []int{-1, -1}
	}

	left, right := 0, n-1

	for left <= right {
		mid := (right-left)/2 + left
		if nums[mid] >= target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	// 此时 left 是第一个 target 下标
	if left == n || nums[left] != target {
		return []int{-1, -1}
	}

	for right = left; right < n && nums[right] == target; right++ {
	}

	return []int{left, right - 1}
}

package threefive

func searchInsert(nums []int, target int) int {
	left, right := 0, len(nums)-1

	for left <= right {
		mid := (right-left)/2 + left
		if nums[mid] == target {
			return mid
		} else if nums[mid] > target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}

	return left
}

package fourone

func firstMissingPositive(nums []int) int {
	n := len(nums)
	// 正整数：1...n
	// 让数字放在正确的位置上：nums[i] == i+1

	for i := 0; i < n; i++ {
		if nums[i] == i+1 { // 已经在正确位置
			continue
		}
		if nums[i] <= 0 || nums[i] > n { // 不在范围内
			continue
		}
		if nums[i] == nums[nums[i]-1] { // 重复的数字
			continue
		}

		nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
		i-- // 交换后还要继续检查当前索引
	}

	for i := 0; i < n; i++ {
		if nums[i] != i+1 {
			return i + 1
		}
	}

	return n + 1
}

package fourtwo

func trap(height []int) int {
	if len(height) == 0 {
		return 0
	}

	left, right := 0, len(height)-1           // 双指针
	maxL, maxR := height[left], height[right] // 两个边界
	sum := 0

	for left < right {
		if maxL < maxR {
			left++
			if maxL-height[left] > 0 {
				sum += maxL - height[left]
			}
			maxL = max(maxL, height[left])
		} else {
			right--
			if maxR-height[right] > 0 {
				sum += maxR - height[right]
			}
			maxR = max(maxR, height[right])
		}
	}

	return sum
}

package fourfive

func jump(nums []int) int {
	n := len(nums)

	// 反向
	position := n - 1
	step := 0

	for position > 0 {
		for i := 0; i < position; i++ {
			if i+nums[i] >= position {
				position = i
				step++
				break
			}
		}
	}

	return step
}

package foursix

func permute(nums []int) [][]int {
	res := [][]int{}                // 结果
	temp := []int{}                 // 路径
	used := make([]bool, len(nums)) // nums 中使用过的

	dfs(nums, &res, temp, used)
	return res
}

func dfs(nums []int, res *[][]int, temp []int, used []bool) {
	if len(temp) == len(nums) {
		copyTemp := make([]int, len(temp))
		copy(copyTemp, temp)
		*res = append(*res, copyTemp)
	}

	for i := 0; i < len(nums); i++ {
		if used[i] {
			continue
		}

		temp = append(temp, nums[i])
		used[i] = true
		dfs(nums, res, temp, used)
		temp = temp[:len(temp)-1]
		used[i] = false
	}
}

package foureight

func rotate(matrix [][]int) {
	row := len(matrix)

	// 1. 上下翻转
    for i := 0; i < row/2; i++ {
        matrix[i], matrix[row-1-i] = matrix[row-1-i], matrix[i]
    }

    // 2. 主对角线翻转
    for i := 0; i < row; i++ {
        for j := 0; j < i; j++ {
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        }
    }
}

package fournine

func groupAnagrams(strs []string) [][]string {
	temp := map[[26]int][]string{}
	res := [][]string{}

	for _, v := range strs {
		temp[getCount(v)] = append(temp[getCount(v)], v)
	}
	for _, v := range temp {
		res = append(res, v)
	}

	return res
}

func getCount(s string) [26]int {
	res := [26]int{}
	for _, v := range s {
		res[v-'a']++
	}
	return res
}

package fivethree

func maxSubArray(nums []int) int {
	// 可以dp，但这里只用到一个状态，所以直接用一个变量记录当前状态就行了
	curSum := nums[0] // 以当前元素结尾的最大子数组和，初始值为nums[0]，因为如果nums全是负数，那么结果就是最大的那个负数
	res := curSum

	for i := 1; i < len(nums); i++ {
		if curSum < 0 { // 直接舍弃之前的
			curSum = nums[i]
		} else {
			curSum += nums[i]
		}
		res = max(res, curSum)
	}

	return res
}

package fivefour

func spiralOrder(matrix [][]int) []int {
	row := len(matrix)
	col := len(matrix[0])

	res := make([]int, 0, row*col)

	// 四个边界
	top, bottom := 0, row-1
	left, right := 0, col-1

	for top <= bottom && left <= right {
		// 上
		for j := left; j <= right; j++ {
			res = append(res, matrix[top][j])
		}
		top++
		if top > bottom || left > right {
			break
		}

		// 右
		for j := top; j <= bottom; j++ {
			res = append(res, matrix[j][right])
		}
		right--
		if top > bottom || left > right {
			break
		}

		// 下
		for j := right; j >= left; j-- {
			res = append(res, matrix[bottom][j])
		}
		bottom--
		if top > bottom || left > right {
			break
		}

		// 左
		for j := bottom; j >= top; j-- {
			res = append(res, matrix[j][left])
		}
		left++
	}

	return res
}

package fivefive

func canJump(nums []int) bool {
	n := len(nums)
	maxPosition := 0

	for i, v := range nums {
		if i <= maxPosition {
			maxPosition = max(maxPosition, i+v)
			if maxPosition >= n-1 { // 注意是下标的比较
				return true
			}
		}
	}

	return false
}

package fivesix

import "slices"

func merge(intervals [][]int) [][]int {
	// 按左端点排序
	slices.SortFunc(intervals, func(p, q []int) int { return p[0] - q[0] })

	res := [][]int{}
	left, right := intervals[0][0], intervals[0][1]

	for i := 1; i < len(intervals); i++ {
		if right >= intervals[i][0] { // 重叠
			right = max(right, intervals[i][1])
		} else {
			res = append(res, []int{left, right})
			left, right = intervals[i][0], intervals[i][1]
		}
	}

	res = append(res, []int{left, right}) // 加上最后一个

	return res
}

package sevenzero

func climbStairs(n int) int {
	if n <= 1 {
		return n
	}

	one, two := 1, 1
	res := 0
	for i := 2; i <= n; i++ {
		res = one + two
		one = two
		two = res
	}
	return res
}

package seventhree

// 空间O(1)版
func setZeroes(matrix [][]int) {
	// 使用矩阵的第一行和第一列来标记，[0][0]避免复用，所以加一个变量
	row := len(matrix)
	col := len(matrix[0])

	firstCol := 1 // 第一列第一个

	for i := 0; i < row; i++ {
		for j := 0; j < col; j++ {
			if matrix[i][j] == 0 {
				// 清晰区分第一行和第一列
				if i == 0 {
					matrix[0][0] = 0
				}
				if j == 0 {
					firstCol = 0
				}
				if i != 0 && j != 0 {
					matrix[i][0] = 0
					matrix[0][j] = 0
				}
			}
		}
	}

	for i := 1; i < row; i++ {
		for j := 1; j < col; j++ {
			if matrix[0][j] == 0 || matrix[i][0] == 0 {
				matrix[i][j] = 0
			}
		}
	}

	// 最后处理第一行和第一列
	if matrix[0][0] == 0 {
		for j := 0; j < col; j++ {
			matrix[0][j] = 0
		}
	}
	if firstCol == 0 {
		for i := 0; i < row; i++ {
			matrix[i][0] = 0
		}
	}
}

// func setZeroes(matrix [][]int) {
// 	row := len(matrix)
// 	col := len(matrix[0])

// 	rowFlag := make([]int, row)
// 	colFlag := make([]int, col)

// 	// 先标记
// 	for i := 0; i < row; i++ {
// 		for j := 0; j < col; j++ {
// 			if matrix[i][j] == 0 {
// 				rowFlag[i] = 1
// 				colFlag[j] = 1
// 			}
// 		}
// 	}

// 	// 再改变
// 	for i := 0; i < row; i++ {
// 		for j := 0; j < col; j++ {
// 			if rowFlag[i] == 1 || colFlag[j] == 1 {
// 				matrix[i][j] = 0
// 			}
// 		}
// 	}
// }

package sevenfour

func searchMatrix(matrix [][]int, target int) bool {
	row := len(matrix)
	col := len(matrix[0])

	i, j := 0, col-1
	for i < row && j >= 0 {
		if matrix[i][j] == target {
			return true
		} else if matrix[i][j] < target {
			i++
		} else {
			j--
		}
	}

	return false
}