Hexo

Posted 2022-06-24Updated 2022-06-24LeetCode / Hard / 复习2 minutes read (About 335 words)

Question

There are n different online courses numbered from 1 to n. You are given an array courses where courses[i] = [durationi, lastDayi] indicate that the ith course should be taken continuously for durationi days and must be finished before or on lastDayi.

You will start on the 1st day and you cannot take two or more courses simultaneously.

Return the maximum number of courses that you can take.

Solution

贪心算法，优先级队列实现。
优先选择截止日期更短的课程。
优先级队列pq记录当前已选课程，按持续时间从长到短排列。
同时维护当前的日期curDay。

当当前选择的课程截止日期晚于curDay加上当前的持续时间duration时，查看大根堆里最长的课程longestDuration。如果最长的时间大于当前时间，则将其挤出，并将当前课程加入。

如果当前课程截止日期晚于curDay，则直接将其加入队列中，并更新curDay。

Code

class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        int curDay = 0;
        for(int[] course : courses){
            int duration = course[0];
            int lastDay = course[1];
            
            if(curDay + duration > lastDay){    //大于截止日期
                if(pq.isEmpty()) continue;
                int longestDuration = pq.peek()[0];
                if(longestDuration > duration){ //替换到当前队列中持续日期最长的课程
                    curDay -= pq.poll()[0];
                    curDay += duration;
                    pq.offer(course);
                }
            }
            else{   //小于截止日期则加入选课
                curDay += duration;
                pq.offer(course);
            }
        }
        return pq.size();
    }
}

Posted 2022-06-24Updated 2022-06-23LeetCode / Hard4 minutes read (About 547 words)

1354. Construct Target Array With Multiple Sums

Question

You are given an array target of n integers. From a starting array arr consisting of n 1’s, you may perform the following procedure :

let x be the sum of all elements currently in your array.

choose index i, such that 0 <= i < n and set the value of arr at index i to x.

You may repeat this procedure as many times as needed.

Return true if it is possible to construct the target array from arr, otherwise, return false.

Solution 1

递归，每次寻找到数组中最大的数字的下标maxIndex，并对整个数组加和。
当数组中出现小于1的数时，不成立，返回false。
当数组加和等于数组长度时，返回true。

记录剩余的数字others，如果没有剩余数字，则返回false。
将target[maxIndex]减去others，因此每次翻倍，快速逼近。
当小于0时，则还原到上一个target[maxIndex]。

递归更改后的数组。

Code

class Solution {
    public boolean isPossible(int[] target) {
        int maxIndex = 0, sum = 0;
        for(int i = 0; i < target.length; i++){
            if(target[i] <= 0) return false;    //数组中出现小于1的数，则不成立，返回false
            if(target[maxIndex] < target[i]) maxIndex = i;
            sum += target[i];
        }
        if(sum == target.length) return true;   //加和等于长度，则数组内全部为1，返回true
        int others = sum - target[maxIndex];
        if(others == 0) return false;   //没有其他值时返回false
        target[maxIndex] -= others;
        int n = 1;
        while(target[maxIndex] > others){
            target[maxIndex] -= n * others;
            if(target[maxIndex] <= 0){
                target[maxIndex] += n * others;
                break;
            }
            n*=2;   //因子每次翻倍，快速逼近
        }
        return isPossible(target);
    }
}

Solution 2

优先级队列，大根堆。
每次挤出队列里最大的数字max。

如果max的值为1，则返回true。

计算加和和新的值，并更新sum。
如果最大的数字max小于0，或者剩余的sum小于0，则返回false。

当max仍然大于剩下的数字时，继续做减法。采用因数翻倍，快速接近目标值。
如果max小于0，则恢复到上一个值，并添加到优先级队列中。

Code

class Solution {
    public boolean isPossible(int[] target) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int sum = 0;
        for(int num : target){
            pq.offer(num);
            sum+=num;
        }
        while(true){
            int max = pq.poll();
            if(max == 1) return true;

            sum -= max;
            max = max - sum;
            if(sum <= 0 || max <= 0) return false;
            
            int n = 1;
            while(max > sum){
                max -= n * sum;
                if(max <= 0){
                    max += n * sum;
                    break;
                }
                n*=2;
            }
            sum += max;
            pq.offer(max);
        }
    }
}

Posted 2022-06-21Updated 2022-06-21LeetCode / Easya minute read (About 142 words)

771. Jewels and Stones

Question

You’re given strings jewels representing the types of stones that are jewels, and stones representing the stones you have. Each character in stones is a type of stone you have. You want to know how many of the stones you have are also jewels.

Letters are case sensitive, so "a" is considered a different type of stone from "A".

Solution

数组统计，先遍历宝石，记录宝石的位置。
然后遍历石头，如果对应的位置已被记录则计数加一。

Code

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        int ret = 0;
        int[] bin = new int[58];
        for(char c : jewels.toCharArray()){
            bin[c-'A']++;
        }
        
        for(char c : stones.toCharArray()){
            if(bin[c-'A'] != 0) ret++;
        }
        return ret;
    }
}

Posted 2022-06-21Updated 2022-06-21LeetCode / Easya few seconds read (About 72 words)

1108. Defanging an IP Address

Question

Given a valid (IPv4) IP address, return a defanged version of that IP address.

A defanged IP address replaces every period "." with "[.]".

Solution

迭代每个字符，用StringBuffer类来组成新的字符串。

Code

class Solution {
    public String defangIPaddr(String address) {
        StringBuffer sb = new StringBuffer();
        for(char c : address.toCharArray()){
            if(c == '.'){
                sb.append("[.]");
            }
            else{
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

Posted 2022-06-21Updated 2022-06-20LeetCode / Medium / 复习2 minutes read (About 341 words)

1642. Furthest Building You Can Reach

Question

You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.

You start your journey from building 0 and move to the next building by possibly using bricks or ladders.

While moving from building i to building i+1 (0-indexed),

If the current building’s height is greater than or equal to the next building’s height, you do not need a ladder or bricks.

If the current building’s height is less than the next building’s height, you can either use one ladder or (h[i+1] - h[i]) bricks.

Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.

Solution

贪心算法+优先级队列。

从第二栋楼开始遍历当前位置，下一栋楼与当前位置的高度差为h。
如果h小于0，则无成本前进。
否则如果剩余砖块，则优先使用砖块，并将使用砖块的个数加入大根堆中。
如果剩余砖块不足，且有梯子剩余时，用梯子替换掉小号最多砖块的位置，增加剩余砖块的数量。
如果剩余砖块和梯子都不足，则返回上一个位置。

如果遍历到最后，则返回最后一个建筑物的位置。

Code

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for(int i = 1; i < heights.length; i++){
            int h = heights[i] - heights[i-1];
            if(h > 0){
                pq.add(h);
                bricks-=h;
                if(bricks < 0){
                    if(ladders > 0){
                        ladders--;
                        bricks += pq.poll();
                    }
                    else{
                        return i-1;
                    }
                }
            }
        }
        return heights.length - 1;
    }
}

Question

Solution

Code

Question

Solution 1

Code

Solution 2

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Recents

Archives

Links