前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2021-12-27:给定一个字符串str,和一个正数k, str子序列的字符种数必须是k种,返回有多少子序列满足这个条件。 已

2021-12-27:给定一个字符串str,和一个正数k, str子序列的字符种数必须是k种,返回有多少子序列满足这个条件。 已

作者头像
福大大架构师每日一题
发布2021-12-29 15:47:09
2320
发布2021-12-29 15:47:09
举报

2021-12-27:给定一个字符串str,和一个正数k,

str子序列的字符种数必须是k种,返回有多少子序列满足这个条件。

已知str中都是小写字母,

原始是取mod,

本节在尝试上,最难的,

搞出桶来,组合公式。

来自百度。

答案2021-12-27:

假设有3种字符,k=2,那么种类上就是3取2,然后2种字符词频,求2的n次方相乘,最后累加。

比如abbccc。

词频:a=1,b=2,c=3。

选a,b:1*(2^2-1)=3,

选b,c:(2^2-1)*(2^3-1)=21,

选a,c:1*(2^3-1)=7,

3+21+7=31。

代码用golang编写。代码如下:

代码语言:javascript
复制
package main

import "fmt"

func main() {
    s := "abbccc"
    k := 2
    ret := nums(s, k)
    fmt.Println(ret)
}

func twoSelectOne(c bool, a, b int) int {
    if c {
        return a
    } else {
        return b
    }
}

func f(bu []int, index, rest int) int {
    if index == len(bu) {
        return twoSelectOne(rest == 0, 1, 0)
    }
    // 最后形成的子序列,一个index代表的字符也没有!
    p1 := f(bu, index+1, rest)
    // 最后形成的子序列,一定要包含index代表的字符,几个呢?(所有可能性都要算上!)
    p2 := 0
    if rest > 0 { // 剩余的种数,没耗尽,可以包含当前桶的字符
        p2 = (1<<bu[index] - 1) * f(bu, index+1, rest-1)
    }
    return p1 + p2
}

func nums(s string, k int) int {
    str := []byte(s)
    counts := make([]int, 26)
    for _, c := range str {
        counts[c-97]++
    }
    return ways(counts, 0, k)
}

func ways(c []int, i, r int) int {
    if r == 0 {
        return 1
    }
    if i == len(c) {
        return 0
    }
    // math(n) -> 2 ^ n -1
    return math(c[i])*ways(c, i+1, r-1) + ways(c, i+1, r)
}

// n个不同的球
// 挑出1个的方法数 + 挑出2个的方法数 + ... + 挑出n个的方法数为:
// C(n,1) + C(n,2) + ... + C(n,n) == (2 ^ n) -1
func math(n int) int {
    return (1 << n) - 1
}

执行结果如下:

[左神java代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class39/Code03_SequenceKDifferentKinds.java)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-12-27,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档