发表于

Vimium

关闭&恢复 tab

x - 关闭当前tab
X - 恢复关闭的网页

网页浏览

j - 向下滚动网页
k - 向上滚动网页

tab 切换

J - 左边一个 tab
K - 右边一个 tab

发表于 | 分类于

Algorithm

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs

解析
这个题目属于简单一类的，看到题目之后感觉很面熟，但是不会，想到的是排列组合，可能时间长一点会有点想法。没有去想，直接看的官方答案解析：

  • 首先通过递归，但是没有通过，以为时间复杂度 O(n²)
  • 对递归进行优化，存储递归中间的值，时间复杂度为 O(n)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    var memory:[Int] = []
    func climbStairs(_ n: Int) -> Int {
        
        for _ in 0..<n + 1 {
            memory.append(0)
        }
        return climbStairsMeomory(n)
    }
    
    
    func climbStairsMeomory(_ n: Int )  -> Int {
        if memory[n] > 0 {
            return memory[n]
        }
        
        if n == 1 {
            memory[n] = 1
        }else  if n == 2 {
            memory[n] = 2
        }else {
            memory[n] = climbStairsMeomory(n - 1) +  climbStairsMeomory(n - 2)
        }
        
        
        return memory[n]
    }
}

Review

Tip

Share

发表于 | 分类于

上周 ARTS 总结，A 做了很多，但是 RTS 明显时间安排不对，这周需要调整
周一： A
周二： R
周三： T
周四： S
周五： 整理总结 ARTS

Algorithm

题目一： 拥有最多糖果的孩子

给你一个数组 candies 和一个整数 extraCandies ，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。

对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子有 最多 的糖果。注意，允许有多个孩子同时拥有 最多 的糖果数目。

示例 1：

输入：candies = [2,3,5,1,3], extraCandies = 3
输出：[true,true,true,false,true]
解释：
孩子 1 有 2 个糖果，如果他得到所有额外的糖果（3个），那么他总共有 5 个糖果，他将成为拥有最多糖果的孩子。
孩子 2 有 3 个糖果，如果他得到至少 2 个额外糖果，那么他将成为拥有最多糖果的孩子。
孩子 3 有 5 个糖果，他已经是拥有最多糖果的孩子。
孩子 4 有 1 个糖果，即使他得到所有额外的糖果，他也只有 4 个糖果，无法成为拥有糖果最多的孩子。
孩子 5 有 3 个糖果，如果他得到至少 2 个额外糖果，那么他将成为拥有最多糖果的孩子。

示例 2：

输入：candies = [4,2,1,1,2], extraCandies = 1
输出：[true,false,false,false,false]
解释：只有 1 个额外糖果，所以不管额外糖果给谁，只有孩子 1 可以成为拥有糖果最多的孩子。

示例 3：

输入：candies = [12,1,12], extraCandies = 10
输出：[true,false,true]

提示：

2 <= candies.length <= 100
1 <= candies[i] <= 100
1 <= extraCandies <= 50

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kids-with-the-greatest-number-of-candies

解析：
相对简单：

  • 排序
  • 遍历比较

代码-Swif：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    func kidsWithCandies(_ candies: [Int], _ extraCandies: Int) -> [Bool] {
        var re:[Bool] = []
        let new = candies.sorted()
        guard  let max = new.last else {
            return re
        }
        
        for item in candies {
            if item + extraCandies >= max {
                re.append(true)
            }else {
                re.append(false)
            }
        }
        
        
        return re
    }
}

题目二： 面试题64. 求1+2+…+n

求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
示例 1：

输入: n = 3
输出: 6
示例 2：

输入: n = 9
输出: 45

限制：

1 <= n <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/qiu-12n-lcof

分析：
从题目要求来看，不能使用循环，所以想到了递归来求和，但是没有想出来怎么终止递归，参考之后知道了通过条件判断 || 和 && 的特性

