ARTS-WEEK 2 | Eric Jin

Algorithm

LeeCode 的第三题，中等难度。

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.

此题寻找字符串中最长的不重复字符子串。
起始思路是找每一个子串，然后每个子串没有重复字符。这个思路确实是最直接，最暴力的，但是也是最没有算法和数据结构的。

solution

public int lengthOfLongestSubstring(String s) {
    int max = 0;
    for (int i = 0; i < s.length() - 1; i++) {
        for(int j = i+ 1; j<s.length(); j++ ) {
            if(allUnique(s,i,j)) max = Math.max(max,j-i);
        }
    }
    return max;
}

private boolean allUnique(String s, int i, int j) {
    Set<Character> set = new HashSet<>();
    for (int k=i;k<j;k++){
        if (set.contains(s.charAt(k))) return false;
        set.add(s.charAt(k));
    }
    return true;
}

test

@Test
public void lengthOfLongestSubstring() {
    LongestSubstring ls = new LongestSubstring();
    String s = "abcabcbb";
    String s1 = "bbbbb";
    String s2 = "pwwkew";

    assertEquals(3,ls.lengthOfLongestSubstring(s));
    assertEquals(1,ls.lengthOfLongestSubstring(s1));
    assertEquals(3,ls.lengthOfLongestSubstring(s2));
}

思路简单粗暴，时间复杂度自然也就是最差的，三个循环 $O(n^3)$。

之后在官方的solution和discuss中找到了一点提示，用两个指针和hash map，记录着不重复的最长子串。右指针扫过整个字符串，找到有相同的字符，左指针滑到右指针位置。leetcode 把这个称之为slide window。

solution

/**
    * create a hash map to maintain the character and integer
    * use two pointer to define the max substring.
    * right to scan the whole string,if there contains the character,
    * move the left pointer to the right pointer.
    * and the same way,compare the max substring's length
    * @param s
    * @return
    */
public int lengthOfLongestSubstringUsingSlideWindow(String s) {
    Map<Character,Integer> map = new HashMap<>();
    int max = 0;
    for (int i = 0 , j = 0; i < s.length(); i++) {
        if (map.containsKey(s.charAt(i))) {
            j = Math.max(j, map.get(s.charAt(i)));
        }
        max = Math.max(max, i - j + 1);
        map.put(s.charAt(i), i + 1);
    }
    return max;
}

这个的时间复杂度就下来了，$O(n)$

Review

这周看到的这篇文章比较印象深刻，Reversing a Linked List: Easy as 1, 2, 3
This article talk about how to reverse a Linked List,it says that the common way to reverse it is to swap the head and the tail,util the two point meet at the middle, but this situation only happen when the linked List is a double linked list. When you only have a single reference,you can’t use this way.
The second is to dump it into another data structure,like array. But when there are many nodes of the linked list,it would take lots of RAM.
所以这个文章的中心思想就是，三个指针，current、previous、following. 用三个指针来记录。

Set following equal to following.next

Set current.next equal to previous

Set previous equal to current

Set current equal to following

function reverse(head) {
// Step 1
  let previous = null
  let current = head
  let following = head
// Step 2
  while(current !== null) {
    following = following.next
    current.next = previous
    previous = current          
    current = following
  }
// Step 3  
  return previous
}

Tip

这周看了Spring MVC官方文档里面的Bean Scope. Spring 中默认的Scope是singleton，也就是整个Spring的IoC 容器里面只有一个对象。而我们在web 应用中，常常会需要跟request、session、application相关的对象，比如每个用户的登陆请求，用户的账户信息，网站的相关信息，这些就不能用单例对象来进行了。实现 scope 的配置也很简单，两种，一种 XML 的，一种annotation的。现在用应该用annotation的会比较多一些。
首先要想明白，如果那个 bean 不是singleton，这个时候，我们常常会把非单例的bean 注入到单例对象中去，这个时候，因为单例对象之后再容器中初始化一次，你注入的非单例的，也就只会是最开始注入的哪一个。所以，在 XML 配置的时候，需要开启代理。注入的时候注入这个 bean 的代理，然后每次请求的时候，会找代理，而代理会找到委托的那个真实的bean。

<bean id="userPreferences" class="com.foo.UserPreferences" scope="session">
    <aop:scoped-proxy/>
</bean>

<bean id="userManager" class="com.foo.UserManager">
    <property name="userPreferences" ref="userPreferences"/>
</bean>

要注意<aop:scoped-proxy/>，如果不使用代理，userManager bean 中注入的userPreferences bean 就会使最开始初始化的那个。
annotation 如果使用annotation的话，它默认就是开启了代理的，所以只需要直接使用@RequestScope,@SessionScope,@ApplicationScope就可以了。

This Week,Share a article about data structure: The top data structures you should know for your next coding interview

Algorithms + Data Structures = Programs

自己还买了《算法（第4版）》这本书，可惜还没看，英文版，板砖一块。跟最近看的《Java编程思想（第4版）》一样的厚。入了耗子叔的坑，在专业的道路上渐行渐远！