0501-0600-Easy
501.二叉搜索树中的众数(2)
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义：
结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
例如：
给定 BST [1,null,2,2],
1
\
2
/
2
返回[2].
提示：如果众数超过1个，不需考虑输出顺序
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归+哈希辅助 |
O(n) |
O(n) |
| 02 |
递归+中序遍历 |
O(n) |
O(log(n)) |
func findMode(root *TreeNode) []int {
m := map[int]int{}
dfs(root, m)
max := -1
res := make([]int, 0)
for i, v := range m {
if max <= v {
if max < v {
max = v
res = res[0:0]
}
res = append(res, i)
}
}
return res
}
func dfs(root *TreeNode, rec map[int]int) {
if root == nil {
return
}
rec[root.Val]++
dfs(root.Left, rec)
dfs(root.Right, rec)
}
#
var max int
var res []int
var cur int
var count int
func findMode(root *TreeNode) []int {
res = make([]int, 0)
max, cur, count = 0, 0, 0
dfs(root)
return res
}
func dfs(root *TreeNode) {
if root == nil {
return
}
dfs(root.Left)
if root.Val != cur {
count = 0
}
count++
if max < count {
max = count
res = []int{root.Val}
} else if max == count {
res = append(res, root.Val)
}
cur = root.Val
dfs(root.Right)
}
504.七进制数(3)
给定一个整数，将其转化为7进制，并以字符串形式输出。
示例 1:输入: 100 输出: "202"
示例 2: 输入: -7 输出: "-10"
注意: 输入范围是 [-1e7, 1e7] 。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(log(n)) |
O(1) |
| 02 |
内置函数 |
O(log(n)) |
O(1) |
| 03 |
递归 |
O(log(n)) |
O(log(n)) |
func convertToBase7(num int) string {
if num == 0 {
return "0"
}
minus := ""
if num < 0 {
minus = "-"
num = -1 * num
}
s := ""
for num > 0 {
s = fmt.Sprintf("%d", num%7) + s
num = num / 7
}
return minus + s
}
#
func convertToBase7(num int) string {
return strconv.FormatInt(int64(num), 7)
}
#
func convertToBase7(num int) string {
if num < 0 {
return "-" + convertToBase7(-1*num)
}
if num < 7 {
return strconv.Itoa(num)
}
return convertToBase7(num/7) + strconv.Itoa(num%7)
}
506.相对名次(1)
给出 N 名运动员的成绩，找出他们的相对名次并授予前三名对应的奖牌。
前三名运动员将会被分别授予 “金牌”，“银牌” 和“ 铜牌”
（"Gold Medal", "Silver Medal", "Bronze Medal"）。
(注：分数越高的选手，排名越靠前。)
示例 1:
输入: [5, 4, 3, 2, 1]
输出: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
解释: 前三名运动员的成绩为前三高的，
因此将会分别被授予 “金牌”，“银牌”和“铜牌” ("Gold Medal", "Silver Medal" and "Bronze Medal").
余下的两名运动员，我们只需要通过他们的成绩计算将其相对名次即可。
提示:
N 是一个正整数并且不会超过 10000。
所有运动员的成绩都不相同。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序+遍历 |
O(nlog(n)) |
O(n) |
func findRelativeRanks(nums []int) []string {
temp := make([]int, len(nums))
copy(temp, nums)
sort.Ints(temp)
m := make(map[int]string)
for i := 0; i < len(temp); i++ {
if i == len(temp)-1 {
m[temp[i]] = "Gold Medal"
} else if i == len(temp)-2 {
m[temp[i]] = "Silver Medal"
} else if i == len(temp)-3 {
m[temp[i]] = "Bronze Medal"
} else {
m[temp[i]] = strconv.Itoa(len(temp) - i)
}
}
res := make([]string,0)
for i := 0; i < len(nums); i++ {
res = append(res, m[nums[i]])
}
return res
}
507.完美数(1)
对于一个 正整数，如果它和除了它自身以外的所有正因子之和相等，我们称它为“完美数”。
给定一个 整数 n， 如果他是完美数，返回 True，否则返回 False
示例：输入: 28 输出: True 解释: 28 = 1 + 2 + 4 + 7 + 14
提示：输入的数字 n 不会超过 100,000,000. (1e8)
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^1/2) |
O(1) |
func checkPerfectNumber(num int) bool {
if num == 1 {
return false
}
sum := 1
for i := 2; i <= num/i; i++ {
if num%i == 0 {
sum = sum + i + (num / i)
}
}
return sum == num
}
509.斐波那契数(6)
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。
该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N，计算 F(N)。
示例 1：输入：2输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
示例 2：输入：3输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2.
示例 3：输入：4输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3.
提示：
0 ≤ N ≤ 30
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
遍历+数组 |
O(n) |
O(n) |
| 03 |
递归 |
O(2^n) |
O(n) |
| 04 |
公式法 |
O(1) |
O(1) |
| 05 |
矩阵快速幂 |
O(log(n)) |
O(1) |
| 06 |
矩阵快速幂 |
O(n) |
O(1) |
func fib(N int) int {
if N == 0 {
return 0
}
if N == 1 {
return 1
}
n1, n2 := 0, 1
for i := 2; i <= N; i++ {
n1, n2 = n2, n1+n2
}
return n2
}
#
func fib(N int) int {
if N == 0 {
return 0
}
if N == 1 {
return 1
}
res := make([]int, N+1)
res[0] = 0
res[1] = 1
for i := 2; i <= N; i++ {
res[i] = res[i-1] + res[i-2]
}
return res[N]
}
#
func fib(N int) int {
if N == 0 {
return 0
}
if N == 1 {
return 1
}
return fib(N-1) + fib(N-2)
}
#
func fib(N int) int {
temp1 := (1 + math.Sqrt(5)) / 2
temp2 := (1 - math.Sqrt(5)) / 2
fn := math.Round((math.Pow(temp1, float64(N))- math.Pow(temp2, float64(N)))/ math.Sqrt(5))
return int(fn)
}
# 5
func fib(N int) int {
if N == 0 {
return 0
}
ans := matrix{
a: 1,
b: 0,
c: 0,
d: 1,
}
m := matrix{
a: 1,
b: 1,
c: 1,
d: 0,
}
for N > 0 {
if N%2 == 1 {
ans = multi(ans, m)
}
m = multi(m, m)
N = N >> 1
}
return ans.b
}
type matrix struct {
a, b, c, d int
}
func multi(x, y matrix) matrix {
newA := x.a*y.a + x.b*y.c
newB := x.a*y.b + x.b*y.d
newC := x.c*y.a + x.d*y.c
newD := x.c*y.b + x.d*y.d
return matrix{
a: newA,
b: newB,
c: newC,
d: newD,
}
}
# 6
func fib(N int) int {
if N == 0 {
return 0
}
ans := matrix{
a: 1,
b: 0,
c: 0,
d: 1,
}
m := matrix{
a: 1,
b: 1,
c: 1,
d: 0,
}
for N > 0 {
ans = multi(ans, m)
N--
}
return ans.b
}
type matrix struct {
a, b, c, d int
}
func multi(x, y matrix) matrix {
newA := x.a*y.a + x.b*y.c
newB := x.a*y.b + x.b*y.d
newC := x.c*y.a + x.d*y.c
newD := x.c*y.b + x.d*y.d
return matrix{
a: newA,
b: newB,
c: newC,
d: newD,
}
}
520.检测大写字母(2)
给定一个单词，你需要判断单词的大写使用是否正确。
我们定义，在以下情况时，单词的大写用法是正确的：
全部字母都是大写，比如"USA"。
单词中所有字母都不是大写，比如"leetcode"。
如果单词不只含有一个字母，只有首字母大写， 比如 "Google"。
否则，我们定义这个单词没有正确使用大写字母。
示例 1:输入: "USA"输出: True
示例 2:输入: "FlaG"输出: False
注意: 输入是由大写和小写拉丁字母组成的非空单词。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
正则 |
O(n) |
O(1) |
func detectCapitalUse(word string) bool {
if word == "" {
return false
}
count := 0
for i := 0; i < len(word); i++ {
if word[i] >= 'A' && word[i] <= 'Z' {
count++
}
}
if count == 0 || count == len(word) ||
(count == 1 && word[0] >= 'A' && word[0] <= 'Z') {
return true
}
return false
}
#
func detectCapitalUse(word string) bool {
pattern := "(^[a-z]+)$|(^[A-Z]+)$|(^[A-Z]{1}[a-z]*)$"
isMatch, _ := regexp.MatchString(pattern, word)
return isMatch
}
521.最长特殊序列Ⅰ(1)
给你两个字符串，请你从这两个字符串中找出最长的特殊序列。
「最长特殊序列」定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。
子序列 可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列，任何字符串为其自身的子序列。
输入为两个字符串，输出最长特殊序列的长度。如果不存在，则返回 -1。
示例 1：输入: "aba", "cdc" 输出: 3
解释: 最长特殊序列可为 "aba" (或 "cdc")，两者均为自身的子序列且不是对方的子序列。
示例 2：输入：a = "aaa", b = "bbb"输出：3
示例 3：输入：a = "aaa", b = "aaa"输出：-1
提示：
两个字符串长度均处于区间 [1 - 100] 。
字符串中的字符仅含有 'a'~'z' 。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
比较 |
O(1) |
O(1) |
func findLUSlength(a string, b string) int {
if a == b {
return -1
}
return max(len(a), len(b))
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
530.二叉搜索树的最小绝对差(3)
给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
示例：
输入：
1
\
3
/
2
输出：1
解释：
最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
提示：
树中至少有 2 个节点。
本题与 783 https://leetcode.cn/problems/minimum-distance-between-bst-nodes/ 相同
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归+中序遍历 |
O(n) |
O(log(n)) |
| 02 |
递归+遍历 |
O(n) |
O(n) |
| 03 |
迭代 |
O(n) |
O(n) |
var minDiff, previous int
func getMinimumDifference(root *TreeNode) int {
minDiff, previous = math.MaxInt32, math.MaxInt32
dfs(root)
return minDiff
}
func dfs(root *TreeNode) {
if root == nil {
return
}
dfs(root.Left)
newDiff := diff(previous, root.Val)
if minDiff > newDiff {
minDiff = newDiff
}
previous = root.Val
dfs(root.Right)
}
func diff(a, b int) int {
if a > b {
return a - b
}
return b - a
}
#
func getMinimumDifference(root *TreeNode) int {
arr := make([]int, 0)
dfs(root, &arr)
minDiff := arr[1] - arr[0]
for i := 2; i < len(arr); i++ {
if minDiff > arr[i]-arr[i-1] {
minDiff = arr[i] - arr[i-1]
}
}
return minDiff
}
func dfs(root *TreeNode, arr *[]int) {
if root == nil {
return
}
dfs(root.Left, arr)
*arr = append(*arr, root.Val)
dfs(root.Right, arr)
}
532.数组中的K-diff数对(3)
给定一个整数数组和一个整数 k, 你需要在数组里找到不同的 k-diff 数对。
这里将 k-diff 数对定义为一个整数对 (i, j), 其中 i 和 j 都是数组中的数字，且两数之差的绝对值是 k.
示例 1: 输入: [3, 1, 4, 1, 5], k = 2 输出: 2
解释: 数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。
尽管数组中有两个1，但我们只应返回不同的数对的数量。
示例 2:输入:[1, 2, 3, 4, 5], k = 1 输出: 4
解释: 数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和 (4, 5)。
示例 3:输入: [1, 3, 1, 5, 4], k = 0 输出: 1
解释: 数组中只有一个 0-diff 数对，(1, 1)。
注意:
数对 (i, j) 和数对 (j, i) 被算作同一数对。
数组的长度不超过10,000。
所有输入的整数的范围在 [-1e7, 1e7]。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
单哈希辅助 |
O(n) |
O(n) |
| 02 |
双哈希辅助 |
O(n) |
O(n) |
| 03 |
排序遍历 |
O(nlog(n)) |
O(1) |
func findPairs(nums []int, k int) int {
if k < 0 {
return 0
}
record := make(map[int]int)
for _, num := range nums {
record[num]++
}
res := 0
if k == 0 {
for _, count := range record {
if count > 1 {
res++
}
}
return res
} else {
for n := range record {
if record[n-k] > 0 {
res++
}
}
return res
}
}
#
func findPairs(nums []int, k int) int {
if k < 0 {
return 0
}
m := make(map[int]bool)
res := make(map[int]bool)
for _, value := range nums {
if m[value-k] {
res[value-k] = true
}
if m[value+k] {
res[value] = true
}
m[value] = true
}
return len(res)
}
538.把二叉搜索树转换为累加树(2)
给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，
使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
例如：
输入: 原始二叉搜索树:
5
/ \
2 13
输出: 转换为累加树:
18
/ \
20 13
注意：
本题和 1038: https://leetcode.cn/problems/binary-search-tree-to-greater-sum-tree/ 相同
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(log(n)) |
| 02 |
栈辅助 |
O(n) |
O(n) |
func convertBST(root *TreeNode) *TreeNode {
sum := 0
dfs(root, &sum)
return root
}
func dfs(root *TreeNode, sum *int) {
if root == nil {
return
}
dfs(root.Right, sum)
*sum = *sum + root.Val
root.Val = *sum
dfs(root.Left, sum)
}
#
func convertBST(root *TreeNode) *TreeNode {
if root == nil {
return root
}
stack := make([]*TreeNode, 0)
temp := root
sum := 0
for {
if temp != nil {
stack = append(stack, temp)
temp = temp.Right
} else if len(stack) != 0 {
temp = stack[len(stack)-1]
stack = stack[:len(stack)-1]
temp.Val = temp.Val + sum
sum = temp.Val
temp = temp.Left
} else {
break
}
}
return root
}
541.反转字符串II(2)
给定一个字符串和一个整数 k，你需要对从字符串开头算起的每个 2k 个字符的前k个字符进行反转。
如果剩余少于 k 个字符，则将剩余的所有全部反转。
如果有小于 2k 但大于或等于 k 个字符，则反转前 k 个字符，并将剩余的字符保持原样。
示例:
输入: s = "abcdefg", k = 2
输出: "bacdfeg"
要求:
该字符串只包含小写的英文字母。
给定字符串的长度和 k 在[1, 10000]范围内。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
func reverseStr(s string, k int) string {
arr := []byte(s)
for i := 0; i < len(s); i = i + 2*k {
j := min(i+k, len(s))
reverse(arr[i:j])
}
return string(arr)
}
func reverse(arr []byte) {
i, j := 0, len(arr)-1
for i < j {
arr[i], arr[j] = arr[j], arr[i]
i++
j--
}
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
#
func reverseStr(s string, k int) string {
arr := []byte(s)
for i := 0; i < len(s); i = i + k {
if i%(2*k) == 0 {
j := i + k
if len(arr) < j {
j = len(arr)
}
reverse(arr[i:j])
}
}
return string(arr)
}
func reverse(arr []byte) {
i, j := 0, len(arr)-1
for i < j {
arr[i], arr[j] = arr[j], arr[i]
i++
j--
}
}
543.二叉树的直径(2)
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。
这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(log(n)) |
| 02 |
栈辅助 |
O(n) |
O(n) |
var res int
func diameterOfBinaryTree(root *TreeNode) int {
res = 0
dfs(root)
return res
}
func dfs(root *TreeNode) int {
if root == nil {
return 0
}
left := dfs(root.Left)
right := dfs(root.Right)
path := max(left, right)
res = max(left+right, res)
return path + 1
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
#
func diameterOfBinaryTree(root *TreeNode) int {
if root == nil {
return 0
}
max := 0
stack := make([]*TreeNode, 0)
m := make(map[*TreeNode]int)
cur := root
var prev *TreeNode
for cur != nil || len(stack) != 0 {
for cur != nil {
stack = append(stack, cur)
cur = cur.Left
}
cur = stack[len(stack)-1]
if cur.Right == nil || cur.Right == prev {
cur = stack[len(stack)-1]
stack = stack[:len(stack)-1]
leftLen := 0
rightLen := 0
if v, ok := m[cur.Left]; ok {
leftLen = v
}
if v, ok := m[cur.Right]; ok {
rightLen = v
}
if leftLen > rightLen {
m[cur] = leftLen + 1
} else {
m[cur] = rightLen + 1
}
if max < leftLen+rightLen {
max = leftLen + rightLen
}
prev = cur
cur = nil
} else {
cur = cur.Right
}
}
return max
}
551.学生出勤记录 I(2)
给定一个字符串来代表一个学生的出勤记录，这个记录仅包含以下三个字符：
'A' : Absent，缺勤
'L' : Late，迟到
'P' : Present，到场
如果一个学生的出勤记录中不超过一个'A'(缺勤)并且不超过两个连续的'L'(迟到),那么这个学生会被奖赏。
你需要根据这个学生的出勤记录判断他是否会被奖赏。
示例 1:输入: "PPALLP"输出: True
示例 2:输入: "PPALLL"输出: False
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
内置函数 |
O(n) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
func checkRecord(s string) bool {
if strings.Count(s, "A") <= 1 && strings.Count(s, "LLL") == 0 {
return true
}
return false
}
#
func checkRecord(s string) bool {
aNum := 0
lNum := 0
for i := 0; i < len(s); i++ {
if s[i] == 'A' {
aNum++
}
if s[i] == 'L' {
lNum++
} else {
lNum = 0
}
if aNum == 2 {
return false
}
if lNum == 3 {
return false
}
}
return true
}
557.反转字符串中的单词 III(2)
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
示例 1:
输入: "Let's take LeetCode contest"
输出: "s'teL ekat edoCteeL tsetnoc"
注意：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
内置函数 |
O(n) |
O(n) |
| 02 |
遍历 |
O(n) |
O(n) |
func reverseWords(s string) string {
strS := strings.Split(s, " ")
for i, s := range strS {
strS[i] = reverse(s)
}
return strings.Join(strS, " ")
}
func reverse(s string) string {
arr := []byte(s)
i, j := 0, len(arr)-1
for i < j {
arr[i], arr[j] = arr[j], arr[i]
i++
j--
}
return string(arr)
}
#
func reverseWords(s string) string {
arr := []byte(s)
j := 0
for i := 0; i < len(arr); i++ {
if arr[i] == ' ' {
reverse(arr, j, i-1)
j = i + 1
}
}
reverse(arr, j, len(arr)-1)
return string(arr)
}
func reverse(arr []byte, i, j int) []byte {
for i < j {
arr[i], arr[j] = arr[j], arr[i]
i++
j--
}
return arr
}
559.N叉树的最大深度(2)
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
例如，给定一个 3叉树 :
我们应返回其最大深度，3。
说明:
树的深度不会超过 1000。
树的节点总不会超过 5000。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(log(n)) |
| 02 |
迭代 |
O(n) |
O(n) |
func maxDepth(root *Node) int {
if root == nil {
return 0
}
depth := 0
for _, node := range root.Children {
depth = max(depth, maxDepth(node))
}
return depth + 1
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
#
func maxDepth(root *Node) int {
if root == nil {
return 0
}
queue := make([]*Node, 0)
depth := 0
queue = append(queue, root)
for len(queue) > 0 {
length := len(queue)
for i := 0; i < length; i++ {
temp := queue[0]
for _, node := range temp.Children {
queue = append(queue, node)
}
queue = queue[1:]
}
depth++
}
return depth
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
561.数组拆分 I(2)
给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，
使得从1 到 n 的 min(ai, bi) 总和最大。
示例 1:输入: [1,4,3,2]输出: 4
解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).
提示:
n 是正整数,范围在 [1, 10000].
数组中的元素范围在 [-10000, 10000].
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序遍历 |
O(nlog(n)) |
P |
| 02 |
数组辅助 |
O(n) |
O(1) |
func arrayPairSum(nums []int) int {
sort.Ints(nums)
sum := 0
for k, v := range nums {
if k%2 == 0 {
sum = sum + v
}
}
return sum
}
#
func arrayPairSum(nums []int) int {
var arr [20010]int
for _, num := range nums {
arr[num+10000]++
}
sum := 0
needAdd := true
for num, count := range arr {
for count > 0 {
if needAdd {
sum = sum + num - 10000
}
needAdd = !needAdd
count--
}
}
return sum
}
563.二叉树的坡度(2)
给定一个二叉树，计算整个树的坡度。
一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。
整个树的坡度就是其所有节点的坡度之和。
示例:
输入:
1
/ \
2 3
输出: 1
解释:
结点的坡度 2 : 0
结点的坡度 3 : 0
结点的坡度 1 : |2-3| = 1
树的坡度 : 0 + 0 + 1 = 1
注意:
任何子树的结点的和不会超过32位整数的范围。
坡度的值不会超过32位整数的范围。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(log(n)) |
| 02 |
迭代 |
O(n) |
O(n) |
var total int
func findTilt(root *TreeNode) int {
total = 0
dfs(root)
return total
}
func dfs(root *TreeNode) int {
if root == nil {
return 0
}
left := dfs(root.Left)
right := dfs(root.Right)
total = total + abs(left, right)
return left + right + root.Val
}
func abs(a, b int) int {
if a > b {
return a - b
}
return b - a
}
#
func findTilt(root *TreeNode) int {
if root == nil {
return 0
}
stack := make([]*TreeNode, 0)
stack = append(stack, root)
list := make([]*TreeNode, 0)
total := 0
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[0 : len(stack)-1]
list = append([]*TreeNode{node}, list...)
if node.Left != nil {
stack = append(stack, node.Left)
}
if node.Right != nil {
stack = append(stack, node.Right)
}
}
for i := range list {
node := list[i]
left := 0
right := 0
if node.Left != nil {
left = node.Left.Val
}
if node.Right != nil {
right = node.Right.Val
}
total = total + abs(left, right)
node.Val = left + right + node.Val
}
return total
}
func abs(a, b int) int {
if a > b {
return a - b
}
return b - a
}
566.重塑矩阵(2)
在MATLAB中，有一个非常有用的函数 reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。
给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。
重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。
如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。
示例 1:输入:
nums =
[[1,2],
[3,4]]
r = 1, c = 4
输出:
[[1,2,3,4]]
解释:行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。
示例 2:输入:
nums =
[[1,2],
[3,4]]
r = 2, c = 4
输出:
[[1,2],
[3,4]]
解释:没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。
注意：
给定矩阵的宽和高范围在 [1, 100]。
给定的 r 和 c 都是正数。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^2) |
O(n^2) |
| 02 |
遍历 |
O(n^2) |
O(n^2) |
func matrixReshape(nums [][]int, r int, c int) [][]int {
row, col := len(nums), len(nums[0])
if (row*col != r*c) || (row == r && col == c) {
return nums
}
res := make([][]int, r)
for i := 0; i < len(res); i++ {
res[i] = make([]int, c)
}
for i := 0; i < r*c; i++ {
res[i/c][i%c] = nums[i/col][i%col]
}
return res
}
#
func matrixReshape(nums [][]int, r int, c int) [][]int {
row, col := len(nums), len(nums[0])
if (row*col != r*c) || (row == r && col == c) {
return nums
}
res := make([][]int, 0)
arr := make([]int, 0)
count := 0
for _, num := range nums {
for _, value := range num {
arr = append(arr, value)
count++
if count == c {
res = append(res, arr)
arr = []int{}
count = 0
}
}
}
return res
}
572.另一个树的子树(3)
给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。
s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1:
给定的树 s:
3
/ \
4 5
/ \
1 2
给定的树 t：
4
/ \
1 2
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
示例 2:
给定的树 s：
3
/ \
4 5
/ \
1 2
/
0
给定的树 t：
4
/ \
1 2
返回 false。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n^2) |
O(log(n)) |
| 02 |
递归+字符串辅助 |
O(n) |
O(log(n)) |
| 03 |
栈辅助 |
O(n) |
O(n) |
func isSubtree(s *TreeNode, t *TreeNode) bool {
if s == nil {
return false
}
return isSame(s, t) || isSubtree(s.Left, t) || isSubtree(s.Right, t)
}
func isSame(s *TreeNode, t *TreeNode) bool {
if s == nil || t == nil{
return t == s
}
return isSame(s.Left, t.Left) && isSame(s.Right, t.Right) && s.Val == t.Val
}
#
func isSubtree(s *TreeNode, t *TreeNode) bool {
sStr := dfs(s, "")
tStr := dfs(t, "")
return strings.Contains(sStr, tStr)
}
func dfs(s *TreeNode, pre string) string {
if s == nil {
return pre
}
return fmt.Sprintf("#%d%s%s", s.Val, dfs(s.Left, "l"), dfs(s.Right, "r"))
}
#
func isSubtree(s *TreeNode, t *TreeNode) bool {
sStr := preOrder(s)
tStr := preOrder(t)
return strings.Contains(sStr, tStr)
}
func preOrder(root *TreeNode) string {
if root == nil {
return ""
}
res := "!"
stack := make([]*TreeNode,0)
temp := root
for {
for temp != nil{
res += strconv.Itoa(temp.Val)
res += "!"
stack = append(stack, temp)
temp = temp.Left
}
res += "#!"
if len(stack) > 0{
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
temp = node.Right
}else {
break
}
}
return res
}
575.分糖果(2)
给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。
你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。
示例 1:输入: candies = [1,1,2,2,3,3] 输出: 3
解析: 一共有三种种类的糖果，每一种都有两个。
最优分配方案：妹妹获得[1,2,3],弟弟也获得[1,2,3]。这样使妹妹获得糖果的种类数最多。
示例 2 : 输入: candies = [1,1,2,3] 输出: 2
解析: 妹妹获得糖果[2,3],弟弟获得糖果[1,1]，妹妹有两种不同的糖果，弟弟只有一种。
这样使得妹妹可以获得的糖果种类数最多。
注意:
数组的长度为[2, 10,000]，并且确定为偶数。
数组中数字的大小在范围[-100,000, 100,000]内。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n) |
O(n) |
| 02 |
排序遍历 |
O(nlog(n)) |
O(1) |
func distributeCandies(candies []int) int {
n := len(candies)
r := make(map[int]bool, n)
for _, c := range candies {
r[c] = true
}
return min(len(r), n/2)
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
#
func distributeCandies(candies []int) int {
length := len(candies)
half := length / 2
count := 1
sort.Ints(candies)
for i := 1; i < length; i++ {
if candies[i] != candies[i-1] {
count++
}
}
if count >= half {
return half
}
return count
}
581.最短无序连续子数组(3)
给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
你找到的子数组应是最短的，请输出它的长度。
示例 1:输入: [2, 6, 4, 8, 10, 9, 15] 输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
说明 :
输入的数组长度范围在 [1, 10,000]。
输入的数组可能包含重复元素 ，所以升序的意思是<=。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双指针 |
O(n) |
O(1) |
| 02 |
2次遍历 |
O(n) |
O(1) |
| 03 |
排序遍历 |
O(nlog(n)) |
O(n) |
func findUnsortedSubarray(nums []int) int {
length := len(nums)
left, right := 0, -1
min, max := nums[length-1], nums[0]
for i := 1; i < length; i++ {
if max <= nums[i] {
max = nums[i]
} else {
right = i
}
j := length - i - 1
if min >= nums[j] {
min = nums[j]
} else {
left = j
}
}
return right - left + 1
}
#
func findUnsortedSubarray(nums []int) int {
length := len(nums)
right := -1
max := nums[0]
for i := 1; i < length; i++ {
if max <= nums[i] {
max = nums[i]
} else {
right = i
}
}
if right == 0 {
return 0
}
left := 0
min := nums[length-1]
for i := length - 2; i >= 0; i-- {
if min >= nums[i] {
min = nums[i]
} else {
left = i
}
}
return right - left + 1
}
#
func findUnsortedSubarray(nums []int) int {
temp := make([]int,len(nums))
copy(temp,nums)
sort.Ints(temp)
i, j := 0, len(nums)-1
for i < len(nums) && nums[i] == temp[i]{
i++
}
for i+1 < j && nums[j] == temp[j]{
j--
}
return j-i+1
}
589.N叉树的前序遍历(2)
给定一个 N 叉树，返回其节点值的前序遍历。
例如，给定一个 3叉树 :
返回其前序遍历: [1,3,5,6,2,4]。
说明: 递归法很简单，你可以使用迭代法完成此题吗?
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(log(n)) |
| 02 |
迭代 |
O(n) |
O(n) |
var res []int
func preorder(root *Node) []int {
res = make([]int, 0)
dfs(root)
return res
}
func dfs(root *Node) {
if root == nil {
return
}
res = append(res, root.Val)
for _, value := range root.Children {
dfs(value)
}
}
#
func preorder(root *Node) []int {
res := make([]int, 0)
if root == nil {
return res
}
stack := make([]*Node, 0)
stack = append(stack, root)
for len(stack) > 0 {
temp := stack[len(stack)-1]
stack = stack[:len(stack)-1]
res = append(res, temp.Val)
for i := len(temp.Children) - 1; i >= 0; i-- {
stack = append(stack, temp.Children[i])
}
}
return res
}
590.N叉树的后序遍历(2)
给定一个 N 叉树，返回其节点值的后序遍历。
例如，给定一个 3叉树 :
返回其后序遍历: [5,6,3,2,4,1].
说明: 递归法很简单，你可以使用迭代法完成此题吗?
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(log(n)) |
| 02 |
迭代 |
O(n) |
O(n) |
var res []int
func postorder(root *Node) []int {
res = make([]int, 0)
dfs(root)
return res
}
func dfs(root *Node) {
if root == nil {
return
}
for _, value := range root.Children {
dfs(value)
}
res = append(res, root.Val)
}
#
func postorder(root *Node) []int {
res := make([]int, 0)
if root == nil {
return res
}
stack := make([]*Node, 0)
stack = append(stack, root)
for len(stack) > 0 {
temp := stack[len(stack)-1]
stack = stack[:len(stack)-1]
res = append(res, temp.Val)
for i := 0; i < len(temp.Children); i++ {
stack = append(stack, temp.Children[i])
}
}
for i := 0; i < len(res)/2; i++ {
res[i], res[len(res)-1-i] = res[len(res)-1-i], res[i]
}
return res
}
594.最长和谐子序列(2)
和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。
现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度。
示例 1:输入: [1,3,2,2,5,2,3,7]输出: 5
原因: 最长的和谐数组是：[3,2,2,2,3].
说明: 输入的数组长度最大不超过20,000.
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n) |
O(n) |
| 02 |
排序遍历 |
O(nlog(n)) |
O(1) |
func findLHS(nums []int) int {
m := make(map[int]int, len(nums))
for _, n := range nums {
m[n]++
}
res := 0
for key, value := range m {
value2, ok := m[key+1]
if ok {
t := value + value2
if res < t {
res = t
}
}
}
return res
}
#
func findLHS(nums []int) int {
sort.Ints(nums)
res := 0
left := 0
for i := 0; i < len(nums); i++ {
for nums[i]-nums[left] > 1 {
left++
}
if nums[i]-nums[left] == 1 {
if res < i-left+1 {
res = i - left + 1
}
}
}
return res
}
598.范围求和 II(1)
给定一个初始元素全部为 0，大小为 m*n 的矩阵 M 以及在 M 上的一系列更新操作。
操作用二维数组表示，其中的每个操作用一个含有两个正整数 a 和 b 的数组表示，
含义是将所有符合 0 <= i < a 以及 0 <= j < b 的元素 M[i][j] 的值都增加 1。
在执行给定的一系列操作后，你需要返回矩阵中含有最大整数的元素个数。
示例 1:输入: m = 3, n = 3operations = [[2,2],[3,3]] 输出: 4
解释: 初始状态, M =
[[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]
执行完操作 [2,2] 后, M =
[[1, 1, 0],
[1, 1, 0],
[0, 0, 0]]
执行完操作 [3,3] 后, M =
[[2, 2, 1],
[2, 2, 1],
[1, 1, 1]]
M 中最大的整数是 2, 而且 M 中有4个值为2的元素。因此返回 4。
注意:
m 和 n 的范围是 [1,40000]。
a 的范围是 [1,m]，b 的范围是 [1,n]。
操作数目不超过 10000。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数学 |
O(n) |
O(1) |
func maxCount(m int, n int, ops [][]int) int {
for _, o := range ops {
m = min(m, o[0])
n = min(n, o[1])
}
return m * n
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
599.两个列表的最小索引总和(2)
假设Andy和Doris想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。
你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。
你可以假设总是存在一个答案。
示例 1:输入:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
输出: ["Shogun"]
解释: 他们唯一共同喜爱的餐厅是“Shogun”。
示例 2:
输入:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]
输出: ["Shogun"]
解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。
提示:
两个列表的长度范围都在 [1, 1000]内。
两个列表中的字符串的长度将在[1，30]的范围内。
下标从0开始，到列表的长度减1。
两个列表都没有重复的元素。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n) |
O(n) |
| 02 |
暴力法 |
O(n^2) |
I |
func findRestaurant(list1 []string, list2 []string) []string {
if len(list1) > len(list2) {
list1, list2 = list2, list1
}
m2 := make(map[string]int, len(list2))
for i := range list2 {
m2[list2[i]] = i
}
min := 2000
res := make([]string, 0, 1000)
for key, value := range list1 {
if key2, ok := m2[value]; ok {
if min == key+key2 {
res = append(res, value)
}
if min > key+key2 {
min = key + key2
res = []string{value}
}
}
}
return res
}
#
func findRestaurant(list1 []string, list2 []string) []string {
min := 2000
res := make([]string, 0, 1000)
for key1, value1 := range list1 {
for key2, value2 := range list2{
if value1 == value2{
if min == key1+key2 {
res = append(res, value1)
}
if min > key1+key2 {
min = key1 + key2
res = []string{value1}
}
}
}
}
return res
}
0501-0600-Medium
503.下一个更大元素II(2)
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。
数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，
这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
示例 1:输入: [1,2,1] 输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
注意: 输入数组的长度不会超过 10000。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
单调栈 |
O(n) |
O(n) |
| 02 |
单调栈 |
O(n) |
O(n) |
func nextGreaterElements(nums []int) []int {
res := make([]int, len(nums))
if len(nums) == 0 {
return res
}
for i := 0; i < len(nums); i++ {
res[i] = -1
}
stack := make([]int, 0)
for i := 0; i < len(nums)*2; i++ {
index := i % len(nums)
for len(stack) > 0 && nums[index] > nums[stack[len(stack)-1]] {
if res[stack[len(stack)-1]] == -1 {
res[stack[len(stack)-1]] = nums[index]
}
stack = stack[:len(stack)-1]
}
stack = append(stack, index)
}
return res
}
# 2
func nextGreaterElements(nums []int) []int {
res := make([]int, len(nums))
if len(nums) == 0 {
return res
}
stack := make([]int, 0)
for i := 2*len(nums) - 1; i >= 0; i-- {
index := i % len(nums)
for len(stack) > 0 && nums[index] >= stack[len(stack)-1] {
stack = stack[:len(stack)-1]
}
if len(stack) == 0 {
res[index] = -1
} else {
res[index] = stack[len(stack)-1]
}
stack = append(stack, nums[index])
}
return res
}
508.出现次数最多的子树元素和(1)
给你一个二叉树的根结点，请你找出出现次数最多的子树元素和。
一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。
你需要返回出现次数最多的子树元素和。
如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。
示例 1：输入:
5
/ \
2 -3
返回[2, -3, 4]，所有的值均只出现一次，以任意顺序返回所有值。
示例2：输入：
5
/ \
2 -5
返回[2]，只有 2 出现两次，-5 只出现 1 次。
提示：假设任意子树元素和均可以用 32 位有符号整数表示。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(n) |
var m map[int]int
func findFrequentTreeSum(root *TreeNode) []int {
m = make(map[int]int)
res := make([]int, 0)
dfs(root)
maxValue := 0
for k, v := range m {
if v > maxValue {
maxValue = v
res = []int{k}
} else if maxValue == v {
res = append(res, k)
}
}
return res
}
func dfs(root *TreeNode) int {
if root == nil {
return 0
}
sum := root.Val + dfs(root.Left) + dfs(root.Right)
m[sum]++
return sum
}
513.找树左下角的值(2)
给定一个二叉树，在树的最后一行找到最左边的值。
示例 1:输入:
2
/ \
1 3
输出:1
示例 2:输入:
1
/ \
2 3
/ / \
4 5 6
/
7
输出:7
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
层序遍历 |
O(n) |
O(n) |
| 02 |
递归 |
O(n) |
O(log(n)) |
func findBottomLeftValue(root *TreeNode) int {
res := 0
queue := make([]*TreeNode, 0)
queue = append(queue, root)
for len(queue) > 0 {
length := len(queue)
res = queue[0].Val
for i := 0; i < length; i++ {
if queue[i].Left != nil {
queue = append(queue, queue[i].Left)
}
if queue[i].Right != nil {
queue = append(queue, queue[i].Right)
}
}
queue = queue[length:]
}
return res
}
# 2
var res int
var maxLevel int
func findBottomLeftValue(root *TreeNode) int {
res = 0
maxLevel = -1
if root == nil {
return res
}
dfs(root, 0)
return res
}
func dfs(root *TreeNode, level int) {
if root == nil {
return
}
dfs(root.Left, level+1)
if level > maxLevel {
maxLevel = level
res = root.Val
}
dfs(root.Right, level+1)
}
515.在每个树行中找最大值(2)
您需要在二叉树的每一行中找到最大的值。
示例：输入:
1
/ \
3 2
/ \ \
5 3 9
输出: [1, 3, 9]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
层序遍历 |
O(n) |
O(n) |
| 02 |
递归 |
O(n) |
O(n) |
func largestValues(root *TreeNode) []int {
res := make([]int, 0)
if root == nil {
return res
}
queue := make([]*TreeNode, 0)
queue = append(queue, root)
for len(queue) > 0 {
length := len(queue)
maxValue := math.MinInt32
for i := 0; i < length; i++ {
if queue[i].Left != nil {
queue = append(queue, queue[i].Left)
}
if queue[i].Right != nil {
queue = append(queue, queue[i].Right)
}
if maxValue < queue[i].Val {
maxValue = queue[i].Val
}
}
res = append(res, maxValue)
queue = queue[length:]
}
return res
}
# 2
var res []int
func largestValues(root *TreeNode) []int {
res = make([]int, 0)
if root == nil {
return res
}
dfs(root, 0)
return res
}
func dfs(root *TreeNode, level int) {
if root == nil {
return
}
if level >= len(res) {
res = append(res, math.MinInt32)
}
res[level] = max(res[level], root.Val)
dfs(root.Left, level+1)
dfs(root.Right, level+1)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
516.最长回文子序列(3)
给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
示例 1:输入:"bbbab"输出:4
一个可能的最长回文子序列为 "bbbb"。
示例 2:输入:"cbbd"输出:2
一个可能的最长回文子序列为 "bb"。
提示：
1 <= s.length <= 1000
s 只包含小写英文字母
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n^2) |
| 02 |
动态规划 |
O(n^2) |
O(n) |
| 03 |
递归 |
O(n^2) |
O(n^2) |
func longestPalindromeSubseq(s string) int {
if len(s) <= 1 {
return len(s)
}
n := len(s)
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, n)
dp[i][i] = 1
}
for i := n - 2; i >= 0; i-- {
for j := i + 1; j < n; j++ {
if s[i] == s[j] {
dp[i][j] = dp[i+1][j-1] + 2
} else {
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
}
}
}
return dp[0][n-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func longestPalindromeSubseq(s string) int {
if len(s) <= 1 {
return len(s)
}
n := len(s)
dp := make([]int, n)
for i := 0; i < n; i++ {
dp[i] = 1
}
for i := n - 1; i >= 0; i-- {
prev := 0
for j := i + 1; j < n; j++ {
temp := dp[j]
if s[i] == s[j] {
dp[j] = prev + 2
} else {
dp[j] = max(dp[j], dp[j-1])
}
prev = temp
}
}
return dp[n-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 3
var dp [][]int
func longestPalindromeSubseq(s string) int {
if len(s) <= 1 {
return len(s)
}
n := len(s)
dp = make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, n)
}
return dfs(s, 0, n-1)
}
func dfs(s string, i, j int) int {
if i == j {
return 1
}
if i > j {
return 0
}
if dp[i][j] > 0 {
return dp[i][j]
}
if s[i] == s[j] {
dp[i][j] = dfs(s, i+1, j-1) + 2
} else {
dp[i][j] = max(dfs(s, i+1, j), dfs(s, i, j-1))
}
return dp[i][j]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
518.零钱兑换II(2)
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:输入: amount = 5, coins = [1, 2, 5] 输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:输入: amount = 3, coins = [2] 输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:输入: amount = 10, coins = [10] 输出: 1
注意:你可以假设：
0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划-二维 |
O(n^2) |
O(n^2) |
| 02 |
动态规划-一维 |
O(n^2) |
O(n) |
func change(amount int, coins []int) int {
n := len(coins)
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, amount+1)
dp[i][0] = 1
}
for i := 1; i <= n; i++ {
for j := 1; j <= amount; j++ {
if j-coins[i-1] >= 0 {
dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
} else {
dp[i][j] = dp[i-1][j]
}
}
}
return dp[n][amount]
}
# 2
func change(amount int, coins []int) int {
n := len(coins)
dp := make([]int, amount+1)
dp[0] = 1
for i := 1; i <= n; i++ {
for j := 1; j <= amount; j++ {
if j-coins[i-1] >= 0 {
dp[j] = dp[j] + dp[j-coins[i-1]]
}
}
}
return dp[amount]
}
519.随机翻转矩阵(1)
题中给出一个 n_rows 行 n_cols 列的二维矩阵，且所有值被初始化为 0。
要求编写一个 flip 函数，均匀随机的将矩阵中的 0 变为 1，并返回该值的位置下标 [row_id,col_id]；
同样编写一个 reset 函数，将所有的值都重新置为 0。
尽量最少调用随机函数 Math.random()，并且优化时间和空间复杂度。
注意:1 <= n_rows, n_cols <= 10000
0 <= row.id < n_rows 并且 0 <= col.id < n_cols
当矩阵中没有值为 0 时，不可以调用 flip 函数
调用 flip 和 reset 函数的次数加起来不会超过 1000 次
示例 1：输入: ["Solution","flip","flip","flip","flip"] [[2,3],[],[],[],[]]
输出: [null,[0,1],[1,2],[1,0],[1,1]]
示例 2：输入: ["Solution","flip","flip","reset","flip"] [[1,2],[],[],[],[]]
输出: [null,[0,0],[0,1],null,[0,0]]
输入语法解释：
输入包含两个列表：被调用的子程序和他们的参数。Solution 的构造函数有两个参数，分别为 n_rows 和 n_cols。
flip和 reset 没有参数，参数总会以列表形式给出，哪怕该列表为空
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n) |
O(n) |
type Solution struct {
m map[int]bool
rows int
cols int
total int
}
func Constructor(n_rows int, n_cols int) Solution {
return Solution{
m: make(map[int]bool),
rows: n_rows,
cols: n_cols,
total: 0,
}
}
func (this *Solution) Flip() []int {
if this.total >= this.rows*this.cols {
return nil
}
for {
index := rand.Intn(this.rows * this.cols)
if this.m[index] == true {
continue
}
a, b := index/this.cols, index%this.cols
this.m[index] = true
this.total++
return []int{a, b}
}
}
func (this *Solution) Reset() {
this.m = make(map[int]bool)
this.total = 0
}
522.最长特殊序列II(3)
给定字符串列表，你需要从它们中找出最长的特殊序列。
最长特殊序列定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。
子序列可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。
空序列为所有字符串的子序列，任何字符串为其自身的子序列。
输入将是一个字符串列表，输出是最长特殊序列的长度。如果最长特殊序列不存在，返回 -1 。
示例：输入: "aba", "cdc", "eae" 输出: 3
提示：所有给定的字符串长度不会超过 10 。
给定字符串列表的长度将在 [2, 50 ] 之间。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(2^n) |
O(2^n) |
| 02 |
暴力法 |
O(n^2) |
O(1) |
| 03 |
暴力法 |
O(n^2) |
O(1) |
func findLUSlength(strs []string) int {
m := make(map[string]int)
for i := 0; i < len(strs); i++ {
total := 1 << (len(strs[i]))
for j := 0; j < total; j++ {
s := ""
for k := 0; k < len(strs[i]); k++ {
if (j>>k)&1 != 0 {
s = s + string(strs[i][k])
}
}
m[s]++
}
}
res := -1
for k, v := range m {
if v == 1 && len(k) > res {
res = len(k)
}
}
return res
}
# 2
func findLUSlength(strs []string) int {
res := -1
var j int
for i := 0; i < len(strs); i++ {
for j = 0; j < len(strs); j++ {
if i == j {
continue
}
if judge(strs[i], strs[j]) == true {
break
}
}
if j == len(strs) && len(strs[i]) > res {
res = len(strs[i])
}
}
return res
}
func judge(a, b string) bool {
j := 0
for i := 0; i < len(b) && j < len(a); i++ {
if a[j] == b[i] {
j++
}
}
return j == len(a)
}
# 3
func findLUSlength(strs []string) int {
sort.Slice(strs, func(i, j int) bool {
return len(strs[i]) > len(strs[j])
})
res := -1
var j int
for i := 0; i < len(strs); i++ {
for j = 0; j < len(strs); j++ {
if i == j {
continue
}
if judge(strs[i], strs[j]) == true {
break
}
}
if j == len(strs) {
return len(strs[i])
}
}
return res
}
func judge(a, b string) bool {
j := 0
for i := 0; i < len(b) && j < len(a); i++ {
if a[j] == b[i] {
j++
}
}
return j == len(a)
}
523.连续的子数组和(2)
给定一个包含 非负数 的数组和一个目标 整数 k，编写一个函数来判断该数组是否含有连续的子数组，
其大小至少为 2，且总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。
示例 1：输入：[23,2,4,6,7], k = 6 输出：True
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6。
示例 2：输入：[23,2,6,4,7], k = 6 输出：True
解释：[23,2,6,4,7]是大小为 5 的子数组，并且和为 42。
说明：
数组的长度不会超过 10,000 。
你可以认为所有数字总和在 32 位有符号整数范围内。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n) |
O(n) |
| 02 |
前缀和-暴力法 |
O(n^2) |
O(n) |
func checkSubarraySum(nums []int, k int) bool {
if len(nums) == 0 {
return false
}
m := make(map[int]int)
m[0] = -1
sum := 0
for i := 0; i < len(nums); i++ {
sum = sum + nums[i]
if k != 0 {
sum = sum % k
}
if _, ok := m[sum]; ok {
if i-m[sum] >= 2 {
return true
}
} else {
m[sum] = i
}
}
return false
}
# 2
func checkSubarraySum(nums []int, k int) bool {
if len(nums) == 0 {
return false
}
arr := make([]int, len(nums))
arr[0] = nums[0]
for i := 1; i < len(nums); i++ {
arr[i] = arr[i-1] + nums[i]
}
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
sum := arr[j] - arr[i] + nums[i]
if sum == k || (k != 0 && sum%k == 0) {
return true
}
}
}
return false
}
524.通过删除字母匹配到字典里最长单词(2)
给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。
示例 1：输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"] 输出："apple"
示例 2：输入：s = "abpcplea", dictionary = ["a","b","c"] 输出："a"
提示：1 <= s.length <= 1000
1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 1000
s 和 dictionary[i] 仅由小写英文字母组成
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序+子序列 |
O(n^2) |
O(1) |
| 02 |
子序列 |
O(n^2) |
O(n) |
func findLongestWord(s string, dictionary []string) string {
sort.Slice(dictionary, func(i, j int) bool {
if len(dictionary[i]) == len(dictionary[j]) {
return dictionary[i] < dictionary[j]
}
return len(dictionary[i]) > len(dictionary[j])
})
for i := 0; i < len(dictionary); i++ {
if isSubsequence(dictionary[i], s) {
return dictionary[i]
}
}
return ""
}
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)
}
# 2
func findLongestWord(s string, dictionary []string) string {
res := ""
for i := 0; i < len(dictionary); i++ {
if isSubsequence(dictionary[i], s) {
if len(dictionary[i]) > len(res) ||
(len(dictionary[i]) == len(res) && dictionary[i] < res) {
res = dictionary[i]
}
}
}
return res
}
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)
}
525.连续数组(1)
给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。
示例 1:输入: [0,1] 输出: 2
说明: [0, 1] 是具有相同数量0和1的最长连续子数组。
示例 2:输入: [0,1,0] 输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。
注意:给定的二进制数组的长度不会超过50000。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
前缀和 |
O(n) |
O(n) |
func findMaxLength(nums []int) int {
res := 0
m := make(map[int]int)
m[0] = -1
total := 0
for i := 0; i < len(nums); i++ {
if nums[i] == 0 {
total--
} else {
total++
}
if first, ok := m[total]; !ok {
m[total] = i
} else {
if i-first > res {
res = i - first
}
}
}
return res
}
526.优美的排列(2)
假设有从 1 到 N 的N个整数，如果从这N个数字中成功构造出一个数组，
使得数组的第 i位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一个优美的排列。条件：
第i位的数字能被i整除
i 能被第 i 位上的数字整除
现在给定一个整数 N，请问可以构造多少个优美的排列？
示例1:输入: 2 输出: 2
解释:
第 1 个优美的排列是 [1, 2]:
第 1 个位置（i=1）上的数字是1，1能被 i（i=1）整除
第 2 个位置（i=2）上的数字是2，2能被 i（i=2）整除
第 2 个优美的排列是 [2, 1]:
第 1 个位置（i=1）上的数字是2，2能被 i（i=1）整除
第 2 个位置（i=2）上的数字是1，i（i=2）能被 1 整除
说明:N 是一个正整数，并且不会超过15。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
回溯 |
O(n^n) |
O(n!) |
| 02 |
回溯 |
O(n^n) |
O(n) |
var res [][]int
func countArrangement(n int) int {
res = make([][]int, 0)
dfs(n, make([]int, 0), make([]bool, n+1))
fmt.Println(res)
return len(res)
}
func dfs(n int, path []int, visited []bool) {
if len(path) == n {
temp := make([]int, len(path))
copy(temp, path)
res = append(res, temp)
return
}
for i := 1; i <= n; i++ {
index := len(path) + 1
if visited[i] == false && (i%index == 0 || index%i == 0) {
visited[i] = true
dfs(n, append(path, i), visited)
visited[i] = false
}
}
}
# 2
var res int
func countArrangement(n int) int {
res = 0
dfs(n, make([]int, 0), make([]bool, n+1))
return res
}
func dfs(n int, path []int, visited []bool) {
if len(path) == n {
res++
return
}
for i := 1; i <= n; i++ {
index := len(path) + 1
if visited[i] == false && (i%index == 0 || index%i == 0) {
visited[i] = true
dfs(n, append(path, i), visited)
visited[i] = false
}
}
}
528.按权重随机选择(1)
给定一个正整数数组w ，其中w[i]代表下标 i的权重（下标从 0 开始），
请写一个函数pickIndex，它可以随机地获取下标 i，选取下标 i的概率与w[i]成正比。
例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3)= 0.25 （即，25%），
而选取下标 1 的概率为 3 / (1 + 3)= 0.75（即，75%）。
也就是说，选取下标 i 的概率为 w[i] / sum(w) 。
示例 1：输入：["Solution","pickIndex"] [[[1]],[]]输出： [null,0]
解释：Solution solution = new Solution([1]);
solution.pickIndex(); // 返回 0，因为数组中只有一个元素，所以唯一的选择是返回下标 0。
示例 2：输入： ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
输出：[null,1,1,1,1,0]
解释：Solution solution = new Solution([1, 3]);
solution.pickIndex(); // 返回 1，返回下标 1，返回该下标概率为 3/4 。
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 0，返回下标 0，返回该下标概率为 1/4 。
由于这是一个随机问题，允许多个答案，因此下列输出都可以被认为是正确的:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
诸若此类。
提示：1 <= w.length <= 10000
1 <= w[i] <= 10^5
pickIndex将被调用不超过10000次
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
前缀和+二分查找 |
O(n) |
O(n) |
type Solution struct {
nums []int
total int
}
func Constructor(w []int) Solution {
total := 0
arr := make([]int, len(w))
for i := 0; i < len(w); i++ {
total = total + w[i]
arr[i] = total
}
return Solution{
nums: arr,
total: total,
}
}
func (this *Solution) PickIndex() int {
target := rand.Intn(this.total)
left, right := 0, len(this.nums)
for left < right {
mid := left + (right-left)/2
if this.nums[mid] <= target {
left = mid + 1
} else {
right = mid
}
}
return left
}
529.扫雷游戏(2)
让我们一起来玩扫雷游戏！
给定一个代表游戏板的二维字符矩阵。 'M' 代表一个未挖出的地雷，'E' 代表一个未挖出的空方块，
'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，
数字（'1' 到 '8'）表示有多少地雷与这块已挖出的方块相邻，'X' 则表示一个已挖出的地雷。
现在给出在所有未挖出的方块中（'M'或者'E'）的下一个点击位置（行和列索引），根据以下规则，
返回相应位置被点击后对应的面板：
如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为 'X'。
如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），
并且所有和其相邻的未挖出方块都应该被递归地揭露。
如果一个至少与一个地雷相邻的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。
如果在此次点击中，若无更多方块可被揭露，则返回面板。
示例 1：输入: [['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'M', 'E', 'E'],
['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'E', 'E', 'E']]
Click : [3,0]
输出: [['B', '1', 'E', '1', 'B'],
['B', '1', 'M', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
解释:示例 2：输入:
[['B', '1', 'E', '1', 'B'],
['B', '1', 'M', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
Click : [1,2]
输出:
[['B', '1', 'E', '1', 'B'],
['B', '1', 'X', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
解释:
注意：输入矩阵的宽和高的范围为 [1,50]。
点击的位置只能是未被挖出的方块 ('M' 或者 'E')，这也意味着面板至少包含一个可点击的方块。
输入面板不会是游戏结束的状态（即有地雷已被挖出）。
简单起见，未提及的规则在这个问题中可被忽略。
例如，当游戏结束时你不需要挖出所有地雷，考虑所有你可能赢得游戏或标记方块的情况。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
深度优先搜索 |
O(n^2) |
O(n^2) |
| 02 |
广度优先搜索 |
O(n^2) |
O(n^2) |
var dx = []int{-1, 1, 0, 0, 1, 1, -1, -1}
var dy = []int{0, 0, -1, 1, 1, -1, 1, -1}
func updateBoard(board [][]byte, click []int) [][]byte {
x, y := click[0], click[1]
if board[x][y] == 'M' {
board[x][y] = 'X'
} else {
dfs(board, x, y)
}
return board
}
func dfs(board [][]byte, x, y int) {
count := 0
for i := 0; i < 8; i++ {
newX := dx[i] + x
newY := dy[i] + y
if newX < 0 || newX >= len(board) || newY < 0 || newY >= len(board[0]) {
continue
}
if board[newX][newY] == 'M' {
count++
}
}
if count > 0 {
board[x][y] = byte(count + '0')
} else {
board[x][y] = 'B'
for i := 0; i < 8; i++ {
newX := dx[i] + x
newY := dy[i] + y
if newX < 0 || newX >= len(board) ||
newY < 0 || newY >= len(board[0]) ||
board[newX][newY] != 'E' {
continue
}
dfs(board, newX, newY)
}
}
}
# 2
var dx = []int{-1, 1, 0, 0, 1, 1, -1, -1}
var dy = []int{0, 0, -1, 1, 1, -1, 1, -1}
func updateBoard(board [][]byte, click []int) [][]byte {
x, y := click[0], click[1]
if board[x][y] == 'M' {
board[x][y] = 'X'
} else {
bfs(board, x, y)
}
return board
}
func bfs(board [][]byte, x, y int) {
visited := make([][]bool, len(board))
for i := 0; i < len(board); i++ {
visited[i] = make([]bool, len(board[i]))
}
queue := make([][2]int, 0)
queue = append(queue, [2]int{x, y})
visited[x][y] = true
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
count := 0
a := node[0]
b := node[1]
for j := 0; j < 8; j++ {
newX := dx[j] + a
newY := dy[j] + b
if newX < 0 || newX >= len(board) ||
newY < 0 || newY >= len(board[0]) ||
visited[newX][newY] == true {
continue
}
if board[newX][newY] == 'M' {
count++
}
}
if count > 0 {
board[a][b] = byte(count + '0')
} else {
board[a][b] = 'B'
for j := 0; j < 8; j++ {
newX := dx[j] + a
newY := dy[j] + b
if newX < 0 || newX >= len(board) ||
newY < 0 || newY >= len(board[0]) ||
board[newX][newY] != 'E' ||
visited[newX][newY] == true {
continue
}
queue = append(queue, [2]int{newX, newY})
visited[newX][newY] = true
}
}
}
}
537.复数乘法(2)
给定两个表示复数的字符串。
返回表示它们乘积的字符串。注意，根据定义 i2 = -1 。
示例 1:输入: "1+1i", "1+1i" 输出: "0+2i"
解释: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i ，你需要将它转换为 0+2i 的形式。
示例 2:输入: "1+-1i", "1+-1i" 输出: "0+-2i"
解释: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i ，你需要将它转换为 0+-2i 的形式。
注意:输入字符串不包含额外的空格。
输入字符串将以a+bi 的形式给出，其中整数 a 和 b 的范围均在 [-100, 100] 之间。输出也应当符合这种形式。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
内置函数 |
O(1) |
O(1) |
| 02 |
内置函数 |
O(1) |
O(1) |
func complexNumberMultiply(a string, b string) string {
a1, a2 := getValue(a)
b1, b2 := getValue(b)
return fmt.Sprintf("%d+%di", a1*b1-a2*b2, a1*b2+a2*b1)
}
func getValue(str string) (a, b int) {
arr := strings.Split(str, "+")
a, _ = strconv.Atoi(arr[0])
b, _ = strconv.Atoi(arr[1][:len(arr[1])-1])
return a, b
}
# 2
func complexNumberMultiply(a string, b string) string {
var a1, a2, b1, b2 int
fmt.Sscanf(a, "%d+%di", &a1, &a2)
fmt.Sscanf(b, "%d+%di", &b1, &b2)
return fmt.Sprintf("%d+%di", a1*b1-a2*b2, a1*b2+a2*b1)
}
539.最小时间差(2)
给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。
示例 1：输入：timePoints = ["23:59","00:00"] 输出：1
示例 2：输入：timePoints = ["00:00","23:59","00:00"]输出：0
提示：2 <= timePoints <= 2 * 104
timePoints[i] 格式为 "HH:MM"
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序 |
O(nlog(n)) |
O(n) |
| 02 |
排序 |
O(nlog(n)) |
O(n) |
func findMinDifference(timePoints []string) int {
m := make(map[int]bool)
for i := 0; i < len(timePoints); i++ {
value := getValue(timePoints[i])
if _, ok := m[value]; ok {
return 0
}
m[value] = true
}
arr := make([]int, 0)
for k := range m {
arr = append(arr, k)
}
sort.Ints(arr)
res := math.MaxInt32
arr = append(arr, arr[0]+1440)
for i := 1; i < len(arr); i++ {
if res > arr[i]-arr[i-1] {
res = arr[i] - arr[i-1]
}
}
return res
}
func getValue(str string) int {
hour, _ := strconv.Atoi(str[:2])
minute, _ := strconv.Atoi(str[3:])
return hour*60 + minute
}
# 2
func findMinDifference(timePoints []string) int {
arr := make([]int, 0)
for i := 0; i < len(timePoints); i++ {
value := getValue(timePoints[i])
arr = append(arr, value)
}
sort.Ints(arr)
res := math.MaxInt32
arr = append(arr, arr[0]+1440)
for i := 1; i < len(arr); i++ {
if res > arr[i]-arr[i-1] {
res = arr[i] - arr[i-1]
}
}
return res
}
func getValue(str string) int {
hour, _ := strconv.Atoi(str[:2])
minute, _ := strconv.Atoi(str[3:])
return hour*60 + minute
}
540.有序数组中的单一元素(3)
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
示例 1:输入: [1,1,2,3,3,4,4,8,8]输出: 2
示例 2:输入: [3,3,7,7,10,11,11]输出: 10
注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
二分查找 |
O(log(n)) |
O(1) |
| 03 |
异或 |
O(n) |
O(1) |
func singleNonDuplicate(nums []int) int {
for i := 0; i < len(nums)-1; i = i + 2 {
if nums[i] != nums[i+1] {
return nums[i]
}
}
return nums[len(nums)-1]
}
# 2
func singleNonDuplicate(nums []int) int {
n := len(nums)
left, right := 0, n-1
for left < right {
mid := left + (right-left)/2
if mid%2 == 1 {
mid--
}
if nums[mid] == nums[mid+1] {
left = mid + 2
} else {
right = mid
}
}
return nums[left]
}
# 3
func singleNonDuplicate(nums []int) int {
res := 0
for i := 0; i < len(nums); i++ {
res = res ^ nums[i]
}
return res
}
542.01矩阵(3)
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1: 输入:
0 0 0
0 1 0
0 0 0
输出:
0 0 0
0 1 0
0 0 0
示例 2: 输入:
0 0 0
0 1 0
1 1 1
输出:
0 0 0
0 1 0
1 2 1
注意:
给定矩阵的元素个数不超过 10000。
给定矩阵中至少有一个元素是 0。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n^2) |
| 02 |
广度优先搜索 |
O(n^2) |
O(n^2) |
| 03 |
动态规划 |
O(n^2) |
O(1) |
func updateMatrix(matrix [][]int) [][]int {
n := len(matrix)
m := len(matrix[0])
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, m)
for j := 0; j < m; j++ {
if matrix[i][j] == 1 {
dp[i][j] = math.MaxInt32 / 10
if i > 0 {
dp[i][j] = min(dp[i][j], dp[i-1][j]+1)
}
if j > 0 {
dp[i][j] = min(dp[i][j], dp[i][j-1]+1)
}
} else {
dp[i][j] = 0
}
}
}
for i := n - 1; i >= 0; i-- {
for j := m - 1; j >= 0; j-- {
if dp[i][j] > 1 {
if i < n-1 {
dp[i][j] = min(dp[i][j], dp[i+1][j]+1)
}
if j < m-1 {
dp[i][j] = min(dp[i][j], dp[i][j+1]+1)
}
}
}
}
return dp
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
var dx = []int{-1, 1, 0, 0}
var dy = []int{0, 0, -1, 1}
func updateMatrix(matrix [][]int) [][]int {
n := len(matrix)
m := len(matrix[0])
queue := make([][2]int, 0)
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if matrix[i][j] == 0 {
queue = append(queue, [2]int{i, j})
} else {
matrix[i][j] = -1
}
}
}
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
for i := 0; i < 4; i++ {
x := node[0] + dx[i]
y := node[1] + dy[i]
if 0 <= x && x < n && 0 <= y && y < m && matrix[x][y] == -1 {
matrix[x][y] = matrix[node[0]][node[1]] + 1
queue = append(queue, [2]int{x, y})
}
}
}
return matrix
}
# 3
func updateMatrix(matrix [][]int) [][]int {
n := len(matrix)
m := len(matrix[0])
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if matrix[i][j] == 1 {
matrix[i][j] = math.MaxInt32 / 10
if i > 0 {
matrix[i][j] = min(matrix[i][j], matrix[i-1][j]+1)
}
if j > 0 {
matrix[i][j] = min(matrix[i][j], matrix[i][j-1]+1)
}
} else {
matrix[i][j] = 0
}
}
}
for i := n - 1; i >= 0; i-- {
for j := m - 1; j >= 0; j-- {
if matrix[i][j] > 1 {
if i < n-1 {
matrix[i][j] = min(matrix[i][j], matrix[i+1][j]+1)
}
if j < m-1 {
matrix[i][j] = min(matrix[i][j], matrix[i][j+1]+1)
}
}
}
}
return matrix
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
547.省份数量(3)
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，
且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，
而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
示例 1：输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]输出：2
示例 2：输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]] 输出：3
提示：1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
并查集 |
O(n^2) |
O(n) |
| 02 |
递归 |
O(n^2) |
O(n) |
| 03 |
广度优先搜索 |
O(n^2) |
O(n) |
func findCircleNum(M [][]int) int {
n := len(M)
fa = Init(n)
count = n
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if M[i][j] == 1 {
union(i, j)
}
}
}
return getCount()
}
var fa []int
var count int
func Init(n int) []int {
arr := make([]int, n)
for i := 0; i < n; i++ {
arr[i] = i
}
count = n
return arr
}
func find(x int) int {
if fa[x] == x {
return x
}
fa[x] = find(fa[x])
return fa[x]
}
func union(i, j int) {
x, y := find(i), find(j)
if x != y {
fa[x] = y
count--
}
}
func query(i, j int) bool {
return find(i) == find(j)
}
func getCount() int {
return count
}
# 2
var arr []bool
func findCircleNum(M [][]int) int {
n := len(M)
arr = make([]bool, n)
res := 0
for i := 0; i < n; i++ {
if arr[i] == false {
dfs(M, i)
res++
}
}
return res
}
func dfs(M [][]int, index int) {
for i := 0; i < len(M); i++ {
if arr[i] == false && M[index][i] == 1 {
arr[i] = true
dfs(M, i)
}
}
}
# 3
func findCircleNum(M [][]int) int {
n := len(M)
arr := make([]bool, n)
res := 0
queue := make([]int, 0)
for i := 0; i < n; i++ {
if arr[i] == false {
queue = append(queue, i)
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
arr[node] = true
for j := 0; j < n; j++ {
if M[node][j] == 1 && arr[j] == false {
queue = append(queue, j)
}
}
}
res++
}
}
return res
}
553.最优除法(1)
给定一组正整数，相邻的整数之间将会进行浮点除法操作。例如，[2,3,4] -> 2 / 3 / 4 。
但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。
你需要找出怎么添加括号，才能得到最大的结果，并且返回相应的字符串格式的表达式。你的表达式不应该含有冗余的括号。
示例：输入: [1000,100,10,2] 输出: "1000/(100/10/2)"
解释:1000/(100/10/2) = 1000/((100/10)/2) = 200
但是，以下加粗的括号 "1000/((100/10)/2)" 是冗余的，
因为他们并不影响操作的优先级，所以你需要返回 "1000/(100/10/2)"。
其他用例:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2
说明:输入数组的长度在 [1, 10] 之间。
数组中每个元素的大小都在 [2, 1000] 之间。
每个测试用例只有一个最优除法解。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
贪心 |
O(n) |
O(n) |
func optimalDivision(nums []int) string {
res := make([]string,0)
for i := 0; i < len(nums); i++{
res = append(res, strconv.Itoa(nums[i]))
}
if len(res) < 3{
return strings.Join(res, "/")
}
return res[0]+"/("+strings.Join(res[1:],"/") + ")"
}
554.砖墙(1)
你的面前有一堵矩形的、由多行砖块组成的砖墙。这些砖块高度相同但是宽度不同。
你现在要画一条自顶向下的、穿过最少砖块的垂线。
砖墙由行的列表表示。 每一行都是一个代表从左至右每块砖的宽度的整数列表。
如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。
你需要找出怎样画才能使这条线穿过的砖块数量最少，并且返回穿过的砖块数量。
你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。
示例：输入: [[1,2,2,1],
[3,1,2],
[1,3,2],
[2,4],
[3,1,2],
[1,3,1,1]]
输出: 2
解释: 提示：每一行砖块的宽度之和应该相等，并且不能超过 INT_MAX。
每一行砖块的数量在[1,10,000] 范围内，墙的高度在[1,10,000] 范围内，总的砖块数量不超过 20,000。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n^2) |
O(n) |
func leastBricks(wall [][]int) int {
maxCount := 0
m := make(map[int]int)
for i := 0; i < len(wall); i++ {
index := 0
for j := 0; j < len(wall[i])-1; j++ {
index = index + wall[i][j]
m[index]++
if maxCount <= m[index] {
maxCount = m[index]
}
}
}
return len(wall) - maxCount
}
556.下一个更大元素III(2)
给你一个正整数n ，请你找出符合条件的最小整数，其由重新排列 n中存在的每位数字组成，并且其值大于 n 。
如果不存在这样的正整数，则返回 -1 。
注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。
示例 1：输入：n = 12 输出：21
示例 2：输入：n = 21 输出：-1
提示：1 <= n <= 231 - 1
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(log(n)) |
O(log(n)) |
| 02 |
遍历 |
O(log(n)) |
O(log(n)) |
func nextGreaterElement(n int) int {
arr := make([]int, 0)
for n > 0 {
arr = append(arr, n%10)
n = n / 10
}
reverse(arr, 0, len(arr)-1)
arr = nextPermutation(arr)
if arr == nil {
return -1
}
res := 0
for i := 0; i < len(arr); i++ {
res = res*10 + arr[i]
if res > math.MaxInt32 {
return -1
}
}
return res
}
func nextPermutation(nums []int) []int {
n := len(nums)
left := n - 2
for left >= 0 && nums[left] >= nums[left+1] {
left--
}
if left >= 0 {
right := n - 1
for right >= 0 && nums[right] <= nums[left] {
right--
}
nums[left], nums[right] = nums[right], nums[left]
} else {
return nil
}
reverse(nums, left+1, n-1)
return nums
}
func reverse(nums []int, left, right int) {
for left < right {
nums[left], nums[right] = nums[right], nums[left]
left++
right--
}
}
# 2
func nextGreaterElement(n int) int {
nums := []byte(strconv.Itoa(n))
length := len(nums)
left := length - 2
for left >= 0 && nums[left] >= nums[left+1] {
left--
}
if left >= 0 {
right := length - 1
for right >= 0 && nums[right] <= nums[left] {
right--
}
nums[left], nums[right] = nums[right], nums[left]
} else {
return -1
}
left = left + 1
right := length - 1
for left < right {
nums[left], nums[right] = nums[right], nums[left]
left++
right--
}
res, _ := strconv.Atoi(string(nums))
if res > math.MaxInt32 {
return -1
}
return res
}
558.四叉树交集(1)
二进制矩阵中的所有元素不是 0 就是 1 。
给你两个四叉树，quadTree1 和 quadTree2。其中 quadTree1 表示一个 n * n 二进制矩阵，
而 quadTree2 表示另一个 n * n 二进制矩阵。
请你返回一个表示 n * n 二进制矩阵的四叉树，它是 quadTree1 和 quadTree2 所表示的两个二进制矩阵进行 按位逻辑或运算 的结果。
注意，当 isLeaf 为 False 时，你可以把 True 或者 False 赋值给节点，两种值都会被判题机制 接受 。
四叉树数据结构中，每个内部节点只有四个子节点。此外，每个节点都有两个属性：
val：储存叶子结点所代表的区域的值。1 对应 True，0 对应 False；
isLeaf: 当这个节点是一个叶子结点时为 True，如果它有 4 个子节点则为 False 。
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
}
我们可以按以下步骤为二维区域构建四叉树：
如果当前网格的值相同（即，全为 0 或者全为 1），将 isLeaf 设为 True ，
将 val 设为网格相应的值，并将四个子节点都设为 Null 然后停止。
如果当前网格的值不同，将 isLeaf 设为 False， 将 val 设为任意值，然后如下图所示，将当前网格划分为四个子网格。
使用适当的子网格递归每个子节点。
如果你想了解更多关于四叉树的内容，可以参考 wiki 。
四叉树格式：
输出为使用层序遍历后四叉树的序列化形式，其中 null 表示路径终止符，其下面不存在节点。
它与二叉树的序列化非常相似。唯一的区别是节点以列表形式表示 [isLeaf, val] 。
如果 isLeaf 或者 val 的值为 True ，则表示它在列表[isLeaf, val] 中的值为 1 ；
如果 isLeaf 或者 val 的值为 False ，则表示值为 0 。
示例 1：输入：quadTree1 = [[0,1],[1,1],[1,1],[1,0],[1,0]],
quadTree2 = [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
输出：[[0,0],[1,1],[1,1],[1,1],[1,0]]
解释：quadTree1 和 quadTree2 如上所示。由四叉树所表示的二进制矩阵也已经给出。
如果我们对这两个矩阵进行按位逻辑或运算，则可以得到下面的二进制矩阵，由一个作为结果的四叉树表示。
注意，我们展示的二进制矩阵仅仅是为了更好地说明题意，你无需构造二进制矩阵来获得结果四叉树。
示例 2：输入：quadTree1 = [[1,0]], quadTree2 = [[1,0]] 输出：[[1,0]]
解释：两个数所表示的矩阵大小都为 1*1，值全为 0
结果矩阵大小为 1*1，值全为 0 。
示例 3：输入：quadTree1 = [[0,0],[1,0],[1,0],[1,1],[1,1]] , quadTree2 = [[0,0],[1,1],[1,1],[1,0],[1,1]]
输出：[[1,1]]
示例 4：输入：quadTree1 = [[0,0],[1,1],[1,0],[1,1],[1,1]],
quadTree2 = [[0,0],[1,1],[0,1],[1,1],[1,1],null,null,null,null,[1,1],[1,0],[1,0],[1,1]]
输出：[[0,0],[1,1],[0,1],[1,1],[1,1],null,null,null,null,[1,1],[1,0],[1,0],[1,1]]
示例 5：输入：quadTree1 = [[0,1],[1,0],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]],
quadTree2 = [[0,1],[0,1],[1,0],[1,1],[1,0],[1,0],[1,0],[1,1],[1,1]]
输出：[[0,0],[0,1],[0,1],[1,1],[1,0],[1,0],[1,0],[1,1],[1,1],[1,0],[1,0],[1,1],[1,1]]
提示：quadTree1 和 quadTree2 都是符合题目要求的四叉树，每个都代表一个 n * n 的矩阵。
n == 2^x ，其中 0 <= x <= 9.
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(n) |
func intersect(quadTree1 *Node, quadTree2 *Node) *Node {
res := &Node{}
if quadTree1.IsLeaf == true {
if quadTree1.Val == true {
return quadTree1
}
return quadTree2
}
if quadTree2.IsLeaf == true {
if quadTree2.Val == true {
return quadTree2
}
return quadTree1
}
tL := intersect(quadTree1.TopLeft, quadTree2.TopLeft)
tR := intersect(quadTree1.TopRight, quadTree2.TopRight)
bL := intersect(quadTree1.BottomLeft, quadTree2.BottomLeft)
bR := intersect(quadTree1.BottomRight, quadTree2.BottomRight)
if tL.IsLeaf == true && tR.IsLeaf == true && bL.IsLeaf == true && bR.IsLeaf == true &&
tL.Val == tR.Val && tR.Val == bL.Val && bL.Val == bR.Val {
res.IsLeaf = true
res.Val = tL.Val
return res
}
res.TopLeft = tL
res.TopRight = tR
res.BottomLeft = bL
res.BottomRight = bR
res.Val = false
res.IsLeaf = false
return res
}
560.和为K的子数组(4)
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明:数组的长度为 [1, 20,000]。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n^2) |
O(1) |
| 02 |
前缀和-遍历 |
O(n^2) |
O(n) |
| 03 |
前缀和-哈希辅助 |
O(n) |
O(n) |
| 04 |
前缀和-哈希辅助 |
O(n) |
O(n) |
func subarraySum(nums []int, k int) int {
res := 0
for i := 0; i < len(nums); i++ {
sum := 0
for j := i; j < len(nums); j++ {
sum = sum + nums[j]
if sum == k {
res++
}
}
}
return res
}
# 2
func subarraySum(nums []int, k int) int {
if len(nums) == 0 {
return 0
}
res := 0
arr := make([]int, len(nums)+1)
arr[0] = 0
for i := 1; i <= len(nums); i++ {
arr[i] = arr[i-1] + nums[i-1]
}
for i := 0; i <= len(nums); i++ {
for j := 0; j < i; j++ {
if arr[i]-arr[j] == k {
res++
}
}
}
return res
}
# 3
func subarraySum(nums []int, k int) int {
res := 0
m := make(map[int]int)
m[0] = 1
sum := 0
for i := 0; i < len(nums); i++ {
sum = sum + nums[i]
if _, ok := m[sum-k]; ok {
res = res + m[sum-k]
}
m[sum]++
}
return res
}
# 4
func subarraySum(nums []int, k int) int {
res := 0
m := make(map[int][]int)
m[0] = []int{-1}
sum := 0
for i := 0; i < len(nums); i++ {
sum = sum + nums[i]
if _, ok := m[sum-k]; ok {
res = res + len(m[sum-k])
}
m[sum] = append(m[sum], i)
}
return res
}
565.数组嵌套(4)
索引从0开始长度为N的数组A，包含0到N - 1的所有整数。找到最大的集合S并返回其大小，
其中 S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }且遵守以下的规则。
假设选择索引为i的元素A[i]为S的第一个元素，S的下一个元素应该是A[A[i]]，
之后是A[A[A[i]]]... 以此类推，不断添加直到S出现重复的元素。
示例1:输入: A = [5,4,0,3,1,6,2] 输出: 4
解释: A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
其中一种最长的 S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
提示：N是[1, 20,000]之间的整数。
A中不含有重复的元素。
A中的元素大小在[0, N-1]之间。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n) |
O(n) |
| 02 |
哈希辅助 |
O(n) |
O(n) |
| 03 |
遍历交换 |
O(n) |
O(1) |
| 04 |
并查集 |
O(n) |
O(n) |
func arrayNesting(nums []int) int {
m := make(map[int]bool)
res := 0
for i := 0; i < len(nums); i++ {
if m[nums[i]] == true {
continue
}
count := 0
cur := i
for {
count++
m[cur] = true
cur = nums[cur]
if cur == i {
break
}
}
if count > res {
res = count
}
}
return res
}
# 2
func arrayNesting(nums []int) int {
m := make(map[int]bool)
res := 0
for i := 0; i < len(nums); i++ {
if m[nums[i]] == true {
continue
}
count := 0
cur := i
for {
count++
m[cur] = true
cur = nums[cur]
if m[cur] == true {
break
}
}
if count > res {
res = count
}
}
return res
}
# 3
func arrayNesting(nums []int) int {
res := 0
for i := 0; i < len(nums); i++ {
count := 1
for nums[i] != i {
count++
nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
}
if count > res {
res = count
}
}
return res
}
# 4
func arrayNesting(nums []int) int {
res := 0
fa = Init(len(nums))
for i := 0; i < len(nums); i++ {
union(i, nums[i])
}
m := make(map[int]int)
for i := 0; i < len(fa); i++ {
m[find(i)]++
}
for _, v := range m {
if v > res {
res = v
}
}
return res
}
var fa []int
func Init(n int) []int {
arr := make([]int, n)
for i := 0; i < n; i++ {
arr[i] = i
}
return arr
}
func find(x int) int {
if fa[x] == x {
return x
}
fa[x] = find(fa[x])
return fa[x]
}
func union(i, j int) {
x, y := find(i), find(j)
if x != y {
fa[x] = y
}
}
567.字符串的排列(2)
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:输入: s1 = "ab" s2 = "eidbaooo" 输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例2:输入: s1= "ab" s2 = "eidboaoo" 输出: False
注意：输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
滑动窗口 |
O(n) |
O(1) |
| 02 |
滑动窗口 |
O(n) |
O(1) |
func checkInclusion(s1 string, s2 string) bool {
if len(s1) > len(s2) {
return false
}
arr1, arr2 := [26]int{}, [26]int{}
for i := 0; i < len(s1); i++ {
arr1[s1[i]-'a']++
arr2[s2[i]-'a']++
}
for i := 0; i < len(s2)-len(s1); i++ {
if arr1 == arr2 {
return true
}
arr2[s2[i]-'a']--
arr2[s2[i+len(s1)]-'a']++
}
return arr1 == arr2
}
# 2
func checkInclusion(s1 string, s2 string) bool {
if len(s1) > len(s2) {
return false
}
m1, m2 := make(map[byte]int), make(map[byte]int)
for i := 0; i < len(s1); i++ {
m1[s1[i]-'a']++
m2[s2[i]-'a']++
}
for i := 0; i < len(s2)-len(s1); i++ {
if compare(m1, m2) {
return true
}
m2[s2[i]-'a']--
if m2[s2[i]-'a'] == 0 {
delete(m2, s2[i]-'a')
}
m2[s2[i+len(s1)]-'a']++
}
return compare(m1, m2)
}
func compare(m1, m2 map[byte]int) bool {
if len(m1) != len(m2) {
return false
}
for k := range m1 {
if m2[k] != m1[k] {
return false
}
}
return true
}
576.出界的路径数(2)
给定一个 m × n 的网格和一个球。球的起始坐标为(i,j)，你可以将球移到相邻的单元格内，
或者往上、下、左、右四个方向上移动使球穿过网格边界。但是，你最多可以移动N次。
找出可以将球移出边界的路径数量。答案可能非常大，返回 结果 mod 109+ 7 的值。
示例 1：输入: m = 2, n = 2, N = 2, i = 0, j = 0 输出: 6
解释:
示例 2：输入: m = 1, n = 3, N = 3, i = 0, j = 1 输出: 12
解释:
说明:球一旦出界，就不能再被移动回网格内。
网格的长度和高度在 [1,50] 的范围内。
N 在 [0,50] 的范围内。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n^3) |
O(n^3) |
| 02 |
动态规划 |
O(n^3) |
O(n^3) |
var dp [60][60][60]int
var dx = []int{-1, 1, 0, 0}
var dy = []int{0, 0, -1, 1}
var mod = 1000000007
func findPaths(m int, n int, N int, i int, j int) int {
dp = [60][60][60]int{}
for i := 0; i < 60; i++ {
for j := 0; j < 60; j++ {
for k := 0; k < 60; k++ {
dp[i][j][k] = -1
}
}
}
return dfs(m, n, i+1, j+1, N)
}
func dfs(m, n, i, j, k int) int {
if k < 0 {
return 0
}
if i < 1 || i > m || j < 1 || j > n {
return 1
}
if dp[i][j][k] != -1 {
return dp[i][j][k]
}
dp[i][j][k] = 0
for a := 0; a < 4; a++ {
x := i + dx[a]
y := j + dy[a]
dp[i][j][k] = (dp[i][j][k] + dfs(m, n, x, y, k-1)) % mod
}
return dp[i][j][k]
}
# 2
var dx = []int{-1, 1, 0, 0}
var dy = []int{0, 0, -1, 1}
var mod = 1000000007
func findPaths(m int, n int, N int, i int, j int) int {
dp := [60][60][60]int{}
for k := 1; k <= N; k++ {
for a := 0; a < m; a++ {
for b := 0; b < n; b++ {
for i := 0; i < 4; i++ {
x := a + dx[i]
y := b + dy[i]
if x < 0 || x >= m || y < 0 || y >= n {
dp[a][b][k]++
} else {
dp[a][b][k] = (dp[a][b][k] + dp[x][y][k-1]) % mod
}
}
}
}
}
return dp[i][j][N] % mod
}
583.两个字符串的删除操作(3)
给定两个单词word1和word2，找到使得word1和word2相同所需的最小步数，
每步可以删除任意一个字符串中的一个字符。
示例：输入: "sea", "eat" 输出: 2
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
提示：给定单词的长度不超过500。
给定单词中的字符只含有小写字母。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n^2) |
| 02 |
动态规划 |
O(n^2) |
O(n^2) |
| 03 |
递归 |
O(n^2) |
O(n^2) |
func minDistance(word1 string, word2 string) int {
a, b := len(word1), len(word2)
dp := make([][]int, a+1)
for i := 0; i <= a; i++ {
dp[i] = make([]int, b+1)
}
for i := 1; i <= a; i++ {
for j := 1; j <= b; j++ {
if word1[i-1] == word2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
}
}
}
return a + b - 2*dp[a][b]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func minDistance(word1 string, word2 string) int {
a, b := len(word1), len(word2)
dp := make([][]int, a+1)
for i := 0; i <= a; i++ {
dp[i] = make([]int, b+1)
dp[i][0] = i
}
for i := 0; i <= b; i++ {
dp[0][i] = i
}
for i := 1; i <= a; i++ {
for j := 1; j <= b; j++ {
if word1[i-1] == word2[j-1] {
dp[i][j] = dp[i-1][j-1]
} else {
dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + 1
}
}
}
return dp[a][b]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 3
var m [][]int
func minDistance(word1 string, word2 string) int {
a, b := len(word1), len(word2)
m = make([][]int, a+1)
for i := 0; i <= a; i++ {
m[i] = make([]int, b+1)
for j := 0; j <= b; j++ {
m[i][j] = -1
}
}
total := dfs(word1, word2, 0, 0)
return a + b - 2*total
}
func dfs(word1 string, word2 string, i, j int) int {
if len(word1) == i || len(word2) == j {
return 0
}
if m[i][j] > -1 {
return m[i][j]
}
if word1[i] == word2[j] {
m[i][j] = dfs(word1, word2, i+1, j+1) + 1
} else {
m[i][j] = max(dfs(word1, word2, i, j+1), dfs(word1, word2, i+1, j))
}
return m[i][j]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
592.分数加减运算(1)
给定一个表示分数加减运算表达式的字符串，你需要返回一个字符串形式的计算结果。这个结果应该是不可约分的分数，即最简分数。
如果最终结果是一个整数，例如2，你需要将它转换成分数形式，其分母为1。所以在上述例子中, 2应该被转换为2/1。
示例1:输入:"-1/2+1/2" 输出: "0/1"
示例 2:输入:"-1/2+1/2+1/3" 输出: "1/3"
示例 3:输入:"1/3-1/2" 输出: "-1/6"
示例 4:输入:"5/3+1/3" 输出: "2/1"
说明:输入和输出字符串只包含'0' 到'9'的数字，以及'/', '+' 和'-'。
输入和输出分数格式均为±分子/分母。如果输入的第一个分数或者输出的分数是正数，则'+'会被省略掉。
输入只包含合法的最简分数，每个分数的分子与分母的范围是[1,10]。如果分母是1，意味着这个分数实际上是一个整数。
输入的分数个数范围是 [1,10]。
最终结果的分子与分母保证是 32 位整数范围内的有效整数。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(nlog(n)) |
O(n) |
func fractionAddition(expression string) string {
s := strings.ReplaceAll(expression, "-", "+-")
s = strings.ReplaceAll(s, "/", "+")
temp := strings.Split(s, "+")
arr := make([]int, 0)
for i := 0; i < len(temp); i++ {
if temp[i] == "" {
continue
}
value, _ := strconv.Atoi(temp[i])
arr = append(arr, value)
}
a, b := 0, 1
for i := 0; i < len(arr); i = i + 2 {
c, d := arr[i], arr[i+1]
a = a*d + b*c
b = b * d
g := gcd(a, b)
if g < 0 {
g = -g
}
a, b = a/g, b/g
}
return fmt.Sprintf("%d/%d", a, b)
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
593.有效的正方形(2)
给定二维空间中四点的坐标，返回四点是否可以构造一个正方形。
一个点的坐标（x，y）由一个有两个整数的整数数组表示。
示例:输入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1] 输出: True
注意:所有输入整数都在 [-10000，10000] 范围内。
一个有效的正方形有四个等长的正长和四个等角（90度角）。
输入点没有顺序。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
几何 |
O(1) |
O(1) |
| 02 |
几何 |
O(1) |
O(1) |
func validSquare(p1 []int, p2 []int, p3 []int, p4 []int) bool {
m := make(map[int]int)
m[getDis(p1, p2)]++
m[getDis(p1, p3)]++
m[getDis(p1, p4)]++
m[getDis(p2, p3)]++
m[getDis(p2, p4)]++
m[getDis(p3, p4)]++
a, b := 0, 0
for k, v := range m {
if v == 2 {
a = k
} else if v == 4 {
b = k
} else {
return false
}
}
return len(m) == 2 && a == 2*b
}
func getDis(a, b []int) int {
return (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1])
}
# 2
func validSquare(p1 []int, p2 []int, p3 []int, p4 []int) bool {
arr := make([]int, 0)
arr = append(arr, getDis(p1, p2))
arr = append(arr, getDis(p1, p3))
arr = append(arr, getDis(p1, p4))
arr = append(arr, getDis(p2, p3))
arr = append(arr, getDis(p2, p4))
arr = append(arr, getDis(p3, p4))
sort.Ints(arr)
return arr[0] > 0 && arr[0] == arr[3] && arr[4] == arr[5] && arr[0]*2 == arr[4]
}
func getDis(a, b []int) int {
return (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1])
}
0501-0600-Hard
502.IPO(2)
假设 力扣（LeetCode）即将开始其 IPO。为了以更高的价格将股票卖给风险投资公司，
力扣 希望在 IPO 之前开展一些项目以增加其资本。
由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。
帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。
给定若干个项目。对于每个项目 i，它都有一个纯利润 Pi，并且需要最小的资本 Ci 来启动相应的项目。
最初，你有 W 资本。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。
总而言之，从给定项目中选择最多 k 个不同项目的列表，以最大化最终资本，并输出最终可获得的最多资本。
示例 1:输入: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1].
输出: 4
解释:由于你的初始资本为 0，你尽可以从 0 号项目开始。
在完成后，你将获得 1 的利润，你的总资本将变为 1。
此时你可以选择开始 1 号或 2 号项目。
由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。
注意:假设所有输入数字都是非负整数。
表示利润和资本的数组的长度不超过 50000。
答案保证在 32 位有符号整数范围内。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双堆 |
O(nlog(n)) |
O(n) |
| 02 |
排序 |
O(nlog(n)) |
O(n) |
func findMaximizedCapital(k int, W int, Profits []int, Capital []int) int {
maxProfit := &ProfitNode{}
minCapital := &CapitalNode{}
heap.Init(maxProfit)
heap.Init(minCapital)
for i := 0; i < len(Profits); i++ {
heap.Push(minCapital, Node{
Profits: Profits[i],
Capital: Capital[i],
})
}
for i := 0; i < k; i++ {
for minCapital.Len() > 0 {
node := heap.Pop(minCapital).(Node)
if node.Capital <= W {
heap.Push(maxProfit, node)
} else {
heap.Push(minCapital, node)
break
}
}
if maxProfit.Len() == 0 {
return W
}
node := heap.Pop(maxProfit).(Node)
W = W + node.Profits
}
return W
}
type Node struct {
Profits int
Capital int
}
type ProfitNode []Node
func (h ProfitNode) Len() int {
return len(h)
}
func (h ProfitNode) Less(i, j int) bool {
return h[i].Profits > h[j].Profits
}
func (h ProfitNode) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *ProfitNode) Push(x interface{}) {
*h = append(*h, x.(Node))
}
func (h *ProfitNode) Pop() interface{} {
value := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return value
}
type CapitalNode []Node
func (h CapitalNode) Len() int {
return len(h)
}
func (h CapitalNode) Less(i, j int) bool {
return h[i].Capital < h[j].Capital
}
func (h CapitalNode) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *CapitalNode) Push(x interface{}) {
*h = append(*h, x.(Node))
}
func (h *CapitalNode) Pop() interface{} {
value := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return value
}
# 2
type Node struct {
profit int
capital int
}
func findMaximizedCapital(k int, W int, Profits []int, Capital []int) int {
arr := make([]Node, 0)
for i := 0; i < len(Profits); i++ {
arr = append(arr, Node{
profit: Profits[i],
capital: Capital[i],
})
}
sort.Slice(arr, func(i, j int) bool {
return arr[i].profit > arr[j].profit
})
index := 0
for k > 0 {
if index == len(arr) {
return W
}
if arr[index].capital <= W {
k--
W = W + arr[index].profit
arr = append(arr[:index], arr[index+1:]...)
index = 0
continue
}
index++
}
return W
}
514.自由之路(2)
电子游戏“辐射4”中，任务“通向自由”要求玩家到达名为“Freedom Trail Ring”的金属表盘，
并使用表盘拼写特定关键词才能开门。
给定一个字符串ring，表示刻在外环上的编码；给定另一个字符串key，表示需要拼写的关键词。
您需要算出能够拼写关键词中所有字符的最少步数。
最初，ring的第一个字符与12:00方向对齐。
您需要顺时针或逆时针旋转 ring 以使key的一个字符在 12:00 方向对齐，
然后按下中心按钮，以此逐个拼写完key中的所有字符。
旋转ring拼出 key 字符key[i]的阶段中：
您可以将ring顺时针或逆时针旋转一个位置，计为1步。
旋转的最终目的是将字符串ring的一个字符与 12:00 方向对齐，并且这个字符必须等于字符key[i] 。
如果字符key[i]已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作1 步。
按完之后，您可以开始拼写key的下一个字符（下一阶段）, 直至完成所有拼写。
示例：输入: ring = "godding", key = "gd" 输出: 4
解释: 对于 key 的第一个字符 'g'，已经在正确的位置, 我们只需要1步来拼写这个字符。
对于 key 的第二个字符 'd'，我们需要逆时针旋转 ring "godding" 2步使它变成 "ddinggo"。
当然, 我们还需要1步进行拼写。
因此最终的输出是 4。
提示：ring 和key的字符串长度取值范围均为1 至100；
两个字符串中都只有小写字符，并且均可能存在重复字符；
字符串key一定可以由字符串 ring旋转拼出。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^3) |
O(n^2) |
| 02 |
递归 |
O(n^3) |
O(n^2) |
func findRotateSteps(ring string, key string) int {
maxValue := math.MaxInt32 / 10
n := len(key)
m := len(ring)
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, m)
for j := 0; j < m; j++ {
dp[i][j] = maxValue
}
}
arr := [26][]int{}
for i := 0; i < len(ring); i++ {
value := int(ring[i] - 'a')
arr[value] = append(arr[value], i)
}
for _, v := range arr[key[0]-'a'] {
dp[0][v] = min(v, m-v) + 1
}
for i := 1; i < n; i++ {
for _, j := range arr[key[i]-'a'] {
for _, k := range arr[key[i-1]-'a'] {
minValue := min(abs(j-k), m-abs(j-k))
dp[i][j] = min(dp[i][j], dp[i-1][k]+minValue+1)
}
}
}
res := math.MaxInt32
for i := 0; i < m; i++ {
res = min(res, dp[n-1][i])
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
# 2
var dp [][]int
var arr [26][]int
func findRotateSteps(ring string, key string) int {
n := len(key)
m := len(ring)
dp = make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, m)
for j := 0; j < m; j++ {
dp[i][j] = -1
}
}
arr = [26][]int{}
for i := 0; i < len(ring); i++ {
value := int(ring[i] - 'a')
arr[value] = append(arr[value], i)
}
return n + dfs(key, ring, 0, 0)
}
func dfs(key, ring string, keyIndex, ringIndex int) int {
if keyIndex == len(key) {
return 0
}
if dp[keyIndex][ringIndex] != -1 {
return dp[keyIndex][ringIndex]
}
cur := int(key[keyIndex] - 'a')
res := math.MaxInt32
for _, v := range arr[cur] {
minValue := min(abs(ringIndex-v), len(ring)-abs(ringIndex-v))
res = min(res, minValue+dfs(key, ring, keyIndex+1, v))
}
dp[keyIndex][ringIndex] = res
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
517.超级洗衣机(1)
假设有 n台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。
在每一步操作中，你可以选择任意 m（1 ≤ m ≤ n）台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。
给定一个非负整数数组代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的最少的操作步数。
如果不能使每台洗衣机中衣物的数量相等，则返回 -1。
示例 1：输入: [1,0,5] 输出: 3
解释: 第一步: 1 0 <-- 5 => 1 1 4
第二步: 1 <-- 1 <-- 4 => 2 1 3
第三步: 2 1 <-- 3 => 2 2 2
示例 2：输入: [0,3,0] 输出: 2
解释: 第一步: 0 <-- 3 0 => 1 2 0
第二步: 1 2 --> 0 => 1 1 1
示例 3:输入: [0,2,0] 输出: -1
解释: 不可能让所有三个洗衣机同时剩下相同数量的衣物。
提示：n 的范围是 [1, 10000]。
在每台超级洗衣机中，衣物数量的范围是 [0, 1e5]。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
贪心 |
O(n) |
O(1) |
func findMinMoves(machines []int) int {
n := len(machines)
sum := 0
for i := 0; i < n; i++ {
sum = sum + machines[i]
}
if sum%n != 0 {
return -1
}
per := sum / n
for i := 0; i < n; i++ {
machines[i] = machines[i] - per
}
maxValue := 0
curSum := 0
res := 0
for i := 0; i < n; i++ {
curSum = curSum + machines[i]
maxValue = max(maxValue, abs(curSum))
res = max(res, max(maxValue, machines[i]))
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
535.TinyURL的加密与解密(2)
TinyURL是一种URL简化服务， 比如：当你输入一个URLhttps://leetcode.com/problems/design-tinyurl时，
它将返回一个简化的URLhttp://tinyurl.com/4e9iAk.
要求：设计一个 TinyURL 的加密encode和解密decode的方法。
你的加密和解密算法如何设计和运作是没有限制的，你只需要保证一个URL可以被加密成一个TinyURL，
并且这个TinyURL可以用解密方法恢复成原本的URL。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(1) |
O(n) |
| 02 |
哈希辅助 |
O(1) |
O(n) |
type Codec struct {
m map[string]string
index int
}
func Constructor() Codec {
return Codec{
m: make(map[string]string),
index: 1,
}
}
func (this *Codec) encode(longUrl string) string {
res := "http://tinyurl.com/" + strconv.Itoa(this.index)
this.m[res] = longUrl
this.index++
return res
}
func (this *Codec) decode(shortUrl string) string {
return this.m[shortUrl]
}
# 2
type Codec struct {
m map[string]string
index int
}
func Constructor() Codec {
return Codec{
m: make(map[string]string),
index: 1,
}
}
func (this *Codec) encode(longUrl string) string {
str := "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
res := "http://tinyurl.com/"
this.index++
count := this.index
temp := make([]byte, 0)
for count > 0 {
temp = append(temp, str[count%62])
count = count / 62
}
res = res + string(temp)
this.m[res] = longUrl
return res
}
func (this *Codec) decode(shortUrl string) string {
return this.m[shortUrl]
}
546.移除盒子
题目
给出一些不同颜色的盒子，盒子的颜色由数字表示，即不同的数字表示不同的颜色。
你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。
每一轮你可以移除具有相同颜色的连续 k 个盒子（k>= 1），这样一轮之后你将得到 k * k 个积分。
当你将所有盒子都去掉之后，求你能获得的最大积分和。
示例 1：输入：boxes = [1,3,2,2,2,3,4,3,1] 输出：23
解释：[1, 3, 2, 2, 2, 3, 4, 3, 1]
----> [1, 3, 3, 4, 3, 1] (3*3=9 分)
----> [1, 3, 3, 3, 1] (1*1=1 分)
----> [1, 1] (3*3=9 分)
----> [] (2*2=4 分)
示例 2：输入：boxes = [1,1,1] 输出：9
示例 3：输入：boxes = [1] 输出：1
提示：1 <= boxes.length <= 100
1 <= boxes[i]<= 100
解题思路
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n) |
O(1) |
552.学生出勤记录II(1)
给定一个正整数n，返回长度为 n 的所有可被视为可奖励的出勤记录的数量。
答案可能非常大，你只需返回结果mod 109 + 7的值。
学生出勤记录是只包含以下三个字符的字符串：
'A' : Absent，缺勤
'L' : Late，迟到
'P' : Present，到场
如果记录不包含多于一个'A'（缺勤）或超过两个连续的'L'（迟到），则该记录被视为可奖励的。
示例 1:输入: n = 2 输出: 8
解释：有8个长度为2的记录将被视为可奖励：
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
只有"AA"不会被视为可奖励，因为缺勤次数超过一次。
注意：n 的值不会超过100000。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n) |
O(1) |
var mod = 1000000007
func checkRecord(n int) int {
dp := [6]int{}
dp[0] = 1
dp[1] = 1
dp[2] = 0
dp[3] = 1
dp[4] = 0
dp[5] = 0
for i := 2; i <= n; i++ {
temp := [6]int{}
temp[0] = (dp[0] + dp[1] + dp[2]) % mod
temp[1] = dp[0]
temp[2] = dp[1]
temp[3] = (dp[0] + dp[1] + dp[2] + dp[3] + dp[4] + dp[5]) % mod
temp[4] = dp[3]
temp[5] = dp[4]
dp = temp
}
res := 0
for i := 0; i < len(dp); i++ {
res = (res + dp[i]) % 1000000007
}
return res
}
600.不含连续1的非负整数(1)
给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含连续的1的个数。
示例 1:输入: 5 输出: 5
解释: 下面是带有相应二进制表示的非负整数<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。
说明: 1 <= n <= 109
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(log(n)) |
O(log(n)) |
func findIntegers(n int) int {
dp := make(map[int]int)
dp[1] = 1
dp[2] = 2
for i := 3; i <= 32; i++ {
dp[i] = dp[i-1] + dp[i-2]
}
res := 0
prev := 0
for i := 32; i >= 1; i-- {
if n&(1<<(i-1)) > 0 {
res = res + dp[i]
if prev == 1 {
break
}
prev = 1
} else {
prev = 0
}
if i == 1 {
res++
}
}
return res
}