每日一題

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+，感覺自己越來越得心應手了，大家如果想練一練應付面試，每天刷幾題也挺有意思的
菜雞相信努力