Блог

У меня вопрос о кодировании. Я думал получить от вас несколько советов по нижеприведенному вопросу. Существует массив целых чисел. Эти номера массива указывают возраст человека. Напишите функцию, которая возвращает true, если есть человек, который ровно в два раза старше любого другого человека в списке, в противном случае функция возвращает false .

Ниже приведены ограничения.

• Возраст — это целое число со значениями в диапазоне от 0 до 50
• вы можете использовать только переменные числовых типов (без массива / среза / карты)
• должен иметь линейную временную сложность только с одним циклом
• вы не можете использовать операторы сложения, вычитания, умножения, деления или по модулю
• функция не может состоять более чем из 15 строк кода
• функция может не вызывать другие функции

Я мог бы придумать нижеприведенную функцию, предполагающую, что список отсортирован

/Функция / Go: предположение, список возрастов отсортирован.

 func isPersonTwiceOldAsOthers(person []Person) bool {
    if len(person) < 2 {
        fmt.Printf("Need minimum 2 person's age to continuen")
        return false
    }
    seen := make(map[int]bool, 15)
    for index, _ := range person {
        if seen[person[index].Age] {
            return true
        }
        seen[person[index].Age*2] = true
    }
    return false
}
  

Я ищу помощь в написании кода с использованием перечисленных выше ограничений. Любая помощь будет оценена.

Вы можете использовать побитовые операторы.

Поскольку возраст ограничен максимальными 50, существует только 25 различных пар, где одна является двойной другой: (0, 0), (1, 2), … (25, 50). Каждая из этих 25 возможностей может быть битом в (32-битном) целом числе.

Вы могли бы использовать одно целое число для обозначения бита, с которым вы столкнулись в возрасте от 0 до 25 (для первой части пары), а другое целое число для обозначения бита, с которым вы столкнулись с четным возрастом: там вы сначала уменьшили бы возраст вдвое, а затем установили соответствующий бит.

Когда эти два целых числа имеют общий набор битов, ответ положительный. Это логическое И .

Существует один особый случай: удвоение 0 равно 0, поэтому, если мы встретим один 0, тогда оба целых числа будут иметь свой первый бит, равный 1. Но требуется, чтобы был «другой» человек с двойным возрастом, поэтому это дало бы ложный положительный результат. Итак, решение состоит в том, чтобы обработать 0 по-разному и просто подсчитать, есть ли у вас два из них.

Вот реализация на JavaScript:

 function isPersonTwiceOldAsOthers(persons) {
    let smalls = 0, halves = 0, numZeroes = 0;
    for (let age of persons) {
        if (age == 0) numZeroes  ;
        if (age > 0 amp;amp; age <= 25) smalls |= (1 << age);
        if (age > 0 amp;amp; (age amp; 1) == 0) halves |= (1 << (age >> 1));
    }
    return numZeroes > 1 || (smalls amp; halves) != 0;
}

// Demo
let res;
res = isPersonTwiceOldAsOthers([4, 9, 34, 12, 18, 37]);
console.log(res); // true

res = isPersonTwiceOldAsOthers([4, 7, 34, 12, 18, 37]);
console.log(res); // false

res = isPersonTwiceOldAsOthers([4, 0, 34, 12, 18, 37]);
console.log(res); // false

res = isPersonTwiceOldAsOthers([4, 0, 34, 12, 18, 0]);
console.log(res); // true  

ПРИМЕЧАНИЕ: количество строк кода является субъективным в C-type и многих других языках.

В Go это может выглядеть так:

 func isPersonTwiceOldAsOthers(person []int) bool {
    var smalls, halves, numZeroes int;
    for _, age := range person {
        if age == 0 {
            numZeroes  ; 
        }
        if age > 0 amp;amp; age < 26 {
            smalls |= (1 << age);
        }
        if age > 0 amp;amp; (age amp; 1) == 0 {
            halves |= (1 << (age >> 1));
        }
    }
    return numZeroes > 1 || (smalls amp; halves) != 0;
}

func main() {
    res := isPersonTwiceOldAsOthers([]int{4, 9, 34, 12, 18, 37});
    println(res); // true
    
    res = isPersonTwiceOldAsOthers([]int{4, 7, 34, 12, 18, 37});
    println(res); // false

    res = isPersonTwiceOldAsOthers([]int{4, 0, 34, 12, 18, 37});
    println(res); // false

    res = isPersonTwiceOldAsOthers([]int{4, 0, 34, 12, 18, 0});
    println(res); // true  
}