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)


相关推荐

  • Android 查看Android版本的方法

    Android 查看Android版本的方法查看Android版本的方法

  • linux更改密码策略_hpunix设置用户密码策略

    linux更改密码策略_hpunix设置用户密码策略如何设置 Linux 系统的密码策略

  • idea构建springboot_jsp项目搭建过程

    idea构建springboot_jsp项目搭建过程SpringBoot项目相对SpringMVC项目有搭建迅速,配置更少的优点。创建springboot项目有很多种方式,本文使用idea创建一个整合mongoDB和mysql数据库的简单的springboot项目。文章末尾附源码地址。搭建步骤:主要是以截图的方式介绍搭建过程。进入新建项目界面,按照下图操作经过以上步骤,基本项目框架就会搭建起来。因为项目中需要用到阿里的数据库连接池和jso

  • QGIS 3.10 路径分析

    QGIS 3.10 路径分析网络数据集(networks)的创建、管理和可视化是GIS的重要组成部分。公路、铁路、管线等公用基础设施都可以建模为由线和节点组成的带有属性信息的网络数据。本教程将学习如何对路网进行建模,如何运用样式对路网属性可视化,同时通过QGIS3.10内置的路径分析工具找出两点之间的最短路径。任务概述通过华盛顿地区道路中心线图层,建立路网并查找城市中任意两点之间的最短路径。将会学到的其他技巧使用数据定义覆盖(datadefinedoverrides),根据线的方向对齐箭头符号。获取示范数据本教程

  • 虚拟机与宿主机网络配置——可互通可上网「建议收藏」

    虚拟机与宿主机网络配置——可互通可上网「建议收藏」     为了学习和使用Linux,多数人选择了使用虚拟机的方式来安装Linux系统。这样我们就可以在windows系统中安装Linux系统了,其中windows机器系统本身我们称作宿主机,安装的虚拟机系统我们简称虚拟机。     由于虚拟机提供的几种网络方式,要么是虚拟机可以ping通宿主机反之不行,要么是虚拟机之间可以互通但宿主机不能访问虚拟机,所以在实际应用中多数被两者间的网络互通和是否…

  • 黑马程序员—只要路对,不怕路远——寂寞中蔓延着成功路途[通俗易懂]

    黑马程序员—只要路对,不怕路远——寂寞中蔓延着成功路途[通俗易懂]文章来源:黑马程序员,黑马论坛

发表回复

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

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