面试资料

寻找旋转排序数组中的最小值已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到： 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2] 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7] 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。 示例 1： 123输入：nums = [3,4,5,1,2]输出：1解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。 示例 2： 123输入：nums = [4,5,6,7,0,1,2]输出：0解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数 ...

搜索旋转排序数组整数数组 nums 按升序排列，数组中的值 互不相同 。 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。 示例 1： 12输入：nums = [4,5,6,7,0,1,2], target = 0输出：4 示例 2： 12输入：nums = [4,5,6,7,0,1,2], target = 3输出：-1 示例 3： 12输入：nums = [1], target = 0输出：-1 提示： 1 ...

在排序数组中查找元素的第一个和最后一个位置给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 示例 1： 12输入：nums = [5,7,7,8,8,10], target = 8输出：[3,4] 示例 2： 12输入：nums = [5,7,7,8,8,10], target = 6输出：[-1,-1] 示例 3： 12输入：nums = [], target = 0输出：[-1,-1] 提示： 0 <= nums.length <= 105 -109 <= nums[i] <= 109 nums 是一个非递减数组 -109 <= target <= 109 简单的二分。 二分查找边界问题。查找左边界也就是nums[mid]>=target的边界，查找有边界就是查找nums[mid]<=target的边界 1234567 ...

搜索二分位置给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 12输入: nums = [1,3,5,6], target = 5输出: 2 示例 2: 12输入: nums = [1,3,5,6], target = 2输出: 1 示例 3: 12输入: nums = [1,3,5,6], target = 7输出: 4 提示: 1 <= nums.length <= 104 -104 <= nums[i] <= 104 nums 为 无重复元素 的 升序 排列数组 -104 <= target <= 104 二分模板题 解法1 123456789101112131415161718192021class Solution { public int searchInsert(int[] nums, int target) { int l = 0; i ...

N皇后按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。 示例 1： 123输入：n = 4输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]解释：如上图所示，4 皇后问题存在两个不同的解法。 示例 2： 12输入：n = 1输出：[["Q"]] 提示： 1 <= n <= 9 使用DFS搜索每一种情况。 1234567891011121314151617181920212223242 ...

分割回文串给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。 示例 1： 12输入：s = "aab"输出：[["a","a","b"],["aa","b"]] 示例 2： 12输入：s = "a"输出：[["a"]] 提示： 1 <= s.length <= 16 s 仅由小写英文字母组成 1234567891011121314151617181920212223242526272829303132333435363738394041class Solution { private List<List<String>> res = new ArrayList<>(); private List<String> list = new ArrayList<>(); ...

单词搜索给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 示例 1： 12输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"输出：true 示例 2： 12输入：board = [["A","B","C","E"],["S","F","C& ...

括号生成数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 示例 1： 12输入：n = 3输出：["((()))","(()())","(())()","()(())","()()()"] 示例 2： 12输入：n = 1输出：["()"] 提示： 1 <= n <= 8 **只有当 ( 数量小于 n 时，才能添加 (**。 **只有当 ) 数量小于 ( 数量时，才能添加 )**，确保括号合法。 终止条件： 括号字符串长度达到 2 * n，将其加入结果集。 123456789101112131415161718192021222324252627class Solution { private List<String> res = new ArrayList<>(); private StringBuilder sb; public List< ...

组合总和给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。 示例 1： 123456输入：candidates = [2,3,6,7], target = 7输出：[[2,2,3],[7]]解释：2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。7 也是一个候选， 7 = 7 。仅有这两种组合。 示例 2： 12输入: candidates = [2,3,5], target = 8输出: [[2,2,2,2],[2,3,3],[3,5]] 示例 3： 12输入: candidates = [2], target = 1输出: [] 提示： 1 <= candidates. ...

电话号码的字母组合给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 示例 1： 12输入：digits = "23"输出：["ad","ae","af","bd","be","bf","cd","ce","cf"] 示例 2： 12输入：digits = ""输出：[] 示例 3： 12输入：digits = "2"输出：["a","b","c"] 提示： 0 <= digits.length <= 4 digits[i] 是范围 ['2', '9'] 的一个数字。 使用DFS判断给每一位赋值 123456789101 ...