Холиварофорум

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

[левел-ап][айти]

Я снова начал литкодить 

Начал я чуть раньше, но руки дошли только сейчас.
Я решал задачи несколько дней подряд, потом переключился на свой проект.
Но сегодня открыл задачу и попробовал решить по памяти, и вообще по тому, насколько я её понял. И получилось!

Массивы, два указателя, лёгкие уровень: по 20 минут на первый раз и на сегодня

▼Дан массив, элементы отсортированы не по убыванию, т.е. возможны повторения.. Удалить повторяющиеся элементы и вернуть количество уникальных элементов, k. Первые k элементов получившегося массива должны быть отсортированы⬍

1 <= nums.length <= 3 * 104
-100 <= nums[j] <= 100

Примеры:
1)
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]

2)
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]

Идея: два указателя, медленный и быстрый. Число k делаем изначально равным 1 - хоть один уникальный элемент, да есть.
Медленный стоит на нынешнем последнем уникальном элементе (начинаем с нулевого элемента), быстрый ищет следующий уникальный элемент, отличный от того, на котором стоит медленный.
Когда быстрый находит его, этот элемент помещается в позицию после элемента, на котором стоит медленный указатель.
Оба указателя перемещаются на одну позицию вперёд. k увеличивается на единицу.
Так делаем до тех пор, пока быстрый указатель не достигнет конца массива.
Возвращаем k, а сам массив уже изменён in-place.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        len_nums = len(nums)
        k = 1
        if len_nums == 1:
            return k
        slow, fast = 0, 1
        while slow <= fast and fast < len_nums:
            if nums[fast] != nums[slow]:
                nums[slow + 1] = nums[fast]
                slow += 1
                fast += 1
                k += 1
            else:
                fast += 1
        return k

Вот вариант проще и лучше:

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        len_nums = len(nums)
        i = 0
        for j in range(1, len_nums):
            if nums[i] != nums[j]:
                i += 1
                nums[i] = nums[j]
        return i + 1

Но по большому счёту надо просто все уникальные элементы переместить в начало массива и вернуть k.
Задача, имхо, не слишком хорошо сформулирована: например, не надо вставлять "_" в массив 

[дыбр]

Снова начались дожди и похолодало. На вершинах гор лежит снег, а сами горы стали тёмно-зелёными.
С одной стороны я люблю дождь и его меланхолию, с другой - не люблю, когда при этом слишком холодно. Ну разве только для сидения дома с игрой или книгой такая погода хороша.
Вышел в обед погулять, было солнце, а потом плотной косой стеной пошёл ливень.

анон-левел-апер