0301-0400-Easy

303.区域和检索-数组不可变(2)

  • 题目
给定一个整数数组  nums,求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和,包含 i,  j 两点。
示例:
给定 nums = [-2, 0, 3, -5, 2, -1],求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

说明:
    你可以假设数组不可变。
    会多次调用 sumRange 方法。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 一维前缀和 O(1) O(n)
02 遍历计算 O(n) O(1)
type NumArray struct {
    arr []int
}

func Constructor(nums []int) NumArray {
    size := len(nums)
    arr := make([]int, size+1)
    for i := 1; i <= size; i++ {
        arr[i] = arr[i-1] + nums[i-1]
    }
    return NumArray{arr: arr}
}

func (n *NumArray) SumRange(i int, j int) int {
    return n.arr[j+1] - n.arr[i]
}

#
type NumArray struct {
    arr []int
}

func Constructor(nums []int) NumArray {
    return NumArray{nums}
}

func (n *NumArray) SumRange(i int, j int) int {
    sum := 0
    for ; i <= j; i++ {
        sum = sum + n.arr[i]
    }
    return sum
}

326.3的幂(3)

  • 题目
给定一个整数,写一个函数来判断它是否是 3 的幂次方。
示例 1: 输入: 27 输出: true
示例 2: 输入: 0 输出: false
示例 3: 输入: 9 输出: true
示例 4: 输入: 45 输出: false
进阶:你能不使用循环或者递归来完成本题吗?
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 迭代 I O(1)
02 转3进制判断 O(log(n)) O(1)
03 递归 O(log(n)) O(log(n))
func isPowerOfThree(n int) bool {
    if n <= 0 {
        return false
    }
    for n > 1 {
        if n % 3 != 0{
            return false
        }
        n = n / 3
    }
    return n == 1
}

#
func isPowerOfThree(n int) bool {
    if n <= 0 {
        return false
    }
    str := strconv.FormatInt(int64(n), 3)
    return str[0:1] == "1" && strings.Count(str, "0") == len(str)-1
}


#
func isPowerOfThree(n int) bool {
    if n <= 0 {
        return false
    }
    if n == 1 {
        return true
    }
    if n%3 != 0 {
        return false
    }
    return isPowerOfThree(n / 3)
}

342.4的幂(4)

  • 题目
给定一个整数 (32 位有符号整数),请编写一个函数来判断它是否是 4 的幂次方。
示例 1: 输入: 16 输出: true
示例 2: 输入: 5 输出: false
进阶:你能不使用循环或者递归来完成本题吗?
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 迭代 O(log(n)) O(1)
02 递归 O(log(n)) O(log(n))
03 位运算 O(1) O(1)
04 转4进制 O(log(n)) O(1)
func isPowerOfFour(num int) bool {
    if num <= 0 {
        return false
    }

    for num > 1 {
        if num%4 != 0 {
            return false
        }
        num = num / 4
    }
    return num == 1
}

#
func isPowerOfFour(num int) bool {
    if num <= 0 {
        return false
    }
    if num == 1{
        return true
    }
    if num % 4 != 0{
        return false
    }

    return isPowerOfFour(num/4)
}

#
func isPowerOfFour(num int) bool {
    if num <= 0 {
        return false
    }
    // return (num & (num-1) == 0) && (num-1)%3 == 0
    return (num&(num-1) == 0) && (num&0xaaaaaaaa == 0)
}

#
func isPowerOfFour(num int) bool {
    if num <= 0 {
        return false
    }
    str := strconv.FormatInt(int64(num), 4)
    return str[0:1] == "1" && strings.Count(str, "0") == len(str)-1
}

344.反转字符串(3)

  • 题目
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1: 输入:["h","e","l","l","o"] 输出:["o","l","l","e","h"]
示例 2: 输入:["H","a","n","n","a","h"] 输出:["h","a","n","n","a","H"]
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 双指针 O(n) O(1)
02 递归 O(n) O(n)
03 单指针 O(n) O(1)
func reverseString(s []byte) {
    i, j := 0, len(s)-1
    for i < j {
        s[i], s[j] = s[j], s[i]
        i++
        j--
    }
}

#
func reverseString(s []byte) {
    var reverse func(int, int)
    reverse = func(left, right int) {
        if left < right {
            s[left], s[right] = s[right], s[left]
            reverse(left+1, right-1)
        }
    }
    reverse(0, len(s)-1)
}

#
func reverseString(s []byte) {
    for i := 0; i < len(s)/2; i++ {
        s[i], s[len(s)-1-i] = s[len(s)-1-i], s[i]
    }
}

345.反转字符串中的元音字母(2)

  • 题目
编写一个函数,以字符串作为输入,反转该字符串中的元音字母。

示例 1:输入: "hello"输出: "holle"
示例 2:输入: "leetcode"输出: "leotcede"
说明:元音字母不包含字母"y"。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 双指针 O(n) O(1)
02 数组辅助替换 O(n) O(n)
func reverseVowels(s string) string {
    bytes := []byte(s)
    length := len(s)
    i, j := 0, length-1
    for i < j {
        if !isvowels(bytes[i]) {
            i++
            continue
        }
        if !isvowels(bytes[j]) {
            j--
            continue
        }
        bytes[i], bytes[j] = bytes[j], bytes[i]
        i++
        j--
    }
    return string(bytes)
}

func isvowels(b byte) bool {
    return b == 'a' || b == 'e' || b == 'i' || b == 'o' || b == 'u' ||
        b == 'A' || b == 'E' || b == 'I' || b == 'O' || b == 'U'
}

#
func reverseVowels(s string) string {
    bytes := []byte(s)
    length := len(s)
    temp := make([]byte, 0)
    for i := 0; i < length; i++ {
        if isvowels(bytes[i]) {
            temp = append(temp, bytes[i])
        }
    }
    count := 0
    for i := 0; i < length; i++ {
        if isvowels(bytes[i]) {
            bytes[i] = temp[len(temp)-1-count]
            count++
        }
    }
    return string(bytes)
}

func isvowels(b byte) bool {
    return b == 'a' || b == 'e' || b == 'i' || b == 'o' || b == 'u' ||
        b == 'A' || b == 'E' || b == 'I' || b == 'O' || b == 'U'
}

349.两个数组的交集(3)

  • 题目
给定两个数组,编写一个函数来计算它们的交集。
示例 1:输入: nums1 = [1,2,2,1], nums2 = [2,2]输出: [2]
示例 2:输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出: [9,4]
说明:
    输出结果中的每个元素一定是唯一的。
    我们可以不考虑输出结果的顺序。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 单哈希辅助 O(n) O(n)
02 双哈希辅助 O(n) O(n)
03 排序双指针 O(nlog(n)) O(n)
func intersection(nums1 []int, nums2 []int) []int {
    res := make([]int, 0)
    m := make(map[int]int)
    for _, v := range nums1 {
        m[v] = 1
    }
    for _, v := range nums2 {
        if m[v] == 1 {
            res = append(res, v)
            m[v] += 1
        }
    }
    return res
}

#
func intersection(nums1 []int, nums2 []int) []int {
    m1 := make(map[int]bool)
    m2 := make(map[int]bool)
    res := make([]int, 0)
    for _, v := range nums1 {
        m1[v] = true
    }

    for _, v := range nums2 {
        if m1[v] != false {
            m2[v] = true
        }
    }

    for k := range m2 {
        res = append(res, k)
    }
    return res
}

#
func intersection(nums1 []int, nums2 []int) []int {
    sort.Ints(nums1)
    sort.Ints(nums2)
    res := make([]int, 0)
    i := 0
    j := 0
    for i < len(nums1) && j < len(nums2) {
        if nums1[i] < nums2[j] {
            i++
        } else if nums1[i] > nums2[j] {
            j++
        } else {
            if len(res) == 0 || res[len(res)-1] != nums1[i] {
                res = append(res, nums1[i])
            }
            i++
            j++
        }
    }
    return res
}

350.两个数组的交集 II(3)

  • 题目
给定两个数组,编写一个函数来计算它们的交集。
示例 1: 输入: nums1 = [1,2,2,1], nums2 = [2,2]  输出: [2,2]
示例 2: 输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出: [4,9]
说明:输出结果中每个元素出现的次数,应与元素在两个数组中出现的次数一致。
     我们可以不考虑输出结果的顺序。
进阶:
    如果给定的数组已经排好序呢?你将如何优化你的算法?
    如果 nums1 的大小比 nums2 小很多,哪种方法更优?
    如果 nums2 的元素存储在磁盘上,磁盘内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 单哈希辅助 O(n) O(n)
02 双哈希辅助 O(n) O(n)
03 排序双指针 O(nlog(n)) O(n)
func intersect(nums1 []int, nums2 []int) []int {
    m1 := make(map[int]int)
    res := make([]int, 0)
    for _, v := range nums1 {
        m1[v] += 1
    }

    for _, v := range nums2 {
        if m1[v] > 0 {
            res = append(res, v)
            m1[v]--
        }
    }
    return res
}

#
func intersect(nums1 []int, nums2 []int) []int {
    m1 := make(map[int]int)
    m2 := make(map[int]int)
    res := make([]int, 0)
    for _, v := range nums1 {
        m1[v]++
    }

    for _, v := range nums2 {
        if m1[v] != 0 && m1[v] > m2[v] {
            m2[v]++
        }
    }

    for k := range m2 {
        for i := 0; i < m2[k]; i++ {
            res = append(res, k)
        }
    }
    return res
}

#
func intersect(nums1 []int, nums2 []int) []int {
    sort.Ints(nums1)
    sort.Ints(nums2)
    res := make([]int, 0)
    i := 0
    j := 0
    for i < len(nums1) && j < len(nums2) {
        if nums1[i] < nums2[j] {
            i++
        } else if nums1[i] > nums2[j] {
            j++
        } else {
            res = append(res, nums1[i])
            i++
            j++
        }
    }
    return res
}

367.有效的完全平方数(4)

  • 题目
给定一个正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 True,否则返回 False。
说明:不要使用任何内置的库函数,如  sqrt。
示例 1:输入:16 输出:True
示例 2:输入:14 输出:False
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 二分查找 O(log(n)) O(1)
02 牛顿迭代法 O(log(n)) O(1)
03 数学法 O(n^1/2) O(1)
04 暴力法 O(n^1/2) O(1)
func isPerfectSquare(num int) bool {
    if num < 2 {
        return true
    }
    left := 2
    right := num / 2
    for left <= right {
        mid := left + (right-left)/2
        if mid*mid == num {
            return true
        } else if mid*mid > num {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return false
}

#
func isPerfectSquare(num int) bool {
    if num < 2 {
        return true
    }
    x := num / 2
    for x*x > num {
        x = (x + num/x) / 2
    }
    return x*x == num
}

#
func isPerfectSquare(num int) bool {
    i := 1
    for num > 0 {
        num = num - i
        i = i + 2
    }
    return num == 0
}

#
func isPerfectSquare(num int) bool {
    i := 1
    for i * i < num{
        i++
    }
    return i * i == num
}

371.两整数之和(2)

  • 题目
不使用运算符 + 和 - ,计算两整数a,b之和。
示例 1:输入: a = 1, b = 2 输出: 3
示例 2:输入: a = -2, b = 3 输出: 1
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 迭代 O(1) O(1)
02 递归 O(1) O(1)
func getSum(a int, b int) int {
    for b != 0 {
        a, b = a^b, (a&b)<<1
    }
    return a
}


#
func getSum(a int, b int) int {
    if b == 0 {
        return a
    }
    return getSum(a^b, (a&b)<<1)
}

374.猜数字大小(2)

  • 题目
我们正在玩一个猜数字游戏。 游戏规则如下:
我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。
每次你猜错了,我会告诉你这个数字是大了还是小了。
你调用一个预先定义好的接口 guess(int num),它会返回 3 个可能的结果(-1,1 或 0):
-1 : 我的数字比较小
 1 : 我的数字比较大
 0 : 恭喜!你猜对了!

示例 :输入: n = 10, pick = 6 输出: 6
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 二分查找 O(log(n)) O(1)
02 递归 O(log(n)) O(log(n))
func guessNumber(n int) int {
    low := 1
    high := n
    for low < high{
        mid := low + (high-low)/2
        if guess(mid) == 0{
            return mid
        }else if guess(mid) == 1{
            low = mid + 1
        }else {
            high = mid - 1
        }
    }
    return low
}

#
func guessNumber(n int) int {
    return binary(1, n)
}

func binary(left, right int) int {
    mid := left + (right-left)/2
    if guess(mid) == 1 {
        return binary(mid+1, right)
    } else if guess(mid) == -1 {
        return binary(left, mid-1)
    } else {
        return mid
    }
}

383.赎金信(3)

  • 题目
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串,
判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。
如果可以构成,返回 true ;否则返回 false。

(题目说明:为了不暴露赎金信字迹,要从杂志上搜索各个需要的字母,组成单词来表达意思。
杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

注意:你可以假设两个字符串均只含有小写字母。
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 数组辅助 O(n) O(1)
02 哈希辅助 O(n) O(1)
03 排序双指针 O(nlog(n)) O(n)
func canConstruct(ransomNote string, magazine string) bool {
    index := [26]int{}
    for i := 0; i < len(magazine); i++ {
        index[magazine[i]-'a']++
    }

    for i := 0; i < len(ransomNote); i++ {
        index[ransomNote[i]-'a']--
        if index[ransomNote[i]-'a'] < 0 {
            return false
        }
    }
    return true
}

#
func canConstruct(ransomNote string, magazine string) bool {
    index := make(map[uint8]int)
    for i := 0; i < len(magazine); i++ {
        index[magazine[i]-'a']++
    }

    for i := 0; i < len(ransomNote); i++ {
        index[ransomNote[i]-'a']--
        if index[ransomNote[i]-'a'] < 0 {
            return false
        }
    }
    return true
}

#
func canConstruct(ransomNote string, magazine string) bool {
    ransomNoteArr := strings.Split(ransomNote, "")
    magazineArr := strings.Split(magazine, "")
    sort.Strings(ransomNoteArr)
    sort.Strings(magazineArr)

    i := 0
    j := 0
    for i < len(ransomNoteArr) && j < len(magazineArr) {
        if ransomNoteArr[i] > magazineArr[j] {
            j++
        } else if ransomNoteArr[i] < magazineArr[j] {
            return false
        } else {
            i++
            j++
        }
    }
    return i == len(ransomNote)
}

387.字符串中的第一个唯一字符(3)

  • 题目
给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。
案例:
s = "leetcode"返回 0.
s = "loveleetcode",返回 2.
注意事项:您可以假定该字符串只包含小写字母。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 数组辅助 O(n) O(1)
02 哈希辅助 O(n) O(1)
03 暴力法 O(n^2) O(1)
func firstUniqChar(s string) int {
    m := [26]int{}
    for i := 0; i < len(s); i++ {
        m[s[i]-'a']++
    }
    for i := 0; i < len(s); i++ {
        if m[s[i]-'a'] == 1 {
            return i
        }
    }
    return -1
}

#
func firstUniqChar(s string) int {
    m := make(map[uint8]int)
    for i := 0; i < len(s); i++ {
        m[s[i]-'a']++
    }
    for i := 0; i < len(s); i++ {
        if m[s[i]-'a'] == 1 {
            return i
        }
    }
    return -1
}

#
func firstUniqChar(s string) int {
    for i := 0; i < len(s); i++ {
        flag := true
        for j := 0; j < len(s); j++ {
            if s[i] == s[j] && i != j {
                flag = false
                break
            }
        }
        if flag {
            return i
        }
    }
    return -1
}

389.找不同(5)

  • 题目
给定两个字符串 s 和 t,它们只包含小写字母。
字符串 t 由字符串 s 随机重排,然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。 
示例:输入:s = "abcd"t = "abcde"输出:e
解释:'e' 是那个被添加的字母。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 数组辅助 O(n) O(1)
02 哈希辅助 O(n) O(1)
03 位计算 O(n) O(1)
04 数学计算 O(n) O(1)
05 排序遍历 O(nlog(n)) O(1)
func findTheDifference(s string, t string) byte {
    m := [26]int{}
    bytest := []byte(t)
    bytess := []byte(s)
    for _, v := range bytest {
        m[v-'a']++
    }
    for _, v := range bytess {
        m[v-'a']--
    }
    for k := range m {
        if m[k] == 1 {
            return byte(k + 'a')
        }
    }
    return 0
}

#
func findTheDifference(s string, t string) byte {
    m := make(map[byte]int)
    bytest := []byte(t)
    bytess := []byte(s)
    for _, v := range bytest {
        m[v]++
    }
    for _, v := range bytess {
        m[v]--
    }
    for k := range m {
        if m[k] == 1 {
            return k
        }
    }
    return 0
}

#
func findTheDifference(s string, t string) byte {
    ch := byte(0)
    for _, value := range s {
        ch ^= byte(value)
    }
    for _, value := range t {
        ch ^= byte(value)
    }
    return ch
}

#
func findTheDifference(s string, t string) byte {
    ch := byte(0)
    for _, value := range t {
        ch += byte(value)
    }
    for _, value := range s {
        ch -= byte(value)
    }
    return ch
}

#
func findTheDifference(s string, t string) byte {
    sArr := strings.Split(s, "")
    tArr := strings.Split(t, "")
    sort.Strings(sArr)
    sort.Strings(tArr)
    for i := 0; i < len(sArr); i++{
        if sArr[i] != tArr[i]{
            return []byte(tArr[i])[0]
        }
    }
    return []byte(tArr[len(tArr)-1])[0]
}

392.判断子序列(4)

  • 题目
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。
字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。
(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。
示例 1:s = "abc", t = "ahbgdc"返回 true.
示例 2:s = "axc", t = "ahbgdc"返回 false.
后续挑战 :
如果有大量输入的 S,称作S1, S2, ... , Sk 其中 k >= 10亿,
你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 双指针 O(n) O(1)
02 单指针遍历 O(n^2) O(1)
03 二分查找 O(nlog(n)) o
04 动态规划 O(n^2) O(n^2)
func isSubsequence(s string, t string) bool {
    if len(s) > len(t){
        return false
    }
    i := 0
    j := 0
    for i < len(s) && j < len(t){
        if s[i] == t[j]{
            i++
        }
        j++
    }
    return i == len(s)
}

#
func isSubsequence(s string, t string) bool {
    for _, v := range s{
        idx := strings.IndexRune(t, v)
        if idx == -1{
            return false
        }
        t = t[idx+1:]
    }
    return true
}

#
func isSubsequence(s string, t string) bool {
    m := make(map[uint8][]int)
    for i := 0; i < len(t); i++ {
        value := t[i] - 'a'
        if m[value] == nil {
            m[value] = make([]int, 0)
        }
        m[value] = append(m[value], i)
    }
    prev := -1
    for i := 0; i < len(s); i++ {
        value := s[i] - 'a'
        left := 0
        right := len(m[value]) - 1
        if len(m[value]) == 0 {
            return false
        }
        for left < right {
            mid := left + (right-left)/2
            if m[value][mid] > prev {
                right = mid
            } else {
                left = mid + 1
            }
        }
        if left > right || m[value][left] <= prev {
            return false
        }
        prev = m[value][left]
    }
    return true
}

#
/*
状态定义: dp[i][j] 表示长度为i的字符串s是否为长度为j的字符串t的子序列
状态转移方程: 如果s[i] == t[j], 则dp[i][j] = dp[i-1][j-1]
如果s[i] != t[j],则dp[i][j] = dp[i][j-1]
初始: dp[0][j] = true 表示空串s 是任意长度串t的子串
dp[i][0] = false 表示任意长度非空串s 不是空串t的字串
dp[i][0] = false 表示任意长度非空串s 不是空串t的字串
*/
func isSubsequence(s string, t string) bool {
    if len(s) == 0 {
        return true
    } else if len(s) > len(t) {
        return false
    }

    dp := make([][]bool, len(s)+1)
    for i := 0; i < len(s)+1; i++ {
        dp[i] = make([]bool, len(t)+1)
        dp[i][0] = false
    }
    for i := 0; i <= len(t); i++ {
        dp[0][i] = true
    }

    for i := 1; i <= len(s); i++ {
        for j := 1; j <= len(t); j++ {
            if s[i-1] == t[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = dp[i][j-1]
            }
        }
    }
    return dp[len(s)][len(t)]
}

0301-0400-Medium

304.二维区域和检索-矩阵不可变(1)

  • 题目
给定一个二维矩阵,计算其子矩形范围内元素的总和,该子矩阵的左上角为 (row1, col1) ,
右下角为 (row2, col2)。
Range Sum Query 2D
上图子矩阵左上角 (row1, col1) = (2, 1) ,右下角(row2, col2) = (4, 3),
该子矩形内元素的总和为 8。
示例: 给定 matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
说明:你可以假设矩阵不可变。
    会多次调用 sumRegion 方法。
    你可以假设 row1 ≤ row2 且 col1 ≤ col2。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 前缀和 O(1) O(n^2)
type NumMatrix struct {
    arr [][]int
}

func Constructor(matrix [][]int) NumMatrix {
    if matrix == nil || len(matrix) == 0 || matrix[0] == nil || len(matrix[0]) == 0 {
        arr := make([][]int, 1)
        for i := 0; i < 1; i++ {
            arr[i] = make([]int, 1)
        }
        return NumMatrix{arr: arr}
    }
    n, m := len(matrix), len(matrix[0])
    arr := make([][]int, n+1)
    for i := 0; i < n+1; i++ {
        arr[i] = make([]int, m+1)
    }
    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            arr[i][j] = arr[i][j-1] + arr[i-1][j] - arr[i-1][j-1] + matrix[i-1][j-1]
        }
    }
    return NumMatrix{arr: arr}
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
    return this.arr[row2+1][col2+1] - this.arr[row2+1][col1] - this.arr[row1][col2+1] + this.arr[row1][col1]
}

306.累加数(1)

  • 题目
累加数是一个字符串,组成它的数字可以形成累加序列。
一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外,字符串中的其他数都等于它之前两个数相加的和。
给定一个只包含数字 '0'-'9' 的字符串,编写一个算法来判断给定输入是否是累加数。
说明: 累加序列里的数不会以 0 开头,所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
示例 1:输入: "112358" 输出: true 
解释: 累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
示例 2:输入: "199100199" 输出: true 
解释: 累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199
进阶:你如何处理一个溢出的过大的整数输入?
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 回溯 O(n(log(n))^2) O(n)
var res []int

func isAdditiveNumber(num string) bool {
    if len(num) < 3 {
        return false
    }
    res = make([]int, 0)
    dfs(num, 0, 0, 0, make([]int, 0))
    return len(res) >= 3
}

func dfs(s string, index, sum, prev int, path []int) bool {
    if index == len(s) {
        if len(path) >= 3 {
            res = path
        }
        return len(path) >= 3
    }
    value := 0
    for i := index; i < len(s); i++ {
        // 0开头不满足要求(当前i=index的时候,可以为0, 避免错过1+0=1的情况)
        if s[index] == '0' && i > index {
            break
        }
        value = value*10 + int(s[i]-'0')
        if len(path) >= 2 {
            if value < sum {
                continue
            }
            if value > sum {
                break
            }
        }
        if dfs(s, i+1, prev+value, value, append(path, value)) == true {
            return true
        }
    }
    return false
}

307.区域和检索-数组可修改(3)

  • 题目
给你一个数组 nums ,请你完成两类查询,其中一类查询要求更新数组下标对应的值,另一类查询要求返回数组中某个范围内元素的总和。
实现 NumArray 类:
NumArray(int[] nums) 用整数数组 nums 初始化对象
void update(int index, int val) 将 nums[index] 的值更新为 val
int sumRange(int left, int right) 返回子数组 nums[left, right] 的总和
(即,nums[left] + nums[left + 1], ..., nums[right])
示例:输入: ["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
输出: [null, 9, null, 8]
解释:
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // 返回 9 ,sum([1,3,5]) = 9
numArray.update(1, 2);   // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 8 ,sum([1,2,5]) = 8
提示:1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100
0 <= left <= right < nums.length
最多调用 3 * 104 次 update 和 sumRange 方法
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 分块处理 O(n) O(n)
02 线段树 O(nlog(n)) O(n)
03 树状数组 O(nlog(n)) O(n)
type NumArray struct {
    arr    []int // 原数组
    b      []int // 分块和
    length int   // 分块长度
}

func Constructor(nums []int) NumArray {
    n := len(nums)
    per := int(math.Sqrt(float64(n)))
    length := int(math.Ceil(float64(n) / float64(per)))
    b := make([]int, length)
    for i := 0; i < n; i++ {
        b[i/length] = b[i/length] + nums[i]
    }
    return NumArray{
        arr:    nums,
        b:      b,
        length: length,
    }
}

func (this *NumArray) Update(i int, val int) {
    index := i / this.length
    this.b[index] = this.b[index] - this.arr[i] + val
    this.arr[i] = val
}

func (this *NumArray) SumRange(i int, j int) int {
    res := 0
    a, b := i/this.length, j/this.length
    if a == b {
        for k := i; k <= j; k++ {
            res = res + this.arr[k]
        }
    } else {
        // 分3段
        for k := i; k <= (a+1)*this.length-1; k++ {
            res = res + this.arr[k]
        }
        for k := a + 1; k <= b-1; k++ {
            res = res + this.b[k]
        }
        for k := b * this.length; k <= j; k++ {
            res = res + this.arr[k]
        }
    }
    return res
}

# 2
type NumArray struct {
    origin []int // 原数组
    arr    []int // 线段树
    length int   // 长度
}

func Constructor(nums []int) NumArray {
    n := len(nums)
    arr := make([]int, 4*n+1)
    res := NumArray{
        origin: nums,
        arr:    arr,
        length: n,
    }
    for i := 0; i < n; i++ {
        res.UpdateArr(0, 1, res.length, i+1, nums[i]) // 从1开始,添加nums[i]
    }
    return res
}

func (this *NumArray) Update(index int, val int) {
    val, this.origin[index] = val-this.origin[index], val // 需要变更的大小
    this.UpdateArr(0, 1, this.length, index+1, val)       // 从1开始
}

func (this *NumArray) SumRange(left int, right int) int {
    return this.Query(0, 1, this.length, left+1, right+1) // 范围+1
}

func (this *NumArray) UpdateArr(id int, left, right, x int, value int) {
    if left > x || right < x {
        return
    }
    this.arr[id] = this.arr[id] + value
    if left == right {
        return
    }
    mid := left + (right-left)/2
    this.UpdateArr(2*id+1, left, mid, x, value)    // 左节点
    this.UpdateArr(2*id+2, mid+1, right, x, value) // 右节点
}

func (this *NumArray) Query(id int, left, right, queryLeft, queryRight int) int {
    if left > queryRight || right < queryLeft {
        return 0
    }
    if queryLeft <= left && right <= queryRight {
        return this.arr[id]
    }
    mid := left + (right-left)/2
    return this.Query(id*2+1, left, mid, queryLeft, queryRight) +
        this.Query(id*2+2, mid+1, right, queryLeft, queryRight)
}

# 3
type NumArray struct {
    origin []int // 原数组
    c      []int // 树状数组
    length int   // 长度
}

func Constructor(nums []int) NumArray {
    n := len(nums)
    arr := make([]int, n+1)
    res := NumArray{
        origin: nums,
        c:      arr,
        length: n,
    }
    // 单点修改
    for i := 0; i < n; i++ {
        res.UpData(i+1, nums[i]) // 注意下标,默认数组是从1开始
    }
    return res
}

func (this *NumArray) Update(index int, val int) {
    if index < 0 || index > this.length-1 {
        return
    }
    val, this.origin[index] = val-this.origin[index], val // 需要变更的大小
    this.UpData(index+1, val)
}

func (this *NumArray) SumRange(left int, right int) int {
    return this.GetSum(right+1) - this.GetSum(left)
}

func (this *NumArray) LowBit(x int) int {
    return x & (-x)
}

// 单点修改
func (this *NumArray) UpData(i, k int) { // 在i位置加上k
    for i <= this.length {
        this.c[i] = this.c[i] + k
        i = i + this.LowBit(i) // i = i + 2^k
    }
}

// 区间查询
func (this *NumArray) GetSum(i int) int {
    res := 0
    for i > 0 {
        res = res + this.c[i]
        i = i - this.LowBit(i)
    }
    return res
}

309.最佳买卖股票时机含冷冻期(2)

  • 题目
给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。​
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
    你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
    卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:输入: [1,2,3,0,2] 输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划-二维 O(n) O(n)
02 动态规划 O(n) O(1)
func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }
    n := len(prices)
    dp := make([][3]int, n)
    // 0 => 持有
    // 1 => 不持有,本日卖出,下一日冷冻期
    // 2 => 不持有,本日无卖出,下一日不是冷冻期
    dp[0][0] = -prices[0] // 第0天买入,亏损-price[0]
    for i := 1; i < n; i++ {
        dp[i][0] = max(dp[i-1][0], dp[i-1][2]-prices[i]) // 继续持有 or 可以操作,继续买入,导致今天持有股票
        dp[i][1] = dp[i-1][0] + prices[i]                // 卖出操作
        dp[i][2] = max(dp[i-1][1], dp[i-1][2])           // 昨天卖出,无股票,今天是冷冻期 or 昨天没股票,也不操作
    }
    return max(dp[n-1][1], dp[n-1][2]) // 最后一天操作,会导致利润变少,可以忽略
    // return max(dp[n-1][0], max(dp[n-1][1], dp[n-1][2]))
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 2
func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }
    n := len(prices)
    // a => 持有
    // b => 不持有,本日卖出,下一日冷冻期
    // c => 不持有,本日无卖出,下一日不是冷冻期
    var a, b, c int
    a = -prices[0] // 第0天买入,亏损-price[0]
    for i := 1; i < n; i++ {
        A := max(a, c-prices[i]) // 继续持有 or 可以操作,继续买入,导致今天持有股票
        B := a + prices[i]       // 卖出操作
        C := max(b, c)           // 昨天卖出,无股票,今天是冷冻期 or 昨天没股票,也不操作
        a, b, c = A, B, C
    }
    return max(b, c)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

310.最小高度树(1)

  • 题目
树是一个无向图,其中任何两个顶点只通过一条路径连接。 换句话说,一个任何没有简单环路的连通图都是一棵树。
给你一棵包含n个节点的数,标记为0到n - 1 。
给定数字n和一个有 n - 1 条无向边的 edges列表(每一个边都是一对标签),
其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。
可选择树中任何一个节点作为根。当选择节点 x 作为根节点时,设结果树的高度为 h 。
在所有可能的树中,具有最小高度的树(即,min(h))被称为 最小高度树 。
请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。
示例 1:输入:n = 4, edges = [[1,0],[1,2],[1,3]] 输出:[1]
解释:如图所示,当根是标签为 1 的节点时,树的高度是 1 ,这是唯一的最小高度树。
示例 2:输入:n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]] 输出:[3,4]
示例 3:输入:n = 1, edges = [] 输出:[0]
示例 4:输入:n = 2, edges = [[0,1]] 输出:[0,1]
提示:1 <= n <= 2 * 104
edges.length == n - 1
0 <= ai, bi < n
ai != bi
所有 (ai, bi) 互不相同
给定的输入 保证 是一棵树,并且 不会有重复的边
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 广度优先搜索 O(n) O(n)
func findMinHeightTrees(n int, edges [][]int) []int {
    if n == 1 {
        return []int{0}
    }
    if n == 2 {
        return []int{0, 1}
    }
    m := make(map[int][]int)
    degree := make([]int, n)
    for i := 0; i < len(edges); i++ {
        a, b := edges[i][0], edges[i][1]
        m[a] = append(m[a], b)
        m[b] = append(m[b], a)
        degree[a]++
        degree[b]++
    }
    // 从叶子节点开始遍历
    queue := make([]int, 0)
    for i := 0; i < n; i++ {
        if degree[i] == 1 {
            queue = append(queue, i)
        }
    }

    for n > 2 {
        total := len(queue)
        n = n - total
        for i := 0; i < total; i++ {
            node := queue[i]
            degree[node] = 0
            for j := 0; j < len(m[node]); j++ {
                temp := m[node][j]
                if degree[temp] > 0 {
                    degree[temp]--
                    if degree[temp] == 1 {
                        queue = append(queue, temp)
                    }
                }
            }
        }
        queue = queue[total:]
    }
    res := make([]int, 0)
    for i := 0; i < len(queue); i++ {
        res = append(res, queue[i])
    }
    return res
}

313.超级丑数(2)

  • 题目
编写一段程序来查找第 n 个超级丑数。
超级丑数是指其所有质因数都是长度为k的质数列表primes中的正整数。
示例:输入: n = 12, primes = [2,7,13,19] 输出: 32 
解释: 给定长度为 4 的质数列表 primes = [2,7,13,19],前 12 个超级丑数序列为:[1,2,4,7,8,13,14,16,19,26,28,32] 。
说明:1是任何给定primes的超级丑数。
给定primes中的数字以升序排列。
0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000 。
第n个超级丑数确保在 32 位有符整数范围内。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 O(nlog(n)) O(n)
02 数组 O(n^2) O(n)
func nthSuperUglyNumber(n int, primes []int) int {
    if n == 0 || n == 1 {
        return n
    }
    intHeap := &IntHeap{}
    heap.Init(intHeap)
    heap.Push(intHeap, 1)
    n--
    for n > 0 {
        x := heap.Pop(intHeap).(int)
        for intHeap.Len() > 0 && x == (*intHeap)[0] {
            heap.Pop(intHeap)
        }
        for i := 0; i < len(primes); i++ {
            heap.Push(intHeap, x*primes[i])
        }
        n--
    }
    return heap.Pop(intHeap).(int)
}

type IntHeap []int

func (h IntHeap) Len() int {
    return len(h)
}

func (h IntHeap) Less(i, j int) bool {
    return h[i] < h[j]
}

func (h IntHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    value := (*h)[len(*h)-1]
    *h = (*h)[:len(*h)-1]
    return value
}

# 2
func nthSuperUglyNumber(n int, primes []int) int {
    arr := make([]int, n)
    arr[0] = 1
    times := make([]int, len(primes))
    for i := 1; i < n; i++ {
        next := math.MaxInt32
        for j, value := range times {
            next = min(next, primes[j]*arr[value])
        }
        for j, value := range times {
            if primes[j]*arr[value] == next {
                times[j]++
            }
        }
        arr[i] = next
    }
    return arr[n-1]
}

func min(x, y int) int {
    if x > y {
        return y
    }
    return x
}

318.最大单词长度乘积(2)

  • 题目
给定一个字符串数组 words,找到 length(word[i]) * length(word[j]) 的最大值,
并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词,返回 0。
示例 1:输入: ["abcw","baz","foo","bar","xtfn","abcdef"] 输出: 16 
解释: 这两个单词为 "abcw", "xtfn"。
示例 2:输入: ["a","ab","abc","d","cd","bcd","abcd"] 输出: 4 
解释: 这两个单词为 "ab", "cd"。
示例 3:输入: ["a","aa","aaa","aaaa"] 输出: 0 
解释: 不存在这样的两个单词。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 内置函数 O(n^3) O(1)
02 位运算 O(n^2) O(n)
func maxProduct(words []string) int {
    res := 0
    for i := 0; i < len(words); i++ {
        for j := i + 1; j < len(words); j++ {
            if strings.ContainsAny(words[i], words[j]) == false && 
                res < len(words[i])*len(words[j]) {
                res = len(words[i]) * len(words[j])
            }
        }
    }
    return res
}

