Сложность: medium
Вы играете в игру "Быки и коровы" со своим другом.
Вы записываете секретное число и просите своего друга угадать, что это за число. Когда ваш друг делает предположение, вы даете ему подсказку со следующей информацией:
Количество "быков", то есть цифры в предположении, которые находятся на правильной позиции.
Количество "коров", то есть цифры в предположении, которые есть в вашем секретном числе, но находятся на неправильной позиции. Конкретно, это не-бычьи цифры в предположении, которые можно переставить так, чтобы они стали быками.
Дано секретное число secret и предположение вашего друга guess, верните подсказку для предположения вашего друга.
Подсказка должна быть в формате "xAyB", где x — количество быков, а y — количество коров. Обратите внимание, что и secret, и guess могут содержать повторяющиеся цифры.
Пример:
Input: secret = "1807", guess = "7810"
Output: "1A3B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1807"
|
"7810"
👨💻 Алгоритм:
1⃣Инициализация счетчиков:
Инициализируйте количество быков и коров значениями ноль.
Создайте хеш-таблицу для хранения символов строки secret и их частот.
2⃣Обход строки guess:
Для каждого символа ch в строке guess:
Если ch присутствует в строке secret:
Если текущий символ ch совпадает с символом на той же позиции в secret (ch == secret[idx]):
Увеличьте количество быков: bulls += 1.
Обновите количество коров, если количество текущего символа в хеш-таблице отрицательное или равно нулю (то есть этот символ уже использовался для коров): cows -= int(h[ch] <= 0).
Если текущий символ ch не совпадает с символом на той же позиции в secret (ch != secret[idx]):
Увеличьте количество коров, если количество текущего символа в хеш-таблице больше нуля: cows += int(h[ch] > 0).
Обновите хеш-таблицу, помечая текущий символ как использованный: h[ch] -= 1.
3⃣Возврат результата:
Верните количество быков и коров в формате "xAyB".
😎 Решение:
class Solution {
function getHint($secret, $guess) {
$h = [];
for ($i = 0; $i < strlen($secret); $i++) {
$ch = $secret[$i];
if (!isset($h[$ch])) {
$h[$ch] = 0;
}
$h[$ch]++;
}
$bulls = 0;
$cows = 0;
$n = strlen($guess);
$secretArray = str_split($secret);
$guessArray = str_split($guess);
for ($idx = 0; $idx < $n; $idx++) {
$ch = $guessArray[$idx];
if (isset($h[$ch])) {
if ($ch == $secretArray[$idx]) {
$bulls++;
if ($h[$ch] <= 0) {
$cows--;
}
} else {
if ($h[$ch] > 0) {
$cows++;
}
}
$h[$ch]--;
}
}
return "{$bulls}A{$cows}B";
}
}
?>Ставь 👍 и забирай 📚 Базу знаний