LeetCode题解——随机刷题(四)

墨蓝 2022-12-08 04:14 126阅读 0赞

### 文章目录 ###

*   *  448. 找到所有数组中消失的数字
     *   *  解法
     *  438. 找到字符串中所有字母异位词
     *   *  滑动窗口
     *  581. 最短无序连续子数组
     *   *  遍历
     *  560. 和为K的子数组
     *   *  前缀和+哈希表
     *  919. 会议室 II
     *   *  排序
     *  621. 任务调度器
     *   *  排序
         *   *  推荐阅读

## 448. 找到所有数组中消失的数字 ##

[448. 找到所有数组中消失的数字][448.]

给定一个范围在 1 ≤ a\[i\] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。

找到所有在 \[1, n\] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

示例:

输入:  
\[4,3,2,7,8,2,3,1\]

输出:  
\[5,6\]

### 解法 ###

*  先遍历一遍数组，标记哪些出现过，如果nums\[Math.abs(nums\[i\]) - 1\] < 0，就表示i + 1出现过
 *  再遍历一遍，把nums\[i - 1\] < 0 的加大结果数组里。nums\[i - 1\] < 0说明i没出现过

class Solution {
        
        public List<Integer> findDisappearedNumbers(int[] nums) {
        
            for (int i = 0; i < nums.length; i++) {
        
                int newIndex = Math.abs(nums[i]) - 1;
                if (nums[newIndex] > 0) {
        
                    nums[newIndex] *= -1;
                }
            }
            List<Integer> result = new LinkedList<>();
            for (int i = 1; i <= nums.length; i++) {
        
                if (nums[i - 1] > 0) {
        
                    result.add(i);
                }
            }
            return result;
        }
    }

## 438. 找到字符串中所有字母异位词 ##

[438. 找到字符串中所有字母异位词][438.]

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
    
    字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
    
    说明：
    
    字母异位词指字母相同，但排列不同的字符串。
    不考虑答案输出的顺序。
    示例 1:
    
    输入:
    s: "cbaebabacd" p: "abc"
    
    输出:
    [0, 6]
    
    解释:
    起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
    起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
     示例 2:
    
    输入:
    s: "abab" p: "ab"
    
    输出:
    [0, 1, 2]
    
    解释:
    起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
    起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
    起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

### 滑动窗口 ###

class Solution {
        
        public List<Integer> findAnagrams(String s, String p) {
        
            // 用于返回字母异位词的起始索引
            List<Integer> res = new ArrayList<>();
            // 用 map 存储目标值中各个单词出现的次数
            HashMap<Character, Integer> map = new HashMap<>();
            for (Character c : p.toCharArray()) {
        
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
            // 用另外一个 map 存储滑动窗口中有效字符出现的次数
            HashMap<Character, Integer> window = new HashMap<>();
            int left = 0;
            int right = 0;
            // 只有当 valid == p.length 时，才说明 window 中包含了目标子串
            int valid = 0;
            while (right < s.length()) {
        
                // 如果目标子串中包含了该字符，才存入 window 中
                if (map.containsKey(s.charAt(right))) {
        
                    window.put(s.charAt(right), window.getOrDefault(s.charAt(right), 0) + 1);
                    // 只有当 window 中该有效字符数量不大于map中该字符数量，才能算一次有效包含
                    if (window.get(s.charAt(right)) <= map.get(s.charAt(right))) {
        
                        valid++;
                    }
                }
                // 如果 window 符合要求，即两个 map 存储的有效字符相同，就可以移动左指针了
                // 但是只有二个map存储的数据完全相同，才可以记录当前的起始索引，也就是left指针所在位置
                while (valid == p.length()) {
        
                    if (right - left + 1 == p.length()) {
        
                        res.add(left);
                    }
                    // 如果左指针指的是有效字符,需要更改 window 中的 key 对应的 value
                    // 如果 有效字符对应的数量比目标子串少，说明无法匹配了
                    if (map.containsKey(s.charAt(left))) {
        
                        window.put(s.charAt(left), window.get(s.charAt(left)) - 1);
                        if (window.get(s.charAt(left)) < map.get(s.charAt(left))) {
        
                            valid--;
                        }
                    }
                    left++;
                }
                right++;
            }
            return res;
        }
    }

## 581. 最短无序连续子数组 ##

[581. 最短无序连续子数组][581.]

给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
    
    你找到的子数组应是最短的，请输出它的长度。
    
    示例 1:
    
    输入: [2, 6, 4, 8, 10, 9, 15]
    输出: 5
    解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
    说明 :
    
    输入的数组长度范围在 [1, 10,000]。
    输入的数组可能包含重复元素 ，所以升序的意思是<=。

### 遍历 ###

![format_png][]

class Solution {
        
        public int findUnsortedSubarray(int[] nums) {
        
            Deque<Integer> stack = new LinkedList<>();
            int left = nums.length, right = 0;
            for (int i = 0; i < nums.length; i++) {
        
                while (!stack.isEmpty() && nums[stack.peekFirst()] > nums[i]) {
        
                    left = Math.min(left, stack.pollFirst());
                }
                stack.offerFirst(i);
            }
            stack.clear();
            for (int i = nums.length - 1; i >= 0; i--) {
        
                while (!stack.isEmpty() && nums[stack.peekFirst()] < nums[i]) {
        
                    right = Math.max(right, stack.pollFirst());
                }
                stack.offerFirst(i);
            }
            return right - left > 0 ? right - left + 1 : 0;
        }
    }

## 560. 和为K的子数组 ##

[560. 和为K的子数组][560. _K]

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = \[1,1,1\], k = 2  
输出: 2 , \[1,1\] 与 \[1,1\] 为两种不同的情况。  
说明 :

数组的长度为 \[1, 20,000\]。  
数组中元素的范围是 \[-1000, 1000\] ，且整数 k 的范围是 \[-1e7, 1e7\]。

### 前缀和+哈希表 ###

详解见[leetcode][]

class Solution {
        
