0基础 网站建设百度站长提交网址
靠谱的车- 华为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, 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))
（记忆化搜索）相关练习题
| 题号 | 题目 | 难易 |
|---|---|---|
| LeetCode 600 | 600. 不含连续1的非负整数 | 困难 |
| LeetCode 473 | 473. 火柴拼正方形 | 中等 |
🙏整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