首页 > 其他分享 >2023-09-07：用go语言编写。塔子哥最近在处理一些字符串相关的任务 他喜欢 R 字符，因为在某些任务中，这个字符通常表示“正确”的结果 另一方面，他不喜欢 B 字符，因为在某些任务中，这个字符

2023-09-07：用go语言编写。塔子哥最近在处理一些字符串相关的任务 他喜欢 R 字符，因为在某些任务中，这个字符通常表示“正确”的结果 另一方面，他不喜欢 B 字符，因为在某些任务中，这个字符

时间：2023-09-07 21:59:05浏览次数：51  
标签：std 字符 int 字符串 任务 rnumber go dp mod

2023-09-07：用go语言编写。塔子哥最近在处理一些字符串相关的任务

他喜欢 R 字符，因为在某些任务中，这个字符通常表示“正确”的结果

另一方面，他不喜欢 B 字符，因为在某些任务中，这个字符通常表示“错误”的结果

为了解决他的任务，塔子哥定义了字符串的权值为字符串中 R 字符的出现次数

例如，对于字符串 BBRBRB，它的权值为 2，因为其中有 2 个 R 字符

现在，塔子哥面临一个问题，他有一个长度为 n 的字符串 s，它仅由 R 和 B 组成

他想知道，长度为 n 的仅由 R 和 B组成的字符串中，

字典序不小于 s 的字符串的权值之和是多少？

因此，他需要编写一个程序来解决这个问题

输入第一行为一个整数 n ，表示字符串的长度

输入第二行为一个长度为 n 的字符串 s ，字符串中元素组成仅为 R 和 B

输出一个整数，代表长度为 n 的、字典序不小于 s 的字符串权值之和。

输入样例：

3

RBR

输出：

7

解释：共有 3 个字符串字典序大于等于"RBR"，RBR权值为2，RRB为2，RRR为3。

1 <= n <= 100000，

结果可能很大，对1000000007取模。

来自左程云。

答案2023-09-07：

大体过程如下：

算法一（sum1）：

1.定义函数sum1，它接收一个字符串作为参数，并返回字典序不小于该字符串的所有可能字符串中权值之和。

2.在sum1中，定义了辅助函数process1，它通过递归生成所有可能的字符串，并计算符合条件的字符串的权值之和。

3.在process1中，递归地生成新字符串，每次添加'R'或'B'，直到生成的字符串长度与给定字符串长度相等。

4.如果生成的字符串与给定字符串相等或更大，返回权值之和，其中权值为'R'的个数。

5.如果生成的字符串小于给定字符串，返回0，表示没有符合条件的字符串。

6.在每个递归步骤中，将递归调用的结果相加，计算出所有可能字符串的权值之和。

7.在sum1函数中，调用process1函数并返回最终的权值之和。

算法二（sum3）：

1.定义函数sum3，它接受一个字符串作为参数，并返回字典序不小于该字符串的所有可能字符串的权值之和。

2.在sum3中，首先初始化一些辅助数组和变量。

3.使用动态规划的方法来计算权值之和。

4.创建一个长度为n+1的dp数组，其中dp[i]表示以第i个字符作为起始字符的后缀字符串的权值之和。

5.初始化dp[n]为给定字符串最后一个字符的权值。

6.从右到左遍历字符串，计算dp数组的值。

7.如果当前字符是'R'，根据公式计算p1和p2，然后将p1和p2相加得到dp[i]。

8.如果当前字符是'B'，将dp[i+1]的值赋给dp[i]。

9.最后返回dp[0]作为最终的权值之和。

时间复杂度：

  • 算法一（sum1）的时间复杂度为O(2^n)，其中n是给定字符串的长度。因为它通过递归的方式生成所有可能的字符串。

  • 算法二（sum3）的时间复杂度为O(n)，其中n是给定字符串的长度。因为它使用动态规划计算权值之和。

额外空间复杂度：

  • 算法一（sum1）的额外空间复杂度为O(n)，因为递归调用process1函数可能会使用到O(n)的栈空间。

  • 算法二（sum3）的额外空间复杂度为O(n)，因为它使用了dp数组来存储中间结果，数组长度为n+1。

go完整代码如下：

package main

import (
	"fmt"
	"math/rand"
	"strings"
	"time"
)

const MAXN = 100001
const mod = 1000000007

var pow2, f [MAXN]int

func sum1(str string) int {
	return process1("", str)
}

func process1(path, s string) int {
	if len(path) == len(s) {
		if strings.Compare(path, s) >= 0 {
			ans := 0
			for i := 0; i < len(path); i++ {
				if path[i] == 'R' {
					ans++
				}
			}
			return ans
		} else {
			return 0
		}
	} else {
		return process1(path+"R", s) + process1(path+"B", s)
	}
}

func initialize() {
	pow2[0] = 1
	for i := 1; i < MAXN; i++ {
		pow2[i] = (pow2[i-1] * 2) % mod
	}
	f[1] = 1
	for i := 2; i < MAXN; i++ {
		f[i] = (pow2[i-1] + f[i-1]) % mod
		f[i] = (f[i] + f[i-1]) % mod
	}
}

