靠谱的车- 华为OD统一考试（C卷）

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

alt

题目描述

程序员小明打了一辆出租车去上班。出于职业敏感，他注意到这辆出租车的计费表有点问题，总是偏大。

出租车司机解释说他不喜欢数字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, nif i == n:return int(is_num)res = 0if not is_num:res = solve(i + 1, False, False)up = int(s[i]) if is_limit else 9for d in range(1 - int(is_num), up + 1):if d != 4:res += solve(i + 1, is_limit and d == up, True)return resif __name__ == "__main__":s = input()n = len(s)print(solve(0, True, False))