标签： easy

目标

给你一个数组 nums ，数组中的数字 要么 出现一次，要么 出现两次。

请你返回数组中所有出现两次数字的按位 XOR 值，如果没有数字出现过两次，返回 0 。

示例 1：

输入：nums = [1,2,1,3]
输出：1
解释：
nums 中唯一出现过两次的数字是 1 。

示例 2：

输入：nums = [1,2,3]
输出：0
解释：
nums 中没有数字出现两次。

示例 3：

输入：nums = [1,2,2,1]
输出：3
解释：
数字 1 和 2 出现过两次。1 XOR 2 == 3 。

说明：

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 50
• nums 中每个数字要么出现过一次，要么出现过两次。

思路

有一个数组 nums，其中的元素要么出现一次，要么出现两次。求出现两次的元素的异或值，如果没有则返回 0。

由于 nums[i] <= 50，可以使用数组记录元素是否出现过，如果它第二次出现则计算异或值。

网友题解则使用了 long 型变量作为 bitmap 标识是否已经出现过。空间复杂度降为 O(1)。

代码

/**
 * @date 2024-10-12 8:46
 */
public class DuplicateNumbersXOR3158 {

    public int duplicateNumbersXOR(int[] nums) {
        // nums[i] <= 50
        boolean[] seen = new boolean[51];
        int res = 0;
        for (int num : nums) {
            if (seen[num]) {
                res ^= num;
            } else {
                seen[num] = true;
            }
        }
        return res;
    }
}

性能

目标

给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。同时给你一个正整数 k。

如果 nums1[i] 可以被 nums2[j] * k 整除，则称数对 (i, j) 为 优质数对（0 <= i <= n - 1, 0 <= j <= m - 1）。

返回 优质数对 的总数。

示例 1：

输入：nums1 = [1,3,4], nums2 = [1,3,4], k = 1
输出：5
解释：
5个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。

示例 2：

输入：nums1 = [1,2,4,12], nums2 = [2,4], k = 3
输出：2
解释：
2个优质数对分别是 (3, 0) 和 (3, 1)。

说明：

• 1 <= n, m <= 50
• 1 <= nums1[i], nums2[j] <= 50
• 1 <= k <= 50

思路

有两个数组 nums1 nums2，计算满足 nums1[i] % (nums2[j] * k) == 0 的数对 (i, j) 的个数。

数据量不大直接枚举即可。可以优化的点是提前判断 nums[i] 能否整除 k，如果不能，则必然也无法整除 nums2[j] * k，省去了内部循环乘以 k 的计算。

官网题解的非暴力做法是使用两个哈希表 map1 map2 分别统计 nums1 nums2 中元素出现的次数，同时找出 nums1 中的最大值 max1，然后枚举 map2 的 keyset，内层循环初值与步长为 nums2[j] * k，判断倍数是否在 map1 中，直到 倍数 <= max1。这样做的好处是寻找数对的时间复杂度由原来的 O(mn) 变成了 O(n + m + max1/k * log(m))。

这里的 log(max2) 是一个近似的估计，针对每一个外层循环的值 a，内层循环的次数为 max1 / (a * k)，假设 nums2 的元素值为 1 2 …… max2，那么总的循环次数为 (max1/k)Σ(1/a) 这是调和级数的形式，即 1 + 1/2 + 1/3 + …… + 1/max2 + ……，调和级数的部分和 Hn 近似为 ln(max2)，这里 max2 其实是 nums2 的个数 m。当 nums2 中的元素都是 1 时，map2.keySet 中的元素个数也为 1，进化为 O(n + m + max1/k)，当 nums2 中的元素都是 max2 时，进化为 O(n + m + max1/(max2 * k))。

代码

/**
 * @date 2024-10-10 8:56
 */
public class NumberOfPairs3162 {

    public int numberOfPairs_v1(int[] nums1, int[] nums2, int k) {
        int res = 0;
        for (int i = 0; i < nums1.length; i++) {
            if (nums1[i] % k != 0) {
                continue;
            }
            int tmp = nums1[i] / k;
            for (int j = 0; j < nums2.length; j++) {
                if (tmp % nums2[j] == 0) {
                    res++;
                }
            }
        }
        return res;
    }

    public int numberOfPairs(int[] nums1, int[] nums2, int k) {
        int res = 0;
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                if (nums1[i] % (nums2[j] * k) == 0){
                    res++;
                }
            }
        }
        return res;
    }

}

性能

目标

给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。

题目数据保证线路图会形成一条不存在循环的线路，因此恰有一个旅行终点站。

示例 1：

输入：paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
输出："Sao Paulo" 
解释：从 "London" 出发，最后抵达终点站 "Sao Paulo" 。本次旅行的路线是 "London" -> "New York" -> "Lima" -> "Sao Paulo" 。

示例 2：

输入：paths = [["B","C"],["D","B"],["C","A"]]
输出："A"
解释：所有可能的线路是：
"D" -> "B" -> "C" -> "A". 
"B" -> "C" -> "A". 
"C" -> "A". 
"A". 
显然，旅行终点站是 "A" 。

