資訊專欄INFORMATION COLUMN
摘要：用二維數(shù)組進(jìn)行動(dòng)態(tài)規(guī)劃，作為第位和的位已有的重復(fù)子序列長(zhǎng)度最大值計(jì)數(shù)器。
Problem
Given a string, find length of the longest repeating subsequence such that the two subsequence don’t have same string character at same position, i.e., any ith character in the two subsequences shouldn’t have the same index in the original string.
Examplestr = abc, return 0, There is no repeating subsequence
str = aab, return 1, The two subsequence are a(first) and a(second).
Note that b cannot be considered as part of subsequence as it would be at same index in both.
str = aabb, return 2
Solution用二維數(shù)組進(jìn)行動(dòng)態(tài)規(guī)劃，作為第i位和的j位已有的重復(fù)子序列長(zhǎng)度最大值計(jì)數(shù)器。
public class Solution {
/*
* @param str: a string
* @return: the length of the longest repeating subsequence
*/
public int longestRepeatingSubsequence(String str) {
int n = str.length();
int[][] dp = new int[n+1][n+1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i != j && str.charAt(i-1) == str.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[n][n];
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/68210.html
Problem Given a sequence of integers, find the longest increasing subsequence (LIS). You code should return the length of the LIS. Clarification Whats the definition of longest increasing subsequence?...
摘要：哈希表法雙指針法只有當(dāng)也就是時(shí)上面的循環(huán)才會(huì)結(jié)束，，跳過這個(gè)之前的重復(fù)字符再將置為 Problem Given a string, find the length of the longest substring without repeating characters. Example For example, the longest substring without repeat...
摘要：樣例給出，這個(gè)是，返回給出，這個(gè)是，返回挑戰(zhàn)要求時(shí)間復(fù)雜度為或者說明最長(zhǎng)上升子序列的定義最長(zhǎng)上升子序列問題是在一個(gè)無序的給定序列中找到一個(gè)盡可能長(zhǎng)的由低到高排列的子序列，這種子序列不一定是連續(xù)的或者唯一的。 Longest Increasing Subsequence 本文最新版本位于 https://yanjia.me/zh/2018/11/... 給定一個(gè)整數(shù)序列，找到最長(zhǎng)上升子序...
摘要：最長(zhǎng)連續(xù)遞增遞減子序列，設(shè)置正向計(jì)數(shù)器，后一位增加則計(jì)數(shù)器加，否則置。反向計(jì)數(shù)器亦然。每一次比較后將較大值存入。 Problem 最長(zhǎng)連續(xù)遞增／遞減子序列 Give an integer array，find the longest increasing continuous subsequence in this array.An increasing continuous subs...
摘要：解題思路本題借助實(shí)現(xiàn)。如果字符未出現(xiàn)過，則字符，如果字符出現(xiàn)過，則維護(hù)上次出現(xiàn)的遍歷的起始點(diǎn)。注意點(diǎn)每次都要更新字符的位置最后返回時(shí)，一定要考慮到從到字符串末尾都沒有遇到重復(fù)字符的情況，所欲需要比較下和的大小。 Longest Substring Without Repeating CharactersGiven a string, find the length of the lon...
閱讀 3056·2023-04-25 20:09
閱讀 3328·2021-11-23 09:51
閱讀 1981·2021-11-22 15:25
閱讀 3362·2021-11-18 10:02
閱讀 2761·2021-09-27 13:56
閱讀 1317·2019-08-30 15:44
閱讀 1158·2019-08-30 13:21
閱讀 3332·2019-08-30 11:05
