Algorithm
148. 排序链表
自顶向下
type ListNode struct {
Val int
Next *ListNode
}
func sortList(head *ListNode) *ListNode {
return sort(head, nil)
}
func sort(head *ListNode, tail *ListNode) *ListNode {
if head == nil {
return head
}
if head.Next == tail {
head.Next = nil
return head
}
slow, fast := head, head
for fast != nil && fast != tail{
fast = fast.Next
slow = slow.Next
if fast != tail {
fast = fast.Next
}
}
middle := slow
return merge(sort(head, middle), sort(middle, tail))
}
func merge(head1 *ListNode, head2 *ListNode) *ListNode {
oldHead := &ListNode{}
temp1, temp2, temp3 := oldHead, head1, head2
for temp2 != nil && temp3 != nil {
if temp2.Val <= temp3.Val {
temp1.Next = temp2
temp2 = temp2.Next
} else {
temp1.Next = temp3
temp3 = temp3.Next
}
temp1 = temp1.Next
}
if temp2 != nil {
temp1.Next = temp2
}
if temp3 != nil {
temp1.Next = temp3
}
return oldHead.Next
}
自底向上
func merge(head1 *ListNode, head2 *ListNode) *ListNode {
oldHead := &ListNode{}
temp1, temp2, temp3 := oldHead, head1, head2
for temp2 != nil && temp3 != nil {
if temp2.Val <= temp3.Val {
temp1.Next = temp2
temp2 = temp2.Next
} else {
temp1.Next = temp3
temp3 = temp3.Next
}
temp1 = temp1.Next
}
if temp2 != nil {
temp1.Next = temp2
}
if temp3 != nil {
temp1.Next = temp3
}
return oldHead.Next
}
func sortList1(head *ListNode) *ListNode {
length := 0
temp := head
for temp != nil {
length += 1
temp = temp.Next
}
dummyNode := &ListNode{Next: head}
for i := 1; i < length; i = i * 2 {
pre, cur := dummyNode, dummyNode.Next
for cur != nil {
// 找出第一个链表
head1 := cur
j := 1
for cur.Next != nil && j < i {
cur = cur.Next
j += 1
}
head2 := cur.Next
// 这里要把head1的next置为nil，不然merge的时候会有问题
cur.Next = nil
cur = head2
j = 1
// 这里break条件多了一个cur不为nil，就是为了第一次cur为nil的时候不走进for循环
for cur != nil && cur.Next != nil && j < i {
cur = cur.Next
j += 1
}
// 保存好当前节点，用于下一次for循环
var next *ListNode
if cur != nil {
next = cur.Next
// 这里要把head2的next置为nil，不然merge的时候会有问题
cur.Next = nil
}
cur = next
// 合并2个链表,并挪到最尾巴
pre.Next = merge(head1, head2)
// 将pre挪到合并之后的尾巴
for pre.Next != nil {
pre = pre.Next
}
}
}
return dummyNode.Next
}
Review
Golang Technique: How to Add Default Values to Function Parameters?
使用Functional options pattern来实现一个默认值方法
type GreetingOptions struct {
Name string
Age int
}
func Greet(options GreetingOptions) string {
return "Hello, my name is " + options.Name + " and I am " + strconv.Itoa(options.Age) + " years old."
}
type GreetingOption func(*GreetingOptions)
func WithName(name string) GreetingOption {
return func(o *GreetingOptions) {
o.Name = name
}
}
func WithAge(age int) GreetingOption {
return func(o *GreetingOptions) {
o.Age = age
}
}
func GreetWithDefaultOptions(options ...GreetingOption) string {
opts := GreetingOptions{
Name: "Aiden",
Age: 30,
}
for _, o := range options {
o(&opts)
}
return Greet(opts)
}
这个编程范式在许多开源仓库都有用到，典型的就是es client
TIP
为什么需要 redo log ？
写入 redo log 的方式使用了追加操作， 所以磁盘操作是顺序写，而写入数据需要先找到写入位置，然后才写到磁盘，所以磁盘操作是随机写。
磁盘的「顺序写 」比「随机写」 高效的多，因此 redo log 写入磁盘的开销更小。
针对「顺序写」为什么比「随机写」更快这个问题，可以比喻为你有一个本子，按照顺序一页一页写肯定比写一个字都要找到对应页写快得多。
Share
学习mysql 45讲
34 | 到底可不可以使用join？
在实际生产中， 关于join语句使用的问题， 一般会集中在以下两类：
- 我们DBA不让使用join， 使用join有什么问题呢？
- 如果有两个大小不同的表做join， 应该用哪个表做驱动表呢？
答案：
- 如果可以使用被驱动表的索引， join语句还是有其优势的；
- 不能使用被驱动表的索引， 只能使用Block Nested-Loop Join算法， 这样的语句就尽量不要使用；
- 在使用join的时候， 应该让小表做驱动表。
