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() 后，又销毁了该函数。 ...

又开始写世界上最后的语言 PHP 了（狗头保命）。一个很简单的字符串是否包含判断就掉坑了。 方法签名： strpos ( string $haystack , mixed $needle [, int $offset = 0 ] ) : int $mystring = 'abc'; $findme = 'a'; if (strpos($mystring, $findme)) { dump('yes'); } 注意这时是不会输出 yes，因为 strpos($mystring, $findme) 返回的是 0。就想官方文档说的： Warning 此函数可能返回布尔值 FALSE，但也可能返回等同于 FALSE 的非布尔值。应使用 === 运算符来测试此函数的返回值。 正解： if (strpos($mystring, $findme) !== false) { dump('yes'); } 这次问题是网上一搜，找到 strpos 后看到 如果没找到 needle，将返回 FALSE 就没多想就用了。语言间的差异还有注意。 References php.net - strpos – EOF –

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

再读王巍的《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 来修饰。在 protocol 中使用 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）。这样有时候在语法上看起来就会非常漂亮。 ...

重新翻阅的自己工作邮件的发件箱，回顾一年工作。新年伊始自己还是在开发 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 上面的排序需要两个数组，一个原始的，一个排好顺序的。但是我们也可以 就地排序 无需创建一个额外的数组。我们只需要跟踪记录原始数组中哪里部分排好顺序了，哪一部分还没有排序。 ...