LeetCode 每日一题

LeetCode周报

• 1838. 最高频元素的频数 （2021.7.19，中等）
• 1877. 数组中最大数对和的最小值 （2021.7.20，中等）
• 剑指 Offer 52. 两个链表的第一个公共节点 (2021.7.21，简单)
• 138. 复制带随机指针的链表 （2021.7.22，中等）
• 1893. 检查是否区域内所有整数都被覆盖 （2021.7.23，简单）
• 1736. 替换隐藏数字得到的最晚时间 （2021.7.24，中等）
• 1743. 从相邻元素对还原数组 （2021.7.25，中等）

1838. 最高频元素的频数 （2021.7.19，中等）

元素的 频数 是该元素在一个数组中出现的次数。

给你一个整数数组 nums
和一个整数 k
。在一步操作中，你可以选择 nums
的一个下标，并将该下标对应元素的值增加 1 。

执行最多 k
次操作后，返回数组中最高频元素的 最大可能频数 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/frequency-of-the-most-frequent-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例 1：

输入：nums = [1,2,4], k = 5

输出：3

解释：对第一个元素执行 3 次递增操作，对第二个元素执 2 次递增操作，此时 nums = [4,4,4] 。4 是数组中最高频元素，频数是 3 。

示例 2：

输入：nums = [1,4,8,13], k = 5

输出：2

解释：存在多种最优解决方案：
- 对第一个元素执行 3 次递增操作，此时 nums = [4,4,8,13] 。4 是数组中最高频元素，频数是 2 。
- 对第二个元素执行 4 次递增操作，此时 nums = [1,8,8,13] 。8 是数组中最高频元素，频数是 2 。
- 对第三个元素执行 5 次递增操作，此时 nums = [1,4,13,13] 。13 是数组中最高频元素，频数是 2 。

示例 3：

输入：nums = [3,9,6], k = 2

输出：1

提示：

• 1 <= nums.length <= 10^5
  
• 1 <= nums[i] <= 10^5
  
• 1 <= k <= 10^5
  

Answer

排序 + 滑动窗口。i
为右边界，j
为左边界，通过控制左右边界控制窗口的大小，保证窗口内的元素始终满足要求，即经过k次以内的变化后其值都可以变为当前窗口的最大频数的数字。

class Solution {
    // 滑动窗口算法，最后的目标一定是在目标内
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int ans = 1;
        int sum = 0;
        int j = 0;
        for (int i = 1; i < nums.length; i++) {
            sum += (nums[i] - nums[i-1]) * (i - j);
            while (sum > k) {
                sum = sum - (nums[i] - nums[j]);
                j++;
            }
            ans = Math.max(ans, i - j + 1);
        }
        return ans;
    }
}

以 示例1 为例模拟整个过程：

1877. 数组中最大数对和的最小值 （2021.7.20，中等）

一个数对 (a,b)
的 数对和 等于 a + b
。最大数对和 是一个数对数组中最大的 数对和 。

比方说，如果我们有数对 (1,5) ，(2,3) 和 (4,4)，最大数对和 为 max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8
。给你一个长度为 偶数 n 的数组 nums ，请你将 nums 中的元素分成 n 2 个数对，使得：

• nums 中每个元素 恰好 在 一个 数对中，且
• 最大数对和 的值 最小 。

请你在最优数对划分的方案下，返回最小的 最大数对和 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimize-maximum-pair-sum-in-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例 1：

输入：nums = [3,5,2,3]

输出：7

解释：数组中的元素可以分为数对 (3,3) 和 (5,2) 。
最大数对和为 max(3+3, 5+2) = max(6, 7) = 7 。

示例 2：

输入：nums = [3,5,4,2,4,6]

输出：8

解释：数组中的元素可以分为数对 (3,5)，(4,4) 和 (6,2) 。
最大数对和为 max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8 。

提示：

• n == nums.length
  
• 2 <= n <= 10^5
  
• n
  是 偶数 。
• 1 <= nums[i] <= 10^5
  

Answer

排序 + 贪心。将 nums
排序。排序后，我们遍历每一个第 k
大与第 k
小组成的数对，计算它们的和，并维护这些和的最大值。遍历完成后求得的最大数对和就是满足要求的最小值。即依次将有序数组中未选中的数据的最大值和最小值进行匹配，更新其最大值即可。

