leetcode-3. 重複文字なしの最上位列
質問の説明:文字列を指定し、文字列の重複しない文字列の最大長を検索します.
アルゴリズム解析:
文字列や配列クラスの要素を処理する場合、スライドウィンドウは一般的なアルゴリズムです.
スライドウィンドウアルゴリズムは,二重ポインタ[left,right)を用いて文字列に対応するウィンドウサイズを決定するために簡単に記述され,catagery[length=128]は既に出現した要素を格納する.アルゴリズムが開始するとrightポインタが右に移動し、対応する要素を検査し、条件を満たすとcatageryは有効な情報を格納し、rightポインタは右に移動し続ける.条件が満たされていない場合は、左ポインタの対応する要素の有効な情報を削除し、ウィンドウ内の各要素を右に移動してチェックします.
アルゴリズムの実装:
eg1:
:"abcabcbb"
:3
: "abc", 3
eg2:
:"bbbbb"
:1
: "b", 1
アルゴリズム解析:
文字列や配列クラスの要素を処理する場合、スライドウィンドウは一般的なアルゴリズムです.
スライドウィンドウアルゴリズムは,二重ポインタ[left,right)を用いて文字列に対応するウィンドウサイズを決定するために簡単に記述され,catagery[length=128]は既に出現した要素を格納する.アルゴリズムが開始するとrightポインタが右に移動し、対応する要素を検査し、条件を満たすとcatageryは有効な情報を格納し、rightポインタは右に移動し続ける.条件が満たされていない場合は、左ポインタの対応する要素の有効な情報を削除し、ウィンドウ内の各要素を右に移動してチェックします.
アルゴリズムの実装:
public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.isEmpty())
return 0;
int charset[] = new int[256];
int max = 0;
int len = s.length();
// [i,j)
for (int i = 0, j = 0; i < len && j < len;) {
if (charset[s.charAt(j)] == 0) {
// ,
charset[s.charAt(j)] = j - i + 1;
max = max > charset[s.charAt(j)] ? max : charset[s.charAt(j)];
j++;
} else {
// , ,
charset[s.charAt(i)] = 0;
i++;
}
}
return max;
}
}