LeetCode热题Top100 | 中等

给你两个非空的链表，表示两个非负的整数。
它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0开头。

示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

type ListNode struct {
	Val  int
	Next *ListNode
}

/*
模拟法
时间复杂度：O(max(m,n))
空间复杂度：O(1)
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	var head *ListNode
	var tail *ListNode
	carry := 0
	for l1 != nil || l2 != nil {
		n1, n2 := 0, 0
		if l1 != nil {
			n1 = l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			n2 = l2.Val
			l2 = l2.Next
		}
		sum := n1 + n2 + carry
		sum, carry = sum%10, sum/10
		if head == nil {
			head = &ListNode{Val: sum}
			tail = head
		} else {
			tail.Next = &ListNode{Val: sum}
			tail = tail.Next
		}
	}
	if carry > 0 {
		tail.Next = &ListNode{Val: carry}
	}
	return head
}

func main() {
	l1 := new(ListNode)
	l11 := new(ListNode)
	l111 := new(ListNode)
	l1.Val = 2
	l1.Next = l11
	l11.Val = 4
	l11.Next = l111
	l111.Val = 3
	l111.Next = nil

	l2 := new(ListNode)
	l22 := new(ListNode)
	l222 := new(ListNode)
	l2.Val = 5
	l2.Next = l22
	l22.Val = 4
	l22.Next = l222
	l222.Val = 6
	l222.Next = nil

	result := addTwoNumbers(l1, l2)
	fmt.Println(result)
}

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

示例1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。

请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。

/*
滑动窗口法
时间复杂度：O(n)
空间复杂度：O(字符集个数)
*/
func lengthOfLongestSubstring(s string) int {
	//哈希集合，用于去重
	m := map[byte]int{}
	//移动的指针
	rk, ans := -1, 0
	for i := 0; i < len(s); i++ {
		if i != 0 {
			//i每移动一次，把之前的一个删掉
			delete(m, s[i-1])
		}
		//若不重复，则不断向后查找
		for rk+1 < len(s) && m[s[rk+1]] == 0 {
			m[s[rk+1]]++
			rk++
		}
		//比较长度的最大值
		if ans < rk-i+1 {
			ans = rk - i + 1
		}
	}
	return ans
}

func main() {
	s := "abcabcbb"
	fmt.Println(lengthOfLongestSubstring(s))
}

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：
输入：s = "cbbd"
输出："bb"
*/

/*
暴力解法
时间复杂度：O(n³)
空间复杂度：O(1)

题解：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/

/*
暴力解法
时间复杂度：O(n³)
空间复杂度：O(1)

题解：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
*/
func longestPalindrome1(s string) string {
	length := len(s)
	if length < 2 {
		return s
	}
	maxLen, begin := 1, 0
	for i := 0; i < length-1; i++ {
		for j := i + 1; j < length; j++ {
			if j-i+1 > maxLen && validPalindrome(s, i, j) {
				maxLen = j - i + 1
				begin = i
			}
		}
	}
	return s[begin : begin+maxLen]
}

func validPalindrome(s string, left, right int) bool {
	for left < right {
		if s[left] != s[right] {
			return false
		}
		left++
		right--
	}
	return true
}

/*
中心扩散法
时间复杂度：O(n²)
空间复杂度：O(1)
*/
func longestPalindrome2(s string) string {
	length := len(s)
	if length < 2 {
		return s
	}
	maxLen, begin := 1, 0
	for i := 0; i < length-1; i++ {
		oddLen := expendAroundCenter(s, i, i)
		evenLen := expendAroundCenter(s, i, i+1)
		if max(oddLen, evenLen) > maxLen {
			maxLen = max(oddLen, evenLen)
			begin = i - (maxLen-1)/2
		}
	}
	return s[begin : begin+maxLen]
}

func expendAroundCenter(s string, left, right int) int {
	for left >= 0 && right < len(s) {
		if s[left] == s[right] {
			left--
			right++
		} else {
			break
		}
	}
	return right - left - 1
}

func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}

