資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的美麗排列 II
假設我們有兩個整數 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 插入 ret，否則將 j 插入 ret
- 如果 k 是奇數，則將 i 增加 1，否則將 j 減小 1
- 將 k 減小 1
- 否則將 i 插入 res 並將 i 增加 1
- 如果 k > 1，則
- 返回 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, ]
更新於: 2020年5月4日
131 次檢視
廣告