前言
2023-7-1 10:52:39
推荐
HOT 100（21~40）
46. 全排列【中等】
46.全排列
中等
2.6K
相关企业
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1： 输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例 2： 输入：nums = [0,1] 输出：[[0,1],[1,0]] 示例 3： 输入：nums = [1] 输出：[[1]]
提示：
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同
回溯
class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<List<Integer>>(); List<Integer> output = new ArrayList<Integer>(); for (int num : nums) { output.add(num); } int n = nums.length; backtrack(n, output, res, 0); return res; } public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) { // 所有数都填完了 if (first == n) { res.add(new ArrayList<Integer>(output)); } for (int i = first; i < n; i++) { // 动态维护数组 Collections.swap(output, first, i); // 继续递归填下一个数 backtrack(n, output, res, first + 1); // 撤销操作 Collections.swap(output, first, i); } } }
48. 旋转图像【中等】
48.旋转图像
中等
1.7K
相关企业
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 1： 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[7,4,1],[8,5,2],[9,6,3]] 示例 2： 输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] 输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
提示：
n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000
官方
class Solution { public void rotate(int[][] matrix) { int n = matrix.length; for (int i = 0; i < n / 2; ++i) { for (int j = 0; j < (n + 1) / 2; ++j) { int temp = matrix[i][j]; matrix[i][j] = matrix[n - j - 1][i]; matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]; matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]; matrix[j][n - i - 1] = temp; } } } }
49. 字母异位词分组【中等】
49.字母异位词分组
中等
1.5K
相关企业
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1: 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]] 示例 2: 输入: strs = [""] 输出: [[""]] 示例 3: 输入: strs = ["a"] 输出: [["a"]]
提示：
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母
官方
class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap<String, List<String>>(); for (String str : strs) { char[] array = str.toCharArray(); Arrays.sort(array); String key = new String(array); List<String> list = map.getOrDefault(key, new ArrayList<String>()); list.add(str); map.put(key, list); } return new ArrayList<List<String>>(map.values()); } }
53. 最大子数组和【中等】
53.最大子数组和
中等
6.1K
相关企业
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1： 输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 示例 2： 输入：nums = [1] 输出：1 示例 3： 输入：nums = [5,4,-1,7,8] 输出：23
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
官方
动态规划
class Solution { public int maxSubArray(int[] nums) { int pre = 0, maxAns = nums[0]; for (int x : nums) { pre = Math.max(pre + x, x); maxAns = Math.max(maxAns, pre); } return maxAns; } }
