松江网站建设培训费用,浙江省杭州市建设厅网站,年栾洪全单页做网站教程,wordpress 预缓存靠谱的车- 华为OD统一考试#xff08;C卷#xff09; OD统一考试#xff08;C卷#xff09; 分值#xff1a; 100分 题解#xff1a; Java / Python / C 题目描述
程序员小明打了一辆出租车去上班。出于职业敏感#xff0c;他注意到这辆出租车的计费表有点问题#xf…靠谱的车- 华为OD统一考试C卷 OD统一考试C卷 分值 100分 题解 Java / Python / C 题目描述
程序员小明打了一辆出租车去上班。出于职业敏感他注意到这辆出租车的计费表有点问题总是偏大。
出租车司机解释说他不喜欢数字4所以改装了计费表任何数字位置遇到数字4就直接跳过其余功能都正常。
比如 23再多一块钱就变为25 39再多一块钱变为50 399再多一块钱变为500
小明识破了司机的伎俩准备利用自己的学识打败司机的阴谋。
给出计费表的表面读数返回实际产生的费用。
输入描述
只有一行数字N表示里程表的读数。
(1N888888888)。
输出描述
一个数字表示实际产生的费用。以回车结束。
示例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;// 高位不选择元素时比如 12354位数 只构造 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 N15;
int f[N],n;
string s;int solve(int i,bool is_limit,bool is_num) {if(in) return is_num;if (!is_limit is_num f[i] ! -1) return f[i];int res0;if(!is_num) resdp(i1,false,false);int up(is_limit)?s[i]-0:9;for(int d1-is_num; dup; d) {if(4!d) resdp(i1,is_limitdup,true);}if(!is_limitis_num) {f[i]res;}return res;
}int main() {cins;ns.size();memset(f,-1,sizeof(f));coutsolve(0,true,false)endl;return 0;
}Python
from functools import cachecache
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 600600. 不含连续1的非负整数困难LeetCode 473473. 火柴拼正方形中等
整理题解不易 如果有帮助到您请给点个赞 ❤️ 和收藏 ⭐让更多的人看到。
