算法面试汇总（三十三）

Coding的哔哔叨叨 2020-12-07

111

👉👀💬今日练习（一）无重复字符的最长子串（LeetCode-3）。

🙋解法一：滑动窗口+双指针。

🙇思路：

像这种找一个子集的题目，一般都是可以用滑动窗口来做。

此解法主要思路就是双指针（l左指针,r右指针）+滑动窗口，一次只移动其中一个指针。

移动有指针r，并将元素和下标作为key-val放入map中，继续移动r。
当r移动到某个位置是，map中已有此元素，说明元素重复，此时开始移动左指针缩小窗口，剔除重复元素。
重复1、2，知道r走到最右边。

代码：

public int lengthOfLongestSubstring(String s){
    int n =s.length(),result=0;
    Map<Character,Integer> characterMap =new HashMap<>();
    for(int r=0,l=0;r<n;r++){
        if(characterMap.containsKey(s.charAt(r))){
        //这儿为啥取出下标要+1？
        //我们向map中放的是元素的下标，遇到重复元素，
        //从下个元素开始不重复,所以要+1。
            l=Math.max(characterMap.get(s.charAt(r))+1,l);
        }
        result=Math.max(result,r-l+1);
        characterMap.put(s.charAt(r),r);
    }
    return result;
}

🙋解法二：滑动窗口+双指针。

🙇思路：

解法二依旧是滑动窗口+双指针，不过我们思路是另一个逻辑。

依旧是先移动有指针，然后向set中添加遍历过的元素，并在遍历过程中不断更新不重复子串的最大长度。
遇到重复元素，右指针r停下，左指针l开始移动，并从set中移除l所对应的元素，一直移动l到r所对应的重复元素被移除后，再继续开始移动r。
重复1、2直到l或r越界。

代码：

public int lengthOfLongestSubstring(String s) {
        int result = 0, l = 0, r = 0;
        int length = s.length();
        Set<Character> characterSet = new HashSet<>();
        while (l < length && r < length) {
            if (!characterSet.contains(s.charAt(r))) {
            characterSet.add(s.charAt(r++));
            result = Math.max(result, r - l);
        } else {
       //开始移动左指针，直到r现在所对应的元素被清理。
       //与解法一种，
       //l=Math.max(characterMap.get(s.charAt(r))+1,l);
       //最终的效果是一样的。
            characterSet.remove(s.charAt(l++));
        }
        }
    return result;
}

👉👀💬今日练习（二）有效的括号（LeetCode-20）。输入的字符串只包含"("、")"、"{"、"}"、"["、"]"，判断是否为有效括号。括号必须是成对且顺序必须正确，举例：

输入："(){[]}"
输出：true


输入："([)]"
输出：false
解析：虽然括号是成对的，但是顺序不正确。

🙋解法：栈+字典表。

🙇思路：

我们用一个字典表，key为左括号，value为右括号做一个对应。

利用栈先进后出的特性，遍历字符串，左括号出现时，放入栈中，边括号出现时，取出栈中的头元素与之进行匹配，如果不能匹配，则一定不是有效的括号。

代码：

/**
* 构建一个字典表
*/
//java8实例化集合的新写法
private static final Map<Character, Character> dict = new HashMap<Character, Character>() {{
    put('(',')');
    put('[',']');
    put('{','}');
}};
public boolean isValid(String s) {
//如果字符串中第一个字符就不是字典表的key直接返回即可。
    if (s.length() > 0 && !dict.containsKey(s.charAt(0))) return false;
//构建一个栈，默认放入一个元素？用以占位
    LinkedList<Character> stack = new LinkedList<Character>() {{
        add('?');
    }};
    //遍历所有字符，
    for (Character c : s.toCharArray()) {
    //如果是左括号，放入栈中
        if (dict.containsKey(c)) stack.addLast(c);
        // 如果不是左括号，取出栈中最近放入的左括号进行匹配
        //这儿用equals就报错了
        else if (dict.get(stack.removeLast()) != c) return false;
    }
    return stack.size() == 1;
}

不积跬步，无以至千里。

文章有帮助的话，点个转发、在看呗。
谢谢支持哟 (*^__^*)

END

👇

面试

文章转载自Coding的哔哔叨叨，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

算法面试汇总（三十三）

评论