域名备案查询网站备案信息,短视频app推荐,seo站长工具箱,wordpress主分类题目
给你两个数字字符串 num1 和 num2 #xff0c;以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件#xff0c;我们称它是一个好整数#xff1a; num1 x num2 min_sum digit_sum(x) max_sum. 请你返回好整数的数目。答案可能很大以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件我们称它是一个好整数 num1 x num2 min_sum digit_sum(x) max_sum. 请你返回好整数的数目。答案可能很大请返回答案对 109 7 取余后的结果。 注意digit_sum(x) 表示 x 各位数字之和。 示例 1 输入num1 “1”, num2 “12”, min_num 1, max_num 8 输出11 解释总共有 11 个整数的数位和在 1 到 8 之间分别是 1,2,3,4,5,6,7,8,10,11 和 12 。所以我们返回 11 。 示例 2 输入num1 “1”, num2 “5”, min_num 1, max_num 5 输出5 解释数位和在 1 到 5 之间的 5 个整数分别为 1,2,3,4 和 5 。所以我们返回 5 。 提示 1 num1 num2 1022 1 min_sum max_sum 400
分析
a. 先考虑数位相等
DoSameLen函数处理数位相等。用动态规划假定已经处理了i位正在处理第i位。对于某种状态我们只关心一位数和取值范围[0, max_sum]共max_sum1种大于max_sum的状态抛弃。二上下界。非边界、上边界、下边界、上下界。如num1”121”,num2”142”则”1”是上下界12是下界13是非边界、14是上边界。如果上下界则当前位只能取值[num1[i],nums2[i]]。如果上边界则只能取值[0,nums2[i]]。如果是下边界则能取[nums1[i],9]。如果是非边界则可以任意取值。
前一轮状态当前条件新状态上下界同时等于num1[i]和num2[i]上下界上下界等于num1[i]下界上下界等于num2[i]上界上下界num1[i]和num2[i]之间非边界上界等于num2[i]上界上界小于num2[i]非边界下界等于num1[i]下界下界大于num1[i]非边界非边界0到9非边界
b. 优化掉上下界
上下界一定出现再最前面且数量为1。当i为0时有新的上下界那说明num1[0]和num2[i]只能选择num1[i]。当i大于0是有新的上下界那么num1[i]等于num2[i]由于(i-1)也是上下界所有num1和num2的前i1个元素相同。由于第i为只能num1[i]所以数量不变。 假定num1和num2的前i位完全相同则前i位只有一个合法数。 这意味这num1和num2扔掉相同的前者边界状态的数量不变。比如 num1 “112”和num2 “115” 下界115非边界:113和114 上界115。 num1 “12”和num2 “15” 下界15非边界:13和14 上界15。 num1 “2”和num2 “5” 下界5非边界:3和4 上界5。
c. 考虑数位不等
假定num1的长度为l1,num2的长度为l2则分别: Do(num1,string(l1,’9’) for(int i l11; i l2 ;i) { Do(‘1’string(i-1,’0’),string(i,’9’); } Do(‘1’string(i2-1,’0’),num2) 比如 nums1 “1”,nums2”19” Do(“1”,”9”) Do(“10”,”19”) 再如 nums1 “1”,nums2”123” Do(“1”,”9”) Do(“10,”99”) Do(“100,”123”) 注意 l1等于l2时要分别处理。
核心代码
class Solution { public: int count(string num1, string num2, int min_sum, int max_sum) { m_min_sum min_sum; m_max_sum max_sum; const int l1 num1.length(); const int l2 num2.length(); if (l1 l2) { return DoSameLen(num1, num2).ToInt(); } C1097Int biRet; biRet DoSameLen(num1, string(l1, ‘9’)); for (int i l1 1; i l2; i) { biRet DoSameLen(“1” string(i - 1, ‘0’), string(i,‘9’)); } biRet DoSameLen(“1” string(l2-1,‘0’), num2); return biRet.ToInt(); } C1097Int DoSameLen(string num1, string num2) { int n num1.size();//只处理相等位数 int i 0; int sum 0; for (; (i n) (num1[i] num2[i]); i) { sum num1[i] - ‘0’; } if (i n) { return ((sum m_min_sum)( sum m_max_sum)) ? 1 : 0; } //注[1] vectorvectorC1097Int pre(3, vectorC1097Int(m_max_sum1)); Set(pre, 1, sum num1[i]-‘0’, 1); for (int j num1[i] 1; j num2[i]; j) { Set(pre, 0, sum j - ‘0’, 1); } Set(pre, 2, sum num2[i] - ‘0’, 1); for (i; i n; i) { vectorvectorC1097Int dp(3, vectorC1097Int(m_max_sum 1)); for (int preSum 0; preSum m_max_sum; preSum) { //处理下界 Set(dp, 1, preSum num1[i] - ‘0’, pre[1][preSum]); for (int j num1[i] 1; j ‘9’; j) { Set(dp, 0, preSum j - ‘0’, pre[1][preSum]); } //处理无边界 for (int j ‘0’; j ‘9’; j) { Set(dp, 0, preSum j - ‘0’, pre[0][preSum]); } //处理上界 for (int j ‘0’; j num2[i]; j) { Set(dp, 0, preSum j - ‘0’, pre[2][preSum]); } Set(dp,2, preSum num2[i] - ‘0’, pre[2][preSum]); } pre.swap(dp); } return Cal(pre); } void Set(vectorvectorC1097Int dp, int status, int sum,C1097Int iAddNum) { if (sum m_max_sum) { return; } dp[status][sum] iAddNum; } C1097Int Cal(const vectorvectorC1097Int pre) { C1097Int biRet; for (int i 0; i 3; i) { for (int j m_min_sum; j m_max_sum; j) { biRet pre[i][j]; } } return biRet; } int m_min_sum, m_max_sum; };
测试代码
int main() { int res 0; res Solution().count(“2”, “5”, 0, 100); assert(res 4); res Solution().count(“12”, “15”, 0, 100); assert(res 4); res Solution().count(“112”, “115”, 0, 100); assert(res 4); res Solution().count(“112”, “115”, 5, 100); assert(res 3); res Solution().count(“112”, “115”, 0, 6); assert(res 3); res Solution().count(“112”, “115”, 5, 6); assert(res 2); res Solution().count(“1”, “12”, 1, 8); assert(res 11);
CConsole::Out(res);}
其它
视频课程
如果你觉得复杂想从简单的算法开始可以学习我的视频课程。 https://edu.csdn.net/course/detail/38771 我的其它课程 [https://edu.csdn.net/lecturer/6176]
(https://edu.csdn.net/lecturer/6176)
测试环境
win7 VS2019 C17
相关下载
算法精讲《闻缺陷则喜算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