代码-Swift:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
   var re = 0
   func sumNums(_ n: Int) -> Int {
       
       re += n
       let _ = n == 0 || sumNums(n - 1) > 0
       return re
       
   }
   
}

Review

API Pollution in Swift Modules

When you import a module into Swift code, you expect the result to be entirely additive. That is to say: the result to be entirely additive. Taht is to say: the potential for new functionality comes at no expense()

发表于 | 分类于

2020

ARTS（一）0525-0531
ARTS（二）0601-0607
ARTS（三）0608-0614
ARTS（四）0615-0621

ARTS 是什么？

ARTS 高效学习是耗子叔发起的一个高效学习方法，一个需要持续坚持的方法。ARTS 包含四块的内容：

  • Algorithm：主要是为了编程训练和学习。每周至少做一个 leetcode 的算法题（先从Easy开始，然后再Medium，最后才Hard）。进行编程训练，如果不训练你看再多的算法书，你依然不会做算法题，看完书后，你需要训练。关于做Leetcode的的优势，你可以看一下我在coolshell上的文章 Leetcode 编程训练 - 酷 壳 - CoolShell（一个小时以内）；
  • Review：主要是为了学习英文，如果你的英文不行，你基本上无缘技术高手。所以，需要你阅读并点评至少一篇英文技术文章，我个人最喜欢去的地方是 Medium（需要梯子，其他的可以社区的官方文档以及论文学习）以及各个公司的技术blog，如Netflix的（30min）；
  • Tip：主要是为了总结和归纳你在是常工作中所遇到的知识点。学习至少一个技术技巧。你在工作中遇到的问题，踩过的坑，学习的点滴知识（也可以学习【极客时间】上的实用课程）；
  • Share：主要是为了建立你的影响力，能够输出价值观。分享一篇有观点和思考的技术文章，也可以是技术总结的文章。
    ARTS 高效学习一个按周去做的项目，需要持续地坚持下去，这个项目可以让我们不断去反思、总结、归纳，以便让自己更高效地学习（下面的来自耗子叔的一些观点分享，值得学习）：

只有你开始自己思考，开始自己总结和归纳，开始找人交流讨论，开始践行，并开始对外输出，你才会掌握到真正的学习能力

所以，学习不是努力读更多的书，盲目追求阅读的速度和数量，这会让人产生低层次的勤奋和成长的感觉，这只是在使蛮力。要思辨，要践行，要总结和归纳，否则，你只是在机械地重复某件事（记忆知识），而不会有质的成长的。

关于举一反三的能力
重点是如何才能让自己拥有举一反三的能力，在这方面，耗子叔对自己训练如下：

对于一个场景，制造出各种不同的问题或难题；
对于一个问题，努力寻找尽可能多的解，并比较这些解的优劣；
对于一个解，努力寻找各种不同的测试案例，以图让其健壮。
举一反三的能力，可以分解为：

联想能力：这种能力的锻炼需要你平时就在不停地思考同一个事物的不同的用法，或是联想与之有关的别的事物。对于软件开发和技术学习也一样；
抽象能力：抽象能力是举一反三的基本技能。平时你解决问题的时候，如果你能对这个问题进行抽象，你就可以获得更多的表现形式。抽象能力需要找到解决问题的通用模型，比如数学就是对现实世界的一种抽象。只要我们能把现实世界的各种问题建立成数据模型（如，建立各种维度的向量），我们就可以用数学来求解，这也是机

作者：柳年思水
链接：https://www.jianshu.com/p/951607ebbba0
来源：简书

发表于 | 分类于

Algorithm

题目一： 整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

示例 1:
输入: 123 输出: 321
示例 2:
输入: -123 输出: -32
示例 3:
输入: 120 输出: 21

注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-integer

分析