# 2
func maxProduct(words []string) int {
    res := 0
    arr := make([]int, len(words))
    for i := 0; i < len(words); i++ {
        for _, char := range words[i] {
            // 位或 只要有1,那么就是1
            arr[i] = arr[i] | 1<<uint(char-'a')
        }
    }
    for i := 0; i < len(arr); i++ {
        for j := i + 1; j < len(arr); j++ {
            if arr[i]&arr[j] == 0 && res < len(words[i])*len(words[j]) {
                res = len(words[i]) * len(words[j])
            }
        }
    }
    return res
}

319.灯泡开关(1)

  • 题目
初始时有 n 个灯泡关闭。 第 1 轮,你打开所有的灯泡。 第 2 轮,每两个灯泡你关闭一次。 
第 3 轮,每三个灯泡切换一次开关(如果关闭则开启,如果开启则关闭)。
第 i 轮,每 i 个灯泡切换一次开关。 对于第 n 轮,你只切换最后一个灯泡的开关。 
找出 n 轮后有多少个亮着的灯泡。
示例:输入: 3输出: 1 
解释: 初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 
你应该返回 1,因为只有一个灯泡还亮着。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 内置函数 O(log(n)) O(1)
func bulbSwitch(n int) int {
    // 第i个灯泡的反转次数等于它所有因子(包括1和i)的个数
    // 反转奇数次=>变成亮
    // 只有平方数才有奇数个因子
    return int(math.Sqrt(float64(n)))
}

322.零钱兑换(4)

  • 题目
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
如果没有任何一种硬币组合能组成总金额,返回 -1。
示例 1:输入: coins = [1, 2, 5], amount = 11 输出: 3 
解释: 11 = 5 + 5 + 1
示例 2:输入: coins = [2], amount = 3 输出: -1
说明:你可以认为每种硬币的数量是无限的。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^2) O(n)
02 动态规划 O(n^2) O(n)
03 深度优先搜索 O(n^k) O(n)
04 广度优先搜索 O(n) O(n)
func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := 1; i <= amount; i++ {
        dp[i] = -1
        for j := 0; j < len(coins); j++ {
            prev := i - coins[j]
            if i < coins[j] || dp[prev] == -1 {
                continue
            }
            if dp[i] == -1 || dp[i] > dp[prev]+1 {
                dp[i] = dp[prev] + 1
            }
        }
    }
    return dp[amount]
}

# 2
func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := 0; i <= amount; i++ {
        dp[i] = amount + 1
    }
    dp[0] = 0
    for i := 0; i < len(coins); i++ {
        for j := coins[i]; j < amount+1; j++ {
            dp[j] = min(dp[j], dp[j-coins[i]]+1)
        }
    }
    if dp[amount] == amount+1 {
        return -1
    }
    return dp[amount]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

# 3
var res int

func coinChange(coins []int, amount int) int {
    for i := 0; i < len(coins); i++ {
        for j := 0; j < len(coins)-1-i; j++ {
            if coins[j] < coins[j+1] {
                coins[j], coins[j+1] = coins[j+1], coins[j]
            }
        }
    }
    res = math.MaxInt32
    dfs(coins, amount, 0, 0)
    if res == math.MaxInt32 {
        return -1
    }
    return res
}

func dfs(coins []int, amount int, count int, level int) {
    if amount == 0 {
        res = min(res, count)
        return
    }
    if level == len(coins) {
        return
    }
    for i := amount / coins[level]; i >= 0 && i+count < res; i-- {
        dfs(coins, amount-i*coins[level], count+i, level+1)
    }
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

# 4
func coinChange(coins []int, amount int) int {
    if amount == 0 {
        return 0
    }
    res := 1
    sort.Ints(coins)
    list := make([]int, 0)
    list = append(list, amount)
    arr := make([]bool, amount+1)
    arr[amount] = true
    for len(list) > 0 {
        length := len(list)
        for i := 0; i < length; i++ {
            value := list[i]
            for j := 0; j < len(coins); j++ {
                next := value - coins[j]
                if next == 0 {
                    return res
                }
                if next < 0 {
                    break
                }
                if arr[next] == false {
                    list = append(list, next)
                    arr[next] = true
                }
            }
        }
        list = list[length:]
        res++
    }
    return -1
}

324.摆动排序II(2)

  • 题目
给定一个无序的数组 nums,将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。
示例 1:输入: nums = [1, 5, 1, 1, 6, 4] 输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6]
示例 2:输入: nums = [1, 3, 2, 2, 3, 1] 输出: 一个可能的答案是 [2, 3, 1, 3, 1, 2]
说明: 你可以假设所有输入都会得到有效的结果。
进阶:你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗?
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序 O(nlog(n)) O(n)
02 排序 O(nlog(n)) O(n)
func wiggleSort(nums []int) {
    arr := make([]int, len(nums))
    copy(arr, nums)
    sort.Slice(arr, func(i, j int) bool {
        return arr[i] > arr[j]
    })
    a := 1
    for i := 0; i < len(arr)/2; i++ {
        nums[a] = arr[i]
        a = a + 2
    }
    a = 0
    for i := len(arr) / 2; i < len(arr); i++ {
        nums[a] = arr[i]
        a = a + 2
    }
}

# 2
func wiggleSort(nums []int) {
    arr := make([]int, len(nums))
    copy(arr, nums)
    sort.Ints(arr)
    j := len(nums)
    k := (len(nums) + 1) / 2
    for i := 0; i < len(nums); i++ {
        if i%2 == 1 {
            j--
            nums[i] = arr[j]
        } else {
            k--
            nums[i] = arr[k]
        }
    }
}

328.奇偶链表(3)

  • 题目
给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。
请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。
示例 1:输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL
示例 2:输入: 2->1->3->5->6->4->7->NULL  输出: 2->3->6->7->1->5->4->NULL
说明:应当保持奇数节点和偶数节点的相对顺序。
    链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 双指针 O(n) O(1)
02 数组辅助 O(n) O(n)
03 双指针 O(n) O(1)
func oddEvenList(head *ListNode) *ListNode {
    odd := &ListNode{}
    even := &ListNode{}
    a := odd
    b := even
    count := 1
    for head != nil {
        if count%2 == 1 {
            a.Next = head
            a = head
        } else {
            b.Next = head
            b = head
        }
        count++
        head = head.Next
    }
    b.Next = nil
    a.Next = even.Next
    return odd.Next
}

# 2
func oddEvenList(head *ListNode) *ListNode {
    odd := make([]*ListNode, 0)
    even := make([]*ListNode, 0)
    count := 1
    for head != nil {
        if count%2 == 1 {
            odd = append(odd, head)
        } else {
            even = append(even, head)
        }
        count++
        head = head.Next
    }
    temp := &ListNode{}
    node := temp
    for i := 0; i < len(odd); i++ {
        node.Next = odd[i]
        node = node.Next
    }
    for i := 0; i < len(even); i++ {
        node.Next = even[i]
        node = node.Next
    }
    node.Next = nil
    return temp.Next
}

# 3
func oddEvenList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    temp := head.Next // 第一个偶数
    odd, even := head, temp
    for odd.Next != nil && even.Next != nil {
        odd.Next = even.Next
        odd = odd.Next
        even.Next = odd.Next
        even = even.Next
    }
    odd.Next = temp // 第一个偶数接入奇数尾部
    return head
}

331.验证二叉树的前序序列化(2)

  • 题目
序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时,我们可以记录下这个节点的值。
如果它是一个空节点,我们可以使用一个标记值记录,例如 #。
     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #
例如,上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#",其中 # 代表一个空节点。
给定一串以逗号分隔的序列,验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。
你可以认为输入格式总是有效的,例如它永远不会包含两个连续的逗号,比如 "1,,3" 。
示例 1:输入: "9,3,4,#,#,1,#,#,2,#,6,#,#" 输出: true
示例 2:输入: "1,#" 输出: false
示例 3:输入: "9,#,#,1" 输出: false
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(n)
02 栈辅助 O(n) O(n)
func isValidSerialization(preorder string) bool {
    arr := strings.Split(preorder, ",")
    slot := 1
    for i := 0; i < len(arr); i++ {
        slot--
        if slot < 0 {
            return false
        }
        if arr[i] != "#" {
            slot = slot + 2
        }
    }
    return slot == 0
}

# 2
func isValidSerialization(preorder string) bool {
    arr := strings.Split(preorder, ",")
    stack := make([]string, 0)
    for i := 0; i < len(arr); i++ {
        for len(stack) > 0 && stack[len(stack)-1] == "#" && arr[i] == "#" {
            stack = stack[:len(stack)-1]
            if len(stack) == 0 {
                return false
            }
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, arr[i])
    }
    return len(stack) == 1 && stack[0] == "#"
}

332.重新安排行程(1)

  • 题目
给定一个机票的字符串二维数组 [from, to],子数组中的两个成员分别表示飞机出发和降落的机场地点,
对该行程进行重新规划排序。所有这些机票都属于一个从 JFK(肯尼迪国际机场)出发的先生,
所以该行程必须从 JFK 开始。
提示:如果存在多种有效的行程,请你按字符自然排序返回最小的行程组合。
例如,行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小,排序更靠前
所有的机场都用三个大写字母表示(机场代码)。
假定所有机票至少存在一种合理的行程。
所有的机票必须都用一次 且 只能用一次。
示例 1:输入:[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出:["JFK", "MUC", "LHR", "SFO", "SJC"]
示例 2:输入:[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出:["JFK","ATL","JFK","SFO","ATL","SFO"]
解释:另一种有效的行程是["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 Hierholzer算法 O(nlog(n)) O(n)
var m map[string][]string
var res []string

func findItinerary(tickets [][]string) []string {
    res = make([]string, 0)
    m = make(map[string][]string)
    for i := 0; i < len(tickets); i++ {
        a, b := tickets[i][0], tickets[i][1]
        m[a] = append(m[a], b)
    }
    for _, v := range m {
        sort.Strings(v)
    }
    dfs("JFK")
    left, right := 0, len(res)-1
    for left < right {
        res[left], res[right] = res[right], res[left]
        left++
        right--
    }
    return res
}

func dfs(start string) {
    for len(m[start]) > 0 {
        node := m[start][0]
        m[start] = m[start][1:]
        dfs(node)
    }
    res = append(res, start)
}

334.递增的三元子序列(4)

  • 题目
给定一个未排序的数组,判断这个数组中是否存在长度为 3 的递增子序列。
数学表达式如下:
    如果存在这样的 i, j, k,  且满足 0 ≤ i < j < k ≤ n-1,
    使得 arr[i] < arr[j] < arr[k] ,返回 true ; 否则返回 false 。
说明: 要求算法的时间复杂度为 O(n),空间复杂度为 O(1) 。
示例 1:输入: [1,2,3,4,5] 输出: true
示例 2:输入: [5,4,3,2,1] 输出: false
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 数组辅助 O(n) O(n)
03 动态规划 O(n) O(n)
04 暴力法 O(n^3) O(1)
func increasingTriplet(nums []int) bool {
    a, b := math.MaxInt32, math.MaxInt32
    for i := 0; i < len(nums); i++ {
        if a >= nums[i] {
            a = nums[i]
        } else if b >= nums[i] {
            b = nums[i]
        } else {
            return true
        }
    }
    return false
}

# 2
func increasingTriplet(nums []int) bool {
    if len(nums) < 3 {
        return false
    }
    a := make([]int, len(nums))
    b := make([]int, len(nums))
    a[0] = nums[0]
    b[len(b)-1] = nums[len(nums)-1]
    for i := 1; i < len(nums); i++ {
        a[i] = min(a[i-1], nums[i])
    }
    for i := len(nums) - 2; i >= 0; i-- {
        b[i] = max(b[i+1], nums[i])
    }
    for i := 0; i < len(nums); i++ {
        if a[i] < nums[i] && nums[i] < b[i] {
            return true
        }
    }
    return false
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 3
func increasingTriplet(nums []int) bool {
    dp := make([]int, len(nums)+1)
    for i := 0; i < len(nums); i++ {
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
        if dp[i] >= 2 {
            return true
        }
    }
    return false
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 4
func increasingTriplet(nums []int) bool {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] >= nums[j] {
                continue
            }
            for k := j + 1; k < len(nums); k++ {
                if nums[j] < nums[k] {
                    return true
                }
            }
        }
    }
    return false
}

337.打家劫舍III(1)

  • 题目
在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。
这个地区只有一个入口,我们称之为“根”。 
除了“根”之外,每栋房子有且只有一个“父“房子与之相连。
一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 
如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。
计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。
示例 1:输入: [3,2,3,null,3,null,1]
     3
    / \
   2   3
    \   \ 
     3   1
输出: 7 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:输入: [3,4,5,1,3,null,1]
     3
    / \
   4   5
  / \   \ 
 1   3   1
输出: 9解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 递归 O(n) O(log(n))
func rob(root *TreeNode) int {
    a, b := dfs(root)
    return max(a, b)
}

func dfs(root *TreeNode) (int, int) {
    if root == nil {
        return 0, 0
    }
    leftA, leftB := dfs(root.Left)
    rightA, rightB := dfs(root.Right)
    a := root.Val + leftB + rightB               // A=>偷
    b := max(leftA, leftB) + max(rightA, rightB) // B=>不偷
    return a, b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

338.比特位计数(4)

  • 题目
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,
计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:输入: 2 输出: [0,1,1]
示例 2:输入: 5 输出: [0,1,1,2,1,2]
进阶:给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗?
要求算法的空间复杂度为O(n)。
你能进一步完善解法吗?要求在C++或任何其他语言中不使用任何内置函数
(如 C++ 中的 __builtin_popcount)来执行此操作。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 位运算 O(n) O(n)
02 动态规划 O(n) O(n)
03 暴力法 O(n) O(n)
04 内置函数 O(n) O(n)
func countBits(num int) []int {
    res := make([]int, num+1)
    for i := 1; i <= num; i++ {
        res[i] = res[i&(i-1)] + 1
    }
    return res
}

# 2
func countBits(num int) []int {
    res := make([]int, num+1)
    for i := 1; i <= num; i++ {
        if i%2 == 0 {
            res[i] = res[i/2]
        } else {
            res[i] = res[i-1] + 1
        }
    }
    return res
}

# 3
func countBits(num int) []int {
    res := make([]int, 0)
    for i := 0; i <= num; i++ {
        count := 0
        value := i
        for value != 0 {
            if value%2 == 1 {
                count++
            }
            value = value / 2
        }
        res = append(res, count)
    }
    return res
}

# 4
func countBits(num int) []int {
    res := make([]int, 0)
    for i := 0; i <= num; i++ {
        count := bits.OnesCount(uint(i))
        res = append(res, count)
    }
    return res
}

341.扁平化嵌套列表迭代器(2)

  • 题目
给你一个嵌套的整型列表。请你设计一个迭代器,使其能够遍历这个整型列表中的所有整数。
列表中的每一项或者为一个整数,或者是另一个列表。其中列表的元素也可能是整数或是其他列表。
示例 1:输入: [[1,1],2,[1,1]] 输出: [1,1,2,1,1]
解释: 通过重复调用 next 直到 hasNext 返回 false,next 返回的元素的顺序应该是: [1,1,2,1,1]。
示例 2:输入: [1,[4,[6]]] 输出: [1,4,6]
解释: 通过重复调用 next 直到 hasNext 返回 false,next 返回的元素的顺序应该是: [1,4,6]。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 队列辅助 O(n) O(n)
02 队列辅助 O(n) O(n)
type NestedIterator struct {
    arr []*NestedInteger
}

func Constructor(nestedList []*NestedInteger) *NestedIterator {
    return &NestedIterator{arr: nestedList}
}

func (this *NestedIterator) Next() int {
    value := this.arr[0]
    this.arr = this.arr[1:]
    return value.GetInteger()
}

func (this *NestedIterator) HasNext() bool {
    if len(this.arr) == 0 {
        return false
    }
    if this.arr[0].IsInteger() {
        return true
    }
    this.arr = append(this.arr[0].GetList(), this.arr[1:]...)
    return this.HasNext()
}

# 2
type NestedIterator struct {
    arr []int
}

func Constructor(nestedList []*NestedInteger) *NestedIterator {
    arr := getList(nestedList)
    return &NestedIterator{arr: arr}
}

func getList(nestedList []*NestedInteger) []int {
    res := make([]int, 0)
    for i := 0; i < len(nestedList); i++ {
        if nestedList[i].IsInteger() == true {
            res = append(res, nestedList[i].GetInteger())
        } else {
            res = append(res, getList(nestedList[i].GetList())...)
        }
    }
    return res
}
func (this *NestedIterator) Next() int {
    value := this.arr[0]
    this.arr = this.arr[1:]
    return value
}

func (this *NestedIterator) HasNext() bool {
    return len(this.arr) > 0
}

343.整数拆分(2)

  • 题目
给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:输入: 2 输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:输入: 10 输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^2) O(n)
02 贪心法 O(1) O(1)
func integerBreak(n int) int {
    if n < 2 {
        return 0
    }
    if n == 2 {
        return 1
    }
    if n == 3 {
        return 2
    }
    dp := make([]int, n+1)
    dp[0] = 0
    dp[1] = 1
    dp[2] = 2
    dp[3] = 3
    for i := 4; i <= n; i++ {
        max := 0
        for j := 1; j <= i/2; j++ {
            length := dp[j] * dp[i-j]
            if length > max {
                max = length
            }
            dp[i] = max
        }
    }
    return dp[n]
}

#
func integerBreak(n int) int {
    if n < 2 {
        return 0
    }
    if n == 2 {
        return 1
    }
    if n == 3 {
        return 2
    }
    timesOf3 := n / 3
    if n-timesOf3*3 == 1 {
        timesOf3 = timesOf3 - 1
    }
    timesOf2 := (n - timesOf3*3) / 2
    return int(math.Pow(float64(2), float64(timesOf2))) *
        int(math.Pow(float64(3), float64(timesOf3)))
}

347.前K个高频元素(3)

  • 题目
给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
示例 1:输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
示例 2:输入: nums = [1], k = 1 输出: [1]
提示:你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
    你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
    题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的。
    你可以按任意顺序返回答案。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(nlog(n)) O(n)
02 O(nlog(n)) O(n)
03 桶排序 O(n) O(n)
func topKFrequent(nums []int, k int) []int {
    m := make(map[int]int)
    for i := 0; i < len(nums); i++ {
        m[nums[i]]++
    }
    arr := make([][2]int, 0)
    for k, v := range m {
        arr = append(arr, [2]int{k, v})
    }
    sort.Slice(arr, func(i, j int) bool {
        return arr[i][1] > arr[j][1]
    })
    res := make([]int, 0)
    for i := 0; i < k; i++ {
        res = append(res, arr[i][0])
    }
    return res
}

# 2
func topKFrequent(nums []int, k int) []int {
    m := make(map[int]int)
    for i := 0; i < len(nums); i++ {
        m[nums[i]]++
    }
    var h IntHeap
    heap.Init(&h)
    for k, v := range m {
        heap.Push(&h, [2]int{k, v})
    }
    res := make([]int, 0)
    for h.Len() > 0 && k > 0 {
        k--
        node := heap.Pop(&h).([2]int)
        res = append(res, node[0])
    }
    return res
}

type IntHeap [][2]int

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i][1] > h[j][1] }
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.([2]int)) }
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

