力扣(LeetCode)3

_DangJin 发布于2019-08-16 15:43 / 3054人阅读

摘要：示例输入输出解释因为无重复字符的最长子串是，所以其长度为。请注意，你的答案必须是子串的长度，是一个子序列，不是子串。若没有重复元素，则区间右边扩大，否则区间左边缩小。

题目地址：
https://leetcode-cn.com/probl...
题目描述：
给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

解答：
利用双指针法，双指针维护了一个滑动的区间，在用一个哈希表记录这个区间里的字符及其个数，对一个区间
进行检查，每一次这个区间没有重复元素就跟结果比较大小来选择是否更新结果。若没有重复元素，则区间右边
扩大，否则区间左边缩小。直至到达边界。(需要注意的是，这里的字符不仅仅是"A"到"z"，因此hash数组需要开的大一些，来容纳那些ASCII码大的字符。)

java ac代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() == 0)return 0;
        int ans = 1;
        int[]hash = new int[200];
        hash[s.charAt(0)] = 1;
        for(int i = 0,j = 0;i <= j && j < s.length();)
        {
            boolean flag = false;
            for(int k = 0 ;k < hash.length ;k++)
                if(hash[k] > 1){flag = true;break;}
            if(!flag)
            {
                ans = Math.max(ans,j-i+1);
                j++;
                if(j < s.length())
                hash[s.charAt(j)]++;
                else break;
            }
            else
            {
                hash[s.charAt(i)]--;
                i++;
            }
            
        }
        return ans;
        
    }
}

云服务器 GPU云服务器力扣 LeetCode LeetCode_String leetcode_35_SearchIn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73664.html

力扣(LeetCode)310

摘要：图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。因此使用一个数组代表每个节点的入度，若入度为就是叶子节点。题目地址：https://leetcode-cn.com/probl...题目描述：对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小...

amuqiao 2019-08-16 16:13 评论0 收藏0
＜LeetCode天梯＞Day026 反转链表（递归法+（迭代法）双链表法） | 初级算法 | Py

摘要：关于递归这里提一两点递归基本有这几步递归的模板，终止条件，递归调用，逻辑处理。 ?作者简介：大家好，我是车神哥，府学路18号的车神? ?个人主页：应无所住而生...

imingyu 2021-11-17 09:33 评论0 收藏0
力扣(LeetCode)46

摘要：题目地址题目描述给定一个没有重复数字的序列，返回其所有可能的全排列。题目地址：https://leetcode-cn.com/probl...题目描述：给定一个没有重复数字的序列，返回其所有可能的全排列。示例: 输入: [1,2,3]输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]解答：利用递归，我们可...

李增田 2019-08-16 15:13 评论0 收藏0
＜LeetCode天梯＞Day031 验证二叉搜索树（递归+中序遍历） | 初级算法 | Pytho

摘要：有效二叉搜索树定义如下节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。而我们二叉搜索树保证了左子树的节点的值均小于根节点的值，根节点的值均小于右子树的值，因此中序遍历以后得到的序列一定是升序序列。 ...

Genng 2021-11-24 09:39 评论0 收藏0