299. Bulls and Cows
leetcode medium
Task
Вы играете в игру "Быки и коровы" со своим другом.
Вы записываете секретное число и просите своего друга угадать, что это за число. Когда ваш друг делает предположение, вы даете ему подсказку со следующей информацией:
Количество "быков", то есть цифры в предположении, которые находятся на правильной позиции.
Количество "коров", то есть цифры в предположении, которые есть в вашем секретном числе, но находятся на неправильной позиции. Конкретно, это не-бычьи цифры в предположении, которые можно переставить так, чтобы они стали быками.
Дано секретное число 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"
C# solution
matched/originalusing System;
using System.Collections.Generic;
public class Solution {
public string GetHint(string secret, string guess) {
var h = new Dictionary<char, int>();
foreach (var ch in secret) {
if (!h.ContainsKey(ch)) {
h[ch] = 0;
}
h[ch]++;
}
int bulls = 0;
int cows = 0;
int n = guess.Length;
var secretArray = secret.ToCharArray();
var guessArray = guess.ToCharArray();
for (int idx = 0; idx < n; idx++) {
var ch = guessArray[idx];
if (h.ContainsKey(ch)) {
if (ch == secretArray[idx]) {
bulls++;
if (h[ch] <= 0) {
cows--;
}
} else {
if (h[ch] > 0) {
cows++;
}
}
h[ch]--;
}
}
return $"{bulls}A{cows}B";
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public string GetHint(string secret, string guess) {
var h = new unordered_map<char, int>();
foreach (var ch in secret) {
if (!h.count(ch)) {
h[ch] = 0;
}
h[ch]++;
}
int bulls = 0;
int cows = 0;
int n = guess.size();
var secretArray = secret.ToCharArray();
var guessArray = guess.ToCharArray();
for (int idx = 0; idx < n; idx++) {
var ch = guessArray[idx];
if (h.count(ch)) {
if (ch == secretArray[idx]) {
bulls++;
if (h[ch] <= 0) {
cows--;
}
} else {
if (h[ch] > 0) {
cows++;
}
}
h[ch]--;
}
}
return $"{bulls}A{cows}B";
}
}Java solution
matched/originalimport java.util.HashMap;
import java.util.Map;
class Solution {
public String getHint(String secret, String guess) {
Map<Character, Integer> h = new HashMap<>();
for (char ch : secret.toCharArray()) {
h.put(ch, h.getOrDefault(ch, 0) + 1);
}
int bulls = 0;
int cows = 0;
int n = guess.length();
char[] secretArray = secret.toCharArray();
char[] guessArray = guess.toCharArray();
for (int idx = 0; idx < n; idx++) {
char ch = guessArray[idx];
if (h.containsKey(ch)) {
if (ch == secretArray[idx]) {
bulls++;
if (h.get(ch) <= 0) {
cows--;
}
} else {
if (h.get(ch) > 0) {
cows++;
}
}
h.put(ch, h.get(ch) - 1);
}
}
return bulls + "A" + cows + "B";
}
}JavaScript solution
matched/originalfunction getHint(secret, guess) {
const h = {};
for (const ch of secret) {
h[ch] = (h[ch] || 0) + 1;
}
let bulls = 0;
let cows = 0;
const n = guess.length;
const secretArray = [...secret];
const guessArray = [...guess];
for (let idx = 0; idx < n; idx++) {
const ch = guessArray[idx];
if (h[ch] !== undefined) {
if (ch === secretArray[idx]) {
bulls++;
if (h[ch] <= 0) {
cows--;
}
} else {
if (h[ch] > 0) {
cows++;
}
}
h[ch]--;
}
}
return `${bulls}A${cows}B`;
}Python solution
matched/originalclass Solution:
def getHint(self, secret: str, guess: str) -> str:
from collections import defaultdict
h = defaultdict(int)
for ch in secret:
h[ch] += 1
bulls = 0
cows = 0
n = len(guess)
secretArray = list(secret)
guessArray = list(guess)
for idx in range(n):
ch = guessArray[idx]
if ch in h:
if ch == secretArray[idx]:
bulls += 1
if h[ch] <= 0:
cows -= 1
else:
if h[ch] > 0:
cows += 1
h[ch] -= 1
return f"{bulls}A{cows}B"Go solution
matched/originalpackage main
import (
"fmt"
"strconv"
)
func getHint(secret string, guess string) string {
h := make(map[rune]int)
for _, ch := range secret {
h[ch]++
}
bulls, cows := 0, 0
n := len(guess)
secretArray := []rune(secret)
guessArray := []rune(guess)
for idx := 0; idx < n; idx++ {
ch := guessArray[idx]
if count, ok := h[ch]; ok {
if ch == secretArray[idx] {
bulls++
if count <= 0 {
cows--
}
} else {
if count > 0 {
cows++
}
}
h[ch]--
}
}
return strconv.Itoa(bulls) + "A" + strconv.Itoa(cows) + "B"
}Explanation
Algorithm
Инициализация счетчиков:
Инициализируйте количество быков и коров значениями ноль.
Создайте хеш-таблицу для хранения символов строки secret и их частот.
Обход строки 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.
Возврат результата:
Верните количество быков и коров в формате "xAyB".
😎