每日力扣刷题day04

本文主要是介绍每日力扣刷题day04，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 2024.5.25（5题）
- - 1920.基于排练构建数组
  - - 题解一
    - 题解二
    - 题解三
  - 1512.好数对的数目
  - - 题解一
    - 题解二
  - 961.在长度2N的数组中找出重复N次的元素
  - - 题解一
    - 题解二
    - 题解三
    - 题解四
  - 1342.将数字变成0的操作次数
  - - 题解一
    - 题解二
  - 771.宝石与石头
  - - 题解一
    - 题解二
    - 题解三

2024.5.25（5题）

1920.基于排练构建数组

用流处理和数字编码的方式来达到题目的进阶要求

题目链接

给你一个 从 0 开始的排列 nums（下标也从 0 开始）。请你构建一个 同样长度 的数组 ans ，其中，对于每个 i（0 <= i < nums.length），都满足 ans[i] = nums[nums[i]] 。返回构建好的数组 ans 。

从 0 开始的排列 nums 是一个由 0 到 nums.length - 1（0 和 nums.length - 1 也包含在内）的不同整数组成的数组。

示例 1：

输入：nums = [0,2,1,5,3,4]
输出：[0,1,2,4,5,3]
解释：数组 ans 构建如下：
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]= [nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]]= [0,1,2,4,5,3]

示例 2：

输入：nums = [5,0,1,2,3,4]
输出：[4,5,0,1,2,3]
解释：数组 ans 构建如下：
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]= [nums[5], nums[0], nums[1], nums[2], nums[3], nums[4]]= [4,5,0,1,2,3]

提示：

1 <= nums.length <= 1000
0 <= nums[i] < nums.length
nums 中的元素 互不相同

进阶： 你能在不使用额外空间的情况下解决此问题吗（即 O(1) 内存）？

题解一

class Solution {public int[] buildArray(int[] nums) {int[] ans = new int[nums.length];for (int i = 0; i < nums.length; i++) {ans[i] = nums[nums[i]];}return ans;}
}

创建一个新的数组，根据题意，将 nums[nums[i]] 的值赋给 ans[i]。

题解二

class Solution {public int[] buildArray(int[] nums) {return Arrays.stream(nums).map(i -> nums[i]).toArray();}
}

Arrays.stream(int[] array)：将 nums 数组转换为一个 IntStream。
map(IntUnaryOperator mapper)：对流中的每个元素应用给定的映射函数（这里是 i -> nums[i]）。
toArray()：将流的结果收集到一个新的数组中。

题解三

