2023-08-02：給定一棵樹，一共有n個點，
每個點上沒有值，請把1~n這些數字，不重復的分配到二叉樹上，
做到 : 奇數層節點的值總和 與 偶數層節點的值總和 相差不超過1。
返回奇數層節點分配值的一個方案。
2 <= n <= 10^5 。
來自騰訊音樂。
答案2023-08-02：
# 大致步驟如下：
1.計算出1到n的總和sum。
2.確定兩個目標值p1和p2，它們分別是sum的整數除法結果和向上取整結果。p1和p2代表了奇數層節點總和和偶數層節點總和的一半。
3.調用generate函數來生成奇數層節點的分配方案。generate函數用于生成一個數組，其中包含k個數，這k個數的和為指定的wantSum。如果無法生成滿足要求的方案，則返回nil。
4.如果generate函數返回nil并且sum是奇數，說明無法找到滿足要求的奇數層節點方案。這種情況下，重新調用generate函數來生成偶數層節點的分配方案。
5.如果兩次調用generate函數都沒有找到滿足要求的方案，則返回[-1]表示無解。
6.輸出生成的方案。
時間復雜度分析：
- 計算sum的時間復雜度為O(1)。
- generate函數的時間復雜度為O(k)。
- 整體時間復雜度為O(k)。
空間復雜度分析：
- generate函數中創建了一個大小為k的數組來存儲結果，所以空間復雜度為O(k)。
- 整體空間復雜度為O(k)。
# go完整代碼如下：
```go
package main
import "fmt"
// generate returns an array of k numbers between 1 and n whose sum is wantSum
func generate(wantSum, n, k int) []int {
// The minimum sum of k numbers, for example: 1 2 3 ... k
sumMinK := (k + 1) * k / 2
// The range each number can increase
rangeVal := n - k
if wantSum < sumMinK || wantSum > sumMinK+k*rangeVal {
return nil
}
add := wantSum - sumMinK
rightSize := add / rangeVal
midIndex := (k - rightSize) + (add % rangeVal)
leftSize := k - rightSize
if add%rangeVal != 0 {
leftSize--
}
ans := make([]int, k)
for i := 0; i < leftSize; i++ {
ans[i] = i + 1
}
if add%rangeVal != 0 {
ans[leftSize] = midIndex
}
for i, j := k-1, 0; j < rightSize; i, j = i-1, j+1 {
ans[i] = n - j
}
return ans
}
// team returns the values of the odd nodes out of 1 to n, with a total of k nodes
func team(n, k int) []int {
sum := (n + 1) * n / 2
p1 := sum / 2
p2 := (sum + 1) / 2
ans := generate(p1, n, k)
if ans == nil && (sum&1) == 1 {
ans = generate(p2, n, k)
}
if ans == nil {
ans = []int{-1}
}
return ans
}
func main() {
// n is the maximum value, includes 1 to n
n := 100
// k is the number of nodes
k := 33
// Can we approximate half the sum of 1 to n by selecting k nodes? Return the solution.
ans := team(n, k)
fmt.Println("Sum:", (n+1)*n/2)
fmt.Println("Length:", len(ans))
sum := 0
fmt.Print("Numbers:")
for _, num := range ans {
fmt.Print(num, " ")
sum += num
}
fmt.Println()
fmt.Println("Sum:", sum)
fmt.Println("Remaining:", (n+1)*n/2-sum)
}
```
# rust完整代碼如下：
```rust
fn team(n: i32, k: i32) -> Vec<i32> {
let sum = (n + 1) * n / 2;
let p1 = sum / 2;
let p2 = (sum + 1) / 2;
let ans = generate(p1, n, k);
if ans.is_none() && sum % 2 == 1 {
generate(p2, n, k)
} else {
ans
}
.unwrap_or(vec![-1])
}
fn generate(want_sum: i32, n: i32, k: i32) -> Option<Vec<i32>> {
let sum_min_k = (k + 1) * k / 2;
let range = n - k;
if want_sum < sum_min_k || want_sum > sum_min_k + k * range {
return None;
}
let add = want_sum - sum_min_k;
let right_size = add / range;
let mid_index = (k - right_size) + (add % range);
let left_size = k - right_size - if add % range == 0 { 0 } else { 1 };
let mut ans = vec![0; k as usize];
for i in 0..left_size as usize {
ans[i] = (i + 1) as i32;
}
if add % range != 0 {
ans[left_size as usize] = mid_index;
}
let mut i = k - 1;
let mut j = 0;
while j < right_size {
ans[i as usize] = n - j;
i -= 1;
j += 1;
}
Some(ans)
}
fn main() {
let n = 100;
let k = 33;
let ans = team(n, k);
let sum: i32 = ans.iter().sum();
println!("總和: {}", (n + 1) * n / 2);
println!("長度: {}", ans.len());
print!("數字: ");
for num in ans {
print!("{} ", num);
}
println!();
println!("求和: {}", sum);
println!("剩余: {}", (n + 1) * n / 2 - sum);
}
```
# c++完整代碼如下：
```cpp
#include <iostream>
#include <vector>
using namespace std;
vector<int> generate(int wantSum, int n, int k) {
int sumMinK = (k + 1) * k / 2;
int range = n - k;
if (wantSum < sumMinK || wantSum > sumMinK + k * range) {
return {};
}
int add = wantSum - sumMinK;
int rightSize = add / range;
int midIndex = (k - rightSize) + (add % range);
int leftSize = k - rightSize - ((add % range) == 0 ? 0 : 1);
vector<int> ans(k);
for (int i = 0; i < leftSize; i++) {
ans[i] = i + 1;
}
if (add % range != 0) {
ans[leftSize] = midIndex;
}
for (int i = k - 1, j = 0; j < rightSize; i--, j++) {
ans[i] = n - j;
}
return ans;
}
vector<int> team(int n, int k) {
int sum = (n + 1) * n / 2;
int p1 = sum / 2;
int p2 = (sum + 1) / 2;
vector<int> ans = generate(p1, n, k);
if (ans.empty() && (sum & 1) == 1) {
ans = generate(p2, n, k);
}
return ans.empty() ? vector<int>{-1} : ans;
}
int main() {
int n = 100;
int k = 33;
vector<int> ans = team(n, k);
cout << "總和 : " << (n + 1) * n / 2 << endl;
cout << "長度 : " << ans.size() << endl;
int sum = 0;
cout << "數字 : ";
for (int num : ans) {
cout << num << " ";
sum += num;
}
cout << endl;
cout << "求和 : " << sum << endl;
cout << "剩余 : " << ((n + 1) * n / 2 - sum) << endl;
return 0;
}
```
# c完整代碼如下：
```c
#include <stdio.h>
#include <stdlib.h>
// 一共 1 ~ n 這些數字
// 其中選k個數字
// 一定要讓k個數字的累加和是wantSum
// 返回，哪k個數字，只要返回一種方法就可以
int* generate(int wantSum, int n, int k) {
// k個數字，和最小的情況，1 2 3 ... k
int sumMinK = (k + 1) * k / 2;
// 每個數提升的幅度
int range = n - k;
if (wantSum < sumMinK || wantSum > sumMinK + k * range) {
return NULL;
}
int add = wantSum - sumMinK;
int rightSize = add / range;
int midIndex = (k - rightSize) + (add % range);
int leftSize = k - rightSize - (add % range == 0 ? 0 : 1);
int* ans = (int*)malloc(k * sizeof(int));
for (int i = 0; i < leftSize; i++) {
ans[i] = i + 1;
}
if (add % range != 0) {
ans[leftSize] = midIndex;
}
for (int i = k - 1, j = 0; j < rightSize; i--, j++) {
ans[i] = n - j;
}
return ans;
}
// 1 ~ n 奇數節點的個數是k個
// 返回奇數節點的值有哪些
int* team(int n, int k) {
// 1 ~ n , sum = 10 k個奇數 5
// 1 ~ n , sum = 15 k個奇數 7 8
int sum = (n + 1) * n / 2;
int p1 = sum / 2;
int p2 = (sum + 1) / 2;
int* ans = generate(p1, n, k);
if (ans == NULL && (sum & 1) == 1) {
ans = generate(p2, n, k);
}
return ans != NULL ? ans : NULL;
}
int main() {
// n是最大值，1~n這些數字都有
int n = 100;
// k是個數
int k = 33;
// 1~n這些數字，選k個，能不能求和逼近一半
// 返回方案
int* ans = team(n, k);
if (ans != NULL) {
printf("總和 : %d\n", (n + 1) * n / 2);
printf("長度 : %d\n", k);
int sum = 0;
printf("數字 : ");
for (int i = 0; i < k; i++) {
printf("%d ", ans[i]);
sum += ans[i];
}
printf("\n");
printf("求和 : %d\n", sum);
printf("剩余 : %d\n", ((n + 1) * n / 2 - sum));
}
else {
printf("無解\n");
}
free(ans); // 釋放內存
return 0;
}
```
