Problem C - Count XXX

Principle

文字列Sが与えられたとき、同じ文字の繰り返しであるSの明確な部分文字列の数を数えることが目的である。例えば、aabcaaは4つの部分文字列を含む： a、aa、b、cである。aとaaはSに2回出現するが、1回しかカウントされないことに注意。

My solution

問題をきちんと読まなかったために、時間を無駄にしてしまった。🤦‍♂️ 私は、O(n)の複雑さ、つまり1回のパスで部分文字列を計算したかった。そのためには、現在の文字を1つだけ記憶し、繰り返しを数えればよい。文字が変わったら、実際の部分文字列を変更する。最初のバージョンでは、現在の文字と現在の部分文字列をループ変数として保持していた。ある部分文字列が以前に既に存在していたかどうかを判断するために、私はHashMapを使い、ルックアップが一定の時間で済むようにしている。問題は、ハッシュマップのキーに何を使うかということだ。まず、実際の部分文字列を使った。問題は、すべての部分文字列を保存すると、特にすべての長さを保存するため、大量のメモリが必要になることだ。元の文字列の最大長は2E5で、すべての部分文字列をキーとして格納しようとすると、かなりのメモリが必要になる。 ヒント：実は、すべてのキーは繰り返し1文字しか含んでいない。つまり、文字と部分文字列の長さをキーとして格納すればいいのだ。

The Code

let mut cur_char: char = s[0];
let mut cur_len: usize = 1;
let mut substr_hash: HashMap<(char, usize), usize> = HashMap::new();
	substr_hash.insert( (s[0],1) , 1);

for i in 1..n {
	if cur_char != s[i] {
		// We change character
		substr_hash.insert((cur_char, cur_len ), 1);
		cur_len = 1;
		cur_char = s[i];
	} else {
		substr_hash.insert((cur_char, cur_len), 1);
		cur_len = cur_len +1;
	}
}
// We need to process the last substring 
substr_hash.insert((cur_char, cur_len), 1);
println!("{}", substr_hash.len());

Problem D - Election Quick Report

The principle

N人の候補者の間で選挙を行う。一票一票を読み、各投票ごとに最も得票数の多い候補者のIDを印刷する必要がある。

My solution

問題は実はとてもシンプルだ。すべての候補者の得点を、素早くアクセスできるようにHashMapに保存しておく。総当たり的な解決策は、すべての票を比較して有力候補を見つけることだ。しかし、それでは遅すぎる。 ヒント：スコアが変化する唯一の候補は、今投票を受けた候補である。この候補者がリーダーになるか、リーダーは変わらないかのどちらかである。したがって、得点と先頭候補のインデックスをループ変数として保持する必要がある。残念ながら、この解答を提出したのは1分も遅かったので、ポイントはもらえませんでした…。

let mut vote_count: HashMap<usize, usize> = HashMap::new();
let mut max_score: usize = 0;
let mut max_candidate: usize = 0;

for i in 0..m {

	// Recording the current vote
	let current_candidate = a[i];
	let current_score;
	if !vote_count.contains_key(&current_candidate) {
		vote_count.insert(current_candidate, 1);
		current_score = 1;
	} else {
		let new_count = vote_count.get(&current_candidate).unwrap() + 1;
		vote_count.insert(current_candidate, new_count);
		current_score = new_count;
	}

	// Now let's figure out the winner for this round
	if current_score > max_score {
		max_score = current_score;
		max_candidate = current_candidate;
	} else {
		// Rule which says that in case of equal scores,
		// the candidate with the smallest index leads
		if current_score == max_score {
		max_candidate = current_candidate.min(max_candidate);
	}
}
println!("{}", max_candidate);
}