class Solution {
public:
int minimumOperations(string num) {
}
};
8040. 生成特殊数字的最少操作
给你一个下标从 0 开始的字符串 num ，表示一个非负整数。
在一次操作中，您可以选择 num 的任意一位数字并将其删除。请注意，如果你删除 num 中的所有数字，则 num 变为 0。
返回最少需要多少次操作可以使 num 变成特殊数字。
如果整数 x 能被 25 整除，则该整数 x 被认为是特殊数字。
示例 1：
输入：num = "2245047" 输出：2 解释：删除数字 num[5] 和 num[6] ，得到数字 "22450" ，可以被 25 整除。 可以证明要使数字变成特殊数字，最少需要删除 2 位数字。
示例 2：
输入：num = "2908305" 输出：3 解释：删除 num[3]、num[4] 和 num[6] ，得到数字 "2900" ，可以被 25 整除。 可以证明要使数字变成特殊数字，最少需要删除 3 位数字。
示例 3：
输入：num = "10" 输出：1 解释：删除 num[0] ，得到数字 "0" ，可以被 25 整除。 可以证明要使数字变成特殊数字，最少需要删除 1 位数字。
提示
1 <= num.length <= 100num 仅由数字 '0' 到 '9' 组成num 不含任何前导零原站题解
javascript 解法, 执行用时: 64 ms, 内存消耗: 50 MB, 提交时间: 2024-07-25 09:17:14
/**
* @param {string} num
* @return {number}
*/
var minimumOperations = function(num) {
const n = num.length;
let found0 = false, found5 = false;
for (let i = n - 1; i >= 0; i--) {
const c = num[i];
if (found0 && (c === '0' || c === '5') ||
found5 && (c === '2' || c === '7')) {
return n - i - 2;
}
if (c === '0') {
found0 = true;
} else if (c === '5') {
found5 = true;
}
}
return found0 ? n - 1 : n;
};
// 枚举末尾
var minimumOperations2 = function(num) {
const n = num.length;
function f(tail) {
let i = num.lastIndexOf(tail[1]);
if (i <= 0) {
return n;
}
i = num.lastIndexOf(tail[0], i - 1);
return i < 0 ? n : n - i - 2;
}
const zero = n - (num.includes('0') ? 1 : 0)
return Math.min(zero, f("00"), f("25"), f("50"), f("75"));
};
rust 解法, 执行用时: 3 ms, 内存消耗: 2 MB, 提交时间: 2024-07-25 09:16:24
impl Solution {
// 枚举末尾
pub fn minimum_operations(num: String) -> i32 {
let n = num.len() as i32;
let f = |x: char, y: char| -> i32 {
if let Some(i) = num.rfind(y) {
if let Some(i) = num[..i].rfind(x) {
return n - i as i32 - 2;
}
}
n
};
(n - (num.contains('0') as i32)).min(f('0', '0')).min(f('2', '5')).min(f('5', '0')).min(f('7', '5'))
}
// 一次遍历
pub fn minimum_operations2(num: String) -> i32 {
let n = num.len() as i32;
let mut found0 = false;
let mut found5 = false;
for (i, c) in num.bytes().enumerate().rev() {
if found0 && (c == b'0' || c == b'5') ||
found5 && (c == b'2' || c == b'7') {
return n - i as i32 - 2;
}
if c == b'0' {
found0 = true;
} else if c == b'5' {
found5 = true;
}
}
if found0 { n - 1 } else { n }
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2023-09-04 10:04:19
func minimumOperations(num string) int {
ans := len(num)
if strings.Contains(num, "0") {
ans-- // 可以删除 len(num)-1 次得到 "0"
}
f := func(tail string) {
i := strings.LastIndexByte(num, tail[1])
if i < 0 {
return
}
i = strings.LastIndexByte(num[:i], tail[0])
if i < 0 {
return
}
ans = min(ans, len(num)-i-2)
}
f("00")
f("25")
f("50")
f("75")
return ans
}
func min(a, b int) int { if b < a { return b }; return a }
cpp 解法, 执行用时: 4 ms, 内存消耗: 6.1 MB, 提交时间: 2023-09-04 10:04:00
class Solution {
public:
int minimumOperations(string num) {
int n = num.length();
auto f = [&](string tail) {
int i = num.rfind(tail[1]);
if (i == string::npos || i == 0) return n;
i = num.rfind(tail[0], i - 1);
if (i == string::npos) return n;
return n - i - 2;
};
return min({n - (num.find('0') != string::npos), f("00"), f("25"), f("50"), f("75")});
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 39.9 MB, 提交时间: 2023-09-04 10:03:45
public class Solution {
private int ans;
public int minimumOperations(String num) {
ans = num.length();
if (num.contains("0"))
ans--;
f(num, "00");
f(num, "25");
f(num, "50");
f(num, "75");
return ans;
}
private void f(String num, String tail) {
int n = num.length();
int i = num.lastIndexOf(tail.charAt(1));
if (i < 0) return;
i = num.lastIndexOf(tail.charAt(0), i - 1);
if (i < 0) return;
ans = Math.min(ans, n - i - 2);
}
}
python3 解法, 执行用时: 40 ms, 内存消耗: 15.8 MB, 提交时间: 2023-09-04 10:03:25
# 枚举删除后以 00/25/50/75 结尾，注意00左侧必须有非0
class Solution:
def minimumOperations(self, num: str) -> int:
n = len(num)
def f(tail: str) -> int:
i = num.rfind(tail[1])
if i < 0: return n
i = num.rfind(tail[0], 0, i) # 写成 num[:i].rfind(tail[0]) 会产生额外的切片空间
if i < 0: return n
return n - i - 2
return min(n - ('0' in num), f("00"), f("25"), f("50"), f("75"))