CodeFightsでのプログラミング演習２週目です。
解いた問題：Intro 9 ~ 21
std::vector []operator と push_back() -おまけにRange-based For loop
受け取ったstring vectorから最も長いstringだけを集めて返す。
コメントアウトした方でなぜ正しいアウトプットが出てこなかったのかわからない…。
＊std::vectorは動的配列なので、存在しない要素にアクセスはできないとのコメントを頂きました。コメントありがとうございます！(2018.03.12 追記)
std::vector<std::string> allLongestStrings(std::vector<std::string> inputArray) {
std::vector<std::string> longestArray{inputArray[0]};
for(int i = 1; i < inputArray.size(); i++){
if(longestArray[0].length() < inputArray[i].length()){
longestArray.clear();
longestArray.push_back(inputArray[i]);
//Why
//longestArray[0] = inputArray[i];
//did not produce expected result although it wasnt compile error?
}
else if (longestArray[0].length() == inputArray[i].length())
longestArray.push_back(inputArray[i]);
}
return longestArray;
}
こちらは他の方の解答。短い！少しずつこういうコードかけるようになりたい。
std::vector<std::string> r, allLongestStrings(std::vector<std::string> a) {
int b=0;
for (s:a) if (s.size()>b) b=s.size();
for (s:a) if (s.size()==b) r.push_back(s);
return r;
}
ちなみにこのfor loop、やってることはわかるけど馴染みがないので詳細を貼っておく。ここにも全く同じ文法のfor loopは載ってないけど。
もう一つ使用例を別の問題の他の方の解答より。
std::vector<int> t, sortByHeight(std::vector<int> a) {
for (x:a) if (x>-1) t.push_back(x);
sort(begin(t), end(t));
auto p = begin(t);
for (x:a) if (x>-1) x = *(p++);
return a;
}
std::sort()
string内の文字を並び替えてくれる。#include <algorithm>
std::sort(str.begin(), str.end()) //例
std::accumulate
範囲を集計する関数。概要
次は他の方の解答。偶数桁数の正数を渡され、前半の各桁の数字の和が後半の各桁の数字の和に等しければtrueを返す。
bool isLucky(int n) {
std::string s = std::to_string(n);
auto half = s.begin() + s.size() / 2;
return std::accumulate(s.begin(), half, 0) == std::accumulate(half, s.end(), 0);
}
std::reverse, string::find, string::erase
次は他の方の解答より。与えられたstringにおいて()で囲まれた文字の順番をひっくり返し、()を取り除いた上で返す問題。()は内側にあるものから順に処理する。
auto reverseParentheses(auto s) {
for(int f, l; (f = s.rfind(40, l = s.find(41))) > 0;
reverse( & s[f], & s[l] ),
s.erase( l-1, 2 )
);
return s;
}
- for loopこんな風にも使えるのか。セミコロンが最後に追加されていることに注意。
- あとで取り除く()を、文字の順番をひっくり返すときにひとまとめにする発想はなかった。
- ()を見つけるのにASCII Code使ってる。それぞれ４０、４１。
- findとrfindの使い方も重要で、()が囲み囲まれずに複数存在しても大丈夫なようになってる。
std::reverse
template <class BidirectionalIterator>
void reverse (BidirectionalIterator first, BidirectionalIterator last);
Reverses the order of the elements in the range [first,last). BidirectionalIterator shall point to a type for which swap is properly defined.
ここで注意、順番がひっくり返るのはlast-1までで、lastの位置にある要素はそのまま！！
string::find
Searches the string for the first occurrence of the sequence specified by its arguments.
When pos is specified, the search only includes characters at or after position pos, ignoring any possible occurrences that include characters before pos.
If no matches were found, the function returns string::npos. (string::npos is defined with a value of -1.)
string::rfind
Searches the string for the last occurrence of the sequence specified by its arguments.
When pos is specified, the search only includes sequences of characters that begin at or before position pos, ignoring any possible match beginning after pos.
If no matches were found, the function returns string::npos.
string::erase
stringのなかで特定の文字や文字列を消して、その上stringの長さまで消した分短くしてくれる。
string& erase(size_t pos = 0, size_t len = npos); //sequence
iterator erase(const_iterator p); //character
iterator erase (const_iterator first, const_iterator last); //range [first,last)
三つ目のrangeはlastの位置にある文字を削除対象に含まないので要注意！
std::mismatch
template< class InputIt1, class InputIt2 >
std::pair<InputIt1,InputIt2>
mismatch( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2 );
Returns the first mismatching pair of elements from two ranges: one defined by [first1, last1) and another defined by [first2,last2). If last2 is not provided (overloads (1-4)), it denotes first2 + (last1 - first1).
他にも何種類も文法があったけど複雑すぎたので割愛。次は他の方の解答より使い方の例。与えられた二つの配列が、最大１回のswapで同じになるならtrueを返す。
bool areSimilar(std::vector<int> a, std::vector<int> b) {
if (a == b)
return true;
std::iter_swap(
std::mismatch(a.begin(), a.end(), b.begin(), b.end()).first,
std::mismatch(a.rbegin(), a.rend(), b.rbegin(), b.rend()).first
);
return a == b;
}
std::iter_swap
template< class ForwardIt1, class ForwardIt2 >
void iter_swap( ForwardIt1 a, ForwardIt2 b );
Swaps the values of the elements the given iterators are pointing to.
ビットAND &
いくつかあるビット演算子の一つ。その他も含めた参照はこちら
ビットANDは演算子の左辺と右辺の同じ位置にあるビットを比較して、両方のビットが共に「1」の場合だけ「1」にします。
0000000000001011 = 11
0000000000001110 = 14
ーーーーーーーーーーーーー
0000000000001010 = 10
下は与えられたstringが並べ替えて回文になりうるか調べる問題を他の方の解答を参考にして解いたもの。どうやって奇数個あるアルファベットの数を調べるかで悩んでいたのだけどこんな簡単な見つけ方があるなんて。
bool palindromeRearranging(std::string s) {
int a[26] = {0};
for(char c : s) ++a[c - 'a'];
int n = 0;
for(int i : a) n += i & 1;
return n < 2;
}
次は最初の自分の解答。隠されたテストで正しいアウトプットが出なかったみたいなんだけど何がいけなかったのかわからなかった。
bool palindromeRearranging(std::string s) {
std::sort(s.begin(), s.end());
if(s.size() % 2 == 0) {
for (int i = 0; i < s.size(); i += 2)
if(s[i] != s[i + 1]) return false;
return true;
}
else {
int c = 1;
for (int i = 0; i < s.size() - 1; i += 2) {
if(s[i] != s[i + 1]) c--, i--;
return c >= 0;
}
}
}
std::abs
渡したintの絶対値を返す。
abs(3) = abs(-3) = 3
渡す値がlong int や long long intなどの場合にはlabsやllabsなどを使う。
区切り文字によるstringの分割
問題原文
IPv4 addresses are represented in dot-decimal notation, which consists of four decimal numbers, each ranging from 0 to 255 inclusive, separated by dots, e.g., 172.16.254.1.
Given a string, find out if it satisfies the IPv4 address naming rules.
自分の解答
bool isIPv4Address(std::string is) {
char d = '.'; //区切り文字
std::stringstream ss(is); //getlineを使うために必要
//std::stringstream ss(is + ".");
//最後の数字は.を伴わないので付け足したほうがいいかと思ったらそんなことはなかった。なぜだ。
std::string b; //こいつがgetlineで区切られたstringを受け取るぞ。
int n; //bをintに変換したとき用に。
int c = 0; //数字は全部で4つないとダメなのでそれを数える。
while (std::getline(ss, b, d)){ //getlineが返すのはb
if (b == "") return false; //bが空っぽはNG.
for(char e : b) if (!std::isdigit(e)) return false; //全部数字じゃないとNG
try{n = std::stoi(b);} //全部数字でもintで扱える大きさを越えるとerror吐くのでその対処
catch (...) {return false;}
if (n < 0 || 255 < n) return false; //数字がIPV4の条件を満たしているか。
c++;
}
if(c != 4) return false;
return true;
}
参考にしたサイト
C++で文字列が数字かチェックする
C++ 区切り文字／文字列による文字列の分割（split）std::string／文字列ポインタ
他の方の解答
bool isIPv4Address(std::string s) {
regex r("[0-9]{1,3}(.[0-9]{1,3}){3}");
if(!regex_match(s,r))return false;
int a,b,c,d;
sscanf(s.c_str(),"%d.%d.%d.%d", &a,&b,&c,&d);
return a<256 && b<256 && c<256 && d<256;
}
regexって何!?
一旦保留。
あとがき
今週はArcadeモードのIntroより13問解きました。そろそろ色んなメソッドやら何やらが出てきてノートがごっちゃになってきたので、より体系的なまとめ方を必要に感じてきました。新しく出てきたメソッドや型をどこかでまとめて練習できたら最高なのですが…
予定に関して。DatabasesとPythonは知らないことが多すぎるので夏以降に持ち越し。それに伴い予定に少し余裕ができたので、今月中にArcadeモードから１００問終わらせる気でいたのをIntroの６０問だけに。それでも学ぶことは沢山あるので気を抜かず頑張ります。