Java怎么使用指針進行搜索

這篇文章主要講解了“Java怎么使用指針進行搜索”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“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.
 *
 *  時間復雜度為O(N)的算法
 使用i和j兩個指針進行搜索，i代表候選的最長子串的開頭，j代表候選的最長子串的結尾。
 先假設i不動，那么在理想的情況下，我們希望可以一直右移j，直到j到達原字符串的結尾，此時j-i就構成了一個候選的最長子串。每次都維護一個max_length，就可以選出最長子串了。
 實際情況是，不一定可以一直右移j，如果字符j已經重復出現過（假設i在位置k），就需要停止右移了。記錄當前的候選子串并和max_length做比較。接下來為下一次搜尋做準備。
 在下一次搜尋中，i應該更新到k+1。這句話的意思是，用這個例子來理解，abcdef是個不重復的子串，abcdefc中（為了方便記錄為abc1defc2）,c1和c2重復了。
 那么下一次搜尋，應該跨過出現重復的地方進行，否則找出來的候選串依然有重復字符，且長度還不如上次的搜索。所以下一次搜索，直接從c1的下一個字符d開始進行，
 也就是說，下一次搜尋中，i應該更新到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轉為ascII碼,a是97
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;   //將j所在的值,的對應位置存到index數組中
        }
        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沒有出現重復字符,將j添加到set中,這個過程中,i保持不變
//                set.add(s.charAt(j++));
//                ans = Math.max(ans, j - i);        //比較獲取最大的ans
//            }
//            else {                                 //出現重復字符,這個字符在i-j之間,所以從i開始逐個刪除,直到不包含重復字符
//                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怎么使用指針進行搜索”的內容了，經過本文的學習后，相信大家對Java怎么使用指針進行搜索這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！