本文主要是介绍每日力扣刷题day03(从零开始版),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 2024.5.24(5题)
- 2828.判别首字母缩略词
- 题解一
- 题解二
- 1365.有多少小于当前数字的数字
- 题解一
- 题解二
- 题解三
- 2469.温度转换
- 题解一
- 题解二
- 1502.判断能否形成等差数列
- 题解一
- 题解二
- 2351.第一个出现两次的字母
- 题解一
- 题解二
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,返回该字符,表示它是第一个出现两次的字符。
- 字符的 ASCII 值:
- 在 ASCII 编码表中,字符
'a'
的值是 97,字符'b'
的值是 98,依次类推,直到字符'z'
的值是 122。
- 在 ASCII 编码表中,字符
- 字符减去
'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 个小写字母的情况,比如统计字母出现次数、字符频率、快速查找字母等。 - 字符的 ASCII 值:
这篇关于每日力扣刷题day03(从零开始版)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!