文章目录
- 面试经典150题【41-50】
- 49.字母异位词分组
- 1. 两数之和
- 202.快乐数
- 219. 存在重复元素II
- 128.最长连续序列
- 228. 汇总区间
- 56.合并区间（华为面试题）
- 57.插入区间
- 452.用最少的箭引爆气球
- 20.有效的括号
面试经典150题【41-50】
49.字母异位词分组
用这种流式的处理
return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(str -> { 处理逻辑 }））.values() );
不然处理起来太麻烦了。
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。
char[] array = str.toCharArray();
Arrays.sort(array);
return new String(array);
})).values());
}
}
如果不排序的话，可以进行编码： [b,a,a,a,b,c] 编码成 a3b2c1， 然后再group by.
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
return new ArrayList<>(Arrays.stream(strs)
.collect(Collectors.groupingBy(str -> {
int[] counter = new int[26];
for (int i = 0; i < str.length(); i++) {
counter[str.charAt(i) - 'a']++;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 26; i++) {
// 这里的 if 是可省略的，但是加上 if 以后，生成的 sb 更短，后续 groupingBy 会更快。
if (counter[i] != 0) {
sb.append((char) ('a' + i));
sb.append(counter[i]);
}
}
return sb.toString();
})).values());
}
}
1. 两数之和
每遍历一个数，就把这个数字放到哈希表里。当遍历到下一个数字的时候，看哈希表里是否存在Key为 target - nums[i] 的值。
202.快乐数
这个如果不是1，会进入一个循环。判断循环就用双指针就行。
判断成环。一个是可以用快慢指针，他们俩相遇则有环。一个是可以用一个set,如果有重复元素则有环。
219. 存在重复元素II
区间大小为k，但是怎么保证K个里面能直接查出元素呢。
方法一：定义一个大小为k的hashSet, 如果包含元素则说明重复。因为hashSet会自动扩容，所以写法是： if(hashSet.size() > k) hashSet.remove(nums[ i -k ] )
方法二：哈希表记录[k,v]—> [ nums[i],i] ,如果包含则比较与i的距离，大于k则将[nums[i],j] 赋值给[nums[i],i] ，继续遍历。
128.最长连续序列
因为是O(n) ，所以不能排序。遍历一遍，放到set里。
然后再遍历一遍Set, 如果包含 nums[i]+1,依次遍历有没有nums[i] +2, nums[i] +3 等等
但是这样也会导致很多重复的遍历。 可以放到map里 [key,value] ->[ nums[i], 左右最长的长度]
当前的长度 = left + right +1
public int longestConsecutive(int[] nums) {
HashMap<Integer,Integer> hashMap=new HashMap<>();
int ans=0;
for(int i=0;i<nums.length;i++){
//包含说明以前处理过，不包含的话可能是单独，也可能是边界，也可能是刚好插在俩个大条之间
if(!hashMap.containsKey(nums[i])){
int left=hashMap.getOrDefault(nums[i]-1,0);
int right=hashMap.getOrDefault(nums[i]+1,0);
int tempAns=left+right+1;
if(tempAns>ans){
ans=tempAns;
}
hashMap.put(nums[i],tempAns);
//不能只更新自己，边界也要更新
hashMap.put(nums[i]+right,tempAns);
hashMap.put(nums[i]-left,tempAns);
}
}
return ans;
}
228. 汇总区间
按照题意模拟即可。
56.合并区间（华为面试题）
先按左区间排序，然后依次遍历，根据 nums[i+1][0] 和 nums[i][1] 判断是否需要合并。
public class LC56 {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0]-o2[0];
}
});
ArrayList<int[]> ans=new ArrayList<>();
int left=intervals[0][0],right=intervals[0][1];
for(int i=1;i<intervals.length;i++){
if(intervals[i][0]>right){
//不合并，装载
ans.add(new int[]{left,right});
//开始记录新的区间
left=intervals[i][0];
right=intervals[i][1];
}else{
//合并区间
right=Math.max(right,intervals[i][1]);
}
}
//无论是intervals里只有一个元素的特判， 还是 正常情况下最后一步， 都要有下面这一行。
ans.add(new int[]{left,right});
return ans.toArray(new int[][]{});
}
}
57.插入区间
和56.合并区间一个意思
452.用最少的箭引爆气球
所有的这种二维数组的，都要先排序。无非就是按照 左边界 排序 或者按照 右边界 排序。
而气球这种场景，应该是按照右边界排序，然后射击第一个存在的气球的最右边。
判断此次射击会爆几个气球，要看别的气球的左边界是否小于射击点。（因为是按右边界排序的，右边肯定是大的，左边小就能被射到）
public int findMinArrowShots(int[][] points) {
if(points.length==0) return 0;
Arrays.sort(points, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
//return o1[1]-o2[1];
if(o1[1]>o2[1]){
return 1;
}else if(o1[1]<o2[1]){
return -1;
}else{
return 0;
}
}
});
//按右边界 进行排序
//击毙第一个气球的最右边，能击毙几个算几个。
//pos为击毙点
int pos=points[0][1];
int ans=1;
for(int i=0;i<points.length;i++){
//因为是按右边界排序的，判断第i个气球爆没爆，要看第i个气球的左边界。
if(pos<points[i][0]){
ans++;
pos=points[i][1];
}
}
return ans;
}
20.有效的括号
一个个单词放到栈里，放左括号，遇到右括号检查栈顶是否为对应的左括号即可。
