541. Reverse String II
どうにかreverseを使えないかと思ったが自力では考えつかなかった。
https://leetcode.com/problems/reverse-string-ii/discuss/1354754/C%2B%2B-oror-Easy-Solution-oror-91
場合分け
class Solution { public: string reverseStr(string s, int k) { int n = s.size(); int i = 0; string temp =""; while(i < n) { if(n-i >= 2*k)// string sizeが2k以上なら { for(int j=k-1;j>=0;j--){ temp += s[i+j]; } for(int j = k;j<2*k;j++){ temp += s[i+j]; } i += 2*k; } else// string sizeが2k未満なら if(n -i >= k) // string sizeがk以上なら { for(int j=k-1;j>=0;j--){ temp += s[i+j]; } for(int j=i+k;j<n;j++){ temp += s[j]; } break; } else //string sizeがk未満なら { for(int j =n-1;j>=i;j--){ temp += s[j]; } break; } } return temp; } };
reverse
class Solution { public: string reverseStr(string s, int k) { for(int i = 0; i < s.length(); i += (2*k)) { if (i + k < s.length()) { reverse(s.begin()+i, s.begin()+i+k); } else { reverse(s.begin()+i, s.end()); } } return s; } };
1297. Maximum Number of Occurrences of a Substring
シンプルではあるが難しい
class Solution { public: int maxFreq(string s, int maxLetters, int minSize, int maxSize) { unordered_map<char, int> m; //文字種類数 unordered_map<string, int> subs; int j=0; for(int i= 0; i< s.size(); i++){ m[s[i]]++; //現在のsubstringのサイズ int currSize = i-j+1; while(m.size() > maxLetters || currSize > minSize) { int start = j; m[s[j]]--; if(m[s[j]] == 0){ m.erase(s[j]); } j++; currSize--; } //現在のsubstringのサイズがminSize以上なら候補として保存 if(currSize >= minSize) { subs[ s.substr(j, currSize) ]++; } } int maxc = 0; for(auto it = subs.begin(); it != subs.end(); it++) { maxc = max( maxc, it->second); } return maxc; } };
3. Longest Substring Without Repeating Characters
下記を見てsetを使う方法とsliding windowを使う方法を学んだ。
set
class Solution { public: int lengthOfLongestSubstring(string s) { int n=s.length(); if(n==0){ return 0; } set<char> st; int maxSize=0; int i=0; int j=0; while(j < n) { //stに今の文字がなければ、今までの最大値と今のsetのサイズを比較 if(st.count(s[j])==0){ st.insert(s[j]); maxSize = max(maxSize, (int)st.size()); j++; } else{ st.erase(s[i]); i++; } } return maxSize; } };
sliding window
256は1byteだから256文字文ってことのようだ。文字そのものではなく、asciiの数値で扱う発想はなかった。
class Solution { public: int lengthOfLongestSubstring(string s) { vector<int> vec(256, -1); int maxSize=0; int i=0; int j=0; int n=s.size(); while(j<n){ //文字をasciiの数値として扱っている。 if(vec[s[j]] != -1) { i = max(vec[s[j]]+1, i); } vec[s[j]] = j; maxSize = max(maxSize, j-i+1); j++; } return maxSize; } };
1047. Remove All Adjacent Duplicates In String
stackで貯めていき、stackのtopと同じ文字がきたら、popする。
'''cpp
class Solution {
public:
string removeDuplicates(string s) {
stack
for(char i:s)
{
if(st.size() == 0)
{
st.push(i);
}
else if(i == st.top())
{
st.pop();
}
else
{
st.push(i);
}
}
string ans;
while(st.size() != 0)
{
ans += st.top();
st.pop();
}
reverse(ans.begin(),ans.end());
return ans;
}
}; '''
796. Rotate String
substrで切り取って、一文字目を足せば良いのか
class Solution { public: bool rotateString(string s, string goal) { int len = goal.size(); while(len--) { if(s == goal) { return true; } s = s.substr(1) + s[0]; } return false; } };
567. Permutation in String
Sliding Windowを用いた方法
s1をソート
sliding window法を用いて、s1の長さ分だけs2の文字をソートしていく
https://leetcode.com/problems/permutation-in-string/discuss/1385457/Very-Easy-C%2B%2B-Solution
class Solution { public: bool checkInclusion(string s1, string s2) { if(s1.length() > s2.length() ){ return false; } sort(s1.begin(), s1.end()); for(int i= 0; i<s2.length()-s1.length()+1; i++){ string tmp = s2.substr(i, s1.length()); sort(tmp.begin(),tmp.end()); if(s1 == tmp){ return true; } } return false; } };
s1の各文字の個数を算出
sliding window法を持ちいて、s2の各文字の個数を算出し同じならtrue
1.cur[s2[i - s1.size()] - 'a']--;の意味 s2ではs1の文字数だけを見たいので、3 Input: s1 = "ab", s2 = "eidbaooo"ならば、idのところに来たらeを消す
class Solution { public: bool checkInclusion(string s1, string s2) { vector<int> cur(26), goal(26); for(char c : s1){ goal[c - 'a']++; } for(int i = 0; i < s2.size(); i++) { cur[s2[i] - 'a']++; if(i >= s1.size()) { cur[s2[i - s1.size()] - 'a']--; } if(goal == cur){ return true; } } return false; } };
242. Valid Anagram
sortを使う方法
'''cpp class Solution { public: bool isAnagram(string s, string t) {
sort(s.begin(), s.end());
sort(t.begin(), t.end());
if(s ==t){
return true;
}
else{
return false;
}
}
};
unordered_mapに入れてから比較
class Solution { public: bool isAnagram(string s, string t) { if(s.length()!=t.length()) { return false; }
unordered_map<char, int> ss, tt;
for(auto it : s){
ss[it]++;
}
for(auto x:t)
{
tt[x]++;
}
for(auto& [key, value]: ss)
{
if(tt[key] != value){
return false;
}
}
return true;
}
};
