您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

LeetCode342. 4的幂 / 第243场周赛

342. 4的幂

2021.5.31 每日一题,很开心这个月又收货徽章了!

题目描述

给定一个整数,写一个函数来判断它是否是 4 的幂次方。如果是,返回 true ;否则,返回 false 。

整数 n 是 4 的幂次方需满足:存在整数 x 使得 n == 4x


示例 1:

输入:n = 16
输出:true
示例 2:

输入:n = 5
输出:false
示例 3:

输入:n = 1
输出:true

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/power-of-four
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

也想用简单一行的方法,但是没太想出来哈哈,就只能找二进制位的1在哪个位置了

class Solution {
    public boolean isPowerOfFour(int n) {
        //4的幂,就是统计这个1在第几位,如果是偶数位,就是4的幂
        if(n <= 0)
            return false;
        int count = 1;
        while((n & 1) != 1){
            n >>= 1;
            count++;
        }
        count++;
        return n == 1 && count % 2 == 0;
    }
}

官解的写法,构造一个奇数位都是1的整数,然后与n相与,如果是0,就表示是4的幂(是2的幂的前提下)
或者对3取余数,4的幂对3取余是1,如果是2的幂对3取余是2

class Solution {
    public boolean isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
        //return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1;
    }
}

第243场周赛

这场咋说呢,也是前两道秒过吧,第三道能做但卡,第四道基本没咋看,和周六晚上的双周赛基本一个节奏,下次目标还是三道题,不过排名进步了哈哈

1880. 检查某单词是否等于两单词之和

题目描述

字母的 字母值 取决于字母在字母表中的位置,从 0 开始 计数。即,'a' -> 0、'b' -> 1、'c' -> 2,以此类推。

对某个由小写字母组成的字符串 s 而言,其 数值 就等于将 s 中每个字母的 字母值 按顺序 连接 并 转换 成对应整数。

例如,s = "acb" ,依次连接每个字母的字母值可以得到 "021" ,转换为整数得到 21 。
给你三个字符串 firstWord、secondWord 和 targetWord ,每个字符串都由从 'a' 到 'j' (含 'a' 和 'j' )的小写英文字母组成。

如果 firstWord 和 secondWord 的 数值之和 等于 targetWord 的数值,返回 true ;否则,返回 false 。


示例 1:

输入:firstWord = "acb", secondWord = "cba", targetWord = "cdb"
输出:true
解释:
firstWord 的数值为 "acb" -> "021" -> 21
secondWord 的数值为 "cba" -> "210" -> 210
targetWord 的数值为 "cdb" -> "231" -> 231
由于 21 + 210 == 231 ,返回 true
示例 2:

输入:firstWord = "aaa", secondWord = "a", targetWord = "aab"
输出:false
解释:
firstWord 的数值为 "aaa" -> "000" -> 0
secondWord 的数值为 "a" -> "0" -> 0
targetWord 的数值为 "aab" -> "001" -> 1
由于 0 + 0 != 1 ,返回 false
示例 3:

输入:firstWord = "aaa", secondWord = "a", targetWord = "aaaa"
输出:true
解释:
firstWord 的数值为 "aaa" -> "000" -> 0
secondWord 的数值为 "a" -> "0" -> 0
targetWord 的数值为 "aaaa" -> "0000" -> 0
由于 0 + 0 == 0 ,返回 true

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/check-if-word-equals-summation-of-two-words
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

没啥好说的,变成数字,判断加法就行了

class Solution {
    public boolean isSumEqual(String firstWord, String secondWord, String targetWord) {
        int num1 = 0;
        for(int i = 0; i < firstWord.length(); i++){
            num1 = num1 * 10 + firstWord.charAt(i) - 'a';
        }
        int num2 = 0;
        for(int i = 0; i < secondWord.length(); i++){
            num2 = num2 * 10 + secondWord.charAt(i) - 'a';
        }
        int num3 = 0;
        for(int i = 0; i < targetWord.length(); i++){
            num3 = num3 * 10 + targetWord.charAt(i) - 'a';
        }
        return num1 + num2 == num3;
    }
}

1881. 插入后的最大值

题目描述

