0

「abcabcbb」を指定すると、答えは「abc」で、長さは 3 です。

「bbbbb」を指定すると、答えは長さ 1 の「b」になります。

「pwwkew」を指定すると、答えは「wke」で、長さは 3 です。答えは部分文字列でなければならないことに注意してください。「pwke」は部分文字列ではなく部分列です。

機能するソリューションを思いつきましたが、いくつかのテストケースで失敗しました。その後、より良い解決策を見つけ、それを書き直して理解しようとしました。以下の解決策は問題なく動作しますが、この問題と約 2 時間格闘した後でも、この特定のコード行が機能する理由を理解できません。

import java.util.*;
import java.math.*;

public class Solution {

  public int lengthOfLongestSubstring(String str) {

  if(str.length() == 0)
    return 0;

  HashMap<Character,Integer> map = new HashMap<>();
  int startingIndexOfLongestSubstring = 0;
  int max = 0;

  for(int i = 0; i < str.length(); i++){
      char currentChar = str.charAt(i); 
      if(map.containsKey(currentChar))
         startingIndexOfLongestSubstring = Math.max(startingIndexOfLongestSubstring, map.get(currentChar) + 1);

      map.put(currentChar, i);
      max = Math.max(max, i - startingIndexOfLongestSubstring + 1);

      }//End of loop

    return max;

   }
}

問題の行は

max = Math.max(max, i - startingIndexOfLongestSubstring + 1);

なぜこれが機能するのかわかりません。以前の最大値の間の最大値と、現在のインデックスと現在最も長い部分文字列の開始インデックスとの差を取り、1 を追加しています。コードが現在のインデックスとの差を取得していることはわかっています。 startingIndexOfSubstringですが、意図した結果が得られる理由を概念化できません。特になぜそれが機能するのか、誰かが私にこのステップを説明してもらえますか?

4

2 に答える 2

3

説明が下手な私ですが、例を挙げて考えてみましょう。

文字列は「wcabcdeghi」です。

少しの間コードを忘れて、ロジックを考え出そうとしていると仮定してください。

  1. w から始めて、c -> a -> b -> c に到達するまで続けます。
    「c」が繰り返されているため、この時点で停止する必要があります。そのため、文字が繰り返される場合に保存するマップが必要です。(コード内 map.put(currentChar, i);:)
  2. 文字が繰り返されるかどうかがわかったので、最大値を知る必要があります。ここまでの長さ。(コード内 - )max
  3. これで、最初の 2 つの変数 w->c のカウントを追跡しても意味がないことがわかりました。これを含めて、すでにMaxを取得しているからです。価値。したがって、次の反復以降は、a -> b -> すぐに長さのみをチェックする必要があります。これを追跡するために
    、変数 (コード内 - )を用意します。startingIndexOfLongestSubstring(これは startingIndexOfNonRepetativeCharacter という名前にする必要がありましたが、やはり名前付けも苦手です)。
  4. 再び続行しますが、現在解析している部分文字列を追跡する方法がまだ確定していないのを待ちます。(つまり、abcd から...)
    考えてみると、必要なのは "a" があった位置 (つまりstartingIndexOfNonRepetativeCharacter) だけなので、現在の部分文字列の長さを知るには (でcode - ) i - startingIndexOfLongestSubstring + 1(現在の文字位置 - 非反復文字の長さ + (減算は両辺を含めないので 1 を足す)。これを呼び出しましょう。currentLength
  5. しかし、待ってください。このカウントをどうするのでしょうか。新しい変数を見つけるたびに、これcurrentLengthが最大値を超える可能性があるかどうかを確認する必要があります。そう（コード内 -）max = Math.max(max, i - startingIndexOfLongestSubstring + 1);
  6. これで、必要なステートメントのほとんどをカバーしました。ロジックによれば、既に存在する変数に遭遇するたびに、必要なのは だけですstartingIndexOfLongestSubstring = map.get(currentChar)。では、なぜ私たちは を行っているのMaxでしょうか?
    String が「wcabcdewghi」であるシナリオを考えてみましょう。新しいカウンターを a -> b -> c -> d -> e -> wとして処理し始めると、この時点でロジックはこの文字が以前に存在したかどうかをチェックします。現在は、インデックス "1" からカウントを開始します。これは、カウント全体を完全に台無しにします。そのため、マップから取得する次のインデックスが常にカウントの開始点よりも大きいことを確認する必要があります (つまり、文字が の前に出現する場合にのみマップから文字を選択しますstartingIndexOfLongestSubstring)。

コード内のすべての行に回答したことを願っています。主に説明が理解できた場合。

于 2017-01-07T19:54:09.197 に答える
1

なぜなら

i - startingIndexOfLongestSubstring + 1

iとstartingIndexOfLongestSubstringインデックスの間の文字数です。たとえば、位置 2 と 3 の間の文字数は? 3-2=1ただし、位置 2 と位置 3 の 2 つの文字があります。

コード内のすべてのアクションについて説明しました。

public class Solution {

    public int lengthOfLongestSubstring(String str) {

        if(str.length() == 0)
            return 0;

        HashMap<Character,Integer> map = new HashMap<>();
        int startingIndexOfLongestSubstring = 0;
        int max = 0;

        // loop over all characters in the string
        for(int i = 0; i < str.length(); i++){
            // get character at position i
            char currentChar = str.charAt(i);
            // if we already met this character
            if(map.containsKey(currentChar))
                // then get maximum of previous 'startingIndexOfLongestSubstring' and 
                // map.get(currentChar) + 1 (it is last occurrence of the current character in our word before plus 1)
                // "plus 1" - it is because we should start count from the next character because our current character 
                // is the same
                startingIndexOfLongestSubstring = Math.max(startingIndexOfLongestSubstring, map.get(currentChar) + 1);

            // save position of the current character in the map. If map already has some value for current character 
            // then it will override (we don't want to know previous positions of the character)
            map.put(currentChar, i);
            // get maximum between 'max' (candidate for return value) and such value for current character
            max = Math.max(max, i - startingIndexOfLongestSubstring + 1);

        }//End of loop

        return max;

    }
}
于 2017-01-07T19:00:54.823 に答える