剑指offer 03

题面

https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

思考

淼题

有两种思路,一种是时间换空间,对数组进行排序,扫一遍出结果;另一种类似桶排序,是用空间换时间。

不过在解题时,出现了一些问题,由于之前写算法题一直使用c++,而且写golang时习惯用IDE
自动提示,导致go语法记不熟,出现了下面这段鬼畜的代码:

1
2
3
4
5
6
7
8
9
10
11
func findRepeatNumber(nums []int) int {
len := nums.len
var a [len]int
for k, v := range nums {
if a[v] != 0 {
fmt.Println(v)
break
}
++a[v]
}
}

这段代码有几个问题:

  1. 求一个切片的长度应该用len(Slice)
  2. 不能用变量给数组设置大小(至于为什么可以联想一下之前学的CSAPP
  3. k没用到,不该存在
  4. 题目应该是让返回一个值,这里是把它输出了
  5. golang中没有++a[v]这种写法,只能用a[v]++

IDE的帮助下debug之后一遍过,这也提醒了我要注意培养面试时在无顺手IDE的情况下写代码。

剑指offer 04

题面

https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

思考

挺简单的bfs + 贪心,不知道为什么难度被设置成了中等

长时间没写甚至连bfs的板子都忘了,还是重新搜了一下板子才写出来

不过由于不适应力扣的oj,导致出了很多锅

买卖股票的最佳时机 III

题面

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/

思考

不算难的动态规划,这里对状态的抽象挺不错的。

设计LUR缓存结构

题面

https://www.nowcoder.com/practice/e3769a5f49894d49b871c09cadd13a61?tpId=117&tqId=37804&companyId=665&rp=1&ru=%2Fcompany%2Fhome%2Fcode%2F665&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
package main

type Node struct {
key int
value int
next *Node
pre *Node
}

type List struct {
Head *Node
Tail *Node
Size int
}

func (l *List) Init() {
l.Size = 0
l.Head = new(Node)
l.Tail = new(Node)
l.Head.next = l.Tail
l.Tail.pre = l.Head
}

func (l *List) Insert(node *Node) {
old := l.Head.next
node.next = old
node.pre = l.Head
l.Head.next = node
old.pre = node
l.Size++
}

func (l *List) DeleteFromTail() {
newLast := l.Tail.pre.pre
newLast.next = l.Tail
l.Tail.pre = newLast
l.Size--
}

func (l *List) DeleteNode(node *Node) {
preNode := node.pre
nextNode := node.next
preNode.next = nextNode
nextNode.pre = preNode
l.Size--
}

func (l *List) MoveToHead(node *Node) {
l.DeleteNode(node)
l.Insert(node)
}

func LRU( operators [][]int , k int ) []int {
m := make(map[int]*Node)
l := new(List)
ans := make([]int, 0)
l.Init()
for _, operator := range operators {
opType := operator[0]
if opType == 2 {
key := operator[1]
v, ok := m[key]
if ok == false {
ans = append(ans, -1)
} else {
ans = append(ans, v.value)
l.MoveToHead(v)
}
} else {
key := operator[1]
value := operator[2]
v, ok := m[key]
if ok == true {
v.value = value
l.MoveToHead(v)
} else {
newNode := new(Node)
newNode.key = key
newNode.value = value
if l.Size < k {
l.Insert(newNode)
m[key] = newNode
} else {
deletedKey := l.Tail.pre.key
delete(m, deletedKey)
l.Insert(newNode)
}
}
}
}

return ans
}

思考

查询和设置为O(1)显然想到用哈希,然后后面要求插入和删除也是O(1),这个下次遇到要想到使用链表,这里用双向链表就很舒服。

最小k个数

题面

https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?tpId=117&tqId=37765&companyId=665&rp=1&ru=%2Fcompany%2Fhome%2Fcode%2F665&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package main

/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* @param input int整型一维数组
* @param k int整型
* @return int整型一维数组
*/
func partition(s []int, begin, end int) int {
i := begin + 1
j := end
for i < j {
if s[begin] < s[i] {
s[i], s[j] = s[j], s[i]
j--
} else {
i++
}
}

if s[begin] <= s[j] {
i--
}

s[begin], s[i] = s[i], s[begin]
return i
}

func quickSort(s []int, begin, end int) {
if begin < end {
pos := partition(s, begin, end)

quickSort(s, begin, pos - 1)
quickSort(s, pos + 1, end)
}
}

func GetLeastNumbers_Solution( input []int , k int ) []int {
// write code here
if k > len(input) {
return []int{}
}
quickSort(input, 0, len(input) - 1)
s := input[:k]
return s
}

思考

这题有很多方法,

首先很容易想到的一种是:快排,然后对哨兵节点的位置进行分析,如果恰好等于k - 1,直接就得到了这k个数字,懒得解释了,其它情况自己看代码。

以下是核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func quickSort(s []int, begin, end int) {
if begin < end {
pos := partition(s, begin, end)
if pos == k - 1 {
return
}

if pos < k - 1 {
quickSort(s, pos + 1, end)
} else {
quickSort(s, begin, pos - 1)
}
}
}

第二种方法是使用堆的思想,维护一个k个节点的最大堆,逐个扫元素,比根节点小的话,就删除根节点,把该元素push上去,否则不管它。这种方法个人感觉不是很容易想到,思想很不错,值得多回过头想一想。

这个很容易写,懒得放上去了。

第三种方法最傻逼,就是排序然后取前面k个,但是由于牛客给的答案只能是按排序好的k个数字,我就是交的这个(我是傻逼)

求二叉树的层序遍历

题面

https://www.nowcoder.com/practice/04a5560e43e24e9db4595865dc9c63a3?tpId=117&tqId=37723&companyId=665&rp=1&ru=%2Fcompany%2Fhome%2Fcode%2F665&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
package main
import . "nc_tools"
/*
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/

/**
*
* @param root TreeNode类
* @return int整型二维数组
*/
type QueueNode struct {
value *TreeNode
num int
}

type Queue []QueueNode

func (q *Queue) Push(x QueueNode) {
*q = append(*q, x)
}

func (q *Queue) Pop() QueueNode {
x := (*q)[0]
*q = (*q)[1:]
return x
}

func (q Queue) Size() int {
return len(q)
}

func levelOrder( root *TreeNode ) [][]int {
if root == nil {
return [][]int{}
}
q := make(Queue, 0)
ans := make([][]int, 0)
q.Push(QueueNode{
value: root,
num: 0,
})
ansSub := make([]int, 0)
num := 0
for q.Size() != 0 {
node := q.Pop()
if node.num != num {
num = node.num
ans = append(ans, ansSub)
ansSub = make([]int, 0)
}
ansSub = append(ansSub, node.value.Val)

if l := node.value.Left; l != nil {
q.Push(QueueNode{
value: l,
num: num + 1,
})
}
if r := node.value.Right; r != nil {
q.Push(QueueNode{
value: r,
num: num + 1,
})
}
}

if len(ansSub) != 0 {
ans = append(ans, ansSub)
}
return ans
}

思考

题目不难,就是眼瞎

暴露了审题不清的毛病,本来以为只是一个简单的bfs,后来发现它要的是一整层的数据。

这样其实也容易处理,用一个自增的num染色一下就好了。

子数组的最大累加和问题

题面

https://www.nowcoder.com/practice/554aa508dd5d4fefbf0f86e5fe953abd?tpId=117&tqId=37797&companyId=665&rp=1&ru=%2Fcompany%2Fhome%2Fcode%2F665&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package main

/**
* max sum of the subarray
* @param arr int整型一维数组 the array
* @return int整型
*/
func max(a, b int) int {
if a > b {
return a
}
return b
}

func maxsumofSubarray( arr []int ) int {
n := len(arr)
dp := make([]int, n)
m := arr[0]
dp[0] = arr[0]
for i := 1; i < n; i++ {
dp[i] = max(arr[i], dp[i - 1] + arr[i])
m = max(m, dp[i])
}
return m
}

思考

这次最开始思路就不对,总想着它是二维dp,类似合并石子的那种,没有认真思考,样例都没去试就直接写代码,发现不对,因为,这里的一个区间无法通过子区间加上元素得到。

然后就下意识了的一直以为是我二维dp写的不对,一直再瞎折腾 ,没折腾出来。

正确的解决方法是,dp[i]设置为以i结尾的子区间,这样就可以保证连续性。这题属实在能力范围之外了,动态规划还是要多去积累。

旋转数组

题面

https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

思考

这题也是犯了一样的错误,在不合适的思路上面纠结了太久 ,感觉我的做法可以,然后一直在纠结。其实当一条思路纠结太久没有结果,更应该想一想有没有更优的做法。

这一题正确做法是,把数组一切两半,可以判断出哪一半有序,哪一半无序,有序的进行二分查找,无序的继续递归这个操作。

合并有序列表

题面

https://www.nowcoder.com/practice/a479a3f0c4554867b35356e0d57cf03d?tpId=117&tqId=37735&companyId=665&rp=1&ru=%2Fcompany%2Fhome%2Fcode%2F665&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey

思考

还是没确定第一印象中的算法是否正确就去实现,结果发现有问题,(早上没吃早饭,迷迷糊糊就开始做题)

不过后来发现问题之后及时改变了思路,本来用的是双指针,后来发现,当一个节点到末尾时,不知道哪个指针是当前已经合并的链表。

解决方法是再添加一个节点node用来记录已经合并的链表最后一个。之后比较指针l1, l2取比较小的指针假设为min,就让node.next指向min,同时让node等于node.next,让min等于min.next。如果遇到出现两个指针有nil,那么直接让node.next等于非nil指针。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
package main
import . "nc_tools"
/*
* type ListNode struct{
* Val int
* Next *ListNode
* }
*/

/**
*
* @param l1 ListNode类
* @param l2 ListNode类
* @return ListNode类
*/
func mergeTwoLists( l1 *ListNode , l2 *ListNode ) *ListNode {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}

var head, node *ListNode
if l1.Val < l2.Val {
head = l1
node = l1
l1 = l1.Next
} else {
head = l2
node = l2
l2 = l2.Next
}

for {
if l1 == nil {
node.Next = l2
break
}
if l2 == nil {
node.Next = l1
break
}
if l1.Val < l2.Val {
node.Next = l1
node = l1
l1 = l1.Next
} else {
node.Next = l2
node = l2
l2 = l2.Next
}
}
return head
}

