leetcode - 360周赛

这篇具有很好参考价值的文章主要介绍了leetcode - 360周赛。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一,2833. 距离原点最远的点

leetcode - 360周赛,leetcode,算法,职场和发展

 这道题的意思是,遇到 "L" 向左走,遇到 "R" 向右走,遇到 "_" 左右都可以走,那么要想找到距离原点最远的点,就是在找 | "L" + "R" | + "_" 

代码如下:

class Solution {
    public int furthestDistanceFromOrigin(String moves) {
        int _cnt = 0, L = 0, R = 0;
        for(int i=0; i<moves.length(); i++){
            if(moves.charAt(i) == '_'){
                _cnt++;
            }else if(moves.charAt(i) == 'L'){
                L++;
            }else{
                R++;
            }
        }
        return Math.abs(L-R)+_cnt;
    }
}

二,2834. 找出美丽数组的最小和

leetcode - 360周赛,leetcode,算法,职场和发展

 这道题要我们求最小和,那么我们肯定是从1开始往后遍历,而且题目要求不存在两个不同的下标 i 和 j,使得 nums[i] + nums[j] == target,说明 当 nums[i] + nums[j] == target 时,我们只能在其中选择较小的值,例如 :3 + 5 == 8,我们要求最小和,那么就只能选择 3 。还有一种情况,当我们遍历到的正整数 >= target 时,就不会存在上面两数相加等于target的情况,可以直接加入。

代码如下:

class Solution {
    public long minimumPossibleSum(int n, int target) {
        long sum = 0;
        int i = 1;
        int k = 0;
        while(k < n){
        // i 是 nums[i], target-i 是 nums[j]
            if(i <= target-i){
                sum += i; 
                k++;
            }
            if(i >= target){
                sum += i;
                k++;
            }
            i++;
        }
        return sum;
    }
}

三,2835. 使子序列的和等于目标的最少操作次数

leetcode - 360周赛,leetcode,算法,职场和发展

 题目告诉我们nums中存的是2的幂,所以关键是要想到使用二进制来拼凑出 target 的每一个二进制位中的 1。

1.  当 sum < target 时,因为每一个2^i 都能分成 2^i 个 1,所以我们只能得到[0,sum]中的数,说明不可能得到 target ,直接 return  -1.

2.  当 sum >= target 时,求最少的操作次数,最好的情况是,nums中有一个数 或 小于target的几个数的和 恰好等于 target, 这样看来,要求最小的操作次数,我们就要从二进制的低位向高位去考虑,因为我们要先考虑能不能直接用小于target的数凑出target。

 3. target 的第 i 个二进制位的获取方法:

  1. 如果 nums 中 <= 2^i 的值的和 >= 2^i ,那么一定可以直接凑出 2^i ,直接continue
  2. 如果和小于 2^i,那么我们只能在nums中找到大于2^i 的值 2^j (j > i),然后通过不断的 /2 来得到 2^i,又因为 /2 的值都会重新放入数组 nums 中,所以 target 中第 i 到 第 j-1 的二进制位都不需要再算了,直接从第 j 个二进制位开始。

  证明1,(s表示<=2^i的数字之和):

  • 当 i = 1,s >= 2^1 时,

1)nums中存在2,很明显结论正确。

2)  nums中不存在2,那么nums中 < 2^1 的数是 1,而 1 + 1 也能得到2,结论成立。

  • 当 i = 2, s >= 2^2 时,

1)nums中存在4,很明显结论正确。

2)nums中不能在4,那么nums中 < 2^2 的数有 1/2,即<=2^1,s >= 2^2 >= 2^1,根据上面得出的结论,可以得到一个2,那么剩下的 s-2 >= 2,同理,也成立。

  • 当 i = 3,s >= 2^3 时,

1)nums中存在8,很明显结论正确。

2)nums中不存在8,那么nums中 < 2^3 的数是 1/2/4,即<=2^2,s >= 2^3 >= 2^2,根据上面的结论,可以得到一个4,那么剩下的 s-4 >= 4,同理,也成立。 

