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

leetcode日记(99)不同的子序列

挺难的TT一开始居然把动态规划转移方程写错了,导致后面怎么改都通不过……

找转移方程真是件难事啊……

方法是照常建立动态规划数组,nums[i][j]代表s的前i含多少个t的前j,这个比较容易想。

转移方程还是有点难度的,每次遍历一个t[j]就有两种情况,一种是t[j]和s[i]相同,一种是不同,而相同又有两种情况,一种是匹配一种是跳过t[j]不匹配,如果跳过那就和t[j]不等于s[j]一样,直接就取nums[i][j-1],如果匹配那就是nums[i-1][j-1],所以t[j]和s[i]相同的情况下nums[i][j]=nums[i-1][j-1]+nums[i][j-1]。

一开始想的太复杂了,其实只要从最简单的i为0起手就行,i为0时任何j都能匹配所以一整行都是1,然后慢慢往下循环。

这是第一版代码:

class Solution {
public:
    unsigned long int nums[1001][1001];
    int numDistinct(string s, string t) {
        memset(nums,0,sizeof(nums));
        for(int i=0;i<=s.size();i++) nums[i][0]=1;
        for(int i=1;i<=s.size();i++){
            for(int j=1;j<=t.size();j++){
                if(s[i-1]==t[j-1]) nums[i][j]=nums[i-1][j-1]+nums[i-1][j];
                else nums[i][j]=nums[i-1][j];
            }
        }
        return nums[s.size()][t.size()];
    }
};

消耗内存还是太多了,其实想到可以简化空间复杂度,只需要一个一维数组记录就行,若不相等则不变,若相等则加上前一个数。

class Solution {
public:
    unsigned long int nums[1001];
    int numDistinct(string s, string t) {
        memset(nums,0,sizeof(nums));
        nums[0]=1;
        for(int i=1;i<=s.size();i++){
            for(int j=t.size();j>=1;j--){
                if(s[i-1]==t[j-1]) nums[j]=nums[j-1]+nums[j];
            }
        }
        return nums[t.size()];
    }
};

简化了很多,需要注意t要从后往前匹配,因为不能影响到后面的数值。


http://www.kler.cn/a/588741.html

相关文章:

  • PyTorch使用-张量的创建
  • CSS 知识点总结1
  • 【软考-架构】7、系统配置与性能评价
  • CAD球体密堆积3D插件V2.0
  • SpringBoot手动注册定时任务
  • ActiveMQ监听器在MQ重启后不再监听问题
  • Pytorch:Dataset的加载
  • 百度贴吧IP和ID是什么意思?怎么查看
  • NPU、边缘计算与算力都是什么啊?
  • [leetcode] 面试经典 150 题——篇3:滑动窗口
  • 一分钟了解深度学习
  • Lisp语言的网络管理
  • 利用Java爬虫根据关键词获取商品列表:实战指南
  • 一份C#的笔试题及答案
  • 【NLP】 4. NLP项目流程与上下文窗口大小参数的影响
  • Kafka可视化工具KafkaTool工具的使用
  • Lua语言的嵌入式调试
  • qt 自带虚拟键盘的编译使用记录
  • 深入解析 React Diff 算法:原理、优化与实践
  • C或C++中实现数据结构课程中的链表、数组、树和图