C++の美しいアレンジメントII

2つの整数nとkがあるとすると、1からnの範囲のn個の異なる正の整数を含み、次の規則に従うリストを作成する必要があります-

リストが[a1、a2、a3、...、an]であるとすると、リスト[| a1 --a2 |、| a2 --a3 |、| a3 --a4 |、...、| an-1-an |]は正確にk個の一意の整数を持っています。したがって、複数の回答がある場合は、それらのいずれかを表示してください。

入力がn=3およびk=2のような場合、結果は[1,3,2]になります。 [1,3,2]には、1から3の範囲の3つの異なる正の整数があり、[2,1]には、正確に2つの異なる整数1と2があります。

これを解決するには、次の手順に従います-

• 配列retを定義する
• i：=1、j：=nの場合、i <=j
  かどうかを確認します
  • k> 1の場合、
    • kが奇数の場合は、iを挿入します。それ以外の場合は、jをretに挿入します
    • kが奇数の場合は、iを1増やし、それ以外の場合はjを1減らします
    • kを1減らします
  • それ以外の場合は、iをresに挿入し、iを1増やします
• return ret

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> constructArray(int n, int k) {
      vector <int> ret;
      for(int i = 1, j = n; i <= j; ){
         if(k > 1){
            ret.push_back(k % 2 ? i : j);
            if(k % 2 == 1){
               i++;
            }else j--;
            k--;
         } else {
            ret.push_back(i++);
        }
      }
      return ret;
   }
};
main(){
   Solution ob;
   print_vector(ob.constructArray(3, 2));
}

入力

3
2

出力

[3, 1, 2, ]