Java怎么使用指針進行搜索

這篇文章主要講解了“Java怎么使用指針進行搜索”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“Java怎么使用指針進行搜索”吧！

Given a string, find the length of the longest substring without repeating characters.  

Examples:   
Given "abcabcbb", the answer is "abc", which the length is 3.   
Given "bbbbb", the answer is "b", with the length of 1.    
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be   
 a substring;"pwke" is a subsequence and not a substring.*

package com.lifeibigdata.algorithms.leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Created by lifei on 16/5/27.
 *
 *  時間復(fù)雜度為O(N)的算法
 使用i和j兩個指針進行搜索，i代表候選的最長子串的開頭，j代表候選的最長子串的結(jié)尾。
 先假設(shè)i不動，那么在理想的情況下，我們希望可以一直右移j，直到j(luò)到達原字符串的結(jié)尾，此時j-i就構(gòu)成了一個候選的最長子串。每次都維護一個max_length，就可以選出最長子串了。
 實際情況是，不一定可以一直右移j，如果字符j已經(jīng)重復(fù)出現(xiàn)過（假設(shè)i在位置k），就需要停止右移了。記錄當前的候選子串并和max_length做比較。接下來為下一次搜尋做準備。
 在下一次搜尋中，i應(yīng)該更新到k+1。這句話的意思是，用這個例子來理解，abcdef是個不重復(fù)的子串，abcdefc中（為了方便記錄為abc1defc2）,c1和c2重復(fù)了。
 那么下一次搜尋，應(yīng)該跨過出現(xiàn)重復(fù)的地方進行，否則找出來的候選串依然有重復(fù)字符，且長度還不如上次的搜索。所以下一次搜索，直接從c1的下一個字符d開始進行，
 也就是說，下一次搜尋中，i應(yīng)該更新到k+1
 */
public class LengthOfLongestSubstring {
    public static void main(String[] args) {
        LengthOfLongestSubstring lols = new LengthOfLongestSubstring();
        System.out.println(lols.lengthOfLongestSubstring("abcdefcgh"));

    }

    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128]; // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; ++j) {
            i = Math.max(index[s.charAt(j)], i);//index['a']會將char轉(zhuǎn)為ascII碼,a是97
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;   //將j所在的值,的對應(yīng)位置存到index數(shù)組中
        }
        return ans;
    }


//    public int lengthOfLongestSubstring(String s) {
//        int n = s.length();
//        Set<Character> set = new HashSet<>();
//        int ans = 0, i = 0, j = 0;
//        while (i < n && j < n) {
//            // try to extend the range [i, j]
//            if (!set.contains(s.charAt(j))){       //如果j沒有出現(xiàn)重復(fù)字符,將j添加到set中,這個過程中,i保持不變
//                set.add(s.charAt(j++));
//                ans = Math.max(ans, j - i);        //比較獲取最大的ans
//            }
//            else {                                 //出現(xiàn)重復(fù)字符,這個字符在i-j之間,所以從i開始逐個刪除,直到不包含重復(fù)字符
//                set.remove(s.charAt(i++));
//            }
//        }
//        return ans;
//    }


//    public int lengthOfLongestSubstring(String s) {    //使用map存儲字母和索引
//        int n = s.length(), ans = 0;
//        Map<Character, Integer> map = new HashMap<>(); // current index of character
//        // try to extend the range [i, j]
//        for (int j = 0, i = 0; j < n; ++j) {
//            if (map.containsKey(s.charAt(j))) {
//                i = Math.max(map.get(s.charAt(j)), i);
//            }
//            ans = Math.max(ans, j - i + 1);
//            map.put(s.charAt(j), j + 1);
//        }
//        return ans;
//    }


//    public int lengthOfLongestSubstring(String s) {
//        int n = s.length();
//        int ans = 0;
//        for (int i = 0; i < n; ++i)
//            for (int j = i + 1; j <= n; ++j)
//                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
//        return ans;
//    }
//
//    public boolean allUnique(String s, int start, int end) {
//        Set<Character> set = new HashSet<>();
//        for (int i = start; i < end; ++i) {
//            Character ch = s.charAt(i);
//            if (set.contains(ch)) return false;
//            set.add(ch);
//        }
//        return true;
//    }
}

感謝各位的閱讀，以上就是“Java怎么使用指針進行搜索”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對Java怎么使用指針進行搜索這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！