首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >LeetCode 周赛上分之旅 #43 计算机科学本质上是数学吗?

LeetCode 周赛上分之旅 #43 计算机科学本质上是数学吗?

作者头像
用户9995743
发布于 2023-09-09 06:15:02
发布于 2023-09-09 06:15:02
32200
代码可运行
举报
文章被收录于专栏:彭旭锐彭旭锐
运行总次数:0
代码可运行

T1. 判断通过操作能否让字符串相等 I(Easy)

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
https://leetcode.cn/problems/check-if-strings-can-be-made-equal-with-operations-i/

题解(模拟)

因为只能交换距离偶数倍的位置,因此相当于比较两个字符串相同奇偶性下标上的元素是否相等。

  • 写法 1:基于散列表
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    fun canBeEqual(s1: String, s2: String): Boolean {
        return setOf(s1[0], s1[2]) == setOf(s2[0], s2[2]) && setOf(s1[1], s1[3]) == setOf(s2[1], s2[3])
    }
}
  • 写法 2:基于字符串
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def checkStrings(self, s1: str, s2: str) -> bool:
        return sorted(s1[0::2]) == sorted(s2[0::2]) and sorted(s1[1::2]) == sorted(s2[1::2])

复杂度分析:

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

T2. 判断通过操作能否让字符串相等 II(Medium)

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
https://leetcode.cn/problems/check-if-strings-can-be-made-equal-with-operations-ii/

题解(模拟)

同上,分别统计奇偶下标上的元素个数是否相等。

写法 1:基于计数;

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    fun checkStrings(s1: String, s2: String): Boolean {
        val U = 26
        val cnts = Array(2) { IntArray(U) }
        for ((i, e) in s1.withIndex()) {
            cnts[i % 2][e - 'a']++
        }
        for ((i, e) in s2.withIndex()) {
            cnts[i % 2][e - 'a']--
        }
        return cnts[0].all {it == 0} && cnts[1].all {it == 0}
    }
}

复杂度分析:

  • 时间复杂度:
O(n + U)

线性遍历时间与计数时间;

  • 空间复杂度:
O(U)

计数数组空间。

写法 2:基于字符串:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def checkStrings(self, s: str, t: str) -> bool:
        return all(sorted(s[p::2]) == sorted(t[p::2]) for p in range(2))

复杂度分析:

  • 时间复杂度:
O(nlgn)

排序时间;

  • 空间复杂度:
O(n)

构造字符串空间。


T3. 几乎唯一子数组的最大和(Medium)

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
https://leetcode.cn/problems/maximum-sum-of-almost-unique-subarray/

题解(滑动窗口 + 计数)

滑动窗口模板题,维护窗口中不同元素的种类数和总和:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    fun maxSum(nums: List<Int>, m: Int, k: Int): Long {
        var cnts = HashMap<Int, Int>()
        var type = 0
        var sum = 0L
        var ret = 0L
        for (j in nums.indices) {
            // 滑入
            cnts[nums[j]] = cnts.getOrDefault(nums[j], 0) + 1
            if (1 == cnts[nums[j]]!!) type++
            sum += nums[j]
            // 滑出
            if (j >= k) {
                val i = j - k
                cnts[nums[i]] = cnts[nums[i]]!! - 1
                if (0 == cnts[nums[i]]) type --
                sum -= nums[i]
            }
            // 记录
            if (j >= k - 1 && type >= m) {
                ret = max(ret, sum)
            }
        }
        return ret
    }
}

复杂度分析:

  • 时间复杂度:
O(n)

线性遍历时间;

  • 空间复杂度:
O(n)

散列表空间。


T4. 统计一个字符串的 k 子序列美丽值最大的数目(Hard)

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
https://leetcode.cn/problems/count-k-subsequences-of-a-string-with-maximum-beauty/

问题分析

  • 问题目标: 求所有长为
k

的子序列中美丽值是最大值的子序列数目;

  • 问题要件: 先计算长为
k

的子序列的最大美丽值,再计算满足美丽值是最大值的子序列方案数;

  • 关键信息 1: 子序列要选择不重复的字母;
  • 关键信息 2: 同一个字符在原字符串中的不同位置可以构造不同子序列;
  • 核心变量:
f(c)

是 字符

