『LeetCode』#5刷题日记

前言 📢

本日记为个人的刷题学习日记，内容非原创，仅为自己复习知识时，能够看得懂自己写的CV的代码，快速理解题意。另外，👍力扣官方的题解很好用，三叶姐🍭nb！！！！！

821 字符的最短距离

题意

给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。
返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它最近的字符 c 的距离。两个下标 i 和 j 之间的距离为 abs(i - j) ，其中 abs 是绝对值函数。
简单说，从字符串s中找一定出现的字符c，并且记录s中每个字符距离c的最短距离（因为c可能出现多次），返回记录距离的数组

思路

暴力遍历一遍字符数组，找出该字符c的位置，记录为position[]
再遍历一遍，计算当前字符与position数组中距离的最小值

class Solution {
    public int[] shortestToChar(String s, char c) {
        char[] strs = s.toCharArray();
        int len = strs.length;

        int[] answer = new int[len];
        int[] position = new int[len];
        
        int cnt = 0;

        for(int i=0; i < len; i++) {
            if(strs[i] == c) {
                position[cnt] = i;
                // System.out.println(i);
                cnt++;
            }
        }

        for(int i = 0; i < len; i++) {
            int temp = len+1;
            for(int j=0; j<cnt; j++) {
                temp = temp > Math.abs(i - position[j]) ? Math.abs(i - position[j]) : temp;
            }
            answer[i] = temp;
        }
        return answer;
    }
}

6041 多个数组求交集

题意

给你一个二维整数数组 nums ，其中 nums[i] 是由不同正整数组成的一个非空数组，
按 升序排列 返回一个数组，数组中的每个元素在 nums 所有数组 中都出现过。

思路

由于每个数组中，数字各不相同，因此所有数组中均出现的数字，其出现的次数等于数组个数
用哈希表统计所有数字出现的次数，次数等于数组个数的数字，即为我们所要找的
将这些数字添加入列表后排序，返回

class Solution {
    public List<Integer> intersection(int[][] nums) {
        int row = nums.length;
        Map<Integer, Integer> cntMap = new HashMap<>();
        // 哈希表统计数字出现的次数
        for(int i=0; i<row; i++) {
            for(int j=0; j<nums[i].length; j++) {
                cntMap.put(nums[i][j], cntMap.getOrDefault(nums[i][j], 0) + 1);
            }
        }
        // 新建数组列表
        List<Integer> list = new ArrayList<>();
        // int[] list = new int[row];
        int cnt = 0;
        for(int y : cntMap.keySet()) {
            // 将出现次数等于数组数的数字 添加进列表
            if(cntMap.get(y) == row) {
                // System.out.println(key);
                list.add(y);
            }
        }
        // 排序后返回
        Collections.sort(list);
        return list;
    }
}

知识点

剑指 Offer II 119. 最长连续序列

题意

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

思路

双指针

class Solution {
    public int longestConsecutive(int[] nums) {
        // 排除特殊情况 长度0或1的数组
        if(nums.length == 0) {
            return 0;
        }
        if(nums.length == 1) {
            return 1;
        }
        // 数组排序 从小到大满足数组连续
        Arrays.sort(nums);
        int i=0, j=1;
        // 双指针
        int tmpLen = 1, maxLen = 1;
        while(j < nums.length) {
            // 当两数连续的情况 两个指针均向前移动一位 
            // 暂时最大长度增加一位
            if(nums[i] == nums[j] - 1) {
                tmpLen++;
                i++;
                j++;
            } else if(nums[i] == nums[j]) {
                // 解决两数相同的情况 
                // i必须随着j的移动而移动 不然会出现 [0, 1, 2, 2, 2, 3, 8] nums[2] == nums[6] - 1的情况
                i++;    // i = j
                j++;    
            } else {
                // 两数不连续 暂时最大长度初始化
                i++;    // i = j
                j++;    // j = i + 1
                maxLen = tmpLen > maxLen ? tmpLen : maxLen;
                tmpLen = 1;
            }
        }
        // 最后再比较一次 避免 [1, 2, 3, 4, 5, 6, 7]这类情况
        maxLen = tmpLen > maxLen ? tmpLen : maxLen;
        return maxLen;
    }
}