Posts

归并排序（英语：Merge sort，或 mergesort），是创建在归并操作上的一种有效的排序算法，效率为 O(nlogn)。1945 年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。 采用分治法： 分割：递归地把当前序列平均分割成两半。 集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。 归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。 <?php function mergeSort($arr) { $len = count($arr); if ($len <= 1) { return $arr; } // 递归结束条件, 到达这步的时候, 数组就只剩下一个元素了, 也就是分离了数组 $mid = $len / 2; $left = array_slice($arr, 0, $mid); // 拆分数组0-mid这部分给左边left $right = array_slice($arr, $mid); // 拆分数组mid-末尾这部分给右边right $left = mergeSort($left); // 左边拆分完后开始递归合并往上走 $right = mergeSort($right); // 右边拆分完毕开始递归往上走 $arr = merge($left, $right); // 合并两个数组,继续递归 return $arr; } // merge函数将指定的两个有序数组(arrA, arr)合并并且排序 function merge($arrA, $arrB) { $arrC = array(); while (count($arrA) && count($arrB)) { // 这里不断的判断哪个值小, 就将小的值给到arrC, 但是到最后肯定要剩下几个值, // 不是剩下arrA里面的就是剩下arrB里面的而且这几个有序的值, 肯定比arrC里面所有的值都大所以使用 $arrC[] = $arrA[0] < $arrB[0] ? array_shift($arrA) : array_shift($arrB); } return array_merge($arrC, $arrA, $arrB); } $startTime = microtime(1); $arr = range(1, 1000); shuffle($arr); echo 'before sort: ', implode(', ', $arr), "\n"; $sortArr = mergeSort($arr); echo 'after sort: ', implode(', ', $sortArr), "\n"; echo 'use time: ', microtime(1) - $startTime, "s\n"; 假设被排序的数列中有 N 个数。遍历一趟的时间复杂度是 O(N)，需要遍历多少次呢？ ...

启动 Laravel 5.8 文章以 Laravel 学习。入口文件 public/index.php： // Register The Auto Loader require __DIR__.'/../vendor/autoload.php'; autoload.php 不负责具体功能逻辑，只做了两件事：初始化自动加载类、注册自动加载类。 autoload_real.php 中的类名为 ComposerAutoloaderInit... 这可能是为防止与用户自定义类名跟这个类重复冲突，加上了哈希值。 其实还有一个做法我们更加熟悉，是定义一个命名空间。这里为什么不定义一个命名空间呢？一种理解：命名空间一般都是为了复用，而这个类只需要运行一次即可，以后也不会用得到，用哈希值更加合适。 autoload_real.php autoload.php 主要调用了 getLoader()： public static function getLoader() { // 单例模式，自动加载类只能有一个 1 if (null !== self::$loader) { return self::$loader; } // 获得自动加载核心类对象 2 spl_autoload_register(array('ComposerAutoloaderInit76e88f0b305cd64c7c84b90b278c31db', 'loadClassLoader'), true, true); self::$loader = $loader = new \Composer\Autoload\ClassLoader(); spl_autoload_unregister(array('ComposerAutoloaderInit76e88f0b305cd64c7c84b90b278c31db', 'loadClassLoader')); // 初始化自动加载核心类对象 3 $useStaticLoader = PHP_VERSION_ID >= 50600 && !defined('HHVM_VERSION') && (!function_exists('zend_loader_file_encoded') || !zend_loader_file_encoded()); if ($useStaticLoader) { require_once __DIR__ . '/autoload_static.php'; call_user_func(\Composer\Autoload\ComposerStaticInit76e88f0b305cd64c7c84b90b278c31db::getInitializer($loader)); } else { $map = require __DIR__ . '/autoload_namespaces.php'; foreach ($map as $namespace => $path) { $loader->set($namespace, $path); } $map = require __DIR__ . '/autoload_psr4.php'; foreach ($map as $namespace => $path) { $loader->setPsr4($namespace, $path); } $classMap = require __DIR__ . '/autoload_classmap.php'; if ($classMap) { $loader->addClassMap($classMap); } } // 注册自动加载核心类对象 4 $loader->register(true); // 自动加载全局函数 5 if ($useStaticLoader) { $includeFiles = Composer\Autoload\ComposerStaticInit76e88f0b305cd64c7c84b90b278c31db::$files; } else { $includeFiles = require __DIR__ . '/autoload_files.php'; } foreach ($includeFiles as $fileIdentifier => $file) { composerRequire76e88f0b305cd64c7c84b90b278c31db($fileIdentifier, $file); } return $loader; } 单例模式 1 if (null !== self::$loader) { return self::$loader; } 构造 ClassLoader 核心类 2 spl_autoload_register(array('ComposerAutoloaderInit76e88f0b305cd64c7c84b90b278c31db', 'loadClassLoader'), true, true); self::$loader = $loader = new \Composer\Autoload\ClassLoader(); spl_autoload_unregister(array('ComposerAutoloaderInit76e88f0b305cd64c7c84b90b278c31db', 'loadClassLoader')); public static function loadClassLoader($class) { if ('Composer\Autoload\ClassLoader' === $class) { require __DIR__ . '/ClassLoader.php'; } } composer 先向 PHP 自动加载机制注册了一个函数，这个函数 require 了 ClassLoader 文件。成功 new 出该文件中核心类 ClassLoader() 后，又销毁了该函数。 ...

将 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 –

重新翻阅的自己工作邮件的发件箱，回顾一年工作。新年伊始自己还是在开发 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/。 ...

加入 Swift Algorithm Club /‘ælgə’rɪðəm/，回炉重新学习数据结构与算法。 自己创建的项目：GitHub - imzyf/data-structure-and-algorithm。 实现一个 栈 /stæk/，包含 push peek pop 与 Generics 泛型。 stack 栈 非常像一个数组，它包括少量的方法。 push 添加一个新元素到栈顶 pop 从栈顶移除一个元素 peek 查看栈顶的一个元素但是不 pop A stack gives you a LIFO or last-in first-out order. 栈是后进先出，队列是先进先出。 public struct Stack<Element> { fileprivate var array: [Element] = [] } push push 是在数组的尾部添加元素是以 O(1)，如果是在数组最前添加是 O(n) 这是昂贵的。 public mutating func push(_ element: Element) { array.append(element) } 因为使用的 struct，修改属性值的方法要加 mutating。 pop 想从一个空栈中弹出最后一个元素将返回 nil。 ...