代码编织梦想

【LetMeFly】1625.执行操作后字典序最小的字符串

力扣题目链接:https://leetcode.cn/problems/lexicographically-smallest-string-after-applying-operations/

给你一个字符串 s 以及两个整数 ab 。其中,字符串 s 的长度为偶数,且仅由数字 09 组成。

你可以在 s 上按任意顺序多次执行下面两个操作之一:

  • 累加:将  a 加到 s 中所有下标为奇数的元素上(下标从 0 开始)。数字一旦超过 9 就会变成 0,如此循环往复。例如,s = "3456"a = 5,则执行此操作后 s 变成 "3951"
  • 轮转:将 s 向右轮转 b 位。例如,s = "3456"b = 1,则执行此操作后 s 变成 "6345"

请你返回在 s 上执行上述操作任意次后可以得到的 字典序最小 的字符串。

如果两个字符串长度相同,那么字符串 a 字典序比字符串 b 小可以这样定义:在 ab 出现不同的第一个位置上,字符串 a 中的字符出现在字母表中的时间早于 b 中的对应字符。例如,"0158” 字典序比 "0190" 小,因为不同的第一个位置是在第三个字符,显然 '5' 出现在 '9' 之前。

 

示例 1:

输入:s = "5525", a = 9, b = 2
输出:"2050"
解释:执行操作如下:
初态:"5525"
轮转:"2555"
累加:"2454"
累加:"2353"
轮转:"5323"
累加:"5222"
累加:"5121"
轮转:"2151"
累加:"2050"​​​​​​​​​​​​
无法获得字典序小于 "2050" 的字符串。

示例 2:

输入:s = "74", a = 5, b = 1
输出:"24"
解释:执行操作如下:
初态:"74"
轮转:"47"
累加:"42"
轮转:"24"​​​​​​​​​​​​
无法获得字典序小于 "24" 的字符串。

示例 3:

输入:s = "0011", a = 4, b = 2
输出:"0011"
解释:无法获得字典序小于 "0011" 的字符串。

示例 4:

输入:s = "43987654", a = 7, b = 3
输出:"00553311"

 

提示:

  • 2 <= s.length <= 100
  • s.length 是偶数
  • s 仅由数字 09 组成
  • 1 <= a <= 9
  • 1 <= b <= s.length - 1

方法一:模拟

我们只需要明白:

  1. 因为轮转不可能产生无限多种字符串,所以轮转所产生的字符串是在不断循环地
  2. 因为我们只能同时改变偶数位置的字符,所以对于一个轮转后的字符串,我们要让下标为1的字符尽可能地小
  3. 因为字符串长度为偶数,所以如果轮转距离b是奇数,则奇数位置的字符下标也有机会到达偶数;反之奇数下标永远只能处于奇数的位置。

这样,我们就能开开心心地模拟了。

首先模拟所有的“轮转结果”(最多有len(s)种)

对于每种轮转结果,我们让其下标1处的字符加上数个a后尽可能地小,然后让所有奇数下标的字符加上相同数量的a。如果b为奇数,则让下标0处的字符加上数个a后尽可能小,并将所有偶数下标的字符加上相同数量的a。

对于每种轮转结果,得到加最优a后的字符串后,在所有字符串中最小的一个即为答案。

  • 时间复杂度 O ( l e n ( s ) 2 × C ) O(len(s)^2\times C) O(len(s)2×C),其中 C = 10 C=10 C=10。最多需要 l e n ( s ) len(s) len(s)次轮转,对于每次轮转需要 l e n ( s ) × C len(s)\times C len(s)×C的复杂度完成“加a”、比较等操作。最多加上10次a即可找到最优的加a次数。
  • 空间复杂度 O ( l e n ( s ) ) O(len(s)) O(len(s))

AC代码

C++

class Solution {
private:
    int add2minStep(char original, int a) {  // 将original加数次a,使得original尽可能小,需要加几次
        int ans = 0;
        int step = 0;
        int m = original - '0';
        int n = original - '0';
        do {
            n = (n + a) % 10;
            step++;
            if (n < m) {
                m = n;
                ans = step;
            }
        } while (a * step % 10);
        return ans;
    }

    string change2loc2min(string& s, int a, int b, int l) {  // 将s的l、l + 1两个位置变得尽可能小并移动到最前
        string ans = s.substr(l, s.size() - l) + s.substr(0, l);
        if (b % 2) {
            int m1 = add2minStep(ans[0], a);
            for (int i = 0; i < s.size(); i += 2) {
                ans[i] = (char)((ans[i] - '0' + a * m1) % 10 + '0');
            }
        }
        int m2 = add2minStep(ans[1], a);
        for (int i = 1; i < s.size(); i += 2) {
            ans[i] = (char)((ans[i] - '0' + a * m2) % 10 + '0');
        }
        return ans;
    }
public:
    string findLexSmallestString(string& s, int a, int b) {
        string ans = s;
        int totalRotate = b;
        do {
            // string thisStr = change2loc2min(s, a, b, s.size() - totalRotate);  cout << thisStr << endl;  //**********
            ans = min(ans, change2loc2min(s, a, b, s.size() - totalRotate));
            totalRotate = (totalRotate + b) % s.size();
        } while (totalRotate != b);
        return ans;
    }
};

同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/129651164

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Tisfy/article/details/129651164

Leetcode 5544: 执行操作后字典序最笑的字符串-爱代码爱编程

题目描述 给你一个字符串 s 以及两个整数 a 和 b 。其中,字符串 s 的长度为偶数,且仅由数字 0 到 9 组成。 你可以在 s 上按任意顺序多次执行下面两个操作之一: 累加:将  a 加到 s 中所有下标为奇数的元素上(下标从 0 开始)。数字一旦超过 9 就会变成 0,如此循环往复。例如,s = "3456" 且 a = 5,则执行此操作后

leetcode-5128 执行操作后字典序最小的字符串【并查集】-爱代码爱编程

  5128. 带阈值的图连通性 有 n 座城市,编号从 1 到 n 。编号为 x 和 y 的两座城市直接连通的前提是: x 和 y 的公因数中,至少有一个 严格大于 某个阈值 threshold 。更正式地说,如果存在整数 z ,且满足以下所有条件,则编号 x 和 y 的城市之间有一条道路: x % z == 0y % z == 0z > t

leetcode-5544. 执行操作后字典序最小的字符串-爱代码爱编程

题目 给你一个字符串 s 以及两个整数 a 和 b 。其中,字符串 s 的长度为偶数,且仅由数字 0 到 9 组成。 你可以在 s 上按任意顺序多次执行下面两个操作之一: 累加:将 a 加到 s 中所有下标为奇数的元素上(下标从 0 开始)。数字一旦超过 9 就会变成 0,如此循环往复。例如,s = "3456" 且 a = 5,则执行此操作后 s

LeetCode 5544. 执行操作后字典序最小的字符串 lexicographically-smallest-string-after-applying-operation-爱代码爱编程

题目链接 LC5544 题解 题意 两种操作: 轮转,取第b个字符作为第一个,之前的字符在保持相对顺序不变的情况下补到字符串末尾。累加,奇数位的字符加a,数字超过9就会变成0。求最小字典序的字符串。 思路 枚举所有可能的情况,取一个最小的。 在初始字符串轮转i次的情况下,对字符串的奇数位累加j次,若可以使得字符串的偶数位变成奇数位,即b是奇数

1625 执行操作后字典序最小的字符串(递归)-爱代码爱编程

1. 问题描述: 给你一个字符串 s 以及两个整数 a 和 b 。其中,字符串 s 的长度为偶数,且仅由数字 0 到 9 组成。 你可以在 s 上按任意顺序多次执行下面两个操作之一:累加:将  a 加到 s 中所有下标为奇数的元素上(下标从 0 开始)。数字一旦超过 9 就会变成 0,如此循环往复。例如,s = "3456" 且 a = 5,则执行此操作

解题思路-leetcode第1625题:执行操作后字典序最小的字符串-爱代码爱编程

解题思路-leetcode第1625题:执行操作后字典序最小的字符串 题目描述: 给你一个字符串 s 以及两个整数 a 和 b 。其中,字符串 s 的长度为偶数,且仅由数字 0 到 9 组成。 你可以在 s 上按任意顺序多次执行下面两个操作之一: 累加:将 a 加到 s 中所有下标为奇数的元素上(下标从 0 开始)。数字一旦超过 9 就会变成 0,如此循

