LeetCode周赛345（2023/05/14）体验一题多解的算法之美-6ren

LeetCode周赛345（2023/05/14）体验一题多解的算法之美

转载作者：我是一只小鸟更新时间：2023-05-15 22:31:23

27

4

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

往期回顾： LeetCode 双周赛第 104 场 · 流水的动态规划，铁打的结构化思考

周赛概览

T1. 找出转圈游戏输家（Easy）。

标签：模拟、计数

T2. 相邻值的按位异或（Medium）。

标签：模拟、数学、构造

T3. 矩阵中移动的最大次数（Medium）。

标签：图、BFS、DFS、动态规划

T4. 统计完全连通分量的数量（Medium）。

标签：图、BFS、DFS、并查集

T1. 找出转圈游戏输家（Easy）

                        
                          https://leetcode.cn/problems/find-the-losers-of-the-circular-game/

题解（模拟）

简单模拟题.

使用标记数组标记接触到球的玩家，再根据标记数组输出结果:

                        
                          class Solution {
    fun circularGameLosers(n: Int, k: Int): IntArray {
        val visit = BooleanArray(n)
        var i = 0
        var j = 1
        var cnt = n
        while (!visit[i]) {
            visit[i] = true
            i = (i + j++ * k) % n
            cnt--
        }
        val ret = IntArray(cnt)
        var k = 0
        for (i in visit.indices) {
            if(!visit[i]) ret[k++] = i + 1
        }
        return ret
    }
}

复杂度分析:

时间复杂度：$O(n)$ 每位玩家最多标记一次和检查一次；
空间复杂度：$O(n)$ 标记数组空间。

T2. 相邻值的按位异或（Medium）

                        
                          https://leetcode.cn/problems/neighboring-bitwise-xor/

预备知识

记 ⊕ 为异或运算，异或运算满足以下性质:

基本性质：x ⊕ y = 0
交换律：x ⊕ y = y ⊕ x
结合律：(x ⊕ y) ⊕ z = x ⊕ (y ⊕ z)
自反律：x ⊕ y ⊕ y = x

题解一（模拟）

由于每一位 derived[i] 可以由 original[i] ⊕ original[i + 1] 获得，我们可以令原始的 original[0] 为 0，再按顺序递推到 original[n]（循环数组），最后再检查 original[0] 和 original[n] 是否相同。如果不同，说明 derived 数组是不可构造的.

                        
                          class Solution {
    fun doesValidArrayExist(derived: IntArray): Boolean {
        var pre = 0
        for ((i,d) in derived.withIndex()) {
            if (d == 1) pre = pre xor 1
        }
        return pre == 0
    }
}

复杂度分析:

时间复杂度：$O(n)$ 其中 n 为 derived 数组的长度；
空间复杂度：仅使用常量级别空间。

题解二（数学）

继续挖掘问题的数学性质:

题目要求：$derived[i] = original[i] ⊕ original[i + 1]$
根据自反律（两边异或 original[i]）：$original[i + 1] = derived[i] ⊕ original[i]$、$original[i + 2] = derived[i + 1] ⊕ original[i + 1]$
根据递推关系有 $original[n - 1] = derived[n - 2] ⊕ derived[n - 1]… derived[0] ⊕ original[0]$
题目要求：$original[0] ⊕ original[n - 1] = derived[n-1]$
联合两式：$original[0] = original[0] ⊕ derived[n-1] ⊕ derived[n - 1]… derived[0] ⊕ original[0]$，即 $0 = derived[n-1] ⊕ derived[n - 1]… derived[0]$

根据结论公式模拟即可:

                        
                          class Solution {
    fun doesValidArrayExist(derived: IntArray): Boolean {
        // return derived.fold(0) {acc, e -> acc xor e} == 0
        return derived.reduce {acc, e -> acc xor e} == 0
    }
}

复杂度分析:

时间复杂度：$O(n)$ 其中 n 为 derived 数组的长度；
空间复杂度：仅使用常量级别空间。

T3. 矩阵中移动的最大次数（Medium）

                        
                          https://leetcode.cn/problems/maximum-number-of-moves-in-a-grid/

题目描述

给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干正整数组成.

你可以从矩阵第一列中的任一单元格出发，按以下方式遍历 grid :

从单元格 (row, col) 可以移动到 (row - 1, col + 1) 、 (row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值严格大于当前单元格的单元格。

返回你在矩阵中能够移动的最大次数.

示例 1:

                        
                          输入：grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
输出：3
解释：可以从单元格 (0, 0) 开始并且按下面的路径移动：
- (0, 0) -> (0, 1).
- (0, 1) -> (1, 2).
- (1, 2) -> (2, 3).
可以证明这是能够移动的最大次数。

示例 2:

                        
                          输入：grid = [[3,2,4],[2,1,9],[1,1,7]]
输出：0
解释：从第一列的任一单元格开始都无法移动。

提示:

m == grid.length
n == grid[i].length
2 <= m, n <= 1000
4 <= m * n <= 105
1 <= grid[i][j] <= 106

问题结构化

1、概括问题目标。

计算可移动的最大次数，也可以理解为可访问距离 - 1.

2、分析问题要件。

在每次移动操作中，可以移动到右边一列的最近三行位置（i-1, i, j+1）且要求数字严格大于当前位置.

3、提高抽象程度。

子问题：我们发现每次移动后，可移动次数就是在新位置可移动次数 + 1，这是一个与原问题相似但规模更小的子问题；
是否为决策问题？由于每次移动最多有三个位置选择，因此这是决策问题。

4、具体化解决手段。

手段 1（记忆化递归）：定义 dfs(i, j) 表示从 grid[i][j] 开始的最大移动次数，那么有 dfs(i, j)= mas{dfs(i-1, j+1), dfs(i, j+1), dfs(i+1, j+1)}；
手段 2（递推）：在记忆化递归中我们是在「归」的过程中合并子问题的解，由于递归的方向是验证矩阵从上到下，从左到右的，我们可以消除「递」的过程而只保留「归」的过程，将递归转换为递推；
手段 3（BFS）：由于可移动次数取决于最多可以移动到的列号，我们可以用 BFS / DFS 搜索最远可以访问的列号。

题解一（记忆化递归）

根据「手段 1」模拟即可:

递归函数：dfs(i, j)= mas
起始状态：dfs(i, 0)
边界条件：dfs(i, j) = 0

                        
                          class Solution {

    val directions = arrayOf(intArrayOf(-1, 1), intArrayOf(0, 1), intArrayOf(1, 1)) // 右上、右、右下

    private val memo = HashMap<Int, Int>()
    private val U = 1001

    fun maxMoves(grid: Array<IntArray>): Int {
        var ret = 0
        for (i in 0 until grid.size) {
            ret = Math.max(ret, dfs(grid, i, 0))
        }
        return ret - 1
    }

    private fun dfs(grid: Array<IntArray>, i: Int, j: Int): Int {
        val n = grid.size
        val m = grid[0].size
        val key = i * U + j
        if (memo.contains(key)) return memo[key]!!
        // 枚举选项
        var maxChoice = 0
        for (direction in directions) {
            val newI = i + direction[0]
            val newJ = j + direction[1]
            if (newI < 0 || newI >= n || newJ < 0 || newJ >= m || grid[i][j] >= grid[newI][newJ]) continue
            maxChoice = Math.max(maxChoice, dfs(grid, newI, newJ))
        }
        memo[key] = maxChoice + 1
        return maxChoice + 1
    }
}

复杂度分析:

时间复杂度：$O(nm)$ 总共有 nm 个子问题，每个子问题枚举 3 个选项时间复杂度是 O(1)；
空间复杂度：$O(nm)$ 备忘录空间。

题解二（递推）

消除「递」的过程而只保留「归」的过程，将递归转换为递推:

                        
                          class Solution {
    fun maxMoves(grid: Array<IntArray>): Int {
        val n = grid.size
        val m = grid[0].size
        val step = Array(n) { IntArray(m) }
        for (i in 0 until n) step[i][0] = 1
        var ret = 0
        // 按列遍历
        for(j in 1 until m) {
            for(i in 0 until n) {
                for(k in Math.max(0, i - 1) .. Math.min(n - 1,i + 1)) {
                    if (step[k][j - 1] > 0 && grid[i][j] > grid[k][j - 1]) step[i][j] = Math.max(step[i][j], step[k][j - 1] + 1)
                }
                ret = Math.max(ret, step[i][j])
            }
        }
        return Math.max(ret - 1, 0)
    }
}

另外，我们也可以用滚动数组优化空间:

                        
                          class Solution {
    fun maxMoves(grid: Array<IntArray>): Int {
        val n = grid.size
        val m = grid[0].size
        var step = IntArray(n) { 1 }
        var ret = 0
        // 按列遍历
        for(j in 1 until m) {
            val newStep = IntArray(n) { 0 } // 不能直接在 step 数组上修改
            for(i in 0 until n) {
                for(k in Math.max(0, i - 1) .. Math.min(n - 1,i + 1)) {
                    if (step[k] > 0 && grid[i][j] > grid[k][j - 1]) newStep[i] = Math.max(newStep[i], step[k] + 1)
                }
                ret = Math.max(ret, newStep[i])
            }
            step = newStep
        }
        return Math.max(ret - 1, 0)
    }
}

复杂度分析:

时间复杂度：$O(nm)$
空间复杂度：$O(n)$

题解三（BFS）

按照广度优先搜索，使用队列维护可以访问的节点，再使用该节点探测下一层可到达的位置并入队.

                        
                          class Solution {
    fun maxMoves(grid: Array<IntArray>): Int {
        val n = grid.size
        val m = grid[0].size
        // 行号
        var queue = LinkedList<Int>()
        for (i in 0 until n) {
            queue.offer(i)
        }
        // 访问标记
        val visit = IntArray(n) { -1 }
        // 枚举列
        for (j in 0 until m - 1) {
            val newQueue = LinkedList<Int>() // 不能直接在 step 数组上修改
            for (i in queue) {
                for (k in Math.max(0, i - 1)..Math.min(n - 1, i + 1)) {
                    if (visit[k] < j && grid[k][j + 1] > grid[i][j]) {
                        newQueue.offer(k)
                        visit[k] = j
                    }
                }
            }
            queue = newQueue
            if (queue.isEmpty()) return j
        }
        return m - 1
    }
}

复杂度分析:

时间复杂度：$O(nm)$
空间复杂度：$O(n)$

相似问题:

62. 不同路径
63. 不同路径 II

T4. 统计完全连通分量的数量（Medium）

                        
                          https://leetcode.cn/problems/count-the-number-of-complete-components/

问题描述

给你一个整数 n 。现有一个包含 n 个顶点的无向图，顶点按从 0 到 n - 1 编号。给你一个二维整数数组 edges 其中 edges[i] = [ai, bi] 表示顶点 ai 和 bi 之间存在一条无向边.

返回图中完全连通分量的数量.

如果在子图中任意两个顶点之间都存在路径，并且子图中没有任何一个顶点与子图外部的顶点共享边，则称其为连通分量 .

如果连通分量中每对节点之间都存在一条边，则称其为完全连通分量 .

示例 1:

                        
                          输入：n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]