c

的出现次数,美丽值是子序列中字符的

f(c)

之和;

  • 边界情况: 既然子序列要选择不重复的字母,那么存在边界情况,当
k

> 字符串的字符种类数:那么一定不能构造

k

子序列,返回

0

题解一(暴力枚举 + 乘法原理)

最简单的做法,我们可以枚举所有可能的

k

子序列,并记录出现最大美丽值的方案数,怎么实现呢?

  • 方法 1 - 考虑到子序列需要保留原字符串的顺序,直接的想法是枚举字符串中的每个下标
s[i]

选和不选,但是时间复杂度是

O(2^n)

显然不成立;

  • 方法 2 - 事实上我们不需要从原字符串的角度枚举,而是可以从字符集的角度枚举,那样时间复杂度就可以用乘法原理来优化。比如说 a 的出现次数是
2

,而 b 的出现次数是

3

,那么所有 ab 可以构造的子序列方案数就是 2 * 3 = 6

那么,方法会不会超时呢,我们来简单分析下:

由于字符集的大小

U

最多只有

26

个,那么子序列的方案数最多有

C_{26}^k

个,而由于

k

大于

U

的方案是不存在的,因此合法的方案数最多只有

C_{U}^{\frac{U}{2}} = C_{26}^{13} = 10400600

约等于

10^7

。只要我们保证求解每个子问题的时间复杂度是

O(1)

的话是可以通过的。

枚举实现:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    fun countKSubsequencesWithMaxBeauty(s: String, k: Int): Int {
        val MOD = 1000000007
        // 计数
        val cnts = HashMap<Char, Int>()
        for (e in s) {
            cnts[e] = cnts.getOrDefault(e, 0) + 1
        }
        val m = cnts.size
        if (m < k) return 0 // 特判
        // 枚举子序列
        val keys = cnts.toList()
        var maxCount = 0L
        var maxF = 0
        // 回溯
        fun count(index: Int, size: Int, curF: Int, curCount: Long) {
            // 终止条件
            if (size == k) {                
                if (curF > maxF) {
                    maxF = curF
                    maxCount = curCount // 更新最大美丽值方案数
                } else if (curF == maxF) {
                    maxCount = (maxCount + curCount) % MOD // 增加方案数
                }
                return
            }
            if (size + m - index < k) return // 剪枝(长度不够)
            for (i in index until m) {
                val (c, cnt) = keys[i]
                count(i + 1, size + 1, curF + cnt, curCount * cnt % MOD /* 乘法原理 */) 
            }
        }
        count(0, 0, 0, 1)
        return maxCount.toInt()
    }
}

复杂度分析:

  • 时间复杂度:
O(C_m^k)

其中

m

为字符种类 ;

  • 空间复杂度:
O(m)

散列表空间与递归栈空间。

题解二(排序 + 贪心 + 乘法原理)

考虑

k = 1

的边界情况:

显然需要选择

f(c)

值最大的

1

个字母,如果存在

m

个字母的

f(c)

等于最大值,那么存在

C_m^1 = m

种方案。这说明我们没必要枚举所有字母的子序列: 由于子序列中的字符是不重复的,因此

k

子序列必然要选择

f(c)

值最大的

k

个字母,我们可以将字母按照

f(c)

倒序排序,优先取

f(c)

更大的字母。

具体实现上:

我们将字母按照

f(c)

分桶排序,如果桶内字母数量

K

小于等于

k

,那么桶内元素都需要选择,否则还要计算桶内元素选择

k

个的方案数:

  • 选择桶内所有元素,方案数为
cnt^K
  • 选择桶内部分元素,方案数为
C_K^k · cnt^k

其中涉及到幂运算,本质是倍增思想:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
// 快速幂 x^n
private fun powM(a: Int, b: Int, mod: Int) : Long {
    var x = a.toLong()
    var n = b.toLong()
    var ret = 1L
    while (n > 0L) {
        if (n % 2 == 1L) ret = ret * x % mod
        x = x * x % mod
        n /= 2
    }
    return ret
}

