写点什么

2023-08-02:给定一棵树,一共有 n 个点, 每个点上没有值,请把 1~n 这些数字,不重复的分配到二叉树上, 做到 : 奇数层节点的值总和 与 偶数层节点的值总和 相差不超过 1。 返回奇数层节点分配

  • 2023-08-02
    北京
  • 本文字数:3767 字

    阅读完需:约 12 分钟

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 完整代码如下:

package main
import "fmt"
// generate returns an array of k numbers between 1 and n whose sum is wantSumfunc 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 nodesfunc 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 完整代码如下:

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++完整代码如下:

#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 完整代码如下:

#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;}
复制代码



发布于: 刚刚阅读数: 4
用户头像

公众号:福大大架构师每日一题 2021-02-15 加入

公众号:福大大架构师每日一题

评论

发布
暂无评论
2023-08-02:给定一棵树,一共有n个点, 每个点上没有值,请把1~n这些数字,不重复的分配到二叉树上, 做到 : 奇数层节点的值总和 与 偶数层节点的值总和 相差不超过1。 返回奇数层节点分配_福大大架构师每日一题_福大大架构师每日一题_InfoQ写作社区