输出：3
解释：如上图所示，可以看到此图所有分量都是完全连通分量。

示例 2:

                        
                          输入：n = 6, edges = [[0,1],[0,2],[1,2],[3,4],[3,5]]
输出：1
解释：包含节点 0、1 和 2 的分量是完全连通分量，因为每对节点之间都存在一条边。
包含节点 3 、4 和 5 的分量不是完全连通分量，因为节点 4 和 5 之间不存在边。
因此，在图中完全连接分量的数量是 1 。

提示:

1 <= n <= 50
0 <= edges.length <= n * (n - 1) / 2
edges[i].length == 2
0 <= ai, bi <= n - 1
ai != bi
不存在重复的边

预备知识 - 完全图

完全图中每对不同的顶点之间都恰连有一条边相连，n 个节点的完全图有 n*(n − 1) / 2 条边.

问题分析

这道题是比较直接的岛屿 / 连通分量问题，我们直接跑 DFS / BFS / 并查集，计算每个连通分量的节点数和边数是否平衡.

如果连通分量是完全图，那么节点数 v 和边数 e 满足 e == v * (v - 2) / 2 。

题解一（DFS）

枚举每个节点跑 DFS，统计相同连通分量的节点数 v 和节点数 e，由于在遍历的时候，同一条边会在两个节点上重复统计，所以判断连通分量是否为完全图的公式调整为 e == v * (v - 2).

                        
                          class Solution {
    fun countCompleteComponents(n: Int, edges: Array<IntArray>): Int {
        // 建图（邻接表）
        val graph = Array(n) { mutableListOf<Int>() }
        for (edge in edges) {
            graph[edge[0]].add(edge[1])
            graph[edge[1]].add(edge[0]) // 无向边
        }
        // 标记数组
        val visit = BooleanArray(n)
        // 枚举
        var ret = 0
        for (i in 0 until n) {
            if (visit[i]) continue
            val cnt = IntArray(2) // v, e
            dfs(graph, visit, i, cnt)
            if (cnt[1] == cnt[0] * (cnt[0] - 1)) ret++
        }
        return ret
    }

    private fun dfs(graph: Array<out List<Int>>, visit: BooleanArray, i: Int, cnt: IntArray) {
        visit[i] = true
        cnt[0] += 1 // 增加节点
        cnt[1] += graph[i].size // 增加边（会统计两次）
        for (to in graph[i]) {
            if (!visit[to]) dfs(graph, visit, to, cnt)
        }
    }
}