一开始想通过移位的方式去解决，终究没有找到方法，可能对移位操作没那么熟悉的缘故。参考了评论里的一种解决方案：

  • 对 10 取余操作得到个位数
  • 对 10 取整，去掉个位数字
  • 将通过取余得到的数字追加到反转的后面

代码 - Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    func reverse(_ x: Int) -> Int {
        var reverseNum = 0
        var numbers = x
        while numbers != 0 {
            let temp = numbers % 10
            numbers = numbers / 10
            reverseNum = reverseNum * 10 + temp
        }

        if reverseNum > Int32.max || reverseNum < Int32.min {
            return 0
        }
        return reverseNum
         
    }
}

题目二： 回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:

输入: 121 输出: true
示例 2:

输入: -121 输出: false 解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:

输入: 10 输出: false 解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶:

你能不将整数转为字符串来解决这个问题吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-number

分析：
第一反应就是用整数反转，然后比较大小

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    func isPalindrome(_ x: Int) -> Bool {
        if x < 0 {
            return false 
        }
        var reverseNumber = 0
        var num = x
        while (num != 0) {
            let temp = num % 10
            num = num / 10
            reverseNumber = reverseNumber * 10 + temp
        }

        if x == reverseNumber {
            return true 
        }else  {
            return false
        }
    }
}

方法二： 转化为字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    func isPalindrome(_ x: Int) -> Bool {
      if x <  0 {return false}
      let numStr = "\(x)"
      for  n in 0..<numStr.count {
          if n > numStr.count / 2 {
              return true 
          }
          if  numStr[n] != numStr[numStr.count - n - 1] {
              return false 
          }
      }
      return true
    }
}

extension String
{
    subscript(Index:Int)->String
    {
        let begin=self.startIndex
        let start=self.index(begin, offsetBy: Index)
        let end=self.index(begin, offsetBy: Index+1)
        let range: Range = start..<end
         return String(self[range])
        
    }
}

题目三：寻找重复数

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:
输入: [1,3,4,2,2]
输出: 2

示例 2:
输入: [3,1,3,4,2]
输出: 3

说明：
不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-duplicate-number

分析：
先排序，然后相邻数字对比，对比到相等就返回那个数字

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    func findDuplicate(_ nums: [Int]) -> Int {
        let sortedNums = nums.sorted()
        var preNum = 0
        for curNum in sortedNums {
            if preNum == curNum  {
                return preNum
            }
            preNum = curNum
        }
        return 0
    }
}

题目四：罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:
输入: "III" 输出: 3

示例 2:
输入: "IV" 输出: 4

示例 3:
输入: "IX" 输出: 9

示例 4:
输入: "LVIII" 输出: 58 解释: L = 50, V= 5, III = 3.

示例 5:
输入: "MCMXCIV" 输出: 1994 解释: M = 1000, CM = 900, XC = 90, IV = 4.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/roman-to-integer

分析：
分析了一下逻辑，没有发现什么好的方案，最后通过看评论，使用了暴力破解法。自己也想过这个方法，但是考虑的条件判断不成熟（偷懒了，不想考虑暴力破解的判断了），所以就参照一个评论中的解法，相对简单的判断条件

代码-Swift：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    func romanToInt(_ s: String) -> Int {
        
        let romanMap:[Character: Int] = ["I":1, "V":5, "X":10, "L":50, "C":100, "D":500, "M":1000]
        var lastNumber = 0
        var sum = 0
        for c in  s {
            if let number = romanMap[c] {
                sum += number
                if number > lastNumber {
                    sum -= 2 * lastNumber
                }
                
                lastNumber = number
            }
            
        }
        
        return sum
        
        
    }
}

题目五： 和可被 K 整除的子数组

给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。

示例：
输入：A = [4,5,0,-2,-3,1], K = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 K = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

提示：

  • 1 <= A.length <= 30000
  • -10000 <= A[i] <= 10000
  • 2 <= K <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subarray-sums-divisible-by-k

解析：

