最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

LC 3. 无重复字符的最长子串 全球实时

来源：博客园


【资料图】

> 原题链接:3. 无重复字符的最长子串 - 力扣（LeetCode）

class Solution {    public int lengthOfLongestSubstring(String s) {        /*        * 思路:        *        单调栈        *       构建一个用一个队列存放已经遍历过的元素, 如果当前元素在队列中已经存在, 那么不停出队到队列里        *    和当前元素相同的元素的下一个位置, 把当前元素放进去, 每次元素入队, 都更新一次最大值, 这样遍历        *    一遍数组, 就能得到整个字符串的最大不同子串        * */        Deque queue = new LinkedList<>();    // 队列        int index = 0;                                  // 下标位置        char[] chs = s.toCharArray();                   // 字符串转化为字符数组方便操作        int N = chs.length;        int ans = 0;                                    // 返回的答案, 存放最长的子串长度        while (index < N) {            while (index < N && (queue.isEmpty() || !queue.contains(chs[index]))) {                queue.add(chs[index++]);            // 队列为空或者当前元素不在队列里存在, 入队                ans = Math.max(ans, queue.size());  // 更新最大值            }            while (index < N && !queue.isEmpty() && queue.contains(chs[index])) {va                queue.pollFirst();                  // 当前元素在队列里存在, 队头元素不停出队,             }                                   // 直到与当前元素相同的元素出队后位置            if (index < N) {                queue.add(chs[index++]);                ans = Math.max(ans, queue.size());            }        }        return ans;    }}// 单调栈写法优化class Solution {    public int lengthOfLongestSubstring(String s) {        Deque que = new LinkedList<>();        int ans = 0;        for (int i = 0; i < s.length(); i++) {            while (!que.isEmpty() && que.contains(s.charAt(i)))                que.pollFirst();            que.add(s.charAt(i));            ans = Math.max(ans, que.size());        }        return ans;    }}
class Solution {    /**    思路: dp + map         用一张 map 表存储每个字符上一次出现的位置    当前位置向前推的距离 和 上一次位置能向前推出的距离 + 1,     小的那个就是当前位置的最长无重复字符串         */    public int lengthOfLongestSubstring(String s) {        if (s == null || s.length() == 0)            return 0;        char[] str = s.toCharArray();        // map 表记录 (char)i 字符上一次出现的位置        int[] map = new int[128];        // -1 表示都没出现过        for (int i = 0; i < 128; i++)            map[i] = -1;        // dp[i] 表示以 i 位置字符结尾的最长无重复子串        int[] dp = new int[str.length];        // 初始化操作        int ans = 1;        map[str[0]] = 0;        dp[0] = 1;        // 从 1 位置开始        for (int i = 1; i < str.length; i++) {            // 当前位置和上一个相同字符的距离            int cur = i - map[str[i]];            // i-1 位置字符结尾能推出的最长无重复子串是 dp[i-1],            dp[i] = Math.min(dp[i - 1] + 1, cur);            ans = Math.max(ans, dp[i]);            map[str[i]] = i;        }        return ans;    }}
// 空间压缩版本class Solution {    /**    思路: dp + map         用一张 map 表存储每个字符上一次出现的位置    当前位置向前推的距离 和 上一次位置能向前推出的距离 + 1,     小的那个就是当前位置的最长无重复字符串         */    public int lengthOfLongestSubstring(String s) {        if (s == null || s.length() == 0)            return 0;        char[] str = s.toCharArray();        // map 表记录 (char)i 字符上一次出现的位置        int[] map = new int[128];        // -1 表示都没出现过        for (int i = 0; i < 128; i++)            map[i] = -1;        // 初始化操作        int ans = 1;        map[str[0]] = 0;        int pre = 1;        // 从 1 位置开始        for (int i = 1; i < str.length; i++) {            // 当前位置和上一个相同字符的距离            int cur = i - map[str[i]];            // i-1 位置字符结尾能推出的最长无重复子串是 dp[i-1],            pre = cur = Math.min(pre + 1, cur);            ans = Math.max(ans, cur);            map[str[i]] = i;        }        return ans;    }}

关键词：