当前位置:网站首页>Cc36 different subsequences
Cc36 different subsequences
2022-07-06 14:48:00 【sakeww】
link :
Niuke link :
https://www.nowcoder.com/practice/ed2923e49d3d495f8321aa46ade9f873?tpId=46&tqId=29065&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
leetcode link :
https://leetcode-cn.com/problems/distinct-subsequences/
Description and examples :
Code :
Method 1 :
class Solution {
public:
int numDistinct(string S, string T)
{
int row = S.size();
int col = T.size();
vector<vector<int>> arr(row + 1, vector<int>(col + 1));
arr[0][0] = 1;
for (int i = 1; i <= row; ++i)
{
arr[i][0] = 1;
for (int j = 1; j <= col; ++j)
{
if (S[i - 1] == T[j - 1])
arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
else
arr[i][j] = arr[i - 1][j];
}
}
return arr[row][col];
}
};
Method 1 Analysis :
The final result is shown in the figure :
Method 2 :
class Solution {
public:
int numDistinct(string S, string T)
{
int row = S.size();
int col = T.size();
vector<int> arr(col + 1);
arr[0] = 1;
for (int i = 1; i <= row; ++i)
{
for (int j = col; j > 0; --j)
{
if (S[i - 1] == T[j - 1])
arr[j] = arr[j - 1] + arr[j];
}
}
return arr[col];
}
};
Method 2 analysis :
Because we only use one row of data for the two-dimensional array in method 1
When traversing to a point , The value of this point is related to the previous one :
When the same : Equal to its own value plus the previous value
When different : Equal to its own value
边栏推荐
- Résumé des points de connaissance et des réponses aux exercices après la classe du chapitre 7 de Jia junping dans la huitième édition des statistiques
- [pointer] find the value of the largest element in the two-dimensional array
- Numpy快速上手指南
- Always of SystemVerilog usage_ comb 、always_ iff
- Function: find the root of the equation by Newton iterative method
- JDBC transactions, batch processing, and connection pooling (super detailed)
- c语言学习总结(上)(更新中)
- What is the transaction of MySQL? What is dirty reading and what is unreal reading? Not repeatable?
- Statistics, 8th Edition, Jia Junping, Chapter 6 Summary of knowledge points of statistics and sampling distribution and answers to exercises after class
- [pointer] find the length of the string
猜你喜欢
内网渗透之内网信息收集(三)
Summary of thread implementation
《统计学》第八版贾俊平第十三章时间序列分析和预测知识点总结及课后习题答案
New version of postman flows [introductory teaching chapter 01 send request]
1.支付系统
Database monitoring SQL execution
Fundamentals of digital circuits (I) number system and code system
1. Payment system
Solutions to common problems in database development such as MySQL
Wu Enda's latest interview! Data centric reasons
随机推荐
“Hello IC World”
Pointer -- output all characters in the string in reverse order
Four methods of exchanging the values of a and B
Statistics 8th Edition Jia Junping Chapter 2 after class exercises and answer summary
High concurrency programming series: 6 steps of JVM performance tuning and detailed explanation of key tuning parameters
Proceedingjoinpoint API use
Functions: Finding Roots of equations
《统计学》第八版贾俊平第十章方差分析知识点总结及课后习题答案
What is the transaction of MySQL? What is dirty reading and what is unreal reading? Not repeatable?
Using flask_ Whooshalchemyplus Jieba realizes global search of flask
How does SQLite count the data that meets another condition under the data that has been classified once
How to transform functional testing into automated testing?
Always of SystemVerilog usage_ comb 、always_ iff
Function: string storage in reverse order
【指针】八进制转换为十进制
Library management system
数字电路基础(三)编码器和译码器
浙大版《C语言程序设计实验与习题指导(第3版)》题目集
To brush the video, it's better to see if you have mastered these interview questions. Slowly accumulating a monthly income of more than 10000 is not a dream.
Résumé des points de connaissance et des réponses aux exercices après la classe du chapitre 7 de Jia junping dans la huitième édition des statistiques