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&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
}
#
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++ {
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 {
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])
}
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)
}
func (this *NumArray) SumRange(left int, right int) int {
return this.Query(0, 1, this.length, left+1, right+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])
}
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) {
for i <= this.length {
this.c[i] = this.c[i] + k
i = i + this.LowBit(i)
}
}
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)
dp[0][0] = -prices[0]
for i := 1; i < n; i++ {
dp[i][0] = max(dp[i-1][0], dp[i-1][2]-prices[i])
dp[i][1] = dp[i-1][0] + prices[i]
dp[i][2] = max(dp[i-1][1], dp[i-1][2])
}
return 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)
var a, b, c int
a = -prices[0]
for i := 1; i < n; i++ {
A := max(a, c-prices[i])
B := a + prices[i]
C := max(b, c)
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] {
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 {
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
b := max(leftA, leftB) + max(rightA, rightB)
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-- {
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
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) |
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
}
c, d := x, b
queue = append(queue, [2]int{c, d})
c, d = a, y
queue = append(queue, [2]int{c, d})
c, d = 0, b
queue = append(queue, [2]int{c, d})
c, d = a, 0
queue = append(queue, [2]int{c, d})
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})
}
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
}
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
}
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)
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++ {
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)
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++ {
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)
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)
down := make([]int, n)
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
down := 1
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 {
dp := make([]int, target+1)
dp[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 {
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
}
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:]
if count < len(temp) {
temp = temp[:count]
}
if strings.Contains(str, ".") {
length := len(str) + getLength(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
}
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)
}
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 {
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 {
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
for key, value := range m {
if value < k {
split = key
break
}
}
if split == 0 {
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
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)
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)
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++ {
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)
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)
}
func dfs(left, right int) int {
if left+1 >= right {
return 0
}
if res[left][right] != -1 {
return res[left][right]
}
for i := left + 1; i < right; i++ {
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)
}
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)
}
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) {
for i <= length {
c[i] = c[i] + k
i = i + lowBit(i)
}
}
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)
mergeSort(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++ {
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
}
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++ {
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)
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)
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)
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)
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) {
for i <= length {
c[i] = c[i] + k
i = i + lowBit(i)
}
}
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]++
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 {
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
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; {
if i < len(nums) && nums[i] <= target {
target = target + nums[i]
i++
} else {
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++ {
if i >= 3 && distance[i] >= distance[i-2] &&
distance[i-1] <= distance[i-3] {
return true
}
if i >= 4 && distance[i]+distance[i-4] >= distance[i-2] &&
distance[i-1] == distance[i-3] {
return true
}
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)
}
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]
})
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)
}
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)
}
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]
})
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 {
return false
}
if len(m) != 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
}