        public int subarraySum(int[] nums, int k) {
        
            int count = 0, pre = 0;
            HashMap<Integer, Integer> map = new HashMap<>();
            map.put(0, 1);
            for (int i = 0; i < nums.length; i++) {
        
                pre += nums[i];
                if (map.containsKey(pre - k)) {
        
                    count += map.get(pre - k);
                }
                map.put(pre, map.getOrDefault(pre, 0) + 1);
            }
            return count;
        }
    }

## 919. 会议室 II ##

[会议室 II][II]

给定一系列的会议时间间隔intervals，包括起始和结束时间`[[s1,e1],[s2,e2],...] (si < ei)`，找到所需的最小的会议室数量。

**样例1**

输入: intervals = [(0,30),(5,10),(15,20)]
    输出: 2
    解释:
    需要两个会议室
    会议室1:(0,30)
    会议室2:(5,10),(15,20)

**样例2**

输入: intervals = [(2,7)]
    输出: 1
    解释:
    只需要1个会议室就够了

### 排序 ###

/**
     * Definition of Interval:
     * public classs Interval {
     *     int start, end;
     *     Interval(int start, int end) {
     *         this.start = start;
     *         this.end = end;
     *     }
     * }
     */
    
    public class Solution {
        
        /**
         * @param intervals: an array of meeting time intervals
         * @return: the minimum number of conference rooms required
         */
        public int minMeetingRooms(List<Interval> intervals) {
        
            // 对intervals，按start升序排列
            Collections.sort(intervals, (x, y) -> x.start - y.start);
            List<Integer> rooms = new ArrayList<Integer>();
            boolean flag = false;
            for (Interval x : intervals) {
        
                for (int i = 0; i < rooms.size(); i++) {
        
                    // 满足这个条件，说明可以共用一个room
                    if (x.start > rooms.get(i)) {
        
                        rooms.set(i, x.end);
                        flag = true;
                        break;
                    }
                }
                // flag = false,说明只能新开一个room
                if (!flag) {
        
                    rooms.add(x.end);
                }
                flag = false;
            }
            // 最后rooms的大小，即结果
            return rooms.size();
        }
    }

## 621. 任务调度器 ##

[621. 任务调度器][621.]

给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。

然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的最短时间。

示例 ：
    
    输入：tasks = ["A","A","A","B","B","B"], n = 2
    输出：8
    解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
         在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。 
    
    
    提示：
    
    任务的总个数为 [1, 10000]。
    n 的取值范围为 [0, 100]。

### 排序 ###

详解见[leetcode][leetcode 1]

class Solution {
        
        public int leastInterval(char[] tasks, int n) {
        
            int[] map = new int[26];
            for (char c : tasks) {
        
                map[c - 'A']++;
            }
            Arrays.sort(map);
            int maxVal = map[25] - 1, slots = maxVal * n;
            for (int i = 24; i >= 0 && map[i] > 0; i--) {
        
                slots -= Math.min(map[i], maxVal);
            }
            return slots > 0 ? slots + tasks.length : tasks.length;
        }
    }

--------------------

#### 推荐阅读 ####

*  [剑指offer精品题解][offer]
 *  [机器学习资料汇总][Link 1]
 *  [吴恩达《机器学习》视频、作业、源码][Link 2]
 *  [106页《Python进阶》中文版正式发布][106_Python]
 *  [李航《统计学习方法》第二版完整课件][Link 3]
 *  [机器学习数学全书，1900页PDF下载][1900_PDF]

--------------------

**欢迎关注我的公众号呦，率先更新内容，并且后续还有一些源码级的免费教程推出。**  
![format_png 1][]

[448.]: https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/
[438.]: https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/
[581.]: https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/
[format_png]: /images/20221123/67ee90e3b8ad4cf882be0508ac0b620e.png
[560. _K]: https://leetcode-cn.com/problems/subarray-sum-equals-k/
[leetcode]: https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/he-wei-kde-zi-shu-zu-by-leetcode-solution/
[II]: https://www.lintcode.com/problem/meeting-rooms-ii/description
[621.]: https://leetcode-cn.com/problems/task-scheduler/
[leetcode 1]: https://leetcode-cn.com/problems/task-scheduler/solution/ren-wu-diao-du-qi-by-leetcode/
[offer]: https://mp.weixin.qq.com/s/R5VKVxOYBr6CcGTIrlLQpw
[Link 1]: https://mp.weixin.qq.com/s/3nOkk_Yt9D7Qp1WaWEjyZQ
[Link 2]: https://mp.weixin.qq.com/s/dErZNtBYbVA7ItPm7T_HIw
[106_Python]: https://mp.weixin.qq.com/s/_WEuuxj-QgihijjLz7NJ9g
[Link 3]: https://mp.weixin.qq.com/s/xah47OWuu8ahAUa1aFFo4Q
[1900_PDF]: https://mp.weixin.qq.com/s/9BuyhdwuHiHH3ksVUe44ZQ
[format_png 1]: /images/20221123/41981bc021b94040967f86295086accc.png