2023-08-24：請用go語言編寫。給定一個長度為n的數(shù)組arr， 現(xiàn)在你有一次機會, 將其中
2023-08-24：請用go語言編寫。給定一個長度為n的數(shù)組arr，
現(xiàn)在你有一次機會, 將其中連續(xù)的K個數(shù)全修改成任意一個值，
請你計算如何修改可以使修改后的數(shù) 列的最長不下降子序列最長。
請輸出這個最長的長度。
最長不下降子序列:子序列中的每個數(shù)不小于在它之前的數(shù)。
1 <= k, n <= 10^5，
1 <= arr[i] <= 10^6。
來自左程云。
答案2023-08-24：
以下是大致的步驟描述：
1.定義常量MAXN為100001，聲明全局數(shù)組和變量：arr、right、ends、n和k。這些數(shù)組和變量將用于存儲計算過程中的中間結果和輸入數(shù)據(jù)。
2.在main函數(shù)中設置給定的輸入數(shù)據(jù)：n表示數(shù)組的長度為5，k表示連續(xù)的k個數(shù)需要修改，arr存儲具體的數(shù)組元素。
3.判斷如果k大于等于n，則無需做修改，直接輸出n作為最長不下降子序列的長度。
4.否則，調(diào)用rightFn函數(shù)計算修改后的數(shù)組中以每個元素為結尾的最長不下降子序列的長度，并將結果存儲在數(shù)組right和ends中。
5.調(diào)用getAns函數(shù)計算修改后的數(shù)組的最長不下降子序列的長度，并輸出結果。
rightFn函數(shù)的步驟描述：
1.初始化right數(shù)組的最后一個元素right[n]為1，表示以最后一個元素為結尾的最長不下降子序列的長度為1。
2.初始化ends數(shù)組的第一個元素ends[1]為arr[n]，表示以最后一個元素為結尾的最長不下降子序列的最后一個元素為arr[n]。
3.初始化len為1，表示當前得到的最長不下降子序列的長度為1。
4.從倒數(shù)第二個元素開始，循環(huán)遍歷數(shù)組arr，通過二分查找的方式找到以arr[i]為結尾的最長不下降子序列的長度。
5.使用二分查找的輔助數(shù)組ends，找到大于arr[i]的第一個元素位置find。
6.將arr[i]賦值給ends[find]，更新當前的最長不下降子序列的長度為max(len, find)，并將結果存儲在right[i]中。
7.循環(huán)結束后，right數(shù)組存儲了以每個元素為結尾的最長不下降子序列的長度。
getAns函數(shù)的步驟描述：
1.初始化ans為0，表示當前的最長不下降子序列的長度為0。
2.初始化len為0，表示當前最長不下降子序列的長度為0。
3.從第k+1個元素開始，循環(huán)遍歷數(shù)組arr，計算修改后的數(shù)組的最長不下降子序列的長度。
4.使用二分查找的方式找到arr[i]在ends數(shù)組中的位置find。
5.更新ans為max(ans, find+right[i]-1+k)。其中，find表示以arr[i]為結尾的最長不下降子序列的長度，right[i]表示以arr[i]為起點的最長不下降子序列的長度，k表示連續(xù)的k個數(shù)被修改。
6.使用二分查找的輔助數(shù)組ends，找到大于arr[j]的第一個元素位置find（這里j為i-k）。
7.將arr[j]賦值給ends[find]，更新當前的最長不下降子序列的長度為max(len, find)。
8.循環(huán)結束后，ans存儲了修改后的數(shù)組的最長不下降子序列的長度。
9.返回ans作為結果。
總的時間復雜度為O(n log n)，其中n為數(shù)組的長度，主要是由二分查找的過程引起的。
總的額外空間復雜度為O(n)，主要是由數(shù)組的存儲引起的。
go完整代碼如下：
package?main
import?(
????"fmt"
)
const?MAXN?=?100001
var?arr?[MAXN]int
var?right?[MAXN]int
var?ends?[MAXN]int
var?n,?k?int
func?main()?{
????n?=?5
????k?=?1
????arr[1]?=?1
????arr[2]?=?4
????arr[3]?=?2
????arr[4]?=?8
????arr[5]?=?5
????if?k?>=?n?{
????????fmt.Println(n)
????}?else?{
????????rightFn()
????????fmt.Println(getAns())
????}
}
func?rightFn()?{
????right[n]?=?1
????ends[1]?=?arr[n]
????len?:=?1
????for?i?:=?n?-?1;?i?>?0;?i--?{
????????l?:=?1
????????r?:=?len
????????find?:=?len?+?1
????????for?l?<=?r?{
????????????m?:=?(l?+?r)?/?2
????????????if?ends[m]?<?arr[i]?{
????????????????find?=?m
????????????????r?=?m?-?1
????????????}?else?{
????????????????l?=?m?+?1
????????????}
????????}
????????ends[find]?=?arr[i]
????????len?=?max(len,?find)
????????right[i]?=?find
????}
}
func?getAns()?int?{
????ans?:=?0
????len?:=?0
????for?i,?j?:=?k+1,?1;?i?<=?n;?i,?j?=?i+1,?j+1?{
????????l?:=?1
????????r?:=?len
????????find?:=?len?+?1
????????for?l?<=?r?{
????????????m?:=?(l?+?r)?/?2
????????????if?ends[m]?>?arr[i]?{
????????????????find?=?m
????????????????r?=?m?-?1
????????????}?else?{
????????????????l?=?m?+?1
????????????}
????????}
????????ans?=?max(ans,?find+right[i]-1+k)
????????l?=?1
????????r?=?len
????????find?=?len?+?1
????????for?l?<=?r?{
????????????m?:=?(l?+?r)?/?2
????????????if?ends[m]?>?arr[j]?{
????????????????find?=?m
????????????????r?=?m?-?1
????????????}?else?{
????????????????l?=?m?+?1
????????????}
????????}
????????len?=?max(len,?find)
????????ends[find]?=?arr[j]
????}
????ans?=?max(ans,?len+k)
????return?ans
}
func?max(a,?b?int)?int?{
????if?a?>?b?{
????????return?a
????}
????return?b
}
rust完整代碼如下：
const?MAXN:?i32?=?100001;
static?mut?ARR:?[i32;?MAXN?as?usize]?=?[0;?MAXN?as?usize];
static?mut?RIGHT:?[i32;?MAXN?as?usize]?=?[0;?MAXN?as?usize];
static?mut?ENDS:?[i32;?MAXN?as?usize]?=?[0;?MAXN?as?usize];
static?mut?N:?i32?=?0;
static?mut?K:?i32?=?0;
fn?main()?{
????unsafe?{
????????N?=?5;
????????K?=?1;
????????ARR[1]?=?1;
????????ARR[2]?=?4;
????????ARR[3]?=?2;
????????ARR[4]?=?8;
????????ARR[5]?=?5;
????????if?K?>=?N?{
????????????println!("{}",?N);
????????}?else?{
????????????right_fn();
????????????println!("{}",?get_ans());
????????}
????}
}
fn?right_fn()?{
????unsafe?{
????????RIGHT[N?as?usize]?=?1;
????????ENDS[1]?=?ARR[N?as?usize];
????????let?mut?len:?i32?=?1;
????????let?mut?i?=?N?-?1;
????????while?i?>=?0?{
????????????let?mut?l?=?1;
????????????let?mut?r?=?len;
????????????let?mut?find?=?len?+?1;
????????????while?l?<=?r?{
????????????????let?m?=?(l?+?r)?/?2;
????????????????if?ENDS[m?as?usize]?<?ARR[i?as?usize]?{
????????????????????find?=?m;
????????????????????r?=?m?-?1;
????????????????}?else?{
????????????????????l?=?m?+?1;
????????????????}
????????????}
????????????ENDS[find?as?usize]?=?ARR[i?as?usize];
????????????len?=?max(len,?find);
????????????RIGHT[i?as?usize]?=?find;
????????????i?-=?1;
????????}
????}
}
fn?get_ans()?->?i32?{
????let?mut?ans?=?0;
????let?mut?len?=?0;
????unsafe?{
????????let?mut?i?=?K?+?1;
????????let?mut?j:?i32?=?1;
????????while?i?<=?N?{
????????????let?mut?l:?i32?=?1;
????????????let?mut?r?=?len;
????????????let?mut?find?=?len?+?1;
????????????while?l?<=?r?{
????????????????let?m?=?(l?+?r)?/?2;
????????????????if?ENDS[m?as?usize]?>?ARR[i?as?usize]?{
????????????????????find?=?m;
????????????????????r?=?m?-?1;
????????????????}?else?{
????????????????????l?=?m?+?1;
????????????????}
????????????}
????????????ans?=?max(ans,?find?+?RIGHT[i?as?usize]?-?1?+?K);
????????????l?=?1;
????????????r?=?len;
????????????find?=?len?+?1;
????????????while?l?<=?r?{
????????????????let?m?=?(l?+?r)?/?2;
????????????????if?ENDS[m?as?usize]?>?ARR[j?as?usize]?{
????????????????????find?=?m;
????????????????????r?=?m?-?1;
????????????????}?else?{
????????????????????l?=?m?+?1;
????????????????}
????????????}
????????????len?=?max(len,?find);
????????????ENDS[find?as?usize]?=?ARR[j?as?usize];
????????????i?+=?1;
????????????j?+=?1;
????????}
????????ans?=?max(ans,?len?+?K);
????}
????ans
}
fn?max(a:?i32,?b:?i32)?->?i32?{
????if?a?>?b?{
????????a
????}?else?{
????????b
????}
}
c++完整代碼如下：
using?namespace?std;
const?int?MAXN?=?100001;
int?arr[MAXN]?=?{?0?};
int?right0[MAXN]?=?{?0?};
int?ends0[MAXN]?=?{?0?};
int?n,?k;
int?max(int?a,?int?b)?{
????if?(a?>?b)?{
????????return?a;
????}
????return?b;
}
void?rightFn()?{
????right0[n]?=?1;
????ends0[1]?=?arr[n];
????int?len?=?1;
????for?(int?i?=?n?-?1;?i?>?0;?i--)?{
????????int?l?=?1;
????????int?r?=?len;
????????int?find?=?len?+?1;
????????while?(l?<=?r)?{
????????????int?m?=?(l?+?r)?/?2;
????????????if?(ends0[m]?<?arr[i])?{
????????????????find?=?m;
????????????????r?=?m?-?1;
????????????}
????????????else?{
????????????????l?=?m?+?1;
????????????}
????????}
????????ends0[find]?=?arr[i];
????????len?=?max(len,?find);
????????right0[i]?=?find;
????}
}
int?getAns()?{
????int?ans?=?0;
????int?len?=?0;
????for?(int?i?=?k?+?1,?j?=?1;?i?<=?n;?i++,?j++)?{
????????int?l?=?1;
????????int?r?=?len;
????????int?find?=?len?+?1;
????????while?(l?<=?r)?{
????????????int?m?=?(l?+?r)?/?2;
????????????if?(ends0[m]?>?arr[i])?{
????????????????find?=?m;
????????????????r?=?m?-?1;
????????????}
????????????else?{
????????????????l?=?m?+?1;
????????????}
????????}
????????ans?=?max(ans,?find?+?right0[i]?-?1?+?k);
????????l?=?1;
????????r?=?len;
????????find?=?len?+?1;
????????while?(l?<=?r)?{
????????????int?m?=?(l?+?r)?/?2;
????????????if?(ends0[m]?>?arr[j])?{
????????????????find?=?m;
????????????????r?=?m?-?1;
????????????}
????????????else?{
????????????????l?=?m?+?1;
????????????}
????????}
????????len?=?max(len,?find);
????????ends0[find]?=?arr[j];
????}
????ans?=?max(ans,?len?+?k);
????return?ans;
}
int?main()?{
????n?=?5;
????k?=?1;
????arr[1]?=?1;
????arr[2]?=?4;
????arr[3]?=?2;
????arr[4]?=?8;
????arr[5]?=?5;
????if?(k?>=?n)?{
????????cout?<<?n?<<?endl;
????}
????else?{
????????rightFn();
????????cout?<<?getAns()?<<?endl;
????}
????return?0;
}
c完整代碼如下：
int?arr[MAXN];
int?right[MAXN];
int?ends[MAXN];
int?n,?k;
int?max(int?a,?int?b)?{
????return?(a?>?b)???a?:?b;
}
void?rightFn()?{
????right[n]?=?1;
????ends[1]?=?arr[n];
????int?len?=?1;
????for?(int?i?=?n?-?1;?i?>?0;?i--)?{
????????int?l?=?1;
????????int?r?=?len;
????????int?find?=?len?+?1;
????????while?(l?<=?r)?{
????????????int?m?=?(l?+?r)?/?2;
????????????if?(ends[m]?<?arr[i])?{
????????????????find?=?m;
????????????????r?=?m?-?1;
????????????}
????????????else?{
????????????????l?=?m?+?1;
????????????}
????????}
????????ends[find]?=?arr[i];
????????len?=?max(len,?find);
????????right[i]?=?find;
????}
}
int?getAns()?{
????int?ans?=?0;
????int?len?=?0;
????for?(int?i?=?k?+?1,?j?=?1;?i?<=?n;?i++,?j++)?{
????????int?l?=?1;
????????int?r?=?len;
????????int?find?=?len?+?1;
????????while?(l?<=?r)?{
????????????int?m?=?(l?+?r)?/?2;
????????????if?(ends[m]?>?arr[i])?{
????????????????find?=?m;
????????????????r?=?m?-?1;
????????????}
????????????else?{
????????????????l?=?m?+?1;
????????????}
????????}
????????ans?=?max(ans,?find?+?right[i]?-?1?+?k);
????????l?=?1;
????????r?=?len;
????????find?=?len?+?1;
????????while?(l?<=?r)?{
????????????int?m?=?(l?+?r)?/?2;
????????????if?(ends[m]?>?arr[j])?{
????????????????find?=?m;
????????????????r?=?m?-?1;
????????????}
????????????else?{
????????????????l?=?m?+?1;
????????????}
????????}
????????len?=?max(len,?find);
????????ends[find]?=?arr[j];
????}
????ans?=?max(ans,?len?+?k);
????return?ans;
}
int?main()?{
????n?=?5;
????k?=?1;
????arr[0]?=?0;
????arr[1]?=?1;
????arr[2]?=?4;
????arr[3]?=?2;
????arr[4]?=?8;
????arr[5]?=?5;
????if?(k?>=?n)?{
????????printf("%d\n",?n);
????}
????else?{
????????rightFn();
????????printf("%d\n",?getAns());
????}
????return?0;
}
2023-08-24：請用go語言編寫。給定一個長度為n的數(shù)組arr， 現(xiàn)在你有一次機會, 將其中的評論 (共 條)
你需要登录后才可以评论。