由此类推,我们就可以得出结论:如果 nums 中 <= 2^i 的值的和 >= 2^i ,那么一定可以直接凑出 2^i

代码如下:

class Solution {
    
    public int minOperations(List<Integer> nums, int target) {
        long sum = 0;
        //31是根据数据范围确定,从前往后依次代表的是2^0 2^1....
        int[] cnt = new int[31];
        for(int x : nums){
            sum += x;
            for(int i=0; i<31; i++){
                //类似于哈希,记录nums数组中2^i有几个
                cnt[i] += x >> i & 1;
            }
        }
        if(sum < target) return -1;
        int i = 0, ans = 0, s = 0;
        while(1L<<i <= target){
            s += cnt[i]*(1<<i);// <=2^i的数的和
            int mask = (1<<(i+1))-1;
            //j=i
            i += 1;
            if(s >= (target&mask)){// target&mask 是得到target的0~i位的二进制数
                continue;
            }
            ans += 1;//当前2^j在nums中不能通过累加或直接得到
            while(cnt[i] == 0){//在nums中找到大于2^j的数,然后一路分割
                ans += 1;
                i += 1;
            }
        }
        return ans;
    }
}

四,2836. 在传球游戏中最大化函数值

leetcode - 360周赛,leetcode,算法,职场和发展 这道题可以暴力枚举,但是因为数据范围太大,所以需要优化,这里使用了树上倍增的算法思想,直接看代码:

class Solution {
    /**
    dp[i][j]: 从j开始,走2^i所能到达的位置
   
    sum[i][j]: 从j开始,走2^i所能得到的和
     */
    public long getMaxFunctionValue(List<Integer> receiver, long K) {
        int n = receiver.size();
        int m = 64 - Long.numberOfLeadingZeros(K); //K的二进制长度
        int[][] dp = new int[m][n];
        long[][] sum = new long[m][n];
        for (int i = 0; i < n; i++) {//初始化
            dp[0][i] = receiver.get(i);
            sum[0][i] = receiver.get(i);
        }
        for (int i = 0; i < m - 1; i++) {
            for (int x = 0; x < n; x++) {
                dp[i+1][x] = dp[i][dp[i][x]];
                sum[i+1][x] = sum[i][x] + sum[i][dp[i][x]];//合并节点值之和
            }
        }

        long ans = 0;
        for (int i = 0; i < n; i++) {
            long s = i;
            int x = i;
            for (long k = K; k > 0; k &= k-1) {
                int ctz = Long.numberOfTrailingZeros(k);//从低到高最后一个0的位置相当于要走2^ctz
                s += sum[ctz][x];
                x = dp[ctz][x];
            }
            ans = Math.max(ans, s);
        }
        return ans;
    }
}

 文章来源地址https://www.toymoban.com/news/detail-698911.html

