leetcode
leetcode 1451 ~ 1500
执行操作后字典序最小的字符串

执行操作后字典序最小的字符串

难度:

标签:

题目描述

代码结果

运行时间: 79 ms, 内存: 0.0 MB


/*
 * This solution is similar to the Java version but uses Java Streams for concise and functional-style operations.
 */

import java.util.*;
import java.util.stream.*;

public class SmallestStringStream { 
    private static String add(String s, int a) {
        return IntStream.range(0, s.length())
            .mapToObj(i -> (i % 2 == 1) ? (char) (((s.charAt(i) - '0' + a) % 10) + '0') : s.charAt(i))
            .map(String::valueOf)
            .collect(Collectors.joining());
    }

    private static String rotate(String s, int b) {
        int n = s.length();
        b = b % n;
        return s.substring(n - b) + s.substring(0, n - b);
    }

    public static String findLexSmallestString(String s, int a, int b) {
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.offer(s);
        visited.add(s);
        String minString = s;

        while (!queue.isEmpty()) {
            String current = queue.poll();

            String added = add(current, a);
            if (visited.add(added)) {
                queue.offer(added);
                minString = Stream.of(minString, added).min(String::compareTo).orElse(minString);
            }

            String rotated = rotate(current, b);
            if (visited.add(rotated)) {
                queue.offer(rotated);
                minString = Stream.of(minString, rotated).min(String::compareTo).orElse(minString);
            }
        }

        return minString;
    }

    public static void main(String[] args) {
        String s = "5525";
        int a = 9;
        int b = 2;
        System.out.println(findLexSmallestString(s, a, b));  // Output: "2050"
    }
}

解释

方法:

这个题解利用了循环串的概念和数字的周期性。首先,定义了一个辅助函数 generate(num, a) 来找出对于一个给定的数字 num,在累加操作下,如何通过最小的变化使其达到最小的可能值。接着在主函数中,通过旋转和累加操作,尝试生成所有可能的字符串变体。具体步骤包括:将字符串 s 转换为整数数组,然后对每个可能的旋转位移进行遍历,每次旋转后再对奇数位执行累加操作,如果 b 是奇数,也对偶数位执行累加操作,最后将所有可能的字符串收集起来,返回其中字典序最小的字符串。这种方法考虑了通过不同的旋转和累加操作来探索所有可能的字符串配置,并利用集合来避免重复处理相同的旋转配置。

时间复杂度:

O(n^2)

空间复杂度:

O(n^2)

代码细节讲解

🦆
在`generate`函数中,为什么选择循环10次来计算数字在累加`a`后的最小值?这是基于哪些数学原理或者假设?
这是基于模运算的性质和数字的周期性。在十进制系统中,任何数字加上10的倍数都不会改变其在模10运算中的结果。因此,一个数字`num`在累加`a`后,考虑其模10的结果只需考察`num`, `num+a`, `num+2a`, ..., `num+9a`这10个数字即可,因为`num+10a`的模10结果会和`num`相同,从而形成周期。通过这10次迭代,我们可以找到令`num`模10的结果最小的`a`的累加次数。
🦆
题解中提到了通过集合`seen`来避免处理相同的旋转配置,但是如何判断什么时候一个旋转配置已经被处理过?具体是基于哪种属性来避免重复处理的?
旋转配置的处理是基于旋转偏移量`offset`的。在处理字符串旋转时,旋转偏移量`offset`是通过`i*b % n`计算得出的,其中`i`是当前的旋转尝试次数,`b`是旋转步长,而`n`是字符串的长度。如果某个计算出的偏移量已经在之前出现过(即存在于集合`seen`中),则意味着该旋转已经被考虑过,因此可以跳过以避免重复处理。这样确保每种旋转配置只被处理一次,提高了算法的效率和避免了不必要的重复计算。
🦆
关于字典序最小字符串的生成,题解中提到的`如果b是奇数,也对偶数位进行累加操作`,这一操作是基于什么样的考虑?为什么偶数位的处理与`b`的奇偶性有关?
这一操作是基于旋转步长`b`的奇偶性对字符串中字符位置的影响。当`b`是奇数时,偶数索引和奇数索引的字符会在旋转过程中交替出现,这意味着原本在偶数位置的字符因为旋转可以出现在奇数位置上,反之亦然。因此,为了确保在所有可能的字符串配置中找到字典序最小的结果,当`b`为奇数时,我们需要对偶数位和奇数位的数字进行累加操作。这样可以确保不论字符如何旋转,都能考虑到其可能被累加修改的情况,从而生成所有可能的字符串配置,最终选取字典序最小的一个。

相关问题