复杂度分析:

时间复杂度：$O(n + m)$ 其中 n 为节点数，m 为 edges 的长度；
空间复杂度：图空间 $O(m)$，标记数组空间 $O(n)$。

题解二（BFS）

附赠一份 BFS 代码:

                        
                          class Solution {
    fun countCompleteComponents(n: Int, edges: Array<IntArray>): Int {
        // 建图（邻接表）
        val graph = Array(n) { mutableListOf<Int>() }
        for (edge in edges) {
            graph[edge[0]].add(edge[1])
            graph[edge[1]].add(edge[0]) // 无向边
        }
        // 标记数组
        val visit = BooleanArray(n)
        // 枚举
        var ret = 0
        for (i in 0 until n) {
            if (visit[i]) continue
            var v = 0
            var e = 0
            // BFS
            var queue = LinkedList<Int>()
            queue.offer(i)
            visit[i] = true
            while (!queue.isEmpty()) {
                val temp = queue
                queue = LinkedList<Int>()
                for (j in temp) {
                    v += 1 // 增加节点
                    e += graph[j].size // 增加边（会统计两次）
                    for (to in graph[j]) {
                        if (!visit[to]) {
                            queue.offer(to)
                            visit[to] = true
                        }
                    }
                }
            }
            if (e == v * (v - 1)) ret++
        }
        return ret
    }
}

复杂度分析:

时间复杂度：$O(n + m)$ 其中 n 为节点数，m 为 edges 的长度；
空间复杂度：图空间、标记数组空间和队列空间。

题解三（并查集）