到了这里,关于leetcode - 360周赛的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode周赛】LeetCode第358场周赛

    给你一个下标从0开始的整数数组nums。请你从nums中找出和最大的一对数,且这两个数数位上最大的数字相等。 返回最大和,如果不存在满足题意的数字对,返回 -1 。 示例 1: 输入:nums = [51,71,17,24,42] 输出:88 解释: i = 1 和 j = 2 ,nums[i] 和 nums[j] 数位上最大的数字相等,且这

    2024年02月12日
    浏览(45)
  • 【LeetCode周赛】LeetCode第370场周赛

    一场比赛中共有 n 支队伍,按从 0 到 n - 1 编号。 给你一个下标从 0 开始、大小为 n * n 的二维布尔矩阵 grid 。对于满足 0 = i, j = n - 1 且 i != j 的所有 i, j :如果 grid[i][j] == 1,那么 i 队比 j 队 强 ;否则,j 队比 i 队 强 。 在这场比赛中,如果不存在某支强于 a 队的队伍,则认为

    2024年02月05日
    浏览(53)
  • 【LeetCode周赛】LeetCode第359场周赛

    给你一个字符串数组 words 和一个字符串 s ,请你判断 s 是不是 words 的 首字母缩略词 。 如果可以按顺序串联 words 中每个字符串的第一个字符形成字符串 s ,则认为 s 是 words 的首字母缩略词。例如,“ab” 可以由 [“apple”, “banana”] 形成,但是无法从 [“bear”, “aardvark”

    2024年02月10日
    浏览(42)
  • 【职业人生】如何有效的在职场当中避免工作失误和提高个人发展

         《左传·宣公二年》:“人谁无过,过而能改,善莫大焉。”古往今来,多少人犯过错误。强大如“智绝”的诸葛孔明,也有街亭之失。职场人更是难免会在工作中出现失误。     在职场生涯当中避免不了在工作当中带来的失误,在这过程当中,我们应当要学会怎么去

    2024年02月08日
    浏览(44)
  • [office] excel成绩表格数据排名次的教程 #职场发展#知识分享#媒体

    excel成绩表格数据排名次的教程 Excel 中经常需要使用到 排名 次的技巧,成绩表格数据具体该如何排名呢?接下来是小编为大家带来的excel成绩表格数据排名次的教程,供大家参考。 步骤1:不管在学校还是各个统计领域,排名应用随处可见,如果排序会打乱原有次序,那么好多

    2024年02月21日
    浏览(40)
  • 突破职场竞争,引领未来发展:考取《研发效能(DevOps)工程师职业技术认证》

    就业形势堪忧,什么最有保障?考个“国家级”证书傍身吧! 工信部教考中心作为中国领先的行业技能认证机构,其颁发的认证证书不仅代表了个人在信息技术领域的专业能力,更可以录入工业和信息化技术技能人才数据库,这是一个重要的信息资源平台,它可以帮助企业和

    2024年02月05日
    浏览(47)
  • [office] Excel中函数进行计算两个日期参数差值的方法 #职场发展#学习方法#媒体

    Excel中函数进行计算两个日期参数差值的方法 在excel使用中,如果想计算两个日期参数的差值,该用什么函数和如何使用呢?今天,小编就教大家在Excel中函数进行计算两个日期参数差值的方法。 Excel中函数进行计算两个日期参数差值的步骤 在excel中计算两个日期参数的差值,

    2024年02月20日
    浏览(49)
  • [LeetCode108双周赛&LeetCode353周赛] 学习用记忆化搜索解决 DP 问题

    参考灵神直播和代码 @cache 装饰器的作用:将传入不同参数得到的函数值存储到缓存,避免下次传递相同参数重复计算结果,可用于解决递归函数重复计算问题,比如递归求斐波那契问题。 https://leetcode.cn/problems/maximum-number-of-jumps-to-reach-the-last-index/ 记忆化搜索 dfs(i) 表示以

    2024年02月13日
    浏览(39)
  • [LeetCode周赛复盘] 第 348场周赛20230604

    这场可惜了。 T1 模拟。 T2 模拟。 T3 倒序计算。 T4 同时限制上下界的数位DP。 6462. 最小化字符串长度 1. 题目描述 2. 思路分析 题意仔细想一下就会发现,其实会将每个字符仅留1个。 3. 代码实现 6424. 半有序排列 1. 题目描述 2. 思路分析 由于只能相邻交换来移动,因此每次只能

    2024年02月08日
    浏览(41)
  • [LeetCode周赛复盘] 第 359 场周赛20230820

    T1 模拟。 T2 数学贪心。 T3 dp。 T4 分组+滑窗。 2828. 判别首字母缩略词 1. 题目描述 2. 思路分析 按题意模拟即可。 3. 代码实现 2829. k-avoiding 数组的最小总和 1. 题目描述 2. 思路分析 贪心 1~k-1中,选了1就不能选k-1;选了2就不能选k-2… 因此可以选1~k//2 剩余的从k开始向上选。 可以

    2024年02月11日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包