class Solution {
public:
string getSmallestString(string s) {
}
};
100352. 交换后字典序最小的字符串
给你一个仅由数字组成的字符串 s，在最多交换一次 相邻 且具有相同 奇偶性 的数字后，返回可以得到的字典序最小的字符串。
如果两个数字都是奇数或都是偶数，则它们具有相同的奇偶性。例如，5 和 9、2 和 4 奇偶性相同，而 6 和 9 奇偶性不同。
示例 1：
输入： s = "45320"
输出： "43520"
解释：
s[1] == '5' 和 s[2] == '3' 都具有相同的奇偶性，交换它们可以得到字典序最小的字符串。
示例 2：
输入： s = "001"
输出： "001"
解释：
无需进行交换，因为 s 已经是字典序最小的。
提示：
2 <= s.length <= 100s 仅由数字组成。相似题目
原站题解
c 解法, 执行用时: 0 ms, 内存消耗: 7.9 MB, 提交时间: 2024-10-30 23:46:10
char* getSmallestString(char* s) {
for (int i = 1; s[i]; i++) {
char x = s[i - 1], y = s[i];
if (x > y && x % 2 == y % 2) {
s[i - 1] = y;
s[i] = x;
break;
}
}
return s;
}
php 解法, 执行用时: 20 ms, 内存消耗: 20.2 MB, 提交时间: 2024-07-15 09:40:23
class Solution {
/**
* @param String $s
* @return String
*/
function getSmallestString($s) {
$s1 = str_split($s);
$n = strlen($s);
for ( $i = 1; $i < $n; $i++ ) {
$x = ord($s[$i-1]);
$y = ord($s[$i]);
if ( $x > $y && ( $x % 2 === $y % 2 ) ) {
$s1[$i-1] = chr($y);
$s1[$i] = chr($x);
break;
}
}
return implode('', $s1);
}
}
javascript 解法, 执行用时: 67 ms, 内存消耗: 51.8 MB, 提交时间: 2024-07-15 09:30:56
/**
* @param {string} s
* @return {string}
*/
var getSmallestString = function(s) {
let t = s.split(''); // 将字符串转换为字符数组
for (let i = 1; i < t.length; i++) {
let x = t[i - 1];
let y = t[i];
// 注意：在JavaScript中，字符实际上是Unicode字符串，但这里假设只包含ASCII字符
// 因此我们可以直接比较字符编码（charCodeAt()返回的是字符的Unicode编码）
if (x.charCodeAt(0) > y.charCodeAt(0) && x.charCodeAt(0) % 2 === y.charCodeAt(0) % 2) {
t[i - 1] = y;
t[i] = x;
break;
}
}
return t.join(''); // 将字符数组转换回字符串
};
rust 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2024-07-15 09:28:53
impl Solution {
pub fn get_smallest_string(s: String) -> String {
let mut chars: Vec<char> = s.chars().collect();
for i in 1..chars.len() {
let x = chars[i - 1];
let y = chars[i];
if x > y && (x as u8) % 2 == (y as u8) % 2 {
chars.swap(i - 1, i);
break;
}
}
chars.iter().collect()
}
}
java 解法, 执行用时: 1 ms, 内存消耗: 41.8 MB, 提交时间: 2024-07-15 09:27:06
class Solution {
public String getSmallestString(String s) {
char[] t = s.toCharArray();
for (int i = 1; i < t.length; i++) {
char x = t[i - 1];
char y = t[i];
if (x > y && x % 2 == y % 2) {
t[i - 1] = y;
t[i] = x;
break;
}
}
return new String(t);
}
}
cpp 解法, 执行用时: 3 ms, 内存消耗: 7.9 MB, 提交时间: 2024-07-15 09:26:55
class Solution {
public:
string getSmallestString(string s) {
for (int i = 1; i < s.length(); i++) {
char x = s[i - 1], y = s[i];
if (x > y && x % 2 == y % 2) {
swap(s[i - 1], s[i]);
break;
}
}
return s;
}
};
golang 解法, 执行用时: 0 ms, 内存消耗: 2.4 MB, 提交时间: 2024-07-15 09:26:38
func getSmallestString(s string) string {
t := []byte(s)
for i := 1; i < len(t); i++ {
x, y := t[i-1], t[i]
if x > y && x%2 == y%2 {
t[i-1], t[i] = y, x
break
}
}
return string(t)
}
python3 解法, 执行用时: 35 ms, 内存消耗: 16.2 MB, 提交时间: 2024-07-15 09:26:17
class Solution:
def getSmallestString(self, s: str) -> str:
t = list(s)
for i in range(1, len(t)):
x, y = t[i - 1], t[i]
if x > y and ord(x) % 2 == ord(y) % 2:
t[i - 1], t[i] = y, x
break
return ''.join(t)
python3 解法, 执行用时: 47 ms, 内存消耗: 16.3 MB, 提交时间: 2024-07-15 09:25:59
# 贪心：优先交换靠左的，左边的比右边大的
class Solution:
def getSmallestString(self, s: str) -> str:
n = len(s)
s1 = [int(c) for c in s]
for i in range(n-1):
if ( s1[i] % 2 == s1[i+1] % 2 ) and s1[i] > s1[i+1]:
s1[i], s1[i+1] = s1[i+1], s1[i]
return ''.join((str(c) for c in s1))
return s