BAT面試算法進(jìn)階(3)- 無重復(fù)字符的最長子串(滑動窗口法)
BAT面試算法進(jìn)階(2)- 無重復(fù)字符的最長子串(暴力法)
BAT面試算法進(jìn)階(1)--兩數(shù)之和
上一次分享的是滑動窗口解決方法.執(zhí)行的次數(shù)2N個步驟.但是是否還有辦法優(yōu)化了? 答案是肯定的!
一.算法題
- 題目
Given a string, find the length of the longest substring without repeating characters.
- Example
- 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
- Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
二.算法題解讀
題目大意:給定一個字符串,找出不含有重復(fù)字符的最長子串的長度
解讀Example
- 給定"abcabcbb",沒有重復(fù)字符的最長子串是"abc",那么長度就是3
- 給定"bbbbb",最長子串就是"b",長度就是1
- 給定pwwkew,最長子串就是"wke",長度為3,
- ==注意,==必須是一個子串."pwke",是子序列,而不是子串
三.優(yōu)化"滑動窗口"解決思路
到底如何在滑動窗口方法上優(yōu)化了? 實(shí)際上我們可以如果采用進(jìn)一步優(yōu)化,可以達(dá)到只需要N次即可計(jì)算成功.我們可以定義字符到索引映射.而不是使用集合來判斷這個字符的存在與否.當(dāng)遇到重復(fù)的字符時,我們即可跳過該滑動窗口.
也可以理解為,如果s[j]在[i,j)的范圍內(nèi)有與j'重復(fù)的字符.我們不需要逐漸增加i.而是直接跳過[i,j']范圍內(nèi)的所有元素.并將i變成為j'+1就可以做到.
四.代碼實(shí)現(xiàn)
java code
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
//獲取當(dāng)前字符索引
Map<Character, Integer> map = new HashMap<>();
//修改[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;
}
}
五.使用ASCII 128碼 思路
字符串,其實(shí)由字符構(gòu)成.而字符則可以用ASC碼來替代.如此,我們可以用整數(shù)數(shù)組作為直接訪問表來替換Map.
常用表如下:
int [26],用于表示字母 "a" - "z" 或 "A" - "Z";
int [128],用于表示ASCII碼
int [256],用于表示擴(kuò)展ASCII碼
A = 65, a = 97
六.代碼實(shí)現(xiàn)
java code
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
int[] index = new int[128];
for (int j = 0, i = 0; j < n; j++) {
i = Math.max(index[s.charAt(j)], i);
ans = Math.max(ans, j - i + 1);
index[s.charAt(j)] = j + 1;
}
return ans;
}
}
小編OS:
如有疑問,留言即可.胖C會利用空余時間給大家做一個簡單解答的.
持續(xù)更新關(guān)注公眾號!
