二分法，快速幂 // 题目链接-来源：力扣（LeetCode）实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。 示例 1： 输入：x = 2.00000, n = 10输出：1024.00000 思路：此题一上来应有暴力求解的思路，通过 pow(x, n - 1) (n > 0)或 pow(x, n + 1) (n < 0)递归或迭代地求解。但是暴力解法会超时，我们考虑简化运算。注意到，当n为偶数的时候，我们只需计算 pow(x, n / 2)，然后将结果平方即可。而当n为奇数时，我们依然可以 计算 pow(x, n / 2)，将结果平方后再多乘一个 x 即可。事实上，这就是快速幂的思路，我们用 res 存储结果，在 n 为奇数（用 n & 1 判断）时，额外进行 res *= x。在 n 为偶数时，对 n 减半（用 n >> 1 操作），同时让 x 平方。即可在 log n 时间内得到结果。细节上，在 n 为负数时，取反然后将 x 取倒数 ...

位运算 // 题目链接-来源：力扣（LeetCode）请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。 示例 1： 输入：00000000000000000000000000001011输出：3解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。 思路：以最低为为基准，与 1 做与运算，就能得到当前位是否为1。然后将整数逻辑右移，重复与运算，循环31次即可遍历所有位。进一步优化：关于位运算，有个用途很广的小技巧， n & (n - 1)，这个式子的返回值是「当前二进制串的最末尾一个“1”变成“0”」的值举例 1010 & (1010 - 1) = 1010 & (1001) = 1000可以看到倒数第 2 位上的 “1” 被消除了。这样对于 “1”比较稀疏的串，就不需要遍历32位这么多了。 时间复杂度：O(1)空间复杂度：O(1) 实现：1234567 ...

找规律 // 题目链接-来源：力扣（LeetCode）给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m - 1] 。请问 k[0]*k[1]*…*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。 示例 1： 输入: 2输出: 1解释: 2 = 1 + 1, 1 × 1 = 1 思路：此题与上一题的区别就是n的范围增加到了1000，对于 int 型变量会有溢出（因为我们的因子里有3）。那么我们改用 long 存储结果，并在每次获取新的结果时都取一次模即可。（因为我们一开始的结果肯定小于 1000000007，这里我为了提高效率，直接用条件判断 + 减法，本质上还是取模） 时间复杂度：O(n)空间复杂度：O(1) 实现：12345678910111213141516171819 ...

找规律 // 题目链接-来源：力扣（LeetCode） 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]*k[1]*…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。 示例 1： 输入: 2输出: 1解释: 2 = 1 + 1, 1 × 1 = 1 思路：很遗憾，这类题目没有什么直接的思路，只能通过观察尝试找出其中的规律。注意到，对于任意给定的 n，我们将其分解为 3 或者 3 之后，所得的乘积最大。（由于分解为 1 的情况下乘积一定为 1，排除。对于 n = 4，有 4 = 2 + 2 = 2 * 2，从 n = 5 开始，有 5 = 2 + 3 < 2 * 3， 6 = 3 + 3 = 2 + 2 + 2 < 2 * 2 * 2 < 3 * 3）事实上，在实数范 ...

图的遍历，回溯 // 题目链接-来源：力扣（LeetCode） 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？ 示例 1： 输入：m = 2, n = 3, k = 1输出：3 思路：依然是图的遍历问题，考虑 DFS 和 BFS 两种方案。BFS由于需要建立队列，实现起来会麻烦一些，我们考虑DFS。同前一题 矩阵中的路径 一样，本题需要考虑机器人下一步行进的 可能的位置 （数组下标不越界，并且下标之和不能大于k）。由于我们是从[0,0]点开始进行的，所以行进方向只需向下或向右即可，对于遍历过的方格，用一个全局二维数组 reahced[][] 记录是否访问过。DFS每到达新的一 ...

