华为OD统一考试 -字符串变换最小字符串
题目描述
给定一个字符串s,最多只能进行一次变换,返回变换后能得到的最小字符串(按照字典序进行比较)。
变换规则:交换字符串中任意两个不同位置的字符。
输入描述
一串小写字母组成的字符串s
输出描述
按照要求进行变换得到的最小字符串。
备注
- s是都是小写字符组成
- 1 ≤ s.length ≤ 1000
用例
输入 | abcdef |
输出 | abcdef |
说明 | abcdef已经是最小字符串,不需要交换。 |
输入 | bcdefa |
输出 | acdefb |
说明 | a和b进行位置交换,可以得到最小字符串 |
题目解析
我的思路如下,先将输入的字符串str进行字典排序,得到一个新串minStr,如果str和minStr相同,则说明str已经是最小字符串,不需要任何变换,直接返回str。
如果str和minStr不同,则说明str不是最小字符串,我们需要遍历出str的每一个字符,对比str[i] 和 minStr[i] ,具体处理逻辑如下图
import Foundation func ODTest_58() { print("一串小写字母组成的字符串") var str = readLine() ?? "" if str.count < 1 || str.count > 1000 { print("无") return } let minChars = str.sorted(by: { $0 < $1 }).map { $0 } for i in 0 ..< str.count { let range = str.index(str.startIndex, offsetBy: i) if String(minChars[i]) != str[range ... range] { let old = str[range ... range] str.replaceSubrange(range ... range, with: String(minChars[i])) // 出现多个相同字符,取最后一个 guard let index = str.lastIndex(where: { $0 == minChars[i] }) else { return } str.replaceSubrange(index ... index, with: old) break } } print("按照要求进行变换得到的最小字符串") print("\(str)") }
2024华为OD机试卷题 文章被收录于专栏
本专栏给大家提供了华为2024最新华为OD 题目汇总。华为OD机试刷题记录机考算法题库,帮助你上岸华为。提供C++/Java、JavaScript、Python四种语言的解法。