其中涉及到 组合数:

  • 计算式:
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
// 组合数计算公式 O(k)
private fun comb(n: Int, k: Int, mod: Int) : Int {
    var ret = 1L
    for (i in 1 .. k) {
        ret = ret * (n - i + 1) / i % mod
    }
    return ret.toInt()
}
  • 递推式(杨辉三角):
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
// 递归 O(n^2)
private fun comb(n: Int, k: Int, mod: Int) : Int {
    if (n == k) {
        return 1
    } else if (k == 1) {
        return n
    } else {
        return (comb(n - 1, k - 1, mod) + comb(n - 1, k, mod)) % mod
    }
}

// 迭代 O(n^2)
private fun comb(n: Int, k: Int, mod: Int) : Int {
    val c = Array(n + 1) { IntArray(n + 1) }
    for (i in 1 .. n) {
        c[i][0] = 1
        c[i][i] = 1
        for (j in 1 until i) {
            c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod
        }
    }
    return c[n][k]
}
  • 卢卡斯定理: 当问题规模很大,且模不太大时使用 Lucas 定理。
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
// 组合数计算公式
private fun comb(n: Long, k: Long, mod: Int) : Int {
    var n = n
    var ret = 1L
    for (i in 1 .. k) {
        ret = ret * n-- / i % mod
    }
    return ret.toInt()
}

// 卢卡斯定理
fun Lucas(n: Long, k: Long, mod: Int) : Long {
    if (k == 0L) return 1L;
    return (comb(n % mod, k % mod, mod) * Lucas(n / mod, k / mod, mod)) % mod;
}

完整代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    fun countKSubsequencesWithMaxBeauty(s: String, k: Int): Int {
        val MOD = 1000000007
        // 计数
        val cnts = HashMap<Char, Int>()
        var maxCnt = 0
        for (e in s) {
            cnts[e] = cnts.getOrDefault(e, 0) + 1
            maxCnt = max(maxCnt, cnts[e]!!)
        }
        val m = cnts.size
        if (m < k) return 0 // 特判
        // 有序集合
        val map = TreeMap<Int, Int>() { c1, c2 -> 
            c2 - c1
        }
        // 二次频率
        for ((_, c) in cnts) {
            map[c] = map.getOrDefault(c, 0) + 1
        }
        val cntCnts = map.toList()
        // println(cntCnts.joinToString())
        // 构造方案
        var ret = 1L
        var leftK = k
        for ((cnt, K) in cntCnts) {
            if (K > leftK) {
                ret = ret * powM(cnt, leftK, MOD) * comb(K, leftK, MOD) % MOD
            } else {
                ret = ret * powM(cnt, K, MOD) % MOD
            }
            leftK -= K
            if (leftK <= 0) break
        }
        return ret.toInt()
    }

    // 组合数计算公式 C_n^k
    private fun comb(n: Int, k: Int, mod: Int) : Int {
        if (n == k) {
            return 1
        } else if (k == 1) {
            return n
        } else {
            return (comb(n - 1, k - 1, mod) + comb(n - 1, k, mod)) % mod
        }
    }

    // 快速幂 x^n
    private fun powM(x_: Int, n_: Int, mod: Int) : Long {
        var x = x_.toLong()
        var n = n_.toLong()
        var ret = 1L
        while (n > 0L) {
            if (n % 2 == 1L) ret = ret * x % mod
            x = x * x % mod
            n /= 2
        }
        return ret
    }
}

Python 中组合数和幂运算可以很方便地使用库函数:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:
        MOD = 10 ** 9 + 7
        ans = 1
        cnt = Counter(Counter(s).values())
        for c, num in sorted(cnt.items(), reverse=True): # 二次计数
            if num >= k:
                return ans * pow(c, k, MOD) * comb(num, k) % MOD
            ans *= pow(c, num, MOD)
            k -= num
        return 0

复杂度分析:

  • 时间复杂度:
O(n + m)

主要时间在枚举字符串的环节;

  • 空间复杂度:
O(m)

散列表空间。


本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2023-09-04,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 彭旭锐 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
slave have equal MySQL server UUIDs
    最近在部署MySQL主从复制架构的时候,碰到了"Last_IO_Error: Fatal error: The slave I/O thread stops because master and slave have equal MySQL server UUIDs;  these UUIDs must be different for replication to work." 这个错误提示。即主从架构中使用了相同的UUID。检查server_id系统变量,已经是不同的设置,那原因是?接下来为具体描述。 
