面试资料

验证二叉搜索树给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下： 节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 示例 1： 12输入：root = [2,1,3]输出：true 示例 2： 123输入：root = [5,1,4,null,null,3,6]输出：false解释：根节点的值是 5 ，但是右子节点的值是 4 。 提示： 树中节点数目范围在[1, 104] 内 -231 <= Node.val <= 231 - 1 一般的做法是中序遍历，将遍历结果加入数组，然后判断数组是否为升序序列。 数组可以省略，因为判断是否为升序序列只需要判断当前节点的值和上一个节点的值。 用pre表示上一个节点的值，第一个节点值当然是要比前一个节点值大的，所以pre初始化为负无穷，数据范围是int最小值，所以初始化为Long.MIN_VALUE。在遍历到根节点时，更新pre 1234567891011121314151617181920212 ...

寻找重复数给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。 假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。 示例 1： 12输入：nums = [1,3,4,2,2]输出：2 示例 2： 12输入：nums = [3,1,3,4,2]输出：3 示例 3 : 12输入：nums = [3,3,3,3,3]输出：3 提示： 1 <= n <= 105 nums.length == n + 1 1 <= nums[i] <= n nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次 注意题目的数据范围，可以将数组按照链表的方式遍历，题目就变成环形链表了，先使用快慢指针找到第一次相遇的点。另一个指针从起点开始，两个指针同时出发，相遇即为环的起点，也就是重复的数 nums.length == n + 1 1 <= nums[i] <= n 12 ...

下一个排列整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。 给你一个整数数组 nums ，找出 nums 的下一个排列。 必须** 原地 **修改，只允许使用额外常数空间。 示例 1： 12输入：nums = [1,2,3]输出：[1,3,2] 示例 2： 12输入：nums = [3,2 ...

颜色分类给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，**原地** 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 必须在不使用库内置的 sort 函数的情况下解决这个问题。 示例 1： 12输入：nums = [2,0,2,1,1,0]输出：[0,0,1,1,2,2] 示例 2： 12输入：nums = [2,0,1]输出：[0,1,2] 提示： n == nums.length 1 <= n <= 300 nums[i] 为 0、1 或 2 进阶： 你能想出一个仅使用常数空间的一趟扫描算法吗？ 定义两个指针p0,p2,初始化为0和n-1,使用指针i遍历整个数组，遇到0交换到左边的区域，遇到2交换到右边的区域。 所以在遍历过程中p0左边是已经固定好的0,p2右边是已经固定好的2.所以循环结束条件是i>p2. 12345678910111213141516171819202122232425262728293031class Solution  ...

只出现一次的数字给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。 示例 1 ： 输入：nums = [2,2,1] 输出：1 示例 2 ： 输入：nums = [4,1,2,1,2] 输出：4 示例 3 ： 输入：nums = [1] 输出：1 提示： 1 <= nums.length <= 3 * 104 -3 * 104 <= nums[i] <= 3 * 104 除了某个元素只出现一次以外，其余每个元素均出现两次。 异或是相异为1，相同为0。遍历整个数组将所有元素异或，出现两次的元素相互异或变成0，最后只剩0和出现1次的元素异或，结果为该元素。 123456789class Solution { public int singleNumber(int[] nums) { int result = 0; for (int ...

编辑距离给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作： 插入一个字符 删除一个字符 替换一个字符 示例 1： 123456输入：word1 = "horse", word2 = "ros"输出：3解释：horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e') 示例 2： 12345678输入：word1 = "intention", word2 = "execution"输出：5解释：intention -> inention (删除 't')inention -> enention (将 'i' 替换为 'e')enention -> exen ...

最长公共子序列给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。 示例 1： 123输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。 示例 2： 123输入：text1 = "abc", text2 = "abc"输出：3解释：最长公共子序列是 "abc" ，它的长度为 3 。 示例 3： 123输入：text1 = & ...

最长回文子串给你一个字符串 s，找到 s 中最长的 回文 子串。 示例 1： 123输入：s = "babad"输出："bab"解释："aba" 同样是符合题意的答案。 示例 2： 12输入：s = "cbbd"输出："bb" 提示： 1 <= s.length <= 1000 s 仅由数字和英文字母组成 f[j][i]表示s[j,i]是否为回文子串，枚举字符串的起点j和终点i，如果s.charAt(i)!=s.charAt(j)，f[j][i]=false 如果s.charAt(i)==s.charAt(j),此时长度为2或3时，f[j][i]=true,否则，判断f[j+1][i-1]。当前字符串是回文串时更新最长长度和起始位置。 12345678910111213141516171819202122232425262728293031class Solution { public String longestPalindrome(Strin ...

最小路径和给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。 示例 1： 123输入：grid = [[1,3,1],[1,5,1],[4,2,1]]输出：7解释：因为路径 1→3→1→1→1 的总和最小。 示例 2： 12输入：grid = [[1,2,3],[4,5,6]]输出：12 提示： m == grid.length n == grid[i].length 1 <= m, n <= 200 0 <= grid[i][j] <= 200 走到grid[i][j]有两种方法，第一种是从左边grid[i][j-1]过来，第二种是从grid[i-1][j]过来。用f[i][j]表示从起点走到grid[i][j]的最小路径，f[i][j]=Math.min(f[i][j-1],f[i-1][j])+grid[i][j] 1234567891011121314151617181920class Solution { publ ...

不同路径一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？ 示例 1： 12输入：m = 3, n = 7输出：28 示例 2： 1234567输入：m = 3, n = 2输出：3解释：从左上角开始，总共有 3 条路径可以到达右下角。1. 向右 -> 向下 -> 向下2. 向下 -> 向下 -> 向右3. 向下 -> 向右 -> 向下 示例 3： 12输入：m = 7, n = 3输出：28 示例 4： 12输入：m = 3, n = 3输出：6 提示： 1 <= m, n <= 100 题目数据保证答案小于等于 2 * 109 和爬楼梯题目一样。考虑最后一步，可以从终点的左边过来，也可以从终点的上边过来。两条路径是互斥的，所以满足加法原理。 f[i][j]表示从[0,0]到达[i,j]的路径总数，f[i][j]=f[i-1][j]+f[i][j-1] ...