class Solution {public int[] buildArray(int[] nums) {int n = nums.length;// 将新值编码到 nums 中for (int i = 0; i < n; i++) {nums[i] = nums[i] + n * (nums[nums[i]] % n);}// 解码新值并更新数组for (int i = 0; i < n; i++) {nums[i] = nums[i] / n;}return nums;}
}

编码：
- nums[i] + n * (nums[nums[i]] % n)：在原数组中，nums[i] 位置上存储了原始值和新值的组合。
- nums[nums[i]] % n：确保获取的是原始值，因为 nums[nums[i]] 可能已经被编码过。
解码：
- nums[i] / n：提取新值。

我们要在 nums[i] 中同时存储原始值 nums[i] 和新值 nums[nums[i]]。为了不丢失原始值，我们可以利用整数的高位和低位来存储这两个值。

具体来说：

低位存储原始值 nums[i]。
高位存储新值 nums[nums[i]]。

具体思路：

我们可以使用类似「n 进制」的思路来表示每个元素的「当前值」和「最终值」。具体来说，对于每个元素，我们用它除以 n 的商表示它的「最终值」，而用余数表示它的「当前值」。

编码过程：
遍历 nums 数组，计算每个元素的「最终值」。
将「最终值」乘以 n 并加在当前元素上，以同时存储当前值和最终值。

解码过程：
再次遍历数组，将每个元素的值除以 n，保留其商数。这一步将提取出存储在高位的「最终值」。

细节处理

在计算 nums[i] 的「最终值」并修改该元素时，考虑到 nums 数组中下标为 nums[i] 的元素可能已被修改，因此需要对 nums[nums[i]] 取模 n 来得到其原始值，以确保计算的正确性。

1512.好数对的数目

暴力法：通过两层嵌套循环遍历数组中的所有元素对，时间复杂度为 O(n^2)。

哈希表法：使用哈希表记录每个数字出现的次数，时间复杂度为 O(n)。

题目链接

给你一个整数数组 nums 。

如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。

返回好数对的数目。

示例 1：

输入：nums = [1,2,3,1,1,3]
输出：4
解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始

示例 2：

输入：nums = [1,1,1,1]
输出：6
解释：数组中的每组数字都是好数对

示例 3：

输入：nums = [1,2,3]
输出：0

提示：

1 <= nums.length <= 100
1 <= nums[i] <= 100

题解一

class Solution {public int numIdenticalPairs(int[] nums) {int ans = 0;for (int i = 0; i < nums.length - 1; i++) {for (int j = i + 1; j < nums.length; j++) {if (nums[i] == nums[j]) {ans++;}}}return ans;}
}

用计数器计数
用两层嵌套的循环遍历数组 nums 中的所有元素对 (i, j)。
满足条件，计数器加 1

题解二

class Solution {public int numIdenticalPairs(int[] nums) {Map<Integer, Integer> map = new HashMap<>();int count = 0;for (int num : nums) {if (map.containsKey(num)) {count += map.get(num);}map.put(num, map.getOrDefault(num, 0) + 1);}return count;}
}

初始化一个哈希表 map。
遍历数组 nums，对于每个元素 num：
- 如果 num 已经在 map 中，说明它已经形成了 map.get(num) 个好数对，计数器 count 增加 map.get(num)。
- 更新 map 中 num 的出现次数。

961.在长度2N的数组中找出重复N次的元素

给出四种思路和题解

题目链接

给你一个整数数组 nums ，该数组具有以下属性：

nums.length == 2 * n.
nums 包含 n + 1 个 不同的 元素
nums 中恰有一个元素重复 n 次

找出并返回重复了 n 次的那个元素。

示例 1：

输入：nums = [1,2,3,3]
输出：3

示例 2：

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

示例 3：

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

提示：

2 <= n <= 5000
nums.length == 2 * n
0 <= nums[i] <= 104
nums 由 n + 1 个 不同的 元素组成，且其中一个元素恰好重复 n 次

题解一

class Solution {public int repeatedNTimes(int[] nums) {Map<Integer, Integer> map = new HashMap<>();for (int num : nums) {map.put(num, map.getOrDefault(num, 0) + 1);}for (Map.Entry<Integer, Integer> entry : map.entrySet()) {if (entry.getValue() == nums.length / 2) {return entry.getKey();}}return -1;}
}

初始化一个哈希表 map，用于记录每个元素的出现次数。
遍历数组 nums，对于每个元素 num，更新 map 中该元素的出现次数。
遍历哈希表 map，找到出现次数为 n 的那个元素，并返回。

题解二

class Solution {public int repeatedNTimes(int[] nums) {Arrays.sort(nums);for (int i = 0; i < nums.length - 1; i++) {if (nums[i] == nums[i + 1]) {return nums[i];}}return -1;}
}

对数组 nums 进行排序。
遍历排序后的数组，检查相邻的两个元素是否相同，如果相同则返回该元素

题解三

class Solution {public int repeatedNTimes(int[] nums) {int n = nums.length;for (int i = 0; i < n; i++) {int t = nums[i];if (i - 1 >= 0 && nums[i - 1] == t) return t;if (i - 2 >= 0 && nums[i - 2] == t) return t;if (i - 3 >= 0 && nums[i - 3] == t) return t;}return -1;}
}

要用n个数隔开n个相同的数，相同的数之间最坏的情况有两个不一样的数，所以只要依次检查元素与其前 1、2、3 个元素是否相等，如果相等则返回该元素。

题解四

class Solution {public int repeatedNTimes(int[] nums) {Random random = new Random();int n = nums.length / 2;while (true) {int i = random.nextInt(nums.length);int j = random.nextInt(nums.length);if (i != j && nums[i] == nums[j]) {return nums[i];}}}
}

创建一个随机数生成器 Random。
在循环中随机选择两个不同的下标 i 和 j，直到找到一对 nums[i] == nums[j] 为止。
返回 nums[i] 作为答案。
选择两个相同元素的概率为四分之一，理由同题解三

1342.将数字变成0的操作次数

位运算优化代码

题目链接

给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。

示例 1：

输入：num = 14
输出：6
解释：
步骤 1) 14 是偶数，除以 2 得到 7 。
步骤 2） 7 是奇数，减 1 得到 6 。
步骤 3） 6 是偶数，除以 2 得到 3 。
步骤 4） 3 是奇数，减 1 得到 2 。
步骤 5） 2 是偶数，除以 2 得到 1 。
步骤 6） 1 是奇数，减 1 得到 0 。

