解决 WordPress 中的摘要字数问题

WordPress 是一个比较完善的博客系统, 也是我用来淘汰 Emlog 的方案, 但是最近发现有个问题, 即对中文的文字摘要做的不好, 默认是 55 个字符, 但实际上往往会把整片文章进行输出. 通过搜索引擎可以查阅到以下几个解决方案: 1. WordPress 修改摘要擷取字數 2. WordPress 技巧:正确获取文章摘要 3. WordPress 中文摘要插件 4. 教程:WordPress完美解决中文摘要不准确问题 从这里面可以了解到, 问题的核心在于 WordPress 的截取算法是默认通过空格进行计算的. 也就是说对于东亚文字而言, 没有空格的长篇大论都是认为是一个字. 所以, 我们需要通过部分的代码修改进行改正. 但是, 考虑到部分文档的历史久远, 以及严谨的态度, 我还是主要从代码出发, 最终定位到代码的位置为 wordpress/wp-includes/formatting.php line:3699 版本号为 5.2.4 也就是目前最新的版本: function wp_trim_excerpt( $text = ”, $post = null ) { $raw_excerpt = $text; if ( ” == $text ) { $post = get_post( $post ); $text = get_the_content( ”, false, $post ); $text = strip_shortcodes( $text ); $text = excerpt_remove_blocks( $text ); $text = apply_filters( ‘the_content’, $text ); $text = str_replace( ‘]]>’, ‘]]>’, $text ); $excerpt_length = apply_filters( ‘excerpt_length’, 55 ); $excerpt_more = apply_filters( ‘excerpt_more’, ‘ ‘ . ‘[…]’ ); $text = wp_trim_words( $text, $excerpt_length, $excerpt_more ); } return apply_filters( ‘wp_trim_excerpt’, $text, $raw_excerpt ); } 可以看到, 这段代码的主要用途就是截取摘要, 通常, 很多的教程都是在这里进行替换, 将 wp_trim_words 这句改成 substr 或者截取行数之类的, 但实际上这一步是多余的操作. 我们直接看 wp_trim_words 函数: function wp_trim_words( $text, $num_words = 55, $more = null ) { if ( null === $more ) { $more = __( ‘…’ ); } $original_text = $text; $text = wp_strip_all_tags( $text ); /* * translators: If your word count is based on single characters (e.g. East Asian characters), * enter ‘characters_excluding_spaces’ or ‘characters_including_spaces’. Otherwise, enter ‘words’. * Do not translate into…

巨硬实习之旅与近期总结

在巨硬已经呆了 15 个月, 已然创造了团队中实习期最长的记录。本来也没想呆这么久,只是没想到因为离家近, 价格也还好,外加学校也没什么事,就直接呆着了。没想到现在,论文定稿事情这么多,每周来回合肥苏州跑也不现实,导师的邮件回复速度真的是慢的令人发指,只好想着以后回实验室,盯着导师干活。 实习期间还是比较舒服的,之前在类似于国企的校企合作单位实习过,在互联网单位实习过,在台资企业实习过,最后的最后,像人一样工作的还是欧美外企啊。 在巨硬的实习期其实可以分为两个阶段,一个是转正面试前,一个是转正面试后。转正面试前,众所周知,因为转正的压力,干起活来特别卖力,所以这导致的一个结果就是,没啥事干。。。因为任务都是按照 Sprint 来排的,也就是每两周安排一次计划,当计划中的任务完成,那就只能从 backlog 中找点活干,backlog 里面呢,又都是一些无关紧要的低优先级任务(高优先级也没办法在 Sprint 碎片时间完成),所以我也学会了如何正确的工(hua)作(shui)。 本来硕士阶段和本科阶段着重点在于数据库相关的研发,但是众所周知,巨硬的特点就是,来了之后随机分岗。。所以我就被莫名其妙的被一三面面试官捞过去做 ML 相关的产品= =。(后来才知道,在楼上也有做数据库存储底层相关的组)。 实习期间,主要的任务就是处理数据和一个在线计算引擎。不得不说巨硬在存储上面是厉害,实习生项目是一个离线数据处理库,也就是尝试在做数据处理时,做一个中间层,对数据进行规范化梳理,也就是常说的 OLAP 操作。一开始觉得处理 PB 级的数据,哇好兴奋啊,到最后,哦又要等几个小时才能出结果啊。 关于在线计算引擎呢,这个我觉得从架构设计上就已经到了比较先进的水平。总共使用到的服务器在 40K 左右,每天处理的请求也是巨大的数量级。。关于如何处理大规模请求,网上有各种解决方案,巨硬内部的解决方案其实很奇葩,因为 Exchange 服务是从上个世纪 90 年代就开始的,所以受到时代的局限,很多的解决方法在现在看来思想有点落后,但是,很多的解决方法又很超前,因为当时的巨硬没有开源需求,导致很多的技术并没有外传。NoSQL的实践,列数据库实践都很超前。总的来说,我还是觉得巨硬少一个 Steve Jobs 般的营销鬼才,因为内部都是工程师说了算,导致很多的需求,都很工程师范(管用户怎么看,往上堆,这个很牛逼,往上堆)。 关于转正面试,貌似很多人都会觉得这个很难很慌,然而其实真的很简单,只要把给的题做出来,换着法子做出来,用各种奇葩技巧做出来然后一次过,就好了。想到当年在中科大复试,和老师交谈甚是开心,最后在专业面试中直接开始讨论苏州地区的房价对昆山地区的影响。差不多巨硬也是这样,记得面试最后问了下 AA 给我的评价,他也反常的直接给了答案,而不是非常官方的回答(不直接回答结果,编借口说等综合考虑)。 面试后的实习期,不出意外的,我从前端组换到了现在的重后端的部门。我的前端是真的烂,传说中的 Google(Bing) Coder,加上内部又是用 TypeScript,更是很难受。不得不说,内部的 infra 做的是好,哪怕不会写,照葫芦画瓢就行,写的不对的编译会告你怎么改。大不了最后 code review 拉回来重新写。现在的这个组就是在那个在线计算引擎上开发。如果你有幸购买了 Office 的高端版本,你可能就会看到我的代码。这里面也有个好玩的事情,我之前开发了个 feature,结果这个被美国的大老板喜欢上了,隔三差五提需求改,结果就是本来 1 个月就能上线到全球用户的 feature 脱了三个月。。。另一个项目就是 cache 相关的,要把线上所有的 cache 都进行替换到统一的 cache 缓存中,还是挺有挑战的。以前在蘑菇街的时候,也是做 cache,现在在巨硬还是做 cache,也算是一种传承? 到此,基本上就是实习期间的重大项目了。在实习的后期,因为学校开始了论文开题和初稿、定稿的琐事,也算是满负荷工作下抽空进行各种文案的编写,累啊。 近期总结 其实最近比较大的事情就是开源上的事情了,应该目前最大的事就是发掉 v3.0.0 的 hexo-blog-encrypt,当时启动这个项目的原因也是挺好玩的,有同学说 hexo 纯静态做不了加密,我查了下确实没有,然后他斩钉截铁说肯定不行。emmm,那我就只好做一个给他看看。没想到现在也广泛使用了。真的没想到。(vim 的那一堆插件,什么时候有人用啊)。确实感谢了一起付出的人,尤其是有一个 co-ownner 吧。羡慕现在的年轻人,大学期间确实是最轻松的时候了。 接下来也就是希望自己论文定稿顺利,外加顺利毕业吧。

WordPress 的 Github Fetcher 插件

关于最新的介绍和使用安装方式, 建议参考 Github 的 ReadMe.md. 好长时间没有写博客, 主要的原因是比较忙. 这段时间要搞定工作上的事情, 还要处理房屋的装修, 顺便还要准备结婚的事情, 有点焦头烂额. 所以, 也是上班的时候, 抽了一个小时搞定了这个插件. 我个人写博客的习惯是, 本地上写好了博客, 然后提交到自己的 git 库里面, 然后 push 到 github 上. 之前在用 emlog 的时候, 也是自己写了一个同步的插件来帮助同步, 加上 github 的 markdown 渲染效果确实可以, 同时还可以用他们的图片作为 CDN 的加速. 具体细节也不多说, 然后就是具体的使用方法. 如何安装 直接到 github 的 release 页面, 下载 zip 包, 然后通过上传文件的安装方式安装该插件就可以了. TODO: 将插件上传到官方的插件中心 如何使用 通常, 当安装插件之后, 你会看到在编辑器的右侧看到一个对话框, 输入你的 github 博客文章地址, 对于我来说, 通常而言就是 https://github.com/xxx/xx.md, 然后按 Sync 按钮, 之后就可以看到同步好的博客出现在编辑器里了. 目前, 这个插件只支持老版本的编辑器, 对于最新的编辑器 – Gutenberg 并不支持. (说句实话, 新版本的编辑器太难用…) 最后, 如果觉得有用, 有新的需求, 欢迎在 github 上提交 issue. 如果担心是否能同步图片和代码, 可以参考如下的测试部分: using namespace std; class Solution { public: void dfs(vector<vector<int>> &grid, set<pair<int, int>> &points, int idx, int idy) { if (0 <= idx && idx < (int)grid.size() && 0 <= idy && idy < (int)grid[0].size()) { if (points.find(pair<int, int>(idx, idy)) != points.end() || grid[idx][idy] == 0) { return; } points.insert(pair<int, int>(idx, idy)); dfs(grid, points, idx – 1, idy); dfs(grid, points, idx, idy – 1); dfs(grid, points, idx + 1, idy); dfs(grid, points, idx, idy + 1); } } int largestIsland(vector<vector<int>> &grid) { set<pair<int, int>> points; vector<vector<pair<int, int>>> groups( grid.size(), vector<pair<int, int>>(grid[0].size(), pair<int, int>(0, 0))); int maxSize = 0; int groupIdx = 1; vector<pair<int, int>> zeros; for (int i = 0; i < (int)grid.size(); i++) { for (int j = 0;…

Firefox 完全暗黑主题

我是实在想不到什么比较好的名称了… 所以才写了这么个标题. 事情的起因是这样的, 因为最新的 MacOS 已经有了暗黑主题, 所以作为最顺手的浏览器 – Firefox 也遇到了一个新的问题, 就是能否以最完美的姿态迎接这个新的主题. 我们可以先看看正常情况下的火狐浏览器的表现, 即官方的 dark 主题: 可以看到,右键菜单和下来书签都是白色的, 很扎眼. 所以尝试修改了火狐的主题, 新版的效果如下: 从我的个人审美看, 更加喜欢改好的这个主题. 具体的代码在这 具体的安装方法就是找到火狐的 Profile 文件夹, 然后将代码 git clone 到 chrome 文件夹下. 具体的位置可以看我之前的文章 这边推荐下 Fira Code 这个字体, 一开始因为他的 programming ligatures 不太习惯, 但是习惯之后, 确实发现代码的可读性变得很高. 虽然对于一般的新手玩家, 都会推荐 Chrome 作为主要浏览器, 不过如果喜欢折腾, Firefox 显然有着更加充分的自由度. 作为一个从 Firefox 3 开始使用的用户, 真的不忍心看到它被埋没啊.

微软实习面试经历

没想到,半年的学习已经结束了。和导师谈妥之后,研二就可以开始实习了,然后就开始了自己的实习招聘生涯。其实,因为目标比较明确,大部分的公司也并不是特别想去。所以就盯上了一家叫做巨硬的外企。然后就开始准备了。 但是主要好玩的地方不是面试的准备,而是拿 offer 的一段插曲。(巨硬的面试挺好过的,只要所有的算法题,都能很快的想到解决办法(不是最优解都可以),然后能够 bug free 的完成编写部分,都能有个很好的结果。) 当时,4.23 面试结束,在 4.27 收到 congratulations 邮件,被告知 offer 已经确认。然后就是精彩的部分了。邮件中说,具体的 offer 信息会在 few days(原话) 发送。所以,就是接下来的一周时间。但是,直到周三,我都没有收到 offer。因为感觉自己的面试过程非常的顺利。所以很是奇怪。发邮件询问 HR ,被告知,offer 还在发,说周四和周五一定会有。于是又开始了等待。最后周五中午还是没有 offer。于是很是紧张,发邮件给 HR,结果她不在办公室,请假了一天。当时就慌了。然后打电话给另一个北京的 HR,让她查一下我当前的状态,结果被告知,offer 在 5.6 号下午两点已经发送,是最早的几批。但是,我没有收到。于是,一番操作下,终于发出来了。。。真的是一波三折。想想如果自己没有找到另一个北京的 HR 的联系方式,或者我的 HR 没有请假(她回了句继续等待),可能就变成了我默拒了。还好最后的结果不错。 以上就是一个小插曲。就这几个月而言,其实投的公司挺多的,但是大部分都是去刷了个满分的笔试,然后鸽了面试。主要是,不是很喜欢某些公司的背书式面试,或者临时抓一个面试官过来面试毫无准备的面试,这让我觉得没有得到应有的尊重。其实,作为一名工程师,最主要的是解决问题的能力,比如面对某一个场景,会设计出来一个怎样的解决方案,同时,在实现这个方案的过程中,你会如何表现,是 bug free 的一次 AC,还是打回重来,而不是 Spring 的事务有多少种写法,或者数据库的第三范式的内容。所以整个求职中都偏向于考察算法的外企(其实也就是巨硬一家)。近段时间,国内互联网的负面新闻太多了。让我产生了一种,究竟实在 make the world better, 还是 make the world worse。所以选择了一个更加偏向于基础技术的公司。 记得巨硬面试的时候,有个流程是参观办公室,当时有个 50 岁左右的美国老太太,听说我们是来面试实习生的,很热情的张开双臂欢迎,这样的一个氛围确实给我留下了很深的印象。而且他的宣讲也特别的别出新裁,其他的公司都在极度的渲染自己的发展有多么迅速,或者未来有多么光明,而巨硬是指很平淡的描述,在巨硬工作会是一个怎样的场景,如何更好的 work life balance。我觉得这就是企业文化上的一个差异。而引申出来的可能就是两个截然不同的工作氛围。至少,我是喜欢后者的。至于技术上的提升,我觉得更多的是周围同事的水平,或者说公司的眼界。 希望之后一切顺利。

01 背包的二进制优化

也是在刷题的时候发现的,比如 hiho week 195。一眼看过去就是一个 0-1 背包问题,然后直接 DP 上了,当时觉得应该问题不大,结果最后只有 50%,一看数据,100% 的数据为 1E5 量,简单的 DP 的话复杂度为 O(MN),这样复杂度估计是 1E10,这样肯定会 TLE。 然后一看,他的单个商品的全权值很低,都在 [1, 10] 之间,这样的话,最多有 100 种组合,所以极端情况下,每个商品都会有 1000 个同类。这样就有了二进制优化的余地。简单的说就是,将多个重复的商品进行优化。比如 p(w, v) 的商品有 10 个,那么,我们可以将其简化为,一个 p(1w, 1v),一个 p(2w, 2v),一个 p(4w, 4v),最后剩下一个 p(3w, 3v)。 这样的话,就将数据量从 10 简化到了 4。于是乎,就可以将数据量减少一个数量级。所以,最后这题的代码: using namespace std; typedef pair<uint64_t, uint64_t> pii; typedef pair<pii, uint64_t> ppiii; typedef pair<pii, pii> ppiipii; int main() { ios::sync_with_stdio(false); uint64_t n, m; cin >> n >> m; map<pii, uint64_t> _ticks; for (uint64_t i = 0; i < n; i++) { uint64_t w, p; cin >> w >> p; _ticks[pii(w, p)]++; } vector<pii> ticks; for (auto tick : _ticks) { uint64_t idx = 0; uint64_t remain = tick.second; while (remain > 0) { uint64_t cur = pow(2, idx); idx++; if (remain >= cur) { ticks.push_back(pii(cur * tick.first.first, cur * tick.first.second)); } else { ticks.push_back( pii(remain * tick.first.first, remain * tick.first.second)); cur = remain; } remain = remain – cur; } } vector<vector<uint64_t>> DP(2, vector<uint64_t>(m + 1, 0)); for (uint64_t i = ticks[0].first; i <= m; i++) { DP[0][i] = ticks[0].second; } for (uint64_t i = 1; i < (uint64_t)ticks.size(); i++) { uint64_t cur = i % 2; uint64_t pre = (i – 1) % 2; for (uint64_t j =…

Redis 相关的复习

这段时间主要是扑在算法上了,这些工程领域的知识有点遗忘了。所以趁着这次复习,复习下之前做过得项目。同时,正好当时,Redis 官方还没有集群方案,所以才有了之前的 Cache 集群方案,现在正好也看看 Redis 官方的方案。 Codis 方案 一张 Codis 官方给出的架构图: 可以看到,它是采用了 proxy 的方式,和 Redis 官方给出的去中心化的思路不同,Proxy 是一种中心话的思路,将 Redis 仅仅作为存储引擎来使用。这一点其实比较符合组件化的原则,每一个组件只需要做一件事。同时,proxy 的方案,也非常利于简化代码的逻辑。 Zookeeper 用来维护整个集群的 metadata 信息。相比较于去中心化的思路,中心话带来的就是一致性问题。比较简单的,在多个 proxy 中,如何维护同一个正确的 redis 集群信息。所以这个使用了 Zookeeper 来进行维护。也算是做到了 HA。 至于 proxy 中的分区算法,依旧是采用的一致性 Hash 算法。这个也算是在这种扩展性上的一个比较通用的处理手段。 记得我们当时讨论过,是否直接采用这个方案进行部署。但是,当时的负责人始终坚持自研,但是最后的方案也还是参考的 Codis 进行,不得不说是一个很没有意思的事情。 一致性 Hash 其实就是将一个一维线性的地址空间做成环状,收尾相接。 同时部署在上面的机器,都会握有一个 index,比如 1024 中的 256,512,768,1024 这四台机器。 当一个 key = 268 值传入时,就会找第一个接近的值,这里就是 512 号机器。 如果 key = 1025 那么,就会 key = key % 1024 从而映射到 256 上。 Zookeeper 如何进行一致性保证 为什么需要 Zookeeper,上文也说过了,就是保证 Proxy 能获取到最新且一致的集群信息。也就是一致性保证。 一致性保障,其实比较完善的解决方案也就是 Raft 和 Paxos 两个算法。这边 Zookeeper 则是使用的叫 Fastleader 的选举算法,在多实例的情况下,通过选举出来一个 master 进行决策,从而避免了多机同时处理导致的不一致。 Fastleader 算法: 先上一个算法流程图: 第一反应就是和,Raft 算法好像啊。 以上是 Raft 协议的一个状态转移图,可以看到,和 Zookeeper 的选举不同的是,他没有固定的 Observing 状态(一直默默参与数据同步,但是不参与投票)。而且,ZooKeeper 中,一旦 server 进入 leader 选举状态则该 follower 会关闭与 leader 之间的连接,从而旧 leader 无法发送复制数据的请求到新的 leader 上,从而避免了干扰。 具体可以看 图解zookeeper FastLeader选举算法。 至此,基本上说了第一个方案。 Twemproxy 方案 这个也是最早的一个集群管理方案了,更倾向于一个基本的 client 端的静态 sharding。而且他的介绍也很简单,就是提供一个轻量级的代理服务,主要是为了减少后端的连接数。。。所以不是很明白为什么很多人都会写博客说用它做集群会很麻烦。。他本来就不是为了复杂集群管理业务而设计的。。 Redis 官方方案 也是一个使用了一致性 Hash 算法的方案。不过他有意思的一点就是去中心化。主要的好处就是,加入 {A, B, C} 三台机器作为一个集群,那么,你连上任一一台机器,你的所有请求都会在 Redis 内部进行处理,而不会暴露在外面。不过坏处也是显而易见的。访问缓存,基本上都是大量的短连接。所以,这边做并不会减少这个问题的产生(Twemproxy)就是因为这个而产生的。 具体的算法实现: A, B, C 三个节点,采用哈希槽 (hash slot) 的方式来分配 16384 个 slot ,三个节点分别承担的 slot 区间是: 节点 A 覆盖 0-5460; 节点 B 覆盖 5461-10922; 节点 C 覆盖 10923-16383. 获取数据: 如果存入一个值,按照redis cluster哈希槽的算法: CRC16(‘key’) % 16384 = 6782。 那么就会把这个key 的存储分配到 B 上了。同样,当我连接 (A, B, C) 任何一个节点想获取 ‘key’ 这个key时,也会这样的算法,然后内部跳转到B节点上获取数据 新增一个主节点 D,Redis 会从各个机器的前段,拿出一部分给 D: 节点 A 覆盖 1365 – 5460 节点 B 覆盖 6827 – 10922 节点 C 覆盖 12288 – 16383 节点 D 覆盖…

Emlog 迁移至 WordPress

作为一个 Emlog 4 年多的用户同时也是众多参与 Emlog 开发者中的一员,做出这个决定确实很难。不过 Emlog 的长期荒废,加上论坛里高质量的内容越来越少。这个也是势在必行。 最后一根稻草是:混乱的社区。于是乎,最后转向了 WordPress。 说道迁移,最麻烦的时数据的备份,之前也想过迁移,但是总是在最后一步卡住了,因为缺少一个合适的工具进行数据的导入导出。自己写的话,比较麻烦,因为对应的数据库表众多(其实就是懒)。 于是乎,这次我觉定自己玩一下。先是查到了这么一篇文章:emlog 5.3.1程序转入wordpress程序教程。得到了这么一个优秀的脚本 em2wp.php。 但是跑了一下,发现问题挺大的。因为这个版本的 php 是用 5 来写的,现在所有的云主机,基本都是 7 打底,所以就会有兼容性问题: WordPress 版本更新之后,对应的表结构发生了改变。 PHP7 以后不再支持 mysql_xxxx 函数。 代码并不会显示错误代码。 中文字符集的乱码问题。 于是自己修改了下,并且运行成功。代码 GIST – em2wp.php。 代码不会修改 emlog 原始表结构,所以放心的在线上执行,毕竟如果是迁移,Wordpress 的库内容是无足轻重的。并且,我相信各位都是可以成功看到 GIST 的。 不过总体而言,迁移非常的成功。剩下的 https,资源文件,域名,postId 保持一致,则都是体力活了。 本来以为一切都已经搞定了,可是,我去 google 搜了一下我的博客,发现他的 url 为 https://mikecoder.cn/post/{postId},然后看看其他人引用我博客的时候的 url 则是 https://mikecoder.cn/?post={postId}。 不管是哪一种,WP 都没有默认的支持,前者比较好办,直接在后台进行修改就好,修改默认的链接为 /post/%postId%/ 即可,后者则是比较麻烦。因为不太想修改 WordPress 的源码(不太清楚有多少地方需要修改)。想了一会,最后确定添加 NGINX 重写规则的方案(还好会一点 NGINX)。 添加注释中的代码即可。将 ?post=(\d+) 的请求全都重定向到 WP 识别的请求上。 server { listen 443; server_name www.mikecoder.cn mikecoder.cn; … index index.html index.htm index.php; location / { #===================================================== if ($args ~* post=(\d+)) { set $args ”; set $id $1; rewrite ^ https://mikecoder.cn/post/$id; } #===================================================== try_files $uri $uri/ /index.php?$query_string; index index.php; } location ~ \.php$ { fastcgi_split_path_info ^(.+\.php)(/.+)$; fastcgi_pass unix:/run/php/php7.0-fpm.sock; fastcgi_index index.php; fastcgi_param SCRIPT_FILENAME $document_root$fastcgi_script_name; include fastcgi_params; } } 至此,基本上所有的配置已经完成。现在的主要任务又变成了,如何快速的了解 WordPress 的代码结构。同时争取成为 WordPress 的开发者。 最后感慨下,Wordpress 确实是做的最完善的一个博客系统。 为什么不用 hexo 作为一个稍微会一点 php 的人,还是想自己能魔改整个系统的。 作为一个 hexo 的插件开发者,我也知道 hexo 用来写博客的局限性。不是很愿意被限制。 我正好买了 3 年的云主机,不用也是浪费啊。 大量的数据不太好使用静态博客迁移。 为什么不用 typecho 其实和 emlog 一样的问题。WP 能满足所有的功能,且大部分做的更加完善。所以没理由使用 EM 和 TY(追求简单除外)。 论坛活跃度不如 WP,想获得新的主题或者插件,都比较困难。 EM 和 TY 的活跃用户仅限于国内。接轨世界的话,WP 确实是最好的选择。 最后的最后,感谢 EMLOG 的开发者。

二分查找和 Lucas 定理

因为这段时间都在打比赛中度过,有几个小的收获点这边可以留个纪念。 1. 二分查找的几个用法。 一般而言,二分查找都是用在不同数字的数量集中。这样的好处是如何快速的定位。但是,如果是排序的包含相同数字的数组,要求获得某一个数出现的次数时,就得用另一种二分查找的变种了。 假设是 [1, 1, 2, 3, 3] 这样的一个数组,要求获得 1 和 3 的个数时。普通的二分查找只能定位到其中的一个位置。之前我的做法是,向前向后搜索。但是,在极端情况下,比如一整个数组都是 1,此时,算法的复杂度退化为 O(N),然后就 TLE 了。 所以这边也正好是看到【剑指 offer 】里面有这么一题,就写一下。 int getFirstIdx(vector<int> &nums, int target) { if (nums.size() == 0) { return -1; } int left = 0, right = nums.size() – 1; do { int mid = left + (right – left) / 2; if (mid == target) { if (mid == 0 || (mid > 0 && nums[mid – 1] != target)) { return mid; } else { left = mid – 1; } } else if (mid > target) { right = mid – 1; } else { left = mid + 1; } } while (left <= right); return -1; } int getLastIdx(vector<int> &nums, int target) { if (nums.size() == 0) { return -1; } int left = 0, right = nums.size() – 1; do { int mid = left + (right – left) / 2; if (mid == target) { if (mid == (int)nums.size() – 1 || (mid < (int)nums.size() – 1 && nums[mid + 1] != target)) { return mid; } else { right = mid + 1; } } else if (mid > target) { right = mid – 1; }…