给你一个非常大的整数 n 和一个整数数字 x ,大整数 n 用一个字符串表示。n 中每一位数字和数字 x 都处于闭区间 [1, 9] 中,且 n 可能表示一个 负数 。

你打算通过在 n 的十进制表示的任意位置插入 x 来 最大化 n 的 数值 ​​​​​​。但 不能 在负号的左边插入 x 。

例如,如果 n = 73 且 x = 6 ,那么最佳方案是将 6 插入 7 和 3 之间,使 n = 763 。
如果 n = -55 且 x = 2 ,那么最佳方案是将 2 插在第一个 5 之前,使 n = -255 。
返回插入操作后,用字符串表示的 n 的最大值。


示例 1:

输入:n = "99", x = 9
输出:"999"
解释:不管在哪里插入 9 ,结果都是相同的。
示例 2:

输入:n = "-13", x = 2
输出:"-123"
解释:向 n 中插入 x 可以得到 -213、-123 或者 -132 ,三者中最大的是 -123 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-value-after-insertion
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

我当时还在想有0要怎么处理一下,结果一看没有0,那不用多说了

class Solution {
    public String maxValue(String n, int x) {
        //如果n是正数,就从左到右,如果找到大于的第一个数左边插入
        //如果是负数,找到小于的第一个数左边插入
        int l = n.length();
        boolean flag = n.charAt(0) == '-' ? false : true;
        int index = 0;
        if(flag){
            while(index < l){
                char c = n.charAt(index);
                if(x > c - '0')
                    break;
                index++;
            }
        }else{
            index = 1;
            while(index < l){
                char c = n.charAt(index);
                if(x < c - '0')
                    break;
                index++;
            }
        }
        char[] s = new char[l + 1];
        for(int i = 0; i <= l; i++){
            if(i < index)
                s[i] = n.charAt(i);
            else if(i == index)
                s[i] = (char)(x + 48);
            else
                s[i] = n.charAt(i - 1);
        }
        return new String(s);
        
    }   
}

1882. 使用服务器处理任务

题目描述

给你两个 下标从 0 开始 的整数数组 servers 和 tasks ,长度分别为 n​​​​​​ 和 m​​​​​​ 。servers[i] 是第 i​​​​​​​​​​ 台服务器的 权重 ,而 tasks[j] 是处理第 j​​​​​​ 项任务 所需要的时间(单位:秒)。

你正在运行一个仿真系统,在处理完所有任务后,该系统将会关闭。每台服务器只能同时处理一项任务。第 0 项任务在第 0 秒可以开始处理,相应地,第 j 项任务在第 j 秒可以开始处理。处理第 j 项任务时,你需要为它分配一台 权重最小 的空闲服务器。如果存在多台相同权重的空闲服务器,请选择 下标最小 的服务器。如果一台空闲服务器在第 t 秒分配到第 j 项任务,那么在 t + tasks[j] 时它将恢复空闲状态。

如果没有空闲服务器,则必须等待,直到出现一台空闲服务器,并 尽可能早 地处理剩余任务。 如果有多项任务等待分配,则按照 下标递增 的顺序完成分配。

如果同一时刻存在多台空闲服务器,可以同时将多项任务分别分配给它们。

构建长度为 m 的答案数组 ans ,其中 ans[j] 是第 j 项任务分配的服务器的下标。

返回答案数组 ans​​​​ 。


示例 1:

输入:servers = [3,3,2], tasks = [1,2,3,2,1,2]
输出:[2,2,0,2,1,2]
解释:事件按时间顺序如下:
- 0 秒时,第 0 项任务加入到任务队列,使用第 2 台服务器处理到 1 秒。
- 1 秒时,第 2 台服务器空闲,第 1 项任务加入到任务队列,使用第 2 台服务器处理到 3 秒。
- 2 秒时,第 2 项任务加入到任务队列,使用第 0 台服务器处理到 5 秒。
- 3 秒时,第 2 台服务器空闲,第 3 项任务加入到任务队列,使用第 2 台服务器处理到 5 秒。
- 4 秒时,第 4 项任务加入到任务队列,使用第 1 台服务器处理到 5 秒。
- 5 秒时,所有服务器都空闲,第 5 项任务加入到任务队列,使用第 2 台服务器处理到 7 秒。
示例 2:

