สมมติว่าเรามีจำนวนเต็ม n และ k สองจำนวน เราจำเป็นต้องสร้างรายการที่มีจำนวนเต็มบวกที่แตกต่างกัน n จำนวนตั้งแต่ 1 ถึง 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 และ [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
- ถ้า k> 1 แล้ว
- คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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, ]
