每日一题

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！写了篇题解，反响也很好

为什么是位运算，二叉树分析清晰图解I

Day 5

找出第K个字符II（3307）

子母体，同样移步至题解

为什么是位运算，二叉树分析清晰图解II

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+，感觉自己越来越得心应手了，大家如果想练一练应付面试，每天刷几题也挺有意思的
菜鸡相信努力