示例 3：

输入：paths = [["A","Z"]]
输出："Z"

说明：

• 1 <= paths.length <= 100
• paths[i].length == 2
• 1 <= cityAi.length, cityBi.length <= 10
• cityAi != cityBi
• 所有字符串均由大小写英文字母和空格字符组成。

思路

找到旅行的终点，实际上是求在 end 集合而不在 start 集合中的元素，即 end - (start ∩ end)，测试用例保证只有一个终点。

代码

/**
 * @date 2024-10-08 8:43
 */
public class DestCity1436 {

    public String destCity(List<List<String>> paths) {
        Set<String> start = new HashSet<>();
        for (List<String> path : paths) {
            start.add(path.get(0));
        }
        for (List<String> path : paths) {
            String dest = path.get(1);
            if (!start.contains(dest)) {
                return dest;
            }
        }
        return null;
    }
}

性能

目标

有 n 个人前来排队买票，其中第 0 人站在队伍 最前方 ，第 (n - 1) 人站在队伍 最后方 。

给你一个下标从 0 开始的整数数组 tickets ，数组长度为 n ，其中第 i 人想要购买的票数为 tickets[i] 。

每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ，如果需要购买更多票，他必须走到 队尾 重新排队（瞬间 发生，不计时间）。如果一个人没有剩下需要买的票，那他将会 离开 队伍。

返回位于位置 k（下标从 0 开始）的人完成买票需要的时间（以秒为单位）。

示例 1：

输入：tickets = [2,3,2], k = 2
输出：6
解释：

队伍一开始为 [2,3,2]，第 k 个人以下划线标识。
在最前面的人买完票后，队伍在第 1 秒变成 [3,2,1]。
继续这个过程，队伍在第 2 秒变为[2,1,2]。
继续这个过程，队伍在第 3 秒变为[1,2,1]。
继续这个过程，队伍在第 4 秒变为[2,1]。
继续这个过程，队伍在第 5 秒变为[1,1]。
继续这个过程，队伍在第 6 秒变为[1]。第 k 个人完成买票，所以返回 6。

示例 2：

输入：tickets = [5,1,1,1], k = 0
输出：8
解释：
队伍一开始为 [5,1,1,1]，第 k 个人以下划线标识。
在最前面的人买完票后，队伍在第 1 秒变成 [1,1,1,4]。
继续这个过程 3 秒，队伍在第 4 秒变为[4]。
继续这个过程 4 秒，队伍在第 8 秒变为[]。第 k 个人完成买票，所以返回 8。

说明：

• n == tickets.length
• 1 <= n <= 100
• 1 <= tickets[i] <= 100
• 0 <= k < n

思路

有 n 个人在排队买票，每人每次限买一张，每买一张票耗时 1 秒，如果要买多张需要重新排队。现在已知 tickets 数组，表示第 i 个人想买票的数量，问第 k 个人完成买票需要多长时间（仅记录买票时间）。

由于数据量不大，直接的解法是用队列模拟排队。假设所有人都要买 m 张票，k 为 n - 1，那么时间复杂度为 O(mn)。

考虑整体计算，当第 k 个人排到队尾时，将其前面所有人剩余要买的 tickets[i] 减去 第 k 个人剩余需要买的票数 r = tickets[k] - 1，那么剩余的等待时间为 n * r + (tickets[i] 为负的和)。时间复杂度为 O(n)。

网友有一个解法是客户不动，让售票员从头到尾卖票，如果顾客已经完成买票则跳过，这也算是模拟的另一种思路。

代码

/**
 * @date 2024-09-29 8:45
 */
public class TimeRequiredToBuy2073 {

    /**
     * 整体计算
     */
    public int timeRequiredToBuy_v1(int[] tickets, int k) {
        int n = tickets.length;
        int res = 0;
        for (int i = 0; i <= k; i++) {
            tickets[i]--;
            res++;
        }
        int r = tickets[k];
        res += r * n;
        for (int ticket : tickets) {
            int i = ticket - r;
            if (i < 0) {
                res += i;
            }
        }
        return res;
    }

    /**
     * 模拟
     */
    public int timeRequiredToBuy(int[] tickets, int k) {
        ArrayDeque<Integer> q = new ArrayDeque<>();
        int n = tickets.length;
        for (int i = 0; i < n; i++) {
            q.offer(i);
        }
        int res = 0;
        while (!q.isEmpty()) {
            int i = q.poll();
            int remainder = --tickets[i];
            res++;
            if (remainder > 0) {
                q.offer(i);
            } else if (i == k) {
                break;
            }
        }
        return res;
    }
}

性能

目标

给你一个正整数数组 nums 。

• 元素和 是 nums 中的所有元素相加求和。
• 数字和 是 nums 中每一个元素的每一数位（重复数位需多次求和）相加求和。

返回 元素和 与 数字和 的绝对差。

注意：两个整数 x 和 y 的绝对差定义为 |x - y| 。