一开始想用暴力破解法，但是由于限制了，不能通过。然后通过看官方解答，知道这了需要两个知识点：

  • 同余定理
  • 前缀和 prefix sum
    到写完这个题目，其实对于其真正解法还是没有领会，后面再看看（3 h）

代码-Swift:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    func subarraysDivByK(_ A: [Int], _ K: Int) -> Int {
        var record = [Int:Int]()
        record[0] = 1
        var sum = 0
        var ans = 0
        
        for elem in A {
            sum += elem
            let modulus = (sum % K  + K) % K
            let same = record[modulus] ?? 0
            ans += same
            record[modulus] = same + 1
        }
        return ans
    }
}

题目六：字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例:
s = "3[a]2[bc]", 返回 "aaabcbc". s = "3[a2[c]]", 返回 "accaccacc". s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-string

解析：
拿到题目想到的是数据结构-栈和递归算法，奈何栈结构不熟悉，递归也不熟悉，然后就开始先写遍历，然后遇到了第一个“]” 开始回溯处理，写了一个函数，定下输入 xxxx 和 输出 xxxx，比如这个题，我用了 s = “3[a2[c]]”做例子，然后遍历字符串的时候到了 3[a2[c] 这个时候，将这个字符串作为一个函数的输入，其输出为： 3[acc,然后就去实现这样的函数，通过不断的递归条件尝试，最终实验出了这个函数。时间大约 3 h。

代码-Swift：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class Solution {
    func decodeString(_ s: String) -> String {
        
        var tempStr = ""
        for c in s {
            tempStr.append(c)
            if c == "]" {
                tempStr = subString(str: tempStr, ch: "]")
            }
            
        }
        return tempStr
    }
    
    func subString(str: String,
                   ch: Character?,
                   strC: String? = nil,
                   number: String? = nil,
                   isOver: Bool = false) -> String  {
        
        if  isOver  {
            var temp = ""
            guard let num = Int(number ?? "xxx"), let strc_ = strC else {return ""}
            
            for _ in 0..<num {
                temp = temp + strc_
            }
            return  str + temp
        }
        var newStr = str
        let last = newStr.remove(at: newStr.index(before: newStr.endIndex))
        if let asValue = last.asciiValue , isNumber(asciiValue: asValue){
            guard let n = last.wholeNumberValue else {
                return ""
            }
            var num: String = "\(n)"
            if let n_ = number {
                let newN = "\(n)" + "\(n_)"
                num = newN
            }
            
            if newStr.last == nil || newStr.count == 0 {
                return subString(str: newStr, ch: last, strC: strC, number: num, isOver:  true)
            } else if let last_ = newStr.last?.asciiValue ,!isNumber(asciiValue: last_) {
                return subString(str: newStr, ch: last, strC: strC, number: num, isOver:  true)
                
            }else {
                return subString(str: newStr, ch: last, strC: strC, number: num)
            }
            
        }else if let asValue = last.asciiValue , isAlphabet(asciiValue: asValue) {
            
            // 字符串后，继续遍历
            var s = ""
            if let s_ = strC {
                s = s_
            }
            return  subString(str: newStr, ch: last, strC: "\(last)" + s)
        }else {
            // 其他字符，直接丢弃（这里主要是 [ 、]）
            return  subString(str: newStr, ch: last, strC:  strC)
        }
        
    }
    
    func isNumber(asciiValue: UInt8) -> Bool {
        if asciiValue >= 48 && asciiValue <= 57 {
            return true
        }
        return false
    }
    
    func isAlphabet(asciiValue: UInt8) -> Bool{
        if (asciiValue >= 97 && asciiValue <= 122)  || (asciiValue >= 65 && asciiValue <= 90) {
            return true
        }
        return false
    }
}

题目七： 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber

分析：
这到期没解出来，有关动态规划和数组滚动问题

代码-Swift：

1
2
3
4
5
6
7
8
9
10
11
12
13

 class Solution {
    func rob(_ nums: [Int]) -> Int {
        var prev = 0
        var curr = 0
        for i in nums {
            let tmp = curr
            curr = max(prev + i, curr)
            prev = tmp
        }
        return curr
    }
}

题目八： 合并排序的数组

给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。

初始化 A 和 B 的元素数量分别为 m 和 n。

示例:

输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6], n = 3

输出: [1,2,2,3,5,6]
说明:

A.length == n + m

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sorted-merge-lcci

分析：
将 B 数组追加到 A 数组后面，然后整体排序，提交之后竟然过了！看到还有双指针的方法，后面试试吧

代码-Swift

1
2
3
4
5
6
7
8
9
class Solution {
    func merge(_ A: inout [Int], _ m: Int, _ B: [Int], _ n: Int) {
        for i in 0..<n {
            A[m + i] = B[i]
        }
        
        A.sort()
    }
}

Review

Hashable\Hasher

When you make a Genius Bar reservation at an Apple Store, you’re instructed to show up at a particular time of day and check in with the concierge. After directing you to pull up at a stool, the concierge adds you to the queue and makes a note about how to identify you.

According to anonymous reports from former retail employee, there are strict guidelines about how customers can be described. Nothing about their physical appearance is used: age, gender, ethnicity, height – not even that hair color. Instead, all customers are described by their clothing, as in “Person with black turtleneck, jeans, and glasses”.

This practice of describing customers has a lot in common with a hashing function in programming. Like any good hashing function, it’s consistent and easy to compute, and can be used to quickly find what (or who) you’re looking for. Much better than a queue, I think you’ll agree!

Our topic this week is Hasable and its new related type, Hasher . Together, they comprise the functionality underlying two of Swift’s most beloved collection classes: Dictionary and Set.

Let’s say you have a list of objects that can be compared for equality with one another. To find a particular object in that list, you iterate all the elements until you find a match. As you add more elements to the array, the average amount of time necessary to find any one of them increases linearly(O(n)).

If you instead store those objects in a set, you can theoretically find any one of them in constant time(O(1)) – that is, a lookup on a set with 10 elements takes the same amount of time as a lookup on a set with 10, 000. How does this work? Instead of storing objects sequentially, a set computes a hash as an index based on the contents of the object. When you perform a lookup of an object in a set, you use the same function to compute a new has and look for the object there.

Two objects produce a has collision when they have the same has value but aren’t equal. When a collision occurs on insertion, they’re stored in a list at that address. The higher the rate of collision between objects, the more linear the performance of a hash collection becomes.

Hashable
In Swift， Array provides the standard interface for lists and Set for sets. In order for an object to be stored in a Set, its type must conform to Hashable(any by extension, Equatable). Swift’s standard map interface, Dictionary has a similar constraint on its associated Key type.

In previous versions of the language, it took quite a bit of boilerplate code to satisfy the requirements for storing a custom type in a Set or Dictionary.

Consider the following Color type, which represents a color using 8-bit values for red, green, and blue intensity:

1
2
3
4
5
struct Color {
    let red: UInt8
    let green: UInt8
    let blue: UInt8
}

To conform to Equatable, you had to provide an implementation for the == operator. To conform to Hashable, you had to provide an implementation of the computed hasValue property:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Swift < 4.1
extension Color: Equatable {
    static func == (lhs: Color, rhs: Color) -> Bool {
        return lhs.red == rhs.red &&
                lhs.green == rhs.green &&
                lhs.blue == rhs.blue
    }
}

extension Color: Hashable {
    var hashValue: Int {
        return self.red.hashValue ^ self.green.hashValue ^ self.blue.hashValue
    }
}

For most developers, implementing Hashable was a speed bump on the way to getting real work done, so they’re simple XOR over all the stored properties and call it a day.

One downside to this approach is its high rate of hash collisions. Because XOR is commutative, colors as different as cyan and yellow produce a hash collision:

1
2
3
4
5
//Swift < 4.2
let cyan = Color(red: 0x00, green: 0xFF, blue: 0xFF)
let yellow = Color(red: 0xFF, green: 0xFF, blue: 0x00)

cyan.hashValue == yellow.hashValue // true, collision

Most of the time, this isn’t a problem; modern computers are so powerful that you have to get a lot of implementation detail wrong in order to notice any decrease in performance.

But that’s not to say that detail don’t matter – they often matter immensely. More on that later.

Automatic Synthesis of Hashable Conformance

As of Swift4.1, the compiler automatically synthesizes conformance to the Equatable and Hashable protocols for types that adopt these protocols in their declaration if their members also conform to those protocols.

In addition to being a huge boost to developer productivity, this can drastically reduce the size of a codebase. For instance, our Color example from before - is now 1/3 of its original size:

1
2
3
4
5
6
// Swift >= 4.1
struct Color: Hashable {
    let red: UInt8
    let green: UInt8
    let blue: UInt8
}

Despite these unambiguous improvements to the language, there was still a lingering question about some of the implementation details.

In his Swift Evolution proposal SE-0815: Synthesizing Equatable and Hashable conformance, Tony Allevato offered this note about hashing functions:
The choice of hash function is left as an implementation detail, not a fixed part of the design; as such, users should not depend on specific characteristics of its behavior. The most likely implementation would call the standard library's _mixInt function on each member's hash value and then combine them with exclusive - or (^), which mirrors the way Collection types are hashed today.

Fortunately, it didn’t take long for Swift to settle on hash function. We got our answer in the very next release:

Hasher

Swift 4.2 refines Hashable even further by introducing the Hasher type and adopting a new universal hashing functions.

From the Swift Evolution proposal, SE-0206: Hashable Enhancements:

With a good hash function, simple lookups, insertions and removals take constant time on average. However, when the hash function isn't carefully chosen to suit the data, the expected time of such operations can become proportional to eh number of elements sorted in the table.

As Karoy Lorentey and Vincent Esche note, the main draw of hash-based collection like Set and Dictionary is their ability to look up values in constant time. If the hash function doesn’t produce an event distribution of values, these collections effectively become linked lists.

Swift 4.2 implements hashing based on the SipHash family of pseudorandom functions, specifically SipHash-1-3 and SipHash-2-4, with 1 or 2 rounds of hashing per message block and 3 or 4 rounds of finalization, respectively.

Now if you want to customize how your type implememnts Hashable, you can override the hash(into:) method instead of hashValue. The hash(into:) method passes a Hasher object by reference, which you call combine(_:) on to add the essential state information of your type.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Swift 
struct Color: Hashable {
    let red: UInt8
    let green: UInt8
    let blue: UInt8
    
    
    // Synthesized by compiler
    func hash(into hasher: inout Hasher) {
        hasher.combine(self.red)
        hasher.combine(self.green)
        hasher.combine(self.blue)
    }
    
    //Default implementation from protocol extension
    var hashValue: Int {
        var hasher = Hasher()
        self.hash(into: &hasher)
        return hasher.finalize()
    }
}

By abstracting away low-level bit manipulation details, developers automatically take advantage of Swift’s built-in hashing function, which has the extra benefit of not reproducing the collisions we had with ourt original XOR-based implementation:

1
2
3
4
5
//Swift >= 4.2
let cyan = Color(red: 0x00, green: 0xFF, blue: 0xFF)
let yellow = Color(red: 0xFF, green: 0xFF, blue: 0x00)

cyan.hashValue == yellow.hashValue // false, no collision

Customizing Hash Function

By default, Swift uses a universal hash function that reduces a sequence of bytes to a single integer.

However, you can improve on this by tailoring your hash function on your domain. For example, if you were writing a program to play a board game like chess or go, you might implement Zobrist hashing to quickly store the game state.

Guarding Against Hash-Flooding

Selecting a cryptographic algorithm like SipHash helps protect against hash-flooding Dos attacks, which deliberately try to generate hash collisions in an attempt to enforce the worst case of hashing data structures and cause a program to slow to halt. This caused a bunch of problems for the web in the early 2010’s.

You shouldn’t rely on specific hash values or save them access executions. On the rare occasion that you would need deterministic behavior, you can set the flat SWIFT_DETERMINISTIC_HASHING to disable random hash seeds.

The challenge of programming analogies is they normalize antisocial behavior by way of edge case.

We excel as software engineers when we can think through all the ways that an attacker might leverage a particular behavior to some sinister end - as in the case of hash-flooding DoS attacks. But by doing so, we risk failing as humans when we apply that knowledge AFK.

That is to say… I’m not in any way encouraging you, dear reader, to coordinate outfits with your besties the next time you visit your local Apple retailer in an attempt to sow confusion and discord among Geniuses.

Please don’t.

Instead, please let your takeaway be this:

If you’re waiting at the Genius Bar, stay away from anyone wearing the same color shirt as you. It’ll make thing a lot easier for everyone.

Tip

Out of Memory
本来想写内存检测的，但是感觉知识太深，还是从简单的开始吧！查了一些 ARTS 的文章，感觉没有什么好参考的，有几篇看上去像敷衍一样，还是自己写算了。
作为一个 iOS RD，那就从 Swift Tips 中选取一个吧！

柯里化 (Currying)

参考：https://www.jianshu.com/p/b3195e0c68a7

发表于

读完本书后你应该会回答如下几个问题：

  • 如何避免由计算机表示数字的方式导致的奇怪的数字错误；
  • 通过一些聪明的小窍门来优化你的 C 代码，以充分利用现代处理器和存储系统的设计；
  • 了解编译器是如何实现过程调用的，以及如何利用这些知识避免缓冲区溢出错误带来的安全漏洞
  • 如何识别和避免链接时哪些令人讨厌的错误
  • 如何编写自己的 Unix 外壳、自己的动态存储分配包
  • 如何编写自己的 web 服务器
  • 认识并发带来的希望和陷阱，当单个芯片上集成多个处理器核时，这个主题变得越来越重要

1.1 信息就是 位 + 上下文

源程序 实际上就是 0 和 1 组成的位序列， 8 个位组成了一个字节，每个字节表示程序中的某个文本字符;
ASCII 大部分现代系统都使用 ASCII 码来表示文本字符，这种方式实际上就是用一个唯一的单字节大小的整数值来表示每个字符。

发表于 | 分类于

使用Swift实现数据结构——栈，同时，实现栈的操作：push、pop和peek。

栈的基本操作

栈结构类似于数组，只不过其操作受限。对栈的操作有三种：

  1. 向栈顶部添加元素，称为 push 操作；
  2. 将栈顶元素移除，称为 pop 操作；
  3. 获取栈顶元素，称为 peek 操作

为什么会有这样的操作呢？因为在许多算法中，我们需要向一个临时列表中添加一个元素，在后续的操作中又要将这个元素移除掉，比如 iOS app 中的导航栏的 push 和 pop 操作就是这样子的。

Stack 的操作顺序是后进先出，即最后一个入栈的元素第一个被移除。

Swift 实现栈

STACK

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
```
### PUSH

### POP

### PEEK



## 测试

## 拓展
```Swift
public struct Stack<T: Comparable> {
    fileprivate var array = [T]()
    
    public var isEmpty: Bool {
        return array.isEmpty
    }
    
    public var count: Int {
        return array.count
    }
    
    public mutating func push(_ element: T) {
        array.append(element)
    }
    
    public mutating func pop() -> T? {
        return array.popLast()
    }
    
    public var peek: T? {
        return array.last
    }
}