龙空技术网

2023-07-07:给出两个字符串 str1 和 str2。 返回同时以 str1 和 str2 作

福大大架构师每日一题 64

前言:

现时大家对“c语言函数返回一个字符串”大体比较注重,同学们都需要学习一些“c语言函数返回一个字符串”的相关知识。那么小编同时在网络上汇集了一些对于“c语言函数返回一个字符串””的相关内容,希望同学们能喜欢,同学们快快来了解一下吧!

2023-07-07:给出两个字符串 str1 和 str2。

返回同时以 str1 和 str2 作为子序列的最短字符串。

如果答案不止一个,则可以返回满足条件的任意一个答案。

输入:str1 = "abac", str2 = "cab"。

输出:"cabac"。

答案2023-07-07:

大体步骤如下:

1.初始化字符串 str1str2 分别为 "abac" 和 "cab"。

2.创建一个二维数组 dp,其大小为 (n+1) x (m+1),其中 nstr1 的长度,mstr2 的长度。

3.使用动态规划来填充 dp 数组。循环遍历 i 从 1 到 n,以及 j 从 1 到 m

4.在每个循环中,比较 str1[i-1]str2[j-1] 的值:

• 如果它们相等,更新 dp[i][j]dp[i-1][j-1] + 1,表示当前字符能够在最短公共超序列中出现。• 否则,取 dp[i-1][j]dp[i][j-1] 中的较大值,表示当前字符不能同时出现在最短公共超序列中,需要从其中一个字符串中选择。

5.创建一个长度为 n + m - dp[n][m] 的字符数组 ans,用于存储最短公共超序列。

6.初始化变量 ansilen(ans) - 1injm

7.通过回溯 dp 数组,从右下角开始往左上角移动,直到 ij 达到边界 0。

8.如果 dp[i][j] 等于 dp[i-1][j-1] + 1str1[i-1] 等于 str2[j-1],表示当前字符是在 str1str2 的最短公共超序列中,将其存入 ans 中并将 ansi 减一,同时将 ij 减一。

9.如果 dp[i][j] 等于 dp[i-1][j],表示当前字符只出现在 str1 中,将其存入 ans 中并将 ansi 减一,同时将 i 减一。

10.如果 dp[i][j] 等于 dp[i][j-1],表示当前字符只出现在 str2 中,将其存入 ans 中并将 ansi 减一,同时将 j 减一。

11.当完成回溯后,若 i 大于 0,将 str1 中剩余的字符存入 ans 中。

12.当完成回溯后,若 j 大于 0,将 str2 中剩余的字符存入 ans 中。

13.将 ans 转换为字符串,并作为结果返回。

14.在 main 函数中调用 shortestCommonSupersequence 函数,并输出结果 "cabac"。

时间复杂度:O(nm),其中 n 是字符串 str1 的长度,m 是字符串 str2 的长度。

空间复杂度:O(nm),需要使用一个二维数组 dp 来存储中间结果。

这是使用动态规划(Dynamic Programming)解决字符串相关问题的算法。具体来说,这个算法用于找到两个字符串的最短公共超序列(Shortest Common Supersequence)。最短公共超序列是指包含两个字符串的所有字符,并且是长度最短的序列。通过使用动态规划的方法,可以利用子问题的最优解来构建整体的最优解,从而高效地解决这个问题。

go完整代码如下:

package mainimport (    "fmt")func shortestCommonSupersequence(str1 string, str2 string) string {    n := len(str1)    m := len(str2)    dp := make([][]int, n+1)    for i := range dp {        dp[i] = make([]int, m+1)    }    for i := 1; i <= n; i++ {        for j := 1; j <= m; j++ {            dp[i][j] = max(dp[i-1][j], dp[i][j-1])            if str1[i-1] == str2[j-1] {                dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1)            }        }    }    ans := make([]byte, n+m-dp[n][m])    ansi := len(ans) - 1    i := n    j := m    for i > 0 && j > 0 {        if dp[i][j] == dp[i-1][j-1]+1 && str1[i-1] == str2[j-1] {            ans[ansi] = str1[i-1]            ansi--            i--            j--        } else if dp[i][j] == dp[i-1][j] {            ans[ansi] = str1[i-1]            ansi--            i--        } else {            ans[ansi] = str2[j-1]            ansi--            j--        }    }    for ; i > 0; i-- {        ans[ansi] = str1[i-1]        ansi--    }    for ; j > 0; j-- {        ans[ansi] = str2[j-1]        ansi--    }    return string(ans)}func max(a, b int) int {    if a > b {        return a    }    return b}func main() {    str1 := "abac"    str2 := "cab"    result := shortestCommonSupersequence(str1, str2)    fmt.Println(result)}

在这里插入图片描述

rust完整代码如下:

