概述
力扣每日练习-java版（五）
- 31. 下一个排列
- 思路
- 代码
- 时空复杂度
- 备注
- 49. 字母异位词分组
- 思路
- 代码
- 时空复杂度
- 备注
- 1288. 删除被覆盖区间
- 思路
- 代码
- 时空复杂度
- 备注
- 56. 合并区间
- 思路
- 代码
- 时空复杂度
- 备注
- 986. 区间列表的交集
- 思路
- 代码
- 时空复杂度
- 备注
31. 下一个排列
https://leetcode-cn.com/problems/next-permutation/
思路
1.希望下一个数比当前数大
2.希望增加的幅度尽可能的小
根据以上两点要求，可以得出，我们要把低位的大数（尽可能小）和高位的小数交换，且尽量在低位做交换。
所以我们需要四步操作：
1.从右向左查找第一个相邻升序的元素对 (i,j)，满足 A[i] < A[j]。此时 [j,end) 必然是降序
2.在 [j,end) 从右向左查找第一个满足 A[k] > A[i] 的 k。A[i]、A[k] 分别就是上文所说的「小数」、「大数」
3.将 A[i] 与 A[k] 交换
4.因为这时 [j,end) 必然是降序，要想让增加的幅度尽可能小，我们要逆置 [j,end)部分，使其升序
5.如果在步骤 1 找不到符合的相邻元素对，说明数组A从 [begin,end)整个范围都是降序顺序，则直接跳到步骤 4整体转换为升序
代码
class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[i] >= nums[j]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i + 1);
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public void reverse(int[] nums, int start) {
int left = start, right = nums.length - 1;
while (left < right) {
swap(nums, left, right);
left++;
right--;
}
}
}
时空复杂度
1.时间复杂度
O(N)，其中 N 为给定序列的长度。我们至多只需要扫描两次序列，以及进行一次反转操作。
2.空间复杂度
O(1)，只需要常数的空间存放若干变量。
备注
1.算法中的交换、反转操作有多次时，可以考虑封装成函数
49. 字母异位词分组
https://leetcode-cn.com/problems/group-anagrams/
思路
1.排序
将字符串排序，所有源单词中的字母通常恰好只用一次，所以排序后都是一样的结果，排序后的结果作为key，源单词作为value，最后返回所有的value list即可。
2.计算字母出现次数
由于互为字母异位词的两个字符串包含的字母相同，因此两个字符串中的相同字母出现的次数一定是相同的，故可以将每个字母出现的次数使用字符串表示，作为哈希表的键。由于字符串只包含小写字母，因此对可以使用长度为 26 的数组记录每个字母出现的次数。
代码
方法一：
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());
}
}
方法二：
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<String, List<String>>();
for (String str : strs) {
int[] counts = new int[26];
int length = str.length();
for (int i = 0; i < length; i++) {
counts[str.charAt(i) - 'a']++;
}
// 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 26; i++) {
if (counts[i] != 0) {
sb.append((char) ('a' + i));
sb.append(counts[i]);
}
}
String key = sb.toString();
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}
时空复杂度
方法一：
方法二：
备注
1.str.toCharArray(); 字符串转字符数组
2.Arrays.sort(array); 数组排序
3.map.values(); 获取map里所有的value list
4.map.getOrDefault(key,default_value) ; 获取key的value，没查到返回默认值
5.方法一用java的stream实现
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
return new ArrayList<>(Arrays.stream(strs)
.collect(Collectors.groupingBy(str -> {
// 返回 str 排序后的结果。
// 按排序后的结果来grouping by，类似于 sql 里的 group by。返回的是一个 Map<String, List<String>>,我们只需要取出这个map里的value list就好。用map.values();
char[] array = str.toCharArray();
Arrays.sort(array);
return new String(array);
})).values());
}
}
1288. 删除被覆盖区间
https://leetcode-cn.com/problems/remove-covered-intervals/
思路
数字题，没头绪可以先排序试试，看有没有规律。
这道题按start升序，end降序排序，有三种情况。
对于这三种情况，我们应该这样处理：
对于情况一，找到了覆盖区间，结果+1。
对于情况二，两个区间可以合并成一个大区间。扩大end边界。
对于情况三，两个区间完全不相交。更新start和end。
代码
class Solution {
public int removeCoveredIntervals(int[][] intervals) {
// 按照起点升序排列，起点相同时降序排列
Arrays.sort(intervals, (a, b) -> {
if (a[0] == b[0]) {
return b[1] - a[1];
}
return a[0] - b[0];
});
// 记录合并区间的起点和终点
int start = intervals[0][0];
int end = intervals[0][1];
int res = 0;
for (int i = 1; i < intervals.length; i++) {
int[] intv = intervals[i];
// 情况一，找到覆盖区间
if (start <= intv[0] && end >= intv[1]) {
res++;
}
// 情况二，找到相交区间，合并
if (end >= intv[0] && end <= intv[1]) {
end = intv[1];
}
// 情况三，完全不相交，更新起点和终点
if (end < intv[0]) {
start = intv[0];
end = intv[1];
}
}
return intervals.length - res;
}
}
时空复杂度
1.时间复杂度
O(NlogN)。排序过程O(NlogN)，解析排序后的输入数据花费O(N)
2.空间复杂度
O(logN)，其中 N 为区间的数量，O(logN) 为排序所需要的空间复杂度。
备注
1.数组的第一个元素升序，第二个元素降序
Arrays.sort(intervals, (a, b) -> {
if (a[0] == b[0]) {
return b[1] - a[1];
}
return a[0] - b[0];
});
2.思路
数字题，范围题，没有头绪就先排序找规律试试。
56. 合并区间
https://leetcode-cn.com/problems/merge-intervals/
思路
和上一题思路类似，按start升序排序，如果下一个区间的start<=上一个区间的end，就将两个区间合并，end是两个end的最大值【下图情况1和情况2】；如果下一个区间的start>上一个区间的end，将上一个区间放入结果集，处理下一个待合并区间。
代码
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length == 0) {
return new int[0][2];
}
//排序
Arrays.sort(intervals,(a,b)->{
return a[0]-b[0];
});
//结果集
List<int[]> res = new ArrayList<>();
//合并区间
for(int i = 0;i<intervals.length;i++){
int l = intervals[i][0];
int r = intervals[i][1];
if (res.size() == 0 || l > res.get(res.size() - 1)[1]) {
res.add(new int[]{l, r});
} else {
res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], r);
}
}
return res.toArray(new int[res.size()][]);
}
}
时空复杂度
1.时间复杂度
O(NlogN)。排序过程O(NlogN)，解析排序后的输入数据花费O(N)
2.空间复杂度
O(logN)，其中 N 为区间的数量，O(logN) 为排序所需要的空间复杂度。
备注
1.list转数组
res.toArray(new int[res.size()][]);
986. 区间列表的交集
https://leetcode-cn.com/problems/interval-list-intersections/
思路
1.我们用 [a1, a2] 和 [b1, b2] 表示在 A 和 B 中的两个区间，如果这两个区间有交集，需满足 b2 >= a1 && a2 >= b1，分下面四种情况：
可以发现规律，假设交集区间是 [c1, c2]，那么 c1 = max(a1, b1), c2 = min(a2, b2)
2.什么时候换到下一区间？
如果b2 < a2， B的指针走向下一个元素，否则A的指针走向下一个元素
代码
class Solution {
public int[][] intervalIntersection(int[][] A, int[][] B) {
List<int[]> res = new LinkedList<>();
int i = 0, j = 0;
while (i < A.length && j < B.length) {
int a1 = A[i][0], a2 = A[i][1];
int b1 = B[j][0], b2 = B[j][1];
if (b2 >= a1 && a2 >= b1) {
res.add(new int[]{
Math.max(a1, b1), Math.min(a2, b2)
});
}
if (b2 < a2) {
j++;
} else {
i++;
}
}
return res.toArray(new int[0][0]);
}
}
时空复杂度
1.时间复杂度
O(M+N)，其中M,N 分别是数组 A 和 B 的长度。
2.空间复杂度
O(M+N)，答案中区间数量的上限。
备注
1.元素是数组的list
List<int[]> res = new LinkedList<>();
最后
以上就是过时豌豆为你收集整理的力扣每日练习-java版（五）31. 下一个排列49. 字母异位词分组1288. 删除被覆盖区间56. 合并区间986. 区间列表的交集的全部内容，希望文章能够帮你解决力扣每日练习-java版（五）31. 下一个排列49. 字母异位词分组1288. 删除被覆盖区间56. 合并区间986. 区间列表的交集所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复