/*
动态规划
时间复杂度：O(n²)
空间复杂度：O(n²)
*/
func longestPalindrome3(s string) string {
	length := len(s)
	if length < 2 {
		return s
	}

	maxLen, begin := 1, 0
	dp := make([][]bool, length)
	for i := 0; i < length; i++ {
		dp[i] = make([]bool, length)
	}

	for i := 0; i < length; i++ {
		dp[i][i] = true
	}

	for L := 2; L <= length; L++ {
		for i := 0; i < length; i++ {
			j := L + i - 1
			if j >= length {
				break
			}

			if s[i] != s[j] {
				dp[i][j] = false
			} else {
				if j-i < 3 {
					dp[i][j] = true
				} else {
					dp[i][j] = dp[i+1][j-1]
				}
			}

			if dp[i][j] && j-i+1 > maxLen {
				maxLen = j - i + 1
				begin = i
			}
		}
	}

	return s[begin : begin+maxLen]
}

func main() {
	s := "babad"
	fmt.Println(longestPalindrome1(s))
	fmt.Println(longestPalindrome2(s))
	fmt.Println(longestPalindrome3(s))
}

给定一个长度为 n 的整数数组height。有n条垂线，第 i 条线的两个端点是(i, 0)和(i, height[i])。
找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为49。

示例 2：
输入：height = [1,1]
输出：1

/*
对撞指针法
时间复杂度：O(n)
空间复杂度：O(1)
*/
func maxArea(height []int) int {
	first, second := 0, len(height)-1
	area := 0
	h := 0
	for first < second {
		tempArea := 0
		width := second - first
		if height[first] < height[second] {
			h = height[first]
			first++
		} else {
			h = height[second]
			second--
		}
		tempArea = width * h
		if tempArea > area {
			area = tempArea
		}
	}
	return area
}

func main() {
	data := []int{1, 8, 6, 2, 5, 4, 8, 3, 7}
	fmt.Println(maxArea(data))
}

给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，
使得a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：
输入：nums = []
输出：[]

示例 3：
输入：nums = [0]
输出：[]

/*
排序+双指针
时间复杂度：O(n²)
空间复杂度：O(log(n))
*/
func threeSum(nums []int) [][]int {
	n := len(nums)
	sort.Ints(nums)
	ans := make([][]int, 0)

	// 枚举 a
	for first := 0; first < n; first++ {
		// 需要和上一次枚举的数不相同
		if first > 0 && nums[first] == nums[first-1] {
			continue
		}
		// c 对应的指针初始指向数组的最右端
		third := n - 1
		target := -1 * nums[first]
		// 枚举 b
		for second := first + 1; second < n; second++ {
			// 需要和上一次枚举的数不相同
			if second > first+1 && nums[second] == nums[second-1] {
				continue
			}
			// 需要保证 b 的指针在 c 的指针的左侧
			for second < third && nums[second]+nums[third] > target {
				third--
			}
			// 如果指针重合，随着 b 后续的增加
			// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
			if second == third {
				break
			}
			if nums[second]+nums[third] == target {
				ans = append(ans, []int{nums[first], nums[second], nums[third]})
			}
		}
	}
	return ans
}

func main() {
	data := []int{-1, 0, 1, 2, -1, -4}
	fmt.Println(threeSum(data))
}

给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：
输入：digits = ""
输出：[]

示例 3：
输入：digits = "2"
输出：["a","b","c"]

/*
回溯法
时间复杂度：O(3^m × 4^n)
空间复杂度：O(m+n)
*/
var phoneMap map[string]string = map[string]string{
	"2": "abc",
	"3": "def",
	"4": "ghi",
	"5": "jkl",
	"6": "mno",
	"7": "pqrs",
	"8": "tuv",
	"9": "wxyz",
}

var combinations []string

func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}
	combinations = []string{}
	backtrack(digits, 0, "")
	return combinations
}

func backtrack(digits string, index int, combination string) {
	if index == len(digits) {
		combinations = append(combinations, combination)
	} else {
		digit := string(digits[index])
		letters := phoneMap[digit]
		lettersCount := len(letters)
		for i := 0; i < lettersCount; i++ {
			backtrack(digits, index+1, combination+string(letters[i]))
		}
	}
}

