6
2023-07-31：用r、e、d三种字符，拼出一个回文子串数量等于x的字符串。 1 ＜= x ＜= 1...
source link: https://blog.51cto.com/moonfdd/6988185
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
2023-07-31：用r、e、d三种字符，拼出一个回文子串数量等于x的字符串。 1 ＜= x ＜= 10^5。 来自百度。
精选 原创福大大架构师每日一题 2023-08-07 00:47:25 博主文章分类：福大大架构师每日一题 ©著作权
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;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK