0201-0300-Easy
202.快乐数(2)
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。
示例： 输入：19 输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希+遍历 |
O(log(n)) |
O(log(n)) |
| 02 |
遍历+快慢判断环 |
O(log(n)) |
O(1) |
func isHappy(n int) bool {
now, next := n, nextValue(n)
m := make(map[int]int)
m[now] = 1
for {
if next == 1 {
break
}
if _, ok := m[next]; ok {
break
} else {
m[next] = 1
}
next = nextValue(next)
}
if next == 1 {
return true
}
return false
}
func nextValue(n int) int {
ret := 0
for n != 0 {
ret = ret + (n%10)*(n%10)
n = n / 10
}
return ret
}
#
func isHappy(n int) bool {
now, next := n, nextValue(n)
for now != next {
now = nextValue(now)
next = nextValue(nextValue(next))
}
if now == 1 {
return true
}
return false
}
func nextValue(n int) int {
ret := 0
for n != 0 {
ret = ret + (n%10)*(n%10)
n = n / 10
}
return ret
}
203.移除链表元素(2)
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哨兵结点+链表遍历 |
O(n) |
O(1) |
| 02 |
递归 |
O(n) |
O(n) |
func removeElements(head *ListNode, val int) *ListNode {
headPre := &ListNode{Next: head}
temp := headPre
for temp.Next != nil {
if temp.Next.Val == val {
temp.Next = temp.Next.Next
} else {
temp = temp.Next
}
}
return headPre.Next
}
# 递归
func removeElements(head *ListNode, val int) *ListNode {
if head == nil {
return nil
}
head.Next = removeElements(head.Next, val)
if head.Val == val {
return head.Next
}
return head
}
204.计数质数(2)
统计所有小于非负整数 n 的质数的数量。
示例:
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
筛选质数(厄拉多塞筛法) |
O(n^2) |
O(n) |
| 02 |
筛选质数优化 |
O(n) |
O(n) |
func countPrimes(n int) int {
if n < 3 {
return 0
}
notPrimes := make([]bool, n)
count := 0
for i := 2; i < n; i++ {
if notPrimes[i] {
continue
}
for j := i*2 ; j < n; j += i {
notPrimes[j] = true
}
count++
}
return count
}
#
func countPrimes(n int) int {
if n < 3 {
return 0
}
isPrimes := make([]bool, n)
for i := range isPrimes {
isPrimes[i] = true
}
for i := 2; i*i < n; i++ {
if !isPrimes[i] {
continue
}
for j := i * i; j < n; j += i {
isPrimes[j] = false
}
}
count := 0
for i := 2; i < n; i++ {
if isPrimes[i] {
count++
}
}
return count
}
205.同构字符串(3)
给定两个字符串 s 和 t，判断它们是否是同构的。
如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。
两个字符不能映射到同一个字符上，但字符可以映射自己本身。
示例 1: 输入: s = "egg", t = "add" 输出: true
示例 2:输入: s = "foo", t = "bar" 输出: false
示例 3: 输入: s = "paper", t = "title" 输出: true
说明:你可以假设 s 和 t 具有相同的长度。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数组映射 |
O(n) |
O(n) |
| 02 |
哈希映射 |
O(n) |
O(n) |
| 03 |
字符串查找匹配 |
O(n) |
O(1) |
func isIsomorphic(s string, t string) bool {
if len(s) != len(t) {
return false
}
m1 := make([]int, 256)
m2 := make([]int, 256)
for i := 0; i < len(s); i++ {
a := int(s[i])
b := int(t[i])
if m1[a] != m2[b] {
return false
}
m1[a] = i + 1
m2[b] = i + 1
}
return true
}
func isIsomorphic(s string, t string) bool {
if len(s) != len(t) {
return false
}
m := make(map[int]int)
n := make(map[int]int)
for i := 0; i < len(s); i++ {
a := int(s[i])
b := int(t[i])
if m[a] == 0 && n[b] == 0 {
m[a] = b
n[b] = a
} else if m[a] != b || n[b] != a {
return false
}
}
return true
}
func isIsomorphic(s string, t string) bool {
for i := 0; i < len(s); i++ {
if strings.IndexByte(s[i+1:], s[i]) != strings.IndexByte(t[i+1:], t[i]) {
return false
}
}
return true
}
206.反转链表(4)
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(n) |
| 02 |
迭代 |
O(n) |
O(1) |
| 03 |
数组辅助 |
O(n) |
O(n) |
| 04 |
迭代-新建节点 |
O(n) |
O(1) |
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
result := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return result
}
func reverseList(head *ListNode) *ListNode {
var result *ListNode
var temp *ListNode
for head != nil {
temp = head.Next
head.Next = result
result = head
head = temp
}
return result
}
func reverseList(head *ListNode) *ListNode {
result := &ListNode{}
arr := make([]*ListNode, 0)
for head != nil {
arr = append(arr, head)
head = head.Next
}
temp := result
for i := len(arr) - 1; i >= 0; i-- {
arr[i].Next = nil
temp.Next = arr[i]
temp = temp.Next
}
return result.Next
}
func reverseList(head *ListNode) *ListNode {
var res *ListNode
for {
if head == nil {
break
}
res = &ListNode{head.Val, res}
head = head.Next
}
return res
}
217.存在重复元素(2)
给定一个整数数组，判断是否存在重复元素。
如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
示例 1:输入: [1,2,3,1] 输出: true
示例 2:输入: [1,2,3,4] 输出: false
示例 3:输入: [1,1,1,3,3,4,3,2,4,2] 输出: true
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助遍历 |
O(n) |
O(n) |
| 02 |
排序后遍历 |
O(nlog(n)) |
O(1) |
func containsDuplicate(nums []int) bool {
m := make(map[int]int)
for i := 0; i < len(nums); i++ {
if _, ok := m[nums[i]]; ok {
return true
} else {
m[nums[i]] = 1
}
}
return false
}
#
func containsDuplicate(nums []int) bool {
sort.Ints(nums)
for i := 0; i < len(nums)-1; i++{
if nums[i] == nums[i+1]{
return true
}
}
return false
}
219.存在重复元素 II(2)
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，
使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
示例 1:输入: nums = [1,2,3,1], k = 3输出: true
示例 2:输入: nums = [1,0,1,1], k = 1 输出: true
示例 3:输入: nums = [1,2,3,1,2,3], k = 2 输出: false
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助遍历 |
O(n) |
O(n) |
| 02 |
哈希表+滑动窗口 |
O(n) |
O(n) |
#
func containsNearbyDuplicate(nums []int, k int) bool {
m := make(map[int]int)
for i, n := range nums {
if m[n] != 0 && (i+1)-m[n] <= k {
return true
}
m[n] = i + 1
}
return false
}
#
func containsNearbyDuplicate(nums []int, k int) bool {
m := make(map[int]int)
for i, n := range nums {
if m[n] != 0 {
return true
}
m[n] = i + 1
if len(m) > k {
delete(m, nums[i-k])
}
}
return false
}
225.用队列实现栈(4)
使用队列实现栈的下列操作：
push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空
注意:
你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size,
和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 ,
只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
使用切片实现 |
O(1) |
O(n) |
| 02 |
使用1个list实现 |
O(1) |
O(n) |
| 03 |
使用2个list实现 |
O(n) |
O(n) |
| 04 |
使用2个双端队列deque实现 |
O(n) |
O(n) |
type MyStack struct {
arr []int
}
func Constructor() MyStack {
return MyStack{}
}
func (m *MyStack) Push(x int) {
m.arr = append(m.arr, x)
}
func (m *MyStack) Pop() int {
if len(m.arr) == 0 {
return 0
}
last := m.arr[len(m.arr)-1]
m.arr = m.arr[0 : len(m.arr)-1]
return last
}
func (m *MyStack) Top() int {
if len(m.arr) == 0 {
return 0
}
return m.arr[len(m.arr)-1]
}
func (m *MyStack) Empty() bool {
if len(m.arr) == 0 {
return true
}
return false
}
# 使用1个list实现
type MyStack struct {
*list.List
}
func Constructor() MyStack {
return MyStack{
list.New(),
}
}
func (m *MyStack) Push(x int) {
m.PushBack(x)
}
func (m *MyStack) Pop() int {
if m.Len() == 0 {
return -1
}
return m.Remove(m.Back()).(int)
}
func (m *MyStack) Top() int {
if m.Len() == 0 {
return -1
}
return m.Back().Value.(int)
}
func (m *MyStack) Empty() bool {
return m.Len() == 0
}
# 使用2个list实现
type MyStack struct {
l1 *list.List
l2 *list.List
}
func Constructor() MyStack {
return MyStack{
l1: list.New(),
l2: list.New(),
}
}
func (m *MyStack) Push(x int) {
if m.l1.Len() == 0 {
m.l2.PushBack(x)
} else {
m.l1.PushBack(x)
}
}
func (m *MyStack) Pop() int {
var top int
if m.l1.Len() > 0 {
for m.l1.Len() > 1 {
m.l2.PushBack(m.l1.Remove(m.l1.Front()))
}
top = m.l1.Remove(m.l1.Front()).(int)
} else {
for m.l2.Len() > 1 {
m.l1.PushBack(m.l2.Remove(m.l2.Front()))
}
top = m.l2.Remove(m.l2.Front()).(int)
}
return top
}
func (m *MyStack) Top() int {
var top int
if m.l1.Len() > 0 {
for m.l1.Len() > 1 {
m.l2.PushBack(m.l1.Remove(m.l1.Front()))
}
top = m.l1.Back().Value.(int)
m.l2.PushBack(m.l1.Remove(m.l1.Front()))
} else {
for m.l2.Len() > 1 {
m.l1.PushBack(m.l2.Remove(m.l2.Front()))
}
top = m.l2.Back().Value.(int)
m.l1.PushBack(m.l2.Remove(m.l2.Front()))
}
return top
}
func (m *MyStack) Empty() bool {
return m.l1.Len() == 0 && m.l2.Len() == 0
}
# 使用2个双端队列deque实现
type MyStack struct {
l1 *Queue
l2 *Queue
}
func Constructor() MyStack {
return MyStack{
l1: NewQueue(),
l2: NewQueue(),
}
}
func (m *MyStack) Push(x int) {
m.l1.Push(x)
}
func (m *MyStack) Pop() int {
if m.l2.Len() == 0 {
m.l1, m.l2 = m.l2, m.l1
}
for m.l2.Len() > 1 {
m.l1.Push(m.l2.Pop())
}
return m.l2.Pop()
}
func (m *MyStack) Top() int {
res := m.Pop()
m.l1.Push(res)
return res
}
func (m *MyStack) Empty() bool {
return (m.l1.Len() + m.l2.Len()) == 0
}
type Queue struct {
nums []int
}
func NewQueue() *Queue {
return &Queue{
nums: []int{},
}
}
func (q *Queue) Push(n int) {
q.nums = append(q.nums, n)
}
func (q *Queue) Pop() int {
if len(q.nums) == 0 {
return 0
}
res := q.nums[0]
q.nums = q.nums[1:]
return res
}
func (q *Queue) Len() int {
return len(q.nums)
}
func (q *Queue) IsEmpty() bool {
return q.Len() == 0
}
226.翻转二叉树(2)
翻转一棵二叉树。
示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，
但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(n) |
| 02 |
迭代 |
O(n) |
O(n) |
func invertTree(root *TreeNode) *TreeNode {
if root == nil || (root.Left == nil && root.Right == nil) {
return root
}
root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
return root
}
#
func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return root
}
var queue []*TreeNode
queue = append(queue, root)
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
node.Left, node.Right = node.Right, node.Left
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
return root
}
231.2的幂(3)
给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
示例 1:输入: 1 输出: true 解释: 2^0 = 1
示例 2:输入: 16 输出: true 解释: 2^4 = 16
示例 3:输入: 218 输出: false
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
迭代 |
O(log(n)) |
O(1) |
| 02 |
位运算 |
O(1) |
O(1) |
| 03 |
递归 |
O(log(n)) |
O(log(n)) |
func isPowerOfTwo(n int) bool {
if n < 1 {
return false
}
for n > 1 {
if n%2 == 1 {
return false
}
n = n / 2
}
return true
}
#
func isPowerOfTwo(n int) bool {
if n < 1 {
return false
}
return n & (n-1) == 0
}
#
func isPowerOfTwo(n int) bool {
if n < 1 {
return false
}
if n == 1{
return true
}
if n % 2 != 0{
return false
}
return isPowerOfTwo(n/2)
}
232.用栈实现队列(3)
使用栈实现队列的下列操作：
push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。
示例:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
说明:
你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size,
和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
使用切片实现 |
O(1) |
O(n) |
| 02 |
使用2个栈实现 |
O(n) |
O(n) |
| 03 |
使用2个切片实现 |
O(n) |
O(n) |
type MyQueue struct {
a []int
}
func Constructor() MyQueue {
return MyQueue{}
}
func (m *MyQueue) Push(x int) {
m.a = append(m.a, x)
}
func (m *MyQueue) Pop() int {
if len(m.a) == 0 {
return 0
}
first := m.a[0]
m.a = m.a[1:]
return first
}
func (m *MyQueue) Peek() int {
if len(m.a) == 0 {
return 0
}
return m.a[0]
}
func (m *MyQueue) Empty() bool {
if len(m.a) == 0 {
return true
}
return false
}
# 使用2个栈实现
type MyQueue struct {
a, b *Stack
}
func Constructor() MyQueue {
return MyQueue{
a: NewStack(),
b: NewStack(),
}
}
func (m *MyQueue) Push(x int) {
m.a.Push(x)
}
func (m *MyQueue) Pop() int {
if m.b.Len() == 0 {
for m.a.Len() > 0 {
m.b.Push(m.a.Pop())
}
}
return m.b.Pop()
}
func (m *MyQueue) Peek() int {
res := m.Pop()
m.b.Push(res)
return res
}
func (m *MyQueue) Empty() bool {
return m.a.Len() == 0 && m.b.Len() == 0
}
type Stack struct {
nums []int
}
func NewStack() *Stack {
return &Stack{
nums: []int{},
}
}
func (s *Stack) Push(n int) {
s.nums = append(s.nums, n)
}
func (s *Stack) Pop() int {
res := s.nums[len(s.nums)-1]
s.nums = s.nums[:len(s.nums)-1]
return res
}
func (s *Stack) Len() int {
return len(s.nums)
}
func (s *Stack) IsEmpty() bool {
return s.Len() == 0
}
# 使用2个切片实现
type MyQueue struct {
a []int
b []int
}
func Constructor() MyQueue {
return MyQueue{}
}
func (m *MyQueue) Push(x int) {
m.a = append(m.a, x)
}
func (m *MyQueue) Pop() int {
m.Peek()
temp := m.b[len(m.b)-1]
m.b = m.b[:len(m.b)-1]
return temp
}
func (m *MyQueue) Peek() int {
if len(m.b) == 0 {
for len(m.a) > 0 {
m.b = append(m.b, m.a[len(m.a)-1])
m.a = m.a[:len(m.a)-1]
}
}
if len(m.b) == 0 {
return -1
}
return m.b[len(m.b)-1]
}
func (m *MyQueue) Empty() bool {
return len(m.a) == 0 && len(m.b) == 0
}
234.回文链表(4)
请判断一个链表是否为回文链表。
示例 1:输入: 1->2 输出: false
示例 2:输入: 1->2->2->1 输出: true
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数组辅助 |
O(n) |
O(n) |
| 02 |
快慢指针反转链表 |
O(n) |
O(1) |
| 03 |
栈辅助 |
O(n) |
O(n) |
| 04 |
递归 |
O(n) |
O(n) |
func isPalindrome(head *ListNode) bool {
m := make([]int, 0)
for head != nil {
m = append(m, head.Val)
head = head.Next
}
i, j := 0, len(m)-1
for i < j {
if m[i] != m[j] {
return false
}
i++
j--
}
return true
}
# 2
func isPalindrome(head *ListNode) bool {
fast, slow := head, head
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
}
var pre *ListNode
cur := slow
for cur != nil{
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
for pre != nil{
if head.Val != pre.Val{
return false
}
pre = pre.Next
head = head.Next
}
return true
}
# 3
func isPalindrome(head *ListNode) bool {
m := make([]int, 0)
temp := head
for temp != nil {
m = append(m, temp.Val)
temp = temp.Next
}
for head != nil {
val := m[len(m)-1]
m = m[:len(m)-1]
if head.Val != val {
return false
}
head = head.Next
}
return true
}
# 4
var p *ListNode
func isPalindrome(head *ListNode) bool {
if head == nil{
return true
}
if p == nil{
p = head
}
if isPalindrome(head.Next) && (p.Val == head.Val){
p = p.Next
return true
}
p = nil
return false
}
235.二叉搜索树的最近公共祖先(2)
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，
满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(log(n)) |
O(log(n)) |
| 02 |
迭代 |
O(log(n)) |
O(1) |
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if p.Val > root.Val && q.Val > root.Val{
return lowestCommonAncestor(root.Right, p, q)
}else if p.Val < root.Val && q.Val < root.Val{
return lowestCommonAncestor(root.Left, p, q)
}else {
return root
}
}
#
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
for root != nil{
if p.Val > root.Val && q.Val > root.Val{
root = root.Right
}else if p.Val < root.Val && q.Val < root.Val{
root = root.Left
}else {
return root
}
}
return nil
}
237.删除链表中的节点(1)
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
现有一个链表 -- head = [4,5,1,9]，它可以表示为:
示例 1: 输入: head = [4,5,1,9], node = 5 输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:输入: head = [4,5,1,9], node = 1 输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明:
链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
把当前节点替换成下一个节点 |
O(1) |
O(1) |
func deleteNode(node *ListNode) {
node.Val = node.Next.Val
node.Next = node.Next.Next
}
242.有效的字母异位词(2)
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1:输入: s = "anagram", t = "nagaram"输出: true
示例 2:输入: s = "rat", t = "car"输出: false
说明:你可以假设字符串只包含小写字母。
进阶:如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n) |
O(1) |
| 02 |
排序比较 |
O(nlog(n)) |
O(n) |
func isAnagram(s string, t string) bool {
if len(s) != len(t) {
return false
}
sr := []rune(s)
tr := []rune(t)
rec := make(map[rune]int, len(sr))
for i := range sr {
rec[sr[i]]++
rec[tr[i]]--
}
for _, n := range rec {
if n != 0 {
return false
}
}
return true
}
#
func isAnagram(s string, t string) bool {
if len(s) != len(t) {
return false
}
sArr := make([]int, len(s))
tArr := make([]int, len(t))
for i := 0; i < len(s); i++ {
sArr[i] = int(s[i] - 'a')
tArr[i] = int(t[i] - 'a')
}
sort.Ints(sArr)
sort.Ints(tArr)
for i := 0; i < len(s); i++ {
if sArr[i] != tArr[i] {
return false
}
}
return true
}
257.二叉树的所有路径(2)
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入:
1
/ \
2 3
\
5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(log(n)) |
| 02 |
迭代 |
O(n) |
O(n) |
#
func binaryTreePaths(root *TreeNode) []string {
if root == nil {
return nil
}
res := make([]string, 0)
var dfs func(string, *TreeNode)
dfs = func(pre string, root *TreeNode) {
if pre == "" {
pre = strconv.Itoa(root.Val)
} else {
pre += "->" + strconv.Itoa(root.Val)
}
if root.Left != nil {
dfs(pre, root.Left)
}
if root.Right != nil {
dfs(pre, root.Right)
}
if root.Left == nil && root.Right == nil {
res = append(res, pre)
}
}
dfs("", root)
return res
}
#
func binaryTreePaths(root *TreeNode) []string {
res := make([]string, 0)
if root == nil {
return res
}
var queue []*TreeNode
var stringQueue []string
queue = append(queue, root)
stringQueue = append(stringQueue, strconv.Itoa(root.Val))
for len(queue) > 0 {
node := queue[0]
path := stringQueue[0]
queue = queue[1:]
stringQueue = stringQueue[1:]
if node.Left == nil && node.Right == nil {
res = append(res, path)
}
if node.Left != nil {
queue = append(queue, node.Left)
stringQueue = append(stringQueue, path+"->"+strconv.Itoa(node.Left.Val))
}
if node.Right != nil {
queue = append(queue, node.Right)
stringQueue = append(stringQueue, path+"->"+strconv.Itoa(node.Right.Val))
}
}
return res
}
258.各位相加(4)
给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
示例: 输入: 38 输出: 2
解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。
进阶:
你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
找规律1 |
O(1) |
O(1) |
| 02 |
找规律2 |
O(1) |
O(1) |
| 03 |
模拟计算-字符串 |
O(log(n)) |
O(1) |
| 04 |
模拟计算-递归 |
O(log(n)) |
O(log(n)) |
# 找规律1
func addDigits(num int) int {
if num < 10 {
return num
}
if num%9 == 0 {
return 9
}
return num % 9
}
# 找规律2
func addDigits(num int) int {
return (num-1)%9 + 1
}
# 模拟计算-字符串
func addDigits(num int) int {
for num >= 10 {
num = sumDigits(num)
}
return num
}
func sumDigits(num int) int {
sumVal := 0
str := strconv.Itoa(num)
for i := range str {
sumVal = sumVal + int(str[i]-'0')
}
return sumVal
}
# 模拟计算-递归
func addDigits(num int) int {
sum := 0
for num != 0 {
sum = sum + num%10
num = num / 10
}
if sum/10 == 0 {
return sum
}
return addDigits(sum)
}
263.丑数(2)
丑数就是只包含质因数 2, 3, 5 的正整数。
示例 1:输入: 6 输出: true 解释: 6 = 2 × 3
示例 2:输入: 8 输出: true 解释: 8 = 2 × 2 × 2
示例 3: 输入: 14 输出: false 解释: 14 不是丑数，因为它包含了另外一个质因数 7。
说明：
1 是丑数。
输入不会超过 32 位有符号整数的范围: [−231, 231 − 1]。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(log(n)) |
O(log(n)) |
| 02 |
迭代 |
O(log(n)) |
O(1) |
func isUgly(num int) bool {
if num <= 0 {
return false
}
if num <= 6 {
return true
}
if num%2 == 0 {
return isUgly(num / 2)
}
if num%3 == 0 {
return isUgly(num / 3)
}
if num%5 == 0 {
return isUgly(num / 5)
}
return false
}
# 迭代
func isUgly(num int) bool {
if num <= 0 {
return false
}
for num != 1 {
if num%2 == 0 {
num = num / 2
} else if num%3 == 0 {
num = num / 3
} else if num%5 == 0 {
num = num / 5
} else {
return false
}
}
return true
}
268.缺失数字(5)
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
示例 1:输入: [3,0,1]输出: 2
示例 2:输入: [9,6,4,2,3,5,7,0,1] 输出: 8
说明:你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数学计算 |
O(n) |
O(1) |
| 02 |
排序遍历 |
O(nlog(n)) |
O(1) |
| 03 |
异或-位运算 |
O(n) |
O(1) |
| 04 |
交换排序(就地排序) |
O(n) |
O(1) |
| 05 |
哈希辅助 |
O(n) |
O(n) |
func missingNumber(nums []int) int {
n := len(nums)
sum := n * (n + 1) / 2
for i := 0; i < n; i++ {
sum = sum - nums[i]
}
return sum
}
# 2
func missingNumber(nums []int) int {
sort.Ints(nums)
for i := 0; i < len(nums); i++ {
if nums[i] != i {
return i
}
}
return len(nums)
}
# 3
func missingNumber(nums []int) int {
res := 0
for i := 0; i < len(nums); i++ {
res = res ^ (i+1) ^ nums[i]
}
return res
}
# 4
func missingNumber(nums []int) int {
n := len(nums)
index := n
for i := 0; i < n; {
if i == nums[i] {
i++
continue
}
if nums[i] == n {
index = i
i++
continue
}
nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
}
return index
}
# 5
func missingNumber(nums []int) int {
m := make(map[int]bool)
for i := range nums{
m[nums[i]] = true
}
for i := 0; i <= len(nums); i++{
if m[i] == false{
return i
}
}
return 0
}
278.第一个错误的版本(2)
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。
由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。
实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
给定 n = 5，并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
二分查找 |
O(log(n)) |
O(1) |
| 02 |
二分查找 |
O(log(n)) |
O(1) |
func firstBadVersion(n int) int {
low := 1
high := n
for low <= high {
mid := low + (high-low)/2
if isBadVersion(mid) == false {
low = mid + 1
} else if isBadVersion(mid) == true && isBadVersion(mid-1) == true {
high = mid - 1
} else if isBadVersion(mid) == true && isBadVersion(mid-1) == false {
return mid
}
}
return -1
}
#
func firstBadVersion(n int) int {
low := 1
high := n
for low < high {
mid := low + (high-low)/2
if isBadVersion(mid) {
high = mid
} else {
low = mid + 1
}
}
return low
}
283.移动零(3)
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
前移补零 |
O(n) |
O(1) |
| 02 |
遇零交换 |
O(n) |
O(1) |
| 03 |
数组辅助 |
O(n) |
O(n) |
func moveZeroes(nums []int) {
length := 0
for i := 0; i < len(nums); i++ {
if nums[i] != 0 {
nums[length] = nums[i]
length++
}
}
for i := length; i < len(nums); i++ {
nums[i] = 0
}
}
#
func moveZeroes(nums []int) {
length := 0
for i:= 0; i < len(nums); i++ {
nums[i], nums[length] = nums[length], nums[i]
if nums[length] != 0 {
length++
}
}
}
#
func moveZeroes(nums []int) {
arr := make([]int,len(nums))
count := 0
for i := range nums{
if nums[i] != 0{
arr[count] = nums[i]
count++
}
}
copy(nums, arr)
}
290.单词规律(2)
给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。
这里的 遵循 指完全匹配，
例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
示例1:输入: pattern = "abba", str = "dog cat cat dog"输出: true
示例 2:输入:pattern = "abba", str = "dog cat cat fish"输出: false
示例 3:输入: pattern = "aaaa", str = "dog cat cat dog"输出: false
示例 4:输入: pattern = "abba", str = "dog dog dog dog" 输出: false
说明:
你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双哈希相互映射 |
O(n) |
O(n) |
| 02 |
单哈希相互映射 |
O(n) |
O(n) |
func wordPattern(pattern string, str string) bool {
pa := strings.Split(pattern, "")
sa := strings.Split(str, " ")
if len(pa) != len(sa) {
return false
}
length := len(pa)
pMap := make(map[string]string, length)
sMap := make(map[string]string, length)
for i := 0; i < length; i++ {
pStr, ok := pMap[pa[i]]
sStr, ok1 := sMap[sa[i]]
if (ok && pStr != sa[i]) || (ok1 && sStr != pa[i]) {
return false
} else {
pMap[pa[i]] = sa[i]
sMap[sa[i]] = pa[i]
}
}
return true
}
#
func wordPattern(pattern string, str string) bool {
pa := strings.Split(pattern, "")
sa := strings.Split(str, " ")
if len(pa) != len(sa) {
return false
}
return isMatch(pa, sa) && isMatch(sa, pa)
}
func isMatch(pa, sa []string) bool {
length := len(pa)
m := make(map[string]string, length)
for i := 0; i < length; i++ {
if w, ok := m[pa[i]]; ok && w != sa[i] {
return false
} else {
m[pa[i]] = sa[i]
}
}
return true
}
292.Nim 游戏(1)
你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。
拿掉最后一块石头的人就是获胜者。你作为先手。
你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。
示例:
输入: 4
输出: false
解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；
因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
推理 |
O(1) |
O(1) |
func canWinNim(n int) bool {
return n%4 != 0
}
299.猜数字游戏(2)
你正在和你的朋友玩 猜数字（Bulls and Cows）游戏：你写下一个数字让你的朋友猜。
每次他猜测后，你给他一个提示，告诉他有多少位数字和确切位置都猜对了（称为“Bulls”, 公牛），
有多少位数字猜对了但是位置不对（称为“Cows”, 奶牛）。
你的朋友将会根据提示继续猜，直到猜出秘密数字。
请写出一个根据秘密数字和朋友的猜测数返回提示的函数，用 A 表示公牛，用 B 表示奶牛。
请注意秘密数字和朋友的猜测数都可能含有重复数字。
示例 1:输入: secret = "1807", guess = "7810"输出: "1A3B"
解释: 1 公牛和 3 奶牛。公牛是 8，奶牛是 0, 1 和 7。
示例 2:输入: secret = "1123", guess = "0111"输出: "1A1B"
解释: 朋友猜测数中的第一个 1 是公牛，第二个或第三个 1 可被视为奶牛。
说明: 你可以假设秘密数字和朋友的猜测数都只包含数字，并且它们的长度永远相等。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双哈希辅助 |
O(n) |
O(1) |
| 02 |
单哈希辅助 |
O(n) |
O(1) |
func getHint(secret string, guess string) string {
length := len(secret)
right := 0
wrongLoc := 0
m := make(map[byte]int)
n := make(map[byte]int)
for i := 0; i < length; i++ {
if secret[i] == guess[i] {
right++
} else {
m[secret[i]]++
n[guess[i]]++
}
}
for i := range m {
if m[i] < n[i] {
wrongLoc = wrongLoc + m[i]
} else {
wrongLoc = wrongLoc + n[i]
}
}
return fmt.Sprintf("%dA%dB", right, wrongLoc)
}
#
func getHint(secret string, guess string) string {
length := len(secret)
right := 0
wrongNum := 0
m := make(map[int]int)
for i := 0; i < length; i++ {
if secret[i] == guess[i] {
right++
}
m[int(secret[i]-'0')]++
m[int(guess[i]-'0')]--
}
for i := range m {
if m[i] > 0{
wrongNum = wrongNum + m[i]
}
}
wrongLoc := length - right - wrongNum
return fmt.Sprintf("%dA%dB", right, wrongLoc)
}
0201-0300-Medium
201.数字范围按位与(2)
给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。
示例 1: 输入: [5,7]输出: 4
示例 2:输入: [0,1]输出: 0
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
位运算 |
O(1) |
O(1) |
| 02 |
位运算 |
O(1) |
O(1) |
func rangeBitwiseAnd(m int, n int) int {
count := 0
for m != n {
count++
m = m >> 1
n = n >> 1
}
return m << count
}
# 2
func rangeBitwiseAnd(m int, n int) int {
for m < n {
n = n & (n - 1)
}
return n
}
207.课程表(2)
你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。
例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
示例 1:输入: 2, [[1,0]] 输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:输入: 2, [[1,0],[0,1]] 输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，
你还应先完成课程 1。这是不可能的。
提示：
输入的先决条件是由 边缘列表 表示的图形，而不是 邻接矩阵 。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
1 <= numCourses <= 10^5
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
深度优先搜索-判断环 |
O(n) |
O(n) |
| 02 |
广度优先搜索-拓扑排序 |
O(n) |
O(n) |
var res bool
var visited []int
var path []int
var edges [][]int
func canFinish(numCourses int, prerequisites [][]int) bool {
res = true
edges = make([][]int, numCourses)
visited = make([]int, numCourses)
path = make([]int, 0)
for i := 0; i < len(prerequisites); i++ {
prev := prerequisites[i][1]
cur := prerequisites[i][0]
edges[prev] = append(edges[prev], cur)
}
for i := 0; i < numCourses; i++ {
if visited[i] == 0 {
dfs(i)
}
if res == false {
return false
}
}
return res
}
func dfs(start int) {
visited[start] = 1
for i := 0; i < len(edges[start]); i++ {
out := edges[start][i]
if visited[out] == 0 {
dfs(out)
if res == false {
return
}
} else if visited[out] == 1 {
res = false
return
}
}
visited[start] = 2
path = append(path, start)
}
# 2
func canFinish(numCourses int, prerequisites [][]int) bool {
edges := make([][]int, numCourses)
path := make([]int, 0)
inEdges := make([]int, numCourses)
for i := 0; i < len(prerequisites); i++ {
prev := prerequisites[i][1]
cur := prerequisites[i][0]
edges[prev] = append(edges[prev], cur)
inEdges[cur]++
}
queue := make([]int, 0)
for i := 0; i < numCourses; i++ {
if inEdges[i] == 0 {
queue = append(queue, i)
}
}
for len(queue) > 0 {
start := queue[0]
queue = queue[1:]
path = append(path, start)
for i := 0; i < len(edges[start]); i++ {
out := edges[start][i]
inEdges[out]--
if inEdges[out] == 0 {
queue = append(queue, out)
}
}
}
return len(path) == numCourses
}
208.实现Trie(前缀树)(2)
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例:Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true
说明:你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
trie树 |
O(n) |
O(n) |
| 02 |
trie树 |
O(n) |
O(n) |
type Trie struct {
next [26]*Trie
ending int
}
func Constructor() Trie {
return Trie{
next: [26]*Trie{},
ending: 0,
}
}
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) Search(word string) bool {
temp := this
for _, v := range word {
value := v - 'a'
if temp = temp.next[value]; temp == nil {
return false
}
}
if temp.ending > 0 {
return true
}
return false
}
func (this *Trie) StartsWith(prefix string) bool {
temp := this
for _, v := range prefix {
value := v - 'a'
if temp = temp.next[value]; temp == nil {
return false
}
}
return true
}
# 2
type Trie struct {
next map[byte]*Trie
ending int
}
func Constructor() Trie {
return Trie{
next: make(map[byte]*Trie),
ending: 0,
}
}
func (this *Trie) Insert(word string) {
temp := this
for _, v := range word {
value := byte(v - 'a')
if temp.next[value] == nil {
temp.next[value] = &Trie{
next: make(map[byte]*Trie),
ending: 0,
}
}
temp = temp.next[value]
}
temp.ending++
}
func (this *Trie) Search(word string) bool {
temp := this
for _, v := range word {
value := byte(v - 'a')
if temp = temp.next[value]; temp == nil {
return false
}
}
if temp.ending > 0 {
return true
}
return false
}
func (this *Trie) StartsWith(prefix string) bool {
temp := this
for _, v := range prefix {
value := byte(v - 'a')
if temp = temp.next[value]; temp == nil {
return false
}
}
return true
}
209.长度最小的子数组(3)
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，
并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：输入：s = 7, nums = [2,3,1,2,4,3] 输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
进阶：如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n^2) |
O(1) |
| 02 |
前缀和-二分查找 |
O(nlog(n)) |
O(n) |
| 03 |
双指针 |
O(n) |
O(1) |
func minSubArrayLen(target int, nums []int) int {
res := math.MaxInt32
for i := 0; i < len(nums); i++ {
sum := 0
for j := i; j < len(nums); j++ {
sum = sum + nums[j]
if sum >= target {
if res > j-i+1 {
res = j - i + 1
}
break
}
}
}
if res == math.MaxInt32 {
return 0
}
return res
}
# 2
func minSubArrayLen(target int, nums []int) int {
res := math.MaxInt32
arr := make([]int, len(nums)+1)
for i := 1; i <= len(nums); i++ {
arr[i] = arr[i-1] + nums[i-1]
}
for i := 1; i <= len(nums); i++ {
target := target + arr[i-1]
index := sort.SearchInts(arr, target)
if index <= len(nums) {
if res > index-i+1 {
res = index - i + 1
}
}
}
if res == math.MaxInt32 {
return 0
}
return res
}
# 3
func minSubArrayLen(s int, nums []int) int {
res := math.MaxInt32
i, j := 0, 0
sum := 0
for ; j < len(nums); j++ {
sum = sum + nums[j]
for sum >= s {
if res > j-i+1 {
res = j - i + 1
}
sum = sum - nums[i]
i++
}
}
if res == math.MaxInt32 {
return 0
}
return res
}
210.课程表II(2)
现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。
例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
示例 1:输入: 2, [[1,0]] 输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2:输入: 4, [[1,0],[2,0],[3,1],[3,2]] 输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。
并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
说明:输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
提示:
这个问题相当于查找一个循环是否存在于有向图中。
如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
拓扑排序也可以通过 BFS 完成。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
深度优先搜索 |
O(n) |
O(n) |
| 02 |
广度优先搜索-拓扑排序 |
O(n) |
O(n) |
var res bool
var visited []int
var path []int
var edges [][]int
func findOrder(numCourses int, prerequisites [][]int) []int {
res = true
edges = make([][]int, numCourses)
visited = make([]int, numCourses)
path = make([]int, 0)
for i := 0; i < len(prerequisites); i++ {
prev := prerequisites[i][1]
cur := prerequisites[i][0]
edges[prev] = append(edges[prev], cur)
}
for i := 0; i < numCourses; i++ {
if visited[i] == 0 {
dfs(i)
}
if res == false {
return nil
}
}
for i := 0; i < len(path)/2; i++ {
path[i], path[len(path)-1-i] = path[len(path)-1-i], path[i]
}
return path
}
func dfs(start int) {
visited[start] = 1
for i := 0; i < len(edges[start]); i++ {
out := edges[start][i]
if visited[out] == 0 {
dfs(out)
if res == false {
return
}
} else if visited[out] == 1 {
res = false
return
}
}
visited[start] = 2
path = append(path, start)
}
# 2
func findOrder(numCourses int, prerequisites [][]int) []int {
edges := make([][]int, numCourses)
path := make([]int, 0)
inEdges := make([]int, numCourses)
for i := 0; i < len(prerequisites); i++ {
prev := prerequisites[i][1]
cur := prerequisites[i][0]
edges[prev] = append(edges[prev], cur)
inEdges[cur]++
}
queue := make([]int, 0)
for i := 0; i < numCourses; i++ {
if inEdges[i] == 0 {
queue = append(queue, i)
}
}
for len(queue) > 0 {
start := queue[0]
queue = queue[1:]
path = append(path, start)
for i := 0; i < len(edges[start]); i++ {
out := edges[start][i]
inEdges[out]--
if inEdges[out] == 0 {
queue = append(queue, out)
}
}
}
if len(path) != numCourses {
return nil
}
return path
}
211.添加与搜索单词-数据结构设计(1)
如果数据结构中有任何与word匹配的字符串，则bool search（word）返回true，否则返回false。
单词可能包含点“。” 点可以与任何字母匹配的地方。
请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
实现词典类 WordDictionary ：
WordDictionary() 初始化词典对象
void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；
否则，返回 false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。
示例：输入：
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
输出：[null,null,null,null,false,true,true,true]
解释：
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True
提示：1 <= word.length <= 500
addWord 中的 word 由小写英文字母组成
search 中的 word 由 '.' 或小写英文字母组成
最调用多 50000 次 addWord 和 search
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
trie树 |
O(n) |
O(n) |
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) Search(word string, k int) bool {
temp := this
for i := k; i < len(word); i++ {
if word[i] == '.' {
for j := 0; j < len(temp.next); j++ {
if temp.next[j] != nil && temp.next[j].Search(word, i+1) {
return true
}
}
return false
}
value := word[i] - 'a'
if temp = temp.next[value]; temp == nil {
return false
}
}
if temp.ending > 0 {
return true
}
return false
}
type WordDictionary struct {
trie *Trie
}
func Constructor() WordDictionary {
return WordDictionary{trie: &Trie{}}
}
func (this *WordDictionary) AddWord(word string) {
this.trie.Insert(word)
}
func (this *WordDictionary) Search(word string) bool {
return this.trie.Search(word, 0)
}
213.打家劫舍II(3)
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。
这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。
同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:输入: [2,3,2] 输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2:输入: [1,2,3,1] 输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n) |
O(n) |
| 02 |
动态规划 |
O(n) |
O(n) |
| 03 |
动态规划 |
O(n) |
O(1) |
func rob(nums []int) int {
n := len(nums)
if n == 0 {
return 0
} else if n == 1 {
return nums[0]
}
dp1 := make([]int, n)
dp2 := make([]int, n)
dp1[0] = nums[0]
dp1[1] = max(nums[0], nums[1])
dp2[0] = 0
dp2[1] = nums[1]
for i := 2; i < n; i++ {
dp1[i] = max(dp1[i-1], dp1[i-2]+nums[i])
dp2[i] = max(dp2[i-1], dp2[i-2]+nums[i])
}
return max(dp1[n-2], dp2[n-1])
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func rob(nums []int) int {
n := len(nums)
if n == 0 {
return 0
} else if n == 1 {
return nums[0]
} else if n == 2 {
return max(nums[0], nums[1])
}
return max(getMax(nums[:n-1]), getMax(nums[1:]))
}
func getMax(nums []int) int {
n := len(nums)
dp := make([]int, n+1)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i := 2; i < n; i++ {
dp[i] = max(dp[i-1], dp[i-2]+nums[i])
}
return dp[n-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 3
func rob(nums []int) int {
n := len(nums)
if n == 0 {
return 0
} else if n == 1 {
return nums[0]
} else if n == 2 {
return max(nums[0], nums[1])
}
return max(getMax(nums[:n-1]), getMax(nums[1:]))
}
func getMax(nums []int) int {
var a, b int
for i, v := range nums {
if i%2 == 0 {
a = max(a+v, b)
} else {
b = max(a, b+v)
}
}
return max(a, b)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
215.数组中的第K个最大元素(3)
在未排序的数组中找到第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:输入: [3,2,1,5,6,4] 和 k = 2 输出: 5
示例 2:输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4
说明:你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序 |
O(nlog(n)) |
O(1) |
| 02 |
堆排序 |
O(nlog(n)) |
O(log(n)) |
| 03 |
快排 |
O(n) |
O(log(n)) |
func findKthLargest(nums []int, k int) int {
sort.Ints(nums)
return nums[len(nums)-k]
}
# 2
func findKthLargest(nums []int, k int) int {
heapSize := len(nums)
buildMaxHeap(nums, heapSize)
for i := len(nums) - 1; i >= len(nums)-k+1; i-- {
nums[0], nums[i] = nums[i], nums[0]
heapSize--
maxHeapify(nums, 0, heapSize)
}
return nums[0]
}
func buildMaxHeap(a []int, heapSize int) {
for i := heapSize / 2; i >= 0; i-- {
maxHeapify(a, i, heapSize)
}
}
func maxHeapify(a []int, i, heapSize int) {
l, r, largest := i*2+1, i*2+2, i
if l < heapSize && a[l] > a[largest] {
largest = l
}
if r < heapSize && a[r] > a[largest] {
largest = r
}
if largest != i {
a[i], a[largest] = a[largest], a[i]
maxHeapify(a, largest, heapSize)
}
}
# 3
func findKthLargest(nums []int, k int) int {
return findK(nums, 0, len(nums)-1, k)
}
func findK(nums []int, start, end int, k int) int {
if start >= end {
return nums[end]
}
index := partition(nums, start, end)
if index+1 == k {
return nums[index]
} else if index+1 < k {
return findK(nums, index+1, end, k)
}
return findK(nums, start, index-1, k)
}
func partition(nums []int, start, end int) int {
temp := nums[end]
i := start
for j := start; j < end; j++ {
if nums[j] > temp {
if i != j {
nums[i], nums[j] = nums[j], nums[i]
}
i++
}
}
nums[i], nums[end] = nums[end], nums[i]
return i
}
216.组合总和III(1)
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:输入: k = 3, n = 7 输出: [[1,2,4]]
示例 2:输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
回溯算法 |
O(n*C(9,n)) |
O(n) |
var res [][]int
func combinationSum3(k int, n int) [][]int {
res = make([][]int, 0)
arr := make([]int, 0)
dfs(k, n, 1, arr)
return res
}
func dfs(k, n int, level int, arr []int) {
if k == 0 || n < 0 {
if n == 0 {
temp := make([]int, len(arr))
copy(temp, arr)
res = append(res, temp)
}
return
}
for i := level; i <= 9; i++ {
dfs(k-1, n-i, i+1, append(arr, i))
}
}
220.存在重复元素III(2)
在整数数组 nums 中，是否存在两个下标 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t ，
且满足 i 和 j 的差的绝对值也小于等于 ķ 。
如果存在则返回 true，不存在返回 false。
示例 1:输入: nums = [1,2,3,1], k = 3, t = 0 输出: true
示例 2:输入: nums = [1,0,1,1], k = 1, t = 2 输出: true
示例 3:输入: nums = [1,5,9,1,5,9], k = 2, t = 3 输出: false
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n^2) |
O(1) |
| 02 |
桶 |
O(n) |
O(n) |
func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
if len(nums) <= 1 {
return false
}
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums) && j <= i+k; j++ {
if abs(nums[i], nums[j]) <= t {
return true
}
}
}
return false
}
# 2
func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
if len(nums) <= 1 || t < 0 {
return false
}
m := make(map[int]int)
width := t + 1
for i := 0; i < len(nums); i++ {
key := getKey(nums[i], width)
if _, ok := m[key]; ok {
return true
}
if value, ok := m[key-1]; ok && abs(nums[i], value) < width {
return true
}
if value, ok := m[key+1]; ok && abs(nums[i], value) < width {
return true
}
m[key] = nums[i]
if i >= k {
delete(m, getKey(nums[i-k], width))
}
}
return false
}
func getKey(value, width int) int {
if value < 0 {
return (value+1)/width - 1
}
return value / width
}
func abs(a, b int) int {
if a > b {
return a - b
}
return b - a
}
221.最大正方形(3)
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
示例:输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n^4) |
O(1) |
| 02 |
动态规划 |
O(n^2) |
O(n^2) |
| 03 |
动态规划 |
O(n^2) |
O(1) |
func maximalSquare(matrix [][]byte) int {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return 0
}
res := 0
n, m := len(matrix), len(matrix[0])
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if matrix[i][j] == '1' {
res = max(res, 1)
minLength := min(n-i, m-j)
for k := 1; k < minLength; k++ {
flag := true
if matrix[i+k][j+k] == '0' {
break
}
for l := 0; l < k; l++ {
if matrix[i+k][j+l] == '0' || matrix[i+l][j+k] == '0' {
flag = false
break
}
}
if flag == true {
res = max(res, k+1)
} else {
break
}
}
}
}
}
return res * res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
func maximalSquare(matrix [][]byte) int {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return 0
}
res := 0
n, m := len(matrix), len(matrix[0])
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, m)
for j := 0; j < m; j++ {
dp[i][j] = int(matrix[i][j] - '0')
if dp[i][j] == 1 {
res = 1
}
}
}
for i := 1; i < n; i++ {
for j := 1; j < m; j++ {
if dp[i][j] == 1 {
dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1
res = max(res, dp[i][j])
}
}
}
return res * res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 3
func maximalSquare(matrix [][]byte) int {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return 0
}
res := 0
n, m := len(matrix), len(matrix[0])
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if matrix[i][j] == '1' {
res = max(res, int(matrix[i][j]-'0'))
}
if i == 0 || j == 0 {
continue
}
if matrix[i][j] == '1' {
a := int(matrix[i-1][j-1] - '0')
b := int(matrix[i-1][j] - '0')
c := int(matrix[i][j-1] - '0')
matrix[i][j] = byte(min(a, min(b, c)) + 1 + '0')
res = max(res, int(matrix[i][j]-'0'))
}
}
}
return res * res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
222.完全二叉树的节点个数(3)
给出一个完全二叉树，求出该树的节点个数。
说明：
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，
并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例:输入:
1
/ \
2 3
/ \ /
4 5 6
输出: 6
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(log(n)) |
| 02 |
迭代 |
O(n) |
O(n) |
| 03 |
递归 |
O(log(n)^2) |
O(log(n)) |
func countNodes(root *TreeNode) int {
if root == nil {
return 0
}
return 1 + countNodes(root.Left) + countNodes(root.Right)
}
# 2
func countNodes(root *TreeNode) int {
if root == nil {
return 0
}
res := 0
queue := make([]*TreeNode, 0)
queue = append(queue, root)
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
res++
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
return res
}
# 3
func countNodes(root *TreeNode) int {
if root == nil {
return 0
}
left := getLevel(root.Left)
right := getLevel(root.Right)
if left == right{
return 1<<left+countNodes(root.Right)
}
return countNodes(root.Left) + 1<<right
}
func getLevel(root *TreeNode)int {
level := 0
for root != nil{
level++
root = root.Left
}
return level
}
223.矩形面积(1)
在二维平面上计算出两个由直线构成的矩形重叠后形成的总面积。
每个矩形由其左下顶点和右上顶点坐标表示，如图所示。
示例:输入: -3, 0, 3, 4, 0, -1, 9, 2 输出: 45
说明: 假设矩形面积不会超出 int 的范围。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数学计算 |
O(1) |
O(1) |
func computeArea(A int, B int, C int, D int, E int, F int, G int, H int) int {
left, right := max(A, E), min(C, G)
bottom, top := max(B, F), min(D, H)
area1, area2 := (C-A)*(D-B), (G-E)*(H-F)
if left < right && bottom < top {
return area1 + area2 - (right-left)*(top-bottom)
}
return area1 + area2
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
227.基本计算器II(2)
实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。
示例 1:输入: "3+2*2" 输出: 7
示例 2:输入: " 3/2 " 输出: 1
示例 3:输入: " 3+5 / 2 " 输出: 5
说明：
你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
栈辅助 |
O(n) |
O(n) |
| 02 |
栈辅助 |
O(n) |
O(n) |
func calculate(s string) int {
stack := make([]int, 0)
op := make([]int, 0)
num := 0
for i := 0; i < len(s); i++ {
if '0' <= s[i] && s[i] <= '9' {
num = 0
for i < len(s) && '0' <= s[i] && s[i] <= '9' {
num = num*10 + int(s[i]-'0')
i++
}
if len(op) > 0 && op[len(op)-1] > 1 {
if op[len(op)-1] == 2 {
stack[len(stack)-1] = stack[len(stack)-1] * num
} else {
stack[len(stack)-1] = stack[len(stack)-1] / num
}
op = op[:len(op)-1]
} else {
stack = append(stack, num)
}
i--
} else if s[i] == '+' {
op = append(op, 1)
} else if s[i] == '-' {
op = append(op, -1)
} else if s[i] == '*' {
op = append(op, 2)
} else if s[i] == '/' {
op = append(op, 3)
}
}
for len(op) > 0 {
stack[1] = stack[0] + stack[1]*op[0]
stack = stack[1:]
op = op[1:]
}
return stack[0]
}
# 2
func calculate(s string) int {
s = strings.Trim(s, " ")
stack := make([]int, 0)
num := 0
sign := byte('+')
for i := 0; i < len(s); i++ {
if s[i] == ' ' {
continue
}
if '0' <= s[i] && s[i] <= '9' {
num = num*10 + int(s[i]-'0')
}
if s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || i == len(s)-1 {
switch sign {
case '+':
stack = append(stack, num)
case '-':
stack = append(stack, -num)
case '*':
prev := stack[len(stack)-1]
stack = stack[:len(stack)-1]
stack = append(stack, num*prev)
case '/':
prev := stack[len(stack)-1]
stack = stack[:len(stack)-1]
stack = append(stack, prev/num)
}
num = 0
sign = s[i]
}
}
res := 0
for i := 0; i < len(stack); i++ {
res = res + stack[i]
}
return res
}
228.汇总区间(2)
给定一个无重复元素的有序整数数组，返回数组区间范围的汇总。
示例 1:输入: [0,1,2,4,5,7]输出: ["0->2","4->5","7"]
解释: 0,1,2 可组成一个连续的区间; 4,5 可组成一个连续的区间。
示例 2:输入: [0,2,3,4,6,8,9]输出: ["0","2->4","6","8->9"]
解释: 2,3,4 可组成一个连续的区间; 8,9 可组成一个连续的区间。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双指针 |
O(n) |
O(n) |
| 02 |
双指针 |
O(n) |
O(n) |
func summaryRanges(nums []int) []string {
res := make([]string, 0)
if len(nums) == 0 {
return res
}
i, j := 0, 1
for j < len(nums) {
if nums[j]-nums[j-1] != 1 {
str := ""
if j-i > 1 {
str = strconv.Itoa(nums[i]) + "->" + strconv.Itoa(nums[j-1])
} else {
str = strconv.Itoa(nums[i])
}
res = append(res, str)
i = j
}
j++
}
if j == len(nums) {
str := ""
if j-i > 1 {
str = strconv.Itoa(nums[i]) + "->" + strconv.Itoa(nums[j-1])
} else {
str = strconv.Itoa(nums[i])
}
res = append(res, str)
}
return res
}
# 2
func summaryRanges(nums []int) []string {
res := make([]string, 0)
if len(nums) == 0 {
return res
}
nums = append(nums, nums[0])
i, j := 0, 1
index := 0
res = append(res, strconv.Itoa(nums[i]))
for j = 1; j < len(nums); j++ {
if nums[j]-nums[j-1] != 1 {
if j-i > 1 {
str := strconv.Itoa(nums[i]) + "->" + strconv.Itoa(nums[j-1])
res[index] = str
}
res = append(res, strconv.Itoa(nums[j]))
i = j
index++
}
}
return res[:index]
}
229.求众数II(2)
给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。
示例 1:输入: [3,2,3] 输出: [3]
示例 2:输入: [1,1,1,3,3,2,2,2] 输出: [1,2]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n) |
O(n) |
| 02 |
摩尔投票法 |
O(n) |
O(1) |
func majorityElement(nums []int) []int {
m := make(map[int]int)
res := make([]int, 0)
for i := 0; i < len(nums); i++ {
m[nums[i]]++
}
for k, v := range m {
if v > len(nums)/3 {
res = append(res, k)
}
}
return res
}
# 2
func majorityElement(nums []int) []int {
res := make([]int, 0)
if len(nums) == 0 {
return res
}
a, b := nums[0], nums[0]
countA, countB := 0, 0
for i := 0; i < len(nums); i++ {
if nums[i] == a {
countA++
continue
}
if nums[i] == b {
countB++
continue
}
if countA == 0 {
a = nums[i]
countA++
continue
}
if countB == 0 {
b = nums[i]
countB++
continue
}
countA--
countB--
}
countA, countB = 0, 0
for i := 0; i < len(nums); i++ {
if nums[i] == a {
countA++
} else if nums[i] == b {
countB++
}
}
if countA > len(nums)/3 {
res = append(res, a)
}
if countB > len(nums)/3 {
res = append(res, b)
}
return res
}
230.二叉搜索树中第K小的元素(3)
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 1
示例 2:输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 3
进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，
你将如何优化 kthSmallest 函数？
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(log(n)) |
| 02 |
迭代 |
O(n) |
O(n) |
| 03 |
递归 |
O(n) |
O(n) |
var res int
var index int
func kthSmallest(root *TreeNode, k int) int {
res = 0
index = k
dfs(root)
return res
}
func dfs(root *TreeNode) {
if root != nil {
dfs(root.Left)
index--
if index == 0 {
res = root.Val
return
}
dfs(root.Right)
}
}
# 2
func kthSmallest(root *TreeNode, k int) int {
res := 0
stack := make([]*TreeNode, 0)
for k > 0 {
for root != nil {
stack = append(stack, root)
root = root.Left
}
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
res = root.Val
k--
root = root.Right
}
return res
}
# 3
var res []int
func kthSmallest(root *TreeNode, k int) int {
res = make([]int, 0)
dfs(root)
return res[k-1]
}
func dfs(root *TreeNode) {
if root != nil {
dfs(root.Left)
res = append(res, root.Val)
dfs(root.Right)
}
}
236.二叉树的最近公共祖先(2)
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，
满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:所有节点的值都是唯一的。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(log(n)) |
| 02 |
递归 |
O(n) |
O(n) |
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil {
return nil
}
if root.Val == p.Val || root.Val == q.Val {
return root
}
left := lowestCommonAncestor(root.Left, p, q)
right := lowestCommonAncestor(root.Right, p, q)
if left != nil && right != nil {
return root
}
if left == nil {
return right
}
return left
}
# 2
var m map[int]*TreeNode
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil {
return nil
}
m = make(map[int]*TreeNode)
dfs(root)
visited := make(map[int]bool)
for p != nil {
visited[p.Val] = true
p = m[p.Val]
}
for q != nil {
if visited[q.Val] == true {
return q
}
q = m[q.Val]
}
return nil
}
func dfs(root *TreeNode) {
if root == nil {
return
}
if root.Left != nil {
m[root.Left.Val] = root
dfs(root.Left)
}
if root.Right != nil {
m[root.Right.Val] = root
dfs(root.Right)
}
}
238.除自身以外数组的乘积(3)
给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，
其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:输入: [1,2,3,4] 输出: [24,12,8,6]
提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
进阶：你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数组辅助 |
O(n) |
O(n) |
| 02 |
暴力法 |
O(n^2) |
O(n) |
| 03 |
遍历 |
O(n) |
O(n) |
func productExceptSelf(nums []int) []int {
left := make([]int, len(nums))
right := make([]int, len(nums))
res := make([]int, 0)
left[0] = 1
right[len(nums)-1] = 1
for i := 1; i < len(nums); i++ {
left[i] = left[i-1] * nums[i-1]
}
for i := len(nums) - 2; i >= 0; i-- {
right[i] = right[i+1] * nums[i+1]
}
for i := 0; i < len(nums); i++ {
res = append(res, left[i]*right[i])
}
return res
}
# 2
func productExceptSelf(nums []int) []int {
res := make([]int, 0)
for i := 0; i < len(nums); i++ {
value := 1
for j := 0; j < len(nums); j++ {
if i != j {
value = value * nums[j]
}
}
res = append(res, value)
}
return res
}
# 3
func productExceptSelf(nums []int) []int {
res := make([]int, len(nums))
res[0] = 1
for i := 1; i < len(nums); i++ {
res[i] = res[i-1] * nums[i-1]
}
value := 1
for i := len(nums) - 1; i >= 0; i-- {
res[i] = res[i] * value
value = value * nums[i]
}
return res
}
240.搜索二维矩阵II(6)
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例:现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n^2) |
O(1) |
| 02 |
暴力法-优化 |
O(n^2) |
O(1) |
| 03 |
二分查找 |
O(nlog(n)) |
O(1) |
| 04 |
左下角查找 |
O(n) |
O(1) |
| 05 |
右上角查找 |
O(n) |
O(1) |
| 06 |
内置函数 |
O(n^2) |
O(1) |
func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 {
return false
}
if len(matrix[0]) == 0 {
return false
}
for i := 0; i < len(matrix); i++ {
for j := 0; j < len(matrix[i]); j++ {
if matrix[i][j] == target {
return true
}
}
}
return false
}
# 2
func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 {
return false
}
if len(matrix[0]) == 0 {
return false
}
for i := 0; i < len(matrix); i++ {
if matrix[i][0] <= target && matrix[i][len(matrix[i])-1] >= target {
for j := 0; j < len(matrix[i]); j++ {
if matrix[i][j] == target {
return true
}
}
}
}
return false
}
# 3
func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 {
return false
}
if len(matrix[0]) == 0 {
return false
}
for i := 0; i < len(matrix); i++ {
if matrix[i][0] <= target && matrix[i][len(matrix[i])-1] >= target {
res := binarySearch(matrix[i], target)
if res == true {
return true
}
}
}
return false
}
func binarySearch(arr []int, target int) bool {
left := 0
right := len(arr) - 1
for left <= right {
mid := left + (right-left)/2
if arr[mid] == target {
return true
} else if arr[mid] > target {
right = mid - 1
} else {
left = mid + 1
}
}
return false
}
# 4
func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 {
return false
}
if len(matrix[0]) == 0 {
return false
}
i := len(matrix) - 1
j := 0
for i >= 0 && j < len(matrix[0]) {
if matrix[i][j] == target {
return true
} else if matrix[i][j] > target {
i--
} else {
j++
}
}
return false
}
# 5
func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 {
return false
}
if len(matrix[0]) == 0 {
return false
}
i := 0
j := len(matrix[0]) - 1
for j >= 0 && i < len(matrix) {
if matrix[i][j] == target {
return true
} else if matrix[i][j] > target {
j--
} else {
i++
}
}
return false
}
# 6
func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 {
return false
}
if len(matrix[0]) == 0 {
return false
}
for i := 0; i < len(matrix); i++ {
index := sort.SearchInts(matrix[i], target)
if index < len(matrix[i]) && target == matrix[i][index] {
return true
}
}
return false
}
241.为运算表达式设计优先级(2)
给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。
你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。
示例 1:输入: "2-1-1" 输出: [0, 2]
解释:
((2-1)-1) = 0
(2-(1-1)) = 2
示例 2:输入: "2*3-4*5" 输出: [-34, -14, -10, -10, 10]
解释:
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
分治递归 |
O(C(2n,n)/(n+1)) |
O(C(2n,n)/(n+1)) |
| 02 |
动态规划 |
O(n^3) |
O(n^3) |
func diffWaysToCompute(input string) []int {
if value, err := strconv.Atoi(input); err == nil {
return []int{value}
}
res := make([]int, 0)
for i := 0; i < len(input); i++ {
char := string(input[i])
if char == "+" || char == "-" || char == "*" {
left := diffWaysToCompute(input[:i])
right := diffWaysToCompute(input[i+1:])
for _, leftNum := range left {
for _, rightNum := range right {
temp := 0
if char == "+" {
temp = leftNum + rightNum
} else if char == "-" {
temp = leftNum - rightNum
} else if char == "*" {
temp = leftNum * rightNum
}
res = append(res, temp)
}
}
}
}
return res
}
# 2
func diffWaysToCompute(input string) []int {
if value, err := strconv.Atoi(input); err == nil {
return []int{value}
}
numArr := make([]int, 0)
opArr := make([]byte, 0)
num := 0
for i := 0; i < len(input); i++ {
if input[i] == '+' || input[i] == '-' || input[i] == '*' {
opArr = append(opArr, input[i])
numArr = append(numArr, num)
num = 0
continue
}
num = num*10 + int(input[i]-'0')
}
numArr = append(numArr, num)
n := len(numArr)
dp := make([][][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([][]int, n)
arr := make([]int, 0)
arr = append(arr, numArr[i])
dp[i][i] = arr
}
for k := 2; k <= n; k++ {
for i := 0; i < n; i++ {
j := i + k - 1
if j >= n {
break
}
temp := make([]int, 0)
for l := i; l < j; l++ {
left := dp[i][l]
right := dp[l+1][j]
for a := 0; a < len(left); a++ {
for b := 0; b < len(right); b++ {
op := opArr[l]
if op == '+' {
temp = append(temp, left[a]+right[b])
} else if op == '-' {
temp = append(temp, left[a]-right[b])
} else if op == '*' {
temp = append(temp, left[a]*right[b])
}
}
}
}
dp[i][j] = temp
}
}
return dp[0][n-1]
}
260.只出现一次的数字III(3)
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
示例 :
输入: [1,2,1,3,2,5]
输出: [3,5]
注意：
结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n) |
O(n) |
| 02 |
位运算 |
O(n) |
O(1) |
| 03 |
位运算 |
O(n) |
O(1) |
func singleNumber(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 == 1 {
res = append(res, k)
}
}
return res
}
# 2
func singleNumber(nums []int) []int {
a := 0
for i := 0; i < len(nums); i++ {
a = a ^ nums[i]
}
b := a & (-a)
value := 0
for i := 0; i < len(nums); i++ {
if nums[i]&b == 0 {
value = value ^ nums[i]
}
}
return []int{value, a ^ value}
}
# 3
func singleNumber(nums []int) []int {
a := 0
for i := 0; i < len(nums); i++ {
a = a ^ nums[i]
}
b := 1
for a&1 == 0 {
a = a >> 1
b = b << 1
}
res := []int{0, 0}
for i := 0; i < len(nums); i++ {
if nums[i]&b == 0 {
res[0] = res[0] ^ nums[i]
} else {
res[1] = res[1] ^ nums[i]
}
}
return res
}
264.丑数II(1)
编写一个程序，找出第 n 个丑数。
丑数就是质因数只包含 2, 3, 5 的正整数。
示例:输入: n = 10 输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1 是丑数。
n 不超过1690。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n) |
O(n) |
func nthUglyNumber(n int) int {
dp := make([]int, n)
dp[0] = 1
idx2, idx3, idx5 := 0, 0, 0
for i := 1; i < n; i++ {
dp[i] = min(dp[idx2]*2, min(dp[idx3]*3, dp[idx5]*5))
if dp[i] == dp[idx2]*2 {
idx2++
}
if dp[i] == dp[idx3]*3 {
idx3++
}
if dp[i] == dp[idx5]*5 {
idx5++
}
}
return dp[n-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
274.H指数(2)
给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。
h 指数的定义：h 代表“高引用次数”（high citations），
一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。
（其余的 N - h 篇论文每篇被引用次数 不超过 h 次。）
例如：某人的 h 指数是 20，这表示他已发表的论文中，每篇被引用了至少 20 次的论文总共有 20 篇。
示例：输入：citations = [3,0,6,1,5]输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，
所以她的 h 指数是 3。
提示：如果 h 有多种可能的值，h 指数是其中最大的那个。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序 |
O(nlog(n)) |
O(1) |
| 02 |
计数 |
O(n) |
O(n) |
func hIndex(citations []int) int {
sort.Ints(citations)
for i := 0; i < len(citations); i++ {
if citations[i] >= len(citations)-i {
return len(citations) - i
}
}
return 0
}
#
func hIndex(citations []int) int {
arr := make([]int, len(citations)+1)
for i := 0; i < len(citations); i++ {
if citations[i] >= len(citations) {
arr[len(citations)]++
} else {
arr[citations[i]]++
}
}
count := 0
for i := len(citations); i >= 0; i-- {
count = count + arr[i]
if count >= i {
return i
}
}
return 0
}
275.H指数II(2)
给定一位研究者论文被引用次数的数组（被引用次数是非负整数），数组已经按照升序排列。
编写一个方法，计算出研究者的 h 指数。
h 指数的定义: “h 代表“高引用次数”（high citations），
一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。
（其余的 N - h 篇论文每篇被引用次数不多于 h 次。）"
示例:输入: citations = [0,1,3,5,6] 输出: 3
解释: 给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 0, 1, 3, 5, 6 次。
由于研究者有 3 篇论文每篇至少被引用了 3 次，其余两篇论文每篇被引用不多于 3 次，
所以她的 h 指数是 3。
说明:如果 h 有多有种可能的值 ，h 指数是其中最大的那个。
进阶：
这是 H指数 的延伸题目，本题中的 citations 数组是保证有序的。
你可以优化你的算法到对数时间复杂度吗？
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
二分查找 |
O(log(n)) |
O(1) |
func hIndex(citations []int) int {
for i := 0; i < len(citations); i++ {
if citations[i] >= len(citations)-i {
return len(citations) - i
}
}
return 0
}
#
func hIndex(citations []int) int {
left := 0
right := len(citations) - 1
for left <= right {
mid := left + (right-left)/2
if citations[mid] == len(citations)-mid {
return len(citations) - mid
} else if citations[mid] > len(citations)-mid {
right = mid - 1
} else if citations[mid] < len(citations)-mid {
left = mid + 1
}
}
return len(citations) - left
}
279.完全平方数(5)
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。
你需要让组成和的完全平方数的个数最少。
示例 1:输入: n = 12 输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:输入: n = 13 输出: 2
解释: 13 = 4 + 9.
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^(3/2)) |
O(n) |
| 02 |
动态规划 |
O(n^(3/2)) |
O(n) |
| 03 |
广度优先搜索 |
O(n^1/2) |
O(n^1/2) |
| 04 |
递归 |
O(n^1/2) |
O(n^1/2) |
| 05 |
数学 |
O(n^1/2) |
O(1) |
func numSquares(n int) int {
dp := make([]int, n+1)
for i := 1; i <= n; i++ {
dp[i] = math.MaxInt32
}
arr := make([]int, 0)
arr = append(arr, 0)
for i := 1; i*i <= n; i++ {
arr = append(arr, i*i)
}
for i := 1; i <= n; i++ {
for j := 1; j*j <= i; j++ {
if i < arr[j] {
break
}
dp[i] = min(dp[i], dp[i-arr[j]]+1)
}
}
return dp[n]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
#
func numSquares(n int) int {
dp := make([]int, n+1)
for i := 1; i <= n; i++ {
dp[i] = i
for j := 1; j*j <= i; j++ {
dp[i] = min(dp[i], dp[i-j*j]+1)
}
}
return dp[n]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 3
func numSquares(n int) int {
if n == 0 {
return 0
}
list := make([]int, 0)
list = append(list, n)
level := 0
for len(list) > 0 {
level++
length := len(list)
for i := 0; i < length; i++ {
value := list[i]
for j := 1; j*j <= value; j++ {
if j*j == value {
return level
}
list = append(list, value-j*j)
}
}
list = list[length:]
}
return level
}
# 4
var m map[int]int
func numSquares(n int) int {
m = make(map[int]int)
return dfs(n)
}
func dfs(n int) int {
if m[n] > 0 {
return m[n]
}
if n == 0 {
return 0
}
count := math.MaxInt32
for i := 1; i*i <= n; i++ {
count = min(count, dfs(n-i*i)+1)
}
return count
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 5
func numSquares(n int) int {
if judge(n) {
return 1
}
res := n
for res%4 == 0 {
res = res / 4
}
if res%8 == 7 {
return 4
}
for i := 1; i*i < n; i++ {
if judge(n - i*i) {
return 2
}
}
return 3
}
func judge(n int) bool {
value := int(math.Sqrt(float64(n)))
return value*value == n
}
284.顶端迭代器(2)
给定一个迭代器类的接口，接口包含两个方法： next() 和 hasNext()。
设计并实现一个支持 peek() 操作的顶端迭代器 -- 其本质就是把原本应由 next() 方法返回的元素 peek() 出来。
示例:假设迭代器被初始化为列表 [1,2,3]。
调用 next() 返回 1，得到列表中的第一个元素。
现在调用 peek() 返回 2，下一个元素。在此之后调用 next() 仍然返回 2。
最后一次调用 next() 返回 3，末尾元素。在此之后调用 hasNext() 应该返回 false。
进阶：你将如何拓展你的设计？使之变得通用化，从而适应所有的类型，而不只是整数型？
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
缓存 |
O(1) |
O(1) |
| 02 |
缓存 |
O(1) |
O(1) |
type PeekingIterator struct {
Iter *Iterator
cache int
isCache bool
}
func Constructor(iter *Iterator) *PeekingIterator {
return &PeekingIterator{
Iter: iter,
cache: 0,
isCache: false,
}
}
func (this *PeekingIterator) hasNext() bool {
return this.isCache || this.Iter.hasNext()
}
func (this *PeekingIterator) next() int {
if this.isCache == false {
return this.Iter.next()
}
res := this.cache
this.isCache = false
return res
}
func (this *PeekingIterator) peek() int {
if this.isCache == false {
this.cache = this.Iter.next()
this.isCache = true
}
return this.cache
}
# 2
type PeekingIterator struct {
Iter *Iterator
cache *int
}
func Constructor(iter *Iterator) *PeekingIterator {
return &PeekingIterator{
Iter: iter,
cache: nil,
}
}
func (this *PeekingIterator) hasNext() bool {
return this.cache != nil || this.Iter.hasNext()
}
func (this *PeekingIterator) next() int {
if this.cache != nil {
res := *this.cache
this.cache = nil
return res
}
return this.Iter.next()
}
func (this *PeekingIterator) peek() int {
if this.cache == nil {
value := this.Iter.next()
this.cache = &value
}
return *this.cache
}
287.寻找重复数(8)
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），
可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:输入: [1,3,4,2,2] 输出: 2
示例 2:输入: [3,1,3,4,2] 输出: 3
说明：
不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n^2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n) |
O(n) |
| 02 |
排序 |
O(nlog(n)) |
O(1) |
| 03 |
暴力法 |
O(n^2) |
O(1) |
| 04 |
二分查找 |
O(nlog(n)) |
O(1) |
| 05 |
快慢指针 |
O(n) |
O(1) |
| 06 |
位运算 |
O(n) |
O(1) |
| 07 |
交换 |
O(n) |
O(1) |
| 08 |
负号标记 |
O(n) |
O(1) |
func findDuplicate(nums []int) int {
m := make(map[int]int)
for i := 0; i < len(nums); i++ {
if m[nums[i]] > 0 {
return nums[i]
}
m[nums[i]] = 1
}
return -1
}
# 2
func findDuplicate(nums []int) int {
sort.Ints(nums)
for i := 1; i < len(nums); i++{
if nums[i] == nums[i-1]{
return nums[i]
}
}
return -1
}
# 3
func findDuplicate(nums []int) int {
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
if nums[i] == nums[j] {
return nums[i]
}
}
}
return -1
}
# 4
func findDuplicate(nums []int) int {
left, right := 1, len(nums)-1
res := -1
for left <= right {
mid := left + (right-left)/2
count := 0
for i := 0; i < len(nums); i++ {
if nums[i] <= mid {
count++
}
}
if count <= mid {
left = mid + 1
} else {
right = mid - 1
res = mid
}
}
return res
}
# 5
func findDuplicate(nums []int) int {
slow, fast := nums[0], nums[nums[0]]
for slow != fast {
slow, fast = nums[slow], nums[nums[fast]]
}
slow = 0
for slow != fast {
slow, fast = nums[slow], nums[fast]
}
return slow
}
# 6
func findDuplicate(nums []int) int {
arrV := [32]int{}
arrI := [32]int{}
res := 0
for i := 0; i < len(nums); i++ {
value := nums[i]
index := i
for j := 0; j < 32; j++ {
if value&(1<<j) > 0 {
arrV[j]++
}
if index > 0 && (index&(1<<j) > 0) {
arrI[j]++
}
}
}
for i := 0; i < len(arrV); i++ {
if arrV[i] > arrI[i] {
res = res ^ (1 << i)
}
}
return res
}
# 7
func findDuplicate(nums []int) int {
if len(nums) == 0 {
return 0
}
for i := 1; i <= len(nums)-1; i++ {
for i != nums[i] {
value := nums[i]
if value == nums[value] {
return value
}
nums[i], nums[value] = nums[value], nums[i]
}
}
return nums[0]
}
# 8
func findDuplicate(nums []int) int {
for i := 0; i < len(nums); i++ {
index := abs(nums[i]) - 1
if nums[index] > 0 {
nums[index] = -1 * nums[index]
} else {
return abs(nums[i])
}
}
return 0
}
func abs(a int) int {
if a >= 0 {
return a
}
return -a
}
289.生命游戏(2)
根据 百度百科 ，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：
1 即为活细胞（live），或 0 即为死细胞（dead）。
每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。
下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。
示例：输入：
[
[0,1,0],
[0,0,1],
[1,1,1],
[0,0,0]
]
输出：
[
[0,0,0],
[1,0,1],
[0,1,1],
[0,1,0]
]
进阶：
你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：
你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。
你将如何解决这些问题？
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数组辅助 |
O(n^2) |
O(n^2) |
| 02 |
遍历 |
O(n^2) |
O(1) |
func gameOfLife(board [][]int) {
temp := make([][]int, len(board))
for i := 0; i < len(board); i++ {
temp[i] = make([]int, len(board[i]))
}
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[i]); j++ {
count := 0
for a := i - 1; a < i+1; a++ {
for b := j - 1; b < j+1; b++ {
if 0 <= a && a < len(board) &&
0 <= b && b < len(board[i]) && board[i][j] == 1 {
count++
}
}
}
if count < 2 || count > 3 {
temp[i][j] = 0
}
if count == 3 && temp[i][j] == 0 {
temp[i][j] = 1
}
}
}
copy(board, temp)
}
# 2
func gameOfLife(board [][]int) {
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[i]); j++ {
count := 0
for a := i - 1; a <= i+1; a++ {
for b := j - 1; b <= j+1; b++ {
if a == i && b == j {
continue
}
if 0 <= a && a < len(board) &&
0 <= b && b < len(board[i]) {
count = count + board[a][b]%2
}
}
}
if (count < 2 || count > 3) && board[i][j] == 1 {
board[i][j] = 3
}
if count == 3 && board[i][j] == 0 {
board[i][j] = 2
}
}
}
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[i]); j++ {
if board[i][j] == 2 {
board[i][j] = 1
} else if board[i][j] == 3 {
board[i][j] = 0
}
}
}
}
300.最长上升子序列(2)
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:输入: [10,9,2,5,3,7,101,18] 输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n) |
| 02 |
贪心+二分查找 |
O(nlog(n)) |
O(n) |
func lengthOfLIS(nums []int) int {
if len(nums) < 2 {
return len(nums)
}
dp := make([]int, len(nums))
res := 1
for i := 0; i < len(nums); i++ {
dp[i] = 1
for j := 0; j < i; j++ {
if nums[j] < nums[i] {
dp[i] = max(dp[j]+1, dp[i])
}
}
res = max(res, dp[i])
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func lengthOfLIS(nums []int) int {
if len(nums) < 2 {
return len(nums)
}
arr := make([]int, len(nums)+1)
arr[1] = nums[0]
res := 1
for i := 1; i < len(nums); i++ {
if arr[res] < nums[i] {
res++
arr[res] = nums[i]
} else {
left, right := 1, res
index := 0
for left <= right {
mid := left + (right-left)/2
if arr[mid] < nums[i] {
index = mid
left = mid + 1
} else {
right = mid - 1
}
}
arr[index+1] = nums[i]
}
}
return res
}
0201-0300-Hard
214.最短回文串(3)
给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。
找到并返回可以用这种方式转换的最短回文串。
示例 1:输入: "aacecaaa" 输出: "aaacecaaa"
示例 2:输入: "abcd" 输出: "dcbabcd"
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
反转比较 |
O(n^2) |
O(n) |
| 02 |
遍历 |
O(n^2) |
O(n) |
| 03 |
manacher |
O(n^2) |
O(n) |
func shortestPalindrome(s string) string {
str := reverse(s)
i := 0
for i = 0; i < len(s); i++ {
if str[i:] == s[:len(s)-i] {
break
}
}
return str[:i] + s
}
func reverse(s string) string {
res := make([]byte, 0)
for i := len(s) - 1; i >= 0; i-- {
res = append(res, s[i])
}
return string(res)
}
# 2
func shortestPalindrome(s string) string {
i := len(s)
for {
if isPalindrome(s[:i]) == true {
break
}
i--
}
res := s
for j := i; j < len(s); j++ {
res = string(s[j]) + res
}
return res
}
func isPalindrome(s string) bool {
i, j := 0, len(s)-1
for i < j {
if s[i] != s[j] {
return false
}
i++
j--
}
return true
}
# 3
func shortestPalindrome(s string) string {
str := add(s)
index := 0
for i := len(str) / 2; i <= len(str)/2; i-- {
j := i
for ; j > 0; j-- {
if str[i-j] != str[i+j] {
break
}
}
if j == 0 {
index = i
break
}
}
res := s
for j := index; j < len(s); j++ {
res = string(s[j]) + res
}
return res
}
func add(s string) string {
var res []rune
for _, v := range s {
res = append(res, '#')
res = append(res, v)
}
res = append(res, '#')
return string(res)
}
218.天际线问题
题目
解题思路
224.基本计算器(1)
实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。
示例 1：输入：s = "1 + 1" 输出：2
示例 2：输入：s = " 2-1 + 2 " 输出：3
示例 3：输入：s = "(1+(4+5+2)-3)+(6+8)" 输出：23
提示：1 <= s.length <= 3* 105
s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
s 表示一个有效的表达式
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
栈 |
O(n) |
O(n) |
func calculate(s string) int {
stack := make([]int, 0)
num := 0
res := 0
sign := 1
for i := 0; i < len(s); i++ {
if '0' <= s[i] && s[i] <= '9' {
num = 0
for ; i < len(s) && '0' <= s[i] && s[i] <= '9'; i++ {
num = num*10 + int(s[i]-'0')
}
res = res + sign*num
i--
} else if s[i] == '+' {
sign = 1
} else if s[i] == '-' {
sign = -1
} else if s[i] == '(' {
stack = append(stack, res, sign)
res = 0
sign = 1
} else if s[i] == ')' {
sign = stack[len(stack)-1]
prev := stack[len(stack)-2]
stack = stack[:len(stack)-2]
res = prev + sign*res*sign
}
}
return res
}
233.数字1的个数(3)
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
示例:输入: 13输出: 6
解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
找规律-遍历 |
O(log(n)) |
O(1) |
| 02 |
找规律-递归 |
O(log(n)) |
O(log(n)) |
| 03 |
找规律 |
O(log(n)) |
O(1) |
func countDigitOne(n int) int {
res := 0
digit := 1
high := n / 10
cur := n % 10
low := 0
for high != 0 || cur != 0 {
if cur == 0 {
res = res + high*digit
} else if cur == 1 {
res = res + high*digit + low + 1
} else {
res = res + (high+1)*digit
}
low = low + cur*digit
cur = high % 10
high = high / 10
digit = digit * 10
}
return res
}
# 2
func countDigitOne(n int) int {
if n <= 0 {
return 0
}
str := strconv.Itoa(n)
return dfs(str)
}
func dfs(str string) int {
if str == "" {
return 0
}
first := int(str[0] - '0')
if len(str) == 1 && first == 0 {
return 0
}
if len(str) == 1 && first >= 1 {
return 1
}
count := 0
if first > 1 {
count = int(math.Pow(float64(10), float64(len(str)-1)))
} else if first == 1 {
count, _ = strconv.Atoi(str[1:])
count = count + 1
}
other := first * (len(str) - 1) * int(math.Pow(float64(10), float64(len(str)-2)))
numLeft := dfs(str[1:])
return count + numLeft + other
}
# 3
func countDigitOne(n int) int {
if n <= 0 {
return 0
}
res := 0
for i := 1; i <= n; i = i * 10 {
left := n / i
right := n % i
res = res + (left+8)/10*i
if left%10 == 1 {
res = res + right + 1
}
}
return res
}
239.滑动窗口最大值(3)
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
进阶：你能在线性时间复杂度内解决此题吗？
示例:输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
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 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
提示：
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n^2) |
O(n) |
| 02 |
暴力法-有条件更新最大值 |
O(n^2) |
O(n) |
| 03 |
双端队列 |
O(n) |
O(n) |
| 04 |
堆排序(超时) |
O(nlog(n)) |
O(n) |
func maxSlidingWindow(nums []int, k int) []int {
res := make([]int, 0)
if len(nums) == 0 {
return res
}
for i := 0; i < len(nums)-k+1; i++ {
max := nums[i]
for j := i; j < i+k; j++ {
if nums[j] > max {
max = nums[j]
}
}
res = append(res, max)
}
return res
}
# 2
func maxSlidingWindow(nums []int, k int) []int {
res := make([]int, 0)
if len(nums) == 0 {
return res
}
max := math.MaxInt32
for i := 0; i < len(nums)-k+1; i++ {
if i == 0 || nums[i-1] == max {
max = nums[i]
for j := i; j < i+k; j++ {
if nums[j] > max {
max = nums[j]
}
}
} else {
if nums[i+k-1] > max {
max = nums[i+k-1]
}
}
res = append(res, max)
}
return res
}
# 3
func maxSlidingWindow(nums []int, k int) []int {
res := make([]int, 0)
if len(nums) == 0 {
return res
}
deque := make([]int, 0)
for i := 0; i < k; i++ {
for len(deque) > 0 && nums[i] >= nums[deque[len(deque)-1]] {
deque = deque[:len(deque)-1]
}
deque = append(deque, i)
}
for i := k; i < len(nums); i++ {
res = append(res, nums[deque[0]])
for len(deque) > 0 && nums[i] >= nums[deque[len(deque)-1]] {
deque = deque[:len(deque)-1]
}
if len(deque) > 0 && deque[0] <= i-k {
deque = deque[1:]
}
deque = append(deque, i)
}
res = append(res, nums[deque[0]])
return res
}
# 4
func maxSlidingWindow(nums []int, k int) []int {
res := make([]int, 0)
if len(nums) == 0 {
return res
}
intHeap := make(IntHeap, 0, k)
heap.Init(&intHeap)
for i := 0; i < k; i++ {
heap.Push(&intHeap, nums[i])
}
for i := k; i < len(nums); i++ {
temp := heap.Pop(&intHeap).(int)
res = append(res, temp)
if temp != nums[i-k] {
intHeap.Remove(nums[i-k])
heap.Push(&intHeap, temp)
heap.Push(&intHeap, nums[i])
} else {
heap.Push(&intHeap, nums[i])
}
}
res = append(res, heap.Pop(&intHeap).(int))
return res
}
type IntHeap []int
func (i IntHeap) Len() int {
return len(i)
}
func (i IntHeap) Less(x, y int) bool {
return i[x] > i[y]
}
func (i IntHeap) Swap(x, y int) {
i[x], i[y] = i[y], i[x]
}
func (i *IntHeap) Push(v interface{}) {
*i = append(*i, v.(int))
}
func (i *IntHeap) Pop() interface{} {
value := (*i)[len(*i)-1]
*i = (*i)[:len(*i)-1]
return value
}
func (i *IntHeap) Remove(x interface{}) {
for j := 0; j < len(*i); j++ {
if (*i)[j] == x {
*i = append((*i)[:j], (*i)[j+1:]...)
break
}
}
heap.Init(i)
}
273.整数转换英文表(3)
题目
将非负整数转换为其对应的英文表示。可以保证给定输入小于 2^31 - 1 。
示例 1:输入: 123 输出: "One Hundred Twenty Three"
示例 2:输入: 12345 输出: "Twelve Thousand Three Hundred Forty Five"
示例 3:输入: 1234567
输出: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
示例 4:输入: 1234567891
输出: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven
Thousand Eight Hundred Ninety One"
解题思路
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(1) |
O(1) |
| 02 |
递归 |
O(1) |
O(1) |
func numberToWords(num int) string {
if num == 0 {
return "Zero"
}
res := ""
billion := num / 1000000000
million := (num - billion*1000000000) / 1000000
thousand := (num - billion*1000000000 - million*1000000) / 1000
left := num - billion*1000000000 - million*1000000 - thousand*1000
if billion != 0 {
res += three(billion) + " Billion"
}
if million != 0 {
if res != "" {
res += " "
}
res += three(million) + " Million"
}
if thousand != 0 {
if res != "" {
res += " "
}
res += three(thousand) + " Thousand"
}
if left != 0 {
if res != "" {
res += " "
}
res += three(left)
}
return res
}
func three(num int) string {
hundred := num / 100
left := num - hundred*100
if hundred == 0 {
return two(num)
}
res := transfer[hundred] + " Hundred"
if left != 0 {
res += " " + two(left)
}
return res
}
func two(num int) string {
if num == 0 {
return ""
} else if num < 10 {
return transfer[num]
} else if num < 20 {
return transfer[num]
}
ten := num / 10
left := num - ten*10
ten = ten * 10
res := transfer[ten]
if left != 0 {
res += " " + transfer[left]
}
return res
}
var transfer = map[int]string{
0: "Zero",
1: "One",
2: "Two",
3: "Three",
4: "Four",
5: "Five",
6: "Six",
7: "Seven",
8: "Eight",
9: "Nine",
10: "Ten",
11: "Eleven",
12: "Twelve",
13: "Thirteen",
14: "Fourteen",
15: "Fifteen",
16: "Sixteen",
17: "Seventeen",
18: "Eighteen",
19: "Nineteen",
20: "Twenty",
30: "Thirty",
40: "Forty",
50: "Fifty",
60: "Sixty",
70: "Seventy",
80: "Eighty",
90: "Ninety",
}
# 2
func numberToWords(num int) string {
if num == 0 {
return "Zero"
}
return strings.Trim(dfs(num), " ")
}
func dfs(n int) string {
if n < 20 {
return transfer[n]
}
if n < 100 {
return transfer[n/10*10] + dfs(n%10)
}
if n < 1000 {
return transfer[n/100] + "Hundred " + dfs(n%100)
}
if n < 1000000 {
return dfs(n/1000) + "Thousand " + dfs(n%1000)
}
if n < 1000000000 {
return dfs(n/1000000) + "Million " + dfs(n%1000000)
}
return dfs(n/1000000000) + "Billion " + dfs(n%1000000000)
}
var transfer = map[int]string{
1: "One ",
2: "Two ",
3: "Three ",
4: "Four ",
5: "Five ",
6: "Six ",
7: "Seven ",
8: "Eight ",
9: "Nine ",
10: "Ten ",
11: "Eleven ",
12: "Twelve ",
13: "Thirteen ",
14: "Fourteen ",
15: "Fifteen ",
16: "Sixteen ",
17: "Seventeen ",
18: "Eighteen ",
19: "Nineteen ",
20: "Twenty ",
30: "Thirty ",
40: "Forty ",
50: "Fifty ",
60: "Sixty ",
70: "Seventy ",
80: "Eighty ",
90: "Ninety ",
}
282.给表达式添加运算符(2)
给定一个仅包含数字0-9的字符串和一个目标值，在数字之间添加 二元 运算符（不是一元）+、-或*，
返回所有能够得到目标值的表达式。
示例 1:输入: num = "123", target = 6 输出: ["1+2+3", "1*2*3"]
示例2:输入: num = "232", target = 8 输出: ["2*3+2", "2+3*2"]
示例 3:输入: num = "105", target = 5 输出: ["1*0+5","10-5"]
示例4:输入: num = "00", target = 0 输出: ["0+0", "0-0", "0*0"]
示例 5:输入: num = "3456237490", target = 9191 输出: []
提示：0 <= num.length <= 10
num 仅含数字
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
回溯 |
O(3^n) |
O(3^n) |
| 02 |
回溯 |
O(3^n) |
O(3^n) |
var res []string
func addOperators(num string, target int) []string {
res = make([]string, 0)
dfs(num, target, 0, "", 0, 0)
return res
}
func dfs(num string, target int, index int, str string, value int, prev int) {
if index == len(num) {
if value == target {
res = append(res, str)
}
return
}
for i := index; i < len(num); i++ {
if num[index] == '0' && index < i {
return
}
s := num[index : i+1]
a, _ := strconv.Atoi(s)
if index == 0 {
dfs(num, target, i+1, str+s, a, a)
} else {
dfs(num, target, i+1, str+"+"+s, value+a, a)
dfs(num, target, i+1, str+"-"+s, value-a, -a)
dfs(num, target, i+1, str+"*"+s, value-prev+prev*a, prev*a)
}
}
}
# 2
var res []string
func addOperators(num string, target int) []string {
res = make([]string, 0)
dfs(num, target, 0, "")
return res
}
func dfs(num string, target int, index int, str string) {
if index == len(num) {
if calculate(str) == target {
res = append(res, str)
}
return
}
for i := index; i < len(num); i++ {
if num[index] == '0' && index < i {
return
}
s := num[index : i+1]
if index == 0 {
dfs(num, target, i+1, str+s)
} else {
dfs(num, target, i+1, str+"+"+s)
dfs(num, target, i+1, str+"-"+s)
dfs(num, target, i+1, str+"*"+s)
}
}
}
func calculate(s string) int {
stack := make([]int, 0)
num := 0
sign := byte('+')
for i := 0; i < len(s); i++ {
if s[i] == ' ' {
continue
}
if '0' <= s[i] && s[i] <= '9' {
num = num*10 + int(s[i]-'0')
}
if s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || i == len(s)-1 {
switch sign {
case '+':
stack = append(stack, num)
case '-':
stack = append(stack, -num)
case '*':
prev := stack[len(stack)-1]
stack = stack[:len(stack)-1]
stack = append(stack, num*prev)
case '/':
prev := stack[len(stack)-1]
stack = stack[:len(stack)-1]
stack = append(stack, prev/num)
}
num = 0
sign = s[i]
}
}
res := 0
for i := 0; i < len(stack); i++ {
res = res + stack[i]
}
return res
}
295.数据流的中位数(1)
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例：
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
进阶:
如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
大小根堆-内置heap接口 |
O(log(n)) |
O(n) |
type MinHeap []int
func (i MinHeap) Len() int {
return len(i)
}
func (i MinHeap) Less(x, y int) bool {
return i[x] < i[y]
}
func (i MinHeap) Swap(x, y int) {
i[x], i[y] = i[y], i[x]
}
func (i *MinHeap) Push(v interface{}) {
*i = append(*i, v.(int))
}
func (i *MinHeap) Pop() interface{} {
value := (*i)[len(*i)-1]
*i = (*i)[:len(*i)-1]
return value
}
type MaxHeap []int
func (i MaxHeap) Len() int {
return len(i)
}
func (i MaxHeap) Less(x, y int) bool {
return i[x] > i[y]
}
func (i MaxHeap) Swap(x, y int) {
i[x], i[y] = i[y], i[x]
}
func (i *MaxHeap) Push(v interface{}) {
*i = append(*i, v.(int))
}
func (i *MaxHeap) Pop() interface{} {
value := (*i)[len(*i)-1]
*i = (*i)[:len(*i)-1]
return value
}
type MedianFinder struct {
minArr *MinHeap
maxArr *MaxHeap
}
func Constructor() MedianFinder {
res := new(MedianFinder)
res.minArr = new(MinHeap)
res.maxArr = new(MaxHeap)
heap.Init(res.minArr)
heap.Init(res.maxArr)
return *res
}
func (this *MedianFinder) AddNum(num int) {
if this.maxArr.Len() == this.minArr.Len() {
heap.Push(this.minArr, num)
heap.Push(this.maxArr, heap.Pop(this.minArr))
} else {
heap.Push(this.maxArr, num)
heap.Push(this.minArr, heap.Pop(this.maxArr))
}
}
func (this *MedianFinder) FindMedian() float64 {
if this.minArr.Len() == this.maxArr.Len() {
return (float64((*this.maxArr)[0]) + float64((*this.minArr)[0])) / 2
} else {
return float64((*this.maxArr)[0])
}
}
297.二叉树的序列化与反序列化(2)
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，
同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，
你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
示例: 你可以将以下二叉树：
1
/ \
2 3
/ \
4 5
序列化为 "[1,2,3,null,null,4,5]"
提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。
你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。
| 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
}