func main() {
	digits := "234"
	fmt.Println(letterCombinations(digits))
}

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点

示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：
输入：head = [1], n = 1
输出：[]

示例 3：
输入：head = [1,2], n = 1
输出：[1]

type ListNode struct {
	Val  int
	Next *ListNode
}

/*
写法一，无头结点
时间复杂度：O(n)
空间复杂度：O(1)
*/
func removeNthFromEnd1(head *ListNode, n int) *ListNode {
	var length int
	node := head
	for node != nil {
		node = node.Next
		length++
	}
	//如果删除的是第一个结点，单独判断
	if length == n {
		return head.Next
	}
	index := length - n + 1
	h := head
	c := h
	for i := 1; i <= index; i++ {
		if i != index-1 {
			h = h.Next
		} else {
			h.Next = h.Next.Next
		}
	}
	return c
}

/*
写法二，有头结点
时间复杂度：O(n)
空间复杂度：O(1)
*/
func getLength(head *ListNode) (length int) {
	for ; head != nil; head = head.Next {
		length++
	}
	return
}

func removeNthFromEnd2(head *ListNode, n int) *ListNode {
	length := getLength(head)
	dummy := &ListNode{0, head}
	cur := dummy
	for i := 0; i < length-n; i++ {
		cur = cur.Next
	}
	cur.Next = cur.Next.Next
	return dummy.Next
}

func main() {
	n1, n2, n3, n4, n5 := new(ListNode), new(ListNode), new(ListNode), new(ListNode), new(ListNode)
	n1.Val = 1
	n2.Val = 2
	n3.Val = 3
	n4.Val = 4
	n5.Val = 5
	n1.Next = n2
	n2.Next = n3
	n3.Next = n4
	n4.Next = n5
	result := removeNthFromEnd1(n1, 2)
	for result != nil {
		fmt.Println(result.Val)
		result = result.Next
	}
}

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：
输入：n = 1
输出：["()"]

/*
回溯法
*/
func generateParenthesis(n int) []string {
	var result []string
	var backtrace func(left, right int, str string)
	backtrace = func(leftRemain, rightRemain int, str string) {
		if len(str) == 2*n { //递归出口
			result = append(result, str)
			return
		}
		if leftRemain > 0 { //剪枝条件1
			backtrace(leftRemain-1, rightRemain, str+"(")
		}
		if leftRemain < rightRemain { //剪枝条件2
			backtrace(leftRemain, rightRemain-1, str+")")
		}
	}
	backtrace(n, n, "")
	return result
}

func main() {
	fmt.Println(generateParenthesis(3))
}

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：
[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]
这样，排列 [2,3,1] 的下一个排列即为 [3,1,2]。特别的，最大的排列 [3,2,1] 的下一个排列为最小的排列 [1,2,3]。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，
那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，
那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。

示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]

示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]

示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]

/*
两遍扫描 法

思路：
首先从后向前查找第一个顺序对 (i,i+1)，满足 a[i] < a[i+1]。这样「较小数」即为 a[i]。此时 [i+1,n) 必然是下降序列。
如果找到了顺序对，那么在区间 [i+1,n) 中从后向前查找第一个元素 j 满足 a[i] < a[j]。这样「较大数」即为 a[j]。
交换 a[i] 与 a[j]，此时可以证明区间 [i+1,n) 必为降序。我们可以直接使用双指针反转区间 [i+1,n) 使其变为升序，而无需对该区间进行排序。
*/
func nextPermutation(nums []int) {
	n := len(nums)
	i := n - 2
	//从后往前数，找到第一个非升序的数，nums[i] >= nums[i+1] 该方法支持序列中存在重复元素
	for i >= 0 && nums[i] >= nums[i+1] {
		i--
	}
	if i >= 0 {
		j := n - 1
		//从后往前数，找到第一个非升序的数，nums[i]>=nums[j] 该方法支持序列中存在重复元素
		for j >= 0 && nums[i] >= nums[j] {
			j--
		}
		nums[i], nums[j] = nums[j], nums[i]
	}
	remain := nums[i+1:]
	for p, q := 0, len(remain); p < q/2; p++ {
		remain[p], remain[q-1-p] = remain[q-1-p], remain[p]
	}
}