class Solution {
    public int minPairSum(int[] nums) {
        int n = nums.length;
        int res = 0;
        Arrays.sort(nums);
        for (int i = 0; i < n / 2; ++i) {
            res = Math.max(res, nums[i] + nums[n - 1 - i]);
        }
        return res;
    }
}

以 示例1 为例模拟整个过程：

剑指 Offer 52. 两个链表的第一个公共节点 （2021.7.21，简单）

输入两个链表，找出它们的第一个公共节点。如下面的两个链表**：**

在节点 c1 开始相交。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3

输出：Reference of the node with value = 8

输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2:

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

输出：null

输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

• 如果两个链表没有交点，返回 null.
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
• 本题与主站 160 题相同：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

Answer

双指针。当指针到达末尾时指向另一个链表，消除长度差，最终两个指针终将会指向公共结点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p = headA, q = headB;
        while (p != q) {
            p = p == null ? headB : p.next;
            q = q == null ? headA : q.next;
        }
        return p;
    }
}

以 示例1 为例模拟整个过程：

138. 复制带随机指针的链表 （2021.7.22，中等）

给你一个长度为 n
的链表，每个节点包含一个额外增加的随机指针 random
，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next
指针和 random
指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X
和 Y
两个节点，其中 X.random --> Y
。那么在复制链表中对应的两个节点 x
和 y
，同样有 x.random --> y
。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index]
表示：

• val
  ：一个表示 Node.val
  的整数。
• random_index
  ：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]

输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]

输出：[[3,null],[3,0],[3,null]]

示例 4：

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示：

• 0 <= n <= 1000
  
• -10000 <= Node.val <= 10000
  
• Node.random
  为空（null）或指向链表中的节点。

Answer

迭代 + 结点拆分。我们首先将该链表中每一个节点拆分为两个相连的节点，例如对于链表 A→B→C
，我们可以将其拆分为 A → A′ → B → B′ → C → C′
。对于任意一个原节点 S
，其拷贝节点 S′
即为其后继节点。这样，我们可以直接找到每一个拷贝节点 S′
的随机指针应当指向的节点，即为其原节点 S
的随机指针指向的节点 T
的后继节点 T′
。需要注意原节点的随机指针可能为空，我们需要特别判断这种情况。

当我们完成了拷贝节点的随机指针的赋值，我们只需要将这个链表按照原节点与拷贝节点的种类进行拆分即可，只需要遍历一次。同样需要注意最后一个拷贝节点的后继节点为空，我们需要特别判断这种情况。

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
        public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        for (Node node = head; node != null; node = node.next.next) {
            Node nodeNew = new Node(node.val);
            nodeNew.next = node.next;
            node.next = nodeNew;
        }
            
        for (Node node = head; node != null; node = node.next.next) {
            Node nodeNew = node.next;
            nodeNew.random = (node.random != null) ? node.random.next : null;
        }
            
        Node headNew = head.next;
        for (Node node = head; node != null; node = node.next) {
            Node nodeNew = node.next;
            node.next = node.next.next;
            nodeNew.next = (nodeNew.next != null) ? nodeNew.next.next : null;
        }
        return headNew;
    }
}

1893. 检查是否区域内所有整数都被覆盖 （2021.7.23，简单）

给你一个二维整数数组 ranges
和两个整数 left
和 right
。每个 ranges[i] = [start i, end i]
表示一个从 start i
到 end i
的 闭区间。

如果闭区间 [left, right]
内每个整数都被 ranges
中 至少一个 区间覆盖，那么请你返回 true
，否则返回 false
。

已知区间 ranges[i] = [start i, end i]
，如果整数 x
满足 start i <= x <= end i
，那么我们称整数x
被覆盖了。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/check-if-all-the-integers-in-a-range-are-covered
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例 1：

输入：ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5

输出：true

解释：2 到 5 的每个整数都被覆盖了：
- 2 被第一个区间覆盖。
- 3 和 4 被第二个区间覆盖。
- 5 被第三个区间覆盖。

示例 2：

输入：ranges = [[1,10],[10,20]], left = 21, right = 21

输出：false

解释：21 没有被任何一个区间覆盖。

提示：