func sum2(str string) int {
	n := len(str)
	s := []byte(str)
	rnumber := make([]int, n)
	rnumber[0] = map[bool]int{true: 1, false: 0}[s[0] == 'R']
	for i := 1; i < n; i++ {
		rnumber[i] = rnumber[i-1] + map[bool]int{true: 1, false: 0}[s[i] == 'R']
	}
	return process2(s, rnumber, n, 0)
}

func process2(s []byte, rnumber []int, n, i int) int {
	var ans int
	if i == n {
		ans = rnumber[n-1]
	} else {
		if s[i] == 'B' {
			p1 := int(((int64(rnumber[i]+1)*int64(pow2[n-i-1]))%int64(mod) + int64(f[n-i-1])) % int64(mod))
			p2 := process2(s, rnumber, n, i+1)
			ans = (p1 + p2) % mod
		} else {
			ans = process2(s, rnumber, n, i+1)
		}
	}
	return ans
}

func sum3(str string) int {
	n := len(str)
	s := []byte(str)
	rnumber := make([]int, n)
	rnumber[0] = map[bool]int{true: 1, false: 0}[s[0] == 'R']
	for i := 1; i < n; i++ {
		rnumber[i] = rnumber[i-1] + map[bool]int{true: 1, false: 0}[s[i] == 'R']
	}
	dp := make([]int, n+1)
	dp[n] = rnumber[n-1]
	for i := n - 1; i >= 0; i-- {
		if s[i] == 'B' {
			p1 := int(((int64(rnumber[i]+1)*int64(pow2[n-i-1]))%int64(mod) + int64(f[n-i-1])) % int64(mod))
			p2 := dp[i+1]
			dp[i] = (p1 + p2) % mod
		} else {
			dp[i] = dp[i+1]
		}
	}
	return dp[0]
}

func randomString(n int) string {
	s := make([]byte, n)
	for i := 0; i < n; i++ {
		if rand.Float32() < 0.5 {
			s[i] = 'B'
		} else {
			s[i] = 'R'
		}
	}
	return string(s)
}

func main() {
	rand.Seed(time.Now().UnixMilli())
	N := 15
	testTimes := 10000
	fmt.Println("测试开始")
	initialize()
	for i := 0; i < testTimes; i++ {
		n := rand.Intn(N) + 1
		s := randomString(n)
		ans1 := sum1(s)
		ans3 := sum3(s)
		if ans1 != ans3 {
			fmt.Println("出错了!")
		}
	}
	fmt.Println("测试结束")
}

在这里插入图片描述

c++完整代码如下：

#include <iostream>
#include <vector>
#include <string>
#include <random>

constexpr int MAXN = 100001;
constexpr int mod = 1000000007;

std::vector<int> pow2(MAXN);
std::vector<int> f(MAXN);

int process1(const std::string& path, const std::string& s);

int sum1(const std::string& str) {
    return process1("", str);
}

int process1(const std::string& path, const std::string& s) {
    if (path.length() == s.length()) {
        if (path.compare(s) >= 0) {
            int ans = 0;
            for (int i = 0; i < path.length(); i++) {
                if (path[i] == 'R') {
                    ans++;
                }
            }
            return ans;
        }
        else {
            return 0;
        }
    }
    else {
        return process1(path + "R", s) + process1(path + "B", s);
    }
}

void initialize() {
    pow2[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        pow2[i] = (pow2[i - 1] * 2) % mod;
    }
    f[1] = 1;
    for (int i = 2; i < MAXN; i++) {
        f[i] = (pow2[i - 1] + f[i - 1]) % mod;
        f[i] = (f[i] + f[i - 1]) % mod;
    }
}

int process2(const std::vector<char>& s, const std::vector<int>& rnumber, int n, int i);

int sum2(const std::string& str) {
    int n = str.length();
    std::vector<char> s(str.begin(), str.end());
    std::vector<int> rnumber(n);
    rnumber[0] = (s[0] == 'R') ? 1 : 0;
    for (int i = 1; i < n; i++) {
        rnumber[i] = rnumber[i - 1] + ((s[i] == 'R') ? 1 : 0);
    }
    return process2(s, rnumber, n, 0);
}

int process2(const std::vector<char>& s, const std::vector<int>& rnumber, int n, int i) {
    int ans;
    if (i == n) {
        ans = rnumber[n - 1];
    }
    else {
        if (s[i] == 'B') {
            int p1 = (((int64_t)(rnumber[i] + 1) * (int64_t)pow2[n - i - 1]) % (int64_t)mod + (int64_t)f[n - i - 1]) % (int64_t)mod;
            int p2 = process2(s, rnumber, n, i + 1);
            ans = (p1 + p2) % mod;
        }
        else {
            ans = process2(s, rnumber, n, i + 1);
        }
    }
    return ans;
}

int sum3(const std::string& str) {
    int n = str.length();
    std::vector<char> s(str.begin(), str.end());
    std::vector<int> rnumber(n);
    rnumber[0] = (s[0] == 'R') ? 1 : 0;
    for (int i = 1; i < n; i++) {
        rnumber[i] = rnumber[i - 1] + ((s[i] == 'R') ? 1 : 0);
    }
    std::vector<int> dp(n + 1);
    dp[n] = rnumber[n - 1];
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == 'B') {
            int p1 = (((int64_t)(rnumber[i] + 1) * (int64_t)pow2[n - i - 1]) % (int64_t)mod + (int64_t)f[n - i - 1]) % (int64_t)mod;
            int p2 = dp[i + 1];
            dp[i] = (p1 + p2) % mod;
        }
        else {
            dp[i] = dp[i + 1];
        }
    }
    return dp[0];
}

std::string randomString(int n) {
    std::string s(n, ' ');
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(0, 1);
    for (int i = 0; i < n; i++) {
        if (dis(gen) < 0.5) {
            s[i] = 'B';
        }
        else {
            s[i] = 'R';
        }
    }
    return s;
}

int main() {
    std::random_device rd;
    std::mt19937 gen(rd());
    int N = 15;
    int testTimes = 100;
    std::cout << "测试开始" << std::endl;
    initialize();
    for (int i = 0; i < testTimes; i++) {
        int n = gen() % N + 1;
        std::string s = randomString(n);
        int ans1 = sum1(s);
        int ans3 = sum3(s);
        if (ans1 != ans3) {
            std::cout << "出错了!" << std::endl;
        }
    }
    std::cout << "测试结束" << std::endl;
    return 0;
}

在这里插入图片描述

标签：std,字符,int,字符串,任务,rnumber,go,dp,mod
From： https://www.cnblogs.com/moonfdd/p/17686163.html

相关文章

  • 代码随想录个人笔记——字符串篇
    344.反转字符串 题目链接#include<bits/stdc++.h>usingnamespacestd;classSolution{public:voidreverseString(vector<char>&s){intlen=s.size();for(inti=0,j=len-1;i<j;i++,j--){//第一种//i......
  • Go 函数
    函数是一组语句，可以在程序中重复使用。函数不会在页面加载时自动执行。函数将通过调用函数来执行。创建函数要创建（通常称为声明）一个函数，请执行以下操作：使用func关键字。指定函数的名称，后跟括号()。最后，在花括号{}内添加定义函数应执行的代码。语法func函数名(){......
  • 字符串匹配算法
    #include<stdio.h>#defineMaxSize100//定义typedefstruct{charch[MaxSize];intlength;}SString;//朴素模式匹配算法,主串S，辅串T,最坏时间复杂度：O(mn)intIndex(SStringS,SStringT){inti=1,j=1;while(i<=S.length&&j<=T.length){......
  • django高级
    jwt源码1.jwt详解jwt的全称是jsonwebtoken，一般用于用户认证#jwt的原理是什么?用户在第一次登录的时候,会将用户名、密码等信息传到我们的服务器上进行身份验证,验证成功后,服务器会存在密钥,对用户信息进行加密签发生成jwt,并返回给用户,用户将jwt存储下来,然后在下一次......
  • 不用额外插件？RunnerGo内置压测模式怎么选
    我们在做性能测试时需要根据性能需求配置不同的压测模式如：阶梯模式。使用jmeter时我们需要安装插件来配置测试模式，为了方便用户使用，RunnerGo内嵌了压测模式这一选项，今天给大家介绍一下RunnerGo的几种压测模式和怎么根据性能需求选择合适的压测模式。RunnerGo提供了以下五种压测模式......
  • 关于 Google 搜索运作方式的解析
    Google搜索是一款全自动搜索引擎，会使用名为“网页抓取工具”的软件定期探索网络，找出可添加到Google索引中的网页。实际上，Google搜索结果中收录的大多数网页都不是手动提交的，而是我们的网页抓取工具在探索网络时找到并自动添加的。本文档从网站的角度介绍了Google搜索运作方式......
  • go并发编程系列七：使用goroutine写一个线程池
    TRANSLATEwithxEnglishArabicHebrewPolishBulgarianHindiPortugueseCatalanHmongDawRomanianChineseSimplifiedHungarianRussianChineseTraditionalIndonesianSlovakCzechItalianSlovenianDanishJapaneseSpanishDutchKl......
  • 剑指 Offer 46. 把数字翻译成字符串
    题目链接：剑指Offer46.把数字翻译成字符串题目描述：解法思路：代码：//dp[i]=dp[i-1]+dp[i-2]//dp[i]表示长度为i的数字，翻译成字符串有多少种functranslateNum(numint)int{s:=strconv.Itoa(num)n:=len(s)dp:=make([]int,n+1)dp[0]=1......
  • Go语言中互斥锁的最佳实践
    使用互斥锁是确保多个goroutine之间共享数据安全访问的一种常见方式。以下是互斥锁的最佳实践：仅在必要时使用互斥锁：互斥锁的目的是保护共享资源，但不是所有变量都需要被互斥锁保护。只有在多个goroutine并发访问的数据结构或变量上使用互斥锁，以避免不必要的锁定。小范围锁定：......
  • CE搜字符串搜不到
    可能是字符串使用的是宽字符编码  需要搜索hexbyte......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99