1. 两数相加(2)#
代码语言：javascript
复制给你两个非空的链表，表示两个非负的整数。
它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 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]
代码语言：javascript
复制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, 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)
}
2. 无重复字符的最长子串(3)#
代码语言：javascript
复制给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
示例1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。
代码语言：javascript
复制/*
滑动窗口法
时间复杂度：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))
}
3. 最长回文子串(5)#
代码语言：javascript
复制给你一个字符串 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/
代码语言：javascript
复制/*
暴力解法
时间复杂度：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))
}
4. 盛最多水的容器(11)#
代码语言：javascript
复制给定一个长度为 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
代码语言：javascript
复制/*
对撞指针法
时间复杂度：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))
}
5. 三数之和(15)#
代码语言：javascript
复制给你一个包含 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]
输出：[]
代码语言：javascript
复制/*
排序 双指针
时间复杂度：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))
}
6. 电话号码的字母组合(17)#
代码语言：javascript
复制给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
代码语言：javascript
复制/*
回溯法
时间复杂度：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))
}
7. 删除链表的倒数第n个结点(19)#
代码语言：javascript
复制给你一个链表，删除链表的倒数第 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]
代码语言：javascript
复制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
}
}
8. 括号生成(22)#
代码语言：javascript
复制数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
代码语言：javascript
复制/*
回溯法
*/
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))
}
9. 下一个排列(31)#
代码语言：javascript
复制整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如，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]
代码语言：javascript
复制/*
两遍扫描 法
思路：
首先从后向前查找第一个顺序对 (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)
}
10. 搜索旋转排序数组(33)#
代码语言：javascript
复制整数数组 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
代码语言：javascript
复制/*
暴力遍历
时间复杂度：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))
}
11. 排序数组中找元素的第一和末位位置(34)#
代码语言：javascript
复制给定一个按照升序排列的整数数组 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]
代码语言：javascript
复制/*
暴力遍历
时间复杂度：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))
}
12. 组合总和(39)#
代码语言：javascript
复制给你一个 无重复元素 的整数数组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
输出: []
代码语言：javascript
复制/*
搜索回溯，无剪枝
时间复杂度：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))
}
13. 全排列(46)#
代码语言：javascript
复制给定一个不含重复数字的数组 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]]
代码语言：javascript
复制/*
回溯算法 =（递归 纯暴力搜索）因为：有的能用回溯做出来就不错了
特点：抽象
解决问题：组合、切割、子集、排列、棋盘（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))
}
14. 旋转图像(48)#
代码语言：javascript
复制给定一个 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]]
代码语言：javascript
复制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)
}
15. 字母异位词分组(49)#
代码语言：javascript
复制给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
代码语言：javascript
复制/*
排序法
排序后的作为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))
}
16. 跳跃游戏(55)#
代码语言：javascript
复制给定一个非负整数数组nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
代码语言：javascript
复制/*
贪心
时间复杂度：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))
}
17. 合并区间(56)#
代码语言：javascript
复制以数组 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] 可被视为重叠区间。
代码语言：javascript
复制/*
排序
时间复杂度：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))
}
18. 不同路径(62)#
代码语言：javascript
复制一个机器人位于一个 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
代码语言：javascript
复制/*
动态规划
转移方程：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))
}
19. 最小路径和(64)#
代码语言：javascript
复制给定一个包含非负整数的 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
代码语言：javascript
复制/*
动态规划
转移方程：
当 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}}))
}
20. 颜色分类(75)#
代码语言：javascript
复制给定一个包含红色、白色和蓝色、共n 个元素的数组nums，原地对它们进行排序，
使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
代码语言：javascript
复制/*
单指针
时间复杂度：O(n)
空间复杂度：O(1)
*/
func sortColors1(nums []int) {
var swap func(nums []int, target int) (targetIndex int)
swap = func(nums []int, target int) (targetIndex int) {
for i, v := range nums {
if v == target {
nums[i], nums[targetIndex] = nums[targetIndex], nums[i]
targetIndex
}
}
return
}
index := swap(nums, 0)
swap(nums[index:], 1)
}
/*
双指针
时间复杂度：O(n)
空间复杂度：O(1)
*/
func sortColors2(nums []int) {
p0, p1 := 0, 0
for i, v := range nums {
if v == 0 {
nums[p0], nums[i] = nums[i], nums[p0]
if p0 < p1 {
nums[p1], nums[i] = nums[i], nums[p1]
}
p0
p1
} else if v == 1 {
nums[p1], nums[i] = nums[i], nums[p1]
p1
}
}
}
/*
双指针
时间复杂度：O(n)
空间复杂度：O(1)
*/
func sortColors3(nums []int) {
p0, p2 := 0, len(nums)-1
for i := 0; i <= p2; i {
for ; i <= p2 && nums[i] == 2; p2-- {
nums[p2], nums[i] = nums[i], nums[p2]
}
if nums[i] == 0 {
nums[p0], nums[i] = nums[i], nums[p0]
p0
}
}
}
func main() {
nums := []int{2, 0, 2, 1, 1, 0}
//sortColors1(nums)
//sortColors2(nums)
sortColors3(nums)
fmt.Println(nums)
}
21. 子集(78)#
代码语言：javascript
复制给你一个整数数组nums ，数组中的元素互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
代码语言：javascript
复制/*
迭代法实现子集枚举
时间复杂度：O(n*(2^n))
空间复杂度：O(n)
*/
func subsets1(nums []int) [][]int {
var ans [][]int
n := len(nums)
for i := 0; i < (1 << n); i {
var set []int
for j := 0; j < n; j {
if ((i >> j) & 1) > 0 {
set = append(set, nums[j])
}
}
ans = append(ans, append([]int(nil), set...))
}
return ans
}
/*
递归法实现子集枚举
时间复杂度：O(n*(2^n))
空间复杂度：O(n)
解析：https://leetcode-cn.com/problems/subsets/solution/shou-hua-tu-jie-zi-ji-hui-su-fa-xiang-jie-wei-yun-/
*/
func subsets2(nums []int) [][]int {
var ans [][]int
var set []int
n := len(nums)
var dfs func(cur int)
dfs = func(cur int) {
if cur == n {
ans = append(ans, append([]int(nil), set...))
return
}
set = append(set, nums[cur])
dfs(cur 1)
set = set[:len(set)-1] //回溯
dfs(cur 1)
}
dfs(0)
return ans
}
func main() {
arr := []int{1, 2, 3}
fmt.Println(subsets1(arr))
fmt.Println(subsets2(arr))
}
22. 单词搜索(79)#
代码语言：javascript
复制给定一个m x n 二维字符网格board 和一个字符串单词word 。
如果word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，
其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = 'ABCCED'
输出：true
示例 2：
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = 'SEE'
输出：true
示例 3：
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = 'ABCB'
输出：false
代码语言：javascript
复制/*
回溯
时间复杂度：上界为 O(M*N*(3^L))，其中 M,N 为网格的长度与宽度，L 为字符串 word 的长度
空间复杂度：O(M*N)
*/
func exist(board [][]byte, word string) bool {
type pair struct {
x, y int
}
directions := []pair{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
h, w := len(board), len(board[0])
vis := make([][]bool, h)
for i := 0; i < h; i {
vis[i] = make([]bool, w)
}
var check func(i, j, k int) bool
check = func(i, j, k int) bool {
if board[i][j] != word[k] {
return false
}
if k == len(word)-1 {
return true
}
vis[i][j] = true
for m := 0; m < len(directions); m {
newI, newJ := i directions[m].x, j directions[m].y
if (newI >= 0 && newI < h) && (newJ >= 0 && newJ < w) && !vis[newI][newJ] {
if check(newI, newJ, k 1) {
return true
}
}
}
vis[i][j] = false
return false
}
for i := 0; i < h; i {
for j := 0; j < w; j {
if check(i, j, 0) {
return true
}
}
}
return false
}
func main() {
board := [][]byte{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}
word := "ABCCED"
fmt.Println(exist(board, word))
}
23. 不同的二叉搜索树(96)#
代码语言：javascript
复制给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1
解析：https://leetcode-cn.com/problems/unique-binary-search-trees/solution/bu-tong-de-er-cha-sou-suo-shu-by-leetcode-solution/
代码语言：javascript
复制/*
动态规划
转移方程：F(i,n)=G(i−1)⋅G(n−i)
G(i−1)表示根结点左边
G(n−i)表示根结点右边
边界情况：G(0)=1,G(1)=1
时间复杂度 : O(n^2)
空间复杂度 : O(n)
*/
func numTrees1(n int) int {
G := make([]int, n 1)
G[0], G[1] = 1, 1
for i := 2; i <= n; i {
for j := 1; j <= i; j {
G[i] = G[j-1] * G[i-j]
}
}
return G[n]
}
/*
数学公式法
时间复杂度 : O(n)
空间复杂度 : O(1)
*/
func numTrees2(n int) int {
C := 1
for i := 0; i < n; i {
C = C * 2 * (2*i 1) / (i 2)
}
return C
}
func main() {
fmt.Println(numTrees1(3))
fmt.Println(numTrees2(3))
}
24. 验证二叉搜索树(98)#
代码语言：javascript
复制给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3] //按层次遍历生成二叉树
输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6] //按层次遍历生成二叉树
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
代码语言：javascript
复制type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
/*
递归
时间复杂度：O(n)
空间复杂度：O(n)
*/
func isValidBST1(root *TreeNode) bool {
var helper func(root *TreeNode, lower, upper int) bool
helper = func(root *TreeNode, lower, upper int) bool {
if root == nil {
return true
}
if root.Val <= lower || root.Val >= upper {
return false
}
return helper(root.Left, lower, root.Val) && helper(root.Right, root.Val, upper)
}
return helper(root, math.MinInt64, math.MaxInt64)
}
/*
中序遍历
时间复杂度：O(n)
空间复杂度：O(n)
*/
func isValidBST2(root *TreeNode) bool {
var stack []*TreeNode
inorder := math.MinInt64
for len(stack) > 0 || root != nil {
for root != nil {
stack = append(stack, root)
root = root.Left
}
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
if root.Val <= inorder {
return false
}
inorder = root.Val
root = root.Right
}
return true
}
func main() {
n1, n2, n3, n4, n5 := new(TreeNode), new(TreeNode), new(TreeNode), new(TreeNode), new(TreeNode)
n1.Val, n2.Val, n3.Val, n4.Val, n5.Val = 5, 1, 4, 3, 6
n1.Left, n1.Right = n2, n3
n3.Left, n3.Right = n4, n5
fmt.Println(isValidBST1(n1))
fmt.Println(isValidBST2(n1))
}
25. 二叉树的层次遍历(102)#
代码语言：javascript
复制给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
代码语言：javascript
复制type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
/*
广度优先搜索
时间复杂度：O(n)
空间复杂度：O(n)
*/
func levelOrder(root *TreeNode) [][]int {
if root == nil {
return nil
}
var ret [][]int
q := []*TreeNode{root} //根结点赋值
var i int
for len(q) > 0 {
ret = append(ret, []int{}) //给ret增加一个初始化
var p []*TreeNode
for j := 0; j < len(q); j {
node := q[j]
ret[i] = append(ret[i], node.Val)
if node.Left != nil {
p = append(p, node.Left)
}
if node.Right != nil {
p = append(p, node.Right)
}
}
q = p //把下一层结点赋值给q
i //层数加一
}
return ret
}
func main() {
n1, n2, n3, n4, n5 := new(TreeNode), new(TreeNode), new(TreeNode), new(TreeNode), new(TreeNode)
n1.Val, n2.Val, n3.Val, n4.Val, n5.Val = 3, 9, 20, 15, 7
n1.Left, n1.Right = n2, n3
n3.Left, n3.Right = n4, n5
fmt.Println(levelOrder(n1))
}
26. 从前序与中序遍历序列构造二叉树(105)#
代码语言：javascript
复制给定两个整数数组preorder 和 inorder，其中preorder 是二叉树的先序遍历，
inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。
preorder 和 inorder 均 无重复 元素.
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
代码语言：javascript
复制type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
/*
递归
时间复杂度：O(n)
空间复杂度：O(n)
*/
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder) == 0 {
return nil
}
root := &TreeNode{preorder[0], nil, nil}
i := 0
for ; i < len(inorder); i {
if inorder[i] == preorder[0] {
break
}
}
root.Left = buildTree(preorder[1:len(inorder[:i]) 1], inorder[:i])
root.Right = buildTree(preorder[len(inorder[:i]) 1:], inorder[i 1:])
return root
}
func main() {
preorder := []int{3,9,20,15,7}
inorder := []int{9,3,15,20,7}
fmt.Println(buildTree(preorder, inorder))
}
