ARTS 第19周

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

有疑问加站长微信联系(非本文作者)

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
• 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传