LeetCode 1754. 构造字典序最大的合并字符串(贪心贪心)-爱代码爱编程

1754. 构造字典序最大的合并字符串 给你两个字符串 word1 和 word2 。你需要按下述方式构造一个新字符串 merge :如果 word1 或 word2 非空,选择 下面选项之一 继续操作: 如果 word1 非空,将 word1 中的第一个字符附加到 merge 的末尾,并将其从 word1 中移除。 例如,word1 = “abc”

LeetCode 1754. 构造字典序最大的合并字符串(思维)-爱代码爱编程

题意: 给你两个字符串 word1 和 word2 。 你需要按下述方式构造一个新字符串 merge :如果 word1 或 word2 非空,选择 下面选项之一 继续操作: 如果 word1 非空,将 word1 中的第一个字符附加到 merge 的末尾,并将其从 word1 中移除。 例如,word1 = "abc" 且 merge = "dv"

LeetCode——1641. 统计字典序元音字符串的数目-爱代码爱编程

题目描述: 给你一个整数 n,请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。 字符串 s 按 字典序排列 需要满足:对于所有有效的 i,s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。 提示: 1 <= n <= 50示例 1: 输入:n = 1 输出:

执行操作后字典序最小的字符串-爱代码爱编程

1.如何暴力解答2.如何进行优化 题目描述 给你一个字符串 s 以及两个整数 a 和 b 。其中,字符串 s 的长度为偶数,且仅由数字 0 到 9 组成。 你可以在 s 上按任意顺序多次执行下面两个操作之一: 累加:将 a 加到 s 中所有下标为奇数的元素上(下标从 0 开始)。数字一旦超过 9 就会变成 0,如此循环往复。例如,s = “3456

leetcode 1163. 按字典序排在最后的子串_sasakihaise_的博客-爱代码爱编程

1163. 按字典序排在最后的子串   【最小表示法】 最小表示法用在从一个循环字符串(或者不循环)的字符串中找到最小(大)的子串。 例如:从abaabczbzd这个串中找到zd这个最大字典序子串或者zdabaabczb这样一个子串,暴力法就是从每个位置切割字符串,但是这样需要保存n*n个字符串再排序,必然MLE 因此最小表示法的精髓在于,每次都

使用机器人打印字典序最小的字符串(leetcode314周赛第三题)_星河边采花的博客-爱代码爱编程

贪心题 给你一个字符串 s 和一个机器人,机器人当前有一个空字符串 t 。执行以下操作之一,直到 s 和 t 都变成空字符串: 删除字符串 s 的 第一个 字符,并将该字符给机器人。机器人把这个字符添加到 t 的尾部。删除字符串 t 的 最后一个 字符,并将该字符给机器人。机器人将该字符写到纸上。 请你返回纸上能写出的字典序最小的字符串。 示例 1:

【leetcode】1754. 构造字典序最大的合并字符串-爱代码爱编程

构造字典序最大的合并字符串 题目描述 给你两个字符串 word1 和 word2 。你需要按下述方式构造一个新字符串 merge :如果 word1 或 word2 非空,选择 下面选项之一 继续操作: 如果 wor

第314场leetcode周赛|使用机器人打印字典序最小的字符串_1480: 【基础】找字典序最小的字符串-爱代码爱编程

题目: 给你一个字符串 s 和一个机器人,机器人当前有一个空字符串 t 。执行以下操作之一,直到 s 和 t 都变成空字符串: 删除字符串 s 的 第一个 字符,并将该字符给机器人。机器人把这个字符添加到 t 的尾部。 删除字符串 t 的 最后一个 字符,并将该字符给机器人。机器人将该字符写到纸上。 请你返回纸上能写出的字典序最小的字符串。 分析

[山东科技大学oj]1247 problem e: 规范序排列-爱代码爱编程

  Time Limit: 1 Sec  Memory Limit: 16 MB Submit: 4388  Solved: 2531 [Submit][Status] Description 规范序是一种对字符串比较的排序规则,定义如下: 1 串长小的排在前面; 2 相同串长的按照字典序排列顺序。 串的字典序遵循如下递归定义: 1 两串的前