【算法刷题】——美丽整数的最小增量
admin
2024-04-01 23:19:47
0次

美丽整数的最小增量

1.题目描述

原题入口

给你两个正整数 n 和 target 。
如果某个整数每一位上的数字相加小于或等于 target ,则认为这个整数是一个 美丽整数 。
找出并返回满足 n + x 是 美丽整数 的最小非负整数 x 。生成的输入保证总可以使 n 变成一个美丽整数。

示例 1:
输入:n = 16, target = 6 输出:4 解释:最初,n 是 16 ,且其每一位数字的和是 1 + 6 = 7 。在加 4
之后,n 变为 20 且每一位数字的和变成 2 + 0 = 2 。可以证明无法加上一个小于 4 的非负整数使 n 变成一个美丽整数。

提示:

  • 1 <= n <= 10^12
  • 1 <= target <= 150
  • 生成的输入保证总可以使 n 变成一个美丽整数。

2.解题思路

题目描述很容易读懂,给定一个数n,要求n加上一个最小的数 相加之后的数各个数位之和小于 target。最容易想到的思路就是暴力穷举,一直加1直到符合条件。但是看题目数据量 n是12次方的,穷举肯定就超时了。
换一种思路,如何把一个数位的数变小,只能加。很容易想到只要进位变成0,那么这个数位的数就减少了。比如 734504727 10 这个测试示例,我们从低位到高位 每个数位都变成0 一直到符合条件为止。因此我们需要一个集合存储n的各个数位,这样方便进行数位和、相加的数大小的计算。

734504727 39
734504730 33
734504800 31
734505000 24
734510000 20
734600000 20
735000000 15
740000000 11
800000000 8

3.代码实现

class Solution {// 记录每一位的数List list = new ArrayList<>();public long makeIntegerBeautiful(long n, int target) {// 记录当前各位数之和int ans = add(n);//如果本身就符合条件直接返回0if(ans  <= target) return 0L;//记录加的数long res = 0L;//当前到哪一位int idx = 0;while (idx < list.size() && ans > target){//当前位变0  注意 list存储的是进位前的数位 进位后都要加1 ans = ans - list.get(idx) + (idx == 0 ? 1 : 0) ;//加的数字  除了最后一位其余的都进位了,但是list集合中没有更新,因此需要再-1res += ((10-list.get(idx) - (idx == 0 ? 0 : 1)) * Math.pow(10,idx));idx++;}return res;}int add(long n){int num = 0;while( n!= 0){num += n % 10;list.add((int) (n % 10));n /= 10;}return  num;}
}

相关内容

热门资讯

蜻蜓订购APP贵金属订购非法期...   蜻蜓订购APP以"投资平台"名义对外宣传,主打贵金属期货(订购)交易。该平台一方面强调自身"正规...
悟空订购APP非法期货交易欺骗...   近期,有投资者反映,“悟空订购APP”等平台以白银、贵金属订购为名,宣传所谓“高收益”“低门槛”...
小赢淘金APP期货投资骗局,平...   “小赢淘金”之流,最擅长的就是用“注册送现金”、“充值返券”的糖衣炮弹来引流。别天真地以为那是福...
八方淘金APP非法期货交易欺骗...   警惕!八方生财、每日淘金、小赢淘金、悟空订购、蜻蜓订购、斗金订购等APP均涉嫌非法期货交易!  ...
智易购APP贵金属订购交易骗局...   很多人看到“3元起投”“充值送福利”“操作简单”“随时提现”这类宣传,很容易把智易购APP当成普...
喜玛银庄APP商品订购投资骗局...   喜玛银庄APP白银、铂金“现货订购”骗局警示:无资质平台涉嫌非法期货交易,投资者爆仓后如何维权?...
吉鑫乐享APP炒贵金属订购交易...   近期,多名投资者反映在“吉鑫乐享APP”进行贵金属投资时遭遇严重亏损,甚至血本无归。看似正规的“...
易掘金APP虚假期货投资骗局,...   “易掘金”的APP它打着“高收益、灵活投资”的旗号,宣称通过“商品订购”就能轻松赚钱,吸引了不少...
在大吉订购APP订购交易亏损被...   近期,不少投资者反映在“大吉订购App”上投资白银、铂金等商品遭遇严重亏损。该平台宣称提供现货订...
铂银壹号APP商品订购交易亏损...   许多中小投资者误以为网上的“商品现货订购”是合规合法的理财渠道,殊不知这背后隐藏着巨大的合规风险...
兴鑫淘金APP贵金属订购交易亏...   白银、贵金属或其他商品类投资,除国家批准的正规期货交易场所及持牌期货公司外,市面上大量第三方交易...
铂银掘金APP无资质的违规平台...   铂银掘金等平台的投资者,往往是被“注册送现金”“充值返现券”“首单免亏”等广告话术吸引,进而下载...
八方淘金APP订购交易不合规,...   “八方淘金APP”“铂银掘金APP”“铂银壹号APP”等软件被指以“现货订购”为名,实际采用高杠...
在指尖订购APP订购商品亏损被...   指尖订购APP这类平台,表面是“订购交易”,实则是披着电商外衣的非法期货陷阱。绝大多数投资者被蒙...
在犀贝易购APP做商品订购交易...   市面上打着“现货投资”“贵金属交易”旗号的APP并不少,但真正合规、受监管的平台并不多。犀贝易购...
易达淘金APP虚假商品订购交易...   易达淘金APP存在严重的虚假宣传与违规交易行为。该平台打着“商品订购”的旗号,实则通过不合规的交...
大浪淘金APP白银订购亏损被骗...   大浪淘金APP最隐蔽的套路,在于其完全封闭的内盘交易系统。表面上,它宣称与国际贵金属市场接轨;实...
一品好购APP上订购白银出现亏...   一品好购APP原名“一品订购”,运营方为上海宝智未来信息技术有限公司。近期不少投资者反映在该平台...
九州订购APP贵金属订购投资骗...   九州订购APP正通过抖.音、快手、今日头条等平台大量投放投资广告,用“5元起投”“充值返现”“0...
坚锅淘金APP交易软件并不正规...   当前,市面上大量所谓的“现货商城订购”交易软件,早已偏离了正常的实物商品买卖,演变为高杠杆、高手...