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
-
) - 嵌套字段
- 如何忽略一个为空值的字段(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
结束行号
- 单行:可以在url后面加上
- gitattributes设置项目语言
- 在项目的根目录下添加如下.gitattributes文件便可
- 在里面:
*.html linguist-language=JavaScript
主要意思是把所有html文件后缀的代码识别成js文件
- 在里面:
- 在项目的根目录下添加如下.gitattributes文件便可
- 查看自己项目的访问数据
- 点击Insights,然后再点击Traffic
- trending排行榜
-
https://github.com/trending/
+ language +?since=daily
- eg:
https://github.com/trending/golang?since=daily
- eg:
- 或者:访问
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
有疑问加站长微信联系(非本文作者)