Pull to refresh
22
0
Павел Катунин @PavelKatunin

Программист

Send message

Решаем задачу нахождения длины наибольшей возрастающей подпоследовательности

Reading time 7 min
Views 56K

Содержание:

Последовательность Фибоначчи O (n)
Решение за O(n ^ 2)
Бинарный поиск O(log n)
Решение за O(n * log n)


Задача


"Найти длину самой большой возрастающей подпоследовательности в массиве."


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


На пальцах


Есть последовательность:


5, 10, 6, 12, 3, 24, 7, 8


Вот примеры подпоследовательностей:


10, 3, 8
5, 6, 3


А вот примеры возрастающих подпоследовательностей:


5, 6, 7, 8
3, 7, 8


А вот примеры возрастающих подпоследовательностей наибольшей длины:


5, 6, 12, 24
5, 6, 7, 8

Читать дальше →
Total votes 12: ↑12 and ↓0 +12
Comments 12

Swift 4 — слабые ссылки

Reading time 5 min
Views 16K
Вскоре после публикации исходного кода Swift, я написал статью о том как реализованы слабые ссылки. Время не стоит на месте и всё меняется, реализация слабых ссылок в Swift тоже. Сегодня я расскажу о новой реализации и сравню ее со старой. Спасибо Guillaume Lessard за идею для поста.

Старая реализация


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

В старой версии Swift объекты имели 2 счетчика ссылок: счетчик для сильных ссылок и счетчик для слабых. Когда счетчик сильных ссылок становится равен нулю, а слабых еще нет — объект уничтожается, но память не освобождается. Поэтому в памяти остается так называемый “зомби объект” на который ссылается слабая ссылка.

Когда слабая ссылка загружается, среда времени выполнения (runtime) проверяет является ли объект “зомби”. Если он “зомби” то runtime обнуляет слабую ссылку и уменьшает счетчик слабых ссылок на 1. Когда счетчик слабых ссылок достигает 0 — память освобождается (deallocated). Это означает, что полностью объект удаляется только тогда, когда все слабые ссылки на него обнуляются.

Мне нравилась простота этой реализации, но были у нее и недостатки:
Читать дальше →
Total votes 13: ↑10 and ↓3 +7
Comments 3

Emotiv Insight: первое знакомство с нейроинтерфейсом

Reading time 4 min
Views 20K


Emotiv Insight — это небольшой портативный нейроинтерфейс. Пару лет назад (в 2013 году) я проспонсировал этот проект на Kickstarter на сумму 330 $ (сейчас доступен от 299 $). Изначальная дата отправки устройств была назначена на март 2014 года, но получил я его только сегодня.
В этом посте я кратко опишу первое знакомство с Emotiv Insight, после будет опубликована статья с обзором SDK и ПО с точки зрения программиста.
Читать дальше →
Total votes 27: ↑25 and ↓2 +23
Comments 25

App Store style кастомизируемая кнопка загрузки

Reading time 1 min
Views 8.5K
github.com/PavelKatunin/DownloadButton

Недавно появилась потребность сделать кнопку загрузки для видео, сам этап загрузки был очень похож на стандартную кнопку загрузки приложений в Appstore, но только линия, отображающая уже загруженные данные, должна была быть снаружи. Я подумал, что такой контрол может быть удобен для отображения загрузки разных вещей и что он может пригодиться где-то еще — и вынес его в отдельный фреймворк и оформил в виде cocoapods. Опубликован под Apache 2.0.

Очень приветствуется использование, редактирование кода, заведение issue на github, предложения по новым фичам и отправка пул реквестов.
Читать дальше →
Total votes 17: ↑16 and ↓1 +15
Comments 3

Примеры тестовых заданий для iOS-разработчиков

Reading time 3 min
Views 46K
Я воспринимаю тестовые задания как хороший и адекватный метод отбора людей (для противников этого мнения есть голосовалка в конце поста), ведь работодатель может оценить конкретно то, что и будет делать сотрудник за своим рабочим местом. И поэтому зачастую с энтузиазмом принимаюсь за их выполнение, не смотря на то, что делать их приходится по ночам. К тому же, задания обычно небольшие и их можно расценивать как написание прототипов — а прототипы писать я тоже люблю. В общем опыт положительный, а положительный настрой — великое дело.



Здесь я хотел бы поделиться примерами тестовых заданий от разных работодателей: маленьких и больших, зарубежных и отечественных. Названия компаний приводиться не будут. Каждый пример задания будет сопровождаться ссылкой на репозиторий где лежит мой вариант решения. С кодом этим, можно делать все, что угодно: использовать в проектах, исправлять, посылать пул реквесты.
Читать дальше →
Total votes 17: ↑14 and ↓3 +11
Comments 16

Карты счастья

Reading time 1 min
Views 3.6K
История создания карт, основанных на эмоциях и восприятии людей.
Карт которые предоставляют возможность нахождения не только самого короткого или быстрого пути,
но и самого красивого, тихого или приятного.


Читать дальше →
Total votes 9: ↑6 and ↓3 +3
Comments 0

Objective-c блоки и c++ лямбды

Reading time 10 min
Views 25K
Надеюсь, что пост будет полезен людям которые знакомы с лямбдами C++, но хотят изучить блоки Objective-C и наоборот.
Здесь я постарался описать синтаксис замыканий, механизмы захвата контекста, управление памятью и взаимодествие лямбд и блоков между собой.
Во всех примерах использовался Apple LLVM Compiler 4.2 (Clang). Для приведенного Obj-C кода не используется ARC, т.к я придерживаюсь мнения, что необходимо знать как работает non-ARC код, чтобы понять как работает ARC.
Читать дальше →
Total votes 24: ↑23 and ↓1 +22
Comments 19

Information

Rating
Does not participate
Registered
Activity