ARTS(1)

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

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

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

代码：

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
        }
    }
}

方法二：转化为字符串

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

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

代码：

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：

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:

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：

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：


 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

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:

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:

// 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:

//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:

// 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.

// 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:

//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

Algorithm

题目一： 整数反转

题目二： 回文数

题目三：寻找重复数

题目四：罗马数字转整数

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

题目六：字符串解码

题目七： 打家劫舍

题目八： 合并排序的数组

Review

Tip

柯里化 (Currying)

题目一：整数反转

题目二：回文数

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

题目七：打家劫舍

题目八：合并排序的数组