Posts

将 pivot 索引定义为：左边的数字之和等于索引右边的数字之和。 Input: nums = [1, 7, 3, 6, 5, 6] Output: 3 Explanation: 1 + 7 + 3 = 5 + 6 Input: nums = [1, 2, 3] Output: -1 Explanation: There is no index that satisfies the conditions in the problem statement. Note: The length of nums will be in the range [0, 10000]. Each element nums[i] will be an integer in the range [-1000, 1000]. 关键点 动态规划 数组的和 - 中轴数 = 中轴数左边数组的和 * 2 解答 func findPivot(_ array: [Int]) -> Int { // 数组和 let sum = array.reduce(0, +) // 左侧数组和 var leftSum = 0 for (key, value) in array.enumerated() { if sum - value == leftSum * 2 { return key } leftSum += value } return -1 } let array = [1, 7, 3, 6, 5, 6] search(array) // 3 References 找到数组中左右两边的和相等的 pivot 的下标 Find Pivot Index – EOF – ...

思路 m 进制 -> 十进制 -> n 进制 利用柯里化生成函数（炫技 🐶） m 进制 -> 十进制 // carry 范围值: 2-36 // origin 范围值: 0-9 [ascii 48-58], A-Z [65-90], a-z [97-122] func carryToDecimalism(_ carry: Int) -> (_ origin: String) -> Int { return { origin in // 得到字符串对应的 ascii 码 let asciis = origin.uppercased().unicodeScalars.map { Int($0.value) } // 累加每一位 let result = asciis.reversed().enumerated().map { (index, ascii) -> Int in var standard: Int if 65 <= ascii && ascii <= 90 { standard = ascii - 65 + 10 } else { standard = ascii - 48 } return standard * Int(pow(Double(carry), Double(index))) }.reduce(0, +) return result } } let 十六进制转十进制 = carryToDecimalism(16) print(十六进制转十进制("1a")) // 26 let 二进制转十进制 = carryToDecimalism(2) print(二进制转十进制("110")) // 6 十进制 -> n 进制 func decimalismToCarry(_ carry: Int) -> (_ origin: Int) -> String { return { origin in var result = [Int]() var remain = origin while remain > 0 { result.append(remain % carry) remain /= carry } if carry <= 10 { return result.reversed().map(String.init).joined() } else { return result.reversed().map { i -> String in return i < 10 ? String(i) : String(UnicodeScalar(i + 55)!) }.joined() } } } let 十进制转二进制 = decimalismToCarry(2) print(十进制转二进制(26)) // "11010" References ASCII 码对照表 – EOF – ...

打印 n! 的结果（1 <= n <= 100）。注意：当 n > 20 时 64 位的 Int 将无法直接存储结果。 思路 将大数字用 数组 形式表示。比如 987 使用 [9,8,7] 代替。 每一位乘以 n，再进行进位操作，得到新数组。 let nums = [9, 8, 7] let tmpNums = nums.map { $0 * 2 } // [18, 16, 14] // 遍历 tmpNums 每一个数字，进行进制操作 [18, 16, 14] -> [18, 17, 4] -> [19, 7, 4] -> [1, 9, 7, 4] print(tmpNums.map(String.init).joined()) // 1974 解答项目 func extraLongFactorials(n: Int) -> Void { guard n > 0 else { return } // 结果数组 var result: [Int] = [1] for index in 1...n { // 数组翻转 从低位开始每一位乘以本次的数字 let tmpNums = result.reversed().map { $0 * index } // 进位数 var carryNum = 0 // 重置结果 result = [] tmpNums.forEach { // 每一位加上上一位的进的数 let tmpNum = $0 + carryNum // 向下一位进制的数 carryNum = tmpNum / 10 // 本位实际剩下的数 插入结果 result.append(tmpNum % 10) } // 处理剩余进位数 进位数是可能大于 100 while carryNum > 0 { // 逐渐插入进制 result.append(carryNum % 10) carryNum /= 10 } // 翻转回数组 result = result.reversed() } // 连接字符串 print(result.map(String.init).joined()) } References Extra Long Factorials | HackerRank Swift 3 calculate factorial number. Result becomes too high? – EOF – ...

这次以 fastlane 为例，尝试项目中有什么事情可以被自动完成。 fastlane 是 Ruby scripts 的集合，安装方法不多说了见 官网文档。 fastlane 中有但不限于以下工具集： produce 同时在 Apple Developer Portal 和 App Store Connect 中创建新的 iOS apps。 cert 自动创建和维护 iOS 签名证书。 sigh 创建，更新，下载和修复配置文件。 snapshot 自动在每台设备上获取 iOS 应用的本地化屏幕截图。 frameit 将您的屏幕截图放入正确的设备框架中。 gym 构建和打包您的 iOS apps。 deliver 将截图，元数据和您的应用上传到 App Store。 pem 自动生成并更新推送通知配置文件。 spaceship 一个 Ruby 库能够访问苹果开发者中心和应用商店连接 api。 pilot 自动化 TestFlight 部署并管理测试用户。 boarding 邀请 beta 测试人员。 match 使用 Git 同步整个团队的证书和配置文件。 scan 运行 app 测试。 实验环境：Xcode 10.1、Swift 4.2、fastlane 2.116.1、$99 开发者账户 ...

再读王巍的【Swifter - Swift 开发者必备 Tips】，看看有什么新收获。 柯里化（Currying） 柯里化 是把接受多个参数的函数变换成接受一个单一参数（最初函数的第一个参数）的函数，并且返回接受余下的参数而且返回结果的新函数的技术，这个词自己是第一次见到。 自己的理解就是：把接受多个参数的函数变换为，先接受一个参数，然后返回一个函数，这个函数再接受其他参数。 两个细节： 只有一个参数，并且这个参数是该函数的第一个参数。必须按照参数的定义顺序来调用柯里化函数。 柯里化函数的函数体只会执行一次，只会在调用完最后一个参数的时候执行柯里化函数体。 /// 一个数加 x 的函数 func addTo(_ adder: Int) -> (Int) -> Int { return { adder + $0 } } // +2 let addTwo = addTo(2) let result = addTwo(6) // 8 // +10 let addTen = addTo(10) addTen(6) // 16 柯里化是一种量产相似方法的好办法，可以通过柯里化一个方法模板来避免写出很多重复代码，也方便了今后维护。 书中还提到了一个封装 Selector 的例子，但是没懂，欢迎指教。 Reference: Swift 函数柯里化介绍及使用场景 将 protocol 的方法声明为 mutating protocol 不仅可以被 class 类型实现，也适用于 struct 和 enum。因为这个原因就要考虑定义的方法是否应该使用 mutating 来修饰。在 protocl 中使用 mutating 修饰的方法，对于 class 的实现是完全透明的。 多元组（Tuple） python 中有见过类似。 /// 交互数据 func swapMe<T>(_ a: inout T, _ b: inout T) { (a, b) = (b, a) } var a = 10 var b = 20 swapMe(&a, &b) // a: 20 b: 10 /// 可读的返回值 let rect = CGRect(x: 0, y: 0, width: 100, height: 100) let (slice, remainder) = rect.divided(atDistance: 20, from: .minYEdge) // slice {x 0 y 0 w 100 h 20} // remainder {x 0 y 20 w 100 h 80} @autoclosure 和 ?? @autoclosure 做的事情就是把一句表达式自动的封装成一个闭包（closure）。这样有时候在语法上看起来就会非常漂亮。 ...

在 GitHub Trending 中总是看到 mxcl/PromiseKit 它是主要解决的是 “回调地狱” 的问题，决定尝试用一下。 环境：Swift 4.2、PromiseKit 6 then and done 下面是一个典型的 promise 链式（chain）调用： firstly { login() }.then { creds in fetch(avatar: creds.user) }.done { image in self.imageView = image } 如果这段代码使用完成回调（completion handler）实现，他将是： login { creds, error in if let creds = creds { fetch(avatar: creds.user) { image, error in if let image = image { self.imageView = image } } } } then 是完成回调的另一种方式，但是它更丰富。在处级阶段的理解，它更具有可读性。上面的 promise chain 更容易阅读和理解：一个异步操作接着另一个，一行接一行。它与程序代码非常接近，因为我们很容易得到 Swift 的当前状态。 ...

重新翻阅的自己工作邮件的发件箱，回顾一年工作。新年伊始自己还是在开发 P 项目的 iOS App，开始写 Q&A 功能。一些不算太难的 tableView 布局的需求，对我来说，都是头大的问题。 这段时期招聘时的面试，竟成为我学习 App 开发的一扇小窗。 年前收到了奖金还是挺开心的。leader 新年寄语： 要发声，要当主力 当有好的想法时，要学会说服别人 要有耐心，Yifan 需要时间的沉淀 前两点意思差不多，这段时间思想上困扰我的是：自己对自己的定位是一个初级工程师，认为会的东西、经验不多，见识少，我尊重比我年长的工程师的想法与观点，也相信他们是经过长远思考过的。这个思维设定，我觉得没有什么问题。但是也许有人忽略了 责任，对方案负责，对项目负责。开发方案一再重建性修改，接口结构没有规范。 2017 的总结说胜利属于伏地魔，本想苟着发育，这时发现：苟是苟不住的，这个世界 需要英雄 carry。 后来我感觉应该将公司看做一个舞台，舞台上有灯光、音效就要利用，展示自己、锻炼自己，即使是出糗，那就整理整理再来一次，who care? 成长是最重要的。 Course 模块是前工程师用 Objective-C 写的，离职后一直没有再维护，过年期间自己重构了所有 Objective-C 的代码，项目完全转为了一个纯 Swift 项目。使用 Realm 作为数据本地化方案，选择的原因也很朴素，GitHub 哪个星多我就优先选用什么。 后来参考 Jack Feng - 6ag 的几个 Swift 开源项目，新创建了 P 项目的工具 App，也对主项目结构做了重新的整理，在这里再次特别感谢。 西安运营部的成立，加多了 C 项目的后台需求，难以都顾及项目两头。使用 laravel-admin 搭建新后台，也开始使用 Docker 部署项目，感觉从此离不开 Docker 了，像极了遇到 Git 时的感觉。 C 项目主站的前端是在服务端渲染，非常传统的模式，多个工程师转手也是十分混乱。参考了 白俊遥 工程的博客、laravel 项目，修改了项目结构，添加了 gulp 工具制定了工作流，虽然没有实现前后端的完全分离，但终究是向现代化前端走出了一步。 转眼就到了年中调薪，公司不含糊，薪水涨到了我满意的值。这对我很关键，调整的不单单是我的薪水，也调整了我的心态。因为当时我认为没有强的工程师、甚至归我负责，却拿着比我还高的薪水。现在总算是有了一个平衡。 不断向 C 项目投入更多的资源，项目 指标 的要求越来越多。比如：优化了项目、优化了查询，到底优化了多少，怎么量化？这些在之前一直不被重视，改好了就都算叫优化了。项目中出现的问题错误，都要查找真实具体的原因，而不是说一个可能的什么原因，就当解答的了。我一开始也很难适应这些，但心里是认同的。 ...

快速从一个数组中查找一个元素。 Linear Search 线性查找 func linearSearch<T: Equatable>(_ a: [T], _ key: T) -> Int? { for i in 0 ..< a.count { if a[i] == key { return i } } return nil } 线性查找在最坏情况：遍历了整个数组，但没有找到合适的元素。平均要遍历一半的元素性能为 O(n)，而二分查找的效率为 O(log n)，也就是说一个有 1,000,000 元素的数组只需要 20 步就可以找到想要的元素 log_2(1,000,000) = 19.9。 但是二分查找要求数组必须是排好序。 二分查找步骤： 将数组分为两半。 判断想要找的元素是在左边数组还是右边，这也是数组需要排好顺序的原因。 如果要的元素在左边，就将左边的数组分成更小的两部分，并判断要的元素在哪部分。 重复步骤直到找到想要的元素。如果数组不能进一步查分，就说明要找的元素不在数组中。 divide-and-conquer The code func binarySearch<T: Comparable>(_ a: [T], key: T, range: Range<Int>) -> Int? { if range.lowerBound >= range.upperBound { // If we get here, then the search key is not present in the array. return nil } else { // Calculate where to split the array. let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2 // Is the search key in the left half? if a[midIndex] > key { return binarySearch(a, key: key, range: range.lowerBound ..< midIndex) // Is the search key in the right half? // 这里 + 1 的原因是排除 midIndex 中间值 } else if a[midIndex] < key { return binarySearch(a, key: key, range: midIndex + 1 ..< range.upperBound) // If we get here, then we've found the search key! } else { return midIndex } } } // 19 numbers let numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67] // 0 ..< numbers.count 覆盖所有范围 binarySearch(numbers, key: 43, range: 0 ..< numbers.count) // gives 13 二分查找是将数组分为两个，但是我们不需要正真的创建两个新数组。取而代之，我们使用 Swift Range 对象跟踪这些拆分。左闭右开。upperBound 总是比最后一个元素的索引多一。 ...

将一个数组从高到低或者从低到高排序。 插入排序算法的工作原理： 将若干数字放在一个数组里，数组是乱序的。 从数组中挑选一个数字，它是哪个并不重要，但是为了方便我们挑选数组头部的这个。 将这个数字插入到一个新的数组里。 从乱序数组里挑选下一个数字也将它放到新数组里。这个数字要么在第一个数字前或者后，所以这个两个数字是被排序的。 再次重从乱序数组里挑选下一个数字也将它放到新数组里，并将数字放在正确的位置。 一直如此进行直到乱序数组中没有数字。这时也将等到一个排序好的新数组。 自己的一个实现： let array = [2, 1, 3, 8, 3, 5, 4] var newArray = [Int]() for (k, v) in array.enumerated() { for (nK, nV) in newArray.enumerated() { // 本次的数 小于 存在的数的第一个(nv) if v < nV { newArray.insert(v, at: nK) break } } // 没有插入成功 放在末尾 if newArray.count < k + 1 { newArray.append(v) } } In-place sort 上面的排序需要两个数组，一个原始的，一个排好顺序的。但是我们也可以 就地排序 无需创建一个额外的数组。我们只需要跟踪记录原始数组中哪里部分排好顺序了，哪一部分还没有排序。 ...

实现一个 队列，包括 enqueue、dequeue、peek。 Queue 队列 核心也是 array，A queue gives you a FIFO or first-in, first-out order. 队列是：先进先出的。 public struct Queue<T> { fileprivate var array = [T]() } enqueue 进队，在数组尾部追加元素。 public mutating func enqueue(_ element: T) { array.append(element) } dequeue 出队，将首位的元素移除。因为首位元素移除后，其他元素依次向前移动，所以是 O(n)。 public var isEmpty: Bool { // 使用数组自身的方法，而不是 array.count > 0 return array.isEmpty } public mutating func dequeue() -> T? { // 使用定义的变量 if isEmpty { return nil } else { return array.removeLast() } } peek 查看队首元素。 /// peek() 改为更有语义话的只读变量 public var front: T? { return array.first } 优化出队 在出队后不移动元素而是移动 起始索引，就像动的收银台而不是排队的人。 /// 优化 队列 的出队 public struct OptimizedQueue<T> { /// 这里改为了可选型，为了可以清理无效的元素 fileprivate var array = [T?]() /// 起始索引 fileprivate var head = 0 public var count: Int { // 减去 起始索引 前面的数量 return array.count - head } public var isEmpty: Bool { // 根据实际数量判断 return count == 0 } // 保持不变 public mutating func enqueue(_ element: T) { array.append(element) } public mutating func dequeue() -> T? { guard head < array.count, let element = array[head] else { return nil } // 置空当前位置元素 array[head] = nil // 前移起始索引 head += 1 // 空索引的占用比例 let percentage = Double(head)/Double(array.count) // 50 0.25 都是魔法数字，主要是为了控制数组修剪的频率，可以自行调整 if array.count > 50 && percentage > 0.25 { // 将起始空元素删除 array.removeFirst(head) // 重置 起始索引 head = 0 } return element } public var front: T? { if isEmpty { return nil } else { // 根据 起始索引进行 返回 return array[head] } } } 文章代码：GitHub - imzyf/data-structure-and-algorithm/002-Queue/。 ...