靠谱的车- 华为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

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

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))