0401-0500-Easy
401.二进制手表(3)
二进制手表顶部有 4 个 LED 代表小时（0-11），底部的 6 个 LED 代表分钟（0-59）。
每个 LED 代表一个 0 或 1，最低位在右侧。
例如，上面的二进制手表读取 “3:25”。
给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。
案例:输入: n = 1
返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]
注意事项:
输出的顺序没有要求。
小时不会以零开头，比如 “01:00” 是不允许的，应为 “1:00”。
分钟必须由两位数组成，可能会以零开头，比如 “10:2” 是无效的，应为 “10:02”。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(1) |
O(1) |
| 02 |
暴力法 |
O(1) |
O(1) |
| 03 |
回溯法 |
O(2^n) |
O(n) |
func binCount(num int) int {
count := make([]int, 0)
for num != 0 {
temp := num % 2
count = append(count, temp)
num = num / 2
}
countNum := 0
for i := 0; i < len(count); i++ {
if count[i] == 1 {
countNum++
}
}
return countNum
}
func readBinaryWatch(num int) []string {
res := make([]string, 0)
for i := 0; i < 12; i++ {
for j := 0; j < 60; j++ {
if binCount(i)+binCount(j) == num {
res = append(res, fmt.Sprintf("%d:%02d", i, j))
}
}
}
return res
}
#
func readBinaryWatch(num int) []string {
res := make([]string, 0)
for i := 0; i < 12; i++ {
for j := 0; j < 60; j++ {
hour := fmt.Sprintf("%b", i)
minute := fmt.Sprintf("%b", j)
if strings.Count(hour, "1")+strings.Count(minute, "1") == num {
res = append(res, fmt.Sprintf("%d:%02d", i, j))
}
}
}
return res
}
#
func readBinaryWatch(num int) []string {
res := make([]string, 0)
ledS := make([]bool, 10)
var dfs func(int, int)
dfs = func(idx, num int) {
if num == 0 {
m, h := get(ledS[:6]), get(ledS[6:])
if h < 12 && m < 60 {
res = append(res, fmt.Sprintf("%d:%02d", h, m))
}
return
}
for i := idx; i < 11-num; i++ {
ledS[i] = true
dfs(i+1, num-1)
ledS[i] = false
}
}
dfs(0, num)
return res
}
func get(ledS []bool) int {
bs := []int{1, 2, 4, 8, 16, 32}
var sum int
size := len(ledS)
for i := 0; i < size; i++ {
if ledS[i] {
sum += bs[i]
}
}
return sum
}
404.左叶子之和(2)
计算给定二叉树的所有左叶子之和。
示例：
3
/ \
9 20
/ \
15 7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(log(n)) |
| 02 |
迭代 |
O(n) |
O(n) |
func sumOfLeftLeaves(root *TreeNode) int {
if root == nil {
return 0
}
if root.Left == nil {
return sumOfLeftLeaves(root.Right)
}
if root.Left.Left == nil && root.Left.Right == nil {
return root.Left.Val + sumOfLeftLeaves(root.Right)
}
return sumOfLeftLeaves(root.Left) + sumOfLeftLeaves(root.Right)
}
#
func sumOfLeftLeaves(root *TreeNode) int {
sum := 0
if root == nil{
return 0
}
queue := make([]*TreeNode,0)
queue = append(queue, root)
for len(queue) > 0{
node := queue[0]
queue = queue[1:]
if node.Left != nil && node.Left.Left == nil && node.Left.Right == nil{
sum = sum + node.Left.Val
}
if node.Left != nil{
queue = append(queue, node.Left)
}
if node.Right != nil{
queue = append(queue, node.Right)
}
}
return sum
}
405.数字转换为十六进制数(2)
给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。
注意:
十六进制中所有字母(a-f)都必须是小写。
十六进制字符串中不能包含多余的前导零。
如果要转化的数为0，那么以单个字符'0'来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。
给定的数确保在32位有符号整数范围内。
不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。
示例 1： 输入:26 输出:"1a"
示例 2： 输入:-1 输出:"ffffffff"
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
位运算 |
O(1) |
O(1) |
| 02 |
遍历 |
O(1) |
O(1) |
var h = []string{
"0", "1", "2", "3", "4", "5", "6", "7",
"8", "9", "a", "b", "c", "d", "e", "f",
}
func toHex(num int) string {
hex := ""
if num == 0 {
return "0"
}
for i := 0; i < 8 && num != 0; i++ {
hex = h[num&15] + hex
num = num >> 4
}
return hex
}
#
var h = []string{
"0", "1", "2", "3", "4", "5", "6", "7",
"8", "9", "a", "b", "c", "d", "e", "f",
}
func toHex(num int) string {
res := ""
if num == 0{
return "0"
}
if num < 0 {
num = num + 4294967296
}
for num != 0{
temp := num % 16
res = h[temp] + res
num = num / 16
}
return res
}
409.最长回文串(2)
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
注意:假设字符串的长度不会超过 1010。
示例 1:输入:"abccccdd"输出:7
解释:我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数组辅助 |
O(n) |
O(1) |
| 02 |
哈希辅助 |
O(n) |
O(1) |
func longestPalindrome(s string) int {
ret := 0
a := [123]int{}
for i := range s {
a[s[i]]++
}
hasOdd := 0
for i := range a {
if a[i] == 0 {
continue
}
if a[i] % 2 == 0 {
ret += a[i]
} else {
ret += a[i] - 1
hasOdd = 1
}
}
return ret + hasOdd
}
#
func longestPalindrome(s string) int {
ret := 0
a := make(map[byte]int)
for i := range s {
a[s[i]]++
}
hasOdd := 0
for i := range a {
if a[i] == 0 {
continue
}
if a[i]%2 == 0 {
ret += a[i]
} else {
ret += a[i] - 1
hasOdd = 1
}
}
return ret + hasOdd
}
412.Fizz Buzz(1)
写一个程序，输出从 1 到 n 数字的字符串表示。
1. 如果 n 是3的倍数，输出“Fizz”；
2. 如果 n 是5的倍数，输出“Buzz”；
3.如果 n 同时是3和5的倍数，输出 “FizzBuzz”。
示例：n = 15,
返回:
[
"1",
"2",
"Fizz",
"4",
"Buzz",
"Fizz",
"7",
"8",
"Fizz",
"Buzz",
"11",
"Fizz",
"13",
"14",
"FizzBuzz"
]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
func fizzBuzz(n int) []string {
ret := make([]string, n)
for i := range ret {
x := i + 1
switch {
case x%15 == 0:
ret[i] = "FizzBuzz"
case x%5 == 0:
ret[i] = "Buzz"
case x%3 == 0:
ret[i] = "Fizz"
default:
ret[i] = strconv.Itoa(x)
}
}
return ret
}
414.第三大的数(2)
给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
示例 1:输入: [3, 2, 1]输出: 1
解释: 第三大的数是 1.
示例 2:输入: [1, 2]输出: 2
解释: 第三大的数不存在, 所以返回最大的数 2 .
示例 3:输入: [2, 2, 3, 1]输出: 1
解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。存在两个值为2的数，它们都排第二。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
排序遍历 |
O(nlog(n)) |
O(1) |
func thirdMax(nums []int) int {
max1, max2, max3 := math.MinInt64, math.MinInt64, math.MinInt64
for _, n := range nums {
if n == max1 || n == max2 {
continue
}
switch {
case max1 < n:
max1, max2, max3 = n, max1, max2
case max2 < n:
max2, max3 = n, max2
case max3 < n:
max3 = n
}
}
if max3 == math.MinInt64 {
return max1
}
return max3
}
#
func thirdMax(nums []int) int {
sort.Ints(nums)
if len(nums) < 3 {
return nums[len(nums)-1]
}
k := 2
maxValue := nums[len(nums)-1]
for i := len(nums) - 2; i >= 0; i-- {
if nums[i] != nums[i+1] {
k--
}
if k == 0 {
return nums[i]
}
}
return maxValue
}
415.字符串相加(2)
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。
注意：
num1 和num2 的长度都小于 5100.
num1 和num2 都只包含数字 0-9.
num1 和num2 都不包含任何前导零。
你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
模拟遍历 |
O(n) |
O(1) |
| 02 |
逆置进位模拟 |
O(n) |
O(1) |
func addStrings(num1 string, num2 string) string {
if len(num1) > len(num2) {
num1, num2 = num2, num1
}
n1, n2 := len(num1), len(num2)
a1, a2 := []byte(num1), []byte(num2)
carry := byte(0)
buf := make([]byte, n2+1)
buf[0] = '1'
for i := 1; i <= n2; i++ {
if i <= n1 {
buf[n2+1-i] = a1[n1-i] - '0'
}
buf[n2+1-i] = buf[n2+1-i] + a2[n2-i] + carry
if buf[n2+1-i] > '9' {
buf[n2+1-i] = buf[n2+1-i] - 10
carry = byte(1)
} else {
carry = byte(0)
}
}
if carry == 1 {
return string(buf)
}
return string(buf[1:])
}
#
func addStrings(num1 string, num2 string) string {
if len(num1) > len(num2) {
num1, num2 = num2, num1
}
n1, n2 := len(num1), len(num2)
a1, a2 := []byte(num1), []byte(num2)
a1 = reverse(a1)
a2 = reverse(a2)
carry := 0
buf := make([]byte, 0)
for i := 0; i < n2; i++ {
temp := 0
if i < n1 {
temp = int(a1[i] - '0')
}
temp = int(a2[i]-'0') + temp + carry
if temp > 9 {
buf = append(buf, byte(temp-10+'0'))
carry = 1
} else {
buf = append(buf, byte(temp+'0'))
carry = 0
}
}
if carry == 1 {
buf = append(buf, byte('1'))
}
return string(reverse(buf))
}
func reverse(arr []byte) []byte {
for i := 0; i < len(arr)/2; i++ {
arr[i], arr[len(arr)-1-i] = arr[len(arr)-1-i], arr[i]
}
return arr
}
434.字符串中的单词数(2)
统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。
请注意，你可以假定字符串里不包括任何不可打印的字符。
示例:输入: "Hello, my name is John"输出: 5
解释: 这里的单词是指连续的不是空格的字符，所以 "Hello," 算作 1 个单词。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
内置函数 |
O(n) |
O(n) |
| 02 |
遍历 |
O(n) |
O(1) |
func countSegments(s string) int {
if len(s) == 0 {
return 0
}
return len(strings.Fields(s))
}
#
func countSegments(s string) int {
count := 0
for i := 0; i < len(s); i++{
if (i == 0 || s[i-1] == ' ') && s[i] != ' '{
count++
}
}
return count
}
437.路径总和III(4)
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
返回 3。和等于 8 的路径有:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n^2) |
O(n) |
| 02 |
2次递归 |
O(n^2) |
O(n) |
| 03 |
迭代+递归 |
O(n^2) |
O(n) |
| 04 |
保存路径 |
O(n^2) |
O(n) |
func pathSum(root *TreeNode, sum int) int {
if root == nil {
return 0
}
res := 0
var helper func(*TreeNode, int)
helper = func(node *TreeNode, sum int) {
if node == nil {
return
}
sum = sum - node.Val
if sum == 0 {
res++
}
helper(node.Left, sum)
helper(node.Right, sum)
}
helper(root, sum)
return res + pathSum(root.Left, sum) + pathSum(root.Right, sum)
}
#
func helper(node *TreeNode, sum int) int {
if node == nil {
return 0
}
sum = sum - node.Val
res := 0
if sum == 0 {
res = 1
}
return res + helper(node.Left, sum) + helper(node.Right, sum)
}
func pathSum(root *TreeNode, sum int) int {
if root == nil {
return 0
}
return helper(root, sum) + pathSum(root.Left, sum) + pathSum(root.Right, sum)
}
# 迭代+递归
func helper(node *TreeNode, sum int, curSum int) int {
res := 0
curSum = curSum + node.Val
if curSum == sum {
res++
}
if node.Left != nil {
res += helper(node.Left, sum, curSum)
}
if node.Right != nil {
res += helper(node.Right, sum, curSum)
}
return res
}
func pathSum(root *TreeNode, sum int) int {
if root == nil {
return 0
}
queue := make([]*TreeNode, 0)
queue = append(queue, root)
res := 0
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
tempSum := 0
res += helper(node, sum, tempSum)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
return res
}
#
func helper(node *TreeNode, sum int, path []int, level int) int {
if node == nil {
return 0
}
res := 0
if sum == node.Val {
res = 1
}
temp := node.Val
for i := level - 1; i >= 0; i-- {
temp = temp + path[i]
if temp == sum {
res++
}
}
path[level] = node.Val
return res + helper(node.Left, sum, path, level+1) +
helper(node.Right, sum, path, level+1)
}
func pathSum(root *TreeNode, sum int) int {
return helper(root, sum, make([]int, 1001), 0)
}
441.排列硬币(3)
你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
给定一个数字 n，找出可形成完整阶梯行的总行数。
n 是一个非负整数，并且在32位有符号整型的范围内。
示例 1:n = 5
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤
因为第三行不完整，所以返回2.
示例 2:n = 8
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
因为第四行不完整，所以返回3.
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数学法 |
O(1) |
O(1) |
| 02 |
迭代 |
O(n^1/2) |
O(1) |
| 03 |
二分查找 |
O(log(n)) |
O(1) |
func arrangeCoins(n int) int {
return int(math.Sqrt(float64(2*n)+0.25) - 0.5)
}
#
func arrangeCoins(n int) int {
i := 1
for i <= n{
n = n - i
i++
}
return i-1
}
#
func arrangeCoins(n int) int {
if n == 0{
return 0
}
left, right := 1, n
for left < right{
mid := left + (right-left)/2
if mid * (mid+1)/2 < n{
left = mid + 1
}else {
right = mid
}
}
if left*(left+1)/2 == n{
return left
}
return left-1
}
443.压缩字符串(1)
给定一组字符，使用原地算法将其压缩。
压缩后的长度必须始终小于或等于原数组长度。
数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。
在完成原地修改输入数组后，返回数组的新长度。
进阶：你能否仅使用O(1) 空间解决问题？
示例 1：输入：["a","a","b","b","c","c","c"]
输出：返回6，输入数组的前6个字符应该是：["a","2","b","2","c","3"]
说明："aa"被"a2"替代。"bb"被"b2"替代。"ccc"被"c3"替代。
示例 2：输入：["a"]
输出：返回1，输入数组的前1个字符应该是：["a"]
说明：没有任何字符串被替代。
示例 3：输入：["a","b","b","b","b","b","b","b","b","b","b","b","b"]
输出：返回4，输入数组的前4个字符应该是：["a","b","1","2"]。
说明：由于字符"a"不重复，所以不会被压缩。"bbbbbbbbbbbb"被“b12”替代。
注意每个数字在数组中都有它自己的位置。
注意：
所有字符都有一个ASCII值在[35, 126]区间内。
1 <= len(chars) <= 1000。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双指针 |
O(n) |
O(1) |
func compress(chars []byte) int {
j := 0
count := 1
for i := 0; i < len(chars); i++ {
char := chars[i]
if i+1 < len(chars) && char == chars[i+1] {
count++
} else {
chars[j] = char
j++
if count > 1 {
for _, num := range strconv.Itoa(count) {
chars[j] = byte(num)
j++
}
}
count = 1
}
}
return j
}
447.回旋镖的数量(1)
给定平面上 n 对不同的点，“回旋镖” 是由点表示的元组 (i, j, k) ，
其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。
找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。
示例:
输入:[[0,0],[1,0],[2,0]]
输出:2
解释:两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助+遍历 |
O(n^2) |
O(n) |
func numberOfBoomerangs(points [][]int) int {
res := 0
size := len(points)
if size < 3 {
return 0
}
for i := 0; i < size; i++ {
dMap := make(map[int]int, size)
for j := 0; j < size; j++ {
if i == j {
continue
}
d := dSquare(points[i], points[j])
if _, ok := dMap[d]; ok {
dMap[d]++
} else {
dMap[d] = 1
}
}
for _, v := range dMap {
res = res + v*(v-1)
}
}
return res
}
func dSquare(p1, p2 []int) int {
x := p2[0] - p1[0]
y := p2[1] - p1[1]
return x*x + y*y
}
448.找到所有数组中消失的数字(3)
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例:输入:[4,3,2,7,8,2,3,1]输出:[5,6]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历交换 |
O(n) |
O(1) |
| 02 |
遍历置反 |
O(n) |
O(1) |
| 03 |
哈希辅助 |
O(n) |
O(n) |
func findDisappearedNumbers(nums []int) []int {
for i := 0; i < len(nums); i++ {
for nums[i] != nums[nums[i]-1] {
nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
}
}
res := make([]int, 0)
for i, n := range nums {
if n != i+1 {
res = append(res, i+1)
}
}
return res
}
#
func findDisappearedNumbers(nums []int) []int {
for i := 0; i < len(nums); i++ {
value := nums[i]
if value < 0{
value = -value
}
if nums[value-1] > 0{
nums[value-1] = -nums[value-1]
}
}
res := make([]int, 0)
for key, value := range nums {
if value > 0{
res = append(res, key+1)
}
}
return res
}
#
func findDisappearedNumbers(nums []int) []int {
m := make(map[int]int)
for i := 0; i < len(nums); i++ {
m[nums[i]] = 1
}
res := make([]int, 0)
for i := 0; i < len(nums); i++ {
if _, ok := m[i+1]; !ok {
res = append(res, i+1)
}
}
return res
}
453.最小移动次数使数组元素相等(2)
给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动可以使 n - 1 个元素增加 1。
示例:输入:[1,2,3]输出:3
解释:只需要3次移动（注意每次移动会增加两个元素的值）：
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数学公式 |
O(n) |
O(1) |
| 02 |
排序遍历 |
O(nlog(n)) |
O(1) |
func minMoves(nums []int) int {
sum := 0
min := nums[0]
for _, n := range nums {
sum += n
if min > n {
min = n
}
}
return sum - min*len(nums)
}
#
func minMoves(nums []int) int {
sum := 0
sort.Ints(nums)
for i := 1; i < len(nums); i++{
sum = sum + nums[i] - nums[0]
}
return sum
}
455.分发饼干(1)
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；
并且每块饼干 j ，都有一个尺寸 sj 。
如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。
你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
注意：你可以假设胃口值为正。一个小朋友最多只能拥有一块饼干。
示例 1:输入: [1,2,3], [1,1] 输出: 1
解释: 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。所以你应该输出1。
示例 2:输入: [1,2], [1,2,3] 输出: 2
解释: 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输出2.
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序双指针 |
O(nlog(n)) |
O(1) |
func findContentChildren(g []int, s []int) int {
sort.Ints(g)
sort.Ints(s)
var i, j int
for i < len(g) && j < len(s) {
if g[i] <= s[j] {
i++
}
j++
}
return i
}
459.重复的子字符串(2)
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。
给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:输入: "abab"输出: True
解释: 可由子字符串 "ab" 重复两次构成。
示例 2:输入: "aba"输出: False
示例 3:输入: "abcabcabcabc"输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
2倍去除首尾匹配 |
O(n) |
O(1) |
| 02 |
暴力匹配 |
O(n^2) |
O(1) |
func repeatedSubstringPattern(s string) bool {
if len(s) == 0 {
return false
}
size := len(s)
ss := (s + s)[1 : size*2-1]
return strings.Contains(ss, s)
}
#
func repeatedSubstringPattern(s string) bool {
if len(s) == 0 {
return false
}
size := len(s)
for i := 1; i < size; i++ {
if size%i == 0 {
count := size / i
if strings.Repeat(s[0:i], count) == s {
return true
}
}
}
return false
}
461.汉明距离(3)
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
注意：
0 ≤ x, y < 231.
示例:
输入: x = 1, y = 4输出: 2
解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
位运算+遍历统计 |
O(1) |
O(1) |
| 02 |
位运算 |
O(1) |
O(1) |
| 03 |
内置函数 |
O(1) |
O(1) |
func hammingDistance(x int, y int) int {
x = x ^ y
res := 0
for x > 0 {
if x&1 == 1{
res++
}
x = x >> 1
}
return res
}
#
func hammingDistance(x int, y int) int {
x = x ^ y
res := 0
for x > 0 {
res++
x = x & (x-1)
}
return res
}
#
func hammingDistance(x int, y int) int {
x = x ^ y
return bits.OnesCount(uint(x))
}
463.岛屿的周长(3)
给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地 0 表示水域。
网格中的格子水平和垂直方向相连（对角线方向不相连）。
整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。
网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
示例 :
输入:
[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]
输出: 16
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n^2) |
O(1) |
| 02 |
暴力法 |
O(n^2) |
O(1) |
| 03 |
深度优先搜索 |
O(n^2) |
O(n^2) |
func islandPerimeter(grid [][]int) int {
var dx = []int{-1, 1, 0, 0}
var dy = []int{0, 0, -1, 1}
m, n := len(grid), len(grid[0])
res := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 0 {
continue
}
res += 4
for k := 0; k < 4; k++ {
x := i + dx[k]
y := j + dy[k]
if (0 <= x && x < m && 0 <= y && y < n) && grid[x][y] == 1 {
res--
}
}
}
}
return res
}
#
func islandPerimeter(grid [][]int) int {
m, n := len(grid), len(grid[0])
res := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 0 {
continue
}
res += 4
if i > 0 && grid[i-1][j] == 1 {
res -= 2
}
if j > 0 && grid[i][j-1] == 1 {
res -= 2
}
}
}
return res
}
#
func islandPerimeter(grid [][]int) int {
m, n := len(grid), len(grid[0])
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 1 {
return dfs(grid, i, j)
}
}
}
return 0
}
func dfs(grid [][]int, i, j int) int {
if !(0 <= i && i < len(grid) && 0 <= j && j < len(grid[0])) {
return 1
}
if grid[i][j] == 0 {
return 1
}
if grid[i][j] != 1 {
return 0
}
grid[i][j] = 2
return dfs(grid, i-1, j) +
dfs(grid, i+1, j) +
dfs(grid, i, j-1) +
dfs(grid, i, j+1)
}
475.供暖器(2)
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
现在，给出位于一条水平线上的房屋和供暖器的位置，找到可以覆盖所有房屋的最小加热半径。
所以，你的输入将会是房屋和供暖器的位置。你将输出供暖器的最小加热半径。
说明:
给出的房屋和供暖器的数目是非负数且不会超过 25000。
给出的房屋和供暖器的位置均是非负数且不会超过10^9。
只要房屋位于供暖器的半径内(包括在边缘上)，它就可以得到供暖。
所有供暖器都遵循你的半径标准，加热的半径也一样。
示例 1:输入: [1,2,3],[2] 输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。
示例 2:输入: [1,2,3,4],[1,4] 输出: 1
解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序双指针 |
O(nlog(n)) |
O(1) |
| 02 |
排序二分查找 |
O(nlog(n)) |
O(1) |
func findRadius(houses []int, heaters []int) int {
if len(heaters) == 0 {
return 0
}
sort.Ints(houses)
sort.Ints(heaters)
res := 0
j := 0
for i := 0; i < len(houses); i++ {
for j < len(heaters)-1 &&
Abs(houses[i], heaters[j]) >= Abs(houses[i], heaters[j+1]) {
j++
}
res = Max(Abs(houses[i], heaters[j]), res)
}
return res
}
func Abs(a, b int) int {
if a > b {
return a - b
}
return b - a
}
func Max(a, b int) int {
if a > b {
return a
}
return b
}
#
func findRadius(houses []int, heaters []int) int {
if len(heaters) == 0 {
return 0
}
sort.Ints(houses)
sort.Ints(heaters)
res := 0
length := len(heaters)
for i := 0; i < len(houses); i++ {
left := 0
right := length - 1
for left < right {
mid := left + (right-left)/2
if heaters[mid] < houses[i] {
left = mid + 1
} else {
right = mid
}
}
dis := 0
if heaters[left] < houses[i] {
dis = houses[i] - heaters[left]
} else if heaters[left] > houses[i] {
if left == 0 {
dis = heaters[0] - houses[i]
} else {
dis = Min(heaters[left]-houses[i], houses[i]-heaters[left-1])
}
}
res = Max(res, dis)
}
return res
}
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
}
476.数字的补数(3)
给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。
示例 1:输入: 5 输出: 2
解释: 5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。
示例 2:输入: 1 输出: 0
解释: 1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。
注意:
给定的整数保证在 32 位带符号整数的范围内。
你可以假定二进制数不包含前导零位。
本题与 1009 https://leetcode.cn/problems/complement-of-base-10-integer/ 相同
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
位运算 |
O(log(n)) |
O(1) |
| 02 |
位运算 |
O(log(n)) |
O(1) |
| 03 |
遍历 |
O(log(n)) |
O(1) |
func findComplement(num int) int {
temp := 1
for num >= temp {
temp = temp << 1
}
return temp - 1 - num
}
#
func findComplement(num int) int {
temp := num
res := 0
for temp > 0 {
temp = temp >> 1
res = res << 1
res++
}
return res ^ num
}
#
func findComplement(num int) int {
res := 0
if num == 0 {
return 1
}
if num == 1 {
return 0
}
exp := 1
for num > 0 {
temp := num % 2
if temp == 0 {
res = res + exp
exp = exp * 2
} else {
exp = exp * 2
}
num = num / 2
}
return res
}
482.密钥格式化(2)
有一个密钥字符串 S ，只包含字母，数字以及 '-'（破折号）。
其中， N 个 '-' 将字符串分成了 N+1 组。
给你一个数字 K，请你重新格式化字符串，除了第一个分组以外，每个分组要包含 K 个字符；
而第一个分组中，至少要包含 1 个字符。
两个分组之间需要用 '-'（破折号）隔开，并且将所有的小写字母转换为大写字母。
给定非空字符串 S 和数字 K，按照上面描述的规则进行格式化。
示例 1：输入：S = "5F3Z-2e-9-w", K = 4 输出："5F3Z-2E9W"
解释：字符串 S 被分成了两个部分，每部分 4 个字符；注意，两个额外的破折号需要删掉。
示例 2：输入：S = "2-5g-3-J", K = 2 输出："2-5G-3J"
解释：字符串 S 被分成了 3 个部分，按照前面的规则描述，
第一部分的字符可以少于给定的数量，其余部分皆为 2 个字符。
提示:
S 的长度可能很长，请按需分配大小。K 为正整数。
S 只包含字母数字（a-z，A-Z，0-9）以及破折号'-'
S 非空
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
内置函数 |
O(n) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
func licenseKeyFormatting(S string, K int) string {
arr := strings.Join(strings.Split(strings.ToUpper(S), "-"), "")
count := len(arr) / K
first := len(arr) % K
if first > 0 {
count++
}
str := arr[:first]
if first != 0 {
count = count - 1
}
for i := 0; i < count; i++ {
str = str + "-" + arr[first+i*K:first+(i+1)*K]
}
return strings.Trim(str, "-")
}
#
func licenseKeyFormatting(S string, K int) string {
res := make([]rune, 0)
temp := []rune(S)
count := 0
for i := len(temp) - 1; i >= 0; i-- {
value := temp[i]
if value >= 'a' {
value = value - 'a' + 'A'
}
if value == '-' {
continue
}
count++
res = append([]rune{value}, res...)
if count == K {
res = append([]rune{'-'}, res...)
count = 0
}
}
if len(res) == 0 {
return ""
}
if res[0] == '-' {
res = res[1:]
}
return string(res)
}
485.最大连续1的个数(2)
给定一个二进制数组， 计算其中最大连续1的个数。
示例 1:输入: [1,1,0,1,1,1]输出: 3
解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.
注意：
输入的数组只包含 0 和1。
输入数组的长度是正整数，且不超过 10,000。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双指针 |
O(n) |
O(1) |
| 02 |
单指针 |
O(n) |
O(1) |
func findMaxConsecutiveOnes(nums []int) int {
max := 0
for i, j := 0, -1; i < len(nums); i++ {
if nums[i] == 0 {
j = i
} else {
if max < i-j {
max = i - j
}
}
}
return max
}
#
func findMaxConsecutiveOnes(nums []int) int {
max := 0
count := 0
for _, v := range nums {
if v == 1 {
count++
} else {
if count > max {
max = count
}
count = 0
}
}
if count > max {
max = count
}
return max
}
492.构造矩形(1)
作为一位web开发者， 懂得怎样去规划一个页面的尺寸是很重要的。
现给定一个具体的矩形页面面积，你的任务是设计一个长度为 L 和宽度为 W 且满足以下要求的矩形的页面。要求：
1. 你设计的矩形页面必须等于给定的目标面积。
2. 宽度 W 不应大于长度 L，换言之，要求 L >= W 。
3. 长度 L 和宽度 W 之间的差距应当尽可能小。
你需要按顺序输出你设计的页面的长度 L 和宽度 W。
示例：
输入: 4 输出: [2, 2]
解释: 目标面积是 4， 所有可能的构造方案有 [1,4], [2,2], [4,1]。
但是根据要求2，[1,4] 不符合要求; 根据要求3，[2,2] 比 [4,1] 更能符合要求.
所以输出长度 L 为 2， 宽度 W 为 2。
说明:
给定的面积不大于 10,000,000 且为正整数。
你设计的页面的长度和宽度必须都是正整数。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
开方向下遍历 |
O(n) |
O(1) |
func constructRectangle(area int) []int {
for i := int(math.Sqrt(float64(area))); i > 1; i-- {
if area%i == 0 {
return []int{area / i, i}
}
}
return []int{area, 1}
}
496.下一个更大元素 I(3)
给定两个没有重复元素的数组nums1 和 nums2 ，其中nums1 是 nums2 的子集。
找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。
如果不存在，对应位置输出 -1 。
示例 1:
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。
示例 2:
输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
提示：
nums1和nums2中所有元素是唯一的。
nums1和nums2 的数组大小都不超过1000。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n^2) |
O(n) |
| 02 |
哈希辅助 |
O(n^2) |
O(n) |
| 02 |
栈+哈希辅助 |
O(n) |
O(n) |
func nextGreaterElement(nums1 []int, nums2 []int) []int {
m := make(map[int]int)
for i, n := range nums2 {
m[n] = i
}
res := make([]int, len(nums1))
for i, n := range nums1 {
res[i] = -1
for j := m[n] + 1; j < len(nums2); j++ {
if n < nums2[j] {
res[i] = nums2[j]
break
}
}
}
return res
}
#
func nextGreaterElement(nums1 []int, nums2 []int) []int {
m := make(map[int]int)
res := make([]int, len(nums1))
for i := 0; i < len(nums2); i++ {
for j := i + 1; j < len(nums2); j++ {
if nums2[j] > nums2[i] {
m[nums2[i]] = nums2[j]
break
}
}
}
for key, value := range nums1 {
if _, ok := m[value]; ok {
res[key] = m[value]
} else {
res[key] = -1
}
}
return res
}
#
func nextGreaterElement(nums1 []int, nums2 []int) []int {
m := make(map[int]int)
res := make([]int, len(nums1))
stack := make([]int, 0)
for i := 0; i < len(nums2); i++ {
if len(stack) > 0 {
for len(stack) > 0 && nums2[i] > stack[len(stack)-1] {
top := stack[len(stack)-1]
m[top] = nums2[i]
stack = stack[:len(stack)-1]
}
}
stack = append(stack, nums2[i])
}
for key, value := range nums1 {
if _, ok := m[value]; ok {
res[key] = m[value]
} else {
res[key] = -1
}
}
return res
}
500.键盘行(4)
给定一个单词列表，只返回可以使用在键盘同一行的字母打印出来的单词。键盘如下图所示。
示例：
输入: ["Hello", "Alaska", "Dad", "Peace"]
输出: ["Alaska", "Dad"]
注意：
你可以重复使用键盘上同一字符。
你可以假设输入的字符串将只包含字母。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n^2) |
O(1) |
| 02 |
哈希辅助 |
O(n^2) |
O(1) |
| 03 |
遍历 |
O(n^2) |
O(1) |
| 04 |
内置函数 |
O(n^2) |
O(1) |
func findWords(words []string) []string {
m := make(map[byte]int)
m['q'] = 1
m['w'] = 1
m['e'] = 1
m['r'] = 1
m['t'] = 1
m['y'] = 1
m['u'] = 1
m['i'] = 1
m['o'] = 1
m['p'] = 1
m['a'] = 2
m['s'] = 2
m['d'] = 2
m['f'] = 2
m['g'] = 2
m['h'] = 2
m['j'] = 2
m['k'] = 2
m['l'] = 2
m['z'] = 3
m['x'] = 3
m['c'] = 3
m['v'] = 3
m['b'] = 3
m['n'] = 3
m['m'] = 3
res := make([]string, 0)
for i := 0; i < len(words); i++ {
b := []byte(strings.ToLower(words[i]))
level := m[b[0]]
flag := true
for j := 1; j < len(b); j++ {
if m[b[j]] != level {
flag = false
break
}
}
if flag {
res = append(res, words[i])
}
}
return res
}
#
var qRow = map[byte]bool{
'q': true,
'w': true,
'e': true,
'r': true,
't': true,
'y': true,
'u': true,
'i': true,
'o': true,
'p': true,
}
var aRow = map[byte]bool{
'a': true,
's': true,
'd': true,
'f': true,
'g': true,
'h': true,
'j': true,
'k': true,
'l': true,
}
var zRow = map[byte]bool{
'z': true,
'x': true,
'c': true,
'v': true,
'b': true,
'n': true,
'm': true,
}
func findWords(words []string) []string {
res := make([]string, 0, len(words))
for _, word := range words {
w := strings.ToLower(word)
if isAllIn(w, qRow) || isAllIn(w, aRow) || isAllIn(w, zRow) {
res = append(res, word)
}
}
return res
}
func isAllIn(s string, Row map[byte]bool) bool {
for i := range s {
if !Row[s[i]] {
return false
}
}
return true
}
#
func findWords(words []string) []string {
res := make([]string, 0, len(words))
for _, word := range words {
w := strings.ToLower(word)
flag := 0
for _, m := range w {
switch m {
case 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p':
if flag != 0 && flag != 1 {
flag = 4
break
}
flag = 1
case 'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l':
if flag != 0 && flag != 2 {
flag = 4
break
}
flag = 2
case 'z', 'x', 'c', 'v', 'b', 'n', 'm':
if flag != 0 && flag != 3 {
flag = 4
break
}
flag = 3
default:
flag = 4
}
}
if flag != 0 && flag != 4 {
res = append(res, word)
}
}
return res
}
#
func findWords(words []string) []string {
res := make([]string, 0, len(words))
q := "qwertyuiopQWERTYUIOP"
a := "asdfghjklASDFGHJKL"
z := "zxcvbnmZXCVBNM"
for _, word := range words {
qLen, aLen, zLen := 0, 0, 0
for i := 0; i < len(word); i++ {
if strings.Contains(q, string(word[i])) {
qLen++
}
if strings.Contains(a, string(word[i])) {
aLen++
}
if strings.Contains(z, string(word[i])) {
zLen++
}
}
if qLen == len(word) || aLen == len(word) || zLen == len(word) {
res = append(res, word)
}
}
return res
}
0401-0500-Medium
402.移掉K位数字(1)
给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意:num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。
示例 1 :输入: num = "1432219", k = 3 输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
示例 2 :输入: num = "10200", k = 1 输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 :输入: num = "10", k = 2 输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
单调栈-贪心 |
O(n) |
O(n) |
func removeKdigits(num string, k int) string {
stack := make([]byte, 0)
res := ""
for i := 0; i < len(num); i++ {
value := num[i]
for len(stack) > 0 && stack[len(stack)-1] > value && k > 0 {
stack = stack[:len(stack)-1]
k--
}
stack = append(stack, value)
}
stack = stack[:len(stack)-k]
res = strings.TrimLeft(string(stack), "0")
if res == "" {
return "0"
}
return res
}
406.根据身高重建队列(2)
假设有打乱顺序的一群人站成一个队列。
每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。
编写一个算法来重建这个队列。
注意： 总人数少于1100人。
示例 输入:[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
输出:[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序遍历 |
O(n^2) |
O(n) |
| 02 |
排序遍历 |
O(n^2) |
O(n) |
func reconstructQueue(people [][]int) [][]int {
sort.Slice(people, func(i, j int) bool {
if people[i][0] == people[j][0] {
return people[i][1] < people[j][1]
}
return people[i][0] > people[j][0]
})
for i := 0; i < len(people); i++ {
index := people[i][1]
p := people[i]
copy(people[index+1:i+1], people[index:i+1])
people[index] = p
}
return people
}
# 2
func reconstructQueue(people [][]int) [][]int {
sort.Slice(people, func(i, j int) bool {
if people[i][0] == people[j][0] {
return people[i][1] < people[j][1]
}
return people[i][0] > people[j][0]
})
for i := 0; i < len(people); i++ {
index := people[i][1]
p := people[i]
for j := i; j > index; j-- {
people[j] = people[j-1]
}
people[index] = p
}
return people
}
413.等差数列划分(3)
如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。
例如，以下数列为等差数列:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下数列不是等差数列。
1, 1, 2, 5, 7
数组 A 包含 N 个数，且索引从0开始。
数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。
如果满足以下条件，则称子数组(P, Q)为等差数组：
元素 A[P], A[p + 1], ..., A[Q - 1], A[Q] 是等差的。并且P + 1 < Q 。
函数要返回数组 A 中所有为等差数组的子数组个数。
示例:A = [1, 2, 3, 4]
返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
动态规划 |
O(n) |
O(n) |
| 03 |
暴力法 |
O(n^2) |
O(1) |
func numberOfArithmeticSlices(A []int) int {
n := len(A)
if n < 3 {
return 0
}
res := 0
count := 2
diff := A[1] - A[0]
for i := 2; i < n; i++ {
a := A[i] - A[i-1]
if a == diff {
count++
} else {
if count >= 3 {
res = res + getValue(count)
}
count = 2
diff = a
}
}
if count >= 3 {
res = res + getValue(count)
}
return res
}
func getValue(num int) int {
n := num - 2
return n * (n + 1) / 2
}
# 2
func numberOfArithmeticSlices(A []int) int {
n := len(A)
if n < 3 {
return 0
}
res := 0
dp := make([]int, n)
for i := 2; i < n; i++ {
if A[i]-A[i-1] == A[i-1]-A[i-2] {
dp[i] = dp[i-1] + 1
}
res = res + dp[i]
}
return res
}
# 3
func numberOfArithmeticSlices(A []int) int {
n := len(A)
if n < 3 {
return 0
}
res := 0
for i := 0; i < n-2; i++ {
diff := A[i+1] - A[i]
for j := i + 2; j < n; j++ {
if A[j]-A[j-1] == diff {
res++
} else {
break
}
}
}
return res
}
416.分割等和子集(3)
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:输入: [1, 5, 11, 5] 输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:输入: [1, 2, 3, 5] 输出: false
解释: 数组不能分割成两个元素和相等的子集.
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n^2) |
| 02 |
动态规划 |
O(n^2) |
O(n) |
| 03 |
回溯-递归 |
O(n!) |
O(n) |
func canPartition(nums []int) bool {
sum := 0
for i := 0; i < len(nums); i++ {
sum = sum + nums[i]
}
if sum%2 == 1 {
return false
}
target := sum / 2
dp := make([][]bool, len(nums)+1)
for i := 0; i <= len(nums); i++ {
dp[i] = make([]bool, target+1)
dp[i][0] = true
}
for i := 1; i <= len(nums); i++ {
for j := 1; j <= target; j++ {
if j-nums[i-1] < 0 {
dp[i][j] = dp[i-1][j]
} else {
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]]
}
}
}
return dp[len(nums)][target]
}
# 2
func canPartition(nums []int) bool {
sum := 0
for i := 0; i < len(nums); i++ {
sum = sum + nums[i]
}
if sum%2 == 1 {
return false
}
target := sum / 2
dp := make([]bool, target+1)
dp[0] = true
for i := 0; i < len(nums); i++ {
for j := target; j >= 0; j-- {
if j-nums[i] >= 0 && dp[j-nums[i]] == true {
dp[j] = true
}
}
}
return dp[target]
}
# 3
func canPartition(nums []int) bool {
sort.Ints(nums)
sum := 0
for i := 0; i < len(nums); i++ {
sum = sum + nums[i]
}
if sum%2 == 1 {
return false
}
target := sum / 2
return dfs(nums, target, 0)
}
func dfs(nums []int, target int, index int) bool {
if target == 0 {
return true
}
for i := index; i < len(nums); i++ {
if index < i && nums[i] == nums[i-1] {
continue
}
if target-nums[i] < 0 {
return false
}
if dfs(nums, target-nums[i], i+1) == true {
return true
}
}
return false
}
417.太平洋大西洋水流问题(2)
给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。
“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。
规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。
请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
提示：输出坐标的顺序不重要
m 和 n 都小于150
示例：给定下面的 5x5 矩阵:
太平洋 ~ ~ ~ ~ ~
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * 大西洋
返回:[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
深度优先搜索 |
O(n^2) |
O(n^2) |
| 02 |
广度优先搜索 |
O(n^2) |
O(n^2) |
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}
var n, m int
func pacificAtlantic(heights [][]int) [][]int {
res := make([][]int, 0)
n, m = len(heights), len(heights[0])
A, B := make([][]bool, n), make([][]bool, n)
for i := 0; i < n; i++ {
A[i], B[i] = make([]bool, m), make([]bool, m)
}
for i := 0; i < n; i++ {
dfs(heights, A, i, 0)
dfs(heights, B, i, m-1)
}
for j := 0; j < m; j++ {
dfs(heights, A, 0, j)
dfs(heights, B, n-1, j)
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if A[i][j] == true && B[i][j] == true {
res = append(res, []int{i, j})
}
}
}
return res
}
func dfs(heights [][]int, visited [][]bool, i, j int) {
visited[i][j] = true
for k := 0; k < 4; k++ {
x, y := dx[k]+i, dy[k]+j
if 0 <= x && x < n && 0 <= y && y < m &&
heights[x][y] >= heights[i][j] && visited[x][y] == false {
dfs(heights, visited, x, y)
}
}
}
# 2
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}
var queue [][2]int
var n, m int
func pacificAtlantic(heights [][]int) [][]int {
res := make([][]int, 0)
n, m = len(heights), len(heights[0])
queue = make([][2]int, 0)
A, B := make([][]bool, n), make([][]bool, n)
for i := 0; i < n; i++ {
A[i], B[i] = make([]bool, m), make([]bool, m)
}
for i := 0; i < n; i++ {
queue = append(queue, [2]int{i, 0})
A[i][0] = true
bfs(heights, A)
queue = append(queue, [2]int{i, m - 1})
B[i][m-1] = true
bfs(heights, B)
}
for j := 0; j < m; j++ {
queue = append(queue, [2]int{0, j})
A[0][j] = true
bfs(heights, A)
queue = append(queue, [2]int{n - 1, j})
B[n-1][j] = true
bfs(heights, B)
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if A[i][j] == true && B[i][j] == true {
res = append(res, []int{i, j})
}
}
}
return res
}
func bfs(heights [][]int, visited [][]bool) {
for len(queue) > 0 {
i, j := queue[0][0], queue[0][1]
queue = queue[1:]
for k := 0; k < 4; k++ {
x, y := dx[k]+i, dy[k]+j
if 0 <= x && x < n && 0 <= y && y < m &&
heights[x][y] >= heights[i][j] && visited[x][y] == false {
visited[x][y] = true
queue = append(queue, [2]int{x, y})
}
}
}
}
419.甲板上的战舰(3)
给定一个二维的甲板， 请计算其中有多少艘战舰。战舰用'X'表示，空位用'.'表示。你需要遵守以下规则：
给你一个有效的甲板，仅由战舰或者空位组成。
战舰只能水平或者垂直放置。换句话说,战舰只能由1xN (1 行, N 列)组成，
或者Nx1 (N 行, 1 列)组成，其中N可以是任意大小。
两艘战舰之间至少有一个水平或垂直的空位分隔- 即没有相邻的战舰。
示例 :
X..X
...X
...X
在上面的甲板中有2艘战舰。
无效样例 :
...X
XXXX
...X
你不会收到这样的无效甲板- 因为战舰之间至少会有一个空位将它们分开。
进阶:你可以用一次扫描算法，只使用O(1)额外空间，并且不修改甲板的值来解决这个问题吗？
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^2) |
O(1) |
| 02 |
遍历 |
O(n^2) |
O(1) |
| 03 |
并查集 |
O(n^2) |
O(n) |
func countBattleships(board [][]byte) int {
res := 0
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[i]); j++ {
if board[i][j] == 'X' {
if (i > 0 && board[i-1][j] == 'X') ||
(j > 0 && board[i][j-1] == 'X') {
continue
}
res++
}
}
}
return res
}
# 2
func countBattleships(board [][]byte) int {
res := 0
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[i]); j++ {
if board[i][j] == 'X' {
res++
board[i][j] = '.'
for x := i + 1; x < len(board); x++ {
if board[x][j] == 'X' {
board[x][j] = '.'
} else {
break
}
}
for y := j + 1; y < len(board[i]); y++ {
if board[i][y] == 'X' {
board[i][y] = '.'
} else {
break
}
}
}
}
}
return res
}
# 3
func countBattleships(board [][]byte) int {
a, b := len(board), len(board[0])
fa = Init(a * b)
m := make(map[int]bool)
arr := make([]int, 0)
for i := 0; i < a; i++ {
for j := 0; j < b; j++ {
if board[i][j] == 'X' {
if i < a-1 && board[i][j] == board[i+1][j] {
union(i*b+j, i*b+b+j)
}
if j < b-1 && board[i][j] == board[i][j+1] {
union(i*b+j, i*b+j+1)
}
arr = append(arr, i*b+j)
}
}
}
for i := 0; i < len(arr); i++ {
m[find(arr[i])] = true
}
return len(m)
}
var fa []int
func Init(n int) []int {
arr := make([]int, n)
for i := 0; i < n; i++ {
arr[i] = i
}
return arr
}
func union(a, b int) {
x, y := find(a), find(b)
if x != y {
fa[x] = y
}
}
func find(x int) int {
if fa[x] != x {
fa[x] = find(fa[x])
}
return fa[x]
}
421.数组中两个数的最大异或值(2)
给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。
进阶：你可以在 O(n) 的时间解决这个问题吗？
示例 1：输入：nums = [3,10,5,25,2,8] 输出：28
解释：最大运算结果是 5 XOR 25 = 28.
示例 2：输入：nums = [0] 输出：0
示例 3：输入：nums = [2,4] 输出：6
示例 4：输入：nums = [8,10,2] 输出：10
示例 5：输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70] 输出：127
提示：1 <= nums.length <= 2 * 104
0 <= nums[i] <= 231 - 1
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希+位运算 |
O(n) |
O(n) |
| 02 |
trie树 |
O(n) |
O(n) |
func findMaximumXOR(nums []int) int {
res := 0
target := 0
for i := 31; i >= 0; i-- {
m := make(map[int]bool)
target = target | (1 << i)
for j := 0; j < len(nums); j++ {
m[nums[j]&target] = true
}
temp := res | (1 << i)
for k := range m {
if _, ok := m[temp^k]; ok {
res = temp
break
}
}
}
return res
}
# 2
func findMaximumXOR(nums []int) int {
n := len(nums)
if n <= 1 {
return 0
}
res := 0
root := Trie{
next: make([]*Trie, 2),
}
for i := 0; i < n; i++ {
temp := &root
for j := 31; j >= 0; j-- {
value := (nums[i] >> j) & 1
if temp.next[value] == nil {
temp.next[value] = &Trie{
next: make([]*Trie, 2),
}
}
temp = temp.next[value]
}
}
for i := 0; i < n; i++ {
temp := &root
cur := 0
for j := 31; j >= 0; j-- {
value := (nums[i] >> j) & 1
if temp.next[value^1] != nil {
cur = cur | (1 << j)
temp = temp.next[value^1]
} else {
temp = temp.next[value]
}
}
res = max(res, cur)
}
return res
}
type Trie struct {
next []*Trie
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
423.从英文中重建数字(1)
给定一个非空字符串，其中包含字母顺序打乱的英文单词表示的数字0-9。按升序输出原始的数字。
注意:输入只包含小写英文字母。
输入保证合法并可以转换为原始的数字，这意味着像 "abc" 或 "zerone" 的输入是不允许的。
输入字符串的长度小于 50,000。
示例 1:输入: "owoztneoer"输出: "012" (zeroonetwo)
示例 2:输入: "fviefuro"输出: "45" (fourfive)
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
func originalDigits(s string) string {
m := make(map[byte]int)
for i := 0; i < len(s); i++ {
m[s[i]]++
}
arr := [10]int{}
arr[0] = m['z']
arr[2] = m['w']
arr[4] = m['u']
arr[6] = m['x']
arr[8] = m['g']
arr[3] = m['t'] - arr[2] - arr[8]
arr[1] = m['o'] - arr[0] - arr[2] - arr[4]
arr[7] = m['s'] - arr[6]
arr[5] = m['v'] - arr[7]
arr[9] = m['i'] - arr[5] - arr[6] - arr[8]
res := make([]byte, 0)
for i := 0; i < 10; i++ {
for j := 0; j < arr[i]; j++ {
res = append(res, byte(i+'0'))
}
}
return string(res)
}
424.替换后的最长重复字符(3)
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换k次。
在执行上述操作后，找到包含重复字母的最长子串的长度。
注意:字符串长度 和 k 不会超过104。
示例 1:输入:s = "ABAB", k = 2输出: 4
解释:用两个'A'替换为两个'B',反之亦然。
示例 2:输入:s = "AABABBA", k = 1 输出: 4
解释:将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双指针 |
O(n) |
O(1) |
| 02 |
双指针 |
O(n) |
O(1) |
| 03 |
暴力法 |
O(n^2) |
O(1) |
func characterReplacement(s string, k int) int {
if s == "" {
return 0
}
res := 0
left := 0
count := 0
arr := [26]int{}
for right := 0; right < len(s); right++ {
arr[s[right]-'A']++
if arr[s[right]-'A'] > count {
count = arr[s[right]-'A']
}
for right-left+1-count > k {
arr[s[left]-'A']--
left++
}
if right-left+1 > res {
res = right - left + 1
}
}
return res
}
# 2
func characterReplacement(s string, k int) int {
if s == "" {
return 0
}
left := 0
count := 0
arr := [26]int{}
for right := 0; right < len(s); right++ {
arr[s[right]-'A']++
if arr[s[right]-'A'] > count {
count = arr[s[right]-'A']
}
if right-left+1-count > k {
arr[s[left]-'A']--
left++
}
}
return len(s) - left
}
# 3
func characterReplacement(s string, k int) int {
if s == "" {
return 0
}
res := 0
for i := 0; i < len(s); i++ {
temp := k
j := i + 1
for ; j < len(s); j++ {
if s[j] != s[i] {
if temp == 0 {
break
}
temp--
}
}
if j-i+temp > len(s) {
return len(s)
}
if j-i+temp > res {
res = j - i + temp
}
}
return res
}
427.建立四叉树(2)
给你一个 n * n 矩阵 grid ，矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。
你需要返回能表示矩阵的 四叉树 的根结点。
注意，当 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：输入：grid = [[0,1],[1,0]] 输出：[[0,1],[1,0],[1,1],[1,1],[1,0]]
解释：此示例的解释如下：
请注意，在下面四叉树的图示中，0 表示 false，1 表示 True 。
示例 2：输入：grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
输出：[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
解释：网格中的所有值都不相同。我们将网格划分为四个子网格。
topLeft，bottomLeft 和 bottomRight 均具有相同的值。
topRight 具有不同的值，因此我们将其再分为 4 个子网格，这样每个子网格都具有相同的值。
解释如下图所示：
示例 3：输入：grid = [[1,1],[1,1]] 输出：[[1,1]]
示例 4：输入：grid = [[0]] 输出：[[1,0]]
示例 5：输入：grid = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]] 输出：[[0,1],[1,1],[1,0],[1,0],[1,1]]
提示：n == grid.length == grid[i].length
n == 2^x 其中 0 <= x <= 6
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(n) |
| 02 |
递归 |
O(n) |
O(n) |
func construct(grid [][]int) *Node {
n := len(grid)
return dfs(grid, 0, 0, n, n)
}
func dfs(grid [][]int, x1, y1, x2, y2 int) *Node {
if x1+1 == x2 {
value := false
if grid[x1][y1] == 1 {
value = true
}
return &Node{
Val: value,
IsLeaf: true,
}
}
midX := (x1 + x2) / 2
midY := (y1 + y2) / 2
tL := dfs(grid, x1, y1, midX, midY)
tR := dfs(grid, x1, midY, midX, y2)
bL := dfs(grid, midX, y1, x2, midY)
bR := dfs(grid, midX, midY, x2, y2)
if tL.IsLeaf == true && tR.IsLeaf == true && bL.IsLeaf == true && bR.IsLeaf == true &&
((tL.Val == true && tR.Val == true && bL.Val == true && bR.Val == true) ||
(tL.Val == false && tR.Val == false && bL.Val == false && bR.Val == false)) {
return &Node{
Val: tL.Val,
IsLeaf: true,
}
}
return &Node{
Val: false,
IsLeaf: false,
TopLeft: tL,
TopRight: tR,
BottomLeft: bL,
BottomRight: bR,
}
}
# 2
func construct(grid [][]int) *Node {
n := len(grid)
return dfs(grid, 0, 0, n, n)
}
func dfs(grid [][]int, x1, y1, x2, y2 int) *Node {
isLeaf := true
for i := x1; i < x2; i++ {
for j := y1; j < y2; j++ {
if grid[i][j] != grid[x1][y1] {
isLeaf = false
break
}
}
}
if isLeaf == true {
return &Node{
Val: grid[x1][y1] == 1,
IsLeaf: true,
}
}
midX := (x1 + x2) / 2
midY := (y1 + y2) / 2
tL := dfs(grid, x1, y1, midX, midY)
tR := dfs(grid, x1, midY, midX, y2)
bL := dfs(grid, midX, y1, x2, midY)
bR := dfs(grid, midX, midY, x2, y2)
return &Node{
Val: false,
IsLeaf: false,
TopLeft: tL,
TopRight: tR,
BottomLeft: bL,
BottomRight: bR,
}
}
429.N叉树的层序遍历(2)
给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
例如，给定一个 3叉树 :
返回其层序遍历:
[
[1],
[3,2,4],
[5,6]
]
说明:
树的深度不会超过 1000。
树的节点总数不会超过 5000。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
层序遍历 |
O(n) |
O(n) |
| 02 |
递归 |
O(n) |
O(n) |
func levelOrder(root *Node) [][]int {
res := make([][]int, 0)
if root == nil {
return res
}
queue := make([]*Node, 0)
queue = append(queue, root)
for len(queue) > 0 {
temp := make([]int, 0)
length := len(queue)
for i := 0; i < length; i++ {
if queue[i] != nil {
temp = append(temp, queue[i].Val)
for j := 0; j < len(queue[i].Children); j++ {
queue = append(queue, queue[i].Children[j])
}
}
}
res = append(res, temp)
queue = queue[length:]
}
return res
}
# 2
var res [][]int
func levelOrder(root *Node) [][]int {
res = make([][]int, 0)
if root == nil {
return res
}
dfs(root, 0)
return res
}
func dfs(root *Node, level int) {
if root == nil {
return
}
if len(res) == level {
res = append(res, make([]int, 0))
}
res[level] = append(res[level], root.Val)
for i := 0; i < len(root.Children); i++ {
dfs(root.Children[i], level+1)
}
}
430.扁平化多级双向链表(3)
多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。
这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。
给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。
示例 1：输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：输入的多级列表如下图所示：
扁平化后的链表如下图：
示例 2：输入：head = [1,2,null,3] 输出：[1,3,2]
解释：输入的多级列表如下图所示：
1---2---NULL
|
3---NULL
示例 3：输入：head = [] 输出：[]
如何表示测试用例中的多级链表？
以 示例 1 为例：
1---2---3---4---5---6--NULL
|
7---8---9---10--NULL
|
11--12--NULL
序列化其中的每一级之后：
[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]
为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。
[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]
合并所有序列化结果，并去除末尾的 null 。
[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
提示：节点数目不超过 1000
1 <= Node.val <= 10^5
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(n) |
| 02 |
递归 |
O(n) |
O(n) |
| 03 |
迭代 |
O(n) |
O(n) |
func flatten(root *Node) *Node {
if root == nil {
return nil
}
res := &Node{}
cur := res
for root != nil {
cur.Next = root
root.Prev = cur
cur = cur.Next
root = root.Next
if cur.Child != nil {
ch := flatten(cur.Child)
cur.Child = nil
cur.Next = ch
ch.Prev = cur
for cur.Next != nil {
cur = cur.Next
}
}
}
res.Next.Prev = nil
return res.Next
}
# 2
var arr []*Node
func flatten(root *Node) *Node {
arr = make([]*Node, 0)
dfs(root)
for i := 0; i < len(arr); i++ {
if i+1 < len(arr) {
arr[i].Next = arr[i+1]
}
if i > 0 {
arr[i].Prev = arr[i-1]
}
arr[i].Child = nil
}
return root
}
func dfs(root *Node) {
if root == nil {
return
}
arr = append(arr, root)
dfs(root.Child)
dfs(root.Next)
}
# 3
func flatten(root *Node) *Node {
cur := root
stack := make([]*Node, 0)
for cur != nil {
if cur.Child != nil {
if cur.Next != nil {
stack = append(stack, cur.Next)
}
cur.Child.Prev = cur
cur.Next = cur.Child
cur.Child = nil
continue
}
if cur.Next != nil {
cur.Child = nil
cur = cur.Next
continue
}
if len(stack) == 0 {
break
}
last := stack[len(stack)-1]
stack = stack[:len(stack)-1]
cur.Next = last
last.Prev = cur
cur = last
}
return root
}
433.最小基因变化(3)
一条基因序列由一个带有8个字符的字符串表示，其中每个字符都属于 "A", "C", "G", "T"中的任意一个。
假设我们要调查一个基因序列的变化。一次基因变化意味着这个基因序列中的一个字符发生了变化。
例如，基因序列由"AACCGGTT"变化至"AACCGGTA"即发生了一次基因变化。
与此同时，每一次基因变化的结果，都需要是一个合法的基因串，即该结果属于一个基因库。
现在给定3个参数 — start, end, bank，分别代表起始基因序列，目标基因序列及基因库，
请找出能够使起始基因序列变化为目标基因序列所需的最少变化次数。如果无法实现目标变化，请返回 -1。
注意：起始基因序列默认是合法的，但是它并不一定会出现在基因库中。
如果一个起始基因序列需要多次变化，那么它每一次变化之后的基因序列都必须是合法的。
假定起始基因序列与目标基因序列是不一样的。
示例 1：start: "AACCGGTT" end: "AACCGGTA" bank: ["AACCGGTA"]
返回值: 1
示例 2：start: "AACCGGTT" end: "AAACGGTA" bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]
返回值: 2
示例 3：start: "AAAAACCC" end: "AACCCCCC" bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]
返回值: 3
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
广度优先搜索 |
O(n) |
O(n) |
| 02 |
深度优先搜索 |
O(n) |
O(n) |
| 03 |
双向广度优先搜索 |
O(n) |
O(n) |
func minMutation(start string, end string, bank []string) int {
arr := []byte{'A', 'T', 'C', 'G'}
m := make(map[string]bool)
for i := 0; i < len(bank); i++ {
m[bank[i]] = true
}
if _, ok := m[end]; ok == false {
return -1
}
res := 0
queue := make([]string, 0)
queue = append(queue, start)
for len(queue) > 0 {
res++
length := len(queue)
for i := 0; i < length; i++ {
str := queue[i]
for j := 0; j < len(str); j++ {
for k := 0; k < len(arr); k++ {
if arr[k] != str[j] {
newStr := str[:j] + string(arr[k]) + str[j+1:]
if _, ok := m[newStr]; ok {
queue = append(queue, newStr)
delete(m, newStr)
}
if newStr == end {
return res
}
}
}
}
}
queue = queue[length:]
}
return -1
}
# 2
var res int
func minMutation(start string, end string, bank []string) int {
res = math.MaxInt32
m := make(map[string]bool)
for i := 0; i < len(bank); i++ {
m[bank[i]] = true
}
if _, ok := m[end]; ok == false {
return -1
}
dfs(start, end, 0, bank, make([]bool, len(bank)))
if res == math.MaxInt32 {
return -1
}
return res
}
func dfs(start string, end string, index int, bank []string, visited []bool) {
if start == end {
if index < res {
res = index
}
return
}
for i := 0; i < len(bank); i++ {
if visited[i] == false && judge(start, bank[i]) {
visited[i] = true
dfs(bank[i], end, index+1, bank, visited)
visited[i] = false
}
}
}
func judge(a, b string) bool {
count := 0
for i := 0; i < len(a); i++ {
if a[i] != b[i] {
count++
}
}
return count == 1
}
# 3
func minMutation(start string, end string, bank []string) int {
arr := []byte{'A', 'T', 'C', 'G'}
m := make(map[string]bool)
for i := 0; i < len(bank); i++ {
m[bank[i]] = true
}
if _, ok := m[end]; ok == false {
return -1
}
res := 0
queueA := make([]string, 0)
queueA = append(queueA, start)
queueB := make([]string, 0)
queueB = append(queueB, end)
for len(queueA) > 0 {
res++
if len(queueA) > len(queueB) {
queueA, queueB = queueB, queueA
}
length := len(queueA)
for i := 0; i < length; i++ {
str := queueA[i]
for j := 0; j < len(str); j++ {
for k := 0; k < len(arr); k++ {
if arr[k] != str[j] {
newStr := str[:j] + string(arr[k]) + str[j+1:]
if _, ok := m[newStr]; ok {
queueA = append(queueA, newStr)
delete(m, newStr)
}
for l := 0; l < len(queueB); l++ {
if newStr == queueB[l] {
return res
}
}
}
}
}
}
queueA = queueA[length:]
}
return -1
}
435.无重叠区间(4)
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:输入: [ [1,2], [2,3], [3,4], [1,3] ]输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:输入: [ [1,2], [1,2], [1,2] ]输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:输入: [ [1,2], [2,3] ] 输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
贪心 |
O(nlog(n)) |
O(1) |
| 02 |
贪心 |
O(nlog(n)) |
O(1) |
| 03 |
动态规划 |
O(n^2) |
O(n) |
| 04 |
动态规划 |
O(n^2) |
O(n) |
func eraseOverlapIntervals(intervals [][]int) int {
if len(intervals) == 0 {
return 0
}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][1] < intervals[j][1]
})
count := 1
end := intervals[0][1]
for i := 0; i < len(intervals); i++ {
node := intervals[i]
if node[0] >= end {
end = node[1]
count++
}
}
return len(intervals) - count
}
# 2
func eraseOverlapIntervals(intervals [][]int) int {
if len(intervals) == 0 {
return 0
}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][1] < intervals[j][1]
})
count := 0
end := intervals[0][1]
for i := 1; i < len(intervals); i++ {
node := intervals[i]
if node[0] >= end {
end = node[1]
} else {
if node[1] < end {
end = node[1]
}
count++
}
}
return count
}
# 3
func eraseOverlapIntervals(intervals [][]int) int {
if len(intervals) == 0 {
return 0
}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][1] < intervals[j][1]
})
dp := make([]int, len(intervals))
dp[0] = 1
res := 1
for i := 1; i < len(intervals); i++ {
count := 0
for j := i - 1; j >= 0; j-- {
if intervals[j][1] <= intervals[i][0] {
count = max(dp[j], count)
}
}
dp[i] = count + 1
res = max(res, dp[i])
}
return len(intervals) - res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 4
func eraseOverlapIntervals(intervals [][]int) int {
if len(intervals) == 0 {
return 0
}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][1] < intervals[j][1]
})
dp := make([]int, len(intervals))
dp[0] = 1
res := 1
for i := 1; i < len(intervals); i++ {
count := 0
for j := i - 1; j >= 0; j-- {
if intervals[j][1] <= intervals[i][0] {
count = max(dp[j], count)
break
}
}
dp[i] = max(dp[i-1], count+1)
res = max(res, dp[i])
}
return len(intervals) - res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
436.寻找右区间(2)
给你一个区间数组 intervals ，其中intervals[i] = [starti, endi] ，且每个starti 都 不同 。
区间 i 的 右侧区间 可以记作区间 j ，并满足 startj>= endi ，且 startj 最小化 。
返回一个由每个区间 i 的 右侧区间 的最小起始位置组成的数组。如果某个区间 i 不存在对应的 右侧区间 ，则下标 i 处的值设为 -1 。
示例 1：输入：intervals = [[1,2]] 输出：[-1]
解释：集合中只有一个区间，所以输出-1。
示例 2：输入：intervals = [[3,4],[2,3],[1,2]] 输出：[-1, 0, 1]
解释：对于 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间[3,4]具有最小的“右”起点;
对于 [1,2] ，区间[2,3]具有最小的“右”起点。
示例 3：输入：intervals = [[1,4],[2,3],[3,4]] 输出：[-1, 2, -1]
解释：对于区间 [1,4] 和 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间 [3,4] 有最小的“右”起点。
提示：1 <=intervals.length <= 2 * 104
intervals[i].length == 2
-106 <= starti <= endi <= 106
每个间隔的起点都 不相同
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序遍历 |
O(n^2) |
O(n) |
| 02 |
排序+二分排序 |
O(nlog(n)) |
O(n) |
func findRightInterval(intervals [][]int) []int {
m := make(map[int]int)
n := len(intervals)
res := make([]int, n)
for i := 0; i < n; i++ {
res[i] = -1
m[intervals[i][0]] = i
}
sort.Slice(intervals, func(i, j int) bool {
if intervals[i][0] == intervals[j][0] {
return intervals[i][1] < intervals[j][1]
}
return intervals[i][0] < intervals[j][0]
})
for i := 0; i < n; i++ {
for j := i; j < n; j++ {
if intervals[i][1] <= intervals[j][0] {
index := m[intervals[i][0]]
res[index] = m[intervals[j][0]]
break
}
}
}
return res
}
# 2
func findRightInterval(intervals [][]int) []int {
m := make(map[int]int)
n := len(intervals)
res := make([]int, n)
for i := 0; i < n; i++ {
res[i] = -1
m[intervals[i][0]] = i
}
sort.Slice(intervals, func(i, j int) bool {
if intervals[i][0] == intervals[j][0] {
return intervals[i][1] < intervals[j][1]
}
return intervals[i][0] < intervals[j][0]
})
for i := 0; i < n; i++ {
target := intervals[i][1]
index := m[intervals[i][0]]
left, right := i, n-1
for left <= right {
mid := left + (right-left)/2
if target <= intervals[mid][0] {
res[index] = m[intervals[mid][0]]
right = mid - 1
} else {
left = mid + 1
}
}
}
return res
}
438.找到字符串中所有字母异位词(2)
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。
示例 1:输入: s: "cbaebabacd" p: "abc"输出: [0, 6]
解释:起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
示例 2:输入: s: "abab" p: "ab"输出: [0, 1, 2]
解释:起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
滑动窗口 |
O(n) |
O(1) |
| 02 |
滑动窗口 |
O(n) |
O(1) |
func findAnagrams(s string, p string) []int {
res := make([]int, 0)
if len(p) > len(s) {
return res
}
arr1, arr2 := [26]int{}, [26]int{}
for i := 0; i < len(p); i++ {
arr1[p[i]-'a']++
arr2[s[i]-'a']++
}
for i := 0; i < len(s)-len(p); i++ {
if arr1 == arr2 {
res = append(res, i)
}
arr2[s[i]-'a']--
arr2[s[i+len(p)]-'a']++
}
if arr1 == arr2 {
res = append(res, len(s)-len(p))
}
return res
}
# 2
func findAnagrams(s string, p string) []int {
res := make([]int, 0)
if len(p) > len(s) {
return res
}
m1, m2 := make(map[byte]int), make(map[byte]int)
for i := 0; i < len(p); i++ {
m1[p[i]-'a']++
m2[s[i]-'a']++
}
for i := 0; i < len(s)-len(p); i++ {
if compare(m1, m2) {
res = append(res, i)
}
m2[s[i]-'a']--
if m2[s[i]-'a'] == 0 {
delete(m2, s[i]-'a')
}
m2[s[i+len(p)]-'a']++
}
if compare(m1, m2) {
res = append(res, len(s)-len(p))
}
return res
}
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
}
442.数组中重复的数据(5)
给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。
找到所有出现两次的元素。
你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？
示例：输入: [4,3,2,7,8,2,3,1] 输出:[2,3]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n) |
O(n) |
| 02 |
置反 |
O(n) |
O(1) |
| 03 |
置换 |
O(n) |
O(1) |
| 04 |
累加 |
O(n) |
O(1) |
| 05 |
排序 |
O(nlog(n)) |
O(1) |
func findDuplicates(nums []int) []int {
res := make([]int, 0)
m := make(map[int]int)
for i := 0; i < len(nums); i++ {
m[nums[i]]++
}
for k, v := range m {
if v == 2 {
res = append(res, k)
}
}
return res
}
# 2
func findDuplicates(nums []int) []int {
res := make([]int, 0)
for i := 0; i < len(nums); i++ {
index := abs(nums[i]) - 1
if nums[index] < 0 {
res = append(res, abs(nums[i]))
} else {
nums[index] = -nums[index]
}
}
return res
}
func abs(a int) int {
if a >= 0 {
return a
}
return -a
}
# 3
func findDuplicates(nums []int) []int {
res := make([]int, 0)
for i := 0; i < len(nums); i++ {
for nums[nums[i]-1] != nums[i] {
nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
}
}
for i := 0; i < len(nums); i++ {
if nums[i]-1 != i {
res = append(res, nums[i])
}
}
return res
}
# 4
func findDuplicates(nums []int) []int {
res := make([]int, 0)
n := len(nums)
for i := 0; i < n; i++ {
index := nums[i]%(n+1) - 1
nums[index] = nums[index] + (n + 1)
}
for i := 0; i < n; i++ {
if nums[i]/(n+1) == 2 {
res = append(res, i+1)
}
}
return res
}
# 5
func findDuplicates(nums []int) []int {
if len(nums) == 0 {
return nil
}
sort.Ints(nums)
res := make([]int, 0)
prev := nums[0]
count := 1
for i := 1; i < len(nums); i++ {
if prev == nums[i] {
count++
} else {
if count == 2 {
res = append(res, nums[i-1])
}
prev = nums[i]
count = 1
}
}
if count == 2 {
res = append(res, nums[len(nums)-1])
}
return res
}
445.两数相加II(3)
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。
它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶：如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例：输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 8 -> 0 -> 7
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
反转遍历 |
O(n) |
O(n) |
| 02 |
栈辅助 |
O(n) |
O(n) |
| 03 |
递归 |
O(n) |
O(n) |
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
l1 = reverse(l1)
l2 = reverse(l2)
res := &ListNode{}
cur := res
carry := 0
for l1 != nil || l2 != nil || carry > 0 {
sum := carry
if l1 != nil {
sum += l1.Val
l1 = l1.Next
}
if l2 != nil {
sum += l2.Val
l2 = l2.Next
}
carry = sum / 10
cur.Next = &ListNode{Val: sum % 10}
cur = cur.Next
}
return reverse(res.Next)
}
func reverse(head *ListNode) *ListNode {
var result *ListNode
var temp *ListNode
for head != nil {
temp = head.Next
head.Next = result
result = head
head = temp
}
return result
}
# 2
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
stack1 := make([]int, 0)
stack2 := make([]int, 0)
for l1 != nil {
stack1 = append(stack1, l1.Val)
l1 = l1.Next
}
for l2 != nil {
stack2 = append(stack2, l2.Val)
l2 = l2.Next
}
var res *ListNode
carry := 0
for len(stack1) > 0 || len(stack2) > 0 || carry > 0 {
if len(stack1) > 0 {
carry = carry + stack1[len(stack1)-1]
stack1 = stack1[:len(stack1)-1]
}
if len(stack2) > 0 {
carry = carry + stack2[len(stack2)-1]
stack2 = stack2[:len(stack2)-1]
}
temp := &ListNode{
Val: carry % 10,
Next: res,
}
carry = carry / 10
res = temp
}
return res
}
# 3
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
a, b := l1, l2
length1, length2 := 0, 0
for a != nil {
length1++
a = a.Next
}
for b != nil {
length2++
b = b.Next
}
res, carry := add(l1, l2, length1, length2)
if carry > 0 {
return &ListNode{Val: carry, Next: res}
}
return res
}
func add(l1, l2 *ListNode, length1, length2 int) (res *ListNode, carry int) {
if l1 != nil && l2 != nil {
if l1.Next == nil && l2.Next == nil {
val := l1.Val + l2.Val
carry = val / 10
res = &ListNode{Val: val % 10, Next: nil}
return
}
}
a := &ListNode{}
var b, n int
if length1 > length2 {
a, b = add(l1.Next, l2, length1-1, length2)
n = l1.Val + b
} else if length1 < length2 {
a, b = add(l1, l2.Next, length1, length2-1)
n = l2.Val + b
} else {
a, b = add(l1.Next, l2.Next, length1-1, length2-1)
n = l1.Val + l2.Val + b
}
res = &ListNode{Val: n % 10, Next: a}
carry = n / 10
return
}
449.序列化和反序列化二叉搜索树(2)
序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，
以便稍后在同一个或另一个计算机环境中重建。
设计一个算法来序列化和反序列化二叉搜索树。 对序列化/反序列化算法的工作方式没有限制。
您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
编码的字符串应尽可能紧凑。
注意：不要使用类成员/全局/静态变量来存储状态。 你的序列化和反序列化算法应该是无状态的。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(n) |
| 02 |
迭代 |
O(n) |
O(n) |
type Codec struct {
res []string
}
func Constructor() Codec {
return Codec{}
}
func (this *Codec) serialize(root *TreeNode) string {
if root == nil {
return "#"
}
return strconv.Itoa(root.Val) + "," + this.serialize(root.Left) + "," + this.serialize(root.Right)
}
func (this *Codec) deserialize(data string) *TreeNode {
this.res = strings.Split(data, ",")
return this.dfsDeserialize()
}
func (this *Codec) dfsDeserialize() *TreeNode {
node := this.res[0]
this.res = this.res[1:]
if node == "#" {
return nil
}
value, _ := strconv.Atoi(node)
return &TreeNode{
Val: value,
Left: this.dfsDeserialize(),
Right: this.dfsDeserialize(),
}
}
# 2
type Codec struct {
res []string
}
func Constructor() Codec {
return Codec{}
}
func (this *Codec) serialize(root *TreeNode) string {
if root == nil {
return ""
}
res := make([]string, 0)
queue := make([]*TreeNode, 0)
queue = append(queue, root)
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
if node != nil {
res = append(res, strconv.Itoa(node.Val))
queue = append(queue, node.Left, node.Right)
} else {
res = append(res, "#")
}
}
return strings.Join(res, ",")
}
func (this *Codec) deserialize(data string) *TreeNode {
if len(data) == 0 || data == "" {
return nil
}
res := strings.Split(data, ",")
root := &TreeNode{}
root.Val, _ = strconv.Atoi(res[0])
res = res[1:]
queue := make([]*TreeNode, 0)
queue = append(queue, root)
for len(queue) > 0 {
if res[0] != "#" {
left, _ := strconv.Atoi(res[0])
queue[0].Left = &TreeNode{Val: left}
queue = append(queue, queue[0].Left)
}
if res[1] != "#" {
right, _ := strconv.Atoi(res[1])
queue[0].Right = &TreeNode{Val: right}
queue = append(queue, queue[0].Right)
}
queue = queue[1:]
res = res[2:]
}
return root
}
450.删除二叉搜索树中的节点(2)
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，
并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点；
如果找到了，删除它。
说明： 要求算法时间复杂度为 O(h)，h 为树的高度。
示例:root = [5,3,6,2,4,null,7] key = 3
5
/ \
3 6
/ \ \
2 4 7
给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
5
/ \
4 6
/ \
2 7
另一个正确答案是 [5,2,6,null,4,null,7]。
5
/ \
2 6
\ \
4 7
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(log(n)) |
O(log(n)) |
| 02 |
递归 |
O(log(n)) |
O(log(n)) |
func deleteNode(root *TreeNode, key int) *TreeNode {
if root == nil {
return nil
}
if key < root.Val {
root.Left = deleteNode(root.Left, key)
} else if key > root.Val {
root.Right = deleteNode(root.Right, key)
} else {
if root.Left == nil {
return root.Right
}
if root.Right == nil {
return root.Left
}
minNode := root.Right
for minNode.Left != nil {
minNode = minNode.Left
}
minNode.Left = root.Left
root = root.Right
}
return root
}
# 2
func deleteNode(root *TreeNode, key int) *TreeNode {
if root == nil {
return nil
}
if key < root.Val {
root.Left = deleteNode(root.Left, key)
} else if key > root.Val {
root.Right = deleteNode(root.Right, key)
} else {
if root.Left == nil {
return root.Right
}
if root.Right == nil {
return root.Left
}
maxNode := root.Left
for maxNode.Right != nil {
maxNode = maxNode.Right
}
maxNode.Right = root.Right
root = root.Left
}
return root
}
451.根据字符出现频率排序(2)
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
示例 1:输入:"tree"输出:"eert"
解释:'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
示例 2:输入:"cccaaa"输出:"cccaaa"
解释:'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。
示例 3:输入:"Aabb"输出:"bbAa"
解释:此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(nlog(n)) |
O(n) |
| 02 |
堆辅助 |
O(nlog(n)) |
O(n) |
func frequencySort(s string) string {
m := make(map[int]int)
for i := 0; i < len(s); i++ {
m[int(s[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 := ""
for i := range arr {
for j := 0; j < arr[i][1]; j++ {
res = res + string(arr[i][0])
}
}
return res
}
# 2
func frequencySort(s string) string {
m := make(map[byte]string)
for i := 0; i < len(s); i++ {
m[s[i]] = m[s[i]] + string(s[i])
}
var h HeapString
heap.Init(&h)
for _, v := range m {
heap.Push(&h, v)
}
res := ""
for h.Len() > 0 {
str := heap.Pop(&h).(string)
res = res + str
}
return res
}
type HeapString []string
func (h HeapString) Len() int {
return len(h)
}
func (h HeapString) Less(i int, j int) bool {
return len(h[i]) >= len(h[j])
}
func (h HeapString) Swap(i int, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *HeapString) Push(x interface{}) {
*h = append(*h, x.(string))
}
func (h *HeapString) Pop() interface{} {
n := len(*h)
val := (*h)[n-1]
*h = (*h)[:n-1]
return val
}
452.用最少数量的箭引爆气球(1)
在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。
由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。
在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend，
且满足 xstart≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。
弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。
示例 1：输入：points = [[10,16],[2,8],[1,6],[7,12]] 输出：2
解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球
示例 2：输入：points = [[1,2],[3,4],[5,6],[7,8]] 输出：4
示例 3：输入：points = [[1,2],[2,3],[3,4],[4,5]] 输出：2
示例 4：输入：points = [[1,2]] 输出：1
示例 5：输入：points = [[2,3],[2,3]] 输出：1
提示：0 <= points.length <= 104
points[i].length == 2
-231 <= xstart <xend <= 231 - 1
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序 |
O(nlog(n)) |
O(1) |
func findMinArrowShots(points [][]int) int {
if len(points) == 0 {
return 0
}
sort.Slice(points, func(i, j int) bool {
return points[i][1] < points[j][1]
})
right := points[0][1]
res := 1
for i := 0; i < len(points); i++ {
if points[i][0] > right {
right = points[i][1]
res++
}
}
return res
}
454.四数相加II(2)
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，
使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。
所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。
例如:输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
输出:2
解释:两个元组如下:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n^2) |
O(n^2) |
| 02 |
哈希辅助 |
O(n^2) |
O(n^2) |
func fourSumCount(A []int, B []int, C []int, D []int) int {
res := 0
m := make(map[int]int)
for _, a := range A {
for _, b := range B {
m[a+b]++
}
}
for _, c := range C {
for _, d := range D {
res = res + m[0-c-d]
}
}
return res
}
# 2
func fourSumCount(A []int, B []int, C []int, D []int) int {
res := 0
mA := make(map[int]int)
mB := make(map[int]int)
for _, a := range A {
for _, b := range B {
mA[a+b]++
}
}
for _, c := range C {
for _, d := range D {
mB[c+d]++
}
}
for k, v := range mA {
res = res + v*mB[-k]
}
return res
}
456.132模式(3)
给定一个整数序列：a1, a2, ..., an，一个132模式的子序列ai, aj, ak被定义为：
当 i < j < k 时，ai < ak < aj。
设计一个算法，当给定有n 个数字的序列时，验证这个序列中是否含有132模式的子序列。
注意：n 的值小于15000。
示例1:输入: [1, 2, 3, 4] 输出: False
解释: 序列中不存在132模式的子序列。
示例 2:输入: [3, 1, 4, 2]输出: True
解释: 序列中有 1 个132模式的子序列： [1, 4, 2].
示例 3:输入: [-1, 3, 2, 0] 输出: True
解释: 序列中有 3 个132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0].
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
栈辅助 |
O(n) |
O(n) |
| 02 |
遍历 |
O(n^2) |
O(n) |
| 03 |
栈辅助 |
O(n) |
O(n) |
func find132pattern(nums []int) bool {
if len(nums) < 3 {
return false
}
minArr := make([]int, len(nums))
minArr[0] = nums[0]
for i := 1; i < len(nums); i++ {
minArr[i] = min(nums[i], minArr[i-1])
}
stack := make([]int, 0)
for j := len(nums) - 1; j >= 0; j-- {
if nums[j] > minArr[j] {
for len(stack) > 0 && stack[len(stack)-1] <= minArr[j] {
stack = stack[:len(stack)-1]
}
if len(stack) > 0 && stack[len(stack)-1] < nums[j] {
return true
}
stack = append(stack, nums[j])
}
}
return false
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
func find132pattern(nums []int) bool {
if len(nums) < 3 {
return false
}
minArr := make([]int, len(nums))
minArr[0] = nums[0]
for i := 1; i < len(nums); i++ {
minArr[i] = min(nums[i], minArr[i-1])
}
for j := len(nums) - 2; j >= 0; j-- {
if nums[j] != minArr[j] {
for k := j + 1; k < len(nums); k++ {
if nums[k] > minArr[j] && nums[k] < nums[j] {
return true
}
}
}
}
return false
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 3
func find132pattern(nums []int) bool {
if len(nums) < 3 {
return false
}
stack := make([]int, 0)
maxValue := math.MinInt32
for i := len(nums) - 1; i >= 0; i-- {
if nums[i] < maxValue {
return true
}
for len(stack) > 0 && nums[i] > stack[len(stack)-1] {
last := len(stack) - 1
maxValue = max(maxValue, stack[last])
stack = stack[:last]
}
stack = append(stack, nums[i])
}
return false
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
457.环形数组循环(3)
给定一个含有正整数和负整数的环形数组 nums。 如果某个索引中的数 k 为正数，则向前移动 k 个索引。
相反，如果是负数 (-k)，则向后移动 k 个索引。
因为数组是环形的，所以可以假设最后一个元素的下一个元素是第一个元素，而第一个元素的前一个元素是最后一个元素。
确定 nums 中是否存在循环（或周期）。循环必须在相同的索引处开始和结束并且循环长度 > 1。
此外，一个循环中的所有运动都必须沿着同一方向进行。换句话说，一个循环中不能同时包括向前的运动和向后的运动。
示例 1：输入：[2,-1,1,2,2] 输出：true
解释：存在循环，按索引 0 -> 2 -> 3 -> 0 。循环长度为 3 。
示例 2：输入：[-1,2] 输出：false
解释：按索引 1 -> 1 -> 1 ... 的运动无法构成循环，因为循环的长度为 1 。根据定义，循环的长度必须大于 1 。
示例 3:输入：[-2,1,-1,-2,-2] 输出：false
解释：按索引 1 -> 2 -> 1 -> ... 的运动无法构成循环，因为按索引 1 -> 2 的运动是向前的运动，
而按索引 2 -> 1 的运动是向后的运动。一个循环中的所有运动都必须沿着同一方向进行。
提示：-1000 ≤ nums[i] ≤ 1000
nums[i] ≠ 0
0 ≤ nums.length ≤ 5000
进阶：你能写出时间时间复杂度为 O(n) 和额外空间复杂度为 O(1) 的算法吗？
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
快慢指针 |
O(n) |
O(1) |
| 02 |
快慢指针 |
O(n^2) |
O(1) |
| 03 |
模拟 |
O(n^2) |
O(1) |
func circularArrayLoop(nums []int) bool {
n := len(nums)
for i := 0; i < n; i++ {
if nums[i] == 0 {
continue
}
slow, fast := i, getNext(nums, n, i)
for nums[slow]*nums[fast] > 0 && nums[slow]*nums[getNext(nums, n, fast)] > 0 {
if slow == fast {
if slow == getNext(nums, n, slow) {
break
}
return true
}
slow = getNext(nums, n, slow)
fast = getNext(nums, n, getNext(nums, n, fast))
}
temp := i
for nums[temp]*nums[getNext(nums, n, temp)] > 0 {
nums[temp] = 0
temp = getNext(nums, n, temp)
}
}
return false
}
func getNext(nums []int, n, cur int) int {
return ((cur+nums[cur])%n + n) % n
}
# 2
func circularArrayLoop(nums []int) bool {
n := len(nums)
for i := 0; i < n; i++ {
slow, fast := i, getNext(nums, n, i)
for nums[slow]*nums[fast] > 0 && nums[slow]*nums[getNext(nums, n, fast)] > 0 {
if slow == fast {
if slow == getNext(nums, n, slow) {
break
}
return true
}
slow = getNext(nums, n, slow)
fast = getNext(nums, n, getNext(nums, n, fast))
}
}
return false
}
func getNext(nums []int, n, cur int) int {
return ((cur+nums[cur])%n + n) % n
}
# 3
func circularArrayLoop(nums []int) bool {
n := len(nums)
for i := 0; i < n; i++ {
if judge(nums, n, i) == true {
return true
}
}
return false
}
func judge(nums []int, n, cur int) bool {
start := cur
dir := 1
if nums[cur] < 0 {
dir = -1
}
count := 1
for {
if count > n {
return false
}
next := ((cur+nums[cur])%n + n) % n
if (dir > 0 && nums[next] < 0) || (dir < 0 && nums[next] > 0) {
return false
}
if next == start {
return count > 1
}
count++
cur = next
}
}
462.最少移动次数使数组元素相等II(2)
给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。
您可以假设数组的长度最多为10000。
例如:输入: [1,2,3]输出: 2
说明：只有两个动作是必要的（记得每一步仅可使其中一个元素加1或减1）：
[1,2,3] => [2,2,3] => [2,2,2]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(nlog(n)) |
O(1) |
| 02 |
遍历 |
O(nlog(n)) |
O(1) |
func minMoves2(nums []int) int {
sort.Ints(nums)
target := nums[len(nums)/2]
res := 0
for i := 0; i < len(nums); i++ {
res = res + abs(target-nums[i])
}
return res
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
# 2
func minMoves2(nums []int) int {
sort.Ints(nums)
res := 0
left, right := 0, len(nums)-1
for left < right {
res = res + nums[right] - nums[left]
left++
right--
}
return res
}
464.我能赢吗(3)
在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，
先使得累计整数和达到或超过 100 的玩家，即为胜者。
如果我们将游戏规则改为 “玩家不能重复使用整数” 呢？
例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。
给定一个整数maxChoosableInteger（整数池中可选择的最大数）和另一个整数desiredTotal（累计和），
判断先出手的玩家是否能稳赢（假设两位玩家游戏时都表现最佳）？
你可以假设maxChoosableInteger不会大于 20，desiredTotal不会大于 300。
示例：输入：maxChoosableInteger = 10 desiredTotal = 11输出： false
解释：无论第一个玩家选择哪个整数，他都会失败。
第一个玩家可以选择从 1 到 10 的整数。
如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(2^n) |
O(2^n) |
| 02 |
递归 |
O(2^n) |
O(2^n) |
| 03 |
动态规划-状态压缩 |
O(n*2^n) |
O(2^n) |
var m []bool
func canIWin(maxChoosableInteger int, desiredTotal int) bool {
a := maxChoosableInteger
if a*(a+1)/2 < desiredTotal {
return false
}
m = make([]bool, 1<<a)
return dfs(a, desiredTotal, 0)
}
func dfs(a, b int, status int) bool {
if m[status] == true {
return true
}
for i := 1; i <= a; i++ {
cur := 1 << (i - 1)
if cur&status > 0 {
continue
}
if b <= i {
m[status] = true
return true
}
next := status | cur
if dfs(a, b-i, next) == false {
m[status] = true
return true
}
}
m[status] = false
return false
}
# 2
var m map[int]bool
func canIWin(maxChoosableInteger int, desiredTotal int) bool {
a := maxChoosableInteger
if a*(a+1)/2 < desiredTotal {
return false
}
m = make(map[int]bool)
return dfs(a, desiredTotal, 0)
}
func dfs(a, b int, status int) bool {
if v, ok := m[status]; ok {
return v
}
for i := 1; i <= a; i++ {
cur := 1 << (i - 1)
next := status | cur
if cur&status == 0 && (b <= i || dfs(a, b-i, next) == false) {
m[status] = true
return true
}
}
m[status] = false
return false
}
# 3
func canIWin(maxChoosableInteger int, desiredTotal int) bool {
a, b := maxChoosableInteger, desiredTotal
if a*(a+1)/2 < b {
return false
}
total := 1 << a
dp := make([]bool, total)
for i := total - 1; i >= 0; i-- {
sum := 0
for k := 0; k < a; k++ {
if i&(1<<k) > 0 {
sum = sum + (k + 1)
}
}
for k := 0; k < a; k++ {
if i&(1<<k) > 0 {
continue
}
prev := i | (1 << k)
if k+1 >= desiredTotal-sum || dp[prev] == false {
dp[i] = true
}
}
}
return dp[0]
}
467.环绕字符串中唯一的子字符串(1)
把字符串 s 看作是“abcdefghijklmnopqrstuvwxyz”的无限环绕字符串，
所以s 看起来是这样的："...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
现在我们有了另一个字符串 p 。
你需要的是找出 s 中有多少个唯一的 p 的非空子串，
尤其是当你的输入是字符串 p ，你需要输出字符串s 中 p 的不同的非空子串的数目。
注意: p仅由小写的英文字母组成，p 的大小可能超过 10000。
示例1:输入: "a" 输出: 1
解释: 字符串 S 中只有一个"a"子字符。
示例 2:输入: "cac" 输出: 2
解释: 字符串 S 中的字符串“cac”只有两个子串“a”、“c”。.
示例 3:输入: "zab" 输出: 6
解释: 在字符串 S 中有六个子串“z”、“a”、“b”、“za”、“ab”、“zab”。.
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n) |
O(n) |
func findSubstringInWraproundString(p string) int {
dp := [26]int{}
count := 0
for i := 0; i < len(p); i++ {
value := int(p[i] - 'a')
if i > 0 && (value-int(p[i-1]-'a')-1)%26 == 0 {
count++
} else {
count = 1
}
dp[value] = max(dp[value], count)
}
res := 0
for i := 0; i < len(dp); i++ {
res = res + dp[i]
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
468.验证IP地址(1)
编写一个函数来验证输入的字符串是否是有效的 IPv4 或IPv6 地址。
如果是有效的 IPv4 地址，返回 "IPv4" ；
如果是有效的 IPv6 地址，返回 "IPv6" ；
如果不是上述类型的 IP 地址，返回 "Neither" 。
IPv4地址由十进制数和点来表示，每个地址包含 4 个十进制数，其范围为0 -255，用(".")分割。
比如，172.16.254.1；
同时，IPv4 地址内的数不会以 0 开头。比如，地址172.16.254.01 是不合法的。
IPv6地址由 8 组 16 进制的数字来表示，每组表示16 比特。这些组数字通过 (":")分割。
比如,2001:0db8:85a3:0000:0000:8a2e:0370:7334 是一个有效的地址。
而且，我们可以加入一些以 0 开头的数字，字母可以使用大写，也可以是小写。
所以，2001:db8:85a3:0:0:8A2E:0370:7334 也是一个有效的 IPv6 address地址
(即，忽略 0 开头，忽略大小写)。
然而，我们不能因为某个组的值为 0，而使用一个空的组，以至于出现 (::) 的情况。
比如，2001:0db8:85a3::8A2E:0370:7334 是无效的 IPv6 地址。
同时，在 IPv6 地址中，多余的 0 也是不被允许的。
比如，02001:0db8:85a3:0000:0000:8a2e:0370:7334 是无效的。
示例 1：输入：IP = "172.16.254.1" 输出："IPv4"
解释：有效的 IPv4 地址，返回 "IPv4"
示例 2：输入：IP = "2001:0db8:85a3:0:0:8A2E:0370:7334" 输出："IPv6"
解释：有效的 IPv6 地址，返回 "IPv6"
示例 3：输入：IP = "256.256.256.256" 输出："Neither"
解释：既不是 IPv4 地址，又不是 IPv6 地址
示例 4：输入：IP = "2001:0db8:85a3:0:0:8A2E:0370:7334:" 输出："Neither"
示例 5：输入：IP = "1e1.4.5.6"输出："Neither"
提示：IP 仅由英文字母，数字，字符 '.' 和 ':' 组成。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
var defaultRes string = "Neither"
func validIPAddress(IP string) string {
if strings.Contains(IP, ":") {
return checkIPv6(IP)
}
return checkIPv4(IP)
}
func checkIPv4(ip string) string {
arr := strings.Split(ip, ".")
if len(arr) != 4 {
return defaultRes
}
for i := 0; i < len(arr); i++ {
num, err := strconv.Atoi(arr[i])
if err != nil || num > 255 || num < 0 {
return defaultRes
}
if len(arr[i]) > 1 && arr[i][0] == '0' || (i == 0 && num == 0) {
return defaultRes
}
}
return "IPv4"
}
func checkIPv6(ip string) string {
arr := strings.Split(ip, ":")
if len(arr) != 8 {
return defaultRes
}
for i := 0; i < len(arr); i++ {
if arr[i] == "" || len(arr[i]) > 4 {
return defaultRes
}
for j := 0; j < len(arr[i]); j++ {
if (arr[i][j] > 'F' && arr[i][j] < 'a') ||
(arr[i][j] > 'f' && arr[i][j] <= 'z') {
return defaultRes
}
}
}
return "IPv6"
}
470.用Rand7()实现 Rand10()(2)
已有方法rand7可生成 1 到 7 范围内的均匀随机整数，
试写一个方法rand10生成 1 到 10 范围内的均匀随机整数。
不要使用系统的Math.random()方法。
示例 1:输入: 1 输出: [7]
示例 2:输入: 2 输出: [8,4]
示例 3:输入: 3 输出: [8,1,10]
提示:rand7已定义。
传入参数:n表示rand10的调用次数。
进阶:rand7()调用次数的期望值是多少?
你能否尽量少调用 rand7() ?
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
循环 |
O(1) |
O(1) |
| 02 |
循环 |
O(1) |
O(1) |
func rand10() int {
for {
a := rand7()
b := rand7()
target := a + (b-1)*7
if target <= 40 {
return target%10 + 1
}
}
}
# 2
func rand10() int {
for {
a := rand7()
b := rand7()
target := a + (b-1)*7
if target <= 40 {
return target%10 + 1
}
a = rand7()
b = target - 40
target = a + (b-1)*7
if target <= 60 {
return target%10 + 1
}
a = rand7()
b = target - 60
target = a + (b-1)*7
if target <= 20 {
return target%10 + 1
}
}
}
473.火柴拼正方形(2)
还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，
请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。
输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。
示例1:输入: [1,1,2,2,2] 输出: true
解释: 能拼成一个边长为2的正方形，每边两根火柴。
示例2:输入: [3,3,3,3,4] 输出: false
解释: 不能用所有火柴拼成一个正方形。
注意:给定的火柴长度和在0到10^9之间。
火柴数组的长度不超过15。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
深度优先搜索 |
O(4^n) |
O(n) |
| 02 |
深度优先搜索 |
O(2^n) |
O(n) |
func makesquare(nums []int) bool {
n := len(nums)
if nums == nil || n < 4 {
return false
}
sum := 0
for i := 0; i < len(nums); i++ {
sum = sum + nums[i]
}
if sum%4 != 0 {
return false
}
sort.Slice(nums, func(i, j int) bool {
return nums[i] > nums[j]
})
res := make([]int, 4)
return dfs(nums, res, sum/4, 0)
}
func dfs(nums []int, res []int, target int, level int) bool {
if len(nums) == level {
for i := 0; i < len(res); i++ {
if res[i] != target {
return false
}
}
return true
}
for i := 0; i < len(res); i++ {
if nums[level]+res[i] > target {
continue
}
res[i] = res[i] + nums[level]
if dfs(nums, res, target, level+1) == true {
return true
}
res[i] = res[i] - nums[level]
}
return false
}
# 2
func makesquare(nums []int) bool {
n := len(nums)
if nums == nil || n < 4 {
return false
}
sum := 0
for i := 0; i < len(nums); i++ {
sum = sum + nums[i]
}
if sum%4 != 0 {
return false
}
sort.Slice(nums, func(i, j int) bool {
return nums[i] > nums[j]
})
visited := make([]bool, len(nums))
for i := 0; i < 4; i++ {
if dfs(nums, sum/4, 0, 0, visited) == false {
return false
}
}
return true
}
func dfs(nums []int, target int, sum int, level int, visited []bool) bool {
if sum == target {
return true
}
if len(nums) == level {
}
for i := level; i < len(nums); i++ {
if visited[i] == false && sum <= target {
visited[i] = true
if dfs(nums, target, sum+nums[i], level+1, visited) {
return true
}
visited[i] = false
}
}
return false
}
474.一和零(2)
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3 输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。
{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
示例 2：输入：strs = ["10", "0", "1"], m = 1, n = 1 输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
提示：1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i]仅由'0' 和'1' 组成
1 <= m, n <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^3) |
O(n^2) |
| 02 |
动态规划 |
O(n^3) |
O(n^3) |
func findMaxForm(strs []string, m int, n int) int {
dp := make([][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, n+1)
}
for i := 0; i < len(strs); i++ {
a, b := getCount(strs[i])
for j := m; j >= a; j-- {
for k := n; k >= b; k-- {
dp[j][k] = max(dp[j][k], dp[j-a][k-b]+1)
}
}
}
return dp[m][n]
}
func getCount(str string) (a, b int) {
a, b = 0, 0
for i := 0; i < len(str); i++ {
if str[i] == '0' {
a++
} else {
b++
}
}
return a, b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func findMaxForm(strs []string, m int, n int) int {
dp := make([][][]int, len(strs)+1)
for i := 0; i <= len(strs); i++ {
dp[i] = make([][]int, m+1)
for j := 0; j <= m; j++ {
dp[i][j] = make([]int, n+1)
}
}
for i := 1; i <= len(strs); i++ {
a, b := getCount(strs[i-1])
for j := 0; j <= m; j++ {
for k := 0; k <= n; k++ {
dp[i][j][k] = dp[i-1][j][k]
if a <= j && b <= k {
dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-a][k-b]+1)
}
}
}
}
return dp[len(strs)][m][n]
}
func getCount(str string) (a, b int) {
a, b = 0, 0
for i := 0; i < len(str); i++ {
if str[i] == '0' {
a++
} else {
b++
}
}
return a, b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
477.汉明距离总和(1)
两个整数的汉明距离 指的是这两个数字的二进制数对应位不同的数量。
计算一个数组中，任意两个数之间汉明距离的总和。
示例:输入: 4, 14, 2 输出: 6
解释: 在二进制表示中，4表示为0100，14表示为1110，2表示为0010。
（这样表示是为了体现后四位之间关系）
所以答案为：
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
注意:数组中元素的范围为从0到10^9。
数组的长度不超过10^4。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
func totalHammingDistance(nums []int) int {
res := 0
for i := 0; i < 32; i++ {
total := 0
for j := 0; j < len(nums); j++ {
total = total + (nums[j]>>i)&1
}
res = res + total*(len(nums)-total)
}
return res
}
478.在圆内随机生成点(1)
给定圆的半径和圆心的 x、y 坐标，写一个在圆中产生均匀随机点的函数randPoint。
说明:输入值和输出值都将是浮点数。
圆的半径和圆心的 x、y 坐标将作为参数传递给类的构造函数。
圆周上的点也认为是在圆中。
randPoint返回一个包含随机点的x坐标和y坐标的大小为2的数组。
示例 1：输入: ["Solution","randPoint","randPoint","randPoint"] [[1,0,0],[],[],[]]
输出: [null,[-0.72939,-0.65505],[-0.78502,-0.28626],[-0.83119,-0.19803]]
示例 2：输入: ["Solution","randPoint","randPoint","randPoint"] [[10,5,-7.5],[],[],[]]
输出: [null,[11.52438,-8.33273],[2.46992,-16.21705],[11.13430,-12.42337]]
输入语法说明：输入是两个列表：调用成员函数名和调用的参数。Solution的构造函数有三个参数，
圆的半径、圆心的 x 坐标、圆心的 y 坐标。randPoint没有参数。
输入参数是一个列表，即使参数为空，也会输入一个 [] 空列表。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
循环 |
O(1) |
O(1) |
type Solution struct {
x float64
y float64
radius float64
}
func Constructor(radius float64, x_center float64, y_center float64) Solution {
return Solution{
x: x_center,
y: y_center,
radius: radius,
}
}
func (this *Solution) RandPoint() []float64 {
for {
a := this.x - this.radius + 2*this.radius*rand.Float64()
b := this.y - this.radius + 2*this.radius*rand.Float64()
if (a-this.x)*(a-this.x)+(b-this.y)*(b-this.y) < this.radius*this.radius {
return []float64{a, b}
}
}
}
481.神奇字符串(2)
神奇的字符串S只包含 '1' 和 '2'，并遵守以下规则：
字符串 S 是神奇的，因为串联字符 '1' 和 '2' 的连续出现次数会生成字符串 S 本身。
字符串S的前几个元素如下：S = “1221121221221121122 ......”
如果我们将S 中连续的 1 和 2 进行分组，它将变成：
1 22 11 2 1 22 1 22 11 2 11 22 ......
并且每个组中 '1' 或 '2' 的出现次数分别是：
1 2 2 1 1 2 1 2 2 1 2 2 ......
你可以看到上面的出现次数就是 S 本身。
给定一个整数 N 作为输入，返回神奇字符串 S中前 N 个数字中的 '1' 的数目。
注意：N 不会超过 100,000。
示例：输入：6 输出：3
解释：神奇字符串 S 的前 6 个元素是 “12211”，它包含三个 1，因此返回 3。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
| 02 |
遍历 |
O(n) |
O(n) |
func magicalString(n int) int {
if n == 0 {
return 0
}
if n <= 3 {
return 1
}
str := []byte("122")
res := 1
index := 2
for i := 2; i < n; i++ {
if str[i] == '2' {
if str[index] == '2' {
str = append(str, []byte{'1', '1'}...)
} else {
str = append(str, []byte{'2', '2'}...)
}
index = index + 2
} else {
res++
if str[index] == '2' {
str = append(str, '1')
} else {
str = append(str, '2')
}
index = index + 1
}
}
return res
}
# 2
func magicalString(n int) int {
if n == 0 {
return 0
}
if n <= 3 {
return 1
}
str := []byte("122")
flag := true
for i := 2; i < n; i++ {
count := str[i] - '0'
if flag == true {
for count > 0 {
str = append(str, '1')
count--
}
flag = false
} else {
for count > 0 {
str = append(str, '2')
count--
}
flag = true
}
}
res := 0
for i := 0; i < n; i++ {
if str[i] == '1' {
res++
}
}
return res
}
486.预测赢家(3)
给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，
随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。
每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。
最终获得分数总和最多的玩家获胜。
给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。
示例 1：输入：[1, 5, 2] 输出：False
解释：一开始，玩家1可以从1和2中进行选择。
如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。
如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。
所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。
因此，玩家 1 永远不会成为赢家，返回 False 。
示例 2：输入：[1, 5, 233, 7] 输出：True
解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。
无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 True，表示玩家 1 可以成为赢家。
提示：1 <= 给定的数组长度 <= 20.
数组里所有分数都为非负数且不会大于 10000000 。
如果最终两个玩家的分数相等，那么玩家 1 仍为赢家。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(2^n) |
O(n) |
| 02 |
动态规划-一维 |
O(n^2) |
O(n) |
| 03 |
动态规划-二维 |
O(n^2) |
O(n^2) |
func PredictTheWinner(nums []int) bool {
return dfs(nums, 0, len(nums)-1) >= 0
}
func dfs(nums []int, start, end int) int {
if start > end {
return 0
}
left := nums[start] - dfs(nums, start+1, end)
right := nums[end] - dfs(nums, start, end-1)
return max(left, right)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func PredictTheWinner(nums []int) bool {
dp := make([]int, len(nums))
for i := 0; i < len(nums); i++ {
dp[i] = nums[i]
}
for i := len(nums) - 2; i >= 0; i-- {
for j := i + 1; j < len(nums); j++ {
dp[j] = max(nums[i]-dp[j], nums[j]-dp[j-1])
}
}
return dp[len(nums)-1] >= 0
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 3
func PredictTheWinner(nums []int) bool {
n := len(nums)
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, n)
dp[i][i] = nums[i]
}
for i := n - 2; i >= 0; i-- {
for j := i + 1; j < n; j++ {
dp[i][j] = max(nums[i]-dp[i+1][j], nums[j]-dp[i][j-1])
}
}
return dp[0][n-1] >= 0
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
491.递增子序列(2)
给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
示例:输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
说明:给定数组的长度不会超过15。
数组中的整数范围是 [-100,100]。
给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
深度优先搜索-回溯 |
O(2^n) |
O(2^n) |
| 02 |
深度优先搜索-回溯 |
O(2^n) |
O(2^n) |
var res [][]int
func findSubsequences(nums []int) [][]int {
res = make([][]int, 0)
dfs(nums, 0, math.MinInt32, make([]int, 0))
return res
}
func dfs(nums []int, index int, prev int, arr []int) {
if index == len(nums) {
if len(arr) >= 2 {
temp := make([]int, len(arr))
copy(temp, arr)
res = append(res, temp)
}
return
}
if prev <= nums[index] {
arr = append(arr, nums[index])
dfs(nums, index+1, nums[index], arr)
arr = arr[:len(arr)-1]
}
if prev != nums[index] {
dfs(nums, index+1, prev, arr)
}
}
# 2
var res [][]int
func findSubsequences(nums []int) [][]int {
res = make([][]int, 0)
dfs(nums, 0, make([]int, 0))
return res
}
func dfs(nums []int, index int, arr []int) {
if len(arr) >= 2 {
temp := make([]int, len(arr))
copy(temp, arr)
res = append(res, temp)
}
m := make(map[int]bool)
for i := index; i < len(nums); i++ {
if m[nums[i]] == true || (len(arr) > 0 && nums[i] < arr[len(arr)-1]) {
continue
}
m[nums[i]] = true
dfs(nums, i+1, append(arr, nums[i]))
}
}
494.目标和(5)
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。
对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例：输入：nums: [1, 1, 1, 1, 1], S: 3 输出：5
解释：
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
一共有5种方法让最终目标和为3。
提示：数组非空，且长度不会超过 20 。
初始的数组的和不会超过 1000 。
保证返回的最终结果能被 32 位整数存下。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(2^n) |
O(n) |
| 02 |
动态规划 |
O(2^n) |
O(n) |
| 03 |
回溯 |
O(2^n) |
O(n) |
| 04 |
动态规划-01背包 |
O(n^2) |
O(n) |
| 05 |
动态规划 |
O(n^2) |
O(n^2) |
func findTargetSumWays(nums []int, S int) int {
if len(nums) == 0 {
return 0
}
if len(nums) == 1 {
if nums[0] == 0 && S == 0 {
return 2
}
if nums[0] == S || nums[0] == -S {
return 1
}
}
value := nums[0]
nums = nums[1:]
return findTargetSumWays(nums, S-value) + findTargetSumWays(nums, S+value)
}
# 2
func findTargetSumWays(nums []int, S int) int {
dp := make(map[int]int)
dp[nums[0]]++
dp[-nums[0]]++
for i := 1; i < len(nums); i++ {
temp := make(map[int]int)
for k, v := range dp {
temp[k-nums[i]] = temp[k-nums[i]] + v
temp[k+nums[i]] = temp[k+nums[i]] + v
}
dp = temp
}
return dp[S]
}
# 3
var res int
func findTargetSumWays(nums []int, S int) int {
res = 0
dfs(nums, 0, S)
return res
}
func dfs(nums []int, index int, target int) {
if index == len(nums) {
if target == 0 {
res++
}
return
}
dfs(nums, index+1, target+nums[index])
dfs(nums, index+1, target-nums[index])
}
# 4
func findTargetSumWays(nums []int, S int) int {
sum := 0
for i := 0; i < len(nums); i++ {
sum = sum + nums[i]
}
if sum < int(math.Abs(float64(S))) || (sum+S)%2 == 1 {
return 0
}
target := (sum + S) / 2
dp := make([]int, target+1)
dp[0] = 1
for i := 1; i <= len(nums); i++ {
for j := target; j >= 0; j-- {
if j >= nums[i-1] {
dp[j] = dp[j] + dp[j-nums[i-1]]
} else {
dp[j] = dp[j]
}
}
}
return dp[target]
}
# 5
func findTargetSumWays(nums []int, S int) int {
sum := 0
for i := 0; i < len(nums); i++ {
sum = sum + nums[i]
}
if sum < int(math.Abs(float64(S))) || (sum+S)%2 == 1 {
return 0
}
target := (sum + S) / 2
dp := make([][]int, len(nums)+1)
for i := 0; i <= len(nums); i++ {
dp[i] = make([]int, target+1)
dp[i][0] = 1
}
for i := 1; i <= len(nums); i++ {
for j := 0; j <= target; j++ {
if j >= nums[i-1] {
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]
} else {
dp[i][j] = dp[i-1][j]
}
}
}
return dp[len(nums)][target]
}
495.提莫攻击(1)
在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄，
他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。
现在，给出提莫对艾希的攻击时间序列和提莫攻击的中毒持续时间，你需要输出艾希的中毒状态总时长。
你可以认为提莫在给定的时间点进行攻击，并立即使艾希处于中毒状态。
示例1:输入: [1,4], 2 输出: 4
原因: 第 1 秒初，提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟，直到第 2 秒末结束。
第 4 秒初，提莫再次攻击艾希，使得艾希获得另外 2 秒中毒时间。 所以最终输出 4 秒。
示例2:输入: [1,2], 2 输出: 3
原因: 第 1 秒初，提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟，直到第 2 秒末结束。
但是第 2 秒初，提莫再次攻击了已经处于中毒状态的艾希。
由于中毒状态不可叠加，提莫在第 2 秒初的这次攻击会在第 3 秒末结束。 所以最终输出 3 。
提示：你可以假定时间序列数组的总长度不超过 10000。
你可以假定提莫攻击时间序列中的数字和提莫攻击的中毒持续时间都是非负整数，并且不超过 10,000,000。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
func findPoisonedDuration(timeSeries []int, duration int) int {
res := 0
if len(timeSeries) == 0 {
return 0
}
for i := 0; i < len(timeSeries)-1; i++ {
res = res + min(timeSeries[i+1]-timeSeries[i], duration)
}
return res + duration
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
497.非重叠矩形中的随机点(1)
给定一个非重叠轴对齐矩形的列表 rects，写一个函数 pick 随机均匀地选取矩形覆盖的空间中的整数点。
提示：整数点是具有整数坐标的点。
矩形周边上的点包含在矩形覆盖的空间中。
第 i 个矩形 rects [i] = [x1，y1，x2，y2]，其中[x1，y1] 是左下角的整数坐标，[x2，y2] 是右上角的整数坐标。
每个矩形的长度和宽度不超过 2000。
1 <= rects.length<= 100
pick 以整数坐标数组[p_x, p_y]的形式返回一个点。
pick 最多被调用10000次。
示例 1：输入: ["Solution","pick","pick","pick"] [[[[1,1,5,5]]],[],[],[]] 输出: [null,[4,1],[4,1],[3,3]]
示例 2：输入: ["Solution","pick","pick","pick","pick","pick"] [[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
输出: [null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]
输入语法的说明：
输入是两个列表：调用的子例程及其参数。
Solution 的构造函数有一个参数，即矩形数组 rects。pick 没有参数。参数总是用列表包装的，即使没有也是如此。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
前缀和+二分查找 |
O(n) |
O(n) |
type Solution struct {
nums []int
total int
rects [][]int
}
func Constructor(rects [][]int) Solution {
arr := make([]int, 0)
total := 0
for i := 0; i < len(rects); i++ {
x1, y1, x2, y2 := rects[i][0], rects[i][1], rects[i][2], rects[i][3]
total = total + (x2-x1+1)*(y2-y1+1)
arr = append(arr, total)
}
return Solution{nums: arr, total: total, rects: rects}
}
func (this *Solution) Pick() []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
}
}
temp := this.rects[left]
x1, y1, x2, y2 := temp[0], temp[1], temp[2], temp[3]
width := x2 - x1 + 1
height := y2 - y1 + 1
start := this.nums[left] - width*height
return []int{x1 + (target-start)%width, y1 + (target-start)/width}
}
498.对角线遍历(2)
给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，
对角线遍历如下图所示。
示例:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,4,7,5,3,6,8,9]
说明:给定矩阵中的元素总数不会超过 100000 。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^2) |
O(n^2) |
| 02 |
遍历 |
O(n^2) |
O(n^2) |
func findDiagonalOrder(matrix [][]int) []int {
res := make([]int, 0)
if len(matrix) == 0 {
return res
}
n, m := len(matrix), len(matrix[0])
if n == 1 {
return matrix[0]
}
i, j := 0, 0
flag := false
for j < m {
a, b := i, j
temp := make([]int, 0)
temp = append(temp, matrix[a][b])
for a != 0 && b != m-1 {
a--
b++
temp = append(temp, matrix[a][b])
}
if flag == true {
reverse(temp)
flag = false
} else {
flag = true
}
res = append(res, temp...)
if i != n-1 {
i++
} else {
j++
}
}
return res
}
func reverse(arr []int) {
for i := 0; i < len(arr)/2; i++ {
arr[i], arr[len(arr)-1-i] = arr[len(arr)-1-i], arr[i]
}
}
# 2
func findDiagonalOrder(matrix [][]int) []int {
res := make([]int, 0)
if len(matrix) == 0 {
return res
}
n, m := len(matrix), len(matrix[0])
if n == 1 {
return matrix[0]
}
for i := 0; i < n+m-1; i++ {
temp := make([]int, 0)
var a, b int
if i < m {
a = 0
b = i
} else {
a = i - m + 1
b = m - 1
}
for a < n && b >= 0 {
temp = append(temp, matrix[a][b])
a, b = a+1, b-1
}
if i%2 == 0 {
reverse(temp)
}
res = append(res, temp...)
}
return res
}
func reverse(arr []int) {
for i := 0; i < len(arr)/2; i++ {
arr[i], arr[len(arr)-1-i] = arr[len(arr)-1-i], arr[i]
}
}
0401-0500-Hard
403.青蛙过河(4)
一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。
青蛙可以跳上石子，但是不可以跳入水中。
给你石子的位置列表 stones（用单元格序号 升序 表示），
请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。
开始时，青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃一个单位
（即只能从单元格 1 跳至单元格 2 ）。
如果青蛙上一步跳跃了k个单位，那么它接下来的跳跃距离只能选择为k - 1、k或k + 1 个单位。
另请注意，青蛙只能向前方（终点的方向）跳跃。
示例 1：输入：stones = [0,1,3,5,6,8,12,17] 输出：true
解释：青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子,
然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子,
然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子,
最后，跳 5 个单位到第 8 个石子（即最后一块石子）。
示例 2：输入：stones = [0,1,2,3,4,8,9,11] 输出：false
解释：这是因为第 5 和第 6 个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。
提示：2 <= stones.length <= 2000
0 <= stones[i] <= 231 - 1
stones[0] == 0
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n^2) |
O(n^2) |
| 02 |
动态规划 |
O(n^2) |
O(n^2) |
| 03 |
动态规划 |
O(n^2) |
O(n^2) |
| 04 |
广度优先搜索 |
O(n^2) |
O(n^2) |
var m [][]int
func canCross(stones []int) bool {
n := len(stones)
m = make([][]int, n)
for i := 0; i < n; i++ {
m[i] = make([]int, n)
for j := 0; j < n; j++ {
m[i][j] = -1
}
}
return dfs(stones, 0, 0) == 1
}
func dfs(stones []int, index int, k int) int {
if m[index][k] >= 0 {
return m[index][k]
}
for i := index + 1; i < len(stones); i++ {
next := stones[i] - stones[index]
if k-1 <= next && next <= k+1 {
if dfs(stones, i, next) == 1 {
m[index][k] = 1
return 1
}
}
}
if index == len(stones)-1 {
m[index][k] = 1
} else {
m[index][k] = 0
}
return m[index][k]
}
# 2
func canCross(stones []int) bool {
n := len(stones)
m := make(map[int]map[int]int)
for i := 0; i < n; i++ {
m[stones[i]] = make(map[int]int)
}
m[0][0] = 1
for i := 0; i < n; i++ {
for k := range m[stones[i]] {
for next := k - 1; next <= k+1; next++ {
if next > 0 {
if _, ok := m[stones[i]+next]; ok {
m[stones[i]+next][next] = 1
}
}
}
}
}
return len(m[stones[n-1]]) > 0
}
# 3
func canCross(stones []int) bool {
n := len(stones)
dp := make([][]bool, n+1)
for i := 0; i < n; i++ {
dp[i] = make([]bool, n+1)
}
dp[0][0] = true
for i := 0; i < n; i++ {
for j := 0; j < i; j++ {
k := stones[i] - stones[j]
if k <= i {
dp[i][k] = dp[j][k-1] || dp[j][k] || dp[j][k+1]
if i == n-1 && dp[i][k] == true {
return true
}
}
}
}
return false
}
# 4
type Node struct {
index int
size int
}
func canCross(stones []int) bool {
n := len(stones)
m := make(map[int]bool)
for i := 0; i < n; i++ {
m[stones[i]] = true
}
isVisited := make(map[Node]bool)
stack := make([]Node, 0)
node := Node{
index: 0,
size: 0,
}
stack = append(stack, node)
isVisited[node] = true
for len(stack) > 0 {
node = stack[len(stack)-1]
stack = stack[:len(stack)-1]
if node.index == stones[n-1] {
return true
}
for k := node.size - 1; k <= node.size+1; k++ {
next := node.index + k
if k > stones[n-1] {
continue
}
temp := Node{
index: next,
size: k,
}
if k > 0 && m[next] == true && isVisited[temp] == false {
isVisited[temp] = true
stack = append(stack, temp)
}
}
}
return false
}
410.分割数组的最大值(3)
给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。
设计一个算法使得这 m 个子数组各自和的最大值最小。
注意:数组长度 n 满足以下条件:
1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)
示例:输入: nums = [7,2,5,10,8] m = 2输出:18
解释:一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
二分查找 |
O(nlog(n)) |
O(1) |
| 02 |
动态规划+前缀和 |
O(n^3) |
O(n^2) |
| 03 |
二分查找 |
O(nlog(n)) |
O(1) |
func splitArray(nums []int, m int) int {
left, right := 0, 0
for i := 0; i < len(nums); i++ {
right = right + nums[i]
if left < nums[i] {
left = nums[i]
}
}
for left < right {
mid := left + (right-left)/2
if check(nums, mid, m) {
right = mid
} else {
left = mid + 1
}
}
return left
}
func check(arr []int, target int, m int) bool {
sum := 0
count := 1
for i := 0; i < len(arr); i++ {
if sum+arr[i] > target {
count++
sum = arr[i]
} else {
sum = sum + arr[i]
}
}
return count <= m
}
# 2
func splitArray(nums []int, m int) int {
n := len(nums)
dp := make([][]int, n+1)
sub := make([]int, n+1)
for i := 0; i < n+1; i++ {
dp[i] = make([]int, m+1)
for j := 0; j < m+1; j++ {
dp[i][j] = math.MaxInt32
}
}
for i := 0; i < n; i++ {
sub[i+1] = sub[i] + nums[i]
}
dp[0][0] = 0
for i := 1; i <= n; i++ {
for j := 1; j <= min(i, m); j++ {
for k := 0; k < i; k++ {
dp[i][j] = min(dp[i][j], max(dp[k][j-1], sub[i]-sub[k]))
}
}
}
return dp[n][m]
}
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 splitArray(nums []int, m int) int {
left, right := 0, 0
for i := 0; i < len(nums); i++ {
right = right + nums[i]
if left < nums[i] {
left = nums[i]
}
}
for left < right {
mid := left + (right-left)/2
if check(nums, mid, m) > m {
left = mid + 1
} else {
right = mid
}
}
return left
}
func check(arr []int, target int, m int) int {
sum := 0
count := 1
for i := 0; i < len(arr); i++ {
if sum+arr[i] > target {
count++
sum = 0
}
sum = sum + arr[i]
}
return count
}
440.字典序的第K小数字(1)
给定整数n和k，找到1到n中字典序第k小的数字。
注意：1 ≤ k ≤ n ≤ 109。
示例 :输入: n: 13 k: 2 输出: 10
解释:字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O((log(n))^2) |
O(1) |
func findKthNumber(n int, k int) int {
pre := 1
count := 1
for count < k {
total := getCount(pre, n)
if count+total > k {
pre = pre * 10
count++
} else if count+total <= k {
pre++
count = count + total
}
}
return pre
}
func getCount(pre, n int) int {
count := 0
a := pre
b := pre + 1
for a <= n {
if b < n+1 {
count = count + b - a
} else {
count = count + n + 1 - a
}
a = a * 10
b = b * 10
}
return count
}
446.等差数列划分II-子序列(1)
如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。
例如，以下数列为等差数列:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下数列不是等差数列。
1, 1, 2, 5, 7
数组 A 包含 N 个数，且索引从 0 开始。
该数组子序列将划分为整数序列(P0, P1, ..., Pk)，满足 0 ≤ P0 < P1 < ... < Pk < N。
如果序列 A[P0]，A[P1]，...，A[Pk-1]，A[Pk] 是等差的，那么数组 A 的子序列 (P0，P1，…，PK) 称为等差序列。
值得注意的是，这意味着 k ≥ 2。
函数要返回数组 A 中所有等差子序列的个数。
输入包含 N 个整数。每个整数都在 -231 和 231-1 之间，另外 0 ≤ N ≤ 1000。保证输出小于 231-1。
示例：输入：[2, 4, 6, 8, 10] 输出：7
解释： 所有的等差子序列为：
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n^2) |
func numberOfArithmeticSlices(nums []int) int {
n := len(nums)
dp := make([]map[int]int, n)
for i := 0; i < n; i++ {
dp[i] = make(map[int]int)
}
res := 0
for i := 1; i < n; i++ {
for j := 0; j < i; j++ {
diff := nums[i] - nums[j]
dp[i][diff] = dp[i][diff] + dp[j][diff] + 1
res = res + dp[j][diff]
}
}
return res
}
458.可怜的小猪(2)
有 buckets 桶液体，其中 正好 有一桶含有毒药，其余装的都是水。
它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药，你可以喂一些猪喝，通过观察猪是否会死进行判断。
不幸的是，你只有minutesToTest 分钟时间来确定哪桶液体是有毒的。
喂猪的规则如下：
选择若干活猪进行喂养
可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。
小猪喝完水后，必须有 minutesToDie 分钟的冷却时间。在这段时间里，你只能观察，而不允许继续喂猪。
过了 minutesToDie 分钟后，所有喝到毒药的猪都会死去，其他所有猪都会活下来。
重复这一过程，直到时间用完。
给你桶的数目 buckets ，minutesToDie 和 minutesToTest ，返回在规定时间内判断哪个桶有毒所需的 最小 猪数。
示例 1：输入：buckets = 1000, minutesToDie = 15, minutesToTest = 60 输出：5
示例 2：输入：buckets = 4, minutesToDie = 15, minutesToTest = 15 输出：2
示例 3：输入：buckets = 4, minutesToDie = 15, minutesToTest = 30 输出：2
提示：1 <= buckets <= 1000
1 <=minutesToDie <=minutesToTest <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(log(n)) |
O(1) |
| 02 |
内置函数 |
O(1) |
O(1) |
func poorPigs(buckets int, minutesToDie int, minutesToTest int) int {
count := minutesToTest/minutesToDie + 1
res := 0
target := 1
for target < buckets {
target = target * count
res++
}
return res
}
# 2
func poorPigs(buckets int, minutesToDie int, minutesToTest int) int {
count := minutesToTest/minutesToDie + 1
res := math.Log(float64(buckets)) / math.Log(float64(count))
return int(math.Ceil(res))
}
460.LFU缓存(2)
请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。
get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
put(key, value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。
当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。
在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最久未使用的键。
「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。
进阶：你是否可以在 O(1) 时间复杂度内执行两项操作？
示例：LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 去除 key 2
cache.get(2); // 返回 -1 (未找到key 2)
cache.get(3); // 返回 3
cache.put(4, 4); // 去除 key 1
cache.get(1); // 返回 -1 (未找到 key 1)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希+双向链表 |
O(1) |
O(n) |
| 02 |
内置list |
O(1) |
O(n) |
type Node struct {
key int
value int
count int
next *Node
prev *Node
}
type LFUCache struct {
cap int
minFreq int
kv map[int]*Node
fk map[int]*DoubleList
}
func Constructor(capacity int) LFUCache {
return LFUCache{
cap: capacity,
kv: make(map[int]*Node),
fk: make(map[int]*DoubleList),
minFreq: 0,
}
}
func (this *LFUCache) Get(key int) int {
node, ok := this.kv[key]
if ok == false {
return -1
}
this.increaseFreq(node)
return node.value
}
func (this *LFUCache) Put(key int, value int) {
if this.cap <= 0 {
return
}
node, ok := this.kv[key]
if ok {
node.value = value
this.increaseFreq(node)
return
}
if this.cap <= len(this.kv) {
last := this.remove()
delete(this.kv, last.key)
}
temp := &Node{
key: key,
value: value,
count: 1,
}
this.kv[key] = temp
if this.fk[1] == nil {
this.fk[1] = NewDoubleList()
}
this.fk[1].Push(temp)
this.minFreq = 1
}
func (this *LFUCache) increaseFreq(node *Node) {
freq := node.count
this.fk[freq].Remove(node)
if this.fk[freq+1] == nil {
this.fk[freq+1] = NewDoubleList()
}
node.count++
this.fk[freq+1].Push(node)
if this.fk[freq].head.next == this.fk[freq].tail {
if freq == this.minFreq {
this.minFreq++
}
}
return
}
func (this *LFUCache) remove() *Node {
temp := this.fk[this.minFreq]
last := temp.tail.prev
temp.Remove(temp.tail.prev)
return last
}
type DoubleList struct {
head *Node
tail *Node
}
func NewDoubleList() *DoubleList {
node := &DoubleList{
head: &Node{},
tail: &Node{},
}
node.head.next = node.tail
node.tail.prev = node.head
return node
}
func (this *DoubleList) Push(node *Node) {
next := this.head.next
node.next = next
node.prev = this.head
next.prev = node
this.head.next = node
}
func (this *DoubleList) Remove(node *Node) {
node.prev.next = node.next
node.next.prev = node.prev
node.next = nil
node.prev = nil
}
# 2
type Node struct {
key int
value int
count int
}
type LFUCache struct {
cap int
minFreq int
kv map[int]*list.Element
fk map[int]*list.List
}
func Constructor(capacity int) LFUCache {
return LFUCache{
cap: capacity,
minFreq: 0,
kv: make(map[int]*list.Element),
fk: make(map[int]*list.List),
}
}
func (this *LFUCache) Get(key int) int {
node, ok := this.kv[key]
if ok == false {
return -1
}
return this.increaseFreq(node)
}
func (this *LFUCache) Put(key int, value int) {
data, ok := this.kv[key]
if ok {
node := data.Value.(*Node)
node.value = value
this.increaseFreq(data)
return
}
if this.cap == len(this.kv) {
cur, ok := this.fk[this.minFreq]
if ok == false {
return
}
deleteKey := cur.Front()
cur.Remove(deleteKey)
delete(this.kv, deleteKey.Value.(*Node).key)
}
temp := &Node{
key: key,
value: value,
count: 1,
}
if _, ok := this.fk[1]; ok == false {
this.fk[1] = list.New()
}
res := this.fk[1].PushBack(temp)
this.kv[key] = res
this.minFreq = 1
}
func (this *LFUCache) increaseFreq(data *list.Element) int {
node := data.Value.(*Node)
cur, ok := this.fk[node.count]
if ok == false {
return -1
}
cur.Remove(data)
if cur.Len() == 0 && this.minFreq == node.count {
this.minFreq++
}
node.count++
if this.fk[node.count] == nil {
this.fk[node.count] = list.New()
}
res := this.fk[node.count].PushBack(node)
this.kv[node.key] = res
return node.value
}
466.统计重复个数(1)
由 n 个连接的字符串 s 组成字符串 S，记作S = [s,n]。例如，["abc",3]=“abcabcabc”。
如果我们可以从 s2中删除某些字符使其变为 s1，则称字符串 s1可以从字符串 s2 获得。
例如，根据定义，"abc" 可以从 “abdbec” 获得，但不能从 “acbbe” 获得。
现在给你两个非空字符串 s1和 s2（每个最多 100 个字符长）和两个整数 0 ≤ n1 ≤ 106和 1 ≤ n2 ≤ 106。
现在考虑字符串 S1 和 S2，其中 S1=[s1,n1]、S2=[s2,n2] 。
请你找出一个可以满足使[S2,M] 从 S1获得的最大整数 M 。
示例：输入： s1 ="acb",n1 = 4 s2 ="ab",n2 = 2 返回：2
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n^2) |
O(1) |
func getMaxRepetitions(s1 string, n1 int, s2 string, n2 int) int {
count := 0
j := 0
for a := 0; a < n1; a++ {
for i := 0; i < len(s1); i++ {
if s1[i] == s2[j] {
if j == len(s2)-1 {
j = 0
count++
} else {
j++
}
}
}
}
return count / n2
}
472.连接词(1)
给你一个 不含重复 单词的字符串数组 words ，请你找出并返回 words 中的所有 连接词 。
连接词 定义为：一个完全由给定数组中的至少两个较短单词组成的字符串。
示例 1：输入：words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
输出：["catsdogcats","dogcatsdog","ratcatdogcat"]
解释："catsdogcats" 由 "cats", "dog" 和 "cats" 组成;
"dogcatsdog" 由 "dog", "cats" 和 "dog" 组成;
"ratcatdogcat" 由 "rat", "cat", "dog" 和 "cat" 组成。
示例 2：输入：words = ["cat","dog","catdog"] 输出：["catdog"]
提示：1 <= words.length <= 104
0 <= words[i].length <= 1000
words[i] 仅由小写字母组成
0 <= sum(words[i].length) <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
trie树 |
O(nlog(n)) |
O(n) |
func findAllConcatenatedWordsInADict(words []string) []string {
res := make([]string, 0)
sort.Slice(words, func(i, j int) bool {
return len(words[i]) < len(words[j])
})
root := Trie{}
for i := 0; i < len(words); i++ {
if words[i] == "" {
continue
}
if root.Dfs(words[i]) == true {
res = append(res, words[i])
} else {
root.Insert(words[i])
}
}
return res
}
type Trie struct {
next [26]*Trie
ending int
}
func (this *Trie) Insert(word string) {
temp := this
for _, v := range word {
value := v - 'a'
if temp.next[value] == nil {
temp.next[value] = &Trie{
next: [26]*Trie{},
ending: 0,
}
}
temp = temp.next[value]
}
temp.ending++
}
func (this *Trie) Dfs(word string) bool {
if word == "" {
return true
}
temp := this
for i := 0; i < len(word); i++ {
value := word[i] - 'a'
temp = temp.next[value]
if temp == nil {
return false
}
if temp.ending > 0 && this.Dfs(word[i+1:]) == true {
return true
}
}
return false
}
479.最大回文数乘积(1)
你需要找到由两个 n 位数的乘积组成的最大回文数。
由于结果会很大，你只需返回最大回文数 mod 1337得到的结果。
示例:输入: 2 输出: 987
解释: 99 x 91 = 9009, 9009 % 1337 = 987
说明:n 的取值范围为[1,8]。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(2^n) |
O(n) |
func largestPalindrome(n int) int {
if n == 1 {
return 9
}
last := int(math.Pow10(n)) - 1
first := last / 10
for i := last; i > first; i-- {
target := makePalindrome(i)
for j := last; j > first && target < j*j; j-- {
if target%j == 0 {
return target % 1337
}
}
}
return 0
}
func makePalindrome(num int) int {
str := strconv.Itoa(num)
arr := []byte(str)
for i := len(str) - 1; i > -1; i-- {
arr = append(arr, str[i])
}
res, _ := strconv.Atoi(string(arr))
return res
}
480.滑动窗口中位数
题目
中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。
例如：[2,3,4]，中位数是3
[2,3]，中位数是 (2 + 3) / 2 = 2.5
给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。
你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。
示例：给出nums = [1,3,-1,-3,5,3,6,7]，以及k = 3。
窗口位置 中位数
--------------- -----
[1 3 -1] -3 5 3 6 7 1
1 [3 -1 -3] 5 3 6 7 -1
1 3 [-1 -3 5] 3 6 7 -1
1 3 -1 [-3 5 3] 6 7 3
1 3 -1 -3 [5 3 6] 7 5
1 3 -1 -3 5 [3 6 7] 6
因此，返回该滑动窗口的中位数数组[1,-1,-1,3,5,6]。
提示：你可以假设k始终有效，即：k 始终小于等于输入的非空数组的元素个数。
与真实值误差在 10 ^ -5 以内的答案将被视作正确答案。
解题思路
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
归并排序 |
O(nlog(n)) |
O(n) |
493.翻转对(4)
给定一个数组nums，如果i < j且nums[i] > 2*nums[j]我们就将(i, j)称作一个重要翻转对。
你需要返回给定数组中的重要翻转对的数量。
示例 1:输入: [1,3,2,3,1] 输出: 2
示例 2:输入: [2,4,3,5,1] 输出: 3
注意:
给定数组的长度不会超过50000。
输入数组中的所有数字都在32位整数的表示范围内。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
归并排序 |
O(nlog(n)) |
O(n) |
| 02 |
树状数组+离散化 |
O(nlog(n)) |
O(n) |
| 03 |
树状数组+离散化 |
O(nlog(n)) |
O(n) |
| 04 |
线段树+离散化 |
O(nlog(n)) |
O(n) |
func reversePairs(nums []int) int {
n := len(nums)
if n <= 1 {
return 0
}
a := append([]int{}, nums[:n/2]...)
b := append([]int{}, nums[n/2:]...)
res := reversePairs(a) + reversePairs(b)
i, j := 0, 0
for i = 0; i < len(a); i++ {
for j < len(b) && a[i] > 2*b[j] {
j++
}
res = res + j
}
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 reversePairs(nums []int) int {
n := len(nums)
if n <= 1 {
return 0
}
temp := make([]int, 0)
for i := 0; i < n; i++ {
temp = append(temp, nums[i], 2*nums[i])
}
arr, m := getLSH(temp)
length = len(arr)
c = make([]int, length+1)
res := 0
for i := 0; i < n; i++ {
index := m[2*nums[i]]
count := getSum(index)
res = res + i - count
upData(m[nums[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
}
# 3
func reversePairs(nums []int) int {
n := len(nums)
if n <= 1 {
return 0
}
temp := make([]int, 0)
for i := 0; i < n; i++ {
temp = append(temp, nums[i], 2*nums[i])
}
arr, m := getLSH(temp)
length = len(arr)
c = make([]int, length+1)
res := 0
for i := n - 1; i >= 0; i-- {
index := m[nums[i]]
count := getSum(index - 1)
res = res + count
upData(m[2*nums[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
}
# 4
func reversePairs(nums []int) int {
n := len(nums)
if n <= 1 {
return 0
}
temp := make([]int, 0)
for i := 0; i < n; i++ {
temp = append(temp, nums[i], 2*nums[i])
}
tempArr, m := getLSH(temp)
total := len(tempArr)
arr = make([]int, 4*total+1)
res := 0
for i := n - 1; i >= 0; i-- {
index := m[nums[i]]
count := query(0, 1, total, 1, index-1)
res = res + count
update(0, 1, total, m[2*nums[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 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)
}