✏️ Как найти два повторяющихся числа в массиве

Вам дан массив nums длиной n+2, содержащий числа от 0 до n-1. Два числа случайным образом появились в списке дважды. Нужно вернуть эти два числа. Например, для входа [0][1][1][2][3][3][4] ответ будет [1][3].

Для решения можно воспользоваться подсчётом количества появлений каждого числа.

Если встретили число во второй раз — записываем его в ответ:

public int[] GetSneakyNumbers(int[] nums)
{
    int n = nums.Length;
    int[] count = new int[101];
    int[] res = new int[2];
    int idx = 0;

    foreach (var num in nums)
    {
        count[num]++;
        if (count[num] == 2)
        {
            res[idx] = num;
            idx++;
        }
    }
    return res;
}

При помощи вспомогательного массива считаем, сколько раз встречается каждое число, и когда оно появилось второй раз — запоминаем.

➡️ Попробовать решить

🐸 Библиотека шарписта

#dotnet_challenge

✏️ Задачка с собеса

Дано целое число, нужно проверить, является ли оно полным квадратом.

Первый рефлекс новичка — взять квадратный корень и проверить, целое ли число:

(int)Math.Sqrt(num) * (int)Math.Sqrt(num) == num

Но на собесе после этого последует вопрос: «А можете без встроенной функции?» Вот тогда начинается интересное.

Вместо математики используем логику: если x * x = num, то x находится где-то между 1 и num. Сужаем диапазон поиска, пока не найдём точный ответ.

public bool IsPerfectSquare(int num)
{
    long left = 1;
    long right = num;
    
    while (left <= right)
    {
        long mid = (left + right) / 2;
        long square = mid * mid;
        
        if (square == num)
            return true;
        else if (square < num)
            left = mid + 1;
        else
            right = mid - 1;
    }
    
    return false;
}

Есть ещё метод Ньютона для поиска корня — он даже быстрее для больших чисел:

public bool IsPerfectSquare(int num)
{
    long x = num;
    
    while (x * x > num)
    {
        x = (x + num / x) / 2;
    }
    
    return x * x == num;
}

Главное: объясните почему вы выбрали именно этот подход, а не просто скопировали решение. На собесе вас оценивают не только по скорости, а по способности мыслить.

➡️ Попробовать решить

🐸Библиотека шарписта

#dotnet_challenge

📞 Комбинации букв телефонного номера: решение за один проход рекурсии

Задача — сгенерировать все возможные буквенные комбинации по цифрам телефона, где каждая цифра соответствует набору букв.

Идея решения: для каждой цифры берём соответствующие буквы и рекурсивно добавляем их к уже сформированным комбинациям.

Алгоритм:

1. Если входная строка пуста, возвращаем пустой результат

2. Используем массив с отображением цифр на наборы букв.

3. Рекурсивно проходим по цифрам, добавляя буквы к текущей комбинации

4. Когда достигнут конец строки, сохраняем сформированную комбинацию.

Решение:

public class Solution {
    private static readonly string[] map = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

    public IList<string> LetterCombinations(string digits) {
        var result = new List<string>();
        if(string.IsNullOrEmpty(digits))
            return result;
        Backtrack(digits, 0, new StringBuilder(), result);
        return result;
    }

    private void Backtrack(string digits, int index, StringBuilder current, List<string> result) {
        if(index == digits.Length) {
            result.Add(current.ToString());
            return;
        }

        string letters = map[digits[index] - '0'];
        foreach(char c in letters) {
            current.Append(c);
            Backtrack(digits, index + 1, current, result);
            current.Length--;
        }
    }
}

🔸 ML для старта в Data Science
🔸 Получить консультацию менеджера
🔸 Сайт Академии 🔸 Сайт Proglib

🐸Библиотека шарписта

#dotnet_challenge

✏️ Задача без подвоха

Дан массив длиной 2n в виде [x1,x2,xn,y1,y2,yn] нужно вернуть массив [x1,y1,x2,y2,xn,yn], то есть перемешать.

Идея решения

Логически делим массив на две половины по n элементов и в одном цикле по индексу i собираем ответ в новый массив result.
На каждой итерации кладем сначала элемент из первой половины nums[i] потом из второй nums[i+n].

Так мы проходим вход один раз время O(n), где n это половина массива.

Решение:

public class Solution
{
    public int[] Shuffle(int[] nums, int n)
    {
        int[] result = new int[2 * n];
        int index = 0;

        for (int i = 0; i < n; i++)
        {
            result[index++] = nums[i];
            result[index] = nums[i + n];
            index++;
        }

        return result;
    }
}

Ключевой момент в том что мы никогда не выходим за границы
первая половина идет по индексам от нуля до n минус один вторая от n до 2n минус один, а индекс в result просто сдвигается на два шага за итерацию.

➡️ Попробовать решить

🔹 Практический интенсив «Архитектуры и шаблоны проектирования»
🔹 Получить консультацию менеджера
🔹 Сайт Академии 🔹 Сайт Proglib

🐸Библиотека шарписта

#dotnet_challenge