https://leetcode-cn.com/problems/degree-of-an-array/
public class Main {
public static void main(String[] args) {
Main main = new Main();
int[] a = {1, 2, 2, 3, 1};
System.out.println(main.findShortestSubArray(a));
}
public int findShortestSubArray(int[] nums) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
//存储频率最大的几个数
List<Integer> maxNum = new ArrayList<>();
//存储每个数的频率
Map<Integer, Integer> fre = new HashMap<>();
//存储频率最大的数的度
Map<Integer, int[]> degree = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
int frequency = fre.getOrDefault(num, 0) + 1;
if (frequency > fre.getOrDefault(max, 0)) {
maxNum.clear();
maxNum.add(num);
max = num;
} else if (frequency == fre.getOrDefault(max, 0)) {
maxNum.add(num);
}
fre.put(num, frequency);
int d = degree.getOrDefault(num, new int[]{i, i})[0];
degree.put(num, new int[]{d, i});
}
for (int i : maxNum) {
int d = degree.get(i)[1] - degree.get(i)[0];
if (d < min) min = d;
}
return min + 1;
}
}
https://leetcode-cn.com/problems/long-pressed-name/
双指针遍历,指针 i 用于遍历 name,指针 j 用于遍历 typed,从 0 开始进行计算,如果 name[i]==typed[j]
,则游标后移一位,即 i++,j++
;如果不等,就看看 i 是不是 0,如果是 0 直接 false,如果不是 0,就看 typed[j]
和 name[i-1]
是否一致(如果一致,则说明 typed 多了一位),最后返回结果即可
public class Main {
public static void main(String[] args) {
Main main = new Main();
System.out.println(main.isLongPressedName("kikcxmvzi","kiikcxxmmvvzz"));
}
public boolean isLongPressedName(String name, String typed) {
int i = 0;
for (int j = 0; i < name.length() && j < typed.length(); j++) {
if (name.charAt(i) == typed.charAt(j))
i++;
else if (i == 0 || name.charAt(i - 1) != typed.charAt(j))
return false;
}
return i == name.length();
}
}