Codejam之Tidy Numbers

本文主要是介绍Codejam之Tidy Numbers，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述

8，123，555，224488这种数字以非递减的顺序排列的叫做tidy numbers

20，321，495，99999990这种不是

给一个值，要求输出该值之前的最后一个tidy number

问题解决

大数据集中的测试用例如下，如果将值逐次减一，判断是否符合要求太没有效率。

可以遍历数字串，找到第一个nums[i]>nums[i+1]的位置，将nums[i]的值减一，后面的值都赋值9

nums[i]的值减一后，其前面的值可能大于nums[i]，再次检查。

也可以直接找i前面等于nums[i]的最左边的位置

811112333445578899
999999999999999999
430315219406019114
11333445538
10999999999
21233455667777788
839744037703188439

int[] nums = new int[aline.length()];
for(int i=0;i<aline.length();i++)nums[i]=aline.charAt(i)-48;int index = check(nums,0,nums.length-1);
while(index!=-1){index = check(nums,0,index);
}String res = "";
int start = 0;
//处理09999这种情况，把前面的0去掉
while(nums[start]==0){start++;
}
for(int i=start;i<nums.length;i++){res+=nums[i];
}   
writer.write("Case #"+k+": "+res+'\n');

check的实现

private static int check(int[] nums,int lo,int hi){int index = -1;for(int i=lo;i<hi;i++){if(nums[i]>nums[i+1]){nums[i]=nums[i]-1;for(int j=i+1;j<=hi;j++)nums[j]=9;index=i;break;}}return index;
}

1332
第一次check(0,3)后，返回的index=2
1329
check(0,2)后，返回index=1
1299
check(0,1)，返回index=-1，终止循环

这篇关于Codejam之Tidy Numbers的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---