美団2019秋招プログラミング問題-最長全1房-JavaScript解法
10313 ワード
問題の説明
あなたに1つの01文字列をあげて、解答=この列の中で最も長い連続の1の長さを定義して、今あなたは多くK回の機会があって、毎回機会は列の中のある0を1に変えてもいいです.今最大の可能性の解答を聞きます.
説明を入力
1行目の整数N、Kを入力して、文字列の長さと機会の回数を表します.2行目はN個の整数を入力して、文字列の要素(1<=N==3000,000、>0<=K<=N)を表します.
出力の説明
答えを表す行を出力します.
入力サンプル
10 2 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1
出力サンプル
5
問題を解く構想
LeetCode 424の問題を参照してください.「置換後の最大の重複文字」
スライドウィンドウ
leftを利用して、right-left+1はスライドウィンドウのサイズであり、rightポインタは文字列全体を巡回しています.leftの移動はスライドウィンドウ内の1の最大個数+置換個数kおよびrightの大きさに依存します.すなわち、right-left+1>max+k(スライドウィンドウの長さがウィンドウ内のiの数+kより大きい場合)は、スライドウィンドウを縮小する必要があります.
具体的に実現する
コードは以下の通りです
あなたに1つの01文字列をあげて、解答=この列の中で最も長い連続の1の長さを定義して、今あなたは多くK回の機会があって、毎回機会は列の中のある0を1に変えてもいいです.今最大の可能性の解答を聞きます.
説明を入力
1行目の整数N、Kを入力して、文字列の長さと機会の回数を表します.2行目はN個の整数を入力して、文字列の要素(1<=N==3000,000、>0<=K<=N)を表します.
出力の説明
答えを表す行を出力します.
入力サンプル
10 2 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1
出力サンプル
5
問題を解く構想
LeetCode 424の問題を参照してください.「置換後の最大の重複文字」
スライドウィンドウ
leftを利用して、right-left+1はスライドウィンドウのサイズであり、rightポインタは文字列全体を巡回しています.leftの移動はスライドウィンドウ内の1の最大個数+置換個数kおよびrightの大きさに依存します.すなわち、right-left+1>max+k(スライドウィンドウの長さがウィンドウ内のiの数+kより大きい場合)は、スライドウィンドウを縮小する必要があります.
具体的に実現する
function replace(s,k){
if(s.length < k){
return s.length;
}
let nums = s.split("");
let left = 0,right =0;
let max = 0;// 1
for(;right<nums.length;right++){
let index = nums[right];
if(index == 1){
max++
}
if(right -left +1 > max+k){
// ,left
if(nums[left] == 1){
max--
}
left++;
}
}
return (nums.length-1)-left+1;
}
LeetCodeの違いコードは以下の通りです
var characterReplacement = function(s, k) {
if(s.length < k){
return s.length;
}
let map = new Array(s.length).fill(0);
let nums = s.split("");
let left = 0,right =0;
let max = 0;
for(;right<nums.length;right++){
let index = nums[right].charCodeAt(0) - 'A'.charCodeAt(0) ;
map[index]++;
max = Math.max(max,map[index]);
if(right -left +1 > max+k){
map[nums[left].charCodeAt(0) -'A'.charCodeAt(0) ]--;
left++;
}
}
return (nums.length-1)-left+1;
};
大文字の文字列は置換後の最長全X(ある文字)列を求めます.この時は全1列よりも、スライドウィンドウの最大回数を記録する必要があります.map[index]で文字がスライドウィンドウに現れる最大回数を記録する必要があります.