靠谱的车- 华为OD统一考试（C卷）
OD统一考试（C卷）
分值： 100分
题解： Java / Python / C++
题目描述
程序员小明打了一辆出租车去上班。出于职业敏感，他注意到这辆出租车的计费表有点问题，总是偏大。
出租车司机解释说他不喜欢数字4，所以改装了计费表，任何数字位置遇到数字4就直接跳过，其余功能都正常。
比如：
-
23再多一块钱就变为25；
-
39再多一块钱变为50；
-
399再多一块钱变为500；
小明识破了司机的伎俩，准备利用自己的学识打败司机的阴谋。
给出计费表的表面读数，返回实际产生的费用。
输入描述
只有一行，数字N，表示里程表的读数。
(1<=N<=888888888)。
输出描述
一个数字，表示实际产生的费用。以回车结束。
示例1
输入
5
输出
4
说明
5表示计费表的表面读数。
4表示实际产生的费用其实只有4块钱。
示例2
输入
17
输出
15
说明
17表示计费表的表面读数。
15表示实际产生的费用其实只有15块钱。
示例3
输入
100
输出
81
说明
100表示计费表的表面读数。
81表示实际产生的费用其实只有81块钱。
题解
此题采用记忆化搜索（实在不会可以暴力枚举所有的数字，然后去除掉数字中含有4的数字，即为答案，由于题目数据范围较大，暴力肯定会超时）。
代码大致描述:
- 通过递归函数
solve处理计费表的每一位数字，考虑是否跳过数字4，是否有限制，是否是数字。- 使用记忆化缓存
cache避免重复计算，提高效率。- 遍历计费表的每一位，根据不同情况调用递归函数。
- 返回计算结果。
Java
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.nextLine();
Solution solution = new Solution();
System.out.println(solution.solve(s.toCharArray(), 0, true, false));
}
}
class Solution {
int[] cache;
public Solution() {
this.cache = new int[15];
Arrays.fill(this.cache, -1);
}
/**
*
* @param w 原始字符数组
* @param idx 构造索引位置
* @param isLimit 构造时是否有限制
* @param isNum 是否是数字
* @return
*/
public int solve(char[] w, int idx, boolean isLimit, boolean isNum) {
if (idx == w.length) return isNum ? 1 : 0;
// 返回记忆化缓存结果
if (!isLimit && isNum && this.cache[idx] != -1) return this.cache[idx];
int cnt = 0;
// 高位不选择元素时，比如 1235（4位数） 只构造 3位的数字的结果数
if (!isNum) cnt += solve(w, idx + 1, false, false);
// w[idx] 的上限
int up = isLimit ? (w[idx] - '0') : 9;
// 当前 idx 位置枚举所有可能的值
for (int d = isNum ? 0 : 1; d <= up; d++) {
if (d != 4) cnt += solve(w, idx + 1, isLimit && d == up, true);
}
if (!isLimit && isNum) {
this.cache[idx] = cnt;
}
return cnt;
}
}
C++
#include <bits/stdc++.h>
using namespace std;
const int N=15;
int f[N],n;
string s;
int solve(int i,bool is_limit,bool is_num) {
if(i==n) return is_num;
if (!is_limit && is_num && f[i] != -1) return f[i];
int res=0;
if(!is_num) res=dp(i+1,false,false);
int up=(is_limit)?s[i]-'0':9;
for(int d=1-is_num; d<=up; d++) {
if(4!=d) res+=dp(i+1,is_limit&&d==up,true);
}
if(!is_limit&&is_num) {
f[i]=res;
}
return res;
}
int main() {
cin>>s;
n=s.size();
memset(f,-1,sizeof(f));
cout<<solve(0,true,false)<<endl;
return 0;
}
Python
from functools import cache
@cache
def solve(i, is_limit, is_num):
global s, n
if i == n:
return int(is_num)
res = 0
if not is_num:
res = solve(i + 1, False, False)
up = int(s[i]) if is_limit else 9
for d in range(1 - int(is_num), up + 1):
if d != 4:
res += solve(i + 1, is_limit and d == up, True)
return res
if __name__ == "__main__":
s = input()
n = len(s)
print(solve(0, True, False))
（记忆化搜索）相关练习题
🙏整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏
#校招##秋招##华为##面经##java#