删除链表倒数第N个节点

题面

https://www.nowcoder.com/practice/f95dcdafbde44b22a6d741baf71653f6?tpId=117&tqId=37750&companyId=665&rp=1&ru=%2Fcompany%2Fhome%2Fcode%2F665&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey

思考

两种思路,一种是把每个节点用数组记录下来。

第二种是设置快慢指针,快指针比慢指针快n步,这样当快指针走到头时,慢指针就正好指向倒数第n

这个快慢指针第一次见到,处理倒数第n问题应该会很舒服。

用两个栈实现队列

题面

https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6?tpId=117&tqId=37774&companyId=665&rp=1&ru=%2Fcompany%2Fhome%2Fcode%2F665&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey

思考

就是一个栈用来当跳板,有点汉诺塔的味道。

注意当要改变切片的内容时,传参要传地址。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package main

var stack1 [] int
var stack2 [] int

func pushStack(stack *[]int, x int) {
*stack = append(*stack, x)
}

func popStack(stack *[]int) int {
x := (*stack)[len(*stack) - 1]
*stack = (*stack)[:len(*stack) - 1]
return x
}

func Push(node int) {
for len(stack1) != 0 {
x := popStack(&stack1)
pushStack(&stack2, x)
}
pushStack(&stack1, node)

for len(stack2) != 0 {
x := popStack(&stack2)
pushStack(&stack1, x)
}
}

func Pop() int{
return popStack(&stack1)
}

判断列表是否有环

题面

https://www.nowcoder.com/practice/650474f313294468a4ded3ce0f7898b9?tpId=117&tqId=37714&companyId=665&rp=1&ru=%2Fcompany%2Fhome%2Fcode%2F665&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey

思考

使用快慢指针的方法,设置一个指针每次走两步,一个每次走一步,二者如果有环终将相遇。

快慢指针是个好东西啊,学到了。

LCA问题(最近公共祖先)

题面

https://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116?tpId=117&tqId=37826&companyId=665&rp=1&ru=%2Fcompany%2Fhome%2Fcode%2F665&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package main
import . "nc_tools"
/*
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/

/**
*
* @param root TreeNode类
* @param o1 int整型
* @param o2 int整型
* @return int整型
*/
var m, m1, m2 []*TreeNode

func dfs(node *TreeNode, o1, o2 int) bool {
if node == nil {
return false
}
m = append(m, node)
if len(m1) == 0 {
//找第一个节点
if node.Val == o1 || node.Val == o2 {
m1 = make([]*TreeNode, len(m))
copy(m1, m)
}
} else {
//找第二个节点
if node.Val == o2 || node.Val == o1 {
m2 = make([]*TreeNode, len(m))
copy(m2, m)
return true
}
}
if dfs(node.Left, o1, o2) {
return true
}
if dfs(node.Right, o1, o2) {
return true
}
m = m[:len(m) - 1]
return false
}

func lowestCommonAncestor(root *TreeNode, o1 int, o2 int) int {
if o1 == o2 {
return o1
}
m = make([]*TreeNode, 0)
m1 = make([]*TreeNode, 0)
m2 = make([]*TreeNode, 0)
dfs(root, o1, o2)
// fmt.Println(m1, m2)
// if len(m2) == 0 {
// return m1[len(m1) - 2].Val
// }
pos := 0
for m1[pos] == m2[pos]{
pos++
if pos == len(m1) || pos == len(m2) {
return m1[pos - 1].Val
}
}
return m1[pos - 1].Val
}

思考

这题有许多许多种方法,比如线段树,Tarjan离线处理都可以实现。

鉴于本题对于一棵树,只有一个测试点,所以没必要使用复杂的方法。

这里就简单处理,直接扫就行了。

扫到第一个节点保存一下路径,再扫第二个节点再保存一下路径,然后比较,二者中最后一个相同的节点就是最近公众祖先了。

这里补充一下LCA问题的Tarjan离线解法,时间复杂度只有O(n+q)O(n+q),其中n为节点数,q为测试点数。

最后一块石头的重量II

题面

https://leetcode-cn.com/problems/last-stone-weight-ii/

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func lastStoneWeightII(stones []int) int {
if len(stones) == 1 {
return stones[0]
}
var sum int
var dp [2001]bool
for _, v := range stones {
sum += v
}
maxNeg := sum / 2;
dp[0] = true
for i := 1; i <= len(stones); i++ {
for j := maxNeg; j >= 0; j-- {
if stones[i - 1] <= j {
dp[j] = dp[j] || dp[j - stones[i - 1]]
}
}
}

for j := maxNeg; j >= 1; j-- {
if dp[j] {
return sum - 2 * j
}
}


return 0
}

题解

个人感觉是很难想到的01背包问题

理一下思路:首先可以确定的一点就是无论怎么粉碎,最后都会只剩下一个石头,如果正好相消,那么剩下的一个石头为0(可以用归纳法理解,但是最开始的思路归纳不全面,想的是剩下两个石头,或者三个石头其中两个相等,但是其实可以继续归纳成一个的情况)。

既然如此可以继续推演,剩下一个石头的重量可以通过给所有石头数组中的石头赋±号来组合而成

所以这题可以转化为:找到一个方法,给所有的石头赋正负号,让它们的和最小,但是并非所有的赋值方法都可以符合要求,比如如果和为负数就显然无法满足。

通过归纳法可以猜想:和最小且大于零的结果就是答案

假如猜想正确如何处理这个问题呢?当所有的石头重量都被赋予了符号后,把它们相加就满足加法交换律,可以把正的放入一堆A,负的放入一堆B,现在把总重量合记为sum,把负数总重量绝对值记为neg,可以发现:所求的赋予符号后全部重量之和为sum2negsum-2*neg