输入:servers = [5,1,4,3,2], tasks = [2,1,2,4,5,2,1]
输出:[1,4,1,4,1,3,2]
解释:事件按时间顺序如下:
- 0 秒时,第 0 项任务加入到任务队列,使用第 1 台服务器处理到 2 秒。
- 1 秒时,第 1 项任务加入到任务队列,使用第 4 台服务器处理到 2 秒。
- 2 秒时,第 1 台和第 4 台服务器空闲,第 2 项任务加入到任务队列,使用第 1 台服务器处理到 4 秒。
- 3 秒时,第 3 项任务加入到任务队列,使用第 4 台服务器处理到 7 秒。
- 4 秒时,第 1 台服务器空闲,第 4 项任务加入到任务队列,使用第 1 台服务器处理到 9 秒。
- 5 秒时,第 5 项任务加入到任务队列,使用第 3 台服务器处理到 7 秒。
- 6 秒时,第 6 项任务加入到任务队列,使用第 2 台服务器处理到 7 秒。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/process-tasks-using-servers
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

每次看到这种一长串的题,感觉就是模拟了
然后我想的是把服务器放在优先队列中,按照权重和在servers数组中的位置排序;另外用一个哈希表存储<时间,服务器>的键值对,表示当前时间,哪几个服务器完成了工作
然后遍历时间,如果当前时间有服务器完成工作了,就放入优先队列中;如果当前有工作要完成,就去看优先队列中有没有服务器,如果有就安排到map集合中。

就这样,写了下面的代码,示例过了,但是提交超时了,但是不是数组很大的时候超时,而是不到十个数就超时了,那说明代码有问题,下面是当时写的代码:

class Solution {
    public int[] assignTasks(int[] servers, int[] tasks) {
        //模拟一下吧
        //优先队列,放入服务器,按权重和下标排序
        //然后遍历时间,如果可以分配服务器,就将服务器弹出,同时记录返回的时间,存入一个哈希表中
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0];
            }
        });
        int m = servers.length;
        for(int i = 0; i < m; i++){
            pq.offer(new int[]{servers[i], i});
        }
        Map<Integer, List<Integer>> map = new HashMap<>();
        int n = tasks.length;
        int[] res = new int[n];
        int index = 0;
        for(int i = 0; i < n; i++){
            //当前时间,是否有工作完成,有工作完成,把服务器空闲出来
            if(map.containsKey(i)){
                List<Integer> ser = map.get(i);
                map.remove(i);
                for(Integer s : ser){
                    pq.offer(new int[]{servers[s], s});
                }
            }
            while(index <= i){
                if(!pq.isEmpty()){
                    res[index] = pq.peek()[1];
                    if(map.containsKey(i + tasks[index])){
                        List<Integer> list = map.get(i + tasks[index]);
                        list.add(pq.poll()[1]);
                        map.put(i + tasks[index], list);
                    }else{
                        List<Integer> list = new LinkedList<>();
                        list.add(pq.poll()[1]);
                        map.put(i + tasks[index], list);
                    }
                    index++;
                }
            }
            if(index == n)
                break;
        }
        return res;
    }
}

应该是while那部分有问题,改一下看看行不行,简单改了一下,败给了超时,不过也在意料之中,因为时间我是一个一个加的。其实可以改成按tasks中一个个任务来,因为任务的处理是从左到右的,这里就不改了,题解思路也和我的思路差不多
这是我第一次改后的

