算法基础七
缺失的第一个正数
给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
示例 1:输入:nums = [1,2,0] 输出:3
示例 2:输入:nums = [3,4,-1,1] 输出:2
示例 3:输入:nums = [7,8,9,11,12] 输出:1
解题思路:为了减少复杂度,可以把数组缓存到map中,然后将 i 从1开始循环,一次对比map中是否存在 i 只要不存在就立即返回结果 i。
public int firstMissingPositive(int[] nums) {
int len = nums.length;
for(int i = 0; i < len; ++i) {
if (nums[i] <= 0) {
nums[i] = len + 1;
}
}
for(int i = 0; i < len; ++i) {
int num = Math.abs(nums[i]);
if (num <= len) {
nums[num - 1] = -Math.abs(nums[num - 1]);
}
}
for (int i = 0; i < len; ++i) {
if (nums[i] > 0) {
return i + 1;
}
}
return len + 1;
}
全排列
给定一个不含重复数字的数组 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]]
解题思路:DFS深搜
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> output = new ArrayList<>();
for(int num : nums) {
output.add(num);
}
int len = nums.length;
backtrack(len, output, res, 0);
return res;
}
public void backtrack(int len, List<Integer> output, List<List<Integer>> res, int first) {
if (first == len) {
res.add(new ArrayList<>(output));
}
for (int i = first; i < len; i++) {
Collections.swap(output, first, i);
backtrack(len, output, res, first + 1);
Collections.swap(output, first, i);
}
}
全排列二
给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。
示例 1:
输入:nums = [1,1,2] 输出: [[1,1,2], [1,2,1], [2,1,1]]
示例 2:
输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
解题思路:DFS深搜
boolean[] vis;
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
List<Integer> perm = new ArrayList<Integer>();
vis = new boolean[nums.length];
Arrays.sort(nums);
backtrack(nums, ans, 0, perm);
return ans;
}
public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
if (idx == nums.length) {
ans.add(new ArrayList<Integer>(perm));
return;
}
for (int i = 0; i < nums.length; ++i) {
if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
continue;
}
perm.add(nums[i]);
vis[i] = true;
backtrack(nums, ans, idx + 1, perm);
vis[i] = false;
perm.remove(idx);
}
}
旋转图像
给定一个 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]]
public void rotate(int[][] matrix) {
int len = matrix.length;
int[][] matrix_new = new int[len][len];
for(int i = 0; i < len; ++i) {
for(int j = 0; j < len; ++j) {
matrix_new[j][len - i - 1] = matrix[i][j];
}
}
for(int i = 0; i < len; ++i) {
for(int j = 0; j < len; ++j) {
matrix[i][j] = matrix_new[i][j];
}
}
}
字母异位词分组
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
示例 2:
输入: strs = [“”]
输出: [[“”]]
示例 3:
输入: strs = [“a”]
输出: [[“a”]]
解题思路:将每个字符串排序,排完序以后相同的字符串结果一样。
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());
}
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!