S2
S2 copied to clipboard
halfrost
0003. Longest Substring Without Repeating Characters | LeetCode Cookbook
https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0003.Longest-Substring-Without-Repeating-Characters/
@wahyd4 这里的数组index里面的
'a'应该怎么理解呢？
@wahyd4 'a' 是字母的第一个，减去 'a' 就可以算出该字母在 26 个字母表中的排位。排位就对应的是数组的下标。
使用数组来做判断是否存在要比map性能好，很棒
@crissu LeetCode OnlineJudge 就是这样的，有些题如果用 map 性能不好，想办法改成数组，性能就会提升。
打卡
string = input("input: ")
length = 1 if len(string) else 0
index, characterSet = 0, set()
for index1, character in enumerate(string):
while character in characterSet:
characterSet.remove(string[index])
index += 1
else:
characterSet.add(character)
length = length if length >= index1 - index + 1 else index1 - index + 1
print(f"Output: {length}")
python的if-in结构有时候复杂度是O(n), 有时候是O(1)
Java打卡3. 无重复字符的最长子串
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] lastAt = new int[256];
for (int i = 0; i <256; ++i) {
lastAt[i] = -1;
}
int maxLength = 0;
int left = 0;
for (int right = 0; right < s.length(); ++right) {
int ch = (int) s.charAt(right);
left = Math.max(left, lastAt[ch] + 1);
maxLength = Math.max(maxLength, right - left + 1);
lastAt[ch] = right;
}
return maxLength;
}
}
@halfrost
@wahyd4 这里的数组index里面的
'a'应该怎么理解呢？@wahyd4 'a' 是字母的第一个，减去 'a' 就可以算出该字母在 26 个字母表中的排位。排位就对应的是数组的下标。
那为什么freq的长度是256呢？总之因为字符串不止包含小写字母，所以其实没必要 -'a'
@Loverush
@halfrost
@wahyd4 这里的数组index里面的
'a'应该怎么理解呢？@wahyd4 'a' 是字母的第一个，减去 'a' 就可以算出该字母在 26 个字母表中的排位。排位就对应的是数组的下标。
那为什么freq的长度是256呢？总之因为字符串不止包含小写字母，所以其实没必要 -'a'
@Loverush 你说过是有道理的！感谢指点，确实没必要 - 'a'，我更改代码啦。
不好意思，這題我有解出來，不過看了您的解法想請教 解法1的 var bitSet [256]bool 解法2的 var freq [127]int 這兩個array的宣告數字是怎麼來的？ 思考了很久還是想不到，還請您解惑
不好意思，這題我有解出來，不過看了您的解法想請教 解法1的 var bitSet [256]bool 解法2的 var freq [127]int 這兩個array的宣告數字是怎麼來的？ 思考了很久還是想不到，還請您解惑
@whitefloor bitSet [256]，这里的 256 是指的 256 bit 位，用这么长的位做标记。freq [127]int，这里的 127 是指的 127 个字符，这个数组是用来统计每个字符的出现频次的。你可以用更大的数组空间，但是没有必要。比如你写 bitSet [1024]，freq [512]int 也是可以的。