无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"输出: 3解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
解法
首先是子串，所以连续的。一个滑动窗口，窗口内的都是没有重复的字符，我们需要尽可能的扩大窗口的大小。由于窗口在不停向右滑动，窗口的右边界就相当于遍历到的字符的位置。 为了求出窗口的大小，我们需要一个变量 left 来指向滑动窗口左边界，一个变量记录窗口的右边界如果该字符没有出现过就右边界增加，否则就移动左边界直到重复的字符去掉。 为了判断字符是否出现过把出现过的字符都放入 set 中，遇到 set 中没有的字符就加入 set 中并更新结果 res，如果遇到重复的，则从左边开始删字符，直到删到重复的字符停止。
AC代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
set<char>ss;
int ans=0;
int l=0,r=0;
while(r<s.size())
{
if(!ss.count(s[r]))
{
ss.insert(s[r++]);
ans=max(ans,(int)ss.size());
}
else
ss.erase(s[l++]);
}
return ans;
}
};
至多k个无重复字符的最长子串
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
using namespace std;
typedef long long LL;
const int maxn=110;
const int MOD=1e9+7;
int k;
string s;
int main(){
cin>>k;
cin>>s;
int ans=0;
int l=0,r=0;
map<char,int>m;
for(int i=0;i<s.length();i++){
m[s[i]]++;
r=i;
while(m.size()>k){
m[s[l]]--;
if(m[s[l]]==0)
m.erase(m.find(s[l]));
l++;
}
ans=max(ans,r-l+1);
}
cout<<ans<<endl;
return 0;
}
至少有K个重复字符的最长子串
找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。
输入:
s = "ababbc", k = 2
输出:
5
最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
解法
使用两个指针 left、right 和小写字母计数器统计字符段中各个字符出现的次数，然后调整当前的 left、right 指针。再遍历一遍修正后的字符段，如果中间有出现次数小于 k 的字符，那么将修正后的字符段拆开为 [left, index - 1] 和 [index + 1, right] 两个字符段重新寻找。
AC代码
class Solution {
public:
int longestSubstring(string s, int k) {
return myHelper(s, k, 0, s.size() - 1);//left == 0, right = s.size() - 1
}
//寻找s串中[left, right]字符段中至少有K个重复数字的最长子串
int myHelper(string &s, int k, int left, int right) {
if (left > right) {//特殊情况
return 0;
}
vector<int> chCnt(26, 0);//字母计数器
//统计s串中[left, right]各个字符出现的次数
for (int index = left; index <= right; ++index) {
chCnt[s[index] - 'a'] += 1;
}
int maxRes = INT_MIN;//保存结果
//修正left指针
while (left <= right && chCnt[s[left] - 'a'] < k) {
chCnt[s[left] - 'a'] -= 1;
left += 1;
}
//修正right指针
while (left <= right && chCnt[s[right] - 'a'] < k) {
chCnt[s[right] - 'a'] -= 1;
right -= 1;
}
//在修正后的区域[left, right]中寻找，看是否有出现次数少于k的字符
for (int index = left + 1; index < right; ++index) {
if (chCnt[s[index] - 'a'] < k) {//如果出现了
//将[left, right]拆开为两个区间[left, index - 1], [index + 1, right]
maxRes = max(myHelper(s, k, left, index - 1), myHelper(s, k, index + 1, right));
}
}
//如果之前没有拆开区间，说明，[left, right]就是当前段的结果
if (maxRes == INT_MIN) {
maxRes = right - left + 1;
}
return maxRes;
}
};
最长公共前缀
最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
解法
AC代码
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string ans;
if(strs.empty())
return ans;
for(int i=0;i<strs[0].size();i++)
{
char c=strs[0][i];
for(int j=1;j<strs.size();j++)
{
if(i>=strs[j].size() || strs[j][i]!=c)
return ans;
}
ans+=c;
}
return ans;
}
};
字符串的排列
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
说明：
- 输入的字符串只包含小写字母
-
解法
开始想跑 dfs 跑全排列，然后用 KMP 去匹配，但是后来想了一下，不用那么复杂，因为全是小写字母，所以只需要 s2 和 s1 这段字符串的字符数量一样就可以了，因为 s1 的子串可以重新组合，必然能和 s2 匹配成功。
AC代码
class Solution { public: bool check(int a[]) { for(int i=0;i<26;i++) { if(a[i]!=0) return false; } return true; } bool checkInclusion(string s1, string s2) { int len1=s1.length();int len2=s2.length(); if(len1>len2 || len1==0 || len2==0) { return false; } else { int a[26]={0}; for(int i=0;i<len1;i++) { a[s1[i]-'a']--; a[s2[i]-'a']++; } for(int j=len1;j<len2;j++) { if(check(a)) { return true; } a[s2[j-len1]-'a']--; a[s2[j]-'a']++; } return check(a); } } };字符串相乘
给定两个以字符串形式表示的非负整数
num1和num2，返回num1和num2的乘积，它们的乘积也表示为字符串形式。
示例 1:输入: num1 = "2", num2 = "3" 输出: "6"说明：
num1 和 num2 的长度小于110。
- num1 和 num2 只包含数字 0 - 9。
- num1 和 num2 均不以零开头，除非是数字 0 本身。
- 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
解法
模拟数字乘法。参照这个图理解一下代码就可以
AC代码
class Solution { public: string multiply(string num1, string num2) { if(num1=="0" || num2=="0") return "0"; int len1=num1.length();int len2=num2.length(); int a[len1+len2]; memset(a,0,sizeof(a)); int flag=0;int t=len1+len2-2; for(int i=0;i<len1;i++) for(int j=0;j<len2;j++) a[t-i-j]+=((num1[i]-'0')*(num2[j]-'0')); for(int i=0;i<len1+len2;i++) { a[i]+=flag; flag=a[i]/10; a[i]%=10; } int i=len1+len2-1; while(a[i]==0) i--; string ans; if(i<0) return "0"; while(i>=0) ans+=(a[i--]+'0'); return ans; } };翻转字符串里的单词
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1
示例 2：输入: "the sky is blue" 输出: "blue is sky the"
示例 3：输入: " hello world! " 输出: "world! hello" 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。输入: "a good example" 输出: "example good a" 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。解法
遍历这个字符串，按照题意我们采用 stack 来存储这些字符串然后输出即可。AC代码
class Solution { public: string reverseWords(string s) { stack<string> str; string s0 = ""; if(s.empty()) { s = ""; return s; } for(int i=0;i<s.length();i++) { if(s[i]!=' ') { s0+=s[i]; continue; } //得到字符组成字符串。 else if(!s0.empty()) { str.push(s0); s0=""; } } if(!s0.empty()) { str.push(s0); s0=""; } while(!str.empty()) { s0+=str.top(); str.pop(); s0+=" "; } if(s0.empty()) { s = ""; return s; } s0.erase(s0.end()-1); s = s0; return s; } };简化路径
以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径
请注意，返回的规范路径必须始终以斜杠/开头，并且两个目录名之间必须只有一个斜杠/。最后一个目录名（如果存在）不能以/结尾。此外，规范路径必须是表示绝对路径的最短字符串。
示例 1：
示例 2：输入："/home/" 输出："/home" 解释：注意，最后一个目录名后面没有斜杠。
示例 3：输入："/../" 输出："/" 解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
示例 4：输入："/home//foo/" 输出："/home/foo" 解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
示例 5：输入："/a/./b/../../c/" 输出："/c"输入："/a/../../b/../c//.//" 输出："/c"解法
模拟题，注意细节。AC代码
class Solution { public: string simplifyPath(string path) { vector<string> v; int i = 0; while (i < path.size()) { while (path[i] == '/' && i < path.size()) ++i; if (i == path.size()) break; int start = i; while (path[i] != '/' && i < path.size()) ++i; int end = i - 1; string s = path.substr(start, end - start + 1); if (s == "..") { if (!v.empty()) v.pop_back(); } else if (s != ".") { v.push_back(s); } } if (v.empty()) return "/"; string res; for (int i = 0; i < v.size(); ++i) { res += '/' + v[i]; } return res; } };复原IP地址
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例：输入: "25525511135" 输出: ["255.255.11.135", "255.255.111.35"]解法
分为四个数字，每个数字最多三位。
遍历出所有的情况可能，看是否满足需求。AC代码
public class Solution { public List<String> restoreIpAddresses(String s) { List<String> res = new ArrayList<String>(); for (int a = 1; a < 4; ++a) for (int b = 1; b < 4; ++b) for (int c = 1; c < 4; ++c) for (int d = 1; d < 4; ++d) if (a + b + c + d == s.length()) { int A = Integer.parseInt(s.substring(0, a)); int B = Integer.parseInt(s.substring(a, a + b)); int C = Integer.parseInt(s.substring(a + b, a + b + c)); int D = Integer.parseInt(s.substring(a + b + c)); if (A <= 255 && B <= 255 && C <= 255 && D <= 255) { String t = String.valueOf(A) + "." + String.valueOf(B) + "." + String.valueOf(C) + "." + String.valueOf(D); if (t.length() == s.length() + 3) res.add(t); } } return res; } }
若有收获，就点个赞吧
0 人点赞