既然要这个合大于0,所以要求neg<=sum/2neg<= sum/2。如果我们知道了能否选出一些石头,是他们的合为neg,那么就可以通过sum2negsum-2*neg来求出答案了。

而黑体部分显然是一个01背包问题,可以轻松处理。

接下来分析一下这个算法的正确性,也就是这种让和最小且大于零的组合方法一定可以是合理的,也就是可以被碰出来。

对于上述的A,B两堆,假如它们满足条件,即A和B的绝对值之差最小,

那么我们每次从A,B之中各自取出一个带符号的元素,把它们相加,得到一个新元素,如果为正就放到A,反之放到B。

可以发现在进行这个操作时,仍然不会改变A和B总和之差的绝对值

直到A或者B其中的一个没有了元素,假设B没有元素了,这个时候有两种情况:第一种:A还剩下一个元素,那么A剩下的元素就是最后答案,也就是一顿操作后被碰出的最终石头。第二种:A还剩下多个元素,那么对于A中的石头,我们可以把它放到B中,但是这么做就会破坏A和B总和之差的绝对值最小这一条件,也就是不会出现这第二种情况。所以猜想正确。

零钱兑换II

题面

零钱兑换 II

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func change(amount int, coins []int) int {
dp := make([]int, amount + 1)

dp[0] = 1

for i := 0; i < len(coins); i++ {
for j := 1; j <= amount; j++ {
if j - coins[i] >= 0 {
dp[j] += dp[j - coins[i]]
}
}
}

return dp[amount]
}

题解

完全背包问题,i个物品每个都可以使用无数次,总空间为v,对于单个物品,花费为c,收益为w。

这里的总空间就是amout,花费就是面值,收益可以等效一下。

所以动态转移方程就是:

dp(i,amout)=dp(i1,amount)+dp(i,amountcoins[i])dp(i,amout)=dp(i-1,amount)+dp(i,amount-coins[i])

注意完全背包和01背包的不同之处:后面一项的第一个空间是i而不是i - 1。

也就是第i个物品可以从不同amout的第i个物品转移而来,等效为花费了多次第二个物品。

所以在进行空间优化的时候,第二个循环就应该顺序执行。

第一个错误的版本

题面

278. 第一个错误的版本

代码

第一种二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/** 
* Forward declaration of isBadVersion API.
* @param version your guess about first bad version
* @return true if current version is bad
* false if current version is good
* func isBadVersion(version int) bool;
*/

func firstBadVersion(n int) int {
if isBadVersion(1) {
return 1
}
l := 1
r := n
for l < r {
mid := (l + r) / 2
if isBadVersion(mid) {
r = mid - 1
} else {
l = mid
}
}
return l + 1
}

第二种二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/** 
* Forward declaration of isBadVersion API.
* @param version your guess about first bad version
* @return true if current version is bad
* false if current version is good
* func isBadVersion(version int) bool;
*/

func firstBadVersion(n int) int {
l := 1
r := n
for l < r {
mid := (l + r) / 2
if isBadVersion(mid) {
r = mid
} else {
l = mid + 1
}
}
return l
}

反思

两张二分的差别在于:第一种二分是在找最后一个CorrectVersion,第二种二分是在找第一个BadVersion,显然都可以解决问题。

从模板的角度来看,第一种二分是mid := (l + r + 1) / 2而第二种二分是mid = (l + r) / 2

这么做的原因在于边界条件,如果第一种不额外加上一个1,有可能会产生死循环。

在这一题中如果把第一种二分的加1去掉提交,可以发现这一题TLE了。

之前一直知道有两种二分,但一直记不住什么时候该用什么,现在可把我整明白了:

边界l和r的转换动动脑子都可以写出来的,重点就在于,如果使用了r = mid - 1,那么就对应了第一种二分,mid就应该符合mid = (l + r) / 2,可以这么记忆,r减去了1,mid就要加上1,收支平衡嘛(