Leshami
2018/08/13
8330
关于 MySQL GTID 复制
MySQL5.7以后都基本用GTID方式复制了,相对于binlog和position号方式,在failover时候减少很多人工切换操作
星哥玩云
2022/08/18
4760
Mysql主从同步报错解决:Fatal error: The slave I/O thread stops because ..
在搭建Mysql主从架构过程中,由于从服务器是克隆的主服务器系统,导致主从Mysql uuid相同, Slave_IO无法启动,报错如下: Last_IO_Error: Fatal error: The slave I/O thread stops because master and slave have equal MySQL server UUIDs; these UUIDs must be different for replication to work.
非著名运维
2022/06/22
2.6K0
Mysql主从同步报错解决:Fatal error: The slave I/O thread stops because ..
使用Innobackupex快速搭建(修复)MySQL主从架构
    MySQL的主从搭建大家有很多种方式,传统的mysqldump方式是很多人的选择之一。但对于较大的数据库则该方式并非理想的选择。使用Xtrabackup可以快速轻松的构建或修复mysql主从架构。本文描述了使用innobackupex快速来搭建或修复主从架构。供大家参考。
Leshami
2018/08/13
6310
Linux 环境搭建 MySQL8.0.28 主从同步环境
首先在介绍MySQL 主从时,我们来看看 DB-Engines 排行榜上四月数据库的变化,前三甲居然都有小幅度增长,相反增长迅猛的 PG 和 MongoDB 有所减少,一个月的增长趋势说明不了问题,下图是从 13 年开始的趋势图,Oracle 和 MySQL 渐渐趋平,学习了解 MySQL 还是很有必要的。下面开始进入正题。
JiekeXu之路
2022/05/17
1.1K0
Linux 环境搭建 MySQL8.0.28 主从同步环境
CentOS 7.2下MySQL主从复制配置
MySQL的 Replication 是一个异步的复制过程(mysql5.1.7以上版本分为异步复制和半同步两种模式),从一个 Mysql instace(我们称之为 Master)复制到另一个 Mysql instance(我们称之 Slave)。在 Master 与 Slave 之间的实现整个复制过程主要由三个线程来完成,其中两个线程(Sql线程和IO线程)在 Slave 端,另外一个线程(IO线程)在 Master 端。
星哥玩云
2022/08/17
5310
技术分享 | mysqlreplicate 源码分析
1.内置了innodb引擎或者使用了innodb引擎的插件,即为数据库必须有innodb引擎存在
爱可生开源社区
2022/08/23
5710
MySQL基于GTIDs的MySQL Replication
1、GTIDs(Global transaction identifiers)全局事务标识符,是mysql 5.6新加入的一项技术
星哥玩云
2022/08/18
4310
有深度有温度的MySQL主从搭建教程
MySQL 主从搭建一直是以一个很有意思的话题,搭好了很有成就感。松哥之前还专门录过视频教大家搭建 MySQL 主从,一起来回顾下:
江南一点雨
2021/04/22
6370
深入理解MySQL 5.7 GTID系列(二):GTID相关内部数据结构
前一部分是SERVER_UUID,后面一部分是执行事务的唯一标志,通常是自增的。内部使用 GTID这种数据结构表示,后面会描述。
阿炳数记
2019/02/27
1.2K0
深入理解MySQL 5.7 GTID系列(二):GTID相关内部数据结构
10. 选主算法、多版本兼容性及滚动升级 | 深入浅出MGR
本文介绍MGR的选主算法,以及当MGR集群中有多个不同版本混搭时,如何才能正常运行,有什么注意事项。
GreatSQL社区
2022/03/30
5250
MySQL之GTID
GTID,全称Global transaction identifiers,也称之为全局事务ID。MySQL-5.6.2开始支持,MySQL-5.6.10后完善,GTID 分成两部分,一部分是服务的UUid,UUID保存在mysql数据目录的auto.cnf文件中, 这是一个非常重要的文件,不能删除,这一部分是不会变的。下面是一个uuid的值举例:
AsiaYe
2019/11/06
1.2K0
MySQL之GTID
故障案例:主从同步报错Fatal error: The slave I/O thread stops because master and slave have equal MySQL server
场景一:因为数据量非常,大概有1.4T,需要在原先master1-slave1的情况下再创建一个库slave2,并且挂在slave1下,即master1-slave1-slave2的结构。为了方便,当时停掉从库salve1,show master status记录状态,开启log_slave_updates,并且关闭salve1,然后将这个从库的data文件夹直接copy到新的从库,结果在创建slave2和slave1的主从关系时报错
拓荒者
2019/03/11
5K0
安装MySQL Enterprise Monitor
    MySQL Enterprise Monitor是专门为MySQL数据库而设计的一款企业级监控,能非常好地与MySQL各方面特性相结合,包括:MySQL的关键性能指标、主机、磁盘、备份、新特性相关以及各种场景下的架构配置,并支持从单节点到海量节点部署的环境。它不仅能够全面地监控MySQL的运行状态,还能及时发现潜在的问题并给出优化建议。本文描述了MySQL Enterprise Monitor的安装过程。
