gpt4 book ai didi

LeetCode双周赛99,纯纯送分场!

转载 作者:我是一只小鸟 更新时间:2023-03-05 22:36:09 32 4
gpt4 key购买 nike

本文已收录到 AndroidFamily ,技术和职场问题,请关注公众号 [彭旭锐] 提问.

大家好,我是小彭.

昨晚是 LeetCode 第 99 场双周赛,你参加了吗?这场周赛整体难度很低,第 4 题评论区普遍认为是 1 字头,纯纯手速场.


小彭的 Android 交流群 02 群来了,公众号回复 “加群” 加入我们~ 。


2578. 最小和分割

题目地址

https://leetcode.cn/problems/split-with-minimum-sum/ 。

题目描述

给你一个正整数  num  ,请你将它分割成两个非负整数  num1  和  num2  ,满足:

  • num1  和  num2  直接连起来,得到  num  各数位的一个排列。
    • 换句话说, num1  和  num2  中所有数字出现的次数之和等于  num  中所有数字出现的次数。
  • num1  和  num2  可以包含前导 0 。

请你返回  num1  和  num2  可以得到的和的  最小  值.

注意:

  • num  保证没有前导 0 。
  • num1  和  num2  中数位顺序可以与  num  中数位顺序不同。

题解(排序 + 贪心)

第一题相对有点思维.

  • 思考 1:越高位的数字对结果的影响越大,所以优先排列最小的数字;
  • 思考 2:如果划分两个数字的长度不均,会放大最终的值;

算法:对数字排序,从小到大分别排列到两个数字上.

                        
                          class Solution {
    fun splitNum(num: Int): Int {
        val array = "$num".toCharArray()
        array.sort()
        var num1 = 0
        var num2 = 0
        for (index in array.indices step 2) {
            num1 = num1 * 10 + (array[index] - '0')
            if (index + 1 < array.size) {
                num2 = num2 * 10 + (array[index + 1] - '0')
            }
        }
        return num1 + num2
    }
}

                        
                      

