【题解】leetcode 周赛237 ——题解

1.leetcode_1832_Check_if_the_Sentence_Is_Pangram

这一题比较直白,count 一下每个字母出现的次数即可。看独立字母数有没有到 26 即可。

// AC
// Runtime: 5 ms, faster than 25.00% of Java online submissions for Check if the Sentence Is Pangram.
// Memory Usage: 39 MB, less than 25.00% of Java online submissions for Check if the Sentence Is Pangram.
class Solution {
    public boolean checkIfPangram(String sentence) {
        int size = sentence.length();
        Map<String, Integer> record = new HashMap<>();
        for(int i = 0; i < size; i++) {
            String temp = String.valueOf(sentence.charAt(i));
            record.merge(temp, 1, Integer::sum);
        }
        return record.size() == 26;
    }
}

  

2.leetcode_1833_Maximum_Ice_Cream_Bars

贪心法:先排序,然后从小到大累加。如果累加和恰好等于 k,则返回个数。如果恰号大于 k,上一个累加和恰小于 k,则返回(当前累加计数 - 1)

// AC:
// Runtime: 28 ms, faster than 100.00% of Java online submissions for Maximum Ice Cream Bars.
// Memory Usage: 55.9 MB, less than 25.00% of Java online submissions for Maximum Ice Cream Bars.
class Solution {
    public int maxIceCream(int[] costs, int coins) {
        Arrays.sort(costs);
        int sum = 0;
        for(int i = 0; i < costs.length; i++) {
            sum += costs[i];
            if (sum == coins) {
                return i + 1;
            }
            if (sum > coins) {
                if (sum == 0) {
                    return 0;
                } else {
                    return i;
                }
            }
        }
        return costs.length;
    }
}

   

3.leetcode_1834_Single-Threaded_CPU

用优先级队列模拟当前 CPU 可选任务池,每次循环将小于当前 time 的任务插入优先级队列(以执行时间越短越靠前做优先级排序依据)

从队列中 pull 出满足小于当前 time 且执行之间最短的 task

// AC:
// Runtime: 103 ms, faster than 57.14% of Java online submissions for Single-Threaded CPU.
// Memory Usage: 96.7 MB, less than 14.29% of Java online submissions for Single-Threaded CPU.
// 思路:用优先级队列,模拟当前 CPU 可选的任务池,
// 
class Solution {
    public int[] getOrder(int[][] tasks) {
        int taskCount = tasks.length;
        int[] ret = new int[taskCount];
        int[][] taskRecord = new int[taskCount][3];
        for(int i = 0; i < taskCount; i++) {
            taskRecord[i][0] = i;
            taskRecord[i][1] = tasks[i][0];
            taskRecord[i][2] = tasks[i][1];
        }
        Arrays.sort(taskRecord, (a, b) -> (a[1] - b[1]));
        // 按执行时间越短排越前
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>((a, b) -> a[2] == b[2] ? a[0] - b[0] : a[2] - b[2]);
        int time = 0, step = 0, timeStep = 0;
        while (step < taskCount) {
            while (timeStep < taskCount && taskRecord[timeStep][1] <= time) {
                queue.offer(taskRecord[timeStep++]);
            }
            if (queue.isEmpty()) {
                time = taskRecord[timeStep][1];
                continue;
            }
            int[] curTask = queue.poll();
            ret[step++] = curTask[0];
            time += curTask[2];
        }

        return ret;
    }
}


4.leetcode_1835_Find_XOR_Sum_of_All_Pairs_Bitwise_AND

(当时没想出来!) 位运算技巧:(a1 ^ a2) & (b1 ^ b2) = (a1 & b1) ^ (a1 & b2) ^ (a2 & b1) ^ (a2 & b2)

// AC:
// Runtime: 1 ms, faster than 100.00% of Java online submissions for Find XOR Sum of All Pairs Bitwise AND.
// Memory Usage: 52.3 MB, less than 25.00% of Java online submissions for Find XOR Sum of All Pairs Bitwise AND.
// 
// 思路:这个运算场景满足结合律: (a1 ^ a2) & (b1 ^ b2) = (a1 & b1) ^ (a1 & b2) ^ (a2 & b1) ^ (a2 & b2)
// 复杂度:T:O(m + n), S:O(1)
class Solution {
    public int getXORSum(int[] arr1, int[] arr2) {
        int ret1 = 0, ret2 = 0;
        for(int i: arr1) {
            ret1 ^= i;
        }
        for(int i: arr2) {
            ret2 ^= i;
        }
        return ret1 & ret2;
    }
}


发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

«   2021年5月   »
12
3456789
10111213141516
17181920212223
24252627282930
31
控制面板
您好,欢迎到访网站!
  查看权限
网站分类
搜索
最新留言
文章归档
网站收藏
友情链接

    Powered By Z-BlogPHP 1.5.2 Zero

    Copyright liuyang1.com. 转载文章,请注明出处。谢谢!