每日一题
Day1
最长和谐子序列(594)
class Solution {
public int findLHS(int[] nums) {
Arrays.sort(nums);
int lef = 0;
int res = 0;
for (int rig = 0; rig < nums.length; rig++){
while(nums[rig] - nums[lef] > 1) lef++;
if (nums[rig] - nums[lef] == 1) res = Math.max(res, rig -lef + 1);
}
return res;
}
}
- 分析
先对序列进行排序,通过双指针维护序列 时间复杂度 O(nlogn + n)
后来想了一下,长度其实就是 sum(num) + sum(num+1)
,可以通过Hash解决
Day2
找到初始输入字符串I(3330)
class Solution {
public int possibleStringCount(String word) {
int res = 0;
char curr = word.charAt(0);
for (char c : word.toCharArray()){
if (curr == c) res++;
curr = c;
}
return res;
}
}
- 分析
很简单,就是全排列
每一个多输入的字符都可能是输错了
Day3
失败了
找到初始输入字符串II(3333)
- 分析
我本来想的是排列组合嘛,踩坑了。重复的情况没有减掉,处理重复的情况太麻烦,疲惫了,看题解去了。
但我这个还是能算出 ==k的方案数的 骄傲🫡🫡
Day 4
找出第K个字符I(3304)
想到一个绝妙的idea!写了篇题解,反响也很好
Day 5
找出第K个字符II(3307)
子母体,同样移步至题解
Day6
找出数组中的幸运数(1394)
class Solution {
public int findLucky(int[] arr) {
int[] count = new int[501];
for (int num : arr){
count[num]++;
}
for (int i = 500; i >0; i--){
if (count[i] == i) return i;
}
return -1;
}
}
- 分析
非常简单的一题,最大的优化空间可能就是从Hash 到数组了(笑
Day7
找出和为指定的下标对(1865)
class FindSumPairs {
int[] nums1;
int[] nums2;
Map<Integer, Integer> countB = new HashMap<>();
public FindSumPairs(int[] nums1, int[] nums2) {
this.nums1 = nums1;
this.nums2 = nums2;
for (int num : nums2){
countB.put(num, countB.getOrDefault(num, 0) + 1);
}
}
public void add(int index, int val) {
int num = nums2[index];
nums2[index] += val;
countB.put(num, countB.get(num) - 1);
if (countB.get(num) == 0){
countB.remove(num);
}
num += val;
countB.put(num, countB.getOrDefault(num, 0) + 1);
}
public int count(int tot) {
int res = 0;
for(int num : nums1){
res += countB.getOrDefault(tot - num, 0);
}
return res;
}
}
- 分析
有点像数据库查询中的小表驱动大表
1 <= nums1.length <= 1000
1 <= nums1[i] <= 10⁹
1 <= nums2.length <= 10⁵
1 <= nums2[i] <= 10⁵
后面就是我的日常刷题了
不感兴趣的的可以移步了
H指数(274)
- 分析
由题干 h 篇论文被引用次数大于等于 h
我们对 引用次数相等的论文进行计数
再倒序求最大值
O(1) 时间插入、删除和获取随机元素(380)
- 分析
O(1)那必然是Hash,取一个Hash,一个数组,Hash用来保存值对应数组下标
难点在于删除,删除数组的中间元素是比较麻烦的,我们采用交换删除,将数组的最后一个元素移到被删除的元素位置,数组尾指针(通过尾指针向数组put元素)再往回走一格。
加油站(134)
- 分析
对每一个站点计算于全程的profit(能获得多少油),如果最终的profit >0 汽车一定能开一圈
站点的起始,取全程的profit最低点,因为往后开 后半程的profit必然大于0.
分发糖果(135)
- 分析
将相邻条件分两次循环计算,第一次保证左相邻符合题意,第二次保证右相邻符合题意
Z字变换(6)
- 分析
设置numRow个 StringBuilder 分别保管每一列的substring,以idx++和row的加减做上下扫描
leetcode刷题150+,感觉自己越来越得心应手了,大家如果想练一练应付面试,每天刷几题也挺有意思的
菜鸡相信努力