图的遍历，回溯 // 题目链接-力扣（LeetCode） 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 思路：网格搜索类型的题目需要马上联想到图的遍历问题，解法无非2种，DFS或者BFS。细节上的处理就是如何剪枝以减小复杂度。大部分时候，DFS的代码会简洁易懂一些（不需要借助队列），我们考虑用DFS实现。我们用一个辅助函数 search 来进行DFS递归遍历。在函数中，我们用一个 StringBuilder sb 变量存储当前累计获取到的合法字符串。以当前末尾字符为出发点，向四周 可能的位置 探测。（「可能」指的是，下标不越界，并且此轮字符串遍历未访问过的网格。因此，我们还需要为本次遍历存储一个 visited 二维数组，记录是否访问过此网格。）如果访问到的字符与字符串中下一位相同，我们就对该字符继续进行 search，同时修改该位 ...

双指针，二分法 // 题目链接-来源：力扣（LeetCode） 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。 示例 1： 输入：[3,4,5,1,2]输出：1 思路：最直观的思路就是，原数组为非递减数组，则旋转以后可以分解为两个非递减的子数组，我们依次两两比较数组中的数字，一旦出现 xi > xj (i < j) 的情况，输出 xj 即可。进一步优化：对有序数据的查找，容易想到二分法。为了直观说明，假设原数组为 [x0, x1, x2, x3, x4] 我们有 x1 <= x2 <= x3 <= x4，经过旋转后得 [x2, x3, x4, x0, x1]，注意到一定有 最右侧元素 <= 最左侧元素，在本例中即 x1 <= x2，所找元素就应该顺着 x1 向左进行。我们用头指针 left 指向数组最开始元素，用尾指针 ...

简单动态规划 // 题目链接-来源：力扣（LeetCode） 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。 示例 1： 输入：n = 2输出：2 思路：记 f(i) 为青蛙跳到第 i 级台阶的跳法数。由于青蛙可以从 i - 1 或者 i - 2 级台阶跳上来，所以 f(i) = f(i - 1) + f(i - 2)。其实这就是斐波那契数列的递推式，从前一题可以得到启发，用一个队列来迭代地存储这个过程。 时间复杂度：O(n)空间复杂度：O(1) 实现：123456789101112131415class Solution { public int numWays(int n) { int mod = 1000000007; Queue<Integer> q = new LinkedList<>(); q.offer ...

简单动态规划 // 题目链接-来源：力扣（LeetCode） 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下： F(0) = 0,   F(1) = 1F(N) = F(N - 1) + F(N - 2), 其中 N > 1.斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。 示例 1： 输入：n = 2输出：1 思路：最简单的动态规划，每次用2个变量迭代存储前2次的计算结果即可。为了免去2个变量来回转存的麻烦，可以用一个队列来存储这两个变量，把旧的变量弃置出队即可。 时间复杂度：O(n)空间复杂度：O(1) 实现：12345678910111213141516class Solution { public int fib(int n) { int mod = 1000000007; Q ...

用栈实现队列 // 题目链接-来源：力扣（LeetCode） 示例 1： 输入：[“CQueue”,”appendTail”,”deleteHead”,”deleteHead”][[],[3],[],[]]输出：[null,null,3,-1] 思路：栈的特点是后进先出，队列特点是后进后出。对于『后进』的特点， appendTail() 可以直接调用 push() ，我们只需特殊考虑怎么用『先出』实现『后出』。容易想到，用一个辅助栈 helper，将主栈 main 的元素依次压入辅助栈中，即『逆序』了主栈中的元素，此时弹出辅助栈顶元素即为我们需要的队列的头部元素，也即 deleteHead() 的返回值。然后将 helper 中元素依次放回 main 中。为了避免将元素在两个栈来回搬运，注意到从队列的视角看，helper 中的元素相对 main 都是较早进队的元素，那么出队时，我们优先考虑 helper 即可；同理，main中的元素较新，在入队时，我们要优先考虑 main。也就是说，在 helper 不空时，需要出队时我们只要对 helper 调用 pop() 即可，而入队时 对 ...