ARTS 第19周分享

[TOC]

Algorithm

75. Sort Colors

[medium]

[题目描述]

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Example 1:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

[解题思路]

• 假设数组由三段组成，即[0, 0, 1, 1, 2, 2]，可以发现规律：当我们将两边的数据0,2排列好以后，中间的1自然就排列好了，
• 所以问题将变成如何将0和2方在数组的前面和后面
• 用三个指针p0, p2, current，分别指向0的最右边界，2的最左边界 和当前遍历到的元素
  • 初始化：p0指向数组的第一个元素，用于存放0；p2指向数组的最后一个元素，用于存放2；current指向数组的第一个元素，从第一开始遍历
  • 当当前遍历的元素（current）等于 0 时，与p0指向的元素交换，同时p0和current分别加1，用于遍历下一个元素
  • 当当前遍历的元素（current）等于 2 时，与p2指向的元素交换，同时p2减1（从后向前排序），current则加1（用于遍历下一个元素）
  • 当当前遍历的元素（current）等于 1时则跳过
  • 直到current的值大于p2时才结束（代表所有的元素都以及被排序过）

[参考代码]

func sortColors(nums []int) {
    // 使用三个指针p0, p2, current，分别指向0的最右边界，2的最左边界 和当前遍历到的元素
    // 将两头的元素排列好，中间的元素自然就只剩下了1

    p0 := 0
    cur := 0
    p2 := len(nums) - 1

    for cur <= p2 {
        if nums[cur] == 0 {
            nums[p0], nums[cur] = nums[cur], nums[p0]
            p0++
            cur++
        } else if nums[cur] == 2 {
            nums[p2], nums[cur] = nums[cur], nums[p2]
            p2--
        } else {
            cur++
        }
    }
}

147. Insertion Sort List

[medium]

[题目描述]

Sort a linked list using insertion sort.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

[解题思路]

• way1:
  • 新建一个全新的列表，将旧列表中的每一元素有序插入到新列表中
• way2:
  • 直接对该列表通过插入排序的思想进行排序，只要注意将对数组的操作改为对链表的操作即可，整体思路不变

[参考代码]

func insertionSortList(head *ListNode) *ListNode {
    // 新建一个全新的列表，将旧列表中的每一元素插入到新列表中

    // 极端情况判断
    if head == nil {
        return nil
    } else if head.Next == nil {
        return head
    }

    // first
    // 新列表的第一个元素直接为旧列表的第一个元素
    sortedList := &ListNode{Val: head.Val}

    for head.Next != nil {

        cur := head.Next           // 待插入元素
        head.Next = head.Next.Next // 从旧列表中取出一个元素

        // 插入新列表中
        preTmp := sortedList
        tmp := sortedList
        for tmp != nil { // 遍历的最后一个元素，同时待插入元素的值小于等于遍历的元素则停止
            if cur.Val <= tmp.Val {
                break
            }
            preTmp = tmp
            tmp = tmp.Next
        }

        if tmp == sortedList {
            cur.Next = sortedList
            sortedList = cur
        } else {
            cur.Next = tmp
            preTmp.Next = cur
        }
    }

    return sortedList
}

func insertionSortList(head *ListNode) *ListNode {
    /*
        假设开头第一个元素为有序表，遍历后面的所有元素，将每一个元素插入到前面有序表的合适位置。
    */

    if head == nil {
        return nil
    } else if head.Next == nil {
        return head
    }

    // first
    // curVal := head.Val
    preCur := head     // 指向当前待插入的元素的前一个元素
    cur := preCur.Next // 指向当前待插入的元素

    preTmp := head // 指向当前遍历的元素的前一个元素
    tmp := head    // 指向当前遍历的元素

    for cur != nil {
        // 找到要插入的位置
        for tmp != cur && cur.Val > tmp.Val {
            preTmp = tmp
            tmp = tmp.Next
        }

        // 插入
        if tmp == head { // 判断插入的位置
            preCur.Next = cur.Next // 将插入元素取出
            cur.Next = head
            head = cur
            cur = preCur.Next
        } else if tmp == cur {
            preCur = preCur.Next
            cur = cur.Next
        } else {
            preCur.Next = cur.Next // 将插入元素取出
            cur.Next = tmp
            preTmp.Next = cur
            cur = preCur.Next
        }

        // tmp重置为head位置
        tmp = head
    }

    return head
}

