Beautiful Array trong C++

Mảng A là beautiful nếu là hoán vị của 1..N và không tồn tại i

Ví dụ: N=5 → [3,1,2,5,4] (hoặc [1,5,3,2,4] theo code).

Giải pháp xây dựng đệ quy:

• Bắt đầu ret = [1]

• While size(ret) < N:
  Tạo temp: trước thêm 2*x-1 (số lẻ) từ ret nếu ≤ N
  Sau thêm 2*x (số chẵn) từ ret nếu ≤ N
  ret = temp

• Trả về ret

Ý tưởng: tách lẻ/chẵn bảo toàn tính chất không có trung bình cộng.

Ví dụ

#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> beautifulArray(int N) {       vector <int> ret; ret.push_back(1);       while(ret.size() < N){          vector <int> temp;          for(int x : ret) if(x*2-1 <= N) temp.push_back(x*2-1);          for(int x : ret) if(x*2 <= N) temp.push_back(x*2);          ret = temp;       }       return ret;    } }; int main(){ Solution ob; print_vector(ob.beautifulArray(6)); }

Đầu vào

5

Đầu ra

[1,5,3,2,4]