2023-08-02：給定一棵樹(shù)，一共有n個(gè)點(diǎn)， 每個(gè)點(diǎn)上沒(méi)有值，請(qǐng)把1~n這些數(shù)字，不重復(fù)的
2023-08-02：給定一棵樹(shù)，一共有n個(gè)點(diǎn)，
每個(gè)點(diǎn)上沒(méi)有值，請(qǐng)把1~n這些數(shù)字，不重復(fù)的分配到二叉樹(shù)上，
做到 : 奇數(shù)層節(jié)點(diǎn)的值總和 與 偶數(shù)層節(jié)點(diǎn)的值總和 相差不超過(guò)1。
返回奇數(shù)層節(jié)點(diǎn)分配值的一個(gè)方案。
2 <= n <= 10^5 。
來(lái)自騰訊音樂(lè)。
答案2023-08-02：
大致步驟如下：
1.計(jì)算出1到n的總和sum。
2.確定兩個(gè)目標(biāo)值p1和p2，它們分別是sum的整數(shù)除法結(jié)果和向上取整結(jié)果。p1和p2代表了奇數(shù)層節(jié)點(diǎn)總和和偶數(shù)層節(jié)點(diǎn)總和的一半。
3.調(diào)用generate函數(shù)來(lái)生成奇數(shù)層節(jié)點(diǎn)的分配方案。generate函數(shù)用于生成一個(gè)數(shù)組，其中包含k個(gè)數(shù)，這k個(gè)數(shù)的和為指定的wantSum。如果無(wú)法生成滿足要求的方案，則返回nil。
4.如果generate函數(shù)返回nil并且sum是奇數(shù)，說(shuō)明無(wú)法找到滿足要求的奇數(shù)層節(jié)點(diǎn)方案。這種情況下，重新調(diào)用generate函數(shù)來(lái)生成偶數(shù)層節(jié)點(diǎn)的分配方案。
5.如果兩次調(diào)用generate函數(shù)都沒(méi)有找到滿足要求的方案，則返回[-1]表示無(wú)解。
6.輸出生成的方案。
時(shí)間復(fù)雜度分析：
??計(jì)算sum的時(shí)間復(fù)雜度為O(1)。
??generate函數(shù)的時(shí)間復(fù)雜度為O(k)。
??整體時(shí)間復(fù)雜度為O(k)。
空間復(fù)雜度分析：
??generate函數(shù)中創(chuàng)建了一個(gè)大小為k的數(shù)組來(lái)存儲(chǔ)結(jié)果，所以空間復(fù)雜度為O(k)。
??整體空間復(fù)雜度為O(k)。
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完整代碼如下：
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!("長(zhǎng)度:?{}",?ans.len());
????print!("數(shù)字:?");
????for?num?in?ans?{
????????print!("{}?",?num);
????}
????println!();
????println!("求和:?{}",?sum);
????println!("剩余:?{}",?(n?+?1)?*?n?/?2?-?sum);
}
c++完整代碼如下：
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?<<?"長(zhǎng)度?:?"?<<?ans.size()?<<?endl;
????int?sum?=?0;
????cout?<<?"數(shù)字?:?";
????for?(int?num?:?ans)?{
????????cout?<<?num?<<?"?";
????????sum?+=?num;
????}
????cout?<<?endl;
????cout?<<?"求和?:?"?<<?sum?<<?endl;
????cout?<<?"剩余?:?"?<<?((n?+?1)?*?n?/?2?-?sum)?<<?endl;
????return?0;
}
c完整代碼如下：
//?一共?1?~?n?這些數(shù)字
//?其中選k個(gè)數(shù)字
//?一定要讓k個(gè)數(shù)字的累加和是wantSum
//?返回，哪k個(gè)數(shù)字，只要返回一種方法就可以
int*?generate(int?wantSum,?int?n,?int?k)?{
????//?k個(gè)數(shù)字，和最小的情況，1?2?3?...?k
????int?sumMinK?=?(k?+?1)?*?k?/?2;
????//?每個(gè)數(shù)提升的幅度
????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?奇數(shù)節(jié)點(diǎn)的個(gè)數(shù)是k個(gè)
//?返回奇數(shù)節(jié)點(diǎn)的值有哪些
int*?team(int?n,?int?k)?{
????//?1?~?n?,??sum?=?10???k個(gè)奇數(shù)??5
????//?1?~?n?,??sum?=?15???k個(gè)奇數(shù)??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這些數(shù)字都有
????int?n?=?100;
????//?k是個(gè)數(shù)
????int?k?=?33;
????//?1~n這些數(shù)字，選k個(gè)，能不能求和逼近一半
????//?返回方案
????int*?ans?=?team(n,?k);
????if?(ans?!=?NULL)?{
????????printf("總和?:?%d\n",?(n?+?1)?*?n?/?2);
????????printf("長(zhǎng)度?:?%d\n",?k);
????????int?sum?=?0;
????????printf("數(shù)字?:?");
????????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("無(wú)解\n");
????}
????free(ans);??//?釋放內(nèi)存
????return?0;
}