Review

Go and JSON： https://eager.io/blog/go-and-json/

介绍了关于golang中json的具体使用方式以及注意事项：

• 如何marshal和unmarshal
• 结构体的tags
  • 如何忽略一个为空值的字段（use omitempty）
  • 如何跳过一个字段（use -）
  • 嵌套字段
• 注意处理错误，如果实在不想处理可以用MustMarshal
• 解析成通用对象：interface{}
  • 需要在使用该数据时进行类型断言
• 数字的解析：默认为int64，如果想解析成int，可以在tag中声明为json:",string"

Tips

分享一些对git分支操作的方式：

• 修改提交信息

  • git commit --amend

• 拼写错误的分支名，需要重命名一个本地分支：可以使用 mv 命令类似重命名文件的方式重命名此分支：将其移动到具有正确名称的新位置。

  git branch -m feature-brunch feature-branch

• 重命名一个远程分支：我们需要从远程删除旧分支并推送新分支：

  • 先通过上面的命令重命名本地分支
  • 再删除远程分支：git push origin --delete feature-brunch
  • 推送新的分支：git push origin feature-branch

• 不小心将所有更改提交到主分支,需要将更改移动到新的分支

  • 先从主分支上开出一个新的分支，用于保存这些更改：git branch -b feature-branch
  • 切换回主分支， 将主分支回退到这些更改之前：git reset --hard HEAD~num
  • 切换到刚刚的新分支继续开发：git branch feature-branch

• 忘了将文件添加到最后一次提交，添加忘掉的文件：

  • 先直接添加该文件：git add missed-file.txt
  • 再运行：git commit --amend，直接保持不变

share

GitHub 技巧: https://mp.weixin.qq.com/s/1daFgoZjSARpDL2BU1q2qg

• 精准分享关键代码
  • 单行：可以在url后面加上#L行号
  • 多行：url后面加上#L开始行号-L结束行号
• gitattributes设置项目语言
  • 在项目的根目录下添加如下.gitattributes文件便可
    • 在里面：*.html linguist-language=JavaScript 主要意思是把所有html文件后缀的代码识别成js文件
• 查看自己项目的访问数据
  • 点击Insights，然后再点击Traffic
• trending排行榜
  • https://github.com/trending/ + language + ?since=daily
    • eg: https://github.com/trending/golang?since=daily
  • 或者：访问https://github.com/trending， 然后点击Trending

本周阅读

第一周：1, 5, 7
什么是CDN？https://mp.weixin.qq.com/s/K3zqr8Sjt00L9Hgip_7f7A
Go语言interface底层实现  https://mp.weixin.qq.com/s/v6W2Y24l9ghieAxiAdyc_A

红黑树到底是什么： https://mp.weixin.qq.com/s/MSB-vFGqNWB26kPydBJQmQ
最常见的Git错误都有哪些： https://mp.weixin.qq.com/s/apo4Io7xQU9hbw7yeS_LzQ
Golang 中的标签（Tags in Golang）: https://mp.weixin.qq.com/s/zSCNodT64z7OkOkzOxk5DA

 GitHub 技巧：https://mp.weixin.qq.com/s/1daFgoZjSARpDL2BU1q2qg
漫画：什么是微服务？https://mp.weixin.qq.com/s/FRVOYlgZCO524KwzQRohLA
漫画：什么是ZooKeeper？ https://mp.weixin.qq.com/s/Gs4rrF8wwRzF6EvyrF_o4A
漫画：什么是优先队列？https://mp.weixin.qq.com/s/4hXBw7sZ-NKs_asOQxS7gA
漫画：什么是分布式事务？https://mp.weixin.qq.com/s/oKOzvN49zOhl8cwliy3SEg