LeetCode third topic (the Longest Substring Without Repeating Characters) trilogy # 3: two optimization

欢迎访问我的GitHub

这里分类和汇总了欣宸的全部原创(含配套源码)：

https://github.com/zq2599/blog_demos

• 本文是《LeetCode第三题(Longest Substring Without Repeating Characters)三部曲》的第三篇,The previous two articles laid out the ideas and wrote them outJava代码,虽然在LeetCodeSubmitted by the website,但是成绩并不理想,40multi-millisecond speed,There is a big gap with many excellent programs,Let's optimize the code together today,提升速度;

Trilogy full link

• 《LeetCode第三题(Longest Substring Without Repeating Characters)三部曲之一：解题思路》
  ;

• 《LeetCode第三题(Longest Substring Without Repeating Characters)三部曲之二：编码实现》
  ;

• 《LeetCode第三题(Longest Substring Without Repeating Characters)三部曲之三：两次优化》
  ;

原有代码

• Here's a look back at the original code：

public int lengthOfLongestSubstring(String s) {
 //窗口的起始位置,until the end of the window,longest record
 int left = 0, right = 0, max = 0;

 //Indicates what values ​​are in the window
 Set<Character> set = new HashSet<>();

 while (right < s.length()) {
 //例如&quot;abcdc&quot;,inside the window is&quot;abcd&quot;,此时right等于[4],
 //found in the windowarray[right]的值,Just shrink the left side of the window,
 //No shrinking to the windowarray[right]的值为止,
 //当leftGet bigger all the way,直到left=3的时候,There is no longer in the windowarray[right]的值了
 if (set.contains(s.charAt(right))) {
 //If the window is&quot;abc&quot;,当前是&quot;c&quot;,Then the code below will only work&quot;a&quot;删除,left加一,再次循环
 //And a new cycle is still found&quot;c&quot;还在set中,就再把&quot;b&quot;删除,left再加一...
 set.remove(s.charAt(left++));
 } else {
 //Not in the windowarray[right]的时候,就把array[right]的值放入set中,Indicates what values ​​are in the current window
 set.add(s.charAt(right++));

 if ((right - left) > max) {
 max = right - left;
 }
 }
 }

 return max;
 }


第一次优化

• 这次的重点是HashSet对象,This object holds all the elements in the window,Check before adding a new elementHashSet中是否存在该元素;

• 如下图所示,代码中通过
  set.add
  和
  set.remove
  方法将HashSetThe content in the window is always consistent with the content in the window：
  

• 优化前：Determines whether an element is in the window,The current approach isHashSet中为准,When it is determined that an element is to be removed from the window,就调用HashSet的remove方法从HashSet中删除;

• The above code can be optimized,It is not necessary to execute after optimizationHashSet的remove方法,The specific logic is to useHashMap替代HashSet,HashMap的key是字符串的元素,valueis the position of the element in the array,举个例子,当left=1,right=3时,The overall effect is as shown below,HashMap中已经保存了"a"、"b"、"c"Three elements askey,而valueare their subscripts in the array：
  

• Now to check the subscript in the array is4的元素"b"：以"b"为key查找HashMap,If it does not exist, it means not in the window,如果存在,就用对应的value=1去和left比较,如果小于leftIt means not in the window,如果大于或者等于leftis displayed in the window,如下图所示：

• 这里要注意的是：hashmap中任意一个value,Indicates that an element is present
  整个数组
  中的位置,instead of the position in the window,Because the program will not be righthashmap做remove操作;

• Then analyze the graph above,"b"After the element is found to exist in the window,除了将left调整为2,right调整为4,还要调用HashMap的put方法,将"b"The position of the element is changed from the original1更新为4;

• There is another optimization point：Suppose it is in the current window"abc",And the checked element is "b",之前的代码中,To execute the loop twice：先删除"a",left加一,再删除"b",left再加一,现在用了HashMap就能得到"b"的位置,直接将left改为"b"的下一个位置即可,There is no need to execute the loop twice;

• The above is the optimization idea,用HashMap取代HashSet,不再执行remove方法,The tweaks to the code are not that big,The adjusted full code is as follows：

