【数学】【组合数学】1830. 使字符串有序的最少操作次数-阿里云开发者社区

【数学】【组合数学】1830. 使字符串有序的最少操作次数

2024-04-10 24

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【数学】【组合数学】1830. 使字符串有序的最少操作次数

本博文涉及知识点

数学组合数学

LeetCode1830. 使字符串有序的最少操作次数

给你一个字符串 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 开始的字符串后缀反转。

请你返回将字符串变成有序的最少操作次数。由于答案可能会很大，请返回它对 10⁹ + 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 只包含小写英文字母。

组合数学

令 n= s.length

这个操作本质是：求前一字典序的s排列。本题 ⟺ \iff⟺ s的排列中有多少个字典序小于s。

i < j ,交换s[i]和s[j]。

令i1 < i2 ,i1 < j1 ,i2 < j2 s[i1] > s[j1] s[i2] > s[j2]

s交换s[i1]和s[j1]后，结果为t1。

s交换s[i2]和s[j2]后，结果为t2。

则t1< t2，因为t1[i1] < t2[i1]。

求排列的前一个字典序

计算最大下标i，使得存在s[x]<s[i],x∈ \in∈(i,n)。→ \rightarrow→ i1∈ \in∈(i,n) x1∈ \in∈(x1,n)，不存在s[x1] < s[i1] → \rightarrow→

s[i+1,⋯ \cdots⋯…,n) 设升序排列。本题解的i就是题目的i-1。

寻找j，使得s[j] < s[i]，有多个符合的s[j]，取值最大的s[j]。由于s[i+1,… \dots…,n)是升序，所以题解的j，就是题目的j。

交换s[i]和s[j]。

s[i]变小后，后面的字符无论如何变大，都是变小。故让s[i+1,n)变最大，即降序排列。目前是升序排列，反转即可达到目标。

求字典序小于s的排列数量

字典序列小于s的排列t有如下特征：前k位相同,k∈ \in∈[0,n-1]。t[k] < s[k] ，t[k+1,⋯ \cdots⋯,n)不限。假定后面有a个’a’,b个’b’，如果求数量？

假定’a’不同不，则共有(a+b)! 种排放, 考虑到‘a’ 是相同的则 a! 种是相同的，考虑到’b’是相同的，则b! 中不同。

!是阶乘，故：结果为 (a+b)!/a!/b!。

代码

核心代码

template<int MOD = 1000000007>
class C1097Int
{
public:
  C1097Int(long long llData = 0) :m_iData(llData% MOD)
  {
  }
  C1097Int  operator+(const C1097Int& o)const
  {
    return C1097Int(((long long)m_iData + o.m_iData) % MOD);
  }
  C1097Int& operator+=(const C1097Int& o)
  {
    m_iData = ((long long)m_iData + o.m_iData) % MOD;
    return *this;
  }
  C1097Int& operator-=(const C1097Int& o)
  {
    m_iData = (m_iData + MOD - o.m_iData) % MOD;
    return *this;
  }
  C1097Int  operator-(const C1097Int& o)
  {
    return C1097Int((m_iData + MOD - o.m_iData) % MOD);
  }
  C1097Int  operator*(const C1097Int& o)const
  {
    return((long long)m_iData * o.m_iData) % MOD;
  }
  C1097Int& operator*=(const C1097Int& o)
  {
    m_iData = ((long long)m_iData * o.m_iData) % MOD;
    return *this;
  }
  bool operator<(const C1097Int& o)const
  {
    return m_iData < o.m_iData;
  }
  C1097Int pow(long long n)const
  {
    C1097Int iRet = 1, iCur = *this;
    while (n)
    {
      if (n & 1)
      {
        iRet *= iCur;
      }
      iCur *= iCur;
      n >>= 1;
    }
    return iRet;
  }
  C1097Int PowNegative1()const
  {
    return pow(MOD - 2);
  }
  int ToInt()const
  {
    return m_iData;
  }
private:
  int m_iData = 0;;
};
class Solution {
public:
  int makeStringSorted(string s) {
    int cnt[26] = { 0 };
    vector<C1097Int<>> fac(s.length() + 1, 1);
    for (int i = 2; i <= s.length(); i++)
    {
      fac[i] = fac[i - 1] * i;
    }
    C1097Int<> biRet;
    for (int i = s.length() - 1; i >= 0; i--)
    {
      const int n = s[i] - 'a';
      for (int ii = 0; ii < n; ii++)
      {
        if (0 == cnt[ii])
        {
          continue;
        }
        C1097Int<> biDiv = 1;
        for (int j = 0; j < 26; j++)
        {         
          biDiv *= fac[cnt[j]-(j == ii ) + ( j == n )];
        }
        biRet += fac[s.length() - 1 - i]  * biDiv.PowNegative1();
      }     
      cnt[n]++;
    }
    return biRet.ToInt();
  }
};

template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  string s ;
  
  {
    Solution sln;
    s = "aabaa";
    auto res = sln.makeStringSorted(s);
    Assert(2, res);
  }
  {
    Solution sln;
    s =  "cdbea";
      auto res = sln.makeStringSorted(s);
    Assert(63, res);
  }
  {
    Solution sln;
    s = "leetcodeleetcodeleetcode";
    auto res = sln.makeStringSorted(s);
    Assert(982157772, res);
  }
  {
    Solution sln;
    s = "cba";
    auto res = sln.makeStringSorted(s);
    Assert(5, res);
  }
}

2023年9月

class Solution {
public:
int makeStringSorted(const string s) {
m_c = s.length();
vector<C1097Int<>> vRangeMul = { 1 };
for (int i = 1; i <= m_c; i++)
{
vRangeMul.emplace_back(vRangeMul.back() * i);
}
int nums[26] = { 0 };
C1097Int<> biRet = 0;
nums[s.back() - ‘a’]++;
for (int i = m_c - 1 - 1; i >= 0; i–)
{
const int iLessNum = std::accumulate(nums, nums + (s[i] - ‘a’), 0);
if (iLessNum > 0)
{//可以调整顺序
const int iRightNum = m_c - (i+1);
nums[s[i] - ‘a’]++;
C1097Int tmp = vRangeMul[iRightNum];
for (int k = 0; k < 26; k++)
{
tmp = vRangeMul[nums[k]].PowNegative1();
}
for (int j = 0; j < s[i]-‘a’; j++)
{
if (0 == nums[j])
{
continue;
}
biRet += tmp * vRangeMul[nums[j]] vRangeMul[nums[j] - 1].PowNegative1();
}
nums[s[i] - ‘a’]–;
}
nums[s[i] - ‘a’]++;
}
return biRet.ToInt();
}
int m_c;
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。