示例 2：

输入：num = 8
输出：4
解释：
步骤 1） 8 是偶数，除以 2 得到 4 。
步骤 2） 4 是偶数，除以 2 得到 2 。
步骤 3） 2 是偶数，除以 2 得到 1 。
步骤 4） 1 是奇数，减 1 得到 0 。

示例 3：

输入：num = 123
输出：12

提示：

0 <= num <= 10^6

题解一

class Solution {public int numberOfSteps(int num) {int steps = 0;while (num > 0) {if (num % 2 == 0) {num /= 2;} else {num -= 1;}steps++;}return steps;}
}

根据题目写判断分支即可

题解二

class Solution {public int numberOfSteps(int num) {int steps = 0;while (num > 0) {if ((num & 1) == 0) {num >>= 1;} else {num -= 1;}steps++;}return steps;}
}

对于偶数，右移一位相当于除以2；
对于奇数，减一再右移一位相当于先减一再除以2。
使用位运算中的与运算 & 来判断 num 的最低位是否为1，如果是奇数，则与运算的结果为1，如果是偶数，则结果为0。

771.宝石与石头

暴力、哈希、ASCII映射数组，还有一种思想跟题解三一样的，用二进制和位运算，也是ASCII映射

题目链接

给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。

字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。

示例 1：

输入：jewels = "aA", stones = "aAAbbbb"
输出：3

示例 2：

输入：jewels = "z", stones = "ZZ"
输出：0

提示：

1 <= jewels.length, stones.length <= 50
jewels 和 stones 仅由英文字母组成
jewels 中的所有字符都是 唯一的

题解一

class Solution {public int numJewelsInStones(String jewels, String stones) {int count = 0;for (int i = 0; i < jewels.length(); i++) {char jewel = jewels.charAt(i);for (int j = 0; j < stones.length(); j++) {if (stones.charAt(j) == jewel) {count++;}}}return count;}
}

对于 jewels 中的每一个字符，遍历 stones，统计 stones 中与 jewels 中字符相同的个数。

题解二

class Solution {public int numJewelsInStones(String jewels, String stones) {Set<Character> jewelSet = new HashSet<>();for (char jewel : jewels.toCharArray()) {jewelSet.add(jewel);}int count = 0;for (char stone : stones.toCharArray()) {if (jewelSet.contains(stone)) {count++;}}return count;}
}

将 jewels 中的字符存入一个哈希集合（HashSet），然后遍历 stones，对于 stones 中的每个字符，判断是否在哈希集合中，如果在则计数加一。

题解三

class Solution {public int numJewelsInStones(String jewels, String stones) {int[] jewelArray = new int[128];for (char jewel : jewels.toCharArray()) {jewelArray[jewel] = 1;}int count = 0;for (char stone : stones.toCharArray()) {if (jewelArray[stone] == 1) {count++;}}return count;}
}