示例 1：

输入：nums = [1,15,6,3]
输出：9
解释：
nums 的元素和是 1 + 15 + 6 + 3 = 25 。
nums 的数字和是 1 + 1 + 5 + 6 + 3 = 16 。
元素和与数字和的绝对差是 |25 - 16| = 9 。

示例 2：

输入：nums = [1,2,3,4]
输出：0
解释：
nums 的元素和是 1 + 2 + 3 + 4 = 10 。
nums 的数字和是 1 + 2 + 3 + 4 = 10 。
元素和与数字和的绝对差是 |10 - 10| = 0 。

说明：

• 1 <= nums.length <= 2000
• 1 <= nums[i] <= 2000

思路

直接根据题意计算即可。由于元素和一定大于数字和，不用分开计算。

代码

/**
 * @date 2024-09-26 8:45
 */
public class DifferenceOfSum2535 {

    public int differenceOfSum(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res += num;
            while (num > 0) {
                res -= num % 10;
                num /= 10;
            }
        }
        return res;
    }

}

性能

目标

小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。

如果小镇法官真的存在，那么：

1. 小镇法官不会信任任何人。
2. 每个人（除了小镇法官）都信任这位小镇法官。
3. 只有一个人同时满足属性 1 和属性 2 。

给你一个数组 trust ，其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。

如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 -1 。

示例 1：

输入：n = 2, trust = [[1,2]]
输出：2

示例 2：

输入：n = 3, trust = [[1,3],[2,3]]
输出：3

示例 3：

输入：n = 3, trust = [[1,3],[2,3],[3,1]]
输出：-1

说明：

• 1 <= n <= 1000
• 0 <= trust.length <= 10^4
• trust[i].length == 2
• trust 中的所有trust[i] = [ai, bi] 互不相同
• ai != bi
• 1 <= ai, bi <= n

思路

小镇至多有一个法官，他不信任任何人却被所有人信任，二维数组 trust 的元素 [a, b] 表示 a 信任 b，如果小镇法官存在返回其编号，否则返回 -1。

使用集合 trusted 表示被信任的人，trusts 表示愿意相信他人的人。我们需要计算 trusted - (trusted ∩ trusts)，还必须判断这个人是否被所有人所信任。另外，有一种特殊情况，小镇只有法官一个人，trust 数组为空，我们应该返回编号 1，而不是找不到。

代码

/**
 * @date 2024-09-22 15:31
 */
public class FindJudge997 {

    public int findJudge(int n, int[][] trust) {
        if (trust.length == 0) {
            return n == 1 ? 1 : -1;
        }
        int[] trustedCnt = new int[n + 1];
        int res = -1;
        for (int[] relation : trust) {
            if (++trustedCnt[relation[1]] == n - 1) {
                res = relation[1];
                break;
            }
        }
        for (int[] relation : trust) {
            if (res == relation[0]) {
                return -1;
            }
        }
        return res;
    }

}

性能

目标

环形公交路线上有 n 个站，按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离，distance[i] 表示编号为 i 的车站和编号为 (i + 1) % n 的车站之间的距离。

环线上的公交车都可以按顺时针和逆时针的方向行驶。

返回乘客从出发点 start 到目的地 destination 之间的最短距离。

示例 1：

输入：distance = [1,2,3,4], start = 0, destination = 1
输出：1
解释：公交站 0 和 1 之间的距离是 1 或 9，最小值是 1。

示例 2：

输入：distance = [1,2,3,4], start = 0, destination = 2
输出：3
解释：公交站 0 和 2 之间的距离是 3 或 7，最小值是 3。

示例 3：

输入：distance = [1,2,3,4], start = 0, destination = 3
输出：4
解释：公交站 0 和 3 之间的距离是 6 或 4，最小值是 4。

说明：

• 1 <= n <= 10^4
• distance.length == n
• 0 <= start, destination < n
• 0 <= distance[i] <= 10^4

思路

有一个数组 distance，元素 distance[i] 表示车站 i 到 车站 i + 1 的距离。环线上的车可以顺时针或逆时针行驶，求 start 到 destination 的最短距离。

假设，start <= destination。实际上是比较子数组 [start, destination - 1] 的元素和 与 子数组 [0, start - 1] [destination, n - 1] 的元素和，取其中的较小值。

由于是环形的，因此有可能 start > destination。注意处理初始条件，否则子数组 [start, destination - 1] 不合法，而 [0, start - 1] [destination, n - 1] 则覆盖了所有站点。

代码

/**
 * @date 2024-09-16 20:08
 */
public class DistanceBetweenBusStops1184 {

    public int distanceBetweenBusStops(int[] distance, int start, int destination) {
        int n = distance.length;
        int s = Math.min(start, destination);
        int e = Math.max(start, destination);
        int d1 = 0, d2 = 0;
        for (int i = 0; i < n; i++) {
            if (i < s || i >= e) {
                d1 += distance[i];
            } else {
                d2 += distance[i];
            }
        }
        return Math.min(d1, d2);
    }
}

性能