ARTS 第20周分享

[TOC]

Algorithm

164. Maximum Gap

[hard]

[题目描述]

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Return 0 if the array contains less than 2 elements.

Example 1:

Input: [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either
             (3,6) or (6,9) has the maximum difference 3.

[解题思路]

• 先将数组排序，然后遍历找出最大的Gap即可
• 主要是选择合适的排序方式，时间复杂度为线性，我选择了基数排序

[参考代码]

func maximumGap(nums []int) int {
    // 排除少于两个元素的情况
    if len(nums) < 2 {
        return 0
    }

    // 先将数组排序，基数排序（线性时间复杂度）
    radixSort(nums)
    // 然后遍历整个数组相邻的元素，记录最大的Gap
    gap := 0
    for i:=1; i<len(nums); i++ {
        tmpGap := nums[i]-nums[i-1]
        if tmpGap > gap {
            gap = tmpGap
        }
    }
    return gap
}

func radixSort(array []int) {
    // 桶排序的一个升级版，新建10个0-9的桶，将数组中的所有元素按照个位数分别放入到桶中
    // 然后再依次从桶中取出放回原数组。
    // 重复以上步骤，只是将个位改成十位，百位，知道最高位。

    // 创建桶
    bucketCount := 10
    bucket := make([][]int, bucketCount)
    for i := 0; i < bucketCount; i++ {
        bucket[i] = make([]int, 0)
    }

    // 找出数组中的最大数，从而确定基数
    radix := 0
    for _, v := range array {
        if radix < v {
            radix = v
        }
    }
    radixLen := len(strconv.Itoa(radix))
    bit := 1
    for round:= 0; round<radixLen; round++ {
        // 将数组中的所有元素按照个位数分别放入到桶中

        for _, v := range array {
            bucNum := v / bit % 10
            bucket[bucNum] = append(bucket[bucNum], v)
        }
        bit *= 10

        // 然后再依次从桶中取出放回原数组。
        index := 0
        for num := 0; num < bucketCount; num++ {
            for _, v := range bucket[num] {
                array[index] = v
                index++
            }
        }

        // 将桶内元素清空
        for i := 0; i < bucketCount; i++ {
            bucket[i] = make([]int, 0)
        }
    }
}

179. Largest Number

[medium]

[题目描述]

Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:

Input: [3,30,34,5,9]
Output: "9534330"

[解题思路]

• 只需要将数组先按照特殊的规则排序，然后再拼接成字符串即可
• 核心是排序的规则：将两个数(A, B)按照前后相反的方式拼接成两个数：AB, BA ，比较AB 和BA的大小，决定排序顺序。

[参考代码]

func largestNumber(nums []int) (res string) {
    // 将数组排序
    // 1. 将[]int 转成 []string
    var numsStr numsStr
    for i:=0; i<len(nums); i++ {
        numsStr = append(numsStr, strconv.Itoa(nums[i]))
    }

    // 2. 将数组排序
    sort.Sort(numsStr)

    // 拼接
    for i:=0; i<len(numsStr); i++ {
        res += numsStr[i]
    }
    if res[0] == '0' {
        return "0"
    }
    return
}

type numsStr []string

func (ns numsStr) Len() int {
    return len(ns)
}

func (ns numsStr) Less(i, j int) bool {
    a, b := ns[i]+ns[j], ns[j]+ns[i]
    for i := 0; i < len(a); i++ {
        if a[i] > b[i] {
            return true
        } else if a[i] < b[i] {
            return false
        }
    }
    return false
}

func (ns numsStr) Swap(i, j int) {
    ns[i], ns[j] = ns[j], ns[i]
}

Review

golang Mutex : https://golangbot.com/mutex/

• This section of code which modifies shared resources is called critical section. (wiki: https://en.wikipedia.org/wiki/Critical_section )
• the final value of x is 1 or 2 depending on how context switching happens.
• This type of undesirable situation where the output of the program depends on the sequence of execution of Goroutines is called race condition.
• In general use channels when Goroutines need to communicate with each other and mutexes when only one Goroutine should access the critical section of code.
• To choose the tool for the problem and do not try to fit the problem for the tool

Tips

• golang 中 比较字符串单个字符值的方法：

  go中由于每一个字符串实际上是一个slice，所以当你拿一个字符串中的单个字符与某字符对比是会报error的，比如

str := "abcd"
if str[0] == "a" {
    // do something
}

原因是你不能拿一个byte类型的值与[]byte 做对比。

所以就需要用一种到单引号'a' : str[0] == 'a'

• golang 中一共有三种引号：
  • 双引号(single quotes)，是用来表示字符串string，其实质是一个byte类型的数组，即[]byte
  • 单引号(double quotes)，表示rune类型, 而rune本就是uint8类型（即是byte），是指：码点字面量（Unicode code point），不做任何转义的原始内容。
  • 反引号(back quotes)，用来创建原生的字符串字面量，它可以由多行组成，但不支持任何转义序列。

share

• 如何优雅的关闭channel：https://mp.weixin.qq.com/s/TtiaTA5bDqpAz2VihmI3eg

• 首先得知道：

  • 关闭已经关闭的channel会导致panic，所以在closer(关闭者)不知道channel是否已经关闭的情况下去关闭channel是很危险的
  • 发送值到已经关闭的channel会导致panic，所以如果sender(发送者)在不知道channel是否已经关闭的情况下去向channel发送值是很危险的

• 在使用Go channel的时候，一个适用的原则是不要从接收端关闭channel，也不要关闭有多个并发发送者的channel。换句话说，如果sender(发送者)只是唯一的sender或者是channel最后一个活跃的sender，那么你应该在sender的goroutine关闭channel，从而通知receiver(s)(接收者们)已经没有值可以读了。维持这条原则将保证永远不会发生向一个已经关闭的channel发送值或者关闭一个已经关闭的channel。

• 我们应该要理解为什么Go不支持内置SafeSend和SafeClose函数，原因就在于并不推荐从接收端或者多个并发发送端关闭channel。

  • M个receivers，一个sender，sender通过关闭data channel说“不再发送”
    这是最简单的场景了，就只是当sender不想再发送的时候让sender关闭data 来关闭channel

  • 一个receiver，N个sender，receiver通过关闭一个额外的signal channel说“请停止发送”。

    对于额外的signal channel来说，它的sender是data channel的receiver。这个额外的signal channel被它唯一的sender关闭，遵守了channel closing principle。

  • M个receiver，N个sender，它们当中任意一个通过通知一个moderator（仲裁者）关闭额外的signal channel来说“让我们结束游戏吧”。

本周阅读

第二周：1, 4, 5, 7
三星的区块链野心：qshttps://mp.weixin.qq.com/s/wLMFWGXzsZLTW9pDXhkshQ
漫话：如何给女朋友解释鸿蒙OS是怎样实现跨平台的？https://mp.weixin.qq.com/s/spcJhT-Vvew3RtSQUuoeQg

新版本Golang的包管理入门教程: https://juejin.im/post/5c9c8c4fe51d450bc9547ba1

如何优雅地关闭Go channel: https://mp.weixin.qq.com/s/TtiaTA5bDqpAz2VihmI3eg

golang mutex: https://golangbot.com/mutex/