Hexo

Posted 2022-07-05Updated 2022-07-04LeetCode / Medium / 复习2 minutes read (About 306 words)

Question

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Solution 1

哈希表，先将所有元素加入哈希表。
然后遍历哈希表，如果表内没有当前数字-1时（没有更小的连续数字），则将temp初始化为1。
当表内有下一个连续数字时，将temp和curNum增加1。

当没有下一个连续数字时，更新结果到res上。

Code

class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        
        for(int num : nums){
            set.add(num);
        }
        
        int res = 0;
        
        for(int num : set){
            if(!set.contains(num - 1)){
                int temp = 1;
                int curNum = num;
                while(set.contains(curNum + 1)){
                    temp++;
                    curNum++;
                }
                res = Math.max(res, temp);
            }
        }
        return res;
    }
}

Solution 2

先排序，再遍历。
维护一个最大长度res。
用一个temp参数记录连续长度。
如果当前值是上一个值+1，则temp+1。
如果当前值等于上一个值，则continue。
其他情况则更新最大长度res，并将temp恢复为1。

Code

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) return 0;
        Arrays.sort(nums);
        int res = 0, temp = 1;
        
        for(int i = 1; i < nums.length; i++){
            if(nums[i] == nums[i-1] + 1){
                temp++;
            }
            else if(nums[i] == nums[i-1]){
                continue;
            }
            else{
                res = Math.max(res, temp);
                temp = 1;
            }
        }
        res = Math.max(res, temp);
        
        return res;
    }
}

Posted 2022-07-04Updated 2022-07-04LeetCode / Hard / 复习2 minutes read (About 227 words)

135. Candy

Question

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.

Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Solution

双向遍历。
先从左至右遍历数组，如果上一个数值小于当前数值，则当前糖果等于上一个糖果数+1。
然后从右至左遍历数组，同理计算right的数值。
然后保存right与left[]里较大的数值，作为需要分配的糖果数加入到res。

Code

class Solution {
    public int candy(int[] ratings) {
        int[] left = new int[ratings.length];
        for(int i = 0; i < ratings.length; i++){
            if(i > 0 && ratings[i] > ratings[i-1]){
                left[i] = left[i-1] + 1;
            }
            else{
                left[i] = 1;
            }
        }
        
        int right = 0, res = 0;
        for(int i = ratings.length-1; i >= 0; i--){
            if(i < ratings.length-1 && ratings[i] > ratings[i+1]){
                right++;
            }
            else{
                right = 1;
            }
            res += Math.max(left[i], right);
        }
        return res;
    }
}

Posted 2022-07-02Updated 2022-07-01LeetCode / Medium2 minutes read (About 264 words)

1465. Max Area After Horizontal and Vertical Cuts

Question

You are given a rectangular cake of size h x w and two arrays of integers horizontalCuts and verticalCuts where:

horizontalCuts[i] is the distance from the top of the rectangular cake to the ith horizontal cut and similarly, and

verticalCuts[j] is the distance from the left of the rectangular cake to the jth vertical cut.

Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a large number, return this modulo 109 + 7.

Solution

先排序，记录两次切割之间的距离的最大值。
最后同样需要比较蛋糕的总尺寸和最后一次切割的距离。

返回宽度和长度的最大值的乘积即可。

注意：两个int整数相乘会溢出，max需要记录为long类型。

Code

class Solution {
    public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        int MOD = (int) Math.pow(10,9)+7;
        Arrays.sort(horizontalCuts);
        Arrays.sort(verticalCuts);
        long maxH = 0, maxV = 0;
        int lastH = 0, lastV = 0;
        
        for(int i = 0; i < horizontalCuts.length; i++){
            maxH = Math.max(maxH, horizontalCuts[i] - lastH);
            lastH = horizontalCuts[i];
        }
        
        maxH = Math.max(maxH, h - lastH);
        
        for(int i = 0; i < verticalCuts.length; i++){
            maxV = Math.max(maxV, verticalCuts[i] - lastV);
            lastV = verticalCuts[i];
        }
        
        maxV = Math.max(maxV, w - lastV);
        return (int) (maxV * maxH % MOD) ;
    }
}

Posted 2022-07-01Updated 2022-07-01LeetCode / Easya minute read (About 221 words)

1710. Maximum Units on a Truck

Question

You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:

numberOfBoxesi is the number of boxes of type i.

numberOfUnitsPerBoxi is the number of units in each box of the type i.

You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.

Return the maximum total number of units that can be put on the truck.

Solution

根据每个箱子可以装最多单元从大到小排序。
遍历数组，如果truckSize还有剩余，则将res增加容量乘以箱子数量。
然后将truckSize减少箱子数量个。

最后返回res即可。

Code

class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        int res = 0;
        Arrays.sort(boxTypes, (a,b) -> b[1] - a[1]);
        for(int i = 0; i < boxTypes.length; i++){
            int numberOfBoxes = boxTypes[i][0];
            int numberOfUnitesPerBox = boxTypes[i][1];
            
            if(truckSize <= numberOfBoxes){
                res += numberOfUnitesPerBox * truckSize;
                break;
            }
            else{
                truckSize -= numberOfBoxes;
                res += numberOfBoxes * numberOfUnitesPerBox;
            }
        }
        return res;
    }
}

Posted 2022-06-28Updated 2022-07-01LeetCode / Medium2 minutes read (About 227 words)

1647. Make Character Frequencies Unique

Question

A string s is called good if there are no two different characters in s that have the same frequency.

Given a string s, return* the minimum number of characters you need to delete to make s good.*

The frequency of a character in a string is the number of times it appears in the string. For example, in the string "aab", the frequency of 'a' is 2, while the frequency of 'b' is 1.

Solution

数组统计+哈希表
用数组统计记录每个字符出现的数量。
count记录需要减少的字符数量。

遍历统计数组，如果哈希表中已经记录，则将数组统计减少，直到归零。
每减少一次则为count加一。
如果哈希表中未记录，则将当前数字添加到哈希表中。

Code

class Solution {
    public int minDeletions(String s) {
        int count = 0;
        HashSet<Integer> set = new HashSet<>();
        int[] bin = new int[26];
        for(char c : s.toCharArray()){
            bin[c - 'a']++;
        }
        
        for(int i = 0; i < 26; i++){
            while(bin[i] !=0 && set.contains(bin[i])){
                bin[i]--;
                count++;
            }
            set.add(bin[i]);
        }
        return count;
    }
}

Question

Solution 1

Code

Solution 2

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Recents

Archives

Links