2023-07-31：用r、e、d三種字符，拼出一個(gè)回文子串?dāng)?shù)量等于x的字符串。

1 <= x <= 10^5。

來自百度。

答案2023-07-31：

大體步驟如下：

1.初始化一個(gè)字符串builder，用于構(gòu)建結(jié)果字符串。

2.初始化一個(gè)字符變量cur，初始值為'r'，用于輪流使用字符'r'、'e'和'd'構(gòu)建回文串。

3.進(jìn)入循環(huán)，直到輸入的整數(shù)x變?yōu)?。

4.在循環(huán)中，使用near函數(shù)找到最接近x且滿足條件的數(shù)值number。

• ??near函數(shù)采用二分法搜索，從1開始逐漸增加m的值，直到找到滿足條件的m值。

• ??滿足條件是通過ok函數(shù)判斷，即判斷n乘以n+1再除以2是否小于等于x。

• ??將滿足條件的m值賦給ans，并繼續(xù)搜索更大的m值。

5.對(duì)于當(dāng)前找到的number，使用循環(huán)將字符cur添加到字符串builder中，重復(fù)number次。

6.計(jì)算處理完當(dāng)前的number后，需要減去的值，即number乘以(number+1)再除以2，記為delta。

7.將delta從x中減去。

8.根據(jù)當(dāng)前的cur字符，順序更新cur為下一個(gè)字符。

• ??如果cur是'r'，則更新為'e'。

• ??如果cur是'e'，則更新為'd'。

• ??如果cur是'd'，則更新為'r'。注意，這是一個(gè)循環(huán)的過程。

9.返回構(gòu)建好的字符串builder。

總時(shí)間復(fù)雜度為O(x * log(x))，總空間復(fù)雜度為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;
}