当前位置: 首页 > news >正文

力扣 每日一题 902. 最大为 N 的数字组合【难度:困难,rating: 1989】(数学 / 数位dp)

题目链接

https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/

题目来源于:第101场周赛 Q3 rating: 1989

思路一(数学)

设 n 的位数(长度)为 len_n,digits 的长度为 len_d,那么长度小于 len_n 的从 digits 中取出的所有任意组合均满足条件,方案数: ∑ i = 1 l e n _ n − 1 ( l e n _ d ) i \sum_{i=1}^{len\_n-1} {(len\_d)}^i i=1len_n1(len_d)i

接着处理长度相等的组合情况。

  1. 依次找到 n 的每一位数字在 digits 数组中的大概位置 k ,比 k 的所有 digits 数构成的任意组合均满足条件。
  2. 判断 digits 数组中位置 k 的数字与 n 的该位数字是否相等,如果相等则接着遍历 n 的下一位数字,继续比较;否则结束比较。
  3. 当遍历到 n 的最后一位数字时,比 k 小于等于的所有 digits 数均满足条件。

代码一

class Solution {
	int qpow[11]={0}; // len_d^i
    int base[11]={0}; // len_d^1 + len_d^2 +...+ len_d^i
public:
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        int len_d=digits.size();
        base[0]=0;
        qpow[0]=1;
        for(int i=1;i<=9;i++){
            qpow[i]=qpow[i-1]*len_d; // len_d^i
            base[i]=base[i-1]+qpow[i]; // base[i]表示小于10^i的所有方案,即长度小于等于i的所有方案
        }

        vector<int> digits_int;
        for(const string &s:digits){
            digits_int.push_back(s[0]-'0');
        }

        string str_n=to_string(n);
        int len_n=str_n.size();
        int ans=base[len_n-1]; // 长度小于len_n的方案数
        for(int i=0;i<len_n;){
            char c=str_n[i];
            int x=c-'0'; // x是n的第i位的数字
            if(i!=len_n-1){
                // k是digits中小于x的位数
                int k=lower_bound(digits_int.begin(),digits_int.end(),x)-digits_int.begin();
                ans+=k*qpow[len_n-i-1];
                if(k!=len_d&&digits_int[k]==x){  // 当前位置数字相等
                    i++; // 继续找下一位,继续比较
                }else{
                    break; // 否则结束比较
                }
            }else{
                // 到达最后一位
                // k是digits中小于等于x的位数
                int k=upper_bound(digits_int.begin(),digits_int.end(),x)-digits_int.begin();
                ans+=k;
                break;
            } 
        }
        return ans;
    }
};

/*
["3","4","8"]
4
ans: 2

["5","7","8"]
59
ans: 6

["1","4","5","6","7","8"]
52
ans: 19

["1"]
834
ans: 3
*/

思路二(数位dp)

待补

代码二

相关文章:

  • 网站建设手机源码/seo入门培训课程
  • wordpress图片加载非常久/最新域名查询ip
  • 网站建设 温州/seo网站优化案例
  • 云盘建设网站/十大流量平台
  • 网站如何做微信推广/万能搜索 引擎
  • 长春建站模板源码/网页设计大作业
  • 奇迹mu服务器安全和优化设置
  • OC 基础 导航栏UITabBarController的使用(源码)
  • 人脸识别项目FFmpeg+OpenCV+虹软SDK
  • ITRS 与 GCRS 之间的坐标转换
  • 【图像重建】基于matlab SIDER算法图像压缩重建【含Matlab源码 2170期】
  • 多线程同步-条件变量
  • JS(第八课)循环语句中常用到的案例
  • 2022软考高项十大领域知识整理(四)-人力资源管理、干系人管理、采购管理
  • 深度学习基础之BatchNorm和LayerNorm
  • 【Spring】面向切面编程详解(AOP)
  • 力扣(LeetCode)75. 颜色分类(C语言)
  • LeetCode算法题整理(200题左右)