leetcode 算法入门 第六天

第一题：3. 无重复字符的最长子串
public int lengthOfLongestSubstring(String s) {
int max =0;
int lefe = 0;
for (int i = 0; i < s.length(); i++) {
int evenLength =0;
for (int j = i; j < s.length()-i; j++) {
if (s.charAt(i) != s.charAt(j)) {
evenLength++;
} else {break;}
}
max =Math.max(max,evenLength);
}
return max;
}
恩？测试都没过，结果是0，预期是3. 因为第二层循环不+1就会导致 直接相等直接返回0个的长度
public int lengthOfLongestSubstring(String s) {
int max =0;
for (int i = 0; i < s.length(); i++) {
int evenLength =1;
for (int j = i+1; j < s.length(); j++) {
if (s.charAt(i) != s.charAt(j)) {
evenLength++;
} else { return evenLength;}
}
max =Math.max(max,evenLength);
}
return max;
}
测试单例过， 通过测试用例：86 / 987。得用hashset来做，abcbb 这样拿单个做，就变成长度为5了。
public static int lengthOfLongestSubstring(String s) {
int max =0;
HashSet characters = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
characters.add(s.charAt(i));
int evenLength =1;
for (int j = i+1; j < s.length(); j++) {
if (characters.contains(s.charAt(j)) == false) {
characters.add(s.charAt(j));
evenLength++;
} else { break;}
}
max =Math.max(max,evenLength);
characters = new HashSet<>();
}
return max;
} 哈哈，过了过了。但是结果菜到极致了
执行用时：99 ms, 在所有 Java 提交中击败了7.79% 的用户
内存消耗：41.7 MB, 在所有 Java 提交中击败了23.25% 的用户
通过测试用例：987 / 987
去题解里面偷学一手 滑动窗口。
public static int lengthOfLongestSubstring(String s) {
int max = 0;
HashMap hashMap = new HashMap<>();
for (int start = 0, end = 0, n = s.length(); end < n; end++) {
char c = s.charAt(end);
if (hashMap.containsKey(c)) {
start = Math.max(hashMap.get(c) + 1, start);
}
max = Math.max(max, end - start + 1);
hashMap.put(c, end);
}
return max;
}
start = Math.max(hashMap.get(c) + 1, start); 更新 start 位置时+1，就是舍去前面重复元素。
停停，还以找工作为目的， 2022-5-15停
停奶奶个腿，不就是被难住了吗，可真是弟弟，2022-5-16 开
public boolean checkInclusion(String s1, String s2) {
char[] pattern = s1.toCharArray();
char[] text = s2.toCharArray();
int pLen = pattern.length;
int tLen = pattern.length;
int[] pFeq = new int[26];
int[] tFeq = new int[26];
//记录s1的频数
for (int i = 0; i < pLen; i++) {
pFeq[pattern[i] - ‘a’]++;
}
// 记录s1的频数的个数
int pCount = 0;
for (int i = 0; i < pFeq.length; i++) {
if (pFeq[i] > 0) pCount++;
}
int left = 0;
int right = 0;
// 为了达成和pCount在一样的情况下才可判为含有相同的子字符串排列。
int winCount = 0;
while (right < tLen) {
//s1中有的 s2才加数
if (pFeq[text[right] - ‘a’] > 0) tFeq[text[right] - ‘a’]++;
if (pFeq[text[right] - ‘a’] == tFeq[text[right] - ‘a’]) {
winCount++;
}
right++;
//左边界 一直移动
while (pCount == winCount) {
if (right - left == pLen) return true;
if (pFeq[text[left] - ‘a’] > 0) tFeq[text[left] - ‘a’]—;
if (pFeq[text[left] - ‘a’] == tFeq[text[left] - ‘a’]) {
winCount—;
}
}
}
return false;
}
if循环要包含下一层 ， 不然第一个就会导致第一个不在s1的元素 pFeq[text[right] - ‘a’] == tFeq[text[right] - ‘a’] 恒为 0=0；这样就错了
正解为：
public static boolean checkInclusion(String s1, String s2) {
char[] pattern = s1.toCharArray();
char[] text = s2.toCharArray();

int pLen = pattern.length;<br />    int tLen = text.length;
int[] pFreq = new int[26];<br />    int[] tFreq = new int[26];
//记录s1的频数<br />    for (int i = 0; i < pLen; i++) {<br />        pFreq[pattern[i] - 'a']++;<br />    }
// 记录s1的频数的个数<br />    int pCount = 0;<br />    for (int i = 0; i < 26; i++) {<br />        if (pFreq[i] > 0) {<br />            pCount++;<br />        }<br />    }
int left = 0;<br />    int right = 0;
// 为了达成和pCount在一样的情况下才可判为含有相同的子字符串排列。<br />    int winCount = 0;<br />    while (right < tLen) {<br />        //s1中有的 s2才加数<br />        if (pFreq[text[right] - 'a'] > 0) {<br />            tFreq[text[right] - 'a']++;<br />            if (pFreq[text[right] - 'a'] == tFreq[text[right] - 'a']) {<br />                winCount++;<br />            }<br />        }<br />        right++;<br />        //左边界 一直移动<br />        while (pCount == winCount) {<br />            if (right - left == pLen) {<br />                return true;<br />            }<br />            if (pFreq[text[left] - 'a'] > 0) {<br />                tFreq[text[left] - 'a']--;<br />                if (pFreq[text[left] - 'a'] > tFreq[text[left] - 'a']) {<br />                    winCount--;<br />                }<br />            }<br />            left++;<br />        }<br />    }<br />    return false;<br />}