如何运用二分查找算法 一、问题分析 二、扩展延伸 如何运用二分查找算法 二分查找到底有能运用在哪里？ 最常见的就是教科书上的例子，在有序数组 中搜索给定的某个目标值的索引。再推广一点，如果目标值存在重复，修改版的二分查找可以返回目标值的左侧边界索引或者右侧边界索引。 PS：以上提到的三种二分查找算法形式在前文「二分查找详解」有代码详解，如果没...

前缀和技巧 一、什么是前缀和 二、优化解法 三、总结 前缀和技巧 今天来聊一道简单却十分巧妙的算法问题：算出一共有几个和为 k 的子数组。 那我把所有子数组都穷举出来，算它们的和，看看谁的和等于 k 不就行了。 关键是，如何快速得到某个子数组的和呢 ，比如说给你一个数组 nums ，让你实现一个接口 sum(i, j) ，这个接口要返回...

twoSum问题的核心思想 TwoSum I TwoSum II 三、总结 twoSum问题的核心思想 Two Sum 系列问题在 LeetCode 上有好几道，这篇文章就挑出有代表性的几道，介绍一下这种问题怎么解决。 TwoSum I 这个问题的最基本形式 是这样：给你一个数组和一个整数 target ，可以保证数组中存在 两个数的和为...

如何寻找最长回文子串 一、思考 二、代码实现 如何寻找最长回文子串 回文串是面试常常遇到的问题（虽然问题本身没啥意义），本文就告诉你回文串问题的核心思想是什么。 首先，明确一下什：回文串就是正着读和反着读都一样的字符串 。 比如说字符串 aba 和 abba 都是回文串，因为它们对称，反过来还是和本身一样。反之，字符串 abac 就不是...

一、练习 Git 二、练习正则表达式 三、练习 SQL 虽说我没事就喜欢喷应试教育，但我也从应试教育中发现了一个窍门：如果能够以刷题的形式学习某项技能，效率和效果是最佳的。对于技术的学习，我经常面临的困境是，理论知识知道的不少，但是有的场景实在无法模拟，缺少亲自动手实践的机会 ，如果能有一本带标准答案的习题册让我刷刷就好了。 所以在学习新技术时，我...

思路分析 最后总结 今天就聊一道很看起来简单却十分巧妙的问题，寻找缺失和重复的元素。之前的一篇文章「寻找缺失元素」也写过类似的问题，不过这次的和上次的问题使用的技巧不同。 这是 LeetCode 645 题，我来描述一下这个题目： 给一个长度为 N 的数组 nums ，其中本来装着 [1..N] 这 N 个元素，无序。但是现在出现了一些错误，...

如何寻找消失的元素 如何寻找消失的元素 之前也有文章写过几个有趣的智力题，今天再聊一道巧妙的题目。 题目非常简单： 给一个长度为 n 的数组，其索引应该在 [0,n) ，但是现在你要装进去 n + 1 个元素 [0,n] ，那么肯定有一个元素装不下嘛，请你找出这个缺失的元素。 这道题不难的，我们应该很容易想到，把这个数组排个序，然后遍历一遍...

如何k个一组反转链表 一、分析问题 二、代码实现 三、最后说两句 如何k个一组反转链表 之前的文章「递归反转链表的一部分」讲了如何递归地反转一部分链表，有读者就问如何迭代地反转链表，这篇文章解决的问题也需要反转链表的函数，我们不妨就用迭代方式来解决。 本文要解决「K 个一组反转链表」，不难理解： 这个问题经常在面经中看到，而且 Leet...

信封嵌套问题 一、题目概述 二、解法 三、总结 信封嵌套问题 很多算法问题都需要排序技巧，其难点不在于排序本身，而是需要巧妙地排序进行预处理，将算法问题进行转换，为之后的操作打下基础。 信封嵌套问题就需要先按特定的规则排序，之后就转换为一个 最长递增子序列问题 ，可以用前文 二分查找详解 的技巧来解决了。 一、题目概述 信封嵌套问题是...

如何高效寻找素数 高效实现 countPrimes 如何高效寻找素数 素数的定义看起来很简单，如果一个数如果只能被 1 和它本身整除，那么这个数就是素数。 不要觉得素数的定义简单，恐怕没多少人真的能把素数相关的算法写得高效。比如让你写这样一个函数： // 返回区间 [2, n) 中有几个素数 int countPrimes ( int...