每日力扣刷题day03（从零开始版）

2024.5.24（5题）

2828.判别首字母缩略词

常规遍历题，对小白而言可以学两个常见方法

给出两种题解

题目链接

给你一个字符串数组 words 和一个字符串 s ，请你判断 s 是不是 words 的 首字母缩略词 。

如果可以按顺序串联 words 中每个字符串的第一个字符形成字符串 s ，则认为 s 是 words 的首字母缩略词。例如，"ab" 可以由 ["apple"， "banana"] 形成，但是无法从 ["bear"， "aardvark"] 形成。

如果 s 是 words 的首字母缩略词，返回 true ；否则，返回 false 。

示例 1：

输入：words = ["alice"，"bob"，"charlie"]， s = "abc"
输出：true
解释：words 中 "alice"、"bob" 和 "charlie" 的第一个字符分别是 'a'、'b' 和 'c'。因此，s = "abc" 是首字母缩略词。 

示例 2：

输入：words = ["an"，"apple"]， s = "a"
输出：false
解释：words 中 "an" 和 "apple" 的第一个字符分别是 'a' 和 'a'。
串联这些字符形成的首字母缩略词是 "aa" 。
因此，s = "a" 不是首字母缩略词。

示例 3：

输入：words = ["never"，"gonna"，"give"，"up"，"on"，"you"]， s = "ngguoy"
输出：true
解释：串联数组 words 中每个字符串的第一个字符，得到字符串 "ngguoy" 。
因此，s = "ngguoy" 是首字母缩略词。 

提示：

• 1 <= words.length <= 100
• 1 <= words[i].length <= 10
• 1 <= s.length <= 100
• words[i] 和 s 由小写英文字母组成

题解一

class Solution {public boolean isAcronym(List<String> words, String s) {if (words.size() != s.length()) {return false;}for (int i = 0; i < words.size(); i++) {if (words.get(i).charAt(0)!=s.charAt(i)) {return false;}}return true;}
}

• 这个题的难点在于，对数据结构不熟悉的人看不懂List<String>，这就相当于一个数组，里面的元素是一个字符串
• 当words的长度不等于s的长度的时候，直接返回false
• 遍历list，words.get(i)获取每一个字符串，charAt(0)得到字符串第一个字符

题解二

class Solution {public boolean isAcronym(List<String> words, String s) {StringBuilder acronym = new StringBuilder();for (String word : words) {acronym.append(word.charAt(0));}return acronym.toString().equals(s);}
}

• 先获取首字母缩略词，再与s比较一下
• append(char c)：将字符添加到 StringBuilder 的末尾。
• toString()：将 StringBuilder 中的内容转换为 String。
• equals(Object anObject)：比较两个字符串的内容是否相等。

1365.有多少小于当前数字的数字

三种题解，暴力加两种优化

排序加二分查找、前缀和，比较难想到的前缀和实际上第一天的1480题就是求前缀和

题目链接

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。

以数组形式返回答案。

示例 1：

输入：nums = [8,1,2,2,3]
输出：[4,0,1,1,3]
解释： 
对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。 
对于 nums[1]=1 不存在比它小的数字。
对于 nums[2]=2 存在一个比它小的数字：（1）。 
对于 nums[3]=2 存在一个比它小的数字：（1）。 
对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。

示例 2：

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

示例 3：

输入：nums = [7,7,7,7]
输出：[0,0,0,0]

提示：

• 2 <= nums.length <= 500
• 0 <= nums[i] <= 100

题解一

class Solution {public int[] smallerNumbersThanCurrent(int[] nums) {int[] ans = new int[nums.length];for (int i = 0; i < nums.length; i++) {for (int j = 0; j < nums.length; j++) {if (j != i && nums[j]<nums[i]) {ans[i]++;}}}return ans;}
}

• 暴力法的思路非常直接，对于每个元素，遍历数组中其他元素，统计比它小的元素数量。
• 题目给出了 j 要满足的条件，直接放 if 里面就行了

题解二

class Solution {public int[] smallerNumbersThanCurrent(int[] nums) {int n = nums.length;int[] sortedNums = nums.clone();Arrays.sort(sortedNums);int[] result = new int[n];for (int i = 0; i < n; i++) {result[i] = binarySearch(sortedNums, nums[i]);}return result;}private int binarySearch(int[] sortedNums, int target) {int left = 0, right = sortedNums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (sortedNums[mid] >= target) {right = mid - 1;} else {left = mid + 1;}}return left;}
}

• nums.clone() 克隆了 nums 的一个副本用来排序，我们在排序的时候不能改变原来的数组

• 用新数组排序之后，用二分查找来找到比 nums[i] 小的元素数量。

  二分查找是一种非常高效的查找算法，它适用于已排序的数据集合。其基本思想是将待查找的目标值与数据集合的中间值进行比较，如果相等则查找成功;如果目标值小于中间值，则在数据集合的左半部分继续查找;如果目标值大于中间值，则在右半部分继续查找。重复这个过程直到找到目标值或者查找范围为空。

  二分查找的时间复杂度为O(logn)，其中n是数据集合的大小。这比线性查找的时间复杂度O(n)要高效得多，尤其是在处理大型数据集时。

  • 初始化二分查找的左右边界 left 和 right。
  • 在排序数组中查找目标值 target 的位置。
  • 如果 sortedNums[mid] 大于或等于 target，移动右边界，否则移动左边界。
  • 最后返回 left，表示 target 在 sortedNums 中的位置，等同于比 target 小的元素数量

题解三

class Solution {public int[] smallerNumbersThanCurrent(int[] nums) {int n = nums.length;int[] result = new int[n];int[] count = new int[101]; for (int num : nums) {count[num]++;}for (int i = 1; i <= 100; i++) {count[i] += count[i - 1];}for (int i = 0; i < n; i++) {result[i] = nums[i] == 0 ? 0 : count[nums[i] - 1];}return result;}
}

• 创建一个长度为 101 的数组 count，用于记录每个数字的出现次数。

• 第一个循环遍历数组 nums，统计每个数字的出现次数。

• 第二个循环从索引 1 开始遍历 count 数组，将当前值与前一个值相加，构建前缀和数组。count[i] 表示数组中小于等于 i 的数字的总数。

• 第三个循环遍历数组 nums，对于每个数字 nums[i]，使用前缀和数组 count 来确定比 nums[i] 小的数字的数量。如果 nums[i] 为 0，则比它小的数字数量为 0；否则，比 nums[i] 小的数字数量为 count[nums[i] - 1]。

2469.温度转换

这个题应该是力扣最简单的题之一了

题目链接

给你一个四舍五入到两位小数的非负浮点数 celsius 来表示温度，以 摄氏度（Celsius）为单位。

你需要将摄氏度转换为 开氏度（Kelvin）和 华氏度（Fahrenheit），并以数组 ans = [kelvin, fahrenheit] 的形式返回结果。

返回数组 ans 。与实际答案误差不超过 10-5 的会视为正确答案**。**

注意：

• 开氏度 = 摄氏度 + 273.15
• 华氏度 = 摄氏度 * 1.80 + 32.00

示例 1 ：

输入：celsius = 36.50
输出：[309.65000,97.70000]
解释：36.50 摄氏度：转换为开氏度是 309.65 ，转换为华氏度是 97.70 。

示例 2 ：

输入：celsius = 122.11
输出：[395.26000,251.79800]
解释：122.11 摄氏度：转换为开氏度是 395.26 ，转换为华氏度是 251.798 。

提示：

• 0 <= celsius <= 1000

题解一

class Solution {public double[] convertTemperature(double celsius) {double kelvin = celsius+273.15;double fahrenheit = celsius * 1.80 + 32.00;double[] ans = new double[2];ans[0] = kelvin;ans[1] = fahrenheit;return ans;}
}

• 凑行数，实际上一行就能解决

题解二

class Solution {public double[] convertTemperature(double celsius) {return new double[]{celsius + 273.15, celsius * 1.80 + 32.00};}
}

• 对java来说，完全可以忽略精度问题，因为double已经有很高精度了

1502.判断能否形成等差数列

也是一道很简单的题，两种方法，排序和不用排序

题目链接

给你一个数字数组 arr 。

如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列 。

如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。

示例 1：

输入：arr = [3,5,1]
输出：true
解释：对数组重新排序得到 [1,3,5] 或者 [5,3,1] ，任意相邻两项的差分别为 2 或 -2 ，可以形成等差数列。

示例 2：

输入：arr = [1,2,4]
输出：false
解释：无法通过重新排序得到等差数列。

提示：

• 2 <= arr.length <= 1000
• -10^6 <= arr[i] <= 10^6

题解一

class Solution {public boolean canMakeArithmeticProgression(int[] arr) {Arrays.sort(arr);int diff = arr[1] - arr[0];for (int i = 2; i < arr.length; i++) {if (arr[i] - arr[i - 1] != diff) {return false;}}return true;}
}

• 先排序，不需要套等差数列的公式，也不需要求公差，只要后面两数之差不等于第一个两数之差就不是等差数列
• 遍历一遍，解决问题

题解二

class Solution {public boolean canMakeArithmeticProgression(int[] arr) {int min = Integer.MAX_VALUE;int max = Integer.MIN_VALUE;Set<Integer> set = new HashSet<>();for (int num : arr) {min = Math.min(min, num);max = Math.max(max, num);set.add(num);}int n = arr.length;if ((max - min) % (n - 1) != 0) {return false;}int diff = (max - min) / (n - 1);for (int i = 0; i < n; i++) {if (!set.contains(min + i * diff)) {return false;}}return true;}
}

• 不用排序的方法
• 遍历数组找到最小值和最大值，并计算理论上的等差数列的差值。
• 然后检查从最小值开始，每隔一个差值是否能在集合中找到相应的元素。如果都能找到，则可以构成等差数列。

2351.第一个出现两次的字母

哈希和数组，将字母表映射到数组上

题目链接

给你一个由小写英文字母组成的字符串 s ，请你找出并返回第一个出现 两次 的字母。

注意：

• 如果 a 的 第二次 出现比 b 的 第二次 出现在字符串中的位置更靠前，则认为字母 a 在字母 b 之前出现两次。
• s 包含至少一个出现两次的字母。

示例 1：

输入：s = "abccbaacz"
输出："c"
解释：
字母 'a' 在下标 0 、5 和 6 处出现。
字母 'b' 在下标 1 和 4 处出现。
字母 'c' 在下标 2 、3 和 7 处出现。
字母 'z' 在下标 8 处出现。
字母 'c' 是第一个出现两次的字母，因为在所有字母中，'c' 第二次出现的下标是最小的。

示例 2：

输入：s = "abcdd"
输出："d"
解释：
只有字母 'd' 出现两次，所以返回 'd' 。

提示：

• 2 <= s.length <= 100
• s 由小写英文字母组成
• s 包含至少一个重复字母

题解一

class Solution {public char repeatedCharacter(String s) {Set<Character> seen = new HashSet<>();for (char ch : s.toCharArray()) {if (seen.contains(ch)) {return ch;} else {seen.add(ch);}}return ' ';}
}

• 使用 HashSet 来存储已经遇到的字符。

• 将字符串转换为字符数组，并逐个字符检查。

  toCharArray()是Java中String类的一个实例方法,它可以将一个字符串转换为一个字符数组。

• 如果当前字符已经存在于集合中，则返回该字符，表示它是第一个出现两次的字符。如果当前字符不在集合中，将其加入集合。

题解二

class Solution {public char repeatedCharacter(String s) {// 用于记录每个字母的出现次数int[] count = new int[26];for (char ch : s.toCharArray()) {int index = ch - 'a';count[index]++;// 检查该字符是否已经出现过一次if (count[index] == 2) {return ch;}}return ' ';}
}

• 创建一个长度为 26 的数组 count，用于记录每个字母的出现次数。

• 遍历字符串，计算当前字符对应的数组索引，并增加该索引的计数。

• 如果当前字符的计数达到 2，返回该字符，表示它是第一个出现两次的字符。

  1. 字符的 ASCII 值：
     • 在 ASCII 编码表中，字符 'a' 的值是 97，字符 'b' 的值是 98，依次类推，直到字符 'z' 的值是 122。
  2. 字符减去 'a'：
     • 假设 ch 是一个小写字母字符，那么 ch - 'a' 会计算 ch 与 'a' 之间的差值。
     • 例如，如果 ch 是 'a'，那么 index = ch - 'a' = 97 - 97 = 0。
     • 如果 ch 是 'b'，那么 index = ch - 'a' = 98 - 97 = 1。
     • 如果 ch 是 'z'，那么 index = ch - 'a' = 122 - 97 = 25。

  这样就将字符 ch 映射到了从 0 到 25 的整数范围内，对应到数组的索引。这个技巧常用于需要处理 26 个小写字母的情况，比如统计字母出现次数、字符频率、快速查找字母等。