文章目录
242. Valid Anagram
Given two strings s and t , write a function to determine if t is an anagram of s.
Input: s = "anagram", t = "nagaram"
Output: true
Input: s = "rat", t = "car"
Output: false
解法
//长度不同直接返回，使用一个数组记录每一个字母出现的次数，如果最后为0,说明每个字符串出现相同字母的次数相同
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size())
return false;
int freq_s[26] = {};
for(int i=0;i<s.size();i++){
freq_s[ s[i] - 'a']++;
freq_s[ t[i] - 'a']--;
}
for(int i=0;i<26;i++){
if(freq_s[i]!=0)
return false;
}
return true;
}
};
49. Group Anagrams (字母异位词分组)
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
// 思路之一：用map<string,vector> 进行存储，因为键值的唯一性，所以可以将输入的字符进行sort,这样就可以保证，异位词被放在同一个键值对中，最后取出map中所有的value(vector)即可； 复杂度 排序 O(klogk) 插入map O(n) n*k*logk
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
if (strs.size()<1)
return res;
vector<string> buff = strs;
map<string,vector<string>> my_map;
string b;
for(int i=0;i<strs.size();i++){
sort(buff[i].begin(),buff[i].end());
// cout<<strs[i]<<endl;
my_map[buff[i]].push_back(strs[i]);
}
for(auto &v : my_map){
res.push_back(v.second);
}
return res;
}
};
11. 盛最多水的容器
给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。所以不需要判断长度
解题
暴力法，直接遍历所有的元素组合，(n-1)*n ）O(n^2)
双指针法：两线段之间形成的区域总是会受到其中较短那条长度的限制。此外，两线段距离越远，得到的面积就越大。
我们在由线段长度构成的数组中使用两个指针，一个放在开始，一个置于末尾。 此外，我们会使用变量 max 来持续存储到目前为止所获得的最大面积。 在每一步中，我们会找出指针所指向的两条线段形成的区域，更新 max，
并将指向较短线段的指针向较长线段那端移动一步
class Solution {
public:
int maxArea(vector<int>& height) {
int res=0;
int len = height.size();
// if (len<2)
// return res;
int l=0,r=len-1;
while(l<r){
int water = 0;
if (height[l] < height[r])
{
water = height[l]*(r-l);
l++;
}
else
{
water = height[r]*(r-l);
r--;
}
res = max(res,water);
}
return res;
}
};
3. 无重复字符的最长子串(滑动窗口)
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
解法1
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len = s.size();
int res = 0;
if (len<1)
return res;
int l=0,r=-1;
int freq[256]={0};
while(l<len && r+1<len){
if(freq[s[r+1]] == 0){
// 如果右边下一个元素在队列中不存在，则入队
freq[s[r+1]] ++;
r+=1;
}else{
// 如果存在，则需要将左边指针前移，移除已经存在的元素 abca abcb abcc 分别移除a/b/c
freq[s[l]] --;
l++;
}
// 统计队列最大值
res = max(res,r-l+1);
}
return res;
}
};
解法2
其实和上面的方法一样，只不过写法上更好理解
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len = s.size();
int l=0;
int res = 0;
int freq[256] ={0};
for(int i=0;i<len;i++){
while( freq[s[i]] != 0)
{ freq[s[l]] --;
l++;
}
freq[s[i]]++;
res = max(res,i-l+1);
}
return res;
}
};
209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
解题
滑动窗口
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
if (s<=0||nums.size()==0) return 0;
int i=0,j=0,sum=0,minL=INT_MAX;
for (;j<nums.size();j++)
{
sum+=nums[j];
while (sum>=s)
{
minL=min(minL,j-i+1);
sum-=nums[i++];
}
}
if (minL==INT_MAX) return 0;
return minL;
}
};
// class Solution {
// public:
// int minSubArrayLen(int s, vector<int>& nums) {
// int len = nums.size();
// int res=INT_MAX;
// int l=0,r=-1;
// int sum=0;
// while(r+1<len){
// sum+=nums[++r];
// while(sum>=s){
// res = min(res,r-l+1);
// sum-=nums[l++];
// }
// }
// if (res==INT_MAX) return 0;
// return res;
// }
// };
76. 最小覆盖子串
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
示例：
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：
如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。
解题
class Solution {
public:
string minWindow(string s, string t) {
vector<int> tmap(128, 0);
for (char c : t) {
++tmap[c];
}
string res = "";
int counts = 0, minwin = INT_MAX, left = 0;
for (int i=0; i<s.size(); ++i) {
--tmap[s[i]];
if (tmap[s[i]] >= 0) {
++counts;
}
while (counts == t.size()) {
if (minwin > i-left+1) {
minwin = i-left+1;
res = s.substr(left, minwin);
}
// 直到去掉T中的字符 如 DOBECODDEBA 中需要去掉 DOB
if (tmap[s[left]] >= 0) {
--counts;
}
++tmap[s[left]];
++left;
}
}
return res;
}
};
// 熟悉的写法
class Solution2{
public:
string minWindow(string s, string t) {
int len_s = s.size();
int len_t = t.size();
string res = "";
if (len_s<1 || len_t<1)
return res;
int min_size = INT_MAX;
vector<int> freq(128, 0);
int l=0,r=-1;
for(int i=0;i<len_t;i++)
freq[t[i]]++;
int count=0;
for(;r+1<len_s;){
freq[s[++r]]--;
if(freq[s[r]]>=0)
++count;
while(count == len_t){
if( (r-l+1) < min_size)
{
min_size = r-l+1;
res = s.substr(l, min_size);
}
if (freq[s[l]] >= 0) {
--count;
}
++freq[s[l]];
++l;
}
}
return res;
}
};
1004. 最大连续1的个数 III
给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
返回仅包含 1 的最长（连续）子数组的长度。
输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：
[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
解题
// O(n） 定义一个左右指针滑动窗口，找窗口中包含K个0的 窗口的最大宽度
class Solution {
public:
int longestOnes(vector<int>& A, int K) {
int len = A.size();
int l=0,r=-1;
int res = 0;
int count=0;
while(l<len && r+1<len){
if(A[++r]==0)
count+=1;
// 窗口中0大于K时，前移左指针，直到0的个数小于k
while(count > K){
if(A[l++]==0)
count-=1;
}
res = max(res,r-l+1);
}
return res;
}
};
424. 替换后的最长重复字符
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
输入:
s = "AABABBA", k = 1
输出:
4
解释:
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
解题
class Solution {
public:
int characterReplacement(string s, int k) {
int maxcnt=0,res=0; // maxCnt记录字符出现次数最多那个字符 的次数
int len= s.size();
int l=0,r=-1;
vector<int> freq(26,0);
while(l<len && r+1<len){
freq[ s[++r] - 'A']++;
maxcnt = max(maxcnt,freq[ s[r] - 'A']); // 更新窗口中 当前字符的数量 和 出现最多次数字符的数量
while(r-l+1-maxcnt>k){ //若当前窗口大小 减去 窗口中最多相同字符的个数 大于 k 时
// 既存在K个不同的字符时，即为当前窗口最大宽度
freq[ s[l++] - 'A'] --; // 左指针前移
}
res = max(res, r-l+1);
}
return res;
}
};
239. 滑动窗口最大值
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
解题
Runtime: 52 ms, faster than 95.75% of C++ Memory Usage: 13 MB, less than 86.89% of C++
// 首先找到第一个k区间的最大值，后面的nums[i]如果大于max,则直接添加， 如果小于前一个窗口最大值，且前一个窗口最大值还在当前窗口中，则继续添加上一个最大值 如果nums[i-k] == max_buff 既上一个窗口最大值已经不在当前窗口中，则需要重新更新当前窗口最大值，
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int len = nums.size();
vector<int> res;
if (k==0 || len<1)
return res;
int max_buff=INT_MIN;
for (int j=0;j<k;j++)
max_buff = max(nums[j],max_buff);
res.push_back(max_buff);
for(int i=k;i<len;i++){
if (nums[i]>max_buff)
max_buff = nums[i];
else if(nums[i-k] == max_buff){ // 最大值不再窗口中
max_buff=INT_MIN;
for (int j=i-k+1;j<i+1;j++)
max_buff = max(nums[j],max_buff);
}
res.push_back(max_buff);
}
return res;
}
};
其它滑动窗口的题
-
无重复字符的最长子串
-
串联所有单词的子串
-
最小覆盖子串
-
至多包含两个不同字符的最长子串
-
长度最小的子数组
-
滑动窗口最大值
-
字符串的排列
-
最小区间
-
最小窗口子序列
455. 分发饼干
/* 执行用时 : 36 ms, 在所有 C++ 提交中击败了99.42%的用户 内存消耗 :10.3 MB, 在所有 C++ 提交中击败了49.83%的用户 分别排序，然后为需求量最小的人找他适合的最小饼干，找到后，再为第二小需求的人找饼干，直到用完饼干 */
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
if(g.size()==0 || s.size()==0) return 0;
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int res=0;
for(int i=0,j=0;i<s.size()&&j<g.size();i++){
if(s[i]>=g[j]){
res+=1;
j+=1;
}
}
return res;
}
};
482. 密钥格式化
// 首先确定字符串除了‘-’外的长度
// 然后重组字符串，每num个字符加一个‘-’
class Solution {
public:
string licenseKeyFormatting(string S, int K) {
int num = K- (S.size() - count(S.begin(), S.end(), '-')) % K;
string rst = "";
for (auto c : S)
{
if (c == '-') continue;
if (num == 0 && rst != "") rst += '-';
rst += toupper(c);
num = (num + 1) % K;
}
return rst;
}
};
453. 最小移动次数使数组元素相等
给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动可以使 n - 1 个元素增加 1。
输入: [1,2,3]
输出: 3
解释:
只需要3次移动（注意每次移动会增加两个元素的值）：
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
// 给n-1个元素+1，相当于另一个元素-1，直接计算所有元素和最小值的差值和即可
class Solution {
public:
int minMoves(vector<int>& nums) {
int res=0;
int len = nums.size();
int min_s = nums[0];
for(int i=0;i<len;i++){
min_s = min(min_s,nums[i]);
}
for(int i=0;i<len;i++){
res += nums[i]-min_s;
}
return res;
}
};
京公网安备 11010502036488号