Leshami
2018/08/13
1.4K0
安装MySQL Enterprise Monitor
【DB宝45】MySQL高可用之MGR+Consul架构部署
基于目前存在很多MySQL数据库单点故障,传统的MHA,PXC等方案用VIP或者DNS切换的方式可以实现、基于数据库的数据强一致性考虑,采用MGR集群,采用consul服务注册发现实现应用端通过动态DNS 访问MGR集群,实现数据库高可用,自动化切换的方案。
AiDBA宝典
2021/03/29
1.3K0
【DB宝45】MySQL高可用之MGR+Consul架构部署
MyCat分库分表实时同步到GreatSQL
MyCat作为经典的分库分表中间件,在长时间内被广泛认为是管理超大MySQL数据库集合的有效解决方案。近来接到客户需求,需要将MyCat集群迁移到GreatSQL中,并且在一段时间内需要实时从MyCat中同步数据到GreatSQL中,全量同步数据比较容易操作,增量同步有如下两个棘手的问题:
GreatSQL社区
2024/01/10
1880
MyCat分库分表实时同步到GreatSQL
【DB宝35】使用MySQL 8.0 克隆(clone)插件快速添加MGR节点
MySQL 8.0.17的克隆插件允许在本地或从远程 MySQL 实例在线克隆数据,从此搭建从库可以不再需要备份工具(PXB或mysqldump)来实现了。克隆数据是存储在 InnoDB 其中的数据的物理快照,其中包括库、表、表空间和数据字典元数据。克隆的数据包含一个功能齐全的数据目录,允许使用克隆插件进行 MySQL 服务器配置。
AiDBA宝典
2021/01/07
2.1K0
【DB宝35】使用MySQL 8.0 克隆(clone)插件快速添加MGR节点
MySQL高可用方案MGR+consul组合测试
今天来简单理一下MGR和consul的组合方案,前期的准备和步骤还是比较多的,晚上完成了基础的调试,来来回回切换了好多次,还算有点意思。
jeanron100
2018/10/24
2.2K0
Kubernetes 部署 MySQL 高可用读写分离
简介: 在有状态应用中,MySQL是我们最常见也是最常用的。本文我们将实战部署一个一组多从的MySQL集群。
小陈运维
2022/06/08
1K0
面试官你好,我已经掌握了MySQL主从配置和读写分离,你看我还有机会吗?
假设各位都已经安装好了 MySQL 数据库,本次操作采用的 MySQL 版本是 5.7.16。正好还有一台 Mac闲着,所以干脆就用两台物理机直接操作了,没有空闲机器的可以在虚拟机操作是一样的。
古时的风筝
2020/07/30
1.1K0
推荐阅读
相关推荐
slave have equal MySQL server UUIDs
更多 >
LV.1
这个人很懒,什么都没有留下~
目录
  • T1. 判断通过操作能否让字符串相等 I(Easy)
    • 题解(模拟)
  • T2. 判断通过操作能否让字符串相等 II(Medium)
    • 题解(模拟)
  • T3. 几乎唯一子数组的最大和(Medium)
    • 题解(滑动窗口 + 计数)
  • T4. 统计一个字符串的 k 子序列美丽值最大的数目(Hard)
    • 问题分析
    • 题解一(暴力枚举 + 乘法原理)
    • 题解二(排序 + 贪心 + 乘法原理)
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档