附赠一份并查集代码:

                        
                          class Solution {

    fun countCompleteComponents(n: Int, edges: Array<IntArray>): Int {
        val uf = UnionFind(n)
        for (edge in edges) {
            uf.union(edge[0], edge[1])
        }
        return uf.count()
    }

    private class UnionFind(n: Int) {
        private val parent = IntArray(n) { it }
        private val rank = IntArray(n)
        private val e = IntArray(n)
        private val v = IntArray(n) { 1 }

        fun find(x: Int): Int {
            // 路径压缩
            var a = x
            while (parent[a] != a) {
                parent[a] = parent[parent[a]]
                a = parent[a]
            }
            return a
        }

        fun union(x: Int, y: Int) {
            val rootX = find(x)
            val rootY = find(y)
            if (rootX == rootY) {
                e[rootX]++
            } else {
                // 按秩合并
                if (rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY
                    e[rootY] += e[rootX] + 1 // 增加边
                    v[rootY] += v[rootX] // 增加节点
                } else if (rank[rootY] > rank[rootX]) {
                    parent[rootY] = rootX
                    e[rootX] += e[rootY] + 1
                    v[rootX] += v[rootY]
                } else {
                    parent[rootY] = rootX
                    e[rootX] += e[rootY] + 1
                    v[rootX] += v[rootY]
                    rank[rootX]++
                }
            }
        }

        // 统计连通分量
        fun count(): Int {
            return parent.indices.count { parent[it] == it && v[it] * (v[it] - 1) / 2 == e[it] }
        }
    }
}

复杂度分析:

时间复杂度：$O(n + am)$ 其中 n 为节点数，m 为 edges 的长度，其中 $a$ 为反阿克曼函数。
空间复杂度：$O(n)$ 并查集空间。

往期回顾

LeetCode 单周赛第 344 场 · 手写递归函数的通用套路
LeetCode 单周赛第 343 场 · 结合「下一个排列」的贪心构造问题
LeetCode 双周赛第 104 场 · 流水的动态规划，铁打的结构化思考
LeetCode 双周赛第 103 场 · 区间求和的树状数组经典应用

最后此篇关于LeetCode周赛345（2023/05/14）体验一题多解的算法之美的文章就讲到这里了,如果你想了解更多关于LeetCode周赛345（2023/05/14）体验一题多解的算法之美的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！。

27

4

0

文章推荐：

Python数据类型大盘点

文章推荐： Spring源码：Bean生命周期（四）

文章推荐：【深入浅出Yarn架构与实现】6-4Container生命周期源码分析

文章推荐： SICP：元循环求值器（Python实现）

算法~利用zset实现滑动窗口限流
滑动窗口限流滑动窗口限流是一种常用的限流算法，通过维护一个固定大小的窗口，在单位时间内允许通过的请求次数不超过设定的阈值。具体来说，滑动窗口限流算法通常包括以下几个步骤：初始化：设置窗口
【算法】表达式求值
表达式求值：一个只有+,-,*,/的表达式，没有括号一种神奇的做法：使用数组存储数字和运算符，先把优先级别高的乘法和除法计算出来，再计算加法和减法 int GetVal(string s){
【算法】前缀和
【算法】前缀和题目先来看一道题目：（前缀和模板题）已知一个数组A[]，现在想要求出其中一些数字的和。输入格式：先是整数N,M，表示一共有N个数字，有M组询问接下来有N个数，表示A[1]..
【算法】二叉树的各种遍历方式
1.前序遍历根-左-右的顺序遍历，可以使用递归 void preOrder(Node *u){ if(u==NULL)return; printf("%d ",u->val);
【算法】01背包
先看题目物品不能分隔，必须全部取走或者留下，因此称为01背包（只有不取和取两种状态）看第一个样例我们需要把4个物品装入一个容量为10的背包我们可以简化问题，从小到大入手分析 weightva
算法 - 矩阵中被另一种颜色包围的颜色
我最近在一次采访中遇到了这个问题: 给出以下矩阵: [[ R R R R R R], [ R B B B R R], [ B R R R B B], [ R B R R R R]] 找出是否有任
使用Outlook发送电子邮件的C++算法
我正在尝试通过 C++ 算法从我的 outlook 帐户发送一封电子邮件，该帐户已经打开并记录，但真的不知道从哪里开始(对于 outlook-c++ 集成)，谷歌也没有帮我这么多。任何提示将不胜感激。
容器上滑动窗口的C++算法
我发现自己像这样编写了一个手工制作的 while 循环: std::list foo; // In my case, map, but list is simpler auto currentPoin
检测正方形后运行命令的c++算法
我有用于检测正方形的 opencv 代码。现在我想在检测正方形后，代码运行另一个命令。代码如下: #include "cv.h" #include "cxcore.h" #include "high
二值图像的泛洪填充C++算法
我正在尝试模拟一个 matlab 函数“imfill”来填充二进制图像(1 和 0 的二维矩阵)。我想在矩阵中指定一个起点，并像 imfill 的 4 连接版本那样进行洪水填充。这是否已经存在于
算法递归公式
我正在阅读 Robert Sedgewick 的《C++ 算法》。 Basic recurrences section it was mentioned as 这种循环出现在循环输入以消除一个项目的递
算法 - 如何生成日期结构？
我正在思考如何在我的日历中生成代表任务的数据结构(仅供我个人使用)。我有来自 DBMS 的按日期排序的任务记录，如下所示: 买牛奶(18.1.2013) 任务日期 (2013-01-15) 任务标签(
算法:查找恰好出现两次的元素
输入一个未排序的整数数组A[1..n]只有 O(d) :(d int) 计算每个元素在单次迭代中出现在列表中的次数。 map 是balanced Binary Search Tree基于确保 O(nl
算法——基于寻找最大匹配数
我遇到了一个问题，但我仍然不知道如何解决。我想出了如何用蛮力的方式来做到这一点，但是当有成千上万的元素时它就不起作用了。 Problem: Say you are given the followin
算法 - 用于计算成对相互出现的次数
我有一个列表列表。 L1= [[...][...][.......].......]如果我在展平列表后获取所有元素并从中提取唯一值，那么我会得到一个列表 L2。我有另一个列表 L3，它是 L2 的某个
算法 - 在矩阵中求和
我们得到二维矩阵数组(假设长度为 i 和宽度为 j)和整数 k我们必须找到包含这个或更大总和的最小矩形的大小F.e k=7 4 1 1 1 1 1 4 4 Anwser是2，因为4+4=8 >= 7，
算法:根据周数获取下一年日期工作类次类型
我实行 3 类倒制，每周换类。顺序为早类 (m)、晚类 (n) 和下午类 (a)。我固定的订单，即它永远不会改变，即使那个星期不工作也是如此。我创建了一个函数来获取 ISO 周数。当我给它一个日期时
算法 - 找到满足输入元素任意组合的所有集合
假设我们有一个输入，它是一个元素列表: {a, b, c, d, e, f} 还有不同的集合，可能包含这些元素的任意组合，也可能包含不在输入列表中的其他元素: A:{e,f} B:{d,f,a} C:
算法:添加新元素时如何找到集合的子集？
我有一个子集算法，可以找到给定集合的所有子集。原始集合的问题在于它是一个不断增长的集合，如果向其中添加元素，我需要再次重新计算它的子集。有没有一种方法可以优化子集算法，该算法可以从最后一个计算点重新
算法:按预期频率将符号压缩成位串？
我有一个包含 100 万个符号及其预期频率的表格。我想通过为每个符号分配一个唯一(且前缀唯一)的可变长度位串来压缩这些符号的序列，然后将它们连接在一起以表示序列。我想分配这些位串，以使编码序列的预

首页

博学

6Ren·AI

商城