简化写法:

                        
                          class Solution {
    fun splitNum(num: Int): Int {
        val array = "$num".toCharArray().sorted()
        var nums = Array(2) { StringBuilder() }
        for (index in array.indices) {
            nums[index % 2].append(array[index])
        }
        return "${nums[0]}".toInt() + "${nums[1]}".toInt()

                        
                      

复杂度分析:

  • 时间复杂度:$O(mlgm)$ 其中 $m$ 是 $num$ 数字的位数,即 $m = lg,num$。排序时间为 $O(mlgm)$,拆分时间为 $O(m)$;
  • 空间复杂度:$O(m)$ 字符串空间为 $O(m)$,排序递归栈空间为 $O(lgm)$。

2579. 统计染色格子数

题目地址

https://leetcode.cn/problems/count-total-number-of-colored-cells/ 。

题目描述

有一个无穷大的二维网格图,一开始所有格子都未染色。给你一个正整数  n  ,表示你需要执行以下步骤  n  分钟:

  • 第一分钟,将  任一  格子染成蓝色。
  • 之后的每一分钟,将与蓝色格子相邻的  所有  未染色格子染成蓝色。

下图分别是 1、2、3 分钟后的网格图.

题解(找规律)

找规律题。这道题可以用重力加速度类比,重力加速度的 G 是 9.8m/s,而这里的 G 是 4格/s.

  • 最开始只有一格,我们先放到一边单独计算,有 $f(1) = 1$;
  • 从 (n = 1) 递推到 (n = 2) 时的速度为 4,因此 $f(2) = 4 + 1 = 5$;
  • 从 (n = 2) 递推到 (n = 3) 时的速度为 8,因此 $f(3) = 8 + f(2) = 13$;
  • 以此类推,从 (n - 1) 递推到 (n) 时的速度是 $4 *(n - 1)$,即 $f(n) = f(n - 1) + 4(n - 1)$。

显然有:

$f(n)=\begin{cases} 1, &n=1\ f(n-1) + 4(n-1) & n>1 \end{cases}$ 。

可以看到, $n > 1$ 的分支是一个从 0 开始的等差数列,等差数列求和公式知道吧,整理得:$f(n) = 1 + 4 * n * (n - 1) / 2 = 2n^2 - 2n + 1$ 。

                        
                          class Solution {
    fun coloredCells(n: Int): Long {
        return 2 * n * n - 2 * n + 1
    }
}

                        
                      

复杂度分析:

  • 时间复杂度:$O(1)$
  • 空间复杂度:$O(1)$

2580. 统计将重叠区间合并成组的方案数

题目地址

https://leetcode.cn/problems/count-ways-to-group-overlapping-ranges/ 。

题目描述

给你一个二维整数数组  ranges  ,其中  ranges[i] = [starti, endi]  表示  starti  到  endi  之间(包括二者)的所有整数都包含在第  i  个区间中.

你需要将  ranges  分成  两个  组(可以为空),满足:

  • 每个区间只属于一个组。
  • 两个有  交集  的区间必须在  同一个  组内。

如果两个区间有至少  一个  公共整数,那么这两个区间是  有交集  的.

  • 比方说,区间  [1, 3]  和  [2, 5]  有交集,因为  2  和  3  在两个区间中都被包含。

请你返回将  ranges  划分成两个组的  总方案数  。由于答案可能很大,将它对  109 + 7   取余  后返回.

题解(排序 + 贪心)

这道题我第一时间想到了这两道题:

  • 55. 跳跃游戏
  • 252:会议室

后来在评论区看到更接近的原题,好嘛,怪不得印象很深.

  • 435. 无重叠区间

脑海中有闪现过并查集,但显然没有必要.

算法:将区间看成时间段,先按照开始时间对区间排序,然后在遍历区间的同时维护已经占用的最晚结束时间 preEnd 。如果当前区间的开始时间早于 preEnd,说明区间重合。遍历完数组后求出集合个数 m,求 m 个元素放到 2 个位置的方案数,显然每个位置有 m 中可能,因此结果是 $2^m$.

                        
                          class Solution {
    fun countWays(ranges: Array<IntArray>): Int {
        val MOD = 1000000007
        Arrays.sort(ranges) { e1, e2 ->
            e1[0] - e2[0]
        }
        var m = 0
        var preEnd = -1
        for (range in ranges) {
            if (range[0] > preEnd) {
                // 无交集
                m++
            }
            preEnd = Math.max(preEnd, range[1])
        }
        return pow(2, m, MOD)
    }

    private fun pow(x: Int, n: Int, mod: Int): Int {
        var ans = 1
        for (count in 0 until n) {
            ans = (ans * x) % mod
        }
        return ans
    }
}

                        
                      

复杂度分析:

  • 时间复杂度:$O(nlgn + n + lgm)$ 其中 $n$ 是 $nums$ 数组的长度,$m$ 是无交集区间的集合个数,幂运算时间为 $O(m)$;
  • 空间复杂度:$O(lgn)$ 排序递归栈空间。

2581. 统计可能的树根数目

题目地址

https://leetcode.cn/problems/count-number-of-possible-root-nodes/ 。

题目描述

Alice 有一棵  n  个节点的树,节点编号为  0  到  n - 1  。树用一个长度为  n - 1  的二维整数数组  edges  表示,其中  edges[i] = [ai, bi]  ,表示树中节点  ai  和  bi  之间有一条边.

Alice 想要 Bob 找到这棵树的根。她允许 Bob 对这棵树进行若干次  猜测  。每一次猜测,Bob 做如下事情:

  • 选择两个  不相等  的整数  u  和  v  ,且树中必须存在边  [u, v]  。
  • Bob 猜测树中  u  是  v  的  父节点  。

Bob 的猜测用二维整数数组  guesses  表示,其中  guesses[j] = [uj, vj]  表示 Bob 猜  uj  是  vj  的父节点.

Alice 非常懒,她不想逐个回答 Bob 的猜测,只告诉 Bob 这些猜测里面  至少  有  k  个猜测的结果为  true  .

给你二维整数数组  edges  ,Bob 的所有猜测和整数  k  ,请你返回可能成为树根的  节点数目  。如果没有这样的树,则返回  0 .

题解(记忆化递归)

这是换根 DP 问题,这道题相对简单了,只要掌握图的基本结构和递归的基本思想就能实现.

首先是建图的部分,显然 edges 是无向图,guesses 是有向图。我们的算法基本框架应该是:枚举每个根节点,计算 guesses 中猜测正确的边的个数,如果猜测次数 ≥ k 则记录 1 次结果。现在的问题是如果优化查询的时间复杂度,我们观察依次从 0 到 n - 1 修改根节点会发生什么?

我们发现: 每次调整中只有条边的结构关系变化。比如从根 0 调整到根 1 时,只有 0 → 1 被修改为 1 → 0,而其他边都没有变化,存在重叠子结构 / 重叠子问题.

定义 $f(u, v)$ 表示在 u → v 的子结构中猜测正确的边数,例如在示例 2 中,f(1, 2) = 1。显然在已知 f(1,2) 的结果后,在以节点 1 为根节点的情况中不需要重复计算,达到了剪枝的目的.

编码部分有两个细节:

  • 起点需要特殊处理,我们考虑起点是用 u → v 开始的子结构,起点 u 可以采用特殊值 $n$。
  • 注意空间压缩,显然使用领接表比临接矩阵更优。备忘录可以使用移位压缩,Key = u * mod + v,由于题目数据范围是 10000,所以 mod 就取 100000。
                        
                          class Solution {
    private val graph = HashMap<Int, MutableList<Int>>()
    private val guessGraph = HashMap<Int, MutableList<Int>>()

    fun rootCount(edges: Array<IntArray>, guesses: Array<IntArray>, k: Int): Int {
        // 无向图
        for (edge in edges) {
            graph.getOrPut(edge[0]) { LinkedList<Int>() }.add(edge[1])
            graph.getOrPut(edge[1]) { LinkedList<Int>() }.add(edge[0])
        }
        // 有向图
        for (guess in guesses) {
            // 过滤不存在边(题目没有这种用例)
            if (!graph.containsKey(guess[0]) || !graph[guess[0]]!!.contains(guess[1])) continue
            guessGraph.getOrPut(guess[0]) { LinkedList<Int>() }.add(guess[1])
        }
        val n = edges.size + 1
        // 空间溢出:val memo = Array(n + 1) { IntArray(n) { -1 } }
        val memo = HashMap<Long, Int>()
        var count = 0
        // 枚举所有根
        for (root in 0 until n) {
            if (dfs(memo, 100000, n, root) >= k) count++
        }
        return count
    }

    // 记忆化递归
    private fun dfs(memo: HashMap<Long, Int>, mod: Int, u: Int, v: Int): Int {
        // 空间压缩
        val key = 1L * u * (mod) + v
        // 备忘录
        if (memo.containsKey(key)) return memo[key]!!
        var count = 0
        for (to in graph[v]!!) {
            // 过滤指向父节点的边
            if (to == u) continue
            // 检查猜测
            if (guessGraph.containsKey(v) && guessGraph[v]!!.contains(to)) count++
            // 递归
            count += dfs(memo, mod, v, to)
        }
        memo[key] = count
        return count
    }
}

                        
                      

复杂度分析:

  • 时间复杂度:$O(1)$ 其中 $n$ 是 $edges$ 数组的长度,$m$ 是 $guesses$ 数组的长度。建图占用 $O(n + m + 2 n)$,在记忆化递归下每条边的子结构最多访问 2 次,即总共有 2n 个子问题,所以查询的复杂度是 $O(2 n)$
  • 空间复杂度:$O(n + m + 2*n)$ 建图占用 $O(n + m)$,备忘录最多记录 $n$ 条边的两个方向的子结构,递归栈最大为 $n$。

就说这么多,今天单周赛加油💪🏻.

最后此篇关于LeetCode双周赛99,纯纯送分场!的文章就讲到这里了,如果你想了解更多关于LeetCode双周赛99,纯纯送分场!的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

32 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com