国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LintCode] Longest Repeating Subsequence

Karuru / 1398人閱讀

摘要：用二維數(shù)組進(jìn)行動態(tài)規(guī)劃，作為第位和的位已有的重復(fù)子序列長度最大值計(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.

Example

str = 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)行動態(tài)規(guī)劃，作為第i位和的j位已有的重復(fù)子序列長度最大值計(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)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/68210.html

相關(guān)文章

  • [LintCode] Longest Increasing Subsequence

    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?...

    Flands 評論0 收藏0

  • [LintCode] Longest Substring Without Repeating Cha

    摘要：哈希表法雙指針法只有當(dāng)也就是時上面的循環(huán)才會結(jié)束，，跳過這個之前的重復(fù)字符再將置為 Problem Given a string, find the length of the longest substring without repeating characters. Example For example, the longest substring without repeat...

    Scliang 評論0 收藏0

  • [Lintcode] Longest Increasing Subsequence 最長上升序列

    摘要：樣例給出，這個是，返回給出，這個是，返回挑戰(zhàn)要求時間復(fù)雜度為或者說明最長上升子序列的定義最長上升子序列問題是在一個無序的給定序列中找到一個盡可能長的由低到高排列的子序列，這種子序列不一定是連續(xù)的或者唯一的。 Longest Increasing Subsequence 本文最新版本位于 https://yanjia.me/zh/2018/11/... 給定一個整數(shù)序列，找到最長上升子序...

    hlcc 評論0 收藏0

  • [LintCode] Longest Increasing Continuous Subseque

    摘要：最長連續(xù)遞增遞減子序列，設(shè)置正向計(jì)數(shù)器，后一位增加則計(jì)數(shù)器加，否則置。反向計(jì)數(shù)器亦然。每一次比較后將較大值存入。 Problem 最長連續(xù)遞增／遞減子序列 Give an integer array，find the longest increasing continuous subsequence in this array.An increasing continuous subs...

    wwq0327 評論0 收藏0

  • [Leetcode]Longest Substring Without Repeating Char

    摘要：解題思路本題借助實(shí)現(xiàn)。如果字符未出現(xiàn)過，則字符，如果字符出現(xiàn)過，則維護(hù)上次出現(xiàn)的遍歷的起始點(diǎn)。注意點(diǎn)每次都要更新字符的位置最后返回時，一定要考慮到從到字符串末尾都沒有遇到重復(fù)字符的情況，所欲需要比較下和的大小。 Longest Substring Without Repeating CharactersGiven a string, find the length of the lon...

    awesome23 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<