当前位置: 首页 > news >正文

LeetCode·每日一题·940.不同的子序列 || · 动态规划

链接:https://leetcode.cn/problems/distinct-subsequences-ii/solutions/1891268/di-gui-hui-su-dong-tai-gui-hua-zhu-shi-c-m6ac/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处 

题目

 

示例

 

思路

题意 -> 给定一个字符串 s,计算 s 的 不同非空子序列 的个数

C语言库函数实现哈希表,力扣也支持

【递归+回溯】

根据题目意思直接枚举 s 中所有非空子序列,最后统计总数即可

当然我们枚举所有的子序列,肯定是会存在重复子序列的,对于重复的子序列我们只能进行一次统计,所以使用哈希表对子序列进行去重,每次枚举出一个子序列就判断是否在哈希表中存在

递归枚举的过程我们可以不全部枚举出去,对于一些明显重复的子序列我们可以直接不枚举,并利用回溯返回上一步

具体看代码,注释超级详细

当然递归过不了!!!!

【动态规划】

动态规划思路不太好想

对于 s 中任意一个字符, 当我们选择这个字符并构造当前字符的子序列时,存在两种构造方法:

  • 当前字符为结尾:需要选择当前字符的前一个元素
    • 对应的 dp[i] 表示为 以 字符 i 结尾的子序列有多少个
      • 递推公式:dp[i] = dp[i-1] + 1;
        • 遍历方向:因为当前位置需要前一个才能推出,所以要从前往后枚举
  • 当前字符为开头:需要选择当前字符的后一个元素
    • 对应的 dp[i] 表示为 以 字符 i 开始的子序列有多少个
      • 递推公式:dp[i] = dp[i+1] + 1;
        • 遍历方向: 因为当前位置需要后一个才能推出,所以要从后往前枚举

初始化都为 1,因为一个字符就是一个子序列

这两种方法都可以进行构造,只是在遍历方向上面不一样

到这里其实我们已经实现了所以非空子序列的枚举,但是我们没有去重,在这里dp中存在很多重复的子序列,那么对于去重我们还是的用哈希表,这里就可以用数组哈希来进行简单去重了。

去重

对于上述dp中当我们确定一个元素时,都存在下一个元素或者上一个元素的选择

比如 baaabaabcc,当我们选择了第三个 a 时,也就是确定了 dp[i],接下来就是dp[i+1]的选择,当然最简单就是枚举之后的每一个元素,但是就会存在重复的子序列,比如选择了 第二个 a 相加之后 ,再选择第一个 a 相加,其实在第二个 a中就已经包含了选择第一个a相加的情况,就会重复。所以可以使用数组哈希记录相同元素最后出现的位置,每次选择下一个元素时,只从数组哈希中选择

从dp数组的含义理解:对于上一个元素也还是以 字符 i 结尾的子序列有多少个,那么字符只有26个,所以选择上一个结尾字符时也肯定只有26个选择

1 e 9 + 7 是科学计数法 = 1 * 10^9 + 7

代码

【递归+回溯】

//哈希+递归+回溯
struct my_struct {
    char name[2000];          /* key */
    int id;
    UT_hash_handle hh;         /* makes this structure hashable */
};
struct my_struct * users = NULL;

void dfs(char * s, int len, int index, char * path, int next, int * count)
{
    struct my_struct * m = NULL;
    if(index == len)    return;
    int mod = 1e9 + 7;
    for(int i = index; i < len; i++)//枚举切割点
    {
        path[next] = s[i];
        HASH_FIND_STR(users, path, m);
        if(!m)//只有不存在时才切割
        {
            m = (struct my_struct *)malloc(sizeof *m);
            strcpy(m->name, path);
            m->id = i;
            HASH_ADD_STR(users, name, m);
            (*count)++;
            (*count) %= mod;
            dfs(s, len, i+1, path, next+1, count);//下一个切割点
        }
        path[next] = '\0';//回溯
    }
}

int distinctSubseqII(char * s){
    int len = strlen(s);
    char path[len+1];
    memset(path, 0, sizeof(path));
    int count = 0;
    struct my_struct *m, *tmp = NULL;
    dfs(s, len, 0, path, 0, &count);

    /* free the hash table contents */
    HASH_ITER(hh, users, m, tmp) {
      HASH_DEL(users, m);
      free(m);
    }
    return count;
}

作者:小迅要变强
链接:https://leetcode.cn/problems/distinct-subsequences-ii/solutions/1891268/di-gui-hui-su-dong-tai-gui-hua-zhu-shi-c-m6ac/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

【动态规划】

int distinctSubseqII(char * s){
    int hash[26];
    memset(hash, -1, sizeof(hash));
    int len = strlen(s);
    int dp[len];
    int mod = 1e9 + 7;//初始化
    for(int i = 0; i < len; ++i)//枚举数组
    {
        dp[i] = 1;//初始化为 1,
        for(int j = 0; j < 26; j++)//枚举数组
        {
            if(hash[j] != -1)//选择上一个结尾元素
            {
                dp[i] = (dp[i] + dp[hash[j]]) % mod;
            }
        }
        hash[s[i] - 'a'] = i;
    }
    int count = 0;
    for(int i = 0; i < 26; i++)//统计所以字符结尾的子序列,总共只有26个字符
    {
        if(hash[i] != -1)
            count = (count + dp[hash[i]]) % mod;
    }
    return count;
}

作者:小迅要变强
链接:https://leetcode.cn/problems/distinct-subsequences-ii/solutions/1891268/di-gui-hui-su-dong-tai-gui-hua-zhu-shi-c-m6ac/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

相关文章:

  • MySQL实战-开篇
  • 数据仓库的实际应用示例-广告投放平台为例
  • 【算法训练记录——Day32】
  • 【从零到一】电子元器件网站建设/开发方案、流程及搭建要点全解
  • 《计算机英语》缩略词补充
  • Ubuntu下安装docker
  • 死磕Elasticsearch:携手六年,感谢有你!
  • 图论|207. 课程表 210. 课程表 II
  • 水电表远程集中抄表管理系统
  • [云原生] K8S声明式资源管理
  • List去重有几种方式
  • native sql -ABAP开发从入门到精通笔记
  • 【云原生】Elasticsearch + kibana on k8s 讲解与实战操作
  • 神经网络过拟合什么意思,神经网络中解决过拟合
  • win11toast:python桌面通知工具
  • 【cloud Alibaba】(四)分布式事务处理——Seata
  • [算法入门笔记] 19. 有序表
  • (Java岗)秋招打卡!一本学历拿下美团、阿里、快手、米哈游offer
  • Java反射小练之手写BeanUtils的copyProperties(Upgrade)
  • 软件测试过程:单元测试,集成测试,系统测试,验收测试,回归测试
  • 入门力扣自学笔记177 C++ (题目编号:769)
  • QT中QThread的各个方法,UI线程关系,事件关系详解(5)
  • 深度学习:LeNet-5实现服装分类(PyTorch)
  • 核酸系统架构设计
  • 基于Matlab模拟、检测和跟踪飞机着陆进场中异常的仿真(附源码)
  • 面试官:服务端推送到Web前端有哪几种方式?
  • selenium使用篇_键盘鼠标事件
  • Java第17章 - I/O流(一)
  • STM32F103移植FreeRTOS必须搞明白的系列知识---4(FreeRTOSConfig.h配置文件)
  • C语言中的字符串转数字函数常见问题详解
  • 从零开始搭建仿抖音短视频APP-构建后端项目
  • 力扣 221. 最大正方形