searchusermenu
  • 发布文章
  • 消息中心
点赞
收藏
评论
分享
原创

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

2023-08-01 13:08:20
10
0

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完整代码如下:

```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))
}
```

![在这里插入图片描述](https://img-blog.csdnimg.cn/01630b71788f43ac968e4817109b0144.png)

# rust完整代码如下:

```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));
}
```

![在这里插入图片描述](https://img-blog.csdnimg.cn/2d567f9366bd41d9a3cc177094be13e6.png)

# c++完整代码如下:

```cpp
#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;
}
```

![在这里插入图片描述](https://img-blog.csdnimg.cn/713688e687b44508951a18a108ba6d91.png)

0条评论
0 / 1000
3****m
116文章数
2粉丝数
3****m
116 文章 | 2 粉丝
原创

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

2023-08-01 13:08:20
10
0

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完整代码如下:

```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))
}
```

![在这里插入图片描述](https://img-blog.csdnimg.cn/01630b71788f43ac968e4817109b0144.png)

# rust完整代码如下:

```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));
}
```

![在这里插入图片描述](https://img-blog.csdnimg.cn/2d567f9366bd41d9a3cc177094be13e6.png)

# c++完整代码如下:

```cpp
#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;
}
```

![在这里插入图片描述](https://img-blog.csdnimg.cn/713688e687b44508951a18a108ba6d91.png)

文章来自个人专栏
福大大架构师每日一题
116 文章 | 1 订阅
0条评论
0 / 1000
请输入你的评论
0
0