Недавно я прошел испытание кода HackerRank под названием Шерлок и действительная строка. Это интересная задача, и я работал над ее решением с JavaScript. В то время как в моем решении используется Object literal (хеш-карта), Set и два for loop для мускулов, мозг, безусловно, исходит из концептуальной логики, представленной условными выражениями. Элементарно!
Шерлок и верная строка
Постановка задачи:
В постановке задачи Шерлок представлен как главный инспектор strings. Шерлок должен проверить каждый string функцией. Данный string считается действительным, если:
- все символы имеют одинаковую частоту (встречаются одинаковое количество раз)
- можно удалить одиночный символ, чтобы получить
string, в котором все символы имеют одинаковую частоту
Например:
const s = 'abcc'
// this string is valid
// a single (1) deletion of character 'c'
// would produce a string of which each
// character has the same frequency
// {'a': 1, 'b': 1, 'c': 1}
const s = 'aabbcc'
// this string is valid
// each character has the same frequency:
// {'a': 2, 'b': 2, 'c': 2}
const s = 'aaabc'
// this string is NOT valid
// a single (1) deletion of character 'a'
// would produce a string of which each
// character does NOT have the same frequency
// {'a': 2, 'b': 1, 'c': 1}
Описание функции:
Функция isValid() должна возвращать string YES, если ввод string действителен, в противном случае она должна возвращать string NO.
Входные параметры:
s:string, состоящий из букв нижнего регистра (ascii[a–z])
Решение:
Во-первых, необходимо объявить функцию. Он примет единственный аргумент string, представленный здесь как s. По умолчанию будет возвращена строка NO:
function isValid(s) {
return 'NO'
}
Затем необходимо записать частоту каждого символа ввода string, чтобы была ссылка для проверки на соответствие требованиям. Правильный инструмент для работы - это хеш-карта. Создается экземпляр Object literal, присвоенный переменной cMap (c для символа). Затем for loop используется для перебора символов ввода string и загрузки cMap пар ключ-значение, представляющих каждый символ и его частоту. Это делается с помощью условного оператора, чтобы оценить, содержит ли cMap символ, оцениваемый на каждой итерации. Если это так, его соответствующее значение увеличивается на 1. В противном случае соответствующее значение устанавливается на 1.
function isValid(s) {
const cMap = {}
for (let c of s) {
cMap[c] ? cMap[c]++ : cMap[c] = 1
}
console.log(cMap)
return 'NO'
}
////////////////////////////////////////////////////////////////////
const s = 'abcdefghhgfedecba'
isValid(s)
//=> cMap {a: 2, b: 2, c: 2, d: 2, e: 3, f: 2, g: 2, h: 2}
Далее, требования к достоверности диктуют, что частота каждого символа должна быть одинаковой, или должно быть одно исключение, когда одиночное удаление дает желаемый результат. . Важная информация для оценки - это частоты. Хэш-карта была очень полезна для сбора и подсчета, но теперь значения - частоты - можно извлекать и использовать самостоятельно. Правильный инструмент для работы - это Set. Создается новый Set, которому присваивается Array значений из cMap, которые компилируются путем передачи cMap методу Object.values(). Set присваивается переменной freqs (для частот). Set создает уникальный набор значений. В этом случае freqs будет содержать только по одному символу каждой частоты, даже если несколько символов имеют одинаковую частоту. Это будет полезно для этой функции, о которой я расскажу в следующем разделе.
function isValid(s) {
const cMap = {}
for (let c of s) {
cMap[c] ? cMap[c]++ : cMap[c] = 1
}
const freqs = new Set(Object.values(cMap))
console.log(freqs)
return 'NO'
}
////////////////////////////////////////////////////////////////////
const s = 'abcdefghhgfedecba'
isValid(s)
//=> Set {2, 3}
Далее, можно применить некоторую логику. Требования к достоверности допускают два сценария. Первый сценарий состоит в том, что каждый символ в строке input имеет одинаковую частоту. Если это произойдет, значение, связанное с каждым символом в cMap, будет таким же. Затем, когда Set будет построен, он будет включать единственное число: единственную текущую частоту. Во втором сценарии существует одно исключение, в котором одиночный символ может быть удален для получения действительного string. Это будет означать, что есть вторая частота, и ее можно уменьшить на 1, чтобы равняться первой частоте. Если имеется более двух частот, т. Е. в cMap более двух значений, потребуется более одного удаления для получения действительного string, которое не соответствует требования к действительности.
Следовательно, можно определить, что допустимы два случая. Мы можем проверить эти случаи с помощью условных выражений: двух if операторов. Каждый оператор if проверяет свойство .size freqs. Если размер freqs равен 1, что указывает на то, что каждый символ ввода string имеет одинаковую частоту, ввод string считается допустимым, и функция может вернуть YES и завершить работу. Если размер freqs равен 2, что указывает на наличие двух частотных символов, будет выполнена дополнительная логика для проверки ввода string. Если размер freqs больше, чем 2, будет выполнен возврат по умолчанию NO в конце функции.
function isValid(s) {
const cMap = {}
for (let c of s) {
cMap[c] ? cMap[c]++ : cMap[c] = 1
}
const freqs = new Set(Object.values(cMap))
if (freqs.size === 1) return 'YES'
if (freqs.size === 2) {
// additional validation logic
}
return 'NO'
}
Далее необходимо реализовать логику для второго случая. Если есть две частоты символов, можно определить, что есть одно исключение и есть два условия действительности.
Первое условие - если значение одиночного исключения меньше, чем значение основной частоты, и оно равно 1. Например:
const s = 'aabbc'
//=> cMap {'a': 2, 'b': 2, 'c': 1}
//=> freqs {2, 1} *note: a Set is constructed with insertion order
// the exception is the lesser value of the two frequencies
// it is equal to 1, allowing a single deletion to meet
// the validity requirements
Второе условие - если значение одиночного исключения больше, чем значение основной частоты, и оно равно значению основной частоты, увеличенному на 1, т.е. значение исключения минус 1 равно значению основной частоты. Например:
const s = 'aabbbcc'
//=> cMap {'a': 2, 'b': 3, 'c': 2}
//=> freqs {2, 3}
// the exception is the greater value of the two frequencies
// it is equal to the value of the majority frequency plus 1
// allowing a single deletion to meet the validity requirements
В случае наличия двух частот необходимо выполнить две необходимые операции.
- количество символов для каждой частоты необходимо определить
- необходимо определить разницу между двумя частотами
Минимальное - меньшее значение - и максимальное - большее значение - необходимо определить для каждого числа в freqs. Затем, в свою очередь, минимум и максимум можно использовать для вычисления разницы между собой и количеством символов в cMap, которые соответствуют каждой частоте. Во-первых, минимум и максимум можно вычислить с помощью функций Math.min() и Math.max(). Значения из freqs будут извлечены и переданы каждой функции с помощью оператора распространения (…), в каждом случае присваивая соответствующий номер переменным min и max.
function isValid(s) {
const cMap = {}
for (let c of s) {
cMap[c] ? cMap[c]++ : cMap[c] = 1
}
const freqs = new Set(Object.values(cMap))
if (freqs.size === 1) return 'YES'
if (freqs.size === 2) {
const max = Math.max(...freqs)
const min = Math.min(...freqs)
console.log('max =', max)
console.log('min =', min)
}
return 'NO'
}
////////////////////////////////////////////////////////////////////
const s = 'abcdefghhgfedecba'
isValid(s)
//=> max = 3
//=> min = 2
Затем необходимо определить количество символов в cMap, которые соответствуют каждой частоте, т.е., сколько раз встречается каждая из двух частот. Это можно определить, перебирая cMap и увеличивая счетчик для каждой частоты по мере ее появления. Два счетчика могут быть инициализированы значением 0 и назначены двум переменным: maxCt (Ct для счетчика) и minCt. Затем for loop можно использовать с двумя операторами if для соответствующего увеличения счетчиков. Если значение, связанное с ключом, оцениваемым на каждой итерации, равно max, то maxCt увеличивается на 1. Если он равен min, то minCt увеличивается на 1.
function isValid(s) {
const cMap = {}
for (let c of s) {
cMap[c] ? cMap[c]++ : cMap[c] = 1
}
const freqs = new Set(Object.values(cMap))
if (freqs.size === 1) return 'YES'
if (freqs.size === 2) {
const max = Math.max(...freqs)
const min = Math.min(...freqs)
let maxCt = 0
let minCt = 0
for (let c in cMap) {
if (cMap[c] === max) maxCt++
if (cMap[c] === min) minCt++
}
console.log('maxCt =', maxCt)
console.log('minCt =', minCt)
}
return 'NO'
}
////////////////////////////////////////////////////////////////////
const s = 'abcdefghhgfedecba'
isValid(s)
//=> maxCt = 1
//=> minCt = 7
Далее, последний шаг - использовать значения, определенные для max, min, maxCt и minCt, чтобы определить действительность ввода string на основе успешного выполнения одного из двух условий для второго случая - двух существующих частоты:
- значение одиночного исключения меньше, чем значение основной частоты, и оно равно
1 - значение одиночного исключения больше, чем значение основной частоты, и равно значению основной частоты, увеличенному на
1
Оператор if может использоваться со сложным условием, и если оно оценивается как true, вернуть YES и завершить функцию. Сложное условие строится как два набора сравниваемых выражений, которые сами сравниваются с оператором Logical OR (||), что означает, что только один сравниваемый набор должен оцениваться как true, чтобы установить оценку оператора if на true. Первый набор сравниваемых выражений будет использовать оператор Logical AND (&&), чтобы оценить, равно ли minCt 1 и min равно 1, т.е. есть одно исключение частоты, которое меньше, чем частота большинства и его можно устранить одним удалением. Второй набор сравниваемых выражений будет использовать оператор Logical AND, чтобы оценить, равно ли maxCt 1 и max равно значению основной частоты, увеличенному на 1, т.е. есть одно исключение частоты, которое больше чем мажоритарная частота, и ее можно приравнять к мажоритарной частоте, вычитая 1, одно удаление.
Полная функция:
function isValid(s) {
const cMap = {}
for (let c of s) {
cMap[c] ? cMap[c]++ : cMap[c] = 1
}
const freqs = new Set(Object.values(cMap))
if (freqs.size === 1) return 'YES'
if (freqs.size === 2) {
const max = Math.max(...freqs)
const min = Math.min(...freqs)
let maxCt = 0
let minCt = 0
for (let c in cMap) {
if (cMap[c] === max) maxCt++
if (cMap[c] === min) minCt++
}
if (
(minCt === 1 && min === 1) ||
(maxCt === 1 && max === min + 1)
) return 'YES'
}
return 'NO'
}
////////////////////////////////////////////////////////////////////
const s = 'abcdefghhgfedecba'
isValid(s)
//=> YES
////////////////////////////////////////////////////////////////////
const s = 'aaaaabc'
isValid(s)
//=> NO
Проблема требует хорошего логического планирования для подготовки необходимых значений для оценки и определения правильного порядка условных выражений. Вышеупомянутой функции требуется несколько встроенных модулей: Set, Object.values(), Math.max() и Math.min(), но из-за ограничения 26 символьного алфавита и максимального Set размера 26 - относительно небольшое число - их производительность не дорогая. Есть два не вложенных цикла, один из которых оценивается, только если в Set есть две частоты. Это говорит о том, что временная сложность функции линейна: O(n), и, учитывая, что хранимые данные представляют собой одну хеш-карту и одну Set, сложность пространства также составляет O(n). Надеюсь, вам понравилась эта статья, представленная в ней проблема кода и решение, которое я изложил. Удачного кодирования.
Github.com/dangrammer
connected.com/in/danieljromans
danromans.com
