首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode 题解——697/925

Leetcode 题解——697/925

作者头像
出其东门
发布2019-07-19 11:21:48
2970
发布2019-07-19 11:21:48
举报
文章被收录于专栏:01二进制01二进制

697. 数组的度

题目

https://leetcode-cn.com/problems/degree-of-an-array/

题解
  1. 先计算出所有数字的频率(用 map 解决)
  2. 求出度,这里只需要在一开始就设置一个 max,只要某一数字的频率大于 max 就更新
  3. 考虑到可能有多个频率相同的数字,我们可以用一个 List 存储多个最大的 max 的值
  4. 在遍历的过程中记录下所出现的开始位置和结束位置,并存入一个只有两个元素的数组中
  5. 遍历包含所有最大值的数组 List,计算每个值所对应的数组的距离,返回最小值即可
代码
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;
    }

}

925. 长按键入

题目

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();
    }
}
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-06-29,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 01二进制 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 697. 数组的度
    • 题目
      • 题解
        • 代码
        • 925. 长按键入
          • 题目
            • 题解
              • 代码
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档