首页 > 其他分享 >2023-05-22：给定一个长度为 n 的字符串 s ，其中 s[i] 是: D 意味着减少； I 意味着增加。 有效排列 是对有 n + 1 个在 [0, n] 范围内的整数的一个排列 perm

2023-05-22：给定一个长度为 n 的字符串 s ，其中 s[i] 是: D 意味着减少； I 意味着增加。 有效排列 是对有 n + 1 个在 [0, n] 范围内的整数的一个排列 perm

时间：2023-05-22 22:45:58浏览次数：50  
标签：排列 nextLess 22 less int 05 ans usize dp

2023-05-22：给定一个长度为 n 的字符串 s ，其中 s[i] 是:

D 意味着减少；

I 意味着增加。

有效排列 是对有 n + 1 个在 [0, n] 范围内的整数的一个排列 perm ，使得对所有的 i：

如果 s[i] == 'D'，那么 perm[i] > perm[i+1]，以及；

如果 s[i] == 'I'，那么 perm[i] < perm[i+1]。

返回 有效排列 perm的数量 。因为答案可能很大，所以请返回你的答案对 10^9 + 7 取余。

输入：s = "DID"。

输出：5。

答案2023-05-22：

算法1：暴力枚举

1.定义递归函数 ways(s []byte, i int, less int, n int) int，其中 s 为要判断的字符串，i 表示当前要填入的位置，less 记录上一个数的大小信息，n 表示总共有 n + 1 个数字需要填。

2.如果 i 等于 n，则返回 1，表示已经填完了。

3.如果 i 等于 0 或 s[i-1] 等于 'D'，则循环从 0 到 less - 1 枚举下一个数 nextLess，并将结果加到 ans 上。每次递归调用时将 i 增加 1，并更新 less 的值为 nextLess。最后返回 ans。

4.否则 s[i-1] 等于 'I'，则循环从 less 到 n-i 枚举下一个数 nextLess，并将结果加到 ans 上。每次递归调用时将 i 增加 1，并更新 less 的值为 nextLess。最后返回 ans。

时间复杂度：O(n!)，其中 n 为数字序列的长度。

空间复杂度：O(n)，递归过程中需要 O(n) 的栈空间。

算法2：动态规划

1.定义二维数组 dp，其中 dp[i][j] 表示在第 i 个位置填入数字 j 的情况下满足条件的排列的数量。

2.初始化 dp[n][less] 为 1，表示在最后一个位置填入 less 的数量只有一种。

3.从倒数第二个位置开始往前遍历，根据当前位置 s[i-1] 的值，分别枚举下一个数字的大小。如果 s[i-1] 等于 'D'，则循环从 0 到 less - 1 枚举下一个数字的大小，将 dp[i][less] 增加上 dp[i+1][nextLess]，最后取模。

4.如果 s[i-1] 等于 'I'，则循环从 less 到 n-i 枚举下一个数字的大小，将 dp[i][less] 增加上 dp[i+1][nextLess]，最后取模。

5.最终答案为 dp[0][n]。

时间复杂度：O(n^2)，需要填充一个二维数组，数组大小为 n * (n+1)。

空间复杂度：O(n^2)，需要使用一个二维数组来存储状态。

算法3：动态规划 + 优化

1.定义二维数组 dp，其中 dp[i][j] 表示在第 i 个位置填入数字 j 的情况下满足条件的排列的数量。

2.初始化 dp[n][less] 为 1，表示在最后一个位置填入 less 的数量只有一种。

3.从倒数第二个位置开始往前遍历，根据当前位置 s[i-1] 的值，分别枚举下一个数字的大小。如果 s[i-1] 等于 'D'，则从 0 到 less 枚举 nextLess，将 dp[i][less] 增加上 dp[i+1][nextLess]，最后取模。

4.如果 s[i-1] 等于 'I'，则从 n-i 到 less 枚举 nextLess，将 dp[i][less] 增加上 dp[i+1][nextLess]，最后取模。

5.在循环中记录当前已经累计的和 sum，然后 dp[i][less] 的值更新为 sum，同时需要考虑取模的问题。具体来说，如果当前的 sum 大于 mod，则减去一个 mod；如果当前的 sum 小于 0，则加上一个 mod。

6.最终答案为 dp[0][n]。

时间复杂度：O(n)，只需填充一个一维数组即可。

空间复杂度：O(n)，只需使用一个一维数组来存储状态。

go完整代码如下：

package main

import "fmt"

func numPermsDISequence1(s string) int {
	n := len(s) + 1
	return ways1([]byte(s), 0, n, n)
}

func ways1(s []byte, i int, less int, n int) int {
	if i == n {
		return 1
	} else if i == 0 || s[i-1] == 'D' {
		ans := 0
		for nextLess := 0; nextLess < less; nextLess++ {
			ans += ways1(s, i+1, nextLess, n)
		}
		return ans
	} else { // s[i-1] = 'I'
		ans := 0
		for nextLess := less; nextLess < n-i; nextLess++ {
			ans += ways1(s, i+1, nextLess, n)
		}
		return ans
	}
}

func numPermsDISequence2(s string) int {
	mod := 1000000007
	n := len(s) + 1
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for less := 0; less <= n; less++ {
		dp[n][less] = 1
	}
	for i := n - 1; i >= 0; i-- {
		for less := 0; less <= n; less++ {
			if i == 0 || s[i-1] == 'D' {
				for nextLess := 0; nextLess < less; nextLess++ {
					dp[i][less] = (dp[i][less] + dp[i+1][nextLess]) % mod
				}
			} else {
				for nextLess := less; nextLess < n-i; nextLess++ {
					dp[i][less] = (dp[i][less] + dp[i+1][nextLess]) % mod
				}
			}
		}
	}
	return dp[0][n]
}

func numPermsDISequence3(s string) int {
	mod := 1000000007
	n := len(s) + 1
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for less := 0; less <= n; less++ {
		dp[n][less] = 1
	}
	for i := n - 1; i >= 0; i-- {
		if i == 0 || s[i-1] == 'D' {
			for less := 0; less <= n; less++ {
				if less > 0 {
					dp[i][less] = (dp[i][less-1] + dp[i+1][less-1]) % mod
				} else {
					dp[i][less] = 0
				}
			}
		} else { // s[i-1] = 'I'
			dp[i][n-i-1] = dp[i+1][n-i-1]
			for less := n - i - 2; less >= 0; less-- {
				dp[i][less] = (dp[i][less+1] + dp[i+1][less]) % mod
			}
		}
	}
	return dp[0][n]
}

func main() {
	s := "DID"
	res := numPermsDISequence1(s)
	fmt.Println(res)

	res = numPermsDISequence2(s)
	fmt.Println(res)

	res = numPermsDISequence3(s)
	fmt.Println(res)
}

在这里插入图片描述

rust语言完整代码如下：

fn num_perms_di_sequence1(s: String) -> i32 {
    let s = s.as_bytes();
    let n = s.len() + 1;
    ways1(s, 0, n, n)
}

// i : 填的数字的位
// 3 5 2
// 0 1 2
//  I D
// less :
// 之前填的数字X，后面剩下的数字中有几个比X小！
//         X
//        i-1 i
fn ways1(s: &[u8], i: usize, less: usize, n: usize) -> i32 {
    if i == n {
        return 1;
    } else if i == 0 || s[i - 1] == b'D' {
        (0..less)
            .map(|next_less| ways1(s, i + 1, next_less, n))
            .sum()
    } else {
        // s[i-1] = b'I'
        ((less as isize)..((n - i) as isize))
            .map(|next_less| ways1(s, i + 1, next_less as usize, n))
            .sum()
    }
}

fn num_perms_di_sequence2(s: String) -> i32 {
    let s = s.as_bytes();
    let n = s.len() + 1;
    let mod_num = 1000000007;

    let mut dp = vec![vec![0; n + 1]; n + 1];
    for less in 0..=n {
        dp[n][less] = 1;
    }

    let mut i = n as i32 - 1;
    while i >= 0 {
        for less in 0..=n {
            if i == 0 || s[(i - 1) as usize] == b'D' {
                for next_less in 0..less {
                    dp[i as usize][less] =
                        (dp[i as usize][less] + dp[i as usize + 1][next_less]) % mod_num;
                }
            } else {
                // s[i-1] = b'I'
                for next_less in less..n - i as usize {
                    dp[i as usize][less] =
                        (dp[i as usize][less] + dp[i as usize + 1][next_less]) % mod_num;
                }
            }
        }
        i -= 1;
    }
    dp[0][n]
}

fn num_perms_di_sequence3(s: String) -> i32 {
    let s = s.as_bytes();
    let n = s.len() + 1;
    let mod_num = 1000000007;

    let mut dp = vec![vec![0; n + 1]; n + 1];
    for less in 0..=n {
        dp[n][less] = 1;
    }

    let mut i = n as i32 - 1;
    while i >= 0 {
        if i == 0 || s[i as usize - 1] == b'D' {
            for less in 0..=n {
                dp[i as usize][less] = if less > 0 {
                    (dp[i as usize][less - 1] + dp[i as usize + 1][less - 1]) % mod_num
                } else {
                    0
                }
            }
        } else {
            // s[i-1] = b'I'
            dp[i as usize][n - i as usize - 1] = dp[i as usize + 1][n - i as usize - 1];
            let mut less = n as i32 - i - 2;
            while less >= 0 {
                dp[i as usize][less as usize] = (dp[i as usize][less as usize + 1]
                    + dp[i as usize + 1][less as usize])
                    % mod_num;
                less -= 1;
            }
        }
        i -= 1;
    }
    dp[0][n]
}

fn main() {
    let s = String::from("DID");
    let res = num_perms_di_sequence1(s);
    println!("{}", res);

    let s = String::from("DID");
    let res = num_perms_di_sequence2(s);
    println!("{}", res);

    let s = String::from("DID");
    let res = num_perms_di_sequence3(s);
    println!("{}", res);
}

在这里插入图片描述

c语言完整代码如下：

#include <stdio.h>
#include <stdlib.h>

int ways1(char* s, int i, int less, int n);
int numPermsDISequence1(char* s);
int numPermsDISequence2(char* str);
int numPermsDISequence3(char* str);

int main() {
    char s[] = "DID";
    printf("%d\n", numPermsDISequence1(s));
    printf("%d\n", numPermsDISequence2(s));
    printf("%d\n", numPermsDISequence3(s));
    return 0;
}

int numPermsDISequence1(char* s) {
    return ways1(s, 0, strlen(s) + 1, strlen(s) + 1);
}

int ways1(char* s, int i, int less, int n) {
    int ans = 0;
    if (i == n) {
        ans = 1;
    }
    else if (i == 0 || *(s + i - 1) == 'D') {
        for (int nextLess = 0; nextLess < less; nextLess++) {
            ans += ways1(s, i + 1, nextLess, n);
        }
    }
    else {
        for (int nextLess = less; nextLess < n - i; nextLess++) {
            ans += ways1(s, i + 1, nextLess, n);
        }
    }
    return ans;
}

int numPermsDISequence2(char* s) {
    int mod = 1000000007;
    int n = strlen(s) + 1;
    int** dp = (int**)malloc((n + 1) * sizeof(int*));
    for (int i = 0; i <= n; i++) {
        dp[i] = (int*)malloc((n + 1) * sizeof(int));
    }
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = 0;
        }
    }

    for (int less = 0; less <= n; less++) {
        dp[n][less] = 1;
    }
    for (int i = n - 1; i >= 0; i--) {
        for (int less = 0; less <= n; less++) {
            if (i == 0 || s[i - 1] == 'D') {
                for (int nextLess = 0; nextLess < less; nextLess++) {
                    dp[i][less] = (dp[i][less] + dp[i + 1][nextLess]) % mod;
                }
            }
            else {
                for (int nextLess = less; nextLess < n - i; nextLess++) {
                    dp[i][less] = (dp[i][less] + dp[i + 1][nextLess]) % mod;
                }
            }
        }
    }
    int res = dp[0][n];
    for (int i = 0; i <= n; i++) {
        free(dp[i]);
    }
    free(dp);
    return res;
}

int numPermsDISequence3(char* s) {
    int mod = 1000000007;
    int n = strlen(s) + 1;
    int** dp = (int**)malloc((n + 1) * sizeof(int*));
    for (int i = 0; i <= n; i++) {
        dp[i] = (int*)malloc((n + 1) * sizeof(int));
    }

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = 0;
        }
    }


    for (int less = 0; less <= n; less++) {
        dp[n][less] = 1;
    }
    for (int i = n - 1; i >= 0; i--) {
        if (i == 0 || s[i - 1] == 'D') {
            for (int less = 0; less <= n; less++) {
                dp[i][less] = less - 1 >= 0 ? ((dp[i][less - 1] + dp[i + 1][less - 1]) % mod) : 0;
            }
        }
        else { // s[i-1] = 'I'
            dp[i][n - i - 1] = dp[i + 1][n - i - 1];
            for (int less = n - i - 2; less >= 0; less--) {
                dp[i][less] = (dp[i][less + 1] + dp[i + 1][less]) % mod;
            }
        }
    }
    int res = dp[0][n];
    for (int i = 0; i <= n; i++) {
        free(dp[i]);
    }
    free(dp);
    return res;
}

在这里插入图片描述

c++完整代码如下：

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int ways1(vector<char>& s, int i, int less, int n);
int numPermsDISequence1(string s);
int numPermsDISequence2(string s);
int numPermsDISequence3(string s);

// i : 填的数字的位
// 3 5 2
// 0 1 2
//  I D
// less :之前填的数字X，后面剩下的数字中有几个比X小！
//         X
//        i-1 i
int ways1(vector<char>& s, int i, int less, int n) {
    int ans = 0;
    if (i == n) {
        ans = 1;
    }
    else if (i == 0 || s[i - 1] == 'D') {
        for (int nextLess = 0; nextLess < less; nextLess++) {
            ans += ways1(s, i + 1, nextLess, n);
        }
    }
    else { // s[i-1] = 'I'
        for (int nextLess = less; nextLess < n - i; nextLess++) {
            ans += ways1(s, i + 1, nextLess, n);
        }
    }
    return ans;
}

int numPermsDISequence1(string s) {
    vector<char> str(s.begin(), s.end());
    str.push_back('I');
    return ways1(str, 0, s.length() + 1, s.length() + 1);
}

int numPermsDISequence2(string s) {
    int mod = 1000000007;
    vector<char> str(s.begin(), s.end());
    str.push_back('I');
    int n = str.size();
    vector<vector<int>> dp(n + 1, vector<int>(n + 1));
    for (int less = 0; less <= n; less++) {
        dp[n][less] = 1;
    }
    for (int i = n - 1; i >= 0; i--) {
        for (int less = 0; less <= n; less++) {
            if (i == 0 || str[i - 1] == 'D') {
                for (int nextLess = 0; nextLess < less; nextLess++) {
                    dp[i][less] = (dp[i][less] + dp[i + 1][nextLess]) % mod;
                }
            }
            else {
                for (int nextLess = less; nextLess < n - i; nextLess++) {
                    dp[i][less] = (dp[i][less] + dp[i + 1][nextLess]) % mod;
                }
            }
        }
    }
    return dp[0][n];
}

int numPermsDISequence3(string s) {
    int mod = 1000000007;
    vector<char> str(s.begin(), s.end());
    str.push_back('I');
    int n = str.size();
    vector<vector<int>> dp(n + 1, vector<int>(n + 1));
    for (int less = 0; less <= n; less++) {
        dp[n][less] = 1;
    }
    for (int i = n - 1; i >= 0; i--) {
        if (i == 0 || str[i - 1] == 'D') {
            for (int less = 0; less <= n; less++) {
                dp[i][less] = less - 1 >= 0 ? ((dp[i][less - 1] + dp[i + 1][less - 1]) % mod) : 0;
            }
        }
        else { // str[i-1] = 'I'
            dp[i][n - i - 1] = dp[i + 1][n - i - 1];
            for (int less = n - i - 2; less >= 0; less--) {
                dp[i][less] = (dp[i][less + 1] + dp[i + 1][less]) % mod;
            }
        }
    }
    return dp[0][n];
}

int main() {
    string s = "DID";
    cout << numPermsDISequence1(s) << endl; // expect 5
    cout << numPermsDISequence2(s) << endl; // expect 5
    cout << numPermsDISequence3(s) << endl; // expect 5
    return 0;
}

在这里插入图片描述

标签：排列,nextLess,22,less,int,05,ans,usize,dp
From： https://www.cnblogs.com/moonfdd/p/17421991.html

相关文章

  • 5.22
      #include<bits/stdc++.h>intmain(){intt,a[5];longintk,i;for(i=95860;;i++){for(t=0,k=100000;k>=10;t++){a[t]=(i%k)/(k/10);k/=10;......
  • 5.22每日总结
    今天上课听老师讲了未来的学习规划，还有之后的作业期末考核内容，然后继续完成团队项目的优化和与团队成员讨论了将App挂到网机的问题，今天主要对交互页面进行优化，还有与团队成员进行讨论，下面是一些成果。 ......
  • java学习日记20230522-集合选择原则
    1.判断存储的类型，一组对象【单列】或者一组键值对【双列】2.一组对象【单列】：collection的子类：允许重复：List的某个实现类：增删多LinkedList（底层维护的是双向链表）                                改查多ArrayList（底层维护的是object类型的可......
  • 2023 5 22
    #include<iostream>#include<fstream>#include<string>usingnamespacestd;classDog{public:Dog(){}Dog(intage,intwei){this->m_Age=age;this->m_Wei=wei;}intm_Wei;intm_Age;......
  • 2023.5.22编程一小时打卡
    一、问题描述：线性代数中的矩阵可以表示为一个row＊column的二维数组，当row和column均为1时，退化为一个数，当row为1时，为一个行向量，当column为1时，为一个列向量。建立一个整数矩阵类matrix，其私有数据成员如下：introw;intcolumn;int**mat;建立该整数矩阵类matrix构造函数；建立一个*（......
  • RSA之低加密指数广播攻击------2023.5.22
    使用条件：模数n，密文C不同，明文m，加密指数e相同。（一般的话e=k，k是题目给出的n和c的组数）例如：e=k=3同余式组：C1≡m^emodn1C2≡m^emodn2C3≡m^emodn3由中国剩余定理：设n1,n2,n3是两两互素的正整数，M=n1∗n2∗n3Mi=M/ni (i=1,2,3)则同余式组： m^e≡Ci mod ni  (i=1,2,3)有唯一解......
  • 2023.5.22——软件工程日报
    所花时间（包括上课）：6h代码量（行）：0行博客量（篇）：1篇今天，上午学习，下午学习。我了解到的知识点：1.了解了一些数据库的知识；2.了解了一些python的知识；3.了解了一些英语知识；5.了解了一些Javaweb的知识；4.了解了一些数学建模的知识；6.了解了一些计算机网络的知识；......
  • 5.22模版 初见云雨情
    函数模板模板函数定义的一般形式如下所示：template<typenametype>ret-typefunc-name(parameterlist){//函数的主体}在这里，type是函数所使用的数据类型的占位符名称。这个名称可以在函数定义中使用。下面是函数模板的实例，返回两个数中的最大值：实例#include<iostream>#......
  • RSA之低指数攻击------2023.5.22
    1，e=3的小明文攻击：特点：当e=3时，如果明文过小，导致明文的三次方仍然小于n，那么通过直接对密文开三次方即可得到明文。 即：C=m^e mod n,如果e=3,且m^e<n,则C=m^e,m=c^(1/3) 2.如果明文的三次方比n大，但不是足够大，那么设k有： C=m^e+k∗n 爆破k，如果 C−k∗n 或者 C+k∗n......
  • 5.22 3.1
    一、问题描述求某一范围内完数的个数。如果一个数等于它的因子之和，则称该数为“完数”(或“完全数”。例如，6的因子为1，2，3，而6=1+2+3，因此6是“完数”。二、分析for(i=2;i<=n;i++){....for(j=l;j<i;j++){...}if(s==i)输出当前i是完数}三、代码#include<iostream>usingna......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99