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第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日
    浏览(48)
  • 【LeetCode周赛】LeetCode第359场周赛

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

    2024年02月10日
    浏览(41)
  • 【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日
    浏览(40)
  • 【职业人生】如何有效的在职场当中避免工作失误和提高个人发展

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

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

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

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

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

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

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

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

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

    2024年02月13日
    浏览(35)
  • [LeetCode周赛复盘] 第 353 场周赛20230709

    感觉有奖品大家都来了。 T1 数学。 T2 dp。 T3 dp。 T4 差分/BIT RUPQ。 6451. 找出最大的可达成数字 1. 题目描述 2. 思路分析 为了使x num在t步内相同,需要相向而行,每步最大缩短距离是2,那么t步距离是2t。 3. 代码实现 6899. 达到末尾下标所需的最大跳跃次数 1. 题目描述 2. 思路分

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

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

    2024年02月08日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包