LeetCode Various 3

T3. 无重复字符的最长字串

题目描述:

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

 

思路:

当作队列处理,每次加入相同字符时,需从头开始出对,每次处理最大长度即为最后结果。

 

代码:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
    int ans = 0;
    vector<char> res;
    for(int i = 0; i < s.size(); i++){
        while(count(res.begin(), res.end(), s[i])){
            res.erase(res.begin());
        }
        res.push_back(s[i]);
        int length = res.size();
        ans = max(ans, length);
    }
    return ans;
}
};

 

推荐这些文章:

LeetCode(39)

class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
vector<vector<int>>v,result;
vector<int>v2;
map<vector<int>,int>mp;
...

LeetCode第 277 场周赛

A
class Solution {
public:
int countElements(vector<int>& nums) {
int minn = 0x3f3f3f3f, maxx = 0xcfcfcfcf;
for (auto x : nums)
minn = min(minn, x), maxx = max(maxx, x);
int cnt = 0;
for (auto x : nums)
if (x > minn &&...

[LeetCode 32] 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。

没睡醒的脑回路:转换成 +1,-1 序列,利用两个充要条件(子段和为 0,子段任意前缀的和非负),在前缀和序列上用二分找满足条件的最远点
class Solution {
public:
int longestValidParentheses(string s) {
// 对前缀和序列 a,假设 s[i]='('
// 令 j 为 i 右侧 a[i]-2 首次出现位置(不存在则为 n)
// 则任意 i<k<j 满足 a[k]=a...

LeetCode 3. 无重复字符的最长子串

3. 无重复字符的最长子串
Solution
思路:刚开始考虑是map记录下标,然后重复的话就看map的下标位置,得到极大子串的长度,但是没有考虑到这个过程中是可以维护出不重复的字串的,通过几个样例模拟,然后就以为map只是一开始用到了,后面都是靠的下标去得到子串长度,不删除的话还不好维护,没往删除上面考虑,然后感觉意义不大。看了题解,MD很接近了。从左开始枚举起点,整个过程中子串右端点不断递增,通过不断左移以及右移即可维护。
class Solution {
public int lengthOfLongestSubstring(String s) {
int le...

LeetCode 每日一题(5. 最长回文子串)

 

class Solution {
public:
string longestPalindrome(string s) {
if (s.size() <= 1){
return s;
}

int a = 0; //记录临时值
int length = 0;

int ta = 1; //滑动窗口边界
int tb = 0;

int t = 0;

bool flag = false; //匹配标记

...

LeetCode 424. 替换后的最长重复字符

424. 替换后的最长重复字符
解题思路:
采用双指针(尺取)法。首先用一个数组cnt记录区间[l,r]内每个字符出现的次数。该区间所有字符出现的次数sum = r - l + 1,我们找出这个区间字符出现的最大次数max_cnt,那么sum - max_cnt就是这个区间内我们可以替换字符的最小次数,如果sum - max_cnt <= k说明该区间满足条件,我们更新区间长度的最大值。如果sum - max_cnt > k 说明不满足条件,我们通过移动指针l来找到满足条件的区间。
代码:
class Solution {
public:
int characterRe...

LeetCode 每日一题 (3 无重复字符的最长子串)

 

class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (s.size() == 0){
return 0;
}

int ret = 0;
int tlength = 1;

bool flag = false; //匹配标记
int b = 0; // 边界标记

const char* p = s.c_str();
for(...

LeetCode No1 无重复字符的最长子串

题目
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
  请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串...

LeetCode第 71 场双周赛题解

题目链接白天补

题目描述:给你一个四位整数,让你重排这个整数中的数字然后分成两部分,允许有前导\(0\)。问分成的两部分的十进制表示的和的最小值。
思路:根据题意模拟即可、
时间复杂度:\(O(1)\)
参考代码:
class Solution {
public:
int minimumSum(int num) {
string s = to_string(num);
vector<int>cnt(10 , 0);
for(auto c : s) cnt[c - '0'] ++;
int res = 0, ...

【LeetCode】159.至多包含两个不同字符的最长子串

159.至多包含两个不同字符的最长子串

知识点:字符串;滑动窗口

题目描述
给定一个字符串 s ,找出 至多 包含两个不同字符的最长子串 t 。
注意:
对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。
示例
示例 1:
输入: "eceba"
输出: 3
解释: t 是 "ece",长度为3。

示例 2:
输入: "ccaabbb"
输出: 5
解释: t 是 "aabbb",长度为5。

解法一:滑动窗口
这其实也是滑动窗口的一道典型题目
刚看题目,最长子串,其实应该自然的想到滑动窗口。 ...

文章标题:LeetCode Various 3
文章链接:https://www.dianjilingqu.com/51422.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>