题解 | #小红的字符生成#
小红的字符生成
https://www.nowcoder.com/practice/f8659377ca104b1aad45dd2fb564c940
解题思路
这是一道从结果反推构造的题目。我们需要从目标数量的'a'开始，反向思考如何构造原始字符串。 关键思路：
- 从高位字母开始构造，每个字母可以分裂成两个小一位的字母
- 需要找到最小的字母位置k，使得2^k ≥ x
- 从k位置开始，逐步处理剩余数量，必要时添加较小位置的字母
代码
#include <iostream>
#include <string>
using namespace std;
int main() {
long long x;
cin >> x;
string ans;
// 找到最高位
int k = 0;
long long pow2 = 1;
while(pow2 < x) {
k++;
pow2 *= 2;
}
// 从高位往低位构造
while(x > 0) {
while(k >= 0 && (1LL << k) > x) {
k--;
}
if(k < 0) break;
ans += (char)('a' + k);
x -= (1LL << k);
}
if(x == 0) cout << ans << endl;
else cout << -1 << endl;
return 0;
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long x = sc.nextLong();
StringBuilder ans = new StringBuilder();
// 找到最高位
int k = 0;
long pow2 = 1;
while(pow2 < x) {
k++;
pow2 *= 2;
}
// 从高位往低位构造
while(x > 0) {
while(k >= 0 && (1L << k) > x) {
k--;
}
if(k < 0) break;
ans.append((char)('a' + k));
x -= (1L << k);
}
System.out.println(x == 0 ? ans.toString() : -1);
}
}
x = int(input())
ans = []
# 找到最高位
k = 0
pow2 = 1
while pow2 < x:
k += 1
pow2 *= 2
# 从高位往低位构造
while x > 0:
while k >= 0 and (1 << k) > x:
k -= 1
if k < 0:
break
ans.append(chr(ord('a') + k))
x -= (1 << k)
print(''.join(ans) if x == 0 else -1)
算法及复杂度
- 算法：贪心构造。从最高位开始，逐步构造字符串。
- 时间复杂度：
，主要是找到最高位和构造过程。
- 空间复杂度：
