Флип и Зеркальные числа

Question

Я только что взял вопрос об интервью из Интернета и тренируюсь со Swift.

Вопрос состоит в следующем:

Учитывая ввод массива строк, проверьте,повернулся на 180 градусов, это «то же самое».

Например:

[1, 6, 0, 9, 1] => return true 
[1, 7, 1] => return false

Я предложил следующий подход, который я поставилзеркалирование чисел в словаре и проверка, не совпадают ли числа в данном массиве с числами в словаре.

Кажется, это работает с базовыми тестовыми примерами, но мне интересно, если я что-то упустил?

func checkRotation (nums : [Int]) -> Bool
{
    var dict = [Int : Int]()
    dict  = [0:0, 1:1, 2:5, 5:2, 6:9, 8:8, 9:6]

    for n in nums
    {
        guard let exist = dict[n] else
        {
            return false
        }
    }
    return true
}

Answer 1

Мой подход заключается в использовании prefix для ограничения набора данных и enumerated для одновременного перечисления по индексам и значениям.Добавьте lazy, чтобы не делать много копий массивов, а обрабатывать только то, что уместно.

extension Array where Element == Int {
    func isMirrored() -> Bool {
        let flipped = [0:0, 1:1, 2:5, 5:2, 6:9, 8:8, 9:6]

        return lazy                         // means we won't make 3 copies of arrays
            .prefix((count + 1) / 2)        // stops the enumeration at the midway point
            .enumerated()                   // enumerates over (index, value)
            .allSatisfy { (index, value) in // verify all elements meet the criteria below

            // make sure each reversed element matches it's flipped value
            // Note you don't have to explicitly check for nil, since
            // '==' works on Optional<Int>
                return flipped[value] == self[count - index - 1]
            }
    }
}

[1, 6, 0, 9, 1].isMirrored()
[1, 7, 1].isMirrored()

Answer 2

extension Collection where Element == Int {
    func isFlipMirrored() -> Bool {
        let mirrors = [0:0, 1:1, 6:9, 8:8, 9:6]
        return zip(self, self.reversed()) // Create tuples of each element and its opposite
            .allSatisfy {                 // Return whether all of them match the rule:
                mirrors[$0] == $1         // That the element matches its opposite's mirror
        }
    }
}

Это не так эффективно, как могло бы быть, но очень просто и точно.Он просто проверяет, что каждый элемент последовательности совпадает с зеркальными элементами в обратном порядке.

Может быть эффективнее проверить только первую половину элементов, но это довольно незначительная оптимизация, которая требуетдополнительные условия, так что я не уверен, будет ли это действительно быстрее для достаточно маленького N. Вам нужно выполнить профилирование, прежде чем усложнять код слишком сильно.

Конечно, просто потому, что он на самом деле не медленнее (т.е.Я не описал это, чтобы знать), это не означает, что интервьюер не будет оплакивать тот факт, что этот код выполняет избыточные проверки.Есть много недоразумений относительно производительности, и все они, кажется, обнаруживаются в вопросах интервьюИтак, давайте порадуем интервьюера и сверим только первую половину списка с последней половиной.

extension Collection where Element == Int {
    func isFlipMirrored() -> Bool {
        let mirrors = [0:0, 1:1, 6:9, 8:8, 9:6]

        // May test one more thing than we technically have to, but fewer conditionals
        let midpoint = count / 2 + 1

        return zip(self.prefix(midpoint),             // Create tuples of the left-half of the list,
                   self.reversed().prefix(midpoint))  //    and the right half
            .allSatisfy {                 // Return whether all of them match the rule:
                mirrors[$0] == $1         //     that the element matches its opposite's mirror
        }
    }
}

Answer 3

Чтобы узнать, является ли массив конвертируемым, вам необходимо

• пройти элементы до индекса N/2 (включая средний для массива нечетной длины)

• проверить, все ли элементы принадлежат словарю

• проверить, что dict[nums[i]] == nums[N-i-1]

Я не знаю Swift, но пример Pythonдолжен выглядеть очень близко:

def isconv(lst):
    dict = {0:0, 1:1, 2:5, 5:2, 6:9, 8:8, 9:6}
    N = len(lst)
    for i in range((N + 1) // 2):
        if (lst[i] not in dict) or (dict[lst[i]] != lst[N - 1 - i]):
            return False
    return True

print(isconv([1,6,0,9,1]))
print(isconv([5,5,2,2]))
print(isconv([1,6,0,6,1]))
print(isconv([1,4,1]))
>>True
>>True
>>False
>>False

Answer 4

У меня есть некоторые проблемы с вашим кодом, которые я аннотировал ниже:

func checkRotation /* Why the space here? */ (nums /* Why the space here? */ : [Int]) -> Bool
{ // Brackets like this aren't Swift's code style
    // Dict is a horrible name. I can see that it's a dictionary. What is it a dict *of*?!
    var dict = [Int : Int]() // Why is this a `var` variable, that's assigned an empty initial value
    dict  = [0:0, 1:1, 2:5, 5:2, 6:9, 8:8, 9:6] // only to be immediately overwritten?

    for n in nums // This should be a `contains(_:)` call, rather than explicit enumeration
    {
        // If you're not using a `contains(_:)` check, you should at least use a `where` clause on the for loop
        guard let exist = dict[n] else // "exist" is a bad variable name, and it's not even used. Replace this with a `dict[n] != nil` check.
        {
            return false
        }
    }
    return true
}

Вот как я мог бы написать его аналогичным способом:

func checkRotation(nums: [Int]) -> Bool {
    let mirroredDigits = [0:0, 1:1, 2:5, 5:2, 6:9, 8:8, 9:6]

    for n in nums where mirroredDigits[n] == nil {
        return false
    }
    return true
}

Answer 5

Можно попробовать

func checkRotation (nums : [Int]) -> Bool
{
    var dict = [0:0, 1:1, 2:5, 5:2, 6:9, 8:8, 9:6]
    return nums.filter{ dict[$0] != nil }.count == nums.count

}

Или

func checkRotation (nums : [Int]) -> Bool
{
    var dict = [0:0, 1:1, 2:5, 5:2, 6:9, 8:8, 9:6]
    return nums.compactMap{ dict[$0]}.count == nums.count

}