public int lengthOfLongestSubstring(String s) {
 int left =0, right =0, max = 0;
 Map<Character,Integer> map = new HashMap<>();
 while (right<s.length()){
 //mapIf it does not exist, it means that it is not in the window
 if(map.containsKey(s.charAt(right))){
 int pos = map.get(s.charAt(right));
 //map中如果存在,再检查value和left,to determine whether it is in the window
 if(pos>=left){
 //Note that this is another optimization point,Suppose it is in the current window&quot;abc&quot;,And the checked element is &quot;b&quot;,
 //之前的代码中,To execute the loop twice：先删除&quot;a&quot;再删除&quot;b&quot;,
 //现在用了HashMap就能得到&quot;b&quot;的位置,直接将left改为&quot;b&quot;的下一个位置即可,There is no need to execute the loop twice
 left = pos + 1;
 }
 }
 map.put(s.charAt(right), right++);
 if((right-left)>max){
 max = right-left;
 }
 }

 return max;
 }


• Submit the above code to LeetCode,This time the result is27毫秒,Much better than before,如下图：
  

• 然而,This result is still mediocre,Because it can still be optimized,Then optimize again;

第二次优化

• The first optimization point is eliminationremove方法和while循环次数,The second optimization is forHashMap,Each time a new element is processed it is involvedHashMap的操作,如果您对HashMapcontent is understood,know how to calculatehashcode、创建EntrySet,调用equalsMethods These operations are performed frequently,If these operations can be omitted,Then the performance should be significantly improved,问题是：How to get rid ofHashMapwithout affecting the function？

• 我们先明确HashMap在程序中的作用：
  Holds the position of an element in an array
  ,So the direction of optimization is to findHashMap的替代品;

• Suppose a total of twenty-six characters may appear：从"a"到"z",那就简单了,用一个长度为26的intArray to record the position of each character,array[0]的值就是元素"a"的位置,array[1]的值就是元素"b"的位置,array[2]的值就是元素"c"的位置,如下图所示,图中的数字97是"a"的ASCII码：
  

• 按照上面的设计,array[0]=3就表示"a"The position of the element's last occurrence in the entire array is3,array[1]=1表示"b"The position of the element's last occurrence in the entire array is1,array[2]=2就表示"c"The position of the element's last occurrence in the entire array is2,如下图：
  

• According to the above design, it can be coded and submitted immediatelyLeetCode了呢？That's what I did at the time,Unfortunately the commit failed because the test didn't pass,The reason for not passing is：Not only in strings"a"到"z"的小写,There are also capital letters、空格字符、characters such as addition, subtraction, multiplication and division,遇到这些字符时,The length we designed earlier26array is not enough,It appears to be redesigning the array;

• The total length of the new array is 95,This is because all English visible characters are in total95个,从空格开始,到"`"结束,如下图的三个红框所示：

• 如上所示,长度为95的数组,All visible characters can be included,array[0]What is saved is the position of the space character,So count characters"a"在arrayThe subscripts in the array are from before**'a'-97=0
  变成了
  'a'-32=65**;

• 另外要注意的是,The initial value of each element in this array is **-1**,Indicates that the element does not exist in the string(Or that it hasn't been dealt with yet);

• The code optimized according to the above ideas is shown below,It can be seen that the changes are not significant,只是把HashMapAll relevant places have been changed to the above array logic：

public int lengthOfLongestSubstring(String s) {
 int left =0, right =0, max = 0;

 int[] array = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 -1, -1, -1, -1, -1};

 int offset;
 while (right<s.length()){
 //offsetIndicates that the currently processed element is inarray数组中的下标,
 //If the current element is a space,那么减去32后等于0,array[offset]即array[0],
 //这个array[0]The value of is the position of the space character in the string
 offset = s.charAt(right) - 32;

 if(array[offset]>-1){
 int pos = array[offset];

 if(pos>=left){
 left = pos + 1;
 }
 }

 array[offset] = right++;

 if((right-left)>max){
 max = right-left;
 }
 }

 return max;
 }


• Submit the above code to LeetCode,顺利通过,grades increased to 17ms,超过了99.94%的java方案,如下图：
  

• The final effect proves that the direction and results of this optimization are correct,Some friends have already asked where the optimization idea comes from,Actually inspired by
  桶排序
  ,思想是类似的;

• 至此,LeetCodeThe solution to the third problem、编码实现、The optimization practice is all completed,I hope it can give readers some reference in the process of solving the problem,刷题之路,大家一起努力！

欢迎关注InfoQ：程序员欣宸

学习路上,你不孤单,欣宸原创一路相伴...