周赛347(模拟、思维题、动态规划+优化)

这篇具有很好参考价值的文章主要介绍了周赛347(模拟、思维题、动态规划+优化)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

周赛347

2710. 移除字符串中的尾随零

难度简单1

给你一个用字符串表示的正整数 num ,请你以字符串形式返回不含尾随零的整数 num

示例 1:

输入:num = "51230100"
输出:"512301"
解释:整数 "51230100" 有 2 个尾随零,移除并返回整数 "512301" 。

示例 2:

输入:num = "123"
输出:"123"
解释:整数 "123" 不含尾随零,返回整数 "123" 。

提示:

  • 1 <= num.length <= 1000
  • num 仅由数字 09 组成
  • num 不含前导零

模拟

class Solution {
    public String removeTrailingZeros(String num) {
        int j = num.length() - 1;
        while(j >= 0 && num.charAt(j) - '0' == 0)
            j -= 1;
        return num.substring(0, j+1);
    }
}

2711. 对角线上不同值的数量差

难度中等4

给你一个下标从 0 开始、大小为 m x n 的二维矩阵 grid ,请你求解大小同样为 m x n 的答案矩阵 answer

矩阵 answer 中每个单元格 (r, c) 的值可以按下述方式进行计算:

  • topLeft[r][c] 为矩阵 grid 中单元格 (r, c) 左上角对角线上 不同值 的数量。
  • bottomRight[r][c] 为矩阵 grid 中单元格 (r, c) 右下角对角线上 不同值 的数量。

然后 answer[r][c] = |topLeft[r][c] - bottomRight[r][c]|

返回矩阵 answer

矩阵对角线 是从最顶行或最左列的某个单元格开始,向右下方向走到矩阵末尾的对角线。

如果单元格 (r1, c1) 和单元格 (r, c) 属于同一条对角线且 r1 < r ,则单元格 (r1, c1) 属于单元格 (r, c) 的左上对角线。类似地,可以定义右下对角线。

示例 1:

周赛347(模拟、思维题、动态规划+优化)

输入:grid = [[1,2,3],[3,1,5],[3,2,1]]
输出:[[1,1,0],[1,0,1],[0,1,1]]
解释:第 1 个图表示最初的矩阵 grid 。 
第 2 个图表示对单元格 (0,0) 计算,其中蓝色单元格是位于右下对角线的单元格。
第 3 个图表示对单元格 (1,2) 计算,其中红色单元格是位于左上对角线的单元格。
第 4 个图表示对单元格 (1,1) 计算,其中蓝色单元格是位于右下对角线的单元格,红色单元格是位于左上对角线的单元格。
- 单元格 (0,0) 的右下对角线包含 [1,1] ,而左上对角线包含 [] 。对应答案是 |1 - 0| = 1 。
- 单元格 (1,2) 的右下对角线包含 [] ,而左上对角线包含 [2] 。对应答案是 |0 - 1| = 1 。
- 单元格 (1,1) 的右下对角线包含 [1] ,而左上对角线包含 [1] 。对应答案是 |1 - 1| = 0 。
其他单元格的对应答案也可以按照这样的流程进行计算。

示例 2:

输入:grid = [[1]]
输出:[[0]]
解释:- 单元格 (0,0) 的右下对角线包含 [] ,左上对角线包含 [] 。对应答案是 |0 - 0| = 0 。

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n, grid[i][j] <= 50

模拟

class Solution {
    public int[][] differenceOfDistinctValues(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] res = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                Set<Integer> topleft = new HashSet<>();
                Set<Integer> bottomright = new HashSet<>();
                int k = i-1, x = j-1;
                while(k >= 0 && x >= 0){
                    topleft.add(grid[k][x]);
                    k -= 1;
                    x -= 1;
                }
                k = i+1; x = j+1;
                while(k < m && x < n){
                    bottomright.add(grid[k][x]);
                    k += 1;
                    x += 1;
        
                }
                res[i][j] = Math.abs(topleft.size() - bottomright.size());
            }
        }
        return res;
    }
}

2712. 使所有字符相等的最小成本

难度中等6

给你一个下标从 0 开始、长度为 n 的二进制字符串 s ,你可以对其执行两种操作:

  • 选中一个下标 i 并且反转从下标 0 到下标 i(包括下标 0 和下标 i )的所有字符,成本为 i + 1
  • 选中一个下标 i 并且反转从下标 i 到下标 n - 1(包括下标 i 和下标 n - 1 )的所有字符,成本为 n - i

返回使字符串内所有字符 相等 需要的 最小成本

反转 字符意味着:如果原来的值是 ‘0’ ,则反转后值变为 ‘1’ ,反之亦然。

示例 1:

输入:s = "0011"
输出:2
解释:执行第二种操作,选中下标 i = 2 ,可以得到 s = "0000" ,成本为 2 。可以证明 2 是使所有字符相等的最小成本。

示例 2:

输入:s = "010101"
输出:9
解释:执行第一种操作,选中下标 i = 2 ,可以得到 s = "101101" ,成本为 3 。
执行第一种操作,选中下标 i = 1 ,可以得到 s = "011101" ,成本为 2 。
执行第一种操作,选中下标 i = 0 ,可以得到 s = "111101" ,成本为 1 。
执行第二种操作,选中下标 i = 4 ,可以得到 s = "111110" ,成本为 2 。
执行第一种操作,选中下标 i = 5 ,可以得到 s = "111111" ,成本为 1 。
使所有字符相等的总成本等于 9 。可以证明 9 是使所有字符相等的最小成本。 

提示:

  • 1 <= s.length == n <= 105
  • s[i]'0''1'

结论题(思维题)

https://leetcode.cn/problems/minimum-cost-to-make-all-characters-equal/solution/yi-ci-bian-li-jian-ji-xie-fa-pythonjavac-aut0/

class Solution:
    def minimumCost(self, s: str) -> int:
        # 结论1 : 先选择下标1反转再反转下标2 和 先反转下标2再反转下标1 结果相同
        #       ==> 可以从左到右反转
        # 结论2 : 当s[i-1] != s[i]时,必须反转,
        #               而操作:反转左边和反转右边 对[i+1:n]对答案的结果 影响相同
        #               或者说 反转前不同的,反转后仍然不同                        
        #       ==> 当s[i-1] != s[i]时,反转成本少的
        n = len(s)
        ans = 0
        for i in range(1, n):
            if s[i-1] != s[i]:
                ans += min(i, n-i)
        return ans

2713. 矩阵中严格递增的单元格数

难度困难16

给你一个下标从 1 开始、大小为 m x n 的整数矩阵 mat,你可以选择任一单元格作为 起始单元格

从起始单元格出发,你可以移动到 同一行或同一列 中的任何其他单元格,但前提是目标单元格的值 严格大于 当前单元格的值。

你可以多次重复这一过程,从一个单元格移动到另一个单元格,直到无法再进行任何移动。

请你找出从某个单元开始访问矩阵所能访问的 单元格的最大数量

返回一个表示可访问单元格最大数量的整数。

示例 1:

周赛347(模拟、思维题、动态规划+优化)

输入:mat = [[3,1],[3,4]]
输出:2
解释:上图展示了从第 1 行、第 2 列的单元格开始,可以访问 2 个单元格。可以证明,无论从哪个单元格开始,最多只能访问 2 个单元格,因此答案是 2 。 

示例 2:

周赛347(模拟、思维题、动态规划+优化)

输入:mat = [[1,1],[1,1]]
输出:1
解释:由于目标单元格必须严格大于当前单元格,在本示例中只能访问 1 个单元格。 

示例 3:

周赛347(模拟、思维题、动态规划+优化)

输入:mat = [[3,1,6],[-9,5,7]]
输出:4
解释:上图展示了从第 2 行、第 1 列的单元格开始,可以访问 4 个单元格。可以证明,无论从哪个单元格开始,最多只能访问 4 个单元格,因此答案是 4 。  

提示:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 105
  • 1 <= m * n <= 105
  • -105 <= mat[i][j] <= 105

动态规划 + 优化(如何思考?)

https://leetcode.cn/problems/maximum-strictly-increasing-cells-in-a-matrix/solution/dong-tai-gui-hua-you-hua-pythonjavacgo-b-axv0/文章来源地址https://www.toymoban.com/news/detail-463961.html

class Solution {
    /**
        直接DP超时
        定义 f[i][j] 表示到达 mat[i][j] 时所访问的单元格的最大数量。那么答案就是所有 f[i][j] 的最大值。
        考虑转移来源,不需要知道具体从哪个单元格转移过来,只需要知道转移来源的最大值时多少
        维护每一行的 f[i][j] 的最大值
        维护每一列的 f[i][j] 的最大值
        按照元素值的顺序从小到大计算
     */
    public int maxIncreasingCells(int[][] mat) {
        var g = new TreeMap<Integer, List<int[]>>();
        int m = mat.length, n = mat[0].length;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                // 相同元素放在同一组,统计位置
                g.computeIfAbsent(mat[i][j], k -> new ArrayList<>()).add(new int[]{i, j});

        int ans = 0;
        int[] rowMax = new int[m], colMax = new int[n];
        for (var pos : g.values()) { // 按照元素值从小到大进行遍历,顺序与矩阵每行每列的顺序无关
            var mx = new int[pos.size()];  // 先把最大值算出来,再更新 rowMax 和 colMax
            for (int i = 0; i < pos.size(); i++) {
                mx[i] = Math.max(rowMax[pos.get(i)[0]], colMax[pos.get(i)[1]]) + 1;
                ans = Math.max(ans, mx[i]);
            }
            for (int k = 0; k < pos.size(); k++) {
                int i = pos.get(k)[0], j = pos.get(k)[1];
                rowMax[i] = Math.max(rowMax[i], mx[k]); // 更新第 i 行的最大 f 值
                colMax[j] = Math.max(colMax[j], mx[k]); // 更新第 j 列的最大 f 值
            }
        }
        return ans;
    }
}

到了这里,关于周赛347(模拟、思维题、动态规划+优化)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【算法思维】-- 动态规划

    OJ须知: 一般而言,OJ在1s内能接受的算法时间复杂度:10e8 ~ 10e9之间 (中值5*10e8) 。在竞赛中, 一般认为计算机1秒能执行 5*10e8 次计算 。 时间复杂度 取值范围 o(log2n) 大的离谱 O(n) 10e8 O(nlog(n)) 10e6 O(nsqrt(n))) 10e5 O(n^2) 5000 O(n^3) 300 O(2^n) 25 O(3^n) 15 O(n!) 11 时间复杂度排序: o(1

    2024年02月05日
    浏览(38)
  • 【算法思维】-- 动态规划(C++)

    OJ须知: 一般而言,OJ在1s内能接受的算法时间复杂度:10e8 ~ 10e9之间 (中值5*10e8) 。在竞赛中, 一般认为计算机1秒能执行 5*10e8 次计算 。 时间复杂度 取值范围 o(log2n) 大的离谱 O(n) 10e8 O(nlog(n)) 10e6 O(nsqrt(n))) 10e5 O(n^2) 5000 O(n^3) 300 O(2^n) 25 O(3^n) 15 O(n!) 11 时间复杂度排序: o(1

    2024年02月02日
    浏览(50)
  • LeetCode 双周赛 104(2023/05/13)流水的动态规划,铁打的结构化思考

    本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 往期回顾:LeetCode 单周赛第 344 场 · 手写递归函数的通用套路 T1. 老人的数目(Easy) 标签:模拟、计数 T2. 矩阵中的和(Medium) 标签:模拟、排序 T3. 最大或值(Medium) 标签:动态规划、前后缀分解

    2024年02月04日
    浏览(58)
  • Leetcode 第 108 场双周赛 Problem C 将字符串分割为最少的美丽子字符串(动态规划)

    Leetcode 第 108 场双周赛 Problem C 将字符串分割为最少的美丽子字符串(动态规划) 题目 给你一个二进制字符串 s ,你需要将字符串分割成一个或者多个 子字符串 ,使每个子字符串都是 美丽 的。 如果一个字符串满足以下条件,我们称它是 美丽 的: 它不包含前导 0 。 它是

    2024年02月15日
    浏览(47)
  • AOJ 2200 Mr. Rito Post Office 最短路径+动态规划+谨慎+思维

    我写了好多注释,一看就能看懂,这个题目我想了6,7个小时,一开始忽略了船的位置和要把船安置的位置一致的情况,补上就对了。

    2024年02月14日
    浏览(35)
  • 力扣第96题 不同的二叉搜索树 c++ 二叉搜索树 动态规划 + 数学思维

    96. 不同的二叉搜索树 中等 相关标签 树   二叉搜索树   数学   动态规划   二叉树 给你一个整数  n  ,求恰由  n  个节点组成且节点值从  1  到  n  互不相同的  二叉搜索树  有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 示例 2: 提示: 1 = n = 19 vectorint

    2024年02月06日
    浏览(35)
  • 山东大学计算机科学与技术学院程序设计思维与实践作业 week14-动态规划(4)

    山东大学计算机科学与技术学院程序设计思维与实践作业 山大程序设计思维与实践作业 sdu程序设计思维与实践 山东大学程序设计思维实践作业H14 山大程序设计思维实践作业H14 山东大学程序设计思维与实践 week14-动态规划(4) 相关资料:GitHub 题目描述 给出一棵树,求树的

    2024年02月09日
    浏览(139)
  • 【动态规划】1223. 掷骰子模拟

    视频算法专题 有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。 不过我们在使用它时有个约束,就是使得投掷骰子时,连续 掷出数字 i 的次数不能超过 rollMax[i](i 从 1 开始编号)。 现在,给你一个整数数组 rollMax 和一个整数 n,请你来计算掷 n 次骰子可得到的

    2024年04月15日
    浏览(42)
  • LeetCode 双周赛 106(2023/06/10)两道思维题

    本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 加入知识星球提问。 往期回顾:LeetCode 单周赛第 348 场 · 数位 DP 模版学会了吗? T1. 判断一个数是否迷人(Easy) 标签:计数 T2. 找到最长的半重复子字符串(Medium) 标签:同向双指针 T3. 移动机器人(Medi

    2024年02月08日
    浏览(42)
  • 7.思维题(0x3f:从周赛中学算法 2022下)

    来自0x3f【从周赛中学算法 - 2022 年周赛题目总结(下篇)】:https://leetcode.cn/circle/discuss/WR1MJP/ 【【灵茶山艾府】2022 年周赛题目总结(上篇)】https://leetcode.cn/circle/discuss/G0n5iY/ 包含贪心、脑筋急转弯等,挑选一些比较有趣的题目。 注:常见于周赛第二题(约占 21%)、第三题

    2023年04月19日
    浏览(76)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包