配列のコーディングに関する問題をC++で解いてみた
はじめに
ネットで見かけた問題が面白そうでとこうと思い、解き始めました。せっかく解いたので、問題の紹介も兼ねて記事にすることにしました。
全ての問題を解き終わってからまとめようと思ったのですが、時間がかかりそうだったので、見出しで一旦まとめることにしました。
問題
こちらにある50問のうち、大問１(配列のコーディングに関する質問)を解いた。リンク先は海外のページの和訳とのこと。
少し問題の解釈が曖昧なところはあるが、おおまかにはできた。
Q1.不足する数値を探す
与えられた配列をソートして、前から順に値を確認し、差が１でない（不足する数値は１つのようなので２である）場合、その数値が不足する数値である。
q1.cpp
#include <iostream>
#include <vector>
using namespace std;
#define debug(var) do{std::cout << #var << " : "; view(var);}while(0)
template<typename T> void view(const T e){ std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){ for(const auto& e : v) std::cout << e << " "; std::cout << std::endl; }
template<typename T> void view(const std::vector<std::vector<T>>& vv){ for(const auto& v : vv){ view(v); } }
vector<int> genVector(int size){
vector<int> v(size);
for(size_t i=0; i<size; ++i){
v[i] = i;
}
return v;
}
int main(int argc, char **argv) {
vector<string> args(argv, argv+argc);
auto v = genVector(100);
v.erase(v.begin()+50);
sort(v.begin(), v.end());
for(size_t i=1; i<v.size(); ++i){
if(v[i-1]!=v[i]-1){
cout << "Nothing number : " << v[i] << endl;
return i;
}
}
cout << "all number existing!" << endl;
return 0;
}
Q2.重複する数値を探す
Q1と近い方法で解決した。与えられた配列をソートして、前から順に値を確認し、前後が同値である場合、その数値が重複する数値である。
q2.cpp
#include <iostream>
#include <vector>
using namespace std;
template<typename T> void view(const T e){ std::cout << e << std::endl;}
template<typename T> void view(const vector<T>& v){ for(const auto& e : v) std::cout << e << " "; std::cout << std::endl; }
template<typename T> void view(const vector<vector<T>>& vv){ for(const auto& v : vv){ view(v); } }
vector<int> genVector(int size){
vector<int> v(size);
for(size_t i=0; i<size; ++i){
v[i] = i;
}
return v;
}
int main(int argc, char **argv) {
vector<string> args(argv, argv+argc);
auto v = genVector(100);
v.push_back(49);
sort(v.begin(), v.end());
for(size_t i=1; i<v.size(); ++i){
if(v[i-1]==v[i]){
cout << "Duplicate number : " << v[i] << endl;
return i;
}
}
cout << "Nothing duplicate number!" << endl;
return 0;
}
Q3.最大値と最小値を探す
配列を走査し、maximumとminimumを更新することで、最大値と最小値を得る。
q3.cpp
#include <iostream>
#include <vector>
#include <genVector.hpp>
#include <template.hpp>
using namespace std;
int main(int argc, char **argv) {
vector<string> args(argv, argv+argc);
auto v = genVectorByRandom(10);
debug(v);
int minNum = v[0];
int maxNum = v[0];
for(const auto& e : v){
minNum = min(minNum, e);
maxNum = max(maxNum, e);
}
cout << "max number : " << maxNum << endl;
cout << "min number : " << minNum << endl;
return 0;
}
template.hpp
#define debug(var) do{std::cout << #var << " : "; view(var);}while(0)
#ifndef _CPP_VECTOR
#include <vector>
#endif
#ifndef _CPP_MAP
#include <map>
#endif
template<typename T> using V = std::vector<T>;
template<typename T> using VV = std::vector<std::vector<T>>;
template<typename T> using VVV = std::vector<std::vector<std::vector<T>>>;
template<typename T> void view(const T e){ std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){ for(const auto& e : v) std::cout << e << " "; std::cout << std::endl; }
template<typename T> void view(const VV<T>& vv){ for(const auto& v : vv){ view(v); } }
template<typename T1, typename T2> void view(const std::pair<T1,T2> e){ std::cout << "(" << e.first << ", " << e.second << ")" << std::endl;}
template<typename T1, typename T2> void view(const std::vector<std::pair<T1,T2>>& v){ for(const auto& e : v) std::cout << "(" << e.first << ", " << e.second << ") "; std::cout << std::endl; }
template<typename T1, typename T2> void view(const std::map<T1,T2>& v){ for(const auto& e : v) std::cout << "(" << e.first << ", " << e.second << ") "; std::cout << std::endl; }
template<class Iterator> void view(const Iterator& begin, const Iterator& end){ for(auto itr=begin; itr!=end; itr++) std::cout << *itr << " "; std::cout << std::endl; }
genVector.hpp
#ifndef _CPP_VECTOR
#include <vector>
#endif
#ifndef _CPP_RANDOM
#include <random>
#endif
std::vector<int> genVectorByOrder(size_t size){
std::vector<int> v(size);
for(size_t i=0; i<size; ++i){
v[i] = i;
}
return v;
}
std::vector<int> genVectorByRandom(size_t size){
std::mt19937 mt{ std::random_device{}() };
std::uniform_int_distribution<int> rnd(0, 100);
std::vector<int> v(size);
for(size_t i=0; i<size; ++i){
v[i] = rnd(mt);
}
return v;
}
std::vector<int> genVectorByRandom(size_t size, int rndMax){
std::mt19937 mt{ std::random_device{}() };
std::uniform_int_distribution<int> rnd(0, rndMax);
std::vector<int> v(size);
for(size_t i=0; i<size; ++i){
v[i] = rnd(mt);
}
return v;
}
Q4.配列と数値が与えられ、配列のうち和がその数値となるペアを探す
配列をソートして、両端から探索することにした。ペアの和が与えられた数値givenNumber
- と等しい場合はその数値を解に追加
- より小さい場合はペアのうち大きい方を左へ移動
- より大きい場合はペアのうち小さい方を右へ移動
とした。
q4.cpp
#include <iostream>
#include <vector>
#include <genVector.hpp>
#include <template.hpp>
constexpr size_t arSize = 50;
constexpr long givenNumber = 50;
using namespace std;
int main(int argc, char **argv) {
vector<string> args(argv, argv+argc);
auto v = genVectorByRandom(arSize);
sort(v.begin(), v.end());
debug(v);
vector<pair<size_t,size_t>> pairs;
size_t lower = 0;
size_t upper = arSize-1;
bool upFlag = false;
bool downFlag = false;
while(lower!=upper){
long sumOfTwo = v[lower] + v[upper];
if(sumOfTwo==givenNumber){
pairs.emplace_back(v[lower], v[upper]);
if(v[lower+1]+v[upper] == givenNumber && !upFlag){
pairs.emplace_back(v[lower+1], v[upper]);
upFlag = true;
}else if(v[lower]+v[upper-1] == givenNumber && !downFlag){
pairs.emplace_back(v[lower], v[upper-1]);
downFlag = true;
}else{
upFlag = false;
downFlag = false;
lower++;
}
}else if(sumOfTwo<givenNumber){
lower++;
}else if(sumOfTwo>givenNumber){
upper--;
}
}
cout << "pattern of sum : " << pairs.size() << endl;
view(pairs);
return 0;
}
Q5.複数の重複がある配列から重複する数値を探索
Q2同様、ソートして下から走査していった。ここでは、複数の重複があるということで、一つ隣が同値であればその隣、さらに同値であればさらにその隣、、、と比較することにした。
q5.cpp
#include <iostream>
#include <vector>
#include <genVector.hpp>
#include <template.hpp>
constexpr size_t arSize = 50;
constexpr int rndMax = 100;
using namespace std;
int main(int argc, char **argv) {
vector<string> args(argv, argv+argc);
auto v = genVectorByRandom(arSize, rndMax);
sort(v.begin(), v.end());
view(v);
vector<int> duplicate;
size_t i, j;
for(i=0; i<v.size()-1; ++i){
for(j=i; v[i]==v[j]; ++j){}
if(v[i] == v[i+1]) duplicate.push_back(v[i]);
i = j - 1;
}
view(duplicate);
return 0;
}
Q6.配列から重複を削除
実際の問題ではJavaにおいてとあるが、C++でやることにした。
q6.cpp
#include <iostream>
#include <vector>
#include <genVector.hpp>
#include <template.hpp>
constexpr size_t arSize = 50;
constexpr int rndMax = 100;
using namespace std;
int main(int argc, char **argv) {
vector<string> args(argv, argv+argc);
auto v = genVectorByRandom(arSize, rndMax);
view(v);
auto vTemp = v;
sort(vTemp.begin(), vTemp.end());
map<int, int> duplicateMap;
size_t i, j;
for(i=0; i<vTemp.size()-1; ++i){
for(j=i; vTemp[i]==vTemp[j]; ++j){}
if(vTemp[i] == vTemp[i+1]) duplicateMap.emplace(vTemp[i], j-i);
i = j - 1;
}
for(auto& e : duplicateMap) e.second = e.second - 1;
for(i=v.size()-1; i<v.size(); --i){
auto itr = duplicateMap.find(v[i]);
if(itr!=duplicateMap.end()){
if(duplicateMap[v[i]]!=0){
duplicateMap[v[i]] = duplicateMap[v[i]]-1;
v.erase(v.begin()+i);
}
}
}
cout << "duplicate number was erased!" << endl;
view(v);
return 0;
}
Q7.クイックソートの実装
配列の要素で実装しても良いのだが、以前他の記事のコメントで、「イテレータを使うと勉強になるよ」という言葉をいただいたので、この問題は２パターンの関数を作成した。
q7.cpp
#include <iostream>
#include <vector>
#include <genVector.hpp>
#include <template.hpp>
using namespace std;
constexpr size_t arSize = 50;
constexpr int rndMax = 100;
template<typename T> void quickSort(std::vector<T>& v, const int left, const int right){
if(right - left < 1) return ;
auto central = v[(right-left)/2];
auto pivot = central;
if(v[left]<v[right]){
if(v[left]<central){
if(central<v[right]){
}else{
pivot = v[right];
}
}else{
pivot = v[left];
}
}else{
if(central<v[right]){
pivot = v[right];
}else{
if(v[left]<central){
pivot = v[left];
}else{
}
}
}
int i = left, j = right;
while(1){
while(v[i]<pivot) i++;
while(pivot<v[j]) j--;
if(i >= j) break;
swap(v[i],v[j]);
i++;
j--;
}
if(right - left < 2) return ;
quickSort(v, left, i-1);
quickSort(v, j+1, right);
}
template<class Iterator> void quickSort(const Iterator& begin, const Iterator& end){
if(end - begin < 2 ) return;
auto left = begin;
auto right = end-1;
auto central = left + distance(left, right)/2;
auto pivot = *central;
if(*left<*right){
if(*left<*central){
if(*central>*right){
pivot = *right;
}
}else{
pivot = *left;
}
}else{
if(*central<*right){
pivot = *right;
}else{
if(*left<*central){
pivot = *left;
}else{
}
}
}
auto i = left;
auto j = right;
while(1){
while(*i<pivot) i++;
while(pivot<*j) j--;
if(i >= j) break;
iter_swap(i,j);
i++;
j--;
}
if(end - begin <= 2) return ;
if(i-begin>1)quickSort(begin, i);
if(end-j>1)quickSort(j+1, end);
}
template<typename T> bool alignmentCheck(vector<T>& v){
bool alignment = true;
for(size_t i=1; i<v.size(); ++i){
if(v[i-1]>v[i]) alignment = false;
}
return alignment;
}
int main(int argc, char **argv) {
vector<string> args(argv, argv+argc);
auto v = genVectorByRandom(arSize, rndMax);
view(v);
cout << (alignmentCheck(v)? "OK" : "NG" ) << endl;
auto vTemp = v;
quickSort(vTemp, 0, vTemp.size()-1);
view(vTemp);
cout << (alignmentCheck(vTemp)? "OK" : "NG" ) << endl;
vTemp = v;
quickSort(vTemp.begin(), vTemp.end());
view(vTemp);
cout << (alignmentCheck(vTemp)? "OK" : "NG" ) << endl;
return 0;
}
Q8.配列から重複を削除
問題からのリンク先を見ると、削除とは値を0にすることのようなので、ここでもそれを行った。
q8.cpp
#include <iostream>
#include <vector>
#include <genVector.hpp>
#include <template.hpp>
using namespace std;
constexpr size_t arSize = 10;
constexpr int rndMax = 10;
template <typename T> void duplicateTo0 (vector<T>& v){
size_t i, j;
for(i=0; i<v.size(); ++i){
for(j=i+1; j<v.size() && v[i]==v[j]; ++j){
v[j] = 0;
}
i = j - 1;
}
}
int main(int argc, char **argv) {
vector<string> args(argv, argv+argc);
auto v = genVectorByRandom(arSize, rndMax);
view(v);
sort(v.begin(), v.end());
view(v);
duplicateTo0(v);
view(v);
return 0;
}
Q9.配列を反転
q9.cpp
#include <iostream>
#include <vector>
#include <genVector.hpp>
#include <template.hpp>
using namespace std;
constexpr size_t arSize = 10;
constexpr int rndMax = 10;
template <typename T> void reverse (vector<T>& v){
for(size_t i=0; i<v.size()/2; ++i){
swap(v[i], v[v.size()-1-i]);
}
}
int main(int argc, char **argv) {
vector<string> args(argv, argv+argc);
auto v = genVectorByRandom(arSize, rndMax);
view(v);
reverse(v);
view(v);
return 0;
}
Q10.ライブラリを使わないで配列から重複を削除
q9.cpp
#include <iostream>
#include <vector>
#include <genVector.hpp>
#include <template.hpp>
using namespace std;
constexpr size_t arSize = 10;
constexpr int rndMax = 10;
template <typename T> void reverse (vector<T>& v){
for(size_t i=0; i<v.size()/2; ++i){
swap(v[i], v[v.size()-1-i]);
}
}
int main(int argc, char **argv) {
vector<string> args(argv, argv+argc);
auto v = genVectorByRandom(arSize, rndMax);
view(v);
reverse(v);
view(v);
return 0;
}
「ライブラリを使わないで」とあるが、問題の解答例では昇順に並んでいる配列が与えられていたため、配列の生成とソートまではそのまま使うことにした。プログラムはQ8と一緒になってしまった。
q10.cpp
#include <iostream>
#include <vector>
#include <genVector.hpp>
#include <template.hpp>
using namespace std;
constexpr size_t arSize = 10;
constexpr int rndMax = 10;
template <typename T> void duplicateTo0 (vector<T>& v){
size_t i, j;
for(i=0; i<v.size(); ++i){
for(j=i+1; j<v.size() && v[i]==v[j]; ++j){
v[j] = 0;
}
i = j - 1;
}
}
int main(int argc, char **argv) {
vector<string> args(argv, argv+argc);
auto v = genVectorByRandom(arSize, rndMax);
view(v);
sort(v.begin(), v.end());
view(v);
duplicateTo0(v);
view(v);
return 0;
}
おわりに
今回は大問１の配列に関する問題だけをまとめました。続きの問題も少しづつ解いていけたらと思っています！
Author And Source
この問題について(配列のコーディングに関する問題をC++で解いてみた), 我々は、より多くの情報をここで見つけました https://qiita.com/ysuzuki19/items/df4904eda9b7a6b63642著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .