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

創(chuàng)新互聯(lián)公司是專業(yè)的仙桃網(wǎng)站建設(shè)公司，仙桃接單;提供成都網(wǎng)站制作、網(wǎng)站設(shè)計(jì),網(wǎng)頁(yè)設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行仙桃網(wǎng)站開(kāi)發(fā)網(wǎng)頁(yè)制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛(ài)的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來(lái)合作!

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.
 *
 *  時(shí)間復(fù)雜度為O(N)的算法
 使用i和j兩個(gè)指針進(jìn)行搜索，i代表候選的最長(zhǎng)子串的開(kāi)頭，j代表候選的最長(zhǎng)子串的結(jié)尾。
 先假設(shè)i不動(dòng)，那么在理想的情況下，我們希望可以一直右移j，直到j(luò)到達(dá)原字符串的結(jié)尾，此時(shí)j-i就構(gòu)成了一個(gè)候選的最長(zhǎng)子串。每次都維護(hù)一個(gè)max_length，就可以選出最長(zhǎng)子串了。
 實(shí)際情況是，不一定可以一直右移j，如果字符j已經(jīng)重復(fù)出現(xiàn)過(guò)（假設(shè)i在位置k），就需要停止右移了。記錄當(dāng)前的候選子串并和max_length做比較。接下來(lái)為下一次搜尋做準(zhǔn)備。
 在下一次搜尋中，i應(yīng)該更新到k+1。這句話的意思是，用這個(gè)例子來(lái)理解，abcdef是個(gè)不重復(fù)的子串，abcdefc中（為了方便記錄為abc1defc2）,c1和c2重復(fù)了。
 那么下一次搜尋，應(yīng)該跨過(guò)出現(xiàn)重復(fù)的地方進(jìn)行，否則找出來(lái)的候選串依然有重復(fù)字符，且長(zhǎng)度還不如上次的搜索。所以下一次搜索，直接從c1的下一個(gè)字符d開(kāi)始進(jìn)行，
 也就是說(shuō)，下一次搜尋中，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']會(huì)將char轉(zhuǎn)為ascII碼,a是97
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;   //將j所在的值,的對(duì)應(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沒(méi)有出現(xiàn)重復(fù)字符,將j添加到set中,這個(gè)過(guò)程中,i保持不變
//                set.add(s.charAt(j++));
//                ans = Math.max(ans, j - i);        //比較獲取最大的ans
//            }
//            else {                                 //出現(xiàn)重復(fù)字符,這個(gè)字符在i-j之間,所以從i開(kāi)始逐個(gè)刪除,直到不包含重復(fù)字符
//                set.remove(s.charAt(i++));
//            }
//        }
//        return ans;
//    }


//    public int lengthOfLongestSubstring(String s) {    //使用map存儲(chǔ)字母和索引
//        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怎么使用指針進(jìn)行搜索”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)Java怎么使用指針進(jìn)行搜索這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！

標(biāo)題名稱：Java怎么使用指針進(jìn)行搜索
分享鏈接：http://chinadenli.net/article0/gsgoio.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、虛擬主機(jī)、網(wǎng)站排名、面包屑導(dǎo)航、、自適應(yīng)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)