leetcode-1830. 使字符串有序的最少操作次数(数位dp+逆元+快速幂+排列)「建议收藏」

leetcode-1830. 使字符串有序的最少操作次数(数位dp+逆元+快速幂+排列)「建议收藏」给你一个字符串 s (下标从 0 开始)。你需要对 s 执行以下操作直到它变为一个有序字符串:找到 最大下标 i ,使得 1 <= i < s.length 且 s[i] < s[i – 1] 。找到 最大下标 j ,使得 i <= j < s.length 且对于所有在闭区间 [i, j] 之间的 k 都有 s[k] < s[i – 1] 。交换下标为 i – 1​​​​ 和 j​​​​ 处的两个字符。将下标 i 开始的字符串后缀反转。请你返回将字符串变成有序

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

给你一个字符串 s (下标从 0 开始)。你需要对 s 执行以下操作直到它变为一个有序字符串:

找到 最大下标 i ,使得 1 <= i < s.length 且 s[i] < s[i – 1] 。
找到 最大下标 j ,使得 i <= j < s.length 且对于所有在闭区间 [i, j] 之间的 k 都有 s[k] < s[i – 1] 。
交换下标为 i – 1​​​​ 和 j​​​​ 处的两个字符。
将下标 i 开始的字符串后缀反转。
请你返回将字符串变成有序的最少操作次数。由于答案可能会很大,请返回它对 109 + 7 取余 的结果。

示例 1:

输入:s = "cba"
输出:5
解释:模拟过程如下所示:
操作 1:i=2,j=2。交换 s[1] 和 s[2] 得到 s="cab" ,然后反转下标从 2 开始的后缀字符串,得到 s="cab" 。
操作 2:i=1,j=2。交换 s[0] 和 s[2] 得到 s="bac" ,然后反转下标从 1 开始的后缀字符串,得到 s="bca" 。
操作 3:i=2,j=2。交换 s[1] 和 s[2] 得到 s="bac" ,然后反转下标从 2 开始的后缀字符串,得到 s="bac" 。
操作 4:i=1,j=1。交换 s[0] 和 s[1] 得到 s="abc" ,然后反转下标从 1 开始的后缀字符串,得到 s="acb" 。
操作 5:i=2,j=2。交换 s[1] 和 s[2] 得到 s="abc" ,然后反转下标从 2 开始的后缀字符串,得到 s="abc" 。
示例 2:

输入:s = "aabaa"
输出:2
解释:模拟过程如下所示:
操作 1:i=3,j=4。交换 s[2] 和 s[4] 得到 s="aaaab" ,然后反转下标从 3 开始的后缀字符串,得到 s="aaaba" 。
操作 2:i=4,j=4。交换 s[3] 和 s[4] 得到 s="aaaab" ,然后反转下标从 4 开始的后缀字符串,得到 s="aaaab" 。
示例 3:

输入:s = "cdbea"
输出:63
示例 4:

输入:s = "leetcodeleetcodeleetcode"
输出:982157772
 

提示:

1 <= s.length <= 3000
s​ 只包含小写英文字母。

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 3010;
int f[N],g[N];
class Solution { 

public:
ll qmi(ll x,int y){ 

ll base = x,res = 1;
while(y){ 

if(y & 1)res = (res * base) % MOD;
base = base * base % MOD;
y >>= 1;
}
return res;
}
int get(int cnt[]){ 

int ans = 0;
int sum = 0;
for(int i = 0;i < 26;i ++)sum += cnt[i];
ans = f[sum];
for(int i = 0;i < 26;i ++){ 

ans = ((ll)ans * g[cnt[i]]) % MOD;
}
return ans;
}
int makeStringSorted(string s) { 

f[0] = g[0] = 1;
for(int i = 1;i < N;i ++){ 

f[i] = ((ll)f[i - 1] * i) % MOD;
g[i] = qmi(f[i],MOD - 2);
}
int ans = 0;
int cnt[26] = { 
0};
for(auto a : s)cnt[a - 'a'] ++;
for(auto &a : s){ 

int x = a - 'a';
for(int i = 0;i < x;i ++){ 

int sum = 0;
if(cnt[i]){ 

cnt[i] --;
ans = (ans + get(cnt)) % MOD;
cnt[i] ++;
}
}
cnt[x] --;
}
return ans;
}
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168558.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • linux安装mysql8.0.16_mysql安装配置教程

    linux安装mysql8.0.16_mysql安装配置教程1.在/use/local下创建mysql文件夹mkdirmysql2.切换到mysql文件夹下cdmysql3.下载mysqlwgethttps://dev.mysql.com/get/Downloads/MySQL-8.0/mysql-8.0.20-linux-glibc2.12-x86_64.tar.xz也可以直接在官方下载最新版本https://dev.mysql.com/downloads/mysql/选择linux4.解压mysqltar-zx……..

    2022年10月13日
  • jdk8 hashmap线程安全吗_Python中的线程

    jdk8 hashmap线程安全吗_Python中的线程前言只要是对于集合有一定了解的一定都知道HashMap是线程不安全的,我们应该使用ConcurrentHashMap。但是为什么HashMap是线程不安全的呢,之前面试的时候也遇到到这样的问题,但是当时只停留在***知道是***的层面上,并没有深入理解***为什么是***。于是今天重温一个HashMap线程不安全的这个问题。首先需要强调一点,HashMap的线程不安全体现在会造成死循环、数据丢…

    2022年10月11日
  • 01-全文检索

    01-全文检索

  • ubuntu ll命令[通俗易懂]

    ubuntu ll命令[通俗易懂]用过Redhat的朋友应该很熟悉ll这个命令,就相当于ls-l,但在Ubuntu中就不行了。严格来说ll不是一个命令,只是命令的别名而已。很多Linux用户都使用bashshell,对普通用户来说用得最多的就是命令补全(按tab键)和alias(别名)功能。Ubuntu默认建立的用户都用的bashshell,所以它也支持别名功能,我们只需要gedi

  • Tomcat下的appBase和docBase[通俗易懂]

    我们先看appBase,这个目录表示:1这个目录下面的子目录将自动被部署为应用。2这个目录下面的.war文件将被自动解压缩并部署为应用而docBase只是指向了你某个应用的目录,这个可以和appBase没有任何关系。总结:如果你想自己指定路径,那么应该在docBase里面如果你想简单,那么直接把他们复制到appBase下面就行了如果你把他们弄重复了,也就是2个指向了

  • 大数据分析与应用技术创新平台「建议收藏」

    大数据分析与应用技术创新平台「建议收藏」原文链接:https://mp.weixin.qq.com/s/kCDYOInF8KjHstIMAWSljA 大数据分析与应用技术创新平台 张平文,鄂维南,袁晓如,傅毅明北京大学数学科学学院,北京 100871 北京大学大数据科学研究中心,北京 100871  北京大学信息科学技术学院,北京 100871  北京大数据研究院,北京 100871 摘…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号