牛牛恨66

[编程题]牛牛恨66

热度指数：1504 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

众所周知，牛牛不喜欢6这个数字（因为牛牛和66发音相近）

所以他想知道，不超过n位十进制数中有多少个数字不含有连续的6（从1开始算的）

输入只包含一个正整数n（1<=n<20）

示例1

输入

输出

"10"

说明

1，2,3,4,5,6,7,8,9,10 这十个数字中都满足条件

示例2

输入

输出

"99"

说明

因为66不可以

算法知识视频讲解

C/C++

nbgao

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return string字符串
     */

    string calculate(int n) {
        long f[21] = {0, 10, 99};
        for(int i=3;i<20;i++)
            f[i] = (f[i-1]+f[i-2])*9;
        return to_string(f[n]);
    }
};

发表于 2020-08-28 20:03:55 回复(0)

这个双月的OKR是脱单。。。

打表

import java.util.*;

public class Solution {
    static String[] RCD = new String[]{
            "0",
            "10",
            "99",
            "981",
            "9720",
            "96309",
            "954261",
            "9455130",
            "93684519",
            "928256841",
            "9197472240",
            "91131561729",
            "902961305721",
            "8946835807050",
            "88648174014939",
            "878355088397901",
            "8703029361715560",
            "86232460051021149",
            "854419404714630381",
            "8465866782890863770"
    };

    public String calculate(int n) {
       return RCD[n];
    }
}

发表于 2020-03-21 09:37:06 回复(6)

.晚安

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return string字符串
     */
    string calculate(int n) {
        vector<vector<long>> a(n + 1, vector<long>(2));
        a[0] = {1, 0};
        for (int i = 1; i <= n; i++) a[i] = {9 * (a[i - 1][0] + a[i - 1][1]), a[i - 1][0]};
        return to_string(a[n][0] + a[n][1]);
    }
};

编辑于 2020-07-24 17:04:31 回复(0)

xiaoghggghgg

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串
     */
    public String calculate (int n) {
        // write code here
        long dp[] = new long[n+1];
        dp[1]=10;
        dp[2]=99;
        for(int i=3;i<=n;i++){
            dp[i] = (dp[i-1]+dp[i-2])*9;
        }
        
        Long count = dp[n];
        return count.toString();
        
    }
}

感谢题解

发表于 2020-07-22 17:39:12 回复(0)

offerPlusPlus_

import java.util.*;
import java.math.BigInteger;

public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串
     */
    public String calculate (int n) {
        // write code here
        //F(1)=0;F(2)=1;F(n)=9(F(n-1)+F(n-2))+10^(n-2);
        BigInteger[] res=new BigInteger[n+1];
        res[1]= BigInteger.valueOf(0);
        res[2]= BigInteger.valueOf(1);
        for(int i=3;i<=n;i++){
            BigInteger pow=BigInteger.valueOf((long)Math.pow(10,i-2));
            res[i]=BigInteger.valueOf(9).multiply(res[i-1].add(res[i-2])).add(pow);
        }
        String result=pow(n).subtract(res[n])+"";
        return result;
    }
    public static BigInteger pow(int n){
        BigInteger temp=BigInteger.valueOf(10);
        for (int i = 1; i < n; i++) {
            temp=temp.multiply(BigInteger.valueOf(10));
        }
        return temp;
    }
}

动态规划，状态转移方程：F(1)=0;F(2)=1;F(n)=9(F(n-1)+F(n-2))+10^(n-2);

求得含有连续6的数目，再用10^n减去之即得最后结果

发表于 2020-03-23 13:35:10 回复(0)

牛客255818873号

class Solution:
    def calculate(self , n ):
        # write code here
        a = [10, 99]
        if n <= 2:
            return a[n - 1]
        for i in range(2, n):
            count = 9 * sum(a[-2:])
            a.append(count)
        return count

发表于 2020-03-23 05:05:22 回复(1)

嗯学

数位dp直接套模板。。。注意数据类型要用long long ，这可能也是为什么题目让返回字符串的原因吧。

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return string字符串
     */
    long long memo[30][2];//记忆化递归
    long long dfs(int cur, bool g){//cur代表当前是第几位数，g代表上一位是否是6
        if(cur == 0) return 1;
        if(memo[cur][g]) return memo[cur][g];
        long long ans = 0;
        for(int i = 0; i <= 9; ++i){
            if(g && i == 6) continue;
            ans += dfs(cur-1, i == 6);
        }
        return memo[cur][g] = ans;
    }
    string calculate(int n) {
        // write code here
        memset(memo, 0, sizeof memo);
        return to_string(dfs(n, false));
    }
};

编辑于 2020-03-12 01:46:41 回复(0)