ARTS 第19周

陈卧虫 · · 1270 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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

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

本文来自:简书

感谢作者:陈卧虫

查看原文:ARTS 第19周

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1270 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传