15天大厂真题带刷 - ZT8 小红的字符生成 | Go
小红的字符生成
https://www.nowcoder.com/practice/f8659377ca104b1aad45dd2fb564c940
题意
每次可以把一个字符变成两个字母表中比它小一位的字符希望最终可以生成 xx 个'a'，求长度最短的初始字符串
思路
1个b可以变为2个a，1个c可以变为2个b也就是4个a，1个d可以变成2个c=4个b=8个a
可以观察出，数量的规律是2的次方
题目要求长度最短，所以从z开始倒序遍历，看能否使用当前的字符来构造字符串
Go代码
package main
import (
"fmt"
)
func main() {
var x int
fmt.Scan(&x)
//最后生成x个a
//b => 2a
//c => 2b => 4a
//d => 2c => 4b => 8a
//实际上是2的次方
pow2 := make([]int,30)
pow2[1] = 1
for i := 2; i <= 26; i ++ {
pow2[i] = pow2[i-1] * 2
}
for i := 26; i >= 1; i-- {
now := pow2[i]
if x/now > 0 {
for j := 1; j <= x/now; j++ {
fmt.Print(string(rune(i - 1 + 'a')))
}
x = x % now
}
if x == 0 {
break
}
}
}
#牛客创作赏金赛#15天大厂真题带刷Go题解 文章被收录于专栏
15天大厂真题带刷Golang题解
