Shulou(Shulou.com)05/31 Report--

This article mainly explains the "Java how to use the pointer to search", the article explains the content is simple and clear, easy to learn and understand, the following please follow the editor's ideas slowly in depth, together to study and learn "Java how to use the pointer to search" it!

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 * * the algorithm with time complexity O (N) uses I and j pointers to search, where I represents the beginning of the longest substring of the candidate and j represents the end of the longest substring of the candidate. Assuming that I does not move, then ideally we want to move j to the right until j reaches the end of the original string, where Jmuri constitutes a candidate for the longest substring. Maintain a max_length each time, and you can choose the longest substring. The reality is that you may not always be able to move j to the right, but if the character j has been repeated (assuming I is in position k), you need to stop moving right. Record the current candidate substring and compare it with max_length. Next, prepare for the next search. In the next search, I should be updated to knew1. This means that, using this example, abcdef is a non-repeating substring, and C1 and c2 are repeated in abcdefc (to facilitate recording as abc1defc2). Then the next search should be carried out over the place where the repetition occurs, otherwise the candidate string found still has duplicate characters and is not as long as the last search. So the next search will start directly with the next character d of C1, that is, in the next search, I should be updated to Know1 * / 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'] converts char into ascII code, an is 97 ans = Math.max (ans, j-I + 1) Index [s.charat (j)] = j + 1; / / store the corresponding position of j in the index array} return ans;} / / public int lengthOfLongestSubstring (String s) {/ / int n = s.length (); / / Set 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) {/ / if j does not have duplicate characters, add j to set, and in the process, I remains the same / / set.add (s.charAt (jacks +)) / / ans = Math.max (ans, j-I) / / compare to get the largest ans//} / / else {/ / there are duplicate characters between iMJ, so delete them one by one from I until there are no repeating characters / / set.remove (s.charAt (iTunes +)). / /} / / return ans;//} / / public int lengthOfLongestSubstring (String s) {/ / use map to store letters and indexes / / int n = s.length (), ans = 0 current index of character// / Map 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

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.