吉比特编程题第二题(2018数)代码

记忆化搜索:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
int dp[12][5];
int digit[12];
const int a2018[4] = {2, 0, 1, 8};
int dfs(int pos, int i, bool limit) {
    if(pos==-1) {
        return i == 4;
    }
    if(!limit && dp[pos][i]!=-1) {
        return dp[pos][i];
    }
    int ans = 0;
    int up = limit? digit[pos] : 9;
    for(int j = 0; j <= up; ++ j) {
        if(j == a2018[i]) {
            ans += dfs(pos-1, i+1, limit&(j==up));
        }
        else {
            ans += dfs(pos-1, i, limit&j==up);
        }
    }
    if(!limit) {
        dp[pos][i] = ans;
    }
    return ans;
}
int f(int n) {
    int len = -1;
    while(n) {
        digit[++len] = n%10;
        n /= 10;
    }
    return dfs(len, 0, true);
}
int main() {
    int n;
    while(~scanf("%d", &n)) {
        memset(dp, -1, sizeof(dp));
        printf("%d\n", f(n));
    }
    return 0;
}

update:这题是数位dp问题,上面的代码用的时记忆化搜索,思路就是把小于等于n的数都搜一遍,但是有很多结果是重复的,所以加个数组把每次计算出的结果都保存下来,比如要找小于55555555的“2018”数,那么以13开头的13xxxxxx和以14开头的14xxxxxx的“2018”数的个数是一样的;大家可以网上找找数位dp的入门帖子学学。

#吉比特#
全部评论
import java.util.Scanner; /**  * Created by jia on 2018/9/3.  */ public class Main {     public static void main(String[] args) {             Scanner sc = new Scanner(System.in);             String x   = sc.nextLine();             int num = Integer.valueOf(x);             int count = 0;            if (num < 1000000000){                 while(num >999){                     char [] arr = String.valueOf(num).toCharArray();                     StringBuilder str = new StringBuilder();                     for(int i = 0; i < arr.length;i++ ){                         if(arr[i] == '2'){                             str.append("2");                         }                         if(arr[i] == '0'){                             str.append("0");                         }                         if(arr[i] == '1'){                             str.append("1") ;                         }                         if(arr[i] =='8' ){                             str.append("8");                         }                     }                     if (str.toString().equals("2018")){                         count++;                     }                     num --;                 }             }         System.out.print(count);     } }
点赞 回复
分享
发布于 2018-09-10 00:23
大佬啊,很强
点赞 回复
分享
发布于 2018-09-03 20:58
微众银行
校招火热招聘中
官网直投
有题目么
点赞 回复
分享
发布于 2018-09-03 21:01
大佬!
点赞 回复
分享
发布于 2018-09-03 21:02
大佬,可以提供个思路吗?直接代码不懂啊
点赞 回复
分享
发布于 2018-09-03 21:05
大佬强
点赞 回复
分享
发布于 2018-09-03 21:06
大佬能稍微解释一下吗,看不懂啊
点赞 回复
分享
发布于 2018-09-03 21:08
小于等于 是怎么做到的
点赞 回复
分享
发布于 2018-09-03 21:17
题目来了
点赞 回复
分享
发布于 2018-09-03 21:42
大佬,选择题160个箱子,轮流取1-5,a第一个取多少可以保证一定可以取到160,这道题怎么解,谢谢大佬
点赞 回复
分享
发布于 2018-09-04 08:13
 public static void method_1_1(int n){   int []stack={2, 0, 1, 8};   int index=0;   //统计2018数的个数   int count=0;   //遍历   for(int i=2018; i<=n; i++){    String s=i+"";    //遍历这个数    for(int j=0; j<s.length(); j++){     if((s.charAt(j)-'0')==stack[index]){      index++;      //如果找到了2018数      if(index==4){       count++;       break;      }     }    }    index=0;   }   System.out.println(count);    }
点赞 回复
分享
发布于 2018-09-05 16:35
我这种菜鸡做法对不,测试数据是多少
点赞 回复
分享
发布于 2018-09-10 00:25
结果不对啊根本
点赞 回复
分享
发布于 2019-04-10 21:26

相关推荐

发个腾讯的吧,刚面完,以为是kpi,所以没录音,能写多少是多少点击查看详情自我介绍介绍项目1.java和其他语言的区别,比如c++,python,各个方面2.知道几种编程思想,比如面向对象等等3.知道的设计模式4.jvm结构、垃圾回收算法5.乐观锁CAS6.数据结构了解哪些7.排序算法呢,说一下快排,时间复杂度。空间复杂度8.计网1.OSI七层,作用2.http状态码,502如何查找排除3.http报文结构4.https的过程,三次握手,TLS四次握手等等,认证过程5.了解过哪些加密算法,什么是对称加密和非对称加密6.cookie和session了解过吗,区别,集群里,session在一个服务器,请求分配到了其他服务器,怎么解决这种情况说了一些以后,提示我想想redis、mysql7.websocket了解过吗,。。。。我不知道8.http有哪些请求方法,然后给我个场景,问我怎么解决,具体忘了,反正他最后引导我是用head(应该)9.ping用过吗,基于什么协议10.DNS解析过程、我还说了两种方法,递归,迭代,问我迭代体现在哪11.DOS攻击是什么12.TCP三次握手。四次挥手,各阶段的状态,为什么要三次握手、四次挥手,状态那还问我,SYN_RECV之前服务器是什么状态13.为什么要等待2MSL14.TCP&nbsp;&nbsp;&nbsp;UDP区别、应用场景,问我,游戏用的是什么,腾讯会议呢?我答是QUIC,不晓得对不对15.我看你这是个前后端分离项目,那么跨域问题怎么解决。我不知道。。。。16.静态资源问题,后面提醒我用CDN17.TCP拥塞控制四个过程。TCP滑动窗口了解过吗,讲一下18.TCP、UDP格式操作系统1.内核态、用户态,切换方式2.进程线程,区别、协程了解过吗(协程不知道)3.一个进程,你发现cup使用率很高,你怎么排查,我猜与协程有关,就往这方面答了4.一个线程阻塞到这里了,你怎么解决,我还是从协程方面5.进程间通信方式。调度算法6.虚拟内存了解过吗7.分段分页的调度算法8.OOM了解过吗,怎么排查,怎么解决9.什么是死锁,如何避免、解决redis、mysql1.redis持久化机制2.redis的数据结构3.其他想不起来了。。。。字数超了 #腾讯#&nbsp;#腾讯一
点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务