Swift | LeetCode
前往频道在 Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
显示更多
网络:1 339
订阅者
无数据24 小时
-47 天
-2530 天
帖子存档
1 339
GitHub теперь в Telegram!
Более 7000+ репозиториев с исходным кодом нейросетей, ботов, сайтов и других интересных проектов для разработчиков:
Всё разбито по #хештегам. Подписывайтесь: @GitHub
1 339
#medium
Задача: 370. Range Addition
Дано целое число length и массив updates, где updates[i] = [startIdxi, endIdxi, inci].
У вас есть массив arr длины length, заполненный нулями. Вам нужно применить некоторые операции к arr. В i-й операции следует увеличить все элементы arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] на inci.
Верните arr после применения всех обновлений.
Пример:
Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]] Output: [-2,0,3,5,3]👨💻 Алгоритм: 1⃣Для каждого обновления (start, end, val) выполните две операции: Увеличьте значение в позиции start на val: arr[start] = arr[start] + val. Уменьшите значение в позиции end + 1 на val: arr[end + 1] = arr[end + 1] - val. 2⃣Примените конечное преобразование: вычислите кумулятивную сумму всего массива (с индексами, начиная с 0). 3⃣Верните обновленный массив arr. 😎 Решение:
func getModifiedArray(_ length: Int, _ updates: [[Int]]) -> [Int] {
var result = [Int](repeating: 0, count: length)
for update in updates {
let start = update[0], end = update[1], val = update[2]
result[start] += val
if end + 1 < length {
result[end + 1] -= val
}
}
for i in 1..<length {
result[i] += result[i - 1]
}
return result
}1 339
#medium
Задача: 369. Plus One Linked List
Дано неотрицательное целое число, представленное в виде связного списка цифр. Добавьте к этому числу единицу.
Цифры хранятся таким образом, что самая значимая цифра находится в начале списка.
Пример:
Input: head = [1,2,3] Output: [1,2,4]👨💻 Алгоритм: 1⃣Инициализируйте стражевой узел как ListNode(0) и установите его как новую голову: sentinel.next = head. Найдите крайний правый элемент, не равный девяти. 2⃣Увеличьте найденную цифру на единицу и установите все следующие девятки в ноль. 3⃣Верните sentinel, если его значение было установлено на 1, иначе верните head (sentinel.next). 😎 Решение:
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int) { self.val = val; self.next = nil }
}
class Solution {
func plusOne(_ head: ListNode?) -> ListNode? {
let sentinel = ListNode(0)
sentinel.next = head
var notNine = sentinel
var current = head
while current != nil {
if current!.val != 9 {
notNine = current!
}
current = current!.next
}
notNine.val += 1
notNine = notNine.next
while notNine != nil {
notNine!.val = 0
notNine = notNine!.next
}
return sentinel.val == 0 ? sentinel.next : sentinel
}
}1 339
VPN в России — умер. Роскомнадзор инвестирует 60 000 000 000 рублей на новую систему блокировки.
Youtube полностью заблокируют зимой. Google сворачивает ВСЕ свои сервисы. А Windows и Apple ждут удобного момента.
Изоляция ждёт всех, кто не заботится о своей свободе и кибербезопасности. Чтобы такого не было с вами — читайте канал IT ВЕДОМСТВО.
Это главный техноканал Телеграма, где постят инсайдейрскую информацию, лайфхаки, гайды по обходу блокировок без VPN, фишки для айтишников - все самое полезное там.
Подписывайтесь, чтобы не потерять: https://t.me/+wVax9n-CeFRmNzgy
1 339
#hard
Задача: 460. LFU Cache
Спроектируйте и реализуйте структуру данных для кеша с наименьшим количеством использования (Least Frequently Used, LFU).
Реализуйте класс LFUCache:
LFUCache(int capacity): Инициализирует объект с указанной вместимостью структуры данных.
int get(int key): Возвращает значение ключа, если ключ существует в кеше. В противном случае возвращает -1.
void put(int key, int value): Обновляет значение ключа, если он уже присутствует, или вставляет ключ, если его еще нет. Когда кеш достигает своей вместимости, он должен аннулировать и удалить ключ, используемый наименее часто, перед вставкой нового элемента. В этой задаче, если имеется несколько ключей с одинаковой частотой использования, аннулируется наименее недавно использованный ключ.
Чтобы определить наименее часто используемый ключ, для каждого ключа в кеше поддерживается счетчик использования. Ключ с наименьшим счетчиком использования является наименее часто используемым ключом.
Когда ключ впервые вставляется в кеш, его счетчик использования устанавливается на 1 (из-за операции put). Счетчик использования для ключа в кеше увеличивается при вызове операции get или put для этого ключа.
Функции get и put должны иметь среднюю временную сложность O(1).
Пример:
Input ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]] Output [null, null, null, 1, null, -1, 3, null, -1, 3, 4]👨💻 Алгоритм: 1⃣insert(int key, int frequency, int value): Вставить пару частота-значение в cache с заданным ключом. Получить LinkedHashSet, соответствующий данной частоте (по умолчанию пустой Set), и вставить в него ключ. 2⃣int get(int key): Если ключа нет в кеше, вернуть -1. Получить частоту и значение из кеша. Удалить ключ из LinkedHashSet, связанного с частотой. Если minf == frequency и LinkedHashSet пуст, увеличить minf на 1 и удалить запись частоты из frequencies. Вызвать insert(key, frequency + 1, value). Вернуть значение. 3⃣void put(int key, int value): Если capacity <= 0, выйти. Если ключ существует, обновить значение и вызвать get(key). Если размер кеша равен capacity, удалить первый элемент из LinkedHashSet, связанного с minf, и из кеша. Установить minf в 1. Вызвать insert(key, 1, value). 😎 Решение:
class LFUCache {
var frequencies = [Int: LinkedList<(key: Int, value: Int)>]()
var cache = [Int: (frequency: Int, node: LinkedListNode<(key: Int, value: Int)>.Node)]()
var capacity: Int
var minf: Int
init(_ capacity: Int) {
self.capacity = capacity
self.minf = 0
}
private func insert(_ key: Int, _ frequency: Int, _ value: Int) {
if frequencies[frequency] == nil {
frequencies[frequency] = LinkedList()
}
frequencies[frequency]?.append((key, value))
cache[key] = (frequency, frequencies[frequency]!.tail!)
}
func get(_ key: Int) -> Int {
guard let entry = cache[key] else { return -1 }
let (frequency, node) = entry
frequencies[frequency]?.remove(node)
if frequencies[frequency]?.isEmpty ?? false {
frequencies[frequency] = nil
if minf == frequency { minf += 1 }
}
insert(key, frequency + 1, node.value.value)
return node.value.value
}
func put(_ key: Int, _ value: Int) {
if capacity <= 0 { return }
if let entry = cache[key] {
entry.node.value.value = value
_ = get(key)
return
}
if cache.count == capacity {
let (k, _) = frequencies[minf]!.head!.value
cache.removeValue(forKey: k)
frequencies[minf]?.remove(frequencies[minf]!.head!)
if frequencies[minf]?.isEmpty ?? false { frequencies[minf] = nil }
}
minf = 1
insert(key, 1, value)
}
}1 339
#easy
Задача: 234. Palindrome Linked List
Дан головной элемент односвязного списка. Верните true, если список является палиндромом, и false в противном случае.
Пример:
Input: head = [1,2,2,1] Output: true👨💻 Алгоритм: 1⃣Копирование односвязного списка в массив: Итеративно пройдите по односвязному списку, добавляя каждое значение в массив. Для этого используйте переменную currentNode, указывающую на текущий узел. На каждой итерации добавляйте currentNode.val в массив и обновляйте currentNode, чтобы он указывал на currentNode.next. Остановите цикл, когда currentNode укажет на null. 2⃣Проверка массива на палиндром: Используйте метод с двумя указателями для проверки массива на палиндром. Разместите один указатель в начале массива, а другой в конце. На каждом шаге проверяйте, равны ли значения, на которые указывают указатели, и перемещайте указатели к центру, пока они не встретятся. 3⃣Сравнение значений: Помните, что необходимо сравнивать значения узлов, а не сами узлы. Используйте node_1.val == node_2.val для сравнения значений узлов. Сравнение узлов как объектов node_1 == node_2 не даст ожидаемого результата. 😎 Решение:
class Solution {
func isPalindrome(_ head: ListNode?) -> Bool {
var vals: [Int] = []
var currentNode = head
while currentNode != nil {
vals.append(currentNode!.val)
currentNode = currentNode!.next
}
var front = 0
var back = vals.count - 1
while front < back {
if vals[front] != vals[back] {
return false
}
front += 1
back -= 1
}
return true
}
}1 339
Все надоело и пропал интерес, чувствуешь себя амебой и хочется только залипать в телефоне. Бывает?
Психолог взрослого человека - канал для айтишников, у которых периодически опускаются руки и отключается мозг, ибо переработки и постоянная тревожность не приводят к другим исходам.
✔️ Как научиться отвлекаться от работы и отдыхать?
✔️ Как совместить кучу рабочих задач и время с семьей?
✔️ Как справиться с прокрастинацией?
✔️ Как не растерять запал, даже если начальник и коллеги 💩 и кажется, что ничего не выходит?
Подписывайтесь на канал @vadimpetrov_psy и научитесь работать без упахивания, выгорания и ущерба для личной жизни!
👨🏻💻 Псс. Заходите в закреп канала - там много полезного.
https://t.me/+Bz2LiDjD8_s3ZTNi
1 339
#medium
Задача: 331. Verify Preorder Serialization of a Binary Tree
Один из способов сериализации бинарного дерева — использование обхода в порядке предварительного прохода (preorder traversal). Когда мы встречаем ненулевой узел, мы записываем значение узла. Если это нулевой узел, мы записываем его с использованием специального значения, такого как '#'.
Дана строка, содержащая значения, разделенные запятыми, представляющие предварительный обход дерева (preorder). Верните true, если это правильная сериализация предварительного обхода бинарного дерева.
Гарантируется, что каждое значение в строке, разделенное запятыми, должно быть либо целым числом, либо символом '#', представляющим нулевой указатель.
Вы можете предположить, что формат ввода всегда действителен.
Например, он никогда не может содержать две последовательные запятые, такие как "1,,3".
Примечание: Вам не разрешено восстанавливать дерево.
Пример:
Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#" Output: true👨💻 Алгоритм: 1⃣Инициализация и разбор строки: Инициализируйте переменную slots значением 1, представляющую количество доступных слотов. Разделите строку по запятым, чтобы получить массив элементов. 2⃣Итерация по элементам и проверка: Перебирайте каждый элемент массива. Для каждого элемента уменьшайте количество слотов на 1. Если количество слотов становится отрицательным, верните false, так как это означает неправильную сериализацию. Если элемент не равен '#', увеличьте количество слотов на 2, так как непустой узел создает два новых слота. 3⃣Проверка завершения: После итерации по всем элементам проверьте, равно ли количество слотов 0. Если да, верните true, в противном случае false. 😎 Решение:
class Solution {
func isValidSerialization(_ preorder: String) -> Bool {
var slots = 1
let nodes = preorder.split(separator: ",")
for node in nodes {
slots -= 1
if slots < 0 {
return false
}
if node != "#" {
slots += 2
}
}
return slots == 0
}
}1 339
#hard
Задача: 233. Number of Digit One
Дано целое число n, посчитайте общее количество единиц, встречающихся во всех неотрицательных числах, меньших или равных n.
Пример:
Input: n = 13 Output: 6👨💻 Алгоритм: 1⃣Итерация по степеням 10: Итеративно увеличивайте значение i от 1 до n, увеличивая i в 10 раз на каждом шаге. Это позволяет анализировать каждую цифру числа n. 2⃣Подсчет групповых единиц: Для каждой итерации добавляйте (n / (i * 10)) * i к счетчику countr, что представляет собой количество единиц, встречающихся в группах размера i после каждого интервала (i * 10). 3⃣Добавление дополнительных единиц: Для каждой итерации добавляйте min(max((n % (i * 10)) - i + 1, 0), i) к счетчику countr, что представляет собой дополнительные единицы, зависящие от цифры на позиции i. 😎 Решение:
func countDigitOne(_ n: Int) -> Int {
var countr = 0
var i: Int64 = 1
while i <= n {
let divider = i * 10
countr += (n / Int(divider)) * Int(i) + min(max(n % Int(divider) - Int(i) + 1, 0), Int(i))
i *= 10
}
return countr
}1 339
Зачем мне английский, я и без него могу прогать.
Писать код можешь, но на рынке ты будешь стоить гораздо меньше.
Статистика заставляет задуматься:
IT-шников, знающих английский, по РФ 70%. Теперь ответь себе на вопрос: хочется ли тебе входить в 30% людей с низким зп. Сейчас конкуренция огромная и нужно соответствовать.
Подпишись на канал Hello World. Все уникальные рубрики в одном месте: знакомься со сленгом программиста, решай тесты и повторяй базовые правила. Твой уровень не важен, контент адаптирован под всех. Изучай и повторяй!
1 339
#easy
Задача: 232. Implement Queue using Stacks
Реализуйте очередь (FIFO) с использованием только двух стеков. Реализованная очередь должна поддерживать все функции обычной очереди (push, peek, pop и empty).
Реализуйте класс MyQueue:
void push(int x) добавляет элемент x в конец очереди.
int pop() удаляет элемент из начала очереди и возвращает его.
int peek() возвращает элемент из начала очереди.
boolean empty() возвращает true, если очередь пуста, и false в противном случае.
Пример:
Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]
Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return falseclass MyQueue {
private var s1: [Int] = []
private var s2: [Int] = []
private var front: Int = 0
func push(_ x: Int) {
if s1.isEmpty {
front = x
}
while !s1.isEmpty {
s2.append(s1.removeLast())
}
s2.append(x)
while !s2.isEmpty {
s1.append(s2.removeLast())
}
}
func pop() -> Int {
let res = s1.removeLast()
if !s1.isEmpty {
front = s1.last!
}
return res
}
func empty() -> Bool {
return s1.isEmpty
}
func peek() -> Int {
return front
}
}1 339
#easy
Задача: 476. Number Complement
Дополнение целого числа — это число, которое получается при замене всех 0 на 1 и всех 1 на 0 в его двоичном представлении.
Например, целое число 5 в двоичной системе — "101", и его дополнение — "010", что соответствует целому числу 2. Дано целое число num, верните его дополнение.
Пример:
Input: num = 5 Output: 2 Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.👨💻 Алгоритм: 1⃣Вычислите длину в битах входного числа: l=⌊log 2 (num)⌋+1. 2⃣Постройте битовую маску из 1-битов длины l: bitmask=(1≪l)−1. 3⃣Верните результат операции XOR числа и битовой маски: num⊕bitmask num⊕bitmask. 😎 Решение:
class Solution {
func findComplement(_ num: Int) -> Int {
var bitmask = num
bitmask |= (bitmask >> 1)
bitmask |= (bitmask >> 2)
bitmask |= (bitmask >> 4)
bitmask |= (bitmask >> 8)
bitmask |= (bitmask >> 16)
return bitmask ^ num
}
}1 339
#easy
Задача: 231. Power of Two
Дано целое число n, верните true, если оно является степенью двойки. В противном случае верните false.
Целое число n является степенью двойки, если существует целое число x, такое что n == 2^x.
Пример:
Input: n = 1 Output: true Explanation: 2^0 = 1👨💻 Алгоритм: 1⃣Проверка на ноль: Если n равно нулю, верните false, так как ноль не является степенью двойки. 2⃣Преобразование к длинному типу: Преобразуйте n к типу long, чтобы избежать переполнения при выполнении побитовых операций. 3⃣Побитовая проверка: Используйте побитовую операцию, чтобы проверить, является ли число степенью двойки. Число является степенью двойки, если результат выражения (x & (-x)) равен x. 😎 Решение:
class Solution {
func isPowerOfTwo(_ n: Int) -> Bool {
if n == 0 { return false }
let x = Int64(n)
return (x & -x) == x
}
}1 339
#hard
Задача: 330. Patching Array
Дан отсортированный массив целых чисел nums и целое число n. Добавьте/дополните элементы в массив таким образом, чтобы любое число в диапазоне [1, n] включительно могло быть сформировано как сумма некоторых элементов массива.
Верните минимальное количество дополнений, необходимых для этого.
Пример:
Input: nums = [1,3], n = 6 Output: 1 Explanation: Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4. Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3]. Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6]. So we only need 1 patch.👨💻 Алгоритм: 1⃣Инициализация переменных: Создайте переменную miss, представляющую наименьшее пропущенное число, которое еще не покрыто, и установите ее значение на 1. Создайте переменную patches для подсчета необходимых дополнений и переменную i для итерации по массиву nums. 2⃣Основной цикл: Используйте цикл while, который будет выполняться до тех пор, пока miss не станет больше n. Внутри цикла проверьте, покрывает ли текущий элемент nums[i] значение miss. Если да, добавьте nums[i] к miss и увеличьте i. Если нет, добавьте значение miss к самому себе (это означает добавление нового элемента в массив) и увеличьте счетчик patches. 3⃣Возврат результата: После завершения цикла верните значение patches, которое представляет минимальное количество необходимых дополнений. 😎 Решение:
class Solution {
func minPatches(_ nums: [Int], _ n: Int) -> Int {
var patches = 0
var i = 0
var miss: Int64 = 1
while miss <= n {
if i < nums.count && nums[i] <= miss {
miss += Int64(nums[i])
i += 1
} else {
miss += miss
patches += 1
}
}
return patches
}
}1 339
👀 Вы все еще не слышали про канал Путь в IT?
Автор (Илья) на своем примере показывает, через что приходится проходить начинающему специалисту.
😉 Почему такого контента вы еще не видели?
Илья создает уникальные видео, совмещая тренировки, бытовые моменты и рабочий процесс. Сейчас начинающий специалист поступил в вуз и переехал в другой город, поэтому контент будет еще интересней. Если хочешь узнать админа лучше, зайди в закреп его канала.
👋 Подписывайся, данный канал будет разжигать в тебе огонь.
Путь в IT
1 339
#medium
Задача: 230. Kth Smallest Element in a BST
Дан корень бинарного дерева поиска и целое число k. Верните k-ое по величине значение (нумерация с 1) среди всех значений узлов в дереве.
Пример:
Input: root = [3,1,4,null,2], k = 1 Output: 1👨💻 Алгоритм: 1⃣Инициализация стека и обход в глубину: Инициализируйте стек для хранения узлов дерева. Начните обход дерева в глубину, начиная с корня, и перемещайтесь влево, добавляя каждый узел в стек, пока не достигнете самого левого узла. 2⃣Извлечение узлов и проверка: Когда достигнете самого левого узла, извлеките узел из стека и уменьшите значение k на 1. Если k становится равным нулю, верните значение текущего узла, так как это и есть k-ое по величине значение. 3⃣Переход к правому поддереву: Если k не равен нулю, переместитесь к правому поддереву текущего узла и продолжайте обход, повторяя шаги 1 и 2, пока не найдете k-ое по величине значение. 😎 Решение:
class Solution {
func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
var stack = [TreeNode]()
var root = root
var k = k
while true {
while root != nil {
stack.append(root!)
root = root?.left
}
root = stack.removeLast()
k -= 1
if k == 0 {
return root!.val
}
root = root?.right
}
}
}1 339
#hard
Задача: 329. Longest Increasing Path in a Matrix
Дана матрица целых чисел размером m x n. Верните длину самого длинного возрастающего пути в матрице.
Из каждой ячейки можно перемещаться в четырех направлениях: влево, вправо, вверх или вниз. Перемещение по диагонали или выход за границы матрицы (т.е. замкнутые переходы) не допускается.
Пример:
Input: matrix = [[9,9,4],[6,6,8],[2,1,1]] Output: 4 Explanation: The longest increasing path is [1, 2, 6, 9].👨💻 Алгоритм: 1⃣Инициализация и создание матрицы: Инициализируйте размеры матрицы m и n. Создайте матрицу matrix с добавленными границами (нулевыми значениями) вокруг исходной матрицы, чтобы избежать выхода за пределы при обработке. Рассчитайте количество исходящих связей (outdegrees) для каждой клетки и сохраните их в outdegree. 2⃣Поиск начальных листьев: Найдите все клетки с нулевыми исходящими связями и добавьте их в список leaves. Эти клетки будут начальной точкой для "слоевого удаления". 3⃣Удаление слоев: Повторяйте процесс удаления клеток уровня за уровнем в порядке топологической сортировки, пока не останется листьев. Обновляйте количество исходящих связей и добавляйте новые листья на следующем уровне. Подсчитывайте количество уровней, что в итоге даст длину самого длинного возрастающего пути. 😎 Решение:
class Solution {
private let dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]
func longestIncreasingPath(_ matrix: [[Int]]) -> Int {
let m = matrix.count
if m == 0 { return 0 }
let n = matrix[0].count
var outdegree = Array(repeating: Array(repeating: 0, count: n + 2), count: m + 2)
var newMatrix = Array(repeating: Array(repeating: 0, count: n + 2), count: m + 2)
for i in 0..<m {
for j in 0..<n {
newMatrix[i + 1][j + 1] = matrix[i][j]
}
}
for i in 1...m {
for j in 1...n {
for d in dir {
if newMatrix[i][j] < newMatrix[i + d[0]][j + d[1]] {
outdegree[i][j] += 1
}
}
}
}
var leaves = [[Int]]()
for i in 1...m {
for j in 1...n {
if outdegree[i][j] == 0 {
leaves.append([i, j])
}
}
}
var height = 0
while !leaves.isEmpty {
height += 1
var newLeaves = [[Int]]()
for node in leaves {
for d in dir {
let x = node[0] + d[0]
let y = node[1] + d[1]
if newMatrix[node[0]][node[1]] > newMatrix[x][y] {
outdegree[x][y] -= 1
if outdegree[x][y] == 0 {
newLeaves.append([x, y])
}
}
}
}
leaves = newLeaves
}
return height
}
}1 339
#medium
Задача: 229. Majority Element II
Дан массив целых чисел размера n, найдите все элементы, которые встречаются более ⌊ n/3 ⌋ раз.
Пример:
Input: nums = [3,2,3] Output: [3]👨💻 Алгоритм: 1⃣Поиск кандидатов: Пройдите через массив, используя алгоритм Бойера-Мура для поиска двух потенциальных кандидатов, которые могут встречаться более ⌊ n/3 ⌋ раз. Поддерживайте два счётчика и двух кандидатов. Если текущий элемент равен одному из кандидатов, увеличьте соответствующий счётчик. Если счётчик равен нулю, установите текущий элемент как кандидата и установите счётчик в 1. Если текущий элемент не совпадает ни с одним из кандидатов, уменьшите оба счётчика. 2⃣Подсчёт голосов: После определения двух кандидатов, пройдите через массив снова, чтобы посчитать фактическое количество появлений каждого кандидата. 3⃣Проверка порога: Проверьте, превышает ли количество появлений каждого кандидата порог ⌊ n/3 ⌋. Если да, добавьте кандидата в результат. 😎 Решение:
class Solution {
func majorityElement(_ nums: [Int]) -> [Int] {
var count1 = 0, count2 = 0
var candidate1: Int? = nil
var candidate2: Int? = nil
for n in nums {
if let c1 = candidate1, c1 == n {
count1 += 1
} else if let c2 = candidate2, c2 == n {
count2 += 1
} else if count1 == 0 {
candidate1 = n
count1 = 1
} else if count2 == 0 {
candidate2 = n
count2 = 1
} else {
count1 -= 1
count2 -= 1
}
}
count1 = 0
count2 = 0
for n in nums {
if let c1 = candidate1, c1 == n {
count1 += 1
}
if let c2 = candidate2, c2 == n {
count2 += 1
}
}
var result: [Int] = []
let n = nums.count
if let c1 = candidate1, count1 > n / 3 {
result.append(c1)
}
if let c2 = candidate2, count2 > n / 3 {
result.append(c2)
}
return result
}
}1 339
#medium
Задача: 474. Ones and Zeroes
Дан массив двоичных строк strs и два целых числа m и n.
Верните размер наибольшего подмножества strs, такого что в подмножестве содержится не более m нулей и n единиц.
Множество x является подмножеством множества y, если все элементы множества x также являются элементами множества y.
Пример:
Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.
👨💻 Алгоритм:
1⃣Рассматриваем все возможные подмножества, прерывая цикл, если количество нулей превышает m или количество единиц превышает n.
2⃣Считаем количество нулей и единиц в каждом подмножестве.
3⃣Выбираем наибольшее подмножество, соответствующее условиям, и возвращаем его размер.
😎 Решение:
class Solution {
func findMaxForm(_ strs: [String], _ m: Int, _ n: Int) -> Int {
var maxlen = 0
for i in 0..<(1 << strs.count) {
var zeroes = 0, ones = 0, len = 0
for j in 0..<32 {
if (i & (1 << j)) != 0 {
let count = countZeroesOnes(strs[j])
zeroes += count[0]
ones += count[1]
if zeroes > m || ones > n {
break
}
len += 1
}
}
if zeroes <= m && ones <= n {
maxlen = max(maxlen, len)
}
}
return maxlen
}
func countZeroesOnes(_ s: String) -> [Int] {
var c = [0, 0]
for char in s {
c[Int(char.asciiValue! - Character("0").asciiValue!)] += 1
}
return c
}
}1 339
😂 На одном кодинге уже давно не вывезешь, перспектива 2024 года - Информационная Безопасность
Ловите два канала на тему ИБ и хакинга
Арсенал Безопасника - Проект по кибербезопасности - сборник лучших инструментов и утилит по OSINT, хакингу и деанону
Бункер Хакера - Все что необходимо, для того чтобы начать свой путь в безопасности - инструменты, книги, справочники, гайды и ресурсы.
