LoginSignup
0
1

More than 3 years have passed since last update.

@ysuzuki19

配列のコーディングに関する問題をC++で解いてみた

Posted at

はじめに

ネットで見かけた問題が面白そうでとこうと思い、解き始めました。せっかく解いたので、問題の紹介も兼ねて記事にすることにしました。

全ての問題を解き終わってからまとめようと思ったのですが、時間がかかりそうだったので、見出しで一旦まとめることにしました。

問題

こちらにある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.ライブラリを使わないで配列から重複を削除

「ライブラリを使わないで」とあるが、問題の解答例では昇順に並んでいる配列が与えられていたため、配列の生成とソートまではそのまま使うことにした。プログラムは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;
}

おわりに

今回は大問１の配列に関する問題だけをまとめました。続きの問題も少しづつ解いていけたらと思っています！

0
1
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
1