fn shortest_common_supersequence(str1: &str, str2: &str) -> String {    let s1: Vec<char> = str1.chars().collect();    let s2: Vec<char> = str2.chars().collect();    let n = s1.len();    let m = s2.len();    let mut dp = vec![vec![0 as i32; m + 1]; n + 1];    let mut i = 1;    while i <= n {        let mut j = 1;        while j <= m {            dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);            if s1[i - 1] == s2[j - 1] {                dp[i][j] = dp[i][j].max(dp[i - 1][j - 1] + 1);            }            j += 1;        }        i += 1;    }    let ans_length = n + m - dp[n][m] as usize;    let mut ans = vec![' '; ans_length];    let mut ansi = ans_length as i32 - 1;    let (mut i, mut j) = (n, m);    while i > 0 && j > 0 {        if dp[i][j] == dp[i - 1][j - 1] + 1 && str1.chars().nth(i - 1) == str2.chars().nth(j - 1) {            ans[ansi as usize] = str1.chars().nth(i - 1).unwrap();            ansi -= 1;            i -= 1;            j -= 1;        } else if dp[i][j] == dp[i - 1][j] {            ans[ansi as usize] = str1.chars().nth(i - 1).unwrap();            ansi -= 1;            i -= 1;        } else {            ans[ansi as usize] = str2.chars().nth(j - 1).unwrap();            ansi -= 1;            j -= 1;        }    }    while i > 0 {        ans[ansi as usize] = str1.chars().nth(i - 1).unwrap();        ansi -= 1;        i -= 1;    }    while j > 0 {        ans[ansi as usize] = str2.chars().nth(j - 1).unwrap();        ansi -= 1;        j -= 1;    }    ans.iter().collect()}fn main() {    let str1 = String::from("abac");    let str2 = String::from("cab");    let result = shortest_common_supersequence(&str1, &str2);    println!("{}", result);}

在这里插入图片描述

c++完整代码如下:

#include <iostream>#include <vector>#include <string>using namespace std;string shortestCommonSupersequence(string str1, string str2) {    int n = str1.size();    int m = str2.size();    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));    for (int i = 1; i <= n; i++) {        for (int j = 1; j <= m; j++) {            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);            if (str1[i - 1] == str2[j - 1]) {                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);            }        }    }    string ans;    int i = n;    int j = m;    while (i > 0 && j > 0) {        if (dp[i][j] == dp[i - 1][j - 1] + 1 && str1[i - 1] == str2[j - 1]) {            ans = str1[i - 1] + ans;            i--;            j--;        }        else if (dp[i][j] == dp[i - 1][j]) {            ans = str1[i - 1] + ans;            i--;        }        else {            ans = str2[j - 1] + ans;            j--;        }    }    while (i > 0) {        ans = str1[i - 1] + ans;        i--;    }    while (j > 0) {        ans = str2[j - 1] + ans;        j--;    }    return ans;}int main() {    string str1 = "abac";    string str2 = "cab";    string result = shortestCommonSupersequence(str1, str2);    cout << result << endl;    return 0;}

在这里插入图片描述

c完整代码如下:

#include <stdio.h>#include <stdlib.h>#include <string.h>char* shortestCommonSupersequence(char* str1, char* str2) {    int n = strlen(str1);    int m = strlen(str2);    int** dp = (int**)malloc((n + 1) * sizeof(int*));    for (int i = 0; i <= n; i++) {        dp[i] = (int*)malloc((m + 1) * sizeof(int));        memset(dp[i], 0, (m + 1) * sizeof(int));    }    for (int i = 1; i <= n; i++) {        for (int j = 1; j <= m; j++) {            dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];            if (str1[i - 1] == str2[j - 1]) {                dp[i][j] = (dp[i][j] > dp[i - 1][j - 1] + 1) ? dp[i][j] : dp[i - 1][j - 1] + 1;            }        }    }    int len = n + m - dp[n][m];    char* ans = (char*)malloc((len + 1) * sizeof(char));    ans[len] = '\0';    int ansi = len - 1;    int i = n;    int j = m;    while (i > 0 && j > 0) {        if (dp[i][j] == dp[i - 1][j - 1] + 1 && str1[i - 1] == str2[j - 1]) {            ans[ansi--] = str1[i - 1];            i--;            j--;        }        else if (dp[i][j] == dp[i - 1][j]) {            ans[ansi--] = str1[i - 1];            i--;        }        else {            ans[ansi--] = str2[j - 1];            j--;        }    }    for (; i > 0; i--) {        ans[ansi--] = str1[i - 1];    }    for (; j > 0; j--) {        ans[ansi--] = str2[j - 1];    }    for (int i = 0; i <= n; i++) {        free(dp[i]);    }    free(dp);    return ans;}int main() {    char str1[] = "abac";    char str2[] = "cab";    char* result = shortestCommonSupersequence(str1, str2);    printf("%s\n", result);    free(result);    return 0;}

在这里插入图片描述

福大大架构师每日一题java当死,golang当立。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。601篇原创内容

公众号

标签: #c语言函数返回一个字符串 #java返回两个字符串