[면접 알고리즘] 동적 기획
int LCS(string s1, string s2){
int len1 = s1.size(), len2 = s2.size();
vector> lcs(len1 + 1, vector(len2 + 1));
for (int i = 0; i <= len1; i++)
lcs[i][0] = 0;
for (int i = 0; i <= len2; i++){
lcs[0][i] = 0;
}
for (int i = 1; i <= len1; i++){
for (int j = 1; j <= len2; j++){
if (s1[i-1] == s2[j-1]){
lcs[i][j] = lcs[i - 1][j - 1] + 1;
}
else{
lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
}
}
}
return lcs[len1][len2];
}
LCS(최대 공통 하위 문자열)
string LCS(string s1, string s2){
int len1 = s1.size(), len2 = s2.size();
vector> lcs(len1 + 1, vector(len2 + 1, 0));
for (int i = 0; i <= len1; i++)
lcs[i][0] = 0;
for (int i = 0; i <= len2; i++){
lcs[0][i] = 0;
}
int last = 0, len = 0;
for (int i = 1; i <= len1; i++){
for (int j = 1; j <= len2; j++){
if (s1[i - 1] == s2[j - 1]){ //
lcs[i][j] = lcs[i - 1][j - 1] + 1;
}
else{
lcs[i][j] = 0;
}
if (lcs[i][j] > len){
len = lcs[i][j];
last = i;
}
}
}
return s1.substr(last - len, len);
}
LIS(최대 증가 하위 시퀀스)
int lengthOfLIS(vector& nums) {
int maxlen = 0, len = nums.size();
vector dp(len, 1);
for (int i = 0; i < len; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j])
dp[i] = max(dp[i], dp[j] + 1);
}
maxlen = max(maxlen, dp[i]);
}
return maxlen;
}
문자열 편집 거리(문자열 유사도)
int minDistance(string word1, string word2) {
int len1 = word1.size(), len2 = word2.size();
vector> dist(len1 + 1, vector(len2 + 1, 0));
for (int i = 1; i <= len1; i++){
dist[i][0] = i;
}
for (int i = 1; i <= len2; i++){
dist[0][i] = i;
}
int f;
for (int i = 1; i <= len1; i++){
for (int j = 1; j <= len2; j++){
if (word1[i - 1] == word2[j - 1])
f = 0;
else
f = 1;
dist[i][j] = min(dist[i - 1][j] + 1, dist[i][j - 1] + 1);
dist[i][j] = min(dist[i][j], dist[i - 1][j - 1] + f);
}
}
return dist[len1][len2];
}
교체 문자열:
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.size(), len2 = s2.size();
if (len1 + len2 != s3.size())
return false;
vector> dp(len1 + 1, vector(len2 + 1, false));
dp[0][0] = true;
for (int i = 1; i <= len1; i++){
dp[i][0] = dp[i - 1][0] && (s1[i - 1] == s3[i - 1]);
}
for (int j = 1; j <= len2; j++){
dp[0][j] = dp[0][j - 1] && (s2[j - 1] == s3[j - 1]);
}
for (int i = 1; i <= len1; i++){
for (int j = 1; j <= len2; j++){
dp[i][j] = (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]) || (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]);
}
}
return dp[len1][len2];
}
하위 시퀀스 수(Distinct Subsequences)
int numDistinct(string s, string t) {
int len1 = s.size(), len2 = t.size();
vector> dist(len1 + 1, vector(len2 + 1, 0));
for (int i = 0; i <= len1; i++){
dist[i][0] = 1;
}
for (int i = 1; i <= len1; i++){
for (int j = 1; j <= len2; j++){
dist[i][j] = dist[i - 1][j];
if (s[i - 1] == t[j - 1]){
dist[i][j] += dist[i - 1][j - 1];
}
}
}
return dist[len1][len2];
}
GitHub-Leetcode: https://github.com/wenwu313/LeetCode
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode 문제풀이 노트 113.경로 총 II경로 총 II 제목 요구 사항 문제풀이 두 갈래 나무와 목표와 뿌리 노드에서 잎 노드까지의 모든 경로를 찾는 것은 목표와 같은 경로입니다. 설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다. 예: 다음과 같은 두 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.