LeetCode周简报1

每日一题

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