Как стать автором
Обновить
22
0
Павел Катунин @PavelKatunin

Программист

Отправить сообщение

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

Время на прочтение 7 мин
Количество просмотров 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

Читать дальше →
Всего голосов 12: ↑12 и ↓0 +12
Комментарии 12

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

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

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


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

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

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

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

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

Время на прочтение 4 мин
Количество просмотров 20K


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

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

Время на прочтение 1 мин
Количество просмотров 8.5K
github.com/PavelKatunin/DownloadButton

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

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

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

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



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

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

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


Читать дальше →
Всего голосов 9: ↑6 и ↓3 +3
Комментарии 0

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

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

Информация

В рейтинге
Не участвует
Зарегистрирован
Активность