leetcode 中等难度中比较简单的一个,题目描述点击这里。读完描述可将本题精简为如下内容:
给两个整数 n 和 k,返回序列长度为 n 且数字和等于 k 的一个数字序列(每个数字的范围为 1-26,对应 26 个字母),要求小的数字尽量放前面.
看到尽量小的数字放在前面且数字和是固定的,我们就应该想到可以用贪心算法来解决这个问题,思路如下: 设定 i=1,s=1
java 代码见:点击这里,translateNum1 方法
进一步思考会发现上面的解法存在存在很多的循环,效率不高,能否优化?
当然可以,我们并不需要每次+1 后再判断能否满足需求,一次计算即可计算出当前位置最小能填入多少,流程如下:设定 i=1,sum=0
java 代码见:点击这里,translateNum 方法
本文解法是将尽量小的数字填到前面,另外一种思路正好相反,将尽量大的数字填到后面,可自行尝试。
另外本体可换一种描述,要求数字序列拼成的数字最小,比如['12','32']拼成 1232,也是一样的解法。