class Solution {
    public int[] assignTasks(int[] servers, int[] tasks) {
        //模拟一下吧
        //优先队列,放入服务器,按权重和下标排序
        //然后遍历时间,如果可以分配服务器,就将服务器弹出,同时记录返回的时间,存入一个哈希表中
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0];
            }
        });
        int m = servers.length;
        for(int i = 0; i < m; i++){
            pq.offer(new int[]{servers[i], i});
        }
        Map<Long, List<Integer>> map = new HashMap<>();
        int n = tasks.length;
        int[] res = new int[n];
        int index = 0;
        //tasks长度最大为200000,m,n的值最大为200000,所以时间最多400000
        //不对,应该是乘
        for(long i = 0; i < 40000000001l; i++){
            //当前时间,是否有工作完成,有工作完成,把服务器空闲出来
            if(map.containsKey(i)){
                List<Integer> ser = map.get(i);
                map.remove(i);
                for(Integer s : ser){
                    pq.offer(new int[]{servers[s], s});
                }
            }
            //如果当前任务的开工时间小于i,表示可以开工
            while(index <= i){
                //如果有服务器空闲
                if(!pq.isEmpty()){
                    //取出第一个服务器的编号
                    res[index] = pq.peek()[1];
                    //如果哈希表中,存在这个时间点,就把这个服务器插入list集合中
                    if(map.containsKey(i + tasks[index])){
                        List<Integer> list = map.get(i + tasks[index]);
                        list.add(pq.poll()[1]);
                        map.put(i + tasks[index], list);
                    //如果没有这个编号,创建这个集合
                    }else{
                        List<Integer> list = new LinkedList<>();
                        list.add(pq.poll()[1]);
                        map.put(i + tasks[index], list);
                    }
                    index++;
                    if(index == n)
                        break;
                //如果没有,就直接跳出                        
                }else{
                    break;
                }
            }
            if(index == n)
                break;
        }
        return res;
    }
}

然后我看题解发现,只要将当服务器都被占用时,时间直接调成下一个服务器空闲的时间,就可以AC了,然后我就把原来的HashMap改成TreeMap,这样可以使服务器时间排序,然后每次服务器都被占用时,时间就可以跳成map.firstKey(),不过这个方法我还是第一次用
然后直接双百了哈哈

class Solution {
    public int[] assignTasks(int[] servers, int[] tasks) {
        //模拟一下吧
        //优先队列,放入服务器,按权重和下标排序
        //然后遍历时间,如果可以分配服务器,就将服务器弹出,同时记录返回的时间,存入一个哈希表中
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0];
            }
        });
        int m = servers.length;
        for(int i = 0; i < m; i++){
            pq.offer(new int[]{servers[i], i});
        }
        TreeMap<Long, List<Integer>> map = new TreeMap<>();
        int n = tasks.length;
        int[] res = new int[n];
        int index = 0;
        //tasks长度最大为200000,m,n的值最大为200000,所以时间最多400000
        //不对,应该是乘
        for(long i = 0; i < Long.MAX_VALUE; i++){
            //当前时间,是否有工作完成,有工作完成,把服务器空闲出来
            if(map.containsKey(i)){
                List<Integer> ser = map.get(i);
                map.remove(i);
                for(Integer s : ser){
                    pq.offer(new int[]{servers[s], s});
                }
            }
            //如果当前任务的开工时间小于i,表示可以开工
            while(index <= i){
                //如果有服务器空闲
                if(!pq.isEmpty()){
                    //取出第一个服务器的编号
                    res[index] = pq.peek()[1];
                    //如果哈希表中,存在这个时间点,就把这个服务器插入list集合中
                    if(map.containsKey(i + tasks[index])){
                        List<Integer> list = map.get(i + tasks[index]);
                        list.add(pq.poll()[1]);
                        map.put(i + tasks[index], list);
                    //如果没有这个编号,创建这个集合
                    }else{
                        List<Integer> list = new LinkedList<>();
                        list.add(pq.poll()[1]);
                        map.put(i + tasks[index], list);
                    }
                    index++;
                    if(index == n)
                        break;
                //如果没有,就直接跳出  
                //如果没有,就把i设置成下一个服务器可用的时间                      
                }else{
                    i = map.firstKey() - 1;
                    break;
                }
            }
            if(index == n)
                break;
        }
        return res;
    }
}

在这里插入图片描述

1883. 准时抵达会议现场的最小跳过休息次数

题目描述

给你一个整数 hoursBefore ,表示你要前往会议所剩下的可用小时数。要想成功抵达会议现场,你必须途经 n 条道路。道路的长度用一个长度为 n 的整数数组 dist 表示,其中 dist[i] 表示第 i 条道路的长度(单位:千米)。另给你一个整数 speed ,表示你在道路上前进的速度(单位:千米每小时)。

当你通过第 i 条路之后,就必须休息并等待,直到 下一个整数小时 才能开始继续通过下一条道路。注意:你不需要在通过最后一条道路后休息,因为那时你已经抵达会议现场。

例如,如果你通过一条道路用去 1.4 小时,那你必须停下来等待,到 2 小时才可以继续通过下一条道路。如果通过一条道路恰好用去 2 小时,就无需等待,可以直接继续。
然而,为了能准时到达,你可以选择 跳过 一些路的休息时间,这意味着你不必等待下一个整数小时。注意,这意味着与不跳过任何休息时间相比,你可能在不同时刻到达接下来的道路。

例如,假设通过第 1 条道路用去 1.4 小时,且通过第 2 条道路用去 0.6 小时。跳过第 1 条道路的休息时间意味着你将会在恰好 2 小时完成通过第 2 条道路,且你能够立即开始通过第 3 条道路。
返回准时抵达会议现场所需要的 最小跳过次数 ,如果 无法准时参会 ,返回 -1 。


示例 1:

输入:dist = [1,3,2], speed = 4, hoursBefore = 2
输出:1
解释:
不跳过任何休息时间,你将用 (1/4 + 3/4) + (3/4 + 1/4) + (2/4) = 2.5 小时才能抵达会议现场。
可以跳过第 1 次休息时间,共用 ((1/4 + 0) + (3/4 + 0)) + (2/4) = 1.5 小时抵达会议现场。
注意,第 2 次休息时间缩短为 0 ,由于跳过第 1 次休息时间,你是在整数小时处完成通过第 2 条道路。
示例 2:

输入:dist = [7,3,5,5], speed = 2, hoursBefore = 10
输出:2
解释:
不跳过任何休息时间,你将用 (7/2 + 1/2) + (3/2 + 1/2) + (5/2 + 1/2) + (5/2) = 11.5 小时才能抵达会议现场。
可以跳过第 1 次和第 3 次休息时间,共用 ((7/2 + 0) + (3/2 + 0)) + ((5/2 + 0) + (5/2)) = 10 小时抵达会议现场。
示例 3:

输入:dist = [7,3,5,5], speed = 1, hoursBefore = 10
输出:-1
解释:即使跳过所有的休息时间,也无法准时参加会议。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-skips-to-arrive-at-meeting-on-time
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

乍看和上周周赛第二题背景有点相似,但是这个题多了个跳过…并且如果跳过了一个点,那么下一个点也要考虑进去
又是动态规划…
dp[i][j]表示已经走完第i段路,并且使用了j次跳过的最短用时
看到这个写法很妙,学习一下
浮点数精度的处理很需要注意!!!!!

class Solution {
    public int minSkips(int[] dist, int speed, int hoursBefore) {
        int n= dist.length;
        //dp[i][j]表示已经走完第i段道路且跳过次数为j的最短用时
        long[][] dp = new long[n + 1][n + 1];
        //赋初值
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= n; j++){
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        
        //状态转移
        //最后一段路特殊处理
        for(int i = 1; i <= n - 1; i++){
            for(int j = 0; j <= i; j++){
                //由于浮点数有精度限制,直接除的话会导致精度丢失,所以先把分子存下来,最后统一做除法
               	//如果j为0,表明没有跳过,就是和上周周赛第二题一样计算
               	//不过这里dp里先暂存的是距离
                if(j == 0){   
                    dp[i][j]=(dp[i-1][j]+dist[i-1]+speed-1)/speed*speed;
				//如果有跳过,那么当前距离可以选择跳过或者不跳过
                }else{
                	//第一项,跳过;第二项,不跳过
                    dp[i][j]=Math.min(dp[i-1][j-1]+dist[i-1],(dp[i-1][j]+dist[i-1]+speed-1)/speed*speed);
                }
            }
        }
        //处理最后一个距离,最后一个距离不用跳过
        for(int i=0;i<=n;i++){
            if((double)(dp[n-1][i]+dist[n-1])/(double)speed<=(double)hoursBefore)
                return i;
        }
        return -1;
    }
}

作者:garett
链接:https://leetcode-cn.com/problems/minimum-skips-to-arrive-at-meeting-on-time/solution/n2-dp-javashuang-bai-by-garett-s7sc/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进