func main() {
	//nums := []int{4, 5, 2, 6, 3, 1}
	nums := []int{1, 1}
	nextPermutation(nums)
	fmt.Println(nums)
}

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，
使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。
例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为[4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，
则返回它的下标，否则返回-1。

示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：
输入：nums = [1], target = 0
输出：-1

/*
暴力遍历
时间复杂度：O(n)
空间复杂度：O(1)
*/
func search1(nums []int, target int) int {
	for i := 0; i < len(nums); i++ {
		if nums[i] == target {
			return i
		}
	}
	return -1
}

/*
二分查找
时间复杂度：O(log(n))
空间复杂度：O(1)
*/
func search2(nums []int, target int) int {
	length := len(nums)
	if length == 0 {
		return -1
	}
	if length == 1 {
		if nums[0] == target {
			return 0
		} else if nums[0] != target {
			return -1
		}
	}
	l, r := 0, length-1
	for l <= r {
		mid := (l + r) / 2
		if nums[mid] == target {
			return mid
		}
		if nums[0] <= nums[mid] {
			if nums[0] <= target && target < nums[mid] {
				r = mid - 1
			} else {
				l = mid + 1
			}
		} else {
			if nums[mid] < target && target <= nums[length-1] {
				l = mid + 1
			} else {
				r = mid - 1
			}
		}
	}
	return -1
}

func main() {
	nums := []int{4, 5, 6, 7, 0, 1, 2}
	fmt.Println(search1(nums, 0))
	fmt.Println(search2(nums, 0))
}

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回[-1, -1]。

进阶：
你可以设计并实现时间复杂度为O(log n)的算法解决此问题吗？

示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：
输入：nums = [], target = 0
输出：[-1,-1]

/*
暴力遍历
时间复杂度：O(n)
空间复杂度：O(1)
*/
func searchRange1(nums []int, target int) []int {
	mapFirst := make(map[int]int)
	mapEnd := make(map[int]int)
	mapFirst[target], mapEnd[target] = -1, -1
	for i := 0; i < len(nums); i++ {
		if nums[i] == target && mapFirst[target] == -1 {
			mapFirst[target] = i
		}
		if nums[i] == target {
			mapEnd[target] = i
		}
		if i < len(nums)-1 && nums[i] == target && nums[i+1] != target {
			break
		}
	}
	return []int{mapFirst[target], mapEnd[target]}
}

/*
二分查找
时间复杂度：O(log(n))
空间复杂度：O(1)
*/
func searchRange2(nums []int, target int) []int {
	//sort.SearchInts 查找第一个找到的元素的下标(从0开始计数)，如果没有找到，则返回target可以插入的位置下标
	leftmost := sort.SearchInts(nums, target)
	if leftmost == len(nums) || nums[leftmost] != target {
		return []int{-1, -1}
	}
	rightmost := sort.SearchInts(nums, target+1) - 1
	return []int{leftmost, rightmost}
}

func main() {
	nums := []int{5, 7, 7, 8, 8, 10}
	fmt.Println(searchRange1(nums, 8))
	fmt.Println(searchRange2(nums, 8))
}

给你一个 无重复元素 的整数数组candidates 和一个目标整数target，
找出candidates中可以使数字和为目标数target 的 所有不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为target 的不同组合数少于 150 个。

示例1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：
输入: candidates = [2], target = 1
输出: []

/*
搜索回溯，无剪枝
时间复杂度：O(S)
空间复杂度：O(target)
*/
func combinationSum1(candidates []int, target int) (ans [][]int) {
	comb := []int{}
	var dfs func(target, idx int)
	dfs = func(target, idx int) {
		if idx == len(candidates) {
			return
		}
		if target == 0 {
			ans = append(ans, append([]int(nil), comb...))
			return
		}
		// 直接跳过
		dfs(target, idx+1)
		// 选择当前数
		if target-candidates[idx] >= 0 {
			comb = append(comb, candidates[idx])
			dfs(target-candidates[idx], idx)
			comb = comb[:len(comb)-1]
		}
	}
	dfs(target, 0)
	return
}

func combinationSum2(candidates []int, target int) [][]int {
	var res [][]int
	var dfs func(start int, temp []int, sum int)
	dfs = func(start int, temp []int, sum int) {
		if sum >= target {
			if sum == target {
				newTemp := make([]int, len(temp))
				copy(newTemp, temp)
				res = append(res, newTemp)
			}
			return
		}
		for i := start; i < len(candidates); i++ {
			temp = append(temp, candidates[i])
			dfs(i, temp, sum+candidates[i])
			temp = temp[:len(temp)-1]
		}
	}
	dfs(0, []int{}, 0)
	return res
}

func main() {
	candidates := []int{2, 3, 6, 7}
	fmt.Println(combinationSum1(candidates, 7))
	fmt.Println(combinationSum2(candidates, 7))
}

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：
输入：nums = [1]
输出：[[1]]

/*
回溯算法 =（递归+纯暴力搜索）因为：有的能用回溯做出来就不错了
特点：抽象
解决问题：组合、切割、子集、排列、棋盘（N皇后）
解题方法：动手画图（切忌纯想象），一般回溯问题都可以变形为n叉树形结构

解题模板：
func {
	if 终止条件 {
		收集结果
		return
	}
	for 元素集合 {
		处理结点
		递归
		回溯
	}
	正常return
}

学习视频地址：https://www.bilibili.com/video/BV1cy4y167mM/
*/
func permute(nums []int) [][]int {
	var ans [][]int
	var backTrack func(nums []int, length int, path []int)
	backTrack = func(nums []int, length int, path []int) {
		if len(nums) == 0 {
			//重新起一个地址存放，防止path上的值被覆盖
			p := make([]int, len(path))
			copy(p, path) //path -> p
			ans = append(ans, p)
		}
		for i := 0; i < length; i++ {
			cur := nums[i]

			path = append(path, cur)
			nums = append(nums[:i], nums[i+1:]...) //把位置i处的元素去除

			backTrack(nums, len(nums), path)

			//回溯之前的操作
			nums = append(nums[:i], append([]int{cur}, nums[i:]...)...)
			path = path[:len(path)-1]
		}
	}
	backTrack(nums, len(nums), []int{})
	return ans
}

func main() {
	nums := []int{5, 4, 6, 2}
	fmt.Println(permute(nums))
}

给定一个 n×n 的二维矩阵matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

func rotate(matrix [][]int) [][]int {
	if len(matrix) == 0 {
		return nil
	}
	xlen := len(matrix[0])
	ylen := len(matrix)

	var result [][]int
	for i := 0; i <= xlen-1; i++ {
		var tempArr []int
		for j := ylen - 1; j >= 0; j-- {
			tempArr = append(tempArr, matrix[j][i])
		}
		result = append(result, tempArr)
	}
	for i := 0; i < ylen; i++ {
		for j := 0; j < xlen; j++ {
			matrix[i][j] = result[i][j]
		}
	}
	return result
}

func main() {
	/*matrix := [][]int{
		{5, 1, 9, 11},
		{2, 4, 8, 10},
		{13, 3, 6, 7},
		{15, 14, 12, 16},
	}*/
	matrix := [][]int{
		{1, 2, 3},
		{4, 5, 6},
		{7, 8, 9},
	}
	//matrix := [][]int{}
	rotate(matrix)
}

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:
输入: strs = [""]
输出: [[""]]

示例 3:
输入: strs = ["a"]
输出: [["a"]]

/*
排序法
排序后的作为key，对应的字符串作为value数组
*/
func groupAnagrams(strs []string) [][]string {
	mp := map[string][]string{}
	for _, str := range strs {
		sbyte := []byte(str)
		sort.Slice(sbyte, func(i, j int) bool {
			return sbyte[i] < sbyte[j]
		})
		s := string(sbyte)
		mp[s] = append(mp[s], str)
	}
	ans := make([][]string, 0, len(mp))
	for _, v := range mp {
		ans = append(ans, v)
	}
	return ans
}

func main() {
	strs := []string{"eat", "tea", "tan", "ate", "nat", "bat"}
	fmt.Println(groupAnagrams(strs))
}

给定一个非负整数数组nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。

示例1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

/*
贪心
时间复杂度：O(n)
空间复杂度：O(1)
*/
func canJump(nums []int) bool {
	var maxNum func(i, j int) int
	maxNum = func(i, j int) int {
		if i > j {
			return i
		} else {
			return j
		}
	}

	n := len(nums)
	rightmost := 0
	for i := 0; i < n; i++ {
		if i <= rightmost {
			rightmost = maxNum(i+nums[i], rightmost)
			if rightmost >= n-1 {
				return true
			}
		}
	}

	return false
}

func main() {
	nums := []int{2, 3, 1, 1, 4}
	fmt.Println(canJump(nums))
}

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

/*
排序
时间复杂度：O(nlog(n))
空间复杂度：O(log(n))
*/
func merge(intervals [][]int) [][]int {
	var maxNum func(i, j int) int
	maxNum = func(i, j int) int {
		if i > j {
			return i
		} else {
			return j
		}
	}
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	result := make([][]int, 0, len(intervals))
	for i := 0; i < len(intervals); i++ {
		L, R := intervals[i][0], intervals[i][1]
		if len(result) == 0 || result[len(result)-1][1] < L {
			result = append(result, []int{L, R})
		} else {
			result[len(result)-1][1] = maxNum(result[len(result)-1][1], R)
		}
	}
	return result
}

func main() {
	intervals := [][]int{{1, 4}, {0, 3}, {3, 5}, {2, 9}, {2, 7}}
	fmt.Println(merge(intervals))
}

一个机器人位于一个 m x n （m行 x n列）网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
注意：1 <= m, n <= 100

示例 1：
输入：m = 3, n = 7
输出：28

示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：
输入：m = 7, n = 3
输出：28

示例 4：
输入：m = 3, n = 3
输出：6

/*
动态规划
转移方程：f(i,j)=f(i−1,j)+f(i,j−1)
时间复杂度：O(mn)
空间复杂度：O(mn)
*/
func uniquePaths(m int, n int) int {
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, n)
		dp[i][0] = 1
	}
	for j := 0; j < n; j++ {
		dp[0][j] = 1
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			dp[i][j] = dp[i-1][j] + dp[i][j-1]
		}
	}
	return dp[m-1][n-1]
}

