2023-07-31：用 r、e、d 三种字符，拼出一个回文子串数量等于 x 的字符串。 1 ＜= x ＜= 10^5。来自百度。

作者：福大大架构师每日一题

2023-07-31
北京
本文字数：1728 字
阅读完需：约 6 分钟

2023-07-31：用 r、e、d 三种字符，拼出一个回文子串数量等于 x 的字符串。

1 <= x <= 10^5。

来自百度。

答案 2023-07-31：

大体步骤如下：

1.初始化一个字符串builder，用于构建结果字符串。

2.初始化一个字符变量cur，初始值为'r'，用于轮流使用字符'r'、'e'和'd'构建回文串。

3.进入循环，直到输入的整数 x 变为 0。

4.在循环中，使用near函数找到最接近 x 且满足条件的数值 number。

near函数采用二分法搜索，从 1 开始逐渐增加 m 的值，直到找到满足条件的 m 值。
满足条件是通过ok函数判断，即判断 n 乘以 n+1 再除以 2 是否小于等于 x。
将满足条件的 m 值赋给 ans，并继续搜索更大的 m 值。

5.对于当前找到的 number，使用循环将字符 cur 添加到字符串 builder 中，重复 number 次。

6.计算处理完当前的 number 后，需要减去的值，即 number 乘以(number+1)再除以 2，记为 delta。

7.将 delta 从 x 中减去。

8.根据当前的 cur 字符，顺序更新 cur 为下一个字符。

如果 cur 是'r'，则更新为'e'。
如果 cur 是'e'，则更新为'd'。
如果 cur 是'd'，则更新为'r'。注意，这是一个循环的过程。

9.返回构建好的字符串 builder。

总时间复杂度为 O(x * log(x))，总空间复杂度为 O(1)，其中 x 是输入的值。

go 完整代码如下：

package main
import (    "fmt")
func palindromeX(x int) string {    builder := ""    cur := 'r'    for x > 0 {        number := near(x)        for i := 0; i < number; i++ {            builder += string(cur)        }        x -= number * (number + 1) / 2        if cur == 'r' {            cur = 'e'        } else if cur == 'e' {            cur = 'd'        } else {            cur = 'r'        }    }    return builder}
func near(x int) int {    l := 1    r := x    m, ans := 0, 0    for l <= r {        m = (l + r) / 2        if ok(m, x) {            ans = m            l = m + 1        } else {            r = m - 1        }    }    return ans}
func ok(n, x int) bool {    return int64(n*(n+1)/2) <= int64(x)}
func main() {    x := 13    fmt.Println(palindromeX(x))}

复制代码

rust 完整代码如下：

fn palindrome_x(x: i32) -> String {    let mut builder = String::new();    let mut cur = 'r';    let mut x = x;
    while x > 0 {        let number = near(x);        for _ in 0..number {            builder.push(cur);        }        x -= number * (number + 1) / 2;        cur = match cur {            'r' => 'e',            'e' => 'd',            _ => 'r',        };    }
    builder}
fn near(x: i32) -> i32 {    let mut l = 1;    let mut r = x;    let mut ans = 0;
    while l <= r {        let m = (l + r) / 2;        if ok(m, x) {            ans = m;            l = m + 1;        } else {            r = m - 1;        }    }
    ans}
fn ok(n: i32, x: i32) -> bool {    (n * (n + 1) / 2) <= x}
fn main() {    let x = 13;    println!("{}", palindrome_x(x));}

复制代码

c++完整代码如下：

#include <iostream>#include <string>
int near(int x);
std::string palindromeX(int x) {    std::string result;    char cur = 'r';    while (x > 0) {        int number = near(x);        for (int i = 0; i < number; i++) {            result += cur;        }        x -= number * (number + 1) / 2;        cur = (cur == 'r') ? 'e' : (cur == 'e') ? 'd' : 'r';    }    return result;}
bool ok(int n, int x);
int near(int x) {    int l = 1;    int r = x;    int m, ans = 0;    while (l <= r) {        m = (l + r) / 2;        if (ok(m, x)) {            ans = m;            l = m + 1;        }        else {            r = m - 1;        }    }    return ans;}
bool ok(int n, int x) {    return ((long long)n * (n + 1) / 2) <= x;}
int main() {    int x = 13;    std::cout << palindromeX(x) << std::endl;    return 0;}