找规律 // 题目链接-来源：力扣（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() 即可，而入队时 对 ...

重建二叉树 // 题目链接-来源：力扣（LeetCode） 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如，给出 前序遍历 preorder =[3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树： 3 / 9 20 / 15 7 思路：经典二叉树题。给出一个中序序列和一个前序（后序）序列，建树（注意只有前序、后序序列的话无法唯一地建立一棵二叉树）。此类问题只要想办法定位根节点即可。对于本题，前序序列中的每一个节点，一定是后续子树的根节点，那么在中序序列中找到这个根节点，左侧即为左子树，右侧即为右子树。对每一个子树递归地重复这个建树过程即可。注意到不管是前序、中序还是后序序列，一个子树当中的所有元素总是紧邻地出现在一起，那么我们只需要分别记录两个序列中该子树的起始元素的指针、末尾元素的指针，就能在两个序列中划定子树范围，从而递归地执行。 时间复杂度：O(n)空间复杂度：O(n) 实现：12345678 ...

反转链表 // 题目链接-来源：力扣（LeetCode） 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。 示例 1： 输入：head = [1,3,2]输出：[2,3,1] 思路：题目不要求重组链表，只要求反向打印内容，那么用栈存储内容再逐个打印即可。 实现：12345678910111213141516class Solution { public int[] reversePrint(ListNode head) { Stack<ListNode> s = new Stack<>(); while (head != null) { s.push(head); head = head.next; } int[] ret = new int[s.size()]; int i = 0; while (!s.isEmpty()) { ...