func main() {
	fmt.Println(uniquePaths(3, 7))
}

给定一个包含非负整数的 mxn网格grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
注意：1 <= m, n <= 200

示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12

/*
动态规划
转移方程：
当 i>0 且 j=0 时，dp[i][0]=dp[i-1][0]+grid[i][0]
当 i=0 且 j>0 时，dp[0][j]=dp[0][j-1]+grid[0][j]
当 i>0 且 j>0 时，dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]

时间复杂度：O(mn)
空间复杂度：O(mn)
*/

func minPathSum(grid [][]int) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return 0
	}
	raw, column := len(grid), len(grid[0])
	dp := make([][]int, raw)
	for i := 0; i < raw; i++ {
		dp[i] = make([]int, column)
	}
	dp[0][0] = grid[0][0]
	for i := 1; i < raw; i++ {
		dp[i][0] = dp[i-1][0] + grid[i][0]
	}
	for i := 1; i < column; i++ {
		dp[0][i] = dp[0][i-1] + grid[0][i]
	}
	for i := 1; i < raw; i++ {
		for j := 1; j < column; j++ {
			dp[i][j] = int(math.Min(float64(dp[i-1][j]), float64(dp[i][j-1]))) + grid[i][j]
		}
	}
	return dp[raw-1][column-1]
}

func main() {
	fmt.Println(minPathSum([][]int{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}))
}