# 3
func topKFrequent(nums []int, k int) []int {
    m := make(map[int]int)
    for i := 0; i < len(nums); i++ {
        m[nums[i]]++
    }
    arr := make([][]int, len(nums)+1)
    temp := make(map[int][]int)
    for key, value := range m {
        temp[value] = append(temp[value], key)
        arr[value] = append(arr[value], key)
    }
    res := make([]int, 0)
    for i := len(arr) - 1; i >= 0; i-- {
        // 避免出现0=>x次的情况
        if _, ok := temp[i]; ok {
            for j := 0; j < len(arr[i]); j++ {
                k--
                if k < 0 {
                    break
                }
                res = append(res, arr[i][j])
            }
        }
    }
    return res
}

355.设计推特(2)

  • 题目
设计一个简化版的推特(Twitter),可以让用户实现发送推文,关注/取消关注其他用户,
能够看见关注人(包括自己)的最近十条推文。你的设计需要支持以下的几个功能:
postTweet(userId, tweetId): 创建一条新的推文
getNewsFeed(userId): 检索最近的十条推文。每个推文都必须是由此用户关注的人或者是用户自己发出的。
推文必须按照时间顺序由最近的开始排序。
follow(followerId, followeeId): 关注一个用户
unfollow(followerId, followeeId): 取消关注一个用户
示例:Twitter twitter = new Twitter();
// 用户1发送了一条新推文 (用户id = 1, 推文id = 5).
twitter.postTweet(1, 5);
// 用户1的获取推文应当返回一个列表,其中包含一个id为5的推文.
twitter.getNewsFeed(1);
// 用户1关注了用户2.
twitter.follow(1, 2);
// 用户2发送了一个新推文 (推文id = 6).
twitter.postTweet(2, 6);
// 用户1的获取推文应当返回一个列表,其中包含两个推文,id分别为 -> [6, 5].
// 推文id6应当在推文id5之前,因为它是在5之后发送的.
twitter.getNewsFeed(1);
// 用户1取消关注了用户2.
twitter.unfollow(1, 2);
// 用户1的获取推文应当返回一个列表,其中包含一个id为5的推文.
// 因为用户1已经不再关注用户2.
twitter.getNewsFeed(1);
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 暴力法 O(n^2) O(n)
02 O(nlog(n)) O(n)
type Twitter struct {
    data [][2]int
    m    map[int]map[int]int
}

func Constructor() Twitter {
    return Twitter{
        data: make([][2]int, 0),
        m:    make(map[int]map[int]int),
    }
}

func (this *Twitter) PostTweet(userId int, tweetId int) {
    this.data = append(this.data, [2]int{userId, tweetId})
}

func (this *Twitter) GetNewsFeed(userId int) []int {
    res := make([]int, 0)
    for i := len(this.data) - 1; i >= 0; i-- { // 遍历发表的列表
        id, tid := this.data[i][0], this.data[i][1]
        if id == userId || this.m[userId][id] > 0 {
            res = append(res, tid)
        }
        if len(res) == 10 {
            return res
        }
    }
    return res
}

func (this *Twitter) Follow(followerId int, followeeId int) {
    if this.m[followerId] == nil {
        this.m[followerId] = make(map[int]int)
    }
    this.m[followerId][followeeId] = 1
}

func (this *Twitter) Unfollow(followerId int, followeeId int) {
    if this.m[followerId] != nil {
        this.m[followerId][followeeId] = 0
    }
}

# 2
type Twitter struct {
    data  map[int][][2]int
    m     map[int]map[int]int
    count int
}

func Constructor() Twitter {
    return Twitter{
        data:  make(map[int][][2]int),
        m:     make(map[int]map[int]int),
        count: 0,
    }
}

func (this *Twitter) PostTweet(userId int, tweetId int) {
    this.data[userId] = append(this.data[userId], [2]int{this.count, tweetId})
    this.count++
}

func (this *Twitter) GetNewsFeed(userId int) []int {
    res := make([]int, 0)
    intHeap := make(IntHeap, 0)
    heap.Init(&intHeap)
    for i := len(this.data[userId]) - 1; i >= 0; i-- {
        a, b := this.data[userId][i][0], this.data[userId][i][1]
        if intHeap.Len() == 10 && intHeap[0][0] > a {
            break
        }
        heap.Push(&intHeap, [2]int{a, b})
        if intHeap.Len() > 10 {
            heap.Pop(&intHeap)
        }
    }
    for k, v := range this.m[userId] {
        if k == userId || v == 0 {
            continue
        }
        for i := len(this.data[k]) - 1; i >= 0; i-- {
            a, b := this.data[k][i][0], this.data[k][i][1]
            if intHeap.Len() == 10 && intHeap[0][0] > a {
                break
            }
            heap.Push(&intHeap, [2]int{a, b})
            if intHeap.Len() > 10 {
                heap.Pop(&intHeap)
            }
        }
    }
    for intHeap.Len() > 0 {
        node := heap.Pop(&intHeap).([2]int)
        res = append([]int{node[1]}, res...)
    }
    return res
}

func (this *Twitter) Follow(followerId int, followeeId int) {
    if this.m[followerId] == nil {
        this.m[followerId] = make(map[int]int)
    }
    this.m[followerId][followeeId] = 1
}

func (this *Twitter) Unfollow(followerId int, followeeId int) {
    if this.m[followerId] != nil {
        this.m[followerId][followeeId] = 0
    }
}

type IntHeap [][2]int

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i][0] < h[j][0] }
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.([2]int)) }
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

357.计算各个位数不同的数字个数(3)

  • 题目
给定一个非负整数 n,计算各位数字都不同的数字 x 的个数,其中 0 ≤ x < 10n。
示例:输入: 2 输出: 91 
解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外,在 [0,100) 区间内的所有数字。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n) O(n)
02 遍历 O(n) O(1)
03 回溯 O(n!) O(n)
func countNumbersWithUniqueDigits(n int) int {
    if n == 0 {
        return 1
    }
    dp := make([]int, n+10)
    dp[1] = 10
    prev := 9
    /*
        n = 1, 1+9
        n = 2, 1+9+9*9
        n = 3, 1+9+9*9+9*9*8
        n = 4, 1+9+9*9+9*9*8+9*9*8*7
    */
    for i := 2; i <= 10; i++ {
        dp[i] = dp[i-1] + 9*prev
        prev = prev * (10 - i)
    }
    if n >= 10 {
        return dp[10]
    }
    return dp[n]
}

# 2
func countNumbersWithUniqueDigits(n int) int {
    if n == 0 {
        return 1
    }
    res := 1
    prev := 1
    for i := 1; i <= 10 && i <= n; i++ {
        res = res + 9*prev
        prev = prev * (10 - i)
    }
    return res
}

# 3
func countNumbersWithUniqueDigits(n int) int {
    if n == 0 {
        return 1
    }
    return dfs(n, 0, make([]bool, 10))
}

func dfs(n, index int, visited []bool) int {
    if index == n {
        return 0
    }
    res := 0
    for i := 0; i < 10; i++ {
        if n >= 2 && index == 1 && i == 0 {
            continue
        }
        if visited[i] == true {
            continue
        }
        visited[i] = true
        res = res + dfs(n, index+1, visited) + 1
        visited[i] = false
    }
    return res
}

365.水壶问题(3)

  • 题目
有两个容量分别为 x升 和 y升 的水壶以及无限多的水。
请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水?
如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升 水。
你允许:
    装满任意一个水壶
    清空任意一个水壶
    从一个水壶向另外一个水壶倒水,直到装满或者倒空
示例 1: (From the famous "Die Hard" example)
输入: x = 3, y = 5, z = 4  输出: True
示例 2:输入: x = 2, y = 6, z = 5 输出: False
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 数学 O(log(n)) O(1)
02 递归 O(log(n)) O(log(n))
03 广度优先搜索 O(n^2) O(n^2)
// ax+by=z
func canMeasureWater(x int, y int, z int) bool {
    if x > y {
        x, y = y, x
    }
    if x+y < z {
        return false
    }
    if x == 0 || y == 0 {
        return z == 0 || x+y == z
    }
    return z%gcd(x, y) == 0
}

func gcd(a, b int) int {
    if a%b == 0 {
        return b
    }
    return gcd(b, a%b)
}

# 2
func canMeasureWater(x int, y int, z int) bool {
    if z == 0 || z == x+y {
        return true
    } else if z > x+y || y == 0 {
        return false
    }
    return canMeasureWater(y, x%y, z%y)
}

# 3
func canMeasureWater(x int, y int, z int) bool {
    if x+y < z {
        return false
    }
    queue := make([][2]int, 0)
    queue = append(queue, [2]int{0, 0})
    m := make(map[[2]int]bool)
    for len(queue) > 0 {
        a, b := queue[0][0], queue[0][1]
        queue = queue[1:]
        if m[[2]int{a, b}] == true {
            continue
        }
        m[[2]int{a, b}] = true
        if a == z || b == z || a+b == z {
            return true
        }
        // +x
        c, d := x, b
        queue = append(queue, [2]int{c, d})
        // +y
        c, d = a, y
        queue = append(queue, [2]int{c, d})
        // -x
        c, d = 0, b
        queue = append(queue, [2]int{c, d})
        // -y
        c, d = a, 0
        queue = append(queue, [2]int{c, d})
        // x->y
        if a > y-b {
            c, d = a+b-y, y
            queue = append(queue, [2]int{c, d})
        } else {
            c, d = 0, a+b
            queue = append(queue, [2]int{c, d})
        }
        // y->x
        if b > x-a {
            c, d = x, a+b-x
            queue = append(queue, [2]int{c, d})
        } else {
            c, d = a+b, 0
            queue = append(queue, [2]int{c, d})
        }
    }
    return false
}

368.最大整除子集(1)

  • 题目
给出一个由无重复的正整数组成的集合,找出其中最大的整除子集,子集中任意一对 (Si,Sj) 都要满足:
Si % Sj = 0 或 Sj % Si = 0。
如果有多个目标子集,返回其中任何一个均可。
示例 1:输入: [1,2,3] 输出: [1,2] (当然, [1,3] 也正确)
示例 2:输入: [1,2,4,8] 输出: [1,2,4,8]
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^2) O(n^2)
func largestDivisibleSubset(nums []int) []int {
    n := len(nums)
    if n < 2 {
        return nums
    }
    sort.Ints(nums)
    dp := make([][]int, n)
    dp[0] = append(dp[0], nums[0])
    resLength := 0
    index := 0
    for i := 1; i < n; i++ {
        maxLength := 0
        arr := make([]int, 0)
        for j := 0; j < i; j++ {
            // 可除以整除集合中的最大值=>属于该集合
            if nums[i]%nums[j] == 0 && len(dp[j]) >= maxLength {
                maxLength = len(dp[j])
                arr = dp[j]
            }
        }
        dp[i] = append(dp[i], append(arr, nums[i])...)
        if len(dp[i]) > resLength {
            resLength = len(dp[i])
            index = i
        }
    }
    return dp[index]
}

372.超级次方(2)

  • 题目
你的任务是计算ab对1337 取模,a 是一个正整数,b 是一个非常大的正整数且会以数组形式给出。
示例 1:输入:a = 2, b = [3] 输出:8
示例 2:输入:a = 2, b = [1,0] 输出:1024
示例 3:输入:a = 1, b = [4,3,3,8,5,2] 输出:1
示例 4:输入:a = 2147483647, b = [2,0,0] 输出:1198
提示:1 <= a <= 231 - 1
1 <= b.length <= 2000
0 <= b[i] <= 9
b 不含前导 0
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 快速幂 O(nlog(n)) O(n)
02 快速幂 O(nlog(n)) O(1)
var mod int = 1337

func superPow(a int, b []int) int {
    a = a % mod
    if len(b) == 0 {
        return 1
    }
    x := mypow(a, b[len(b)-1])
    y := mypow(superPow(a, b[:len(b)-1]), 10)
    return x * y % mod
}

// a^n
func mypow(a int, n int) int {
    res := 1
    for n > 0 {
        if n%2 == 1 {
            res = res * a % mod
        }
        a = a * a % mod
        n = n / 2
    }
    return res
}

# 2
var mod int = 1337

func superPow(a int, b []int) int {
    a = a % mod
    if len(b) == 0 {
        return 1
    }
    res := 1
    for i := 0; i < len(b); i++ {
        res = mypow(res, 10) * mypow(a, b[i]) % mod
    }
    return res
}

// a^n
func mypow(a int, n int) int {
    res := 1
    for n > 0 {
        if n%2 == 1 {
            res = res * a % mod
        }
        a = a * a % mod
        n = n / 2
    }
    return res
}

373.查找和最小的K对数字(2)

  • 题目
给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。
定义一对值(u,v),其中第一个元素来自nums1,第二个元素来自 nums2。
找到和最小的 k 对数字(u1,v1), (u2,v2) ... (uk,vk)。
示例 1:输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3 输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数:
     [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
示例 2:输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2 输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数:
    [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
示例 3:输入: nums1 = [1,2], nums2 = [3], k = 3  输出: [1,3],[2,3]
解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 O(nlog(n)) O(n)
02 排序 O(nlog(n)) O(n^2)
func kSmallestPairs(nums1 []int, nums2 []int, k int) [][]int {
    Heap := &NodeHeap{}
    heap.Init(Heap)
    for i := 0; i < len(nums1); i++ {
        for j := 0; j < len(nums2); j++ {
            heap.Push(Heap, Node{
                i: nums1[i],
                j: nums2[j],
            })
            if Heap.Len() > k {
                heap.Pop(Heap)
            }
        }
    }
    res := make([][]int, 0)
    for Heap.Len() > 0 {
        node := heap.Pop(Heap).(Node)
        res = append(res, []int{node.i, node.j})
    }
    return res
}

type Node struct {
    i int
    j int
}

type NodeHeap []Node

func (h NodeHeap) Len() int {
    return len(h)
}

func (h NodeHeap) Less(i, j int) bool {
    return h[i].i+h[i].j > h[j].i+h[j].j
}

func (h NodeHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *NodeHeap) Push(x interface{}) {
    *h = append(*h, x.(Node))
}

func (h *NodeHeap) Pop() interface{} {
    value := (*h)[len(*h)-1]
    *h = (*h)[:len(*h)-1]
    return value
}

# 2
func kSmallestPairs(nums1 []int, nums2 []int, k int) [][]int {
    arr := make([][]int, 0)
    for i := 0; i < len(nums1); i++ {
        for j := 0; j < len(nums2); j++ {
            arr = append(arr, []int{nums1[i], nums2[j]})
        }
    }
    sort.Slice(arr, func(i, j int) bool {
        return arr[i][0]+arr[i][1] < arr[j][0]+arr[j][1]
    })
    if len(arr) < k {
        return arr
    }
    return arr[:k]
}

375.猜数字大小II(3)

  • 题目
我们正在玩一个猜数游戏,游戏规则如下:
我从1到 n 之间选择一个数字,你来猜我选了哪个数字。
每次你猜错了,我都会告诉你,我选的数字比你的大了或者小了。
然而,当你猜了数字 x 并且猜错了的时候,你需要支付金额为 x 的现金。
直到你猜到我选的数字,你才算赢得了这个游戏。
示例:n = 10, 我选择了8.
第一轮: 你猜我选择的数字是5,我会告诉你,我的数字更大一些,然后你需要支付5块。
第二轮: 你猜是7,我告诉你,我的数字更大一些,你支付7块。
第三轮: 你猜是9,我告诉你,我的数字更小一些,你支付9块。
游戏结束。8 就是我选的数字。
你最终要支付 5 + 7 + 9 = 21 块钱。
给定n ≥ 1,计算你至少需要拥有多少现金才能确保你能赢得这个游戏。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^3) O(n^2)
02 动态规划 O(n^3) O(n^2)
03 递归 O(n^3) O(n^2)
func getMoneyAmount(n int) int {
    dp := make([][]int, n+1) // 表示从[i,j]之间选择一个数字来猜,你确保获胜所需要的最少现金
    for i := 0; i <= n; i++ {
        dp[i] = make([]int, n+1)
    }
    for i := n; i >= 1; i-- {
        for j := i + 1; j <= n; j++ {
            minValue := math.MaxInt32
            for k := i; k < j; k++ { // 可以选择[i-j],其中最小值
                minValue = min(minValue, max(dp[i][k-1], dp[k+1][j])+k)
            }
            dp[i][j] = minValue
        }
    }
    return dp[1][n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

# 2
func getMoneyAmount(n int) int {
    dp := make([][]int, n+1) // 表示从[i,j]之间选择一个数字来猜,你确保获胜所需要的最少现金
    for i := 0; i <= n; i++ {
        dp[i] = make([]int, n+1)
    }
    for i := 2; i <= n; i++ {
        for j := 1; j+i-1 <= n; j++ {
            minValue := math.MaxInt32
            for k := j; k < i+j-1; k++ { // 可以选择[i-j],其中最小值
                minValue = min(minValue, max(dp[j][k-1], dp[k+1][i+j-1])+k)
            }
            dp[j][i+j-1] = minValue
        }
    }
    return dp[1][n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

# 3
var dp [][]int

func getMoneyAmount(n int) int {
    dp = make([][]int, n+1) // 表示从[i,j]之间选择一个数字来猜,你确保获胜所需要的最少现金
    for i := 0; i <= n; i++ {
        dp[i] = make([]int, n+1)
    }
    return dfs(1, n)
}

func dfs(start, end int) int {
    if start >= end {
        return 0
    }
    if dp[start][end] > 0 {
        return dp[start][end]
    }
    minValue := math.MaxInt32
    for i := start; i <= end; i++ {
        res := i + max(dfs(i+1, end), dfs(start, i-1))
        minValue = min(minValue, res)
    }
    dp[start][end] = minValue
    return minValue
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

376.摆动序列(3)

  • 题目
如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。
第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。
例如,[1,7,4,9,2,5] 是一个摆动序列,因为差值 (6,-3,5,-7,3)是正负交替出现的。
相反, [1,4,7,2,5]和[1,7,4,5,5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,
第二个序列是因为它的最后一个差值为零。
给定一个整数序列,返回作为摆动序列的最长子序列的长度。 
通过从原始序列中删除一些(也可以不删除)元素来获得子序列,剩下的元素保持其原始顺序。
示例 1:输入: [1,7,4,9,2,5] 输出: 6 
解释: 整个序列均为摆动序列。
示例 2:输入: [1,17,5,10,13,15,10,5,16,8] 输出: 7
解释: 这个序列包含几个长度为 7 摆动序列,其中一个可为[1,17,10,13,10,16,8]。
示例 3:输入: [1,2,3,4,5,6,7,8,9] 输出: 2
进阶:你能否用O(n) 时间复杂度完成此题?
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n) O(n)
02 动态规划 O(n) O(1)
03 贪心 O(n) O(1)
func wiggleMaxLength(nums []int) int {
    n := len(nums)
    if n < 2 {
        return n
    }
    up := make([]int, n)   // 以前i个元素中的某一个为结尾的最长的上升摆动序列的长度
    down := make([]int, n) // 以前i个元素中的某一个为结尾的最长的下降摆动序列的长度。
    up[0] = 1
    down[0] = 1
    for i := 1; i < n; i++ {
        if nums[i-1] < nums[i] { // 递增
            up[i] = max(up[i-1], down[i-1]+1)
            down[i] = down[i-1]
        } else if nums[i-1] > nums[i] { // 递减
            up[i] = up[i-1]
            down[i] = max(up[i-1]+1, down[i-1])
        } else {
            up[i] = up[i-1]
            down[i] = down[i-1]
        }
    }
    return max(up[n-1], down[n-1])
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 2
func wiggleMaxLength(nums []int) int {
    n := len(nums)
    if n < 2 {
        return n
    }
    up := 1   // 以前i个元素中的某一个为结尾的最长的上升摆动序列的长度
    down := 1 // 以前i个元素中的某一个为结尾的最长的下降摆动序列的长度。
    for i := 1; i < n; i++ {
        if nums[i-1] < nums[i] { // 递增
            up = down + 1
        } else if nums[i-1] > nums[i] { // 递减

            down = up + 1
        }
    }
    return max(up, down)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 3
func wiggleMaxLength(nums []int) int {
    n := len(nums)
    if n < 2 {
        return n
    }
    res := 1
    diff := nums[1] - nums[0]
    if diff != 0 {
        res = 2
    }
    for i := 2; i < n; i++ {
        newDiff := nums[i] - nums[i-1]
        if (diff >= 0 && newDiff < 0) ||
            (diff <= 0 && newDiff > 0) {
            res++
            diff = newDiff
        }
    }
    return res
}

377.组合总和Ⅳ(2)

  • 题目
给定一个由正整数组成且不存在重复数字的数组,找出和为给定目标正整数的组合的个数。
示例:nums = [1, 2, 3] target = 4
所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意,顺序不同的序列被视作不同的组合。
因此输出为 7。
进阶:如果给定的数组中含有负数会怎么样?
问题会产生什么变化?
我们需要在题目中添加什么限制来允许负数的出现?
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^2) O(n)
02 递归 O(n^2) O(n)
func combinationSum4(nums []int, target int) int {
    // 等价于:
    // 假设你正在爬楼梯。需要n阶你才能到达楼顶。
    // 每次你可以爬num(num in nums)级台阶。
    // 你有多少种不同的方法可以爬到楼顶呢?
    dp := make([]int, target+1)
    dp[0] = 1 // 爬0楼1种解法
    for i := 1; i <= target; i++ {
        for j := 0; j < len(nums); j++ {
            if i-nums[j] >= 0 {
                dp[i] = dp[i] + dp[i-nums[j]]
            }
        }
    }
    return dp[target]
}

# 2
var m map[int]int

func combinationSum4(nums []int, target int) int {
    m = make(map[int]int)
    res := dfs(nums, target)
    if res == -1 {
        return 0
    }
    return res
}

func dfs(nums []int, target int) int {
    if target == 0 {
        return 1
    }
    if target < 0 {
        return -1
    }
    if v, ok := m[target]; ok {
        return v
    }
    temp := 0
    for i := 0; i < len(nums); i++ {
        if dfs(nums, target-nums[i]) != -1 {
            temp = temp + dfs(nums, target-nums[i])
        }
    }
    m[target] = temp
    return temp
}

378.有序矩阵中第K小的元素(3)

  • 题目
给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。
请注意,它是排序后的第 k 小元素,而不是第 k 个不同的元素。
示例:matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,
返回 13。
提示:你可以假设 k 的值永远是有效的,1 ≤ k ≤ n2 。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 数组辅助排序 O(n^2log(n)) O(n^2)
02 二分查找 O(nlog(n)) O(1)
03 O(n^2log(n)) O(n^2)
func kthSmallest(matrix [][]int, k int) int {
    res := make([]int, 0)
    for i := 0; i < len(matrix); i++ {
        for j := 0; j < len(matrix[i]); j++ {
            res = append(res, matrix[i][j])
        }
    }
    sort.Ints(res)
    return res[k-1]
}

# 2
func kthSmallest(matrix [][]int, k int) int {
    n := len(matrix)
    left, right := matrix[0][0], matrix[n-1][n-1]
    for left < right {
        mid := left + (right-left)/2
        if check(matrix, mid, k, n) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

// 左下角查找
func check(matrix [][]int, mid, k, n int) bool {
    i := n - 1
    j := 0
    num := 0
    for i >= 0 && j < n {
        if matrix[i][j] <= mid {
            // 往右,说明左边一列都小于mid
            num = num + i + 1
            j++
        } else {
            // 往上
            i--
        }
    }
    return num >= k
}

# 3
func kthSmallest(matrix [][]int, k int) int {
    var h IntHeap
    heap.Init(&h)
    for i := 0; i < len(matrix); i++ {
        for j := 0; j < len(matrix[i]); j++ {
            heap.Push(&h, matrix[i][j])
        }
    }
    for h.Len() > 0 && k > 0 {
        k--
        res := heap.Pop(&h).(int)
        if k == 0 {
            return res
        }
    }
    return 0
}

type IntHeap []int

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

380.常数时间插入、删除和获取随机元素(2)

  • 题目
设计一个支持在平均 时间复杂度 O(1) 下,执行以下操作的数据结构。
    insert(val):当元素 val 不存在时,向集合中插入该项。
    remove(val):元素 val 存在时,从集合中移除该项。
    getRandom:随机返回现有集合中的一项。每个元素应该有相同的概率被返回。
示例 :
// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();
// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);
// 返回 false ,表示集合中不存在 2 。
randomSet.remove(2);
// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);
// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();
// 从集合中移除 1 ,返回 true 。集合现在包含 [2] 。
randomSet.remove(1);
// 2 已在集合中,所以返回 false 。
randomSet.insert(2);
// 由于 2 是集合中唯一的数字,getRandom 总是返回 2 。
randomSet.getRandom();
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希表+数组 O(1) O(n)
02 哈希表 O(n) O(n)
type RandomizedSet struct {
    m   map[int]int
    arr []int
}

func Constructor() RandomizedSet {
    return RandomizedSet{
        m:   make(map[int]int),
        arr: make([]int, 0),
    }
}

func (this *RandomizedSet) Insert(val int) bool {
    if _, ok := this.m[val]; ok {
        return false
    }
    this.arr = append(this.arr, val)
    this.m[val] = len(this.arr) - 1
    return true
}

func (this *RandomizedSet) Remove(val int) bool {
    if _, ok := this.m[val]; !ok {
        return false
    }
    index := this.m[val]
    this.arr[index], this.arr[len(this.arr)-1] = this.arr[len(this.arr)-1], this.arr[index]
    this.m[this.arr[index]] = index
    this.arr = this.arr[:len(this.arr)-1]
    delete(this.m, val)
    return true
}

func (this *RandomizedSet) GetRandom() int {
    if len(this.arr) == 0 {
        return -1
    }
    index := rand.Intn(len(this.arr))
    return this.arr[index]
}

# 2
type RandomizedSet struct {
    m map[int]bool
}

func Constructor() RandomizedSet {
    return RandomizedSet{
        m: make(map[int]bool),
    }
}

func (this *RandomizedSet) Insert(val int) bool {
    if _, ok := this.m[val]; ok {
        return false
    }
    this.m[val] = true
    return true
}

func (this *RandomizedSet) Remove(val int) bool {
    if _, ok := this.m[val]; !ok {
        return false
    }
    delete(this.m, val)
    return true
}

func (this *RandomizedSet) GetRandom() int {
    if len(this.m) == 0 {
        return -1
    }
    index := rand.Intn(len(this.m))
    res := -1
    for res = range this.m {
        index--
        if index == -1 {
            break
        }
    }
    return res
}

382.链表随机节点(1)

  • 题目
给定一个单链表,随机选择链表的一个节点,并返回相应的节点值。保证每个节点被选的概率一样。
进阶:如果链表十分大且长度未知,如何解决这个问题?你能否使用常数级空间复杂度实现?
示例:// 初始化一个单链表 [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);
// getRandom()方法应随机返回1,2,3中的一个,保证每个元素被返回的概率相等。
solution.getRandom();
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 蓄水池抽样 O(n) O(1)
type Solution struct {
    head *ListNode
    r    *rand.Rand
}

func Constructor(head *ListNode) Solution {
    return Solution{
        head: head,
        r:    rand.New(rand.NewSource(time.Now().Unix())),
    }
}

func (this *Solution) GetRandom() int {
    res := this.head.Val
    cur := this.head
    count := 1
    for cur != nil {
        if this.r.Intn(count)+1 == count {
            res = cur.Val
        }
        count++
        cur = cur.Next
    }
    return res
}

384.打乱数组(2)

  • 题目
打乱一个没有重复元素的数组。
示例:
// 以数字集合 1, 2 和 3 初始化数组。
int[] nums = {1,2,3};
Solution solution = new Solution(nums);
// 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。
solution.shuffle();
// 重设数组到它的初始状态[1,2,3]。
solution.reset();
// 随机返回数组[1,2,3]打乱后的结果。
solution.shuffle();
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 内置函数 O(n^2) O(n)
02 内置函数 O(n^2) O(n)
type Solution struct {
    nums []int
}

func Constructor(nums []int) Solution {
    return Solution{nums: nums}
}

func (this *Solution) Reset() []int {
    return this.nums
}

func (this *Solution) Shuffle() []int {
    arr := make([]int, len(this.nums))
    copy(arr, this.nums)
    rand.Shuffle(len(arr), func(i, j int) {
        arr[i], arr[j] = arr[j], arr[i]
    })
    return arr
}

#
type Solution struct {
    nums []int
}

func Constructor(nums []int) Solution {
    return Solution{nums: nums}
}

func (this *Solution) Reset() []int {
    return this.nums
}

func (this *Solution) Shuffle() []int {
    arr := make([]int, len(this.nums))
    copy(arr, this.nums)
    res := make([]int, len(this.nums))
    for i := 0; i < len(res); i++{
        j := rand.Intn(len(arr))
        res[i] = arr[j]
        arr = append(arr[:j], arr[j+1:]...)
    }
    return res
}

385.迷你语法分析器(1)

  • 题目
给定一个用字符串表示的整数的嵌套列表,实现一个解析它的语法分析器。
列表中的每个元素只可能是整数或整数嵌套列表
提示:你可以假定这些字符串都是格式良好的:
字符串非空
字符串不包含空格
字符串只包含数字0-9、[、-、,、]
示例 1:给定 s = "324",
你应该返回一个 NestedInteger 对象,其中只包含整数值 324。
示例 2:给定 s = "[123,[456,[789]]]",
返回一个 NestedInteger 对象包含一个有两个元素的嵌套列表:
1. 一个 integer 包含值 123
2. 一个包含两个元素的嵌套列表:
    i.  一个 integer 包含值 456
    ii. 一个包含一个元素的嵌套列表
         a. 一个 integer 包含值 789
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 栈辅助 O(n) O(n)
func deserialize(s string) *NestedInteger {
    if s[0] != '[' {
        res := &NestedInteger{}
        num, _ := strconv.Atoi(s)
        res.SetInteger(num)
        return res
    }
    stack := make([]NestedInteger, 0)
    str := ""
    for i := 0; i < len(s); i++ {
        if s[i] == '[' {
            stack = append(stack, NestedInteger{})
        } else if s[i] == ']' {
            if len(str) > 0 {
                node := NestedInteger{}
                num, _ := strconv.Atoi(str)
                node.SetInteger(num)
                stack[len(stack)-1].Add(node)
            }
            str = ""
            if len(stack) > 1 { // 出栈
                last := stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                stack[len(stack)-1].Add(last)
            }
        } else if s[i] == ',' {
            if len(str) > 0 {
                node := NestedInteger{}
                num, _ := strconv.Atoi(str)
                node.SetInteger(num)
                stack[len(stack)-1].Add(node)
            }
            str = ""
        } else {
            str = str + string(s[i])
        }
    }
    return &stack[len(stack)-1]
}

386.字典序排数(2)

  • 题目
给定一个整数n, 返回从1到n的字典顺序。
例如,给定 n =1 3,返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。
请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据n小于等于5,000,000。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(n)
02 递归 O(n) O(n)
func lexicalOrder(n int) []int {
    res := make([]int, 0)
    num := 1
    for {
        if num <= n {
            res = append(res, num)
            num = num * 10
        } else {
            num = num / 10
            for num%10 == 9 {
                num = num / 10
            }
            if num == 0 {
                break
            }
            num++
        }
    }
    return res
}

# 2
var res []int

func lexicalOrder(n int) []int {
    res = make([]int, 0)
    for i := 1; i <= 9; i++ {
        dfs(n, i)
    }
    return res
}

func dfs(n, start int) {
    if start > n {
        return
    }
    // N叉树前序遍历
    res = append(res, start)
    for i := 0; i <= 9; i++ {
        dfs(n, start*10+i)
    }
}

388.文件的最长绝对路径(1)

  • 题目
假设文件系统如下图所示:
这里将 dir 作为根目录中的唯一目录。dir 包含两个子目录 subdir1 和 subdir2 。
subdir1 包含文件 file1.ext 和子目录 subsubdir1;
subdir2 包含子目录 subsubdir2,该子目录下包含文件 file2.ext 。
在文本格式中,如下所示(⟶表示制表符):
dir
⟶ subdir1
⟶ ⟶ file1.ext
⟶ ⟶ subsubdir1
⟶ subdir2
⟶ ⟶ subsubdir2
⟶ ⟶ ⟶ file2.ext
如果是代码表示,上面的文件系统可以写为 "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n
\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" 。'\n' 和 '\t' 分别是换行符和制表符。
文件系统中的每个文件和文件夹都有一个唯一的 绝对路径 ,即必须打开才能到达文件/目录所在位置的目录顺序,
所有路径用 '/' 连接。上面例子中,
指向 file2.ext 的绝对路径是 "dir/subdir2/subsubdir2/file2.ext" 。
每个目录名由字母、数字和/或空格组成,每个文件名遵循 name.extension 的格式,
其中名称和扩展名由字母、数字和/或空格组成。
给定一个以上述格式表示文件系统的字符串 input ,返回文件系统中 指向文件的最长绝对路径 的长度。 
如果系统中没有文件,返回0。
示例 1:输入:input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" 输出:20
解释:只有一个文件,绝对路径为 "dir/subdir2/file.ext" ,路径长度 20
路径 "dir/subdir1" 不含任何文件
示例 2:输入:input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2
\n\t\tsubsubdir2\n\t\t\tfile2.ext"
输出:32
解释:存在两个文件:
"dir/subdir1/file1.ext" ,路径长度 21
"dir/subdir2/subsubdir2/file2.ext" ,路径长度 32
返回 32 ,因为这是最长的路径
示例 3:输入:input = "a" 输出:0
解释:不存在任何文件
示例 4:输入:input = "file1.txt\nfile2.txt\nlongfile.txt" 输出:12
解释:根目录下有 3 个文件。
因为根目录中任何东西的绝对路径只是名称本身,所以答案是 "longfile.txt" ,路径长度为 12
提示:1 <= input.length <= 104
input 可能包含小写或大写的英文字母,一个换行符 '\n',
一个指表符 '\t',一个点 '.',一个空格 ' ',和数字。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(n)
func lengthLongestPath(input string) int {
    res := 0
    arr := strings.Split(input, "\n")
    temp := make([]string, 0)
    for i := 0; i < len(arr); i++ {
        str := arr[i]
        count := strings.Count(arr[i], "\t")
        str = str[count:] // 去除\t后的字符串
        if count < len(temp) { // 多个\t的个数小于当前层级,需要去除
            temp = temp[:count]
        }
        if strings.Contains(str, ".") {
            length := len(str) + getLength(temp) + len(temp) // len(temp)个分隔符
            if length > res {
                res = length
            }
        } else {
            temp = append(temp, str)
        }
    }
    return res
}

func getLength(arr []string) int {
    res := 0
    for i := 0; i < len(arr); i++ {
        res = res + len(arr[i])
    }
    return res
}

390.消除游戏(2)

  • 题目
给定一个从1 到 n 排序的整数列表。
首先,从左到右,从第一个数字开始,每隔一个数字进行删除,直到列表的末尾。
第二步,在剩下的数字中,从右到左,从倒数第一个数字开始,每隔一个数字进行删除,直到列表开头。
我们不断重复这两步,从左到右和从右到左交替进行,直到只剩下一个数字。
返回长度为 n 的列表中,最后剩下的数字。
示例:输入:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6
输出:6
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 递归 O(log(n)) O(log(n))
02 递归 O(log(n)) O(log(n))
func lastRemaining(n int) int {
    if n == 1 {
        return 1
    }
    // f(2k)/f(2k+1) = 2(k+1-f(k)),最后奇数2k+1不影响结果
    return 2 * (n/2 + 1 - lastRemaining(n/2))
}

# 2
func lastRemaining(n int) int {
    return dfs(n, 1)
}

func dfs(n int, isLeftToRight int) int {
    if n == 1 {
        return 1
    }
    if n%2 == 1 { // 奇数
        return 2 * dfs(n/2, 1-isLeftToRight)
    }
    if isLeftToRight == 1 { // 偶数从左往右
        return 2 * dfs(n/2, 1-isLeftToRight)
    }
    // 偶数从右往左,如1,2,3,4,5,6,7,8 => 1,3,5,7
    return 2*dfs(n/2, 1-isLeftToRight) - 1
}

393.UTF-8编码验证(2)

  • 题目
UTF-8 中的一个字符可能的长度为 1 到 4 字节,遵循以下的规则:
对于 1 字节的字符,字节的第一位设为0,后面7位为这个符号的unicode码。
对于 n 字节的字符 (n > 1),第一个字节的前 n 位都设为1,第 n+1 位设为0,后面字节的前两位一律设为10。
剩下的没有提及的二进制位,全部为这个符号的unicode码。
这是 UTF-8 编码的工作方式:
   Char. number range  |        UTF-8 octet sequence
      (hexadecimal)    |              (binary)
   --------------------+---------------------------------------------
   0000 0000-0000 007F | 0xxxxxxx
   0000 0080-0000 07FF | 110xxxxx 10xxxxxx
   0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
   0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
给定一个表示数据的整数数组,返回它是否为有效的 utf-8 编码。
注意:输入是整数数组。只有每个整数的最低 8 个有效位用来存储数据。这意味着每个整数只表示 1 字节的数据。
示例 1:data = [197, 130, 1], 表示 8 位的序列: 11000101 10000010 00000001.返回 true 。
这是有效的 utf-8 编码,为一个2字节字符,跟着一个1字节字符。
示例 2:data = [235, 140, 4], 表示 8 位的序列: 11101011 10001100 00000100. 返回 false 。
前 3 位都是 1 ,第 4 位为 0 表示它是一个3字节字符。
下一个字节是开头为 10 的延续字节,这是正确的。
但第二个延续字节不以 10 开头,所以是不符合规则的。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 位运算 O(n) O(1)
02 位运算 O(n) O(1)
func validUtf8(data []int) bool {
    count := 0
    for i := 0; i < len(data); i++ {
        if count == 0 {
            if data[i]&0b11111000 == 0b11110000 {
                count = 3
            } else if data[i]&0b11110000 == 0b11100000 {
                count = 2
            } else if data[i]&0b11100000 == 0b11000000 {
                count = 1
            } else if data[i]&0b10000000 != 0b00000000 { // 其它以1开头的
                return false
            }
        } else {
            if data[i]&0b10000000 != 0b10000000 {
                return false
            }
            count--
        }
    }
    return count == 0
}

# 2
func validUtf8(data []int) bool {
    count := 0
    for i := 0; i < len(data); i++ {
        if count == 0 {
            if data[i]>>3 == 0b11110 {
                count = 3
            } else if data[i]>>4 == 0b1110 {
                count = 2
            } else if data[i]>>5 == 0b110 {
                count = 1
            } else if data[i]>>7 != 0b0 { // 其它以1开头的
                return false
            }
        } else {
            if data[i]>>6 != 0b10 {
                return false
            }
            count--
        }
    }
    return count == 0
}

394.字符串解码(2)

  • 题目
给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。
注意 k 保证为正整数。
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。
示例 1:输入:s = "3[a]2[bc]" 输出:"aaabcbc"
示例 2:输入:s = "3[a2[c]]" 输出:"accaccacc"
示例 3:输入:s = "2[abc]3[cd]ef" 输出:"abcabccdcdcdef"
示例 4:输入:s = "abc3[cd]xyz" 输出:"abccdcdcdxyz"
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 栈辅助 O(n) O(n)
02 递归 O(n) O(n)
func decodeString(s string) string {
    res := make([]byte, 0)
    numStack := make([]int, 0)
    lenStack := make([]int, 0)
    var count int
    for i := 0; i < len(s); i++ {
        if '0' <= s[i] && s[i] <= '9' {
            count = count*10 + int(s[i]-'0')
        } else if s[i] == '[' {
            numStack = append(numStack, count)
            count = 0
            lenStack = append(lenStack, len(res))
        } else if s[i] == ']' {
            c := numStack[len(numStack)-1]
            numStack = numStack[:len(numStack)-1]
            l := lenStack[len(lenStack)-1]
            lenStack = lenStack[:len(lenStack)-1]
            str := res[l:]
            res = res[:l]
            for i := 0; i < c; i++ {
                res = append(res, str...)
            }
        } else {
            res = append(res, s[i])
        }
    }
    return string(res)
}

#
func decodeString(s string) string {
    res := ""
    count := 0
    for i := 0; i < len(s); i++ {
        if '0' <= s[i] && s[i] <= '9' {
            count = count*10 + int(s[i]-'0')
        } else if s[i] == '[' {
            times := 0
            i++
            str := make([]byte, 0)
            for s[i] != ']' || times != 0 {
                if s[i] == '[' {
                    times++
                } else if s[i] == ']' {
                    times--
                }
                str = append(str, s[i])
                i++
            }
            temp := decodeString(string(str))
            for j := 0; j < count; j++ {
                res = res + (temp)
            }
            count = 0
        } else {
            res = res + string(s[i])
        }
    }
    return res
}

395.至少有K个重复字符的最长子串(2)

  • 题目
找到给定字符串(由小写字符组成)中的最长子串 T , 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。
示例 1:输入: s = "aaabb", k = 3输出: 3
最长子串为 "aaa" ,其中 'a' 重复了 3 次。
示例 2:输入:s = "ababbc", k = 2 输出:5 
最长子串为 "ababb" ,其中 'a' 重复了 2 次, 'b' 重复了 3 次。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 分治 O(n) O(1)
02 滑动窗口 O(n) O(1)
func longestSubstring(s string, k int) int {
    res := 0
    m := make(map[byte]int) // 统计每个字符的个数
    for i := 0; i < len(s); i++ {
        m[s[i]]++
    }
    var split byte // 某个字符出现的次数:0<x<k
    for key, value := range m {
        if value < k {
            split = key
            break
        }
    }
    if split == 0 { // 字符出现次数都>=k
        return len(s)
    }
    arr := strings.Split(s, string(split)) // 以该字符切割的子串
    for i := 0; i < len(arr); i++ {
        temp := longestSubstring(arr[i], k)
        if temp > res {
            res = temp
        }
    }
    return res
}

# 2
func longestSubstring(s string, k int) int {
    res := 0
    // 多次滑动窗口
    for i := 1; i < 26; i++ { // 枚举字符种类的个数
        m := make(map[byte]int)
        count := 0
        left := 0
        lessK := 0 // 字符出现次数<k的个数
        for right := 0; right < len(s); right++ {
            if m[s[right]] == 0 {
                count++
                lessK++
            }
            m[s[right]]++
            if m[s[right]] == k {
                lessK--
            }
            for count > i { // 字母出现次数大于枚举的次数
                if m[s[left]] == k {
                    lessK++
                }
                m[s[left]]-- // 移动左窗口
                if m[s[left]] == 0 {
                    count--
                    lessK--
                }
                left++
            }
            if lessK == 0 && right-left+1 > res { // 更新结果
                res = right - left + 1
            }
        }
    }
    return res
}

396.旋转函数(1)

  • 题目
给定一个长度为 n 的整数数组A。
假设Bk是数组A顺时针旋转 k 个位置后的数组,我们定义A的“旋转函数”F为:
F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]。
计算F(0), F(1), ..., F(n-1)中的最大值。
注意:可以认为 n 的值小于 10^5。
示例:A = [4, 3, 2, 6]
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
所以 F(0), F(1), F(2), F(3) 中的最大值是 F(3) = 26 。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
func maxRotateFunction(A []int) int {
    res := 0
    total := 0
    n := len(A)
    for i := 0; i < n; i++ {
        total = total + A[i]
        res = res + i*A[i]
    }
    temp := res
    for i := 0; i < n; i++ {
        // 最后移动到第一位,其他右移一位
        temp = temp + total      // 每一位都加一次
        temp = temp - n*A[n-1-i] // 最后一位删除
        if temp > res {
            res = temp
        }
    }
    return res
}

397.整数替换(2)

  • 题目
给定一个正整数 n,你可以做如下操作:
1. 如果 n 是偶数,则用 n / 2替换 n。
2. 如果 n 是奇数,则可以用 n + 1或n - 1替换 n。
n 变为 1 所需的最小替换次数是多少?
示例 1:输入: 8输出: 3
解释:8 -> 4 -> 2 -> 1
示例 2:输入: 7输出: 4
解释:7 -> 8 -> 4 -> 2 -> 1 或7 -> 6 -> 3 -> 2 -> 1
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 递归 O(log(n)) O(log(n))
02 递归 O(log(n)) O(log(n))
func integerReplacement(n int) int {
    if n < 3 {
        return n - 1
    }
    if n == math.MinInt32 {
        return 32
    }
    if n%2 == 0 {
        return integerReplacement(n/2) + 1
    }
    a := integerReplacement(n+1) + 1
    b := integerReplacement(n-1) + 1
    if a > b {
        return b
    }
    return a
}

# 2
var m map[int]int

func integerReplacement(n int) int {
    m = make(map[int]int)
    return dfs(n)
}

func dfs(n int) int {
    if m[n] > 0 {
        return m[n]
    }
    if n == 1 {
        return 0
    }
    if n%2 == 0 {
        m[n] = dfs(n/2) + 1
    } else {
        m[n] = min(dfs(n-1), dfs(n+1)) + 1
    }
    return m[n]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

398.随机数索引(2)

  • 题目
给定一个可能含有重复元素的整数数组,要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。
注意:数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。
示例:int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);
// pick(3) 应该返回索引 2,3 或者 4。每个索引的返回概率应该相等。
solution.pick(3);
// pick(1) 应该返回 0。因为只有nums[0]等于1。
solution.pick(1);
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(1) O(n)
02 遍历 O(n) O(n)
type Solution struct {
    m map[int][]int
    r *rand.Rand
}

func Constructor(nums []int) Solution {
    res := Solution{
        m: make(map[int][]int),
        r: rand.New(rand.NewSource(time.Now().Unix())),
    }
    for i := 0; i < len(nums); i++ {
        res.m[nums[i]] = append(res.m[nums[i]], i)
    }
    return res
}

func (this *Solution) Pick(target int) int {
    arr := this.m[target]
    index := this.r.Intn(len(arr))
    return arr[index]
}

# 2
type Solution struct {
    nums []int
    r    *rand.Rand
}

func Constructor(nums []int) Solution {
    return Solution{
        nums: nums,
        r:    rand.New(rand.NewSource(time.Now().Unix())),
    }
}

func (this *Solution) Pick(target int) int {
    res := 0
    count := 1
    for i := 0; i < len(this.nums); i++ {
        if this.nums[i] == target {
            // 蓄水池采样法
            if this.r.Intn(count)+1 == count {
                res = i
            }
            count++
        }
    }
    return res
}

399.除法求值(3)

  • 题目
给出方程式A / B = k, 其中A 和B 均为用字符串表示的变量,k 是一个浮点型数字。
根据已知方程式求解问题,并返回计算结果。如果结果不存在,则返回-1.0。
输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况,且不存在任何矛盾的结果。
示例 1:输入:equations = [["a","b"],["b","c"]], values = [2.0,3.0], 
queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
输出:[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释:给定:a / b = 2.0, b / c = 3.0
问题:a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
返回:[6.0, 0.5, -1.0, 1.0, -1.0 ]
示例 2:输入:equations = [["a","b"],["b","c"],["bc","cd"]], 
values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
输出:[3.75000,0.40000,5.00000,0.20000]
示例 3:输入:equations = [["a","b"]], values = [0.5], 
queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
输出:[0.50000,2.00000,-1.00000,-1.00000]
提示:1 <= equations.length <= 20
equations[i].length == 2
1 <= equations[i][0].length, equations[i][1].length <= 5
values.length ==equations.length
0.0 <values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= queries[i][0].length, queries[i][1].length <= 5
equations[i][0], equations[i][1],queries[i][0], queries[i][1] 由小写英文字母与数字组成
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 广度优先搜索 O(n^2) O(n^2)
02 Floyd O(n^3) O(n^2)
03 并查集 O(nlog(n)) O(n)
type Node struct {
    to    int
    value float64
}

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
    m := make(map[string]int) // 计算对应的id
    for i := 0; i < len(equations); i++ {
        a, b := equations[i][0], equations[i][1]
        if _, ok := m[a]; ok == false {
            m[a] = len(m)
        }
        if _, ok := m[b]; ok == false {
            m[b] = len(m)
        }
    }
    arr := make([][]Node, len(m)) // 邻接表
    for i := 0; i < len(equations); i++ {
        a, b := m[equations[i][0]], m[equations[i][1]]
        arr[a] = append(arr[a], Node{to: b, value: values[i]})
        arr[b] = append(arr[b], Node{to: a, value: 1 / values[i]}) // 除以
    }
    res := make([]float64, len(queries))
    for i := 0; i < len(queries); i++ {
        a, okA := m[queries[i][0]]
        b, okB := m[queries[i][1]]
        if okA == false || okB == false {
            res[i] = -1
        } else {
            res[i] = bfs(arr, a, b) // 广度优先查找
        }
    }
    return res
}

func bfs(arr [][]Node, start, end int) float64 {
    temp := make([]float64, len(arr)) // 结果的比例
    temp[start] = 1
    queue := make([]int, 0)
    queue = append(queue, start)
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        if node == end {
            return temp[node]
        }
        for i := 0; i < len(arr[node]); i++ {
            next := arr[node][i].to
            if temp[next] == 0 {
                temp[next] = temp[node] * arr[node][i].value
                queue = append(queue, next)
            }
        }
    }
    return -1
}

# 2
func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
    m := make(map[string]int) // 计算对应的id
    for i := 0; i < len(equations); i++ {
        a, b := equations[i][0], equations[i][1]
        if _, ok := m[a]; ok == false {
            m[a] = len(m)
        }
        if _, ok := m[b]; ok == false {
            m[b] = len(m)
        }
    }
    arr := make([][]float64, len(m)) // 邻接矩阵
    for i := 0; i < len(m); i++ {
        arr[i] = make([]float64, len(m))
    }
    for i := 0; i < len(equations); i++ {
        a, b := m[equations[i][0]], m[equations[i][1]]
        arr[a][b] = values[i]
        arr[b][a] = 1 / values[i]
    }
    for k := 0; k < len(arr); k++ { // Floyd
        for i := 0; i < len(arr); i++ {
            for j := 0; j < len(arr); j++ {
                if arr[i][k] > 0 && arr[k][j] > 0 {
                    arr[i][j] = arr[i][k] * arr[k][j]
                }
            }
        }
    }
    res := make([]float64, len(queries))
    for i := 0; i < len(queries); i++ {
        a, okA := m[queries[i][0]]
        b, okB := m[queries[i][1]]
        if okA == false || okB == false || arr[a][b] == 0 {
            res[i] = -1
        } else {
            res[i] = arr[a][b]
        }
    }
    return res
}

# 3
func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
    m := make(map[string]int) // 计算对应的id
    for i := 0; i < len(equations); i++ {
        a, b := equations[i][0], equations[i][1]
        if _, ok := m[a]; ok == false {
            m[a] = len(m)
        }
        if _, ok := m[b]; ok == false {
            m[b] = len(m)
        }
    }
    fa, rank = Init(len(m))
    for i := 0; i < len(equations); i++ {
        a, b := m[equations[i][0]], m[equations[i][1]]
        union(a, b, values[i])
    }
    res := make([]float64, len(queries))
    for i := 0; i < len(queries); i++ {
        a, okA := m[queries[i][0]]
        b, okB := m[queries[i][1]]
        if okA == true && okB == true && find(a) == find(b) {
            res[i] = rank[a] / rank[b]
        } else {
            res[i] = -1
        }
    }
    return res
}

var fa []int
var rank []float64

// 初始化
func Init(n int) ([]int, []float64) {
    arr := make([]int, n)
    r := make([]float64, n)
    for i := 0; i < n; i++ {
        arr[i] = i
        r[i] = 1
    }
    return arr, r
}

// 查询
func find(x int) int {
    // 彻底路径压缩
    if fa[x] != x {
        origin := fa[x]
        fa[x] = find(fa[x])
        rank[x] = rank[x] * rank[origin] // 秩处理是难点
    }
    return fa[x]
}

// 合并
func union(i, j int, value float64) {
    x, y := find(i), find(j)
    rank[x] = value * rank[j] / rank[i] // 秩处理是难点
    fa[x] = y
}

400.第N个数字(2)

  • 题目
在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...中找到第 n 个数字。
注意:n 是正数且在32位整数范围内 ( n < 231)。
示例 1:输入:3输出:3
示例 2:输入:11输出:0
说明:第11个数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是0,它是10的一部分。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 找规律 O(log(n)) O(1)
02 找规律 O(log(n)) O(1)
func findNthDigit(n int) int {
    if n < 0 {
        return -1
    }
    digits := 1
    for {
        numbers := countOfIntegers(digits)
        if n < numbers*digits {
            return digitAtIndex(n, digits)
        }
        n = n - numbers*digits
        digits++
    }
}

func countOfIntegers(n int) int {
    if n == 1 {
        return 10
    }
    count := math.Pow(float64(10), float64(n-1))
    return 9 * int(count)
}

func digitAtIndex(n, digits int) int {
    number := beginNumber(digits) + n/digits
    indexFromRight := digits - n%digits
    for i := 1; i < indexFromRight; i++ {
        number = number / 10
    }
    return number % 10
}

func beginNumber(digits int) int {
    if digits == 1 {
        return 0
    }
    return int(math.Pow(float64(10), float64(digits-1)))
}

# 2
func findNthDigit(n int) int {
    if n < 10 {
        return n
    }
    digits := 1
    count := 9
    number := 1
    for n-digits*count > 0 {
        n = n - digits*count
        digits++
        count = count * 10
        number = number * 10
    }
    number = number + (n-1)/digits
    index := (n - 1) % digits
    str := strconv.Itoa(number)
    return int(str[index] - '0')
}

0301-0400-Hard

301.删除无效的括号(2)

  • 题目
删除最小数量的无效括号,使得输入的字符串有效,返回所有可能的结果。
说明: 输入可能包含了除 ( 和 ) 以外的字符。
示例 1:输入: "()())()" 输出: ["()()()", "(())()"]
示例 2:输入: "(a)())()" 输出: ["(a)()()", "(a())()"]
示例 3:输入: ")(" 输出: [""]
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 广度优先搜索 O(2^n) O(n)
02 深度优先搜索 O(2^n) O(n)
func removeInvalidParentheses(s string) []string {
    res := make([]string, 0)
    cur := make(map[string]int)
    cur[s] = 1
    for {
        for k := range cur {
            if isValid(k) {
                res = append(res, k)
            }
        }
        if len(res) > 0 {
            return res
        }
        next := make(map[string]int)
        for k := range cur {
            for i := range k {
                if k[i] == '(' || k[i] == ')' {
                    str := k[:i] + k[i+1:]
                    next[str] = 1
                }
            }
        }
        cur = next
    }
}

func isValid(s string) bool {
    left := 0
    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            left++
        } else if s[i] == ')' {
            left--
        }
        if left < 0 {
            return false
        }
    }
    return left == 0
}

# 2
var m map[string]bool
var max int

func removeInvalidParentheses(s string) []string {
    m = make(map[string]bool)
    res := make([]string, 0)
    max = 0
    dfs(s, 0, 0, "")
    for k := range m {
        res = append(res, k)
    }
    return res
}

func dfs(s string, start, count int, temp string) {
    if count < 0 {
        return
    }
    if start == len(s) {
        if count == 0 {
            if len(temp) > max {
                max = len(temp)
                m = make(map[string]bool)
                m[temp] = true
            } else if max == len(temp) {
                m[temp] = true
            }
        }
        return
    }
    if s[start] == '(' {
        dfs(s, start+1, count+1, temp+"(")
    } else if s[start] == ')' {
        dfs(s, start+1, count-1, temp+")")
    } else {
        dfs(s, start+1, count, temp+string(s[start]))
    }
    if s[start] == '(' || s[start] == ')' {
        dfs(s, start+1, count, temp)
    }
}

312.戳气球(3)

  • 题目
有 n 个气球,编号为0 到 n-1,每个气球上都标有一个数字,这些数字存在数组 nums 中。
现在要求你戳破所有的气球。如果你戳破气球 i ,就可以获得 nums[left] * nums[i] * nums[right] 个硬币。
这里的 left 和 right 代表和 i 相邻的两个气球的序号。
注意当你戳破了气球 i 后,气球 left 和气球 right 就变成了相邻的气球。
求所能获得硬币的最大数量。
说明:你可以假设 nums[-1] = nums[n] = 1,但注意它们不是真实存在的所以并不能被戳破。
    0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
示例:输入: [3,1,5,8] 输出: 167 
解释: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
     coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 递归-记忆化搜索 O(n^3) O(n^2)
02 动态规划 O(n^3) O(n^2)
03 动态规划 O(n^3) O(n^2)
var res [][]int
var arr []int

func maxCoins(nums []int) int {
    n := len(nums)
    arr = make([]int, n+2)
    arr[0], arr[len(arr)-1] = 1, 1
    for i := 1; i <= n; i++ {
        arr[i] = nums[i-1]
    }
    res = make([][]int, n+2)
    for i := 0; i < len(res); i++ {
        res[i] = make([]int, n+2)
        for j := 0; j < len(res[i]); j++ {
            res[i][j] = -1
        }
    }
    return dfs(0, n+1)
}

// 将开区间(i,j)内的位置全部填满气球能够得到的最多硬币数
func dfs(left, right int) int {
    // 不满足3个
    if left+1 >= right {
        return 0
    }
    if res[left][right] != -1 {
        return res[left][right]
    }
    for i := left + 1; i < right; i++ {
        // 填充第i位,两边是arr[left],arr[right]
        sum := arr[left] * arr[i] * arr[right]
        sum = sum + dfs(left, i) + dfs(i, right)
        res[left][right] = max(res[left][right], sum)
    }
    return res[left][right]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 2
func maxCoins(nums []int) int {
    n := len(nums)
    arr := make([]int, n+2)
    arr[0], arr[len(arr)-1] = 1, 1
    for i := 1; i <= n; i++ {
        arr[i] = nums[i-1]
    }
    dp := make([][]int, n+2)
    for i := 0; i < len(dp); i++ {
        dp[i] = make([]int, n+2)
    }
    // dp[i][j] 表示填满开区间(i,j)能得到的最多硬币数
    // i => left
    // k => i
    // j => right
    // i不能0->n+1
    for i := n - 1; i >= 0; i-- {
        for j := i + 2; j <= n+1; j++ {
            for k := i + 1; k < j; k++ {
                sum := arr[i] * arr[k] * arr[j]
                sum = sum + dp[i][k] + dp[k][j]
                dp[i][j] = max(dp[i][j], sum)
            }
        }
    }
    return dp[0][n+1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 3
func maxCoins(nums []int) int {
    n := len(nums)
    arr := make([]int, n+2)
    arr[0], arr[len(arr)-1] = 1, 1
    for i := 1; i <= n; i++ {
        arr[i] = nums[i-1]
    }
    dp := make([][]int, n+2)
    for i := 0; i < len(dp); i++ {
        dp[i] = make([]int, n+2)
    }
    // dp[i][j] 表示填满开区间(i,j)能得到的最多硬币数
    // i => left
    // k => i
    // j => right
    for j := 2; j <= n+1; j++ {
        for i := j - 2; i >= 0; i-- {
            for k := i + 1; k < j; k++ {
                sum := arr[i] * arr[k] * arr[j]
                sum = sum + dp[i][k] + dp[k][j]
                dp[i][j] = max(dp[i][j], sum)
            }
        }
    }
    return dp[0][n+1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

315.计算右侧小于当前元素的个数(3)

  • 题目
给定一个整数数组 nums,按要求返回一个新数组counts。
数组 counts 有该性质: counts[i] 的值是 nums[i] 右侧小于nums[i] 的元素的数量。
示例:输入:nums = [5,2,6,1] 输出:[2,1,1,0] 
解释:5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素
提示:0 <= nums.length <= 10^5
-10^4<= nums[i] <= 10^4
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 树状数组+离散化 O(nlog(n)) O(n)
02 归并排序 O(nlog(n)) O(n)
03 线段树+离散化 O(nlog(n)) O(n)
func countSmaller(nums []int) []int {
    n := len(nums)
    res := make([]int, n)
    arr, _ := getLSH(nums)
    length = n
    c = make([]int, n+1)
    for i := n - 1; i >= 0; i-- {
        res[i] = getSum(arr[i] - 1)
        upData(arr[i], 1)
    }
    return res
}

func getLSH(a []int) ([]int, map[int]int) {
    n := len(a)
    arr := make([]int, n)
    copy(arr, a)
    sort.Ints(arr) // 排序
    m := make(map[int]int)
    m[arr[0]] = 1
    index := 1
    for i := 1; i < n; i++ {
        if arr[i] != arr[i-1] {
            index++
            m[arr[i]] = index
        }
    }
    res := make([]int, n)
    for i := 0; i < n; i++ {
        res[i] = m[a[i]]
    }
    return res, m
}

var length int
var c []int // 树状数组

func lowBit(x int) int {
    return x & (-x)
}

// 单点修改
func upData(i, k int) { // 在i位置加上k
    for i <= length {
        c[i] = c[i] + k
        i = i + lowBit(i) // i = i + 2^k
    }
}

// 区间查询
func getSum(i int) int {
    res := 0
    for i > 0 {
        res = res + c[i]
        i = i - lowBit(i)
    }
    return res
}

# 2
type Node struct {
    Value int
    Index int
}

var res []int

func countSmaller(nums []int) []int {
    n := len(nums)
    res = make([]int, n)
    arr := make([]Node, 0)
    for i := 0; i < n; i++ {
        arr = append(arr, Node{
            Value: nums[i],
            Index: i,
        })
    }
    mergeSort(arr)
    return res
}

func mergeSort(nums []Node) {
    n := len(nums)
    if n <= 1 {
        return
    }
    a := append([]Node{}, nums[:n/2]...)
    b := append([]Node{}, nums[n/2:]...)
    mergeSort(a) // a已经有序
    mergeSort(b) // b已经有序
    i, j := 0, 0
    for i = 0; i < len(a); i++ {
        for j < len(b) && a[i].Value > b[j].Value { // 统计比右边多多少个数
            j++
        }
        res[a[i].Index] = res[a[i].Index] + j // 找到下标,然后加上次数
    }
    i, j = 0, 0
    for k := 0; k < len(nums); k++ { // 2个有序数组合并
        if i < len(a) && (j == len(b) || a[i].Value <= b[j].Value) {
            nums[k] = a[i]
            i++
        } else {
            nums[k] = b[j]
            j++
        }
    }
    return
}

# 3
func countSmaller(nums []int) []int {
    n := len(nums)
    res := make([]int, n)
    tempArr, m := getLSH(nums)
    total := len(tempArr)
    arr = make([]int, 4*total+1)
    for i := n - 1; i >= 0; i-- {
        index := m[nums[i]]
        res[i] = query(0, 1, total, 1, index-1)
        update(0, 1, total, index, 1)
    }
    return res
}

func getLSH(a []int) ([]int, map[int]int) {
    n := len(a)
    arr := make([]int, n)
    copy(arr, a)
    sort.Ints(arr) // 排序
    m := make(map[int]int)
    m[arr[0]] = 1
    index := 1
    for i := 1; i < n; i++ {
        if arr[i] != arr[i-1] {
            index++
            m[arr[i]] = index
        }
    }
    res := make([]int, n)
    for i := 0; i < n; i++ {
        res[i] = m[a[i]]
    }
    return res, m
}

var arr []int // 线段树

func update(id int, left, right, x int, value int) {
    if left > x || right < x {
        return
    }
    arr[id] = arr[id] + value
    if left == right {
        return
    }
    mid := left + (right-left)/2
    update(2*id+1, left, mid, x, value)    // 左节点
    update(2*id+2, mid+1, right, x, value) // 右节点
}

func query(id int, left, right, queryLeft, queryRight int) int {
    if left > queryRight || right < queryLeft {
        return 0
    }
    if queryLeft <= left && right <= queryRight {
        return arr[id]
    }
    mid := left + (right-left)/2
    return query(id*2+1, left, mid, queryLeft, queryRight) +
        query(id*2+2, mid+1, right, queryLeft, queryRight)
}

316.去除重复字母(2)

  • 题目
给你一个仅包含小写字母的字符串,请你去除字符串中重复的字母,使得每个字母只出现一次。
需保证返回结果的字典序最小(要求不能打乱其他字符的相对位置)。
示例 1:输入: "bcabc" 输出: "abc"
示例 2:输入: "cbacdcbc" 输出: "acdb"
注意:该题与 1081 
https://leetcode.cn/problems/smallest-subsequence-of-distinct-characters 相同
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 单调栈 O(n) O(n)
02 递归 O(n) O(n)
func removeDuplicateLetters(s string) string {
    stack := make([]byte, 0)
    arr := [256]byte{}
    m := make(map[byte]bool)
    for i := 0; i < len(s); i++ {
        arr[s[i]]++
    }
    for i := 0; i < len(s); i++ {
        if m[s[i]] == true {
            arr[s[i]]--
            continue
        }
        // arr[栈顶]说明有重复元素
        // 栈顶>s[i]:说明字典序不满足
        for len(stack) > 0 && stack[len(stack)-1] > s[i] && arr[stack[len(stack)-1]] > 0 {
            m[stack[len(stack)-1]] = false
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, s[i])
        arr[s[i]]--
        m[s[i]] = true
    }
    return string(stack)
}

# 2
func removeDuplicateLetters(s string) string {
    arr := [26]int{}
    pos := 0
    for i := 0; i < len(s); i++ {
        arr[s[i]-'a']++
    }
    for i := 0; i < len(s); i++ {
        if s[i] < s[pos] {
            pos = i
        }
        arr[s[i]-'a']--
        if arr[s[i]-'a'] == 0 {
            break
        }
    }
    if len(s) == 0 {
        return ""
    }
    newStr := strings.ReplaceAll(s[pos+1:], string(s[pos]), "")
    return string(s[pos]) + removeDuplicateLetters(newStr)
}

321.拼接最大数(1)

  • 题目
给定长度分别为m和n的两个数组,其元素由0-9构成,表示两个自然数各位上的数字。
现在从这两个数组中选出 k (k <= m + n)个数字拼接成一个新的数,
要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
求满足该条件的最大数。结果返回一个表示该最大数的长度为k的数组。
说明: 请尽可能地优化你算法的时间和空间复杂度。
示例1:输入:nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5
输出:[9, 8, 6, 5, 3]
示例 2:输入:nums1 = [6, 7]nums2 = [6, 0, 4]k = 5
输出:[6, 7, 6, 0, 4]
示例 3:输入:nums1 = [3, 9]nums2 = [8, 9] k = 3
输出:[9, 8, 9]
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 枚举 O(n^3) O(n)
func maxNumber(nums1 []int, nums2 []int, k int) []int {
    res := make([]int, k)
    for i := 0; i <= k; i++ {
        if i <= len(nums1) && k-i <= len(nums2) {
            a := check(nums1, i)
            b := check(nums2, k-i)
            c := merge(a, b)
            if compare(res, c) == true {
                res = c
            }
        }
    }
    return res
}

func check(num []int, k int) []int {
    stack := make([]int, 0)
    count := len(num) - k
    for i := 0; i < len(num); i++ {
        for len(stack) > 0 && count > 0 && stack[len(stack)-1] < num[i] {
            stack = stack[:len(stack)-1]
            count--
        }
        stack = append(stack, num[i])
    }
    return stack[:k]
}

func merge(nums1, nums2 []int) []int {
    res := make([]int, len(nums1)+len(nums2))
    if len(nums1) == 0 {
        copy(res, nums2)
        return res
    }
    if len(nums2) == 0 {
        copy(res, nums1)
        return res
    }
    for i := 0; i < len(res); i++ {
        if compare(nums1, nums2) {
            res[i], nums2 = nums2[0], nums2[1:]
        } else {
            res[i], nums1 = nums1[0], nums1[1:]
        }
    }
    return res
}

func compare(nums1, nums2 []int) bool {
    for i := 0; i < len(nums1) && i < len(nums2); i++ {
        if nums1[i] != nums2[i] {
            return nums1[i] < nums2[i]
        }
    }
    return len(nums1) < len(nums2)
}

327.区间和的个数(3)

  • 题目
给你一个整数数组nums 以及两个整数lower 和 upper 。
求数组中,值位于范围 [lower, upper] (包含lower和upper)之内的 区间和的个数 。
区间和S(i, j)表示在nums中,位置从i到j的元素之和,包含i和j(i ≤ j)。
示例 1:输入:nums = [-2,5,-1], lower = -2, upper = 2 输出:3
解释:存在三个区间:[0,0]、[2,2] 和 [0,2] ,对应的区间和分别是:-2 、-1 、2 。
示例 2:输入:nums = [0], lower = 0, upper = 0 输出:1
提示:1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
-105 <= lower <= upper <= 105
题目数据保证答案是一个 32 位 的整数
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 归并排序+前缀和 O(nlog(n)) O(n)
02 线段树+前缀和+离散化 O(nlog(n)) O(n)
03 树状数组+前缀和+离散化 O(nlog(n)) O(n)
 func countRangeSum(nums []int, lower int, upper int) int {
     n := len(nums)
     arr := make([]int, n+1) // 前缀和
     for i := 0; i < n; i++ {
         arr[i+1] = arr[i] + nums[i]
     }
     return countSum(arr, lower, upper)
 }

 func countSum(nums []int, lower int, upper int) int {
     n := len(nums)
     if n <= 1 {
         return 0
     }
     a := append([]int{}, nums[:n/2]...)
     b := append([]int{}, nums[n/2:]...)
     res := countSum(a, lower, upper) + countSum(b, lower, upper)
     left, right := 0, 0
     for i := 0; i < len(a); i++ {
         for left < len(b) && b[left]-a[i] < lower { 
             left++
         }
         for right < len(b) && b[right]-a[i] <= upper {
             right++
         }
         res = res + right - left
     }
     i, j := 0, 0
     for k := 0; k < len(nums); k++ { // 2个有序数组合并
         if i < len(a) && (j == len(b) || a[i] <= b[j]) {
             nums[k] = a[i]
             i++
         } else {
             nums[k] = b[j]
             j++
         }
     }
     return res
 }

 # 2
 func countRangeSum(nums []int, lower int, upper int) int {
     n := len(nums)
     preSum := make([]int, n+1) // 前缀和
     temp := make([]int, 0)
     temp = append(temp, 0) // 注意0
     for i := 0; i < n; i++ {
         preSum[i+1] = preSum[i] + nums[i]
         temp = append(temp, preSum[i+1], preSum[i+1]-lower, preSum[i+1]-upper)
     }
     tempArr, m := getLSH(temp) // 离散化
     total := len(tempArr)
     arr = make([]int, 4*total+1)
     update(0, 1, total, m[0], 1) // 注意0
     res := 0
     for i := 1; i < len(preSum); i++ {
         left := m[preSum[i]-upper]
         right := m[preSum[i]-lower]
         index := m[preSum[i]]
         count := query(0, 1, total, left, right)
         res = res + count
         update(0, 1, total, index, 1)
     }
     return res
 }

 // 离散化
 func getLSH(a []int) ([]int, map[int]int) {
     n := len(a)
     arr := make([]int, n)
     copy(arr, a)
     sort.Ints(arr) // 排序
     m := make(map[int]int)
     m[arr[0]] = 1
     index := 1
     for i := 1; i < n; i++ {
         if arr[i] != arr[i-1] {
             index++
             m[arr[i]] = index
         }
     }
     res := make([]int, n)
     for i := 0; i < n; i++ {
         res[i] = m[a[i]]
     }
     return res, m
 }

 var arr []int // 线段树

 func update(id int, left, right, x int, value int) {
     if left > x || right < x {
         return
     }
     arr[id] = arr[id] + value
     if left == right {
         return
     }
     mid := left + (right-left)/2
     update(2*id+1, left, mid, x, value)    // 左节点
     update(2*id+2, mid+1, right, x, value) // 右节点
 }

 func query(id int, left, right, queryLeft, queryRight int) int {
     if left > queryRight || right < queryLeft {
         return 0
     }
     if queryLeft <= left && right <= queryRight {
         return arr[id]
     }
     mid := left + (right-left)/2
     return query(id*2+1, left, mid, queryLeft, queryRight) +
         query(id*2+2, mid+1, right, queryLeft, queryRight)
 }

 # 3
 func countRangeSum(nums []int, lower int, upper int) int {
     n := len(nums)
     preSum := make([]int, n+1) // 前缀和
     temp := make([]int, 0)
     temp = append(temp, 0) // 注意0
     for i := 0; i < n; i++ {
         preSum[i+1] = preSum[i] + nums[i]
         temp = append(temp, preSum[i+1], preSum[i+1]-lower, preSum[i+1]-upper)
     }
     tempArr, m := getLSH(temp) // 离散化
     length = len(tempArr)
     c = make([]int, length+1)
     upData(m[0], 1) // 注意0
     res := 0
     for i := 1; i < len(preSum); i++ {
         left := m[preSum[i]-upper]
         right := m[preSum[i]-lower]
         index := m[preSum[i]]
         count := getSum(right) - getSum(left-1)
         res = res + count
         upData(index, 1)
     }
     return res
 }

 // 离散化
 func getLSH(a []int) ([]int, map[int]int) {
     n := len(a)
     arr := make([]int, n)
     copy(arr, a)
     sort.Ints(arr) // 排序
     m := make(map[int]int)
     m[arr[0]] = 1
     index := 1
     for i := 1; i < n; i++ {
         if arr[i] != arr[i-1] {
             index++
             m[arr[i]] = index
         }
     }
     res := make([]int, n)
     for i := 0; i < n; i++ {
         res[i] = m[a[i]]
     }
     return res, m
 }

 var length int
 var c []int // 树状数组

 func lowBit(x int) int {
     return x & (-x)
 }

 // 单点修改
 func upData(i, k int) { // 在i位置加上k
     for i <= length {
         c[i] = c[i] + k
         i = i + lowBit(i) // i = i + 2^k
     }
 }

 // 区间查询
 func getSum(i int) int {
     res := 0
     for i > 0 {
         res = res + c[i]
         i = i - lowBit(i)
     }
     return res
 }

329.矩阵中的最长递增路径(3)

  • 题目
给定一个m x n 整数矩阵matrix ,找出其中 最长递增路径 的长度。
对于每个单元格,你可以往上,下,左,右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外(即不允许环绕)。
示例 1:输入:matrix = [[9,9,4],[6,6,8],[2,1,1]] 输出:4 
解释:最长递增路径为[1, 2, 6, 9]。
示例 2:输入:matrix = [[3,4,5],[3,2,6],[2,2,1]]输出:4 
解释:最长递增路径是[3, 4, 5, 6]。注意不允许在对角线方向上移动。
示例 3:输入:matrix = [[1]]输出:1
提示:m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 231 - 1
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 深度优先搜索 O(n^2) O(n^2)
02 广度优先搜索+拓扑排序 O(n^2) O(n^2)
03 排序+动态规划 O(n^2*log(n)) O(n^2)
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}
var n, m int
var arr [][]int

func longestIncreasingPath(matrix [][]int) int {
    n, m = len(matrix), len(matrix[0])
    arr = make([][]int, n)
    for i := 0; i < n; i++ {
        arr[i] = make([]int, m)
    }
    res := 0
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            res = max(res, dfs(matrix, i, j))
        }
    }
    return res
}

func dfs(matrix [][]int, i, j int) int {
    if arr[i][j] != 0 {
        return arr[i][j]
    }
    arr[i][j]++ // 长度为1
    for k := 0; k < 4; k++ {
        x, y := i+dx[k], j+dy[k]
        if 0 <= x && x < n && 0 <= y && y < m && matrix[x][y] > matrix[i][j] {
            arr[i][j] = max(arr[i][j], dfs(matrix, x, y)+1)
        }
    }
    return arr[i][j]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 2
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}

func longestIncreasingPath(matrix [][]int) int {
    n, m := len(matrix), len(matrix[0])
    arr := make([][]int, n)
    for i := 0; i < n; i++ {
        arr[i] = make([]int, m)
    }
    queue := make([][2]int, 0) // 从最大数开始广度优先搜索
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            for k := 0; k < 4; k++ {
                x, y := i+dx[k], j+dy[k]
                if 0 <= x && x < n && 0 <= y && y < m && matrix[x][y] > matrix[i][j] {
                    arr[i][j]++ // 四周大于当前的个数
                }
            }
            if arr[i][j] == 0 { // 四周没有大于当前的数
                queue = append(queue, [2]int{i, j})
            }
        }
    }
    res := 0
    for len(queue) > 0 {
        res++
        length := len(queue)
        for i := 0; i < length; i++ {
            a, b := queue[i][0], queue[i][1]
            for k := 0; k < 4; k++ {
                x, y := a+dx[k], b+dy[k]
                if 0 <= x && x < n && 0 <= y && y < m && matrix[a][b] > matrix[x][y] {
                    arr[x][y]--
                    if arr[x][y] == 0 { // 个数为0,加入队列
                        queue = append(queue, [2]int{x, y})
                    }
                }
            }
        }
        queue = queue[length:]
    }
    return res
}

# 3
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}

func longestIncreasingPath(matrix [][]int) int {
    n, m := len(matrix), len(matrix[0])
    dp := make([][]int, n)
    temp := make([][3]int, 0)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, m)
        for j := 0; j < m; j++ {
            dp[i][j] = 1
            temp = append(temp, [3]int{i, j, matrix[i][j]})
        }
    }
    sort.Slice(temp, func(i, j int) bool {
        return temp[i][2] < temp[j][2]
    })
    res := 1 // 一个数的时候,没有周围4个数,此时为1
    for i := 0; i < len(temp); i++ {
        a, b := temp[i][0], temp[i][1]
        for k := 0; k < 4; k++ {
            x, y := a+dx[k], b+dy[k]
            if 0 <= x && x < n && 0 <= y && y < m && matrix[x][y] > matrix[a][b] {
                dp[x][y] = max(dp[x][y], dp[a][b]+1) // 更新长度
                res = max(res, dp[x][y])
            }
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

330.按要求补齐数组(1)

  • 题目
给定一个已排序的正整数数组 nums,和一个正整数n 。从[1, n]区间内选取任意个数字补充到nums中,
使得[1, n]区间内的任何数字都可以用nums中某几个数字的和来表示。
请输出满足上述要求的最少需要补充的数字个数。
示例1:输入: nums = [1,3], n = 6 输出: 1 
解释: 根据 nums里现有的组合[1], [3], [1,3],可以得出1, 3, 4。
现在如果我们将2添加到nums 中,组合变为: [1], [2], [3], [1,3], [2,3], [1,2,3]。
其和可以表示数字1, 2, 3, 4, 5, 6,能够覆盖[1, 6]区间里所有的数。
所以我们最少需要添加一个数字。
示例 2:输入: nums = [1,5,10], n = 20 输出: 2
解释: 我们需要添加[2, 4]。
示例3:输入: nums = [1,2,2], n = 5 输出: 0
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 贪心 O(n) O(1)
func minPatches(nums []int, n int) int {
    res := 0
    target := 1
    for i := 0; target <= n; {
        // 对于正整数x,如果区间[1,x-1]内的所有数字都已经被覆盖,
        // 加上x后,则区间[1,2x-1]内的所有数字被覆盖。
        if i < len(nums) && nums[i] <= target {
            // 贪心思路:把当前在范围内的加上,target之前的[1,target-1]都已经满足
            target = target + nums[i]
            i++
        } else {
            // 没有就把target加入数组,范围扩大1倍
            target = target * 2
            res++
        }
    }
    return res
}

335.路径交叉(2)

  • 题目
给定一个含有n个正数的数组x。从点(0,0)开始,先向北移动x[0]米,
然后向西移动x[1]米,向南移动x[2]米,向东移动x[3]米,持续移动。
也就是说,每次移动后你的方位会发生逆时针变化。
编写一个O(1)空间复杂度的一趟扫描算法,判断你所经过的路径是否相交。
示例1:
┌───┐
│  │
└───┼──>
  │
输入: [2,1,1,2] 输出: true 
示例2:
┌──────┐
│   │
│
│
└────────────>
输入: [1,2,3,4] 输出: false 
示例 3:
┌───┐
│  │
└───┼>
输入: [1,1,1,1] 输出: true
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 遍历 O(n) O(n)
func isSelfCrossing(distance []int) bool {
    n := len(distance)
    if n < 4 {
        return false
    }
    for i := 3; i < n; i++ {
        // 长度为4相交
        if i >= 3 && distance[i] >= distance[i-2] &&
            distance[i-1] <= distance[i-3] {
            return true
        }
        // 长度为5相交
        if i >= 4 && distance[i]+distance[i-4] >= distance[i-2] &&
            distance[i-1] == distance[i-3] {
            return true
        }
        // 长度为6相交
        if i >= 5 && distance[i]+distance[i-4] >= distance[i-2] &&
            distance[i-1]+distance[i-5] >= distance[i-3] &&
            distance[i-2] > distance[i-4] &&
            distance[i-1] < distance[i-3] {
            return true
        }
    }
    return false
}

# 2
func isSelfCrossing(distance []int) bool {
    arr := append([]int{0, 0, 0, 0}, distance...)
    n := len(arr)
    i := 4
    // 圈变大
    for i < n && arr[i] > arr[i-2] {
        i++
    }
    if i == n {
        return false
    }
    if arr[i] >= arr[i-2]-arr[i-4] {
        arr[i-1] = arr[i-1] - arr[i-3]
    }
    i++
    // 圈变小
    for i < n && arr[i] < arr[i-2] {
        i++
    }
    if i == n {
        return false
    }
    return true
}

336.回文对

题目

给定一组 互不相同 的单词, 找出所有不同的索引对(i, j),使得列表中的两个单词,
words[i] + words[j],可拼接成回文串。
示例 1:输入:["abcd","dcba","lls","s","sssll"] 输出:[[0,1],[1,0],[3,2],[2,4]] 
解释:可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
示例 2:输入:["bat","tab","cat"] 输出:[[0,1],[1,0]] 
解释:可拼接成的回文串为 ["battab","tabbat"]

解题思路

No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^2) O(n)


354.俄罗斯套娃信封问题(3)

  • 题目
给定一些标记了宽度和高度的信封,宽度和高度以整数对形式 (w, h) 出现。
当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。
请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。
说明: 不允许旋转信封。
示例:输入: envelopes = [[5,4],[6,4],[6,7],[2,3]] 输出: 3 
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^2) O(n)
02 贪心-二分查找 O(nlog(n)) O(n)
03 动态规划 O(n^2) O(n)
func maxEnvelopes(envelopes [][]int) int {
    if len(envelopes) <= 1 {
        return len(envelopes)
    }
    // 宽[0] 高[1]排序
    sort.Slice(envelopes, func(i, j int) bool {
        if envelopes[i][0] == envelopes[j][0] {
            return envelopes[i][1] < envelopes[j][1]
        }
        return envelopes[i][0] < envelopes[j][0]
    })
    // 第i个信封套几个
    dp := make([]int, len(envelopes))
    for i := 0; i < len(dp); i++ {
        dp[i] = 1
    }
    res := 1
    for i := 1; i < len(envelopes); i++ {
        for j := 0; j < i; j++ {
            if envelopes[i][0] > envelopes[j][0] &&
                envelopes[i][1] > envelopes[j][1] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
        res = max(res, dp[i])
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 2
func maxEnvelopes(envelopes [][]int) int {
    if len(envelopes) <= 1 {
        return len(envelopes)
    }
    // 宽[0] 高[1]排序
    sort.Slice(envelopes, func(i, j int) bool {
        if envelopes[i][0] == envelopes[j][0] {
            return envelopes[i][1] < envelopes[j][1]
        }
        return envelopes[i][0] < envelopes[j][0]
    })
    arr := make([]int, 0)
    for i := 0; i < len(envelopes); i++ {
        left := 0
        right := len(arr) - 1
        for left <= right {
            mid := left + (right-left)/2
            if envelopes[i][1] > arr[mid] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        if left >= len(arr) {
            arr = append(arr, envelopes[i][1])
        } else {
            arr[left] = envelopes[i][1]
        }
    }
    return len(arr)
}

# 3
func maxEnvelopes(envelopes [][]int) int {
    if len(envelopes) <= 1 {
        return len(envelopes)
    }
    // 宽[0] 高[1]排序
    sort.Slice(envelopes, func(i, j int) bool {
        if envelopes[i][0] == envelopes[j][0] {
            return envelopes[i][1] < envelopes[j][1]
        }
        return envelopes[i][0] < envelopes[j][0]
    })
    // 第i个信封套几个
    dp := make([]int, len(envelopes))
    dp[0] = 1
    res := 1
    for i := 1; i < len(envelopes); i++ {
        temp := 0
        for j := i - 1; j >= 0; j-- {
            if envelopes[i][0] > envelopes[j][0] &&
                envelopes[i][1] > envelopes[j][1] && dp[j] > temp {
                temp = dp[j]
            }
        }
        dp[i] = temp + 1
        if dp[i] > res {
            res = dp[i]
        }
    }
    return res
}

391.完美矩形(1)

  • 题目
我们有 N 个与坐标轴对齐的矩形, 其中 N > 0, 判断它们是否能精确地覆盖一个矩形区域。
每个矩形用左下角的点和右上角的点的坐标来表示。例如,一个单位正方形可以表示为 [1,1,2,2]。
( 左下角的点的坐标为 (1, 1) 以及右上角的点的坐标为 (2, 2) )。
示例 1:rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [3,2,4,4],
  [1,3,2,4],
  [2,3,3,4]
]
返回 true。5个矩形一起可以精确地覆盖一个矩形区域。
示例2:rectangles = [
  [1,1,2,3],
  [1,3,2,4],
  [3,1,4,2],
  [3,2,4,4]
]
返回 false。两个矩形之间有间隔,无法覆盖成一个矩形。
示例 3:rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [3,2,4,4]
]
返回 false。图形顶端留有间隔,无法覆盖成一个矩形。
示例 4:rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [2,2,4,4]
]
返回 false。因为中间有相交区域,虽然形成了矩形,但不是精确覆盖。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(n)
func isRectangleCover(rectangles [][]int) bool {
    minX, maxX := math.MaxInt32, math.MinInt32
    minY, maxY := math.MaxInt32, math.MinInt32
    res := 0
    m := make(map[string]bool)
    for i := 0; i < len(rectangles); i++ {
        a, b, c, d := rectangles[i][0], rectangles[i][1], rectangles[i][2], rectangles[i][3]
        minX = min(minX, a)
        minY = min(minY, b)
        maxX = max(maxX, c)
        maxY = max(maxY, d)
        res = res + (c-a)*(d-b)
        arr := []string{
            fmt.Sprintf("%d-%d", a, b), 
            fmt.Sprintf("%d-%d", c, d),
            fmt.Sprintf("%d-%d", a, d), 
            fmt.Sprintf("%d-%d", c, b),
        }
        for _, v := range arr {
            if _, ok := m[v]; ok {
                delete(m, v)
            } else {
                m[v] = true
            }
        }
    }
    if (maxX-minX)*(maxY-minY) != res { // 满足条件1:所有小矩形相加的面积之和要等于完美矩形的面积
        return false
    }
    if len(m) != 4 || // 满足条件2:除最终大矩形4个顶点外其它点都出现偶数次
        m[fmt.Sprintf("%d-%d", minX, minY)] == false || 
        m[fmt.Sprintf("%d-%d", minX, maxY)] == false ||
        m[fmt.Sprintf("%d-%d", maxX, minY)] == false || 
        m[fmt.Sprintf("%d-%d", maxX, maxY)] == false {
        return false
    }
    return true
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}
Copyright © Zhi2014 2023 all right reserved,powered by Gitbook该文件修订时间: 2023-10-23 15:20:51

results matching ""

    No results matching ""