• 1 <= ranges.length <= 50
  
• 1 <= starti <= endi <= 50
  
• 1 <= left <= right <= 50
  

Answer

常规思路。为了判断某个区域内所有整数都被覆盖，我们需要对每个整数 x
计算覆盖该整数的区间数量，记作 cnt_x
。朴素的做法是，遍历 ranges
中的所有区间 [l,r]
，将区间内每个整数的 cnt
值加上 1。遍历结束后，检查 [left,right]
内的每个整数的 cnt
值是否均大于 0，是则返回 true
，否则返回 false
。

class Solution {
    public boolean isCovered(int[][] ranges, int left, int right) {
        for(int i = left; i <= right; i++){
            boolean flag = false;
            for(int j = 0; j < ranges.length; j++){
                if(i <= ranges[j][1] && i >= ranges[j][0]){
                    flag = true;
                    break;
                }
            }
            if(!flag){
                return false;
            }
        }
        return true;
    }
}

差分数组。用差分数组 diff
维护相邻两个整数的被覆盖区间数量变化量，其中 diff[i]
对应覆盖整数 i
的区间数量相对于覆盖 i−1
的区间数量变化量。这样，当遍历到闭区间 [l,r]
时，l
相对于 l−1
被覆盖区间数量多 1
，r+1
相对于 r
被覆盖区间数量少 1
。对应到差分数组上，我们需要将 diff[l]
加上 1
，并将 diff[r+1]
减去 1
。

在维护完差分数组 diff
后，我们遍历 diff
求前缀和得出覆盖每个整数的区间数量。下标 i
对应的被覆盖区间数量即为初始数量 0 加上[1,i]
闭区间的变化量之和。在计算被覆盖区间数量的同时，我们可以一并判断 [left,right]
闭区间内的所有整数是否都被覆盖。

class Solution {
    public boolean isCovered(int[][] ranges, int left, int right) {
        int[] diff = new int[52];   // 差分数组，注意分析这里为52的意义
        for (int[] range : ranges) {
            ++diff[range[0]];
            --diff[range[1] + 1];
        }
        // 前缀和
        int curr = 0;
        for (int i = 1; i <= 50; ++i) {
            curr += diff[i];
            if (i >= left && i <= right && curr <= 0) {
                return false;
            }
        }
        return true;
    }
}

以 示例1 为例模拟整个过程：

1736. 替换隐藏数字得到的最晚时间 （2021.7.24，中等）

给你一个字符串 time ，格式为 hh:mm
（小时：分钟），其中某几位数字被隐藏（用 ? 表示）。

有效的时间为 00:00
到 23:59
之间的所有时间，包括 00:00
和 23:59
。

替换 time 中隐藏的数字，返回你可以得到的最晚有效时间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/latest-time-by-replacing-hidden-digits
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例 1：

输入：time = "2?:?0"

输出："23:50"

解释：以数字 '2' 开头的最晚一小时是 23 ，以 '0' 结尾的最晚一分钟是 50 。

示例 2：

输入：time = "0?:3?"

输出："09:39"

示例 3：

输入：time = "1?:22"

输出："19:22"

提示：

• time
  的格式为 hh:mm
  
• 题目数据保证你可以由输入的字符串生成有效的时间

Answer

分情况讨论。由于给定的字符串的格式是固定的，因此可以分别对小时和分钟结合实际情况具体分析。

针对小时：

• 第一位：若第二位的值已经确定，且值落在区间 [4,9]
  中时，第一位的值最大只能为 1，否则最大可以为 2；
• 第二位：若第一位的值已经确定，且值为 2 时，第二位的值最大为 3，否则为 9；

针对分钟：

• 第三位：第三位的值的选取与其它位无关，最大为 5；
• 第四位：第四位的值的选取与其它位无关，最大为 9。

class Solution {
    public String maximumTime(String time) {
        char[] arr = time.toCharArray();
        if (arr[0] == '?') {
            arr[0] = ('4' <= arr[1] && arr[1] <= '9') ? '1' : '2';
        }
        if (arr[1] == '?') {
            arr[1] = (arr[0] == '2') ? '3' : '9';
        }
        if (arr[3] == '?') {
            arr[3] = '5';
        }
        if (arr[4] == '?') {
            arr[4] = '9';
        }
        return new String(arr);
    }
}

以 示例1 为例模拟整个过程：

1743. 从相邻元素对还原数组 （2021.7.25，中等）

存在一个由 n
个不同元素组成的整数数组 nums
，但你已经记不清具体内容。好在你还记得 nums
中的每一对相邻元素。

给你一个二维整数数组 adjacentPairs
，大小为 n - 1
，其中每个 adjacentPairs[i] = [ui, vi]
表示元素 ui
和 vi
在 nums
中相邻。

题目数据保证所有由元素 nums[i]
和 nums[i+1]
组成的相邻元素对都存在于 adjacentPairs
中，存在形式可能是 [nums[i], nums[i+1]]
，也可能是 [nums[i+1], nums[i]]
。这些相邻元素对可以 按任意顺序 出现。

返回 原始数组 nums
。如果存在多种解答，返回 其中任意一个 即可。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/restore-the-array-from-adjacent-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例 1：

输入：adjacentPairs = [[2,1],[3,4],[3,2]]

输出：[1,2,3,4]

解释：数组的所有相邻元素对都在 adjacentPairs 中。
特别要注意的是，adjacentPairs[i] 只表示两个元素相邻，并不保证其 左-右 顺序。

示例 2：

输入：adjacentPairs = [[4,-2],[1,4],[-3,1]]

输出：[-2,4,1,-3]

解释：数组中可能存在负数。
另一种解答是 [-3,1,4,-2] ，也会被视作正确答案。

示例 3：

输入：adjacentPairs = [[100000,-100000]]

输出：[100000,-100000]

提示：

• nums.length == n
  
• adjacentPairs.length == n - 1
  
• adjacentPairs[i].length == 2
  
• 2 <= n <= 10^5
  
• -10^5 <= nums[i], ui, vi <= 10^5
  
• 题目数据保证存在一些以 adjacentPairs
  作为元素对的数组 nums
  

Answer

哈希表。对于一维数组 nums
中的元素 nums[i]
，若其为数组的第一个或最后一个元素，则该元素有且仅有一个元素与其相邻；若其为数组的中间元素，则该元素有且仅有两个元素与其相邻。

我们可以对每个元素记录与它相邻的元素有哪些，然后依次检查每个元素的相邻元素数量，即可找到原数组的第一个元素和最后一个元素。由于我们可以返回任意一个满足条件的数组，故指定这两个元素中的一个为原数组的第一个元素，然后根据相邻元素信息确定数组的第二个、第三个元素……直到确定最后一个元素为止。

具体地，我们使用哈希表记录每一个的元素的相邻元素有哪些，然后我们遍历哈希表，找到有且仅有一个相邻元素的元素 e_1
作为原数组的第一个元素。那么与 e_1
唯一相邻的元素 e_2
即为原数组的第二个元素。此时排除掉与 e_2
相邻的 e_1
后，可以确认与 e_2
相邻的 e_3
即为原数组的第三个元素……以此类推，我们可以将原数组完整推断出来。

class Solution {
    public int[] restoreArray(int[][] adjacentPairs) {
        Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
        for (int[] adjacentPair : adjacentPairs) {
            // putIfAbsent():如果传入key对应的value已经存在，就返回存在的value，不进行替换。如果不存在，就添加key和value，返回null
            map.putIfAbsent(adjacentPair[0], new ArrayList<Integer>());
            map.putIfAbsent(adjacentPair[1], new ArrayList<Integer>());
            map.get(adjacentPair[0]).add(adjacentPair[1]);
            map.get(adjacentPair[1]).add(adjacentPair[0]);
        }

        int n = adjacentPairs.length + 1;
        int[] ret = new int[n];
        // 确定边界元素
        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            int e = entry.getKey();
            List<Integer> adj = entry.getValue();
            if (adj.size() == 1) {
                ret[0] = e;
                break;
            }
        }

        // 根据HashMap还原数组
        ret[1] = map.get(ret[0]).get(0);
        for (int i = 2; i < n; i++) {
            List<Integer> adj = map.get(ret[i - 1]);
            ret[i] = ret[i - 2] == adj.get(0) ? adj.get(1) : adj.get(0);
        }
        return ret;
    }
}

以 示例1 为例模拟整个过程：