Swift | LeetCode
Open in Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Show more
Network:1 340
Subscribers
-124 hours
-97 days
-2430 days
Posts Archive
1 340
Задача: 717. 1-bit and 2-bit Characters
Сложность: easy
У нас есть два специальных символа: первый символ может быть представлен одним битом 0. Второй символ может быть представлен двумя битами (10 или 11). Если задан двоичный массив bits, который заканчивается 0, верните true, если последний символ должен быть однобитным.
Пример:
Input: bits = [1,0,0] Output: true👨💻 Алгоритм: 1⃣Инициализируйте индекс для итерации по массиву. 2⃣Пройдите по массиву, увеличивая индекс на 1, если текущий бит равен 0, и на 2, если текущий бит равен 1. 3⃣Проверьте, достиг ли индекс последнего элемента массива, и верните результат. 😎 Решение:
func isOneBitCharacter(_ bits: [Int]) -> Bool {
var i = 0
while i < bits.count - 1 {
i += bits[i] + 1
}
return i == bits.count - 1
}1 340
Задача: 435. Non-overlapping Intervals
Сложность: medium
Дан массив интервалов intervals, где intervals[i] = [starti, endi]. Верните минимальное количество интервалов, которые нужно удалить, чтобы остальные интервалы не пересекались.
Пример:
Input: intervals = [[1,2],[2,3],[3,4],[1,3]] Output: 1 Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.👨💻 Алгоритм: 1⃣Отсортируйте интервалы по времени окончания. 2⃣Инициализируйте переменную ответа ans = 0 и целое число k для представления самого последнего времени окончания. k следует инициализировать небольшим значением, например, INT_MIN. 3⃣Итеративно пройдитесь по интервалам. Для каждого интервала: Если время начала больше или равно k, обновите k до времени окончания текущего интервала. В противном случае увеличьте ans. Верните ans. 😎 Решение:
class Solution {
func eraseOverlapIntervals(_ intervals: [[Int]]) -> Int {
let sortedIntervals = intervals.sorted { $0[1] < $1[1] }
var ans = 0
var k = Int.min
for interval in sortedIntervals {
let x = interval[0]
let y = interval[1]
if x >= k {
k = y
} else {
ans += 1
}
}
return ans
}
}1 340
Задача: 245. Shortest Word Distance II
Сложность: medium
Дан массив строк wordsDict и две строки word1 и word2, которые уже существуют в массиве. Верните наименьшее расстояние между вхождениями этих двух слов в списке.
Обратите внимание, что word1 и word2 могут быть одинаковыми. Гарантируется, что они представляют собой два отдельных слова в списке.
Пример:
Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding" Output: 1👨💻 Алгоритм: 1⃣Переберите список wordsDict и сохраните индексы слова word1 в список indices1 и индексы слова word2 в список indices2. Инициализируйте переменную shortestDistance = INT_MAX. 2⃣Переберите индексы в списке indices1 и для каждого индекса найдите верхнюю границу в списке indices2, используя бинарный поиск, и сохраните этот индекс в переменную x. Рассмотрите индексы indices2[x] и indices2[x - 1], обновляя shortestDistance, если индексы не совпадают. 3⃣Верните значение переменной shortestDistance. 😎 Решение:
class Solution {
func shortestWordDistance(_ wordsDict: [String], _ word1: String, _ word2: String) -> Int {
var indices1 = [Int]()
var indices2 = [Int]()
for (i, word) in wordsDict.enumerated() {
if word == word1 {
indices1.append(i)
}
if word == word2 {
indices2.append(i)
}
}
var shortestDistance = Int.max
for index in indices1 {
let x = indices2.partitioningIndex(where: { $0 > index })
if x < indices2.count {
shortestDistance = min(shortestDistance, indices2[x] - index)
}
if x > 0 && indices2[x - 1] != index {
shortestDistance = min(shortestDistance, index - indices2[x - 1])
}
}
return shortestDistance
}
}1 340
Задача: 567. Permutation in String
Сложность: medium
Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае.
Другими словами, верните true, если одна из перестановок s1 является подстрокой s2.
Пример:
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").
👨💻 Алгоритм:
1⃣Создать массив для подсчета символов в строке s1. Затем создать аналогичный массив для первых len(s1) символов строки s2.
2⃣Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять массив подсчета символов и сравнивать его с массивом для строки s1.
3⃣Если массивы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false.
😎 Решение:
class Solution {
func checkInclusion(_ s1: String, _ s2: String) -> Bool {
let s1Len = s1.count, s2Len = s2.count
if s1Len > s2Len { return false }
let s1Arr = Array(s1), s2Arr = Array(s2)
var s1Count = [Int](repeating: 0, count: 26)
var s2Count = [Int](repeating: 0, count: 26)
for i in 0..<s1Len {
s1Count[Int(s1Arr[i].asciiValue! - Character("a").asciiValue!)] += 1
s2Count[Int(s2Arr[i].asciiValue! - Character("a").asciiValue!)] += 1
}
for i in 0..<(s2Len - s1Len) {
if s1Count == s2Count { return true }
s2Count[Int(s2Arr[i].asciiValue! - Character("a").asciiValue!)] -= 1
s2Count[Int(s2Arr[i + s1Len].asciiValue! - Character("a").asciiValue!)] += 1
}
return s1Count == s2Count
}
}1 340
Задача: 442. Find All Duplicates in an Array
Сложность: medium
Дан целочисленный массив nums длины n, где все целые числа nums находятся в диапазоне [1, n], и каждое число появляется один или два раза. Верните массив всех чисел, которые появляются дважды.
Вы должны написать алгоритм, который работает за время O(n) и использует только постоянное дополнительное пространство.
Пример:
Input: nums = [4,3,2,7,8,2,3,1] Output: [2,3]👨💻 Алгоритм: 1⃣Когда мы итерируемся по элементам входного массива, мы можем просто искать любое другое вхождение текущего элемента в оставшейся части массива. 2⃣Поскольку элемент может появляться только один или два раза, нам не нужно беспокоиться о получении дубликатов элементов, которые появляются дважды: Случай I: Если элемент встречается в массиве только один раз, при поиске его в остальной части массива ничего не найдется. Случай II: Если элемент встречается дважды, вы найдете второе вхождение элемента в оставшейся части массива. Когда вы наткнетесь на второе вхождение в более поздней итерации, это будет аналогично случаю I (поскольку больше вхождений этого элемента в оставшейся части массива не будет). 3⃣Таким образом, можно эффективно определить все элементы, которые встречаются дважды, и добавить их в результирующий массив, проходя по каждому элементу массива и проверяя наличие его второго вхождения в оставшейся части массива. 😎 Решение:
class Solution {
func findDuplicates(_ nums: [Int]) -> [Int] {
var ans = [Int]()
for i in 0..<nums.count {
for j in (i+1)..<nums.count {
if nums[j] == nums[i] {
ans.append(nums[i])
break
}
}
}
return ans
}
}1 340
Сегодня последний день!
Акция на Пожизненный easyoffer PRO - по цене 1 года заканчивается сегодня.
PRO подписка включает:
– Доступ ко всем профессиям сайта без ограничений
– Все текущие и новые функции, которые будут появляться на сайте
👉 Акция до 31 марта 23:59 по МСК https://easyoffer.ru/pro
1 340
Задача: 946. Validate Stack Sequences
Сложность: medium
Вам дан целочисленный массив nums. За один ход вы можете выбрать индекс i, где 0 <= i < nums.length, и увеличить nums[i] на 1. Верните минимальное количество ходов, чтобы каждое значение в nums было уникальным. Тестовые примеры генерируются так, чтобы ответ умещался в 32-битное целое число.
Пример:
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1] Output: true👨💻 Алгоритм: 1⃣Инициализировать пустой стек. Использовать указатель j для отслеживания текущей позиции в массиве popped. 2⃣Пройти по каждому элементу в массиве pushed: Добавить элемент в стек. Проверить верхний элемент стека: Если он совпадает с текущим элементом в popped, удалить элемент из стека и увеличить указатель j. 3⃣В конце вернуть true, если указатель j достиг конца массива popped, иначе вернуть false. 😎 Решение:
class Solution {
func validateStackSequences(_ pushed: [Int], _ popped: [Int]) -> Bool {
var stack = [Int]()
var j = 0
for x in pushed {
stack.append(x)
while !stack.isEmpty && j < popped.count && stack.last == popped[j] {
stack.removeLast()
j += 1
}
}
return j == popped.count
}
}1 340
Задача: 1155. Number of Dice Rolls With Target Sum
Сложность: medium
У вас есть n кубиков, и на каждом кубике k граней, пронумерованных от 1 до k.
Даны три целых числа n, k и target. Необходимо вернуть количество возможных способов (из общего количества kn способов) выбросить кубики так, чтобы сумма выпавших чисел равнялась target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
Input: n = 1, k = 6, target = 3
Output: 1
Explanation: You throw one die with 6 faces.
There is only one way to get a sum of 3.class Solution {
let MOD = 1_000_000_007
func waysToTarget(_ memo: inout [[Int]], _ diceIndex: Int, _ n: Int, _ currSum: Int, _ target: Int, _ k: Int) -> Int {
if diceIndex == n {
return currSum == target ? 1 : 0
}
if memo[diceIndex][currSum] != -1 {
return memo[diceIndex][currSum]
}
var ways = 0
for i in 1...min(k, target - currSum) {
ways = (ways + waysToTarget(&memo, diceIndex + 1, n, currSum + i, target, k)) % MOD
}
memo[diceIndex][currSum] = ways
return ways
}
func numRollsToTarget(_ n: Int, _ k: Int, _ target: Int) -> Int {
var memo = Array(repeating: Array(repeating: -1, count: target + 1), count: n + 1)
return waysToTarget(&memo, 0, n, 0, target, k)
}
}1 340
Завтра последний день!
Успей купить пожизненный easyoffer PRO - по цене 1 года
Покупаешь один раз — пользуешься всю жизнь.
👉 Акция до 31 марта: https://easyoffer.ru/pro
1 340
Задача: 434. Number of Segments in a String
Сложность: easy
Дана строка s, верните количество сегментов в строке.
Сегмент определяется как непрерывная последовательность символов, отличных от пробелов.
Пример:
Input: s = "Hello, my name is John" Output: 5 Explanation: The five segments are ["Hello,", "my", "name", "is", "John"]👨💻 Алгоритм: 1⃣Инициализируйте счетчик сегментов segment_count равным 0. 2⃣Итеративно пройдитесь по строке s. Для каждого индекса i проверьте, начинается ли на этом индексе сегмент: Если символ s[i] не является пробелом, и (либо это первый символ строки, либо предыдущий символ s[i-1] является пробелом), увеличьте segment_count. 3⃣Верните segment_count. 😎 Решение:
class Solution {
func countSegments(_ s: String) -> Int {
var segmentCount = 0
let chars = Array(s)
for i in 0..<chars.count {
if (i == 0 || chars[i - 1] == " ") && chars[i] != " " {
segmentCount += 1
}
}
return segmentCount
}
}1 340
Задача: 316. Remove Duplicate Letters
Сложность: medium
Дана строка
s, удалите повторяющиеся буквы так, чтобы каждая буква появилась один раз и только один раз. Вы должны сделать так, чтобы результат был наименьшим в лексикографическом порядке среди всех возможных результатов.
Пример:
Input: s = "bcabc" Output: "abc"👨💻 Алгоритм: 1⃣Инициализация стека Создайте стек, который будет хранить результат, построенный по мере итерации строки. 2⃣Итерация по строке На каждой итерации добавляйте текущий символ в стек, если он еще не был использован. Перед добавлением текущего символа удаляйте как можно больше символов из вершины стека, если это возможно и улучшает лексикографический порядок. 3⃣Удаление символов Удаляйте символы с вершины стека при выполнении следующих условий: Символ на вершине стека больше текущего символа. Символ может быть удален, так как он встречается позже в строке. На каждом этапе итерации по строке жадно минимизируйте содержимое стека. 😎 Решение:
class Solution {
func removeDuplicateLetters(_ s: String) -> String {
var stack = [Character]()
var seen = Set<Character>()
let lastOccurrence = Dictionary(uniqueKeysWithValues: s.enumerated().map { ($1, $0) })
for (i, c) in s.enumerated() {
if !seen.contains(c) {
while let last = stack.last, c < last, i < lastOccurrence[last]! {
seen.remove(stack.popLast()!)
}
seen.insert(c)
stack.append(c)
}
}
return String(stack)
}
}1 340
Задача: 496. Next Greater Element I
Сложность: easy
Следующий больший элемент для некоторого элемента x в массиве — это первый больший элемент, который находится справа от x в том же массиве.
Вам даны два различных целочисленных массива с индексами, начинающимися с 0: nums1 и nums2, где nums1 является подмножеством nums2.
Для каждого 0 <= i < nums1.length найдите индекс j, такой что nums1[i] == nums2[j], и определите следующий больший элемент для nums2[j] в nums2. Если следующего большего элемента нет, то ответ для этого запроса — -1.
Верните массив ans длиной nums1.length, где ans[i] — это следующий больший элемент, как описано выше.
Пример:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2] Output: [-1,3,-1] Explanation: The next greater element for each value of nums1 is as follows: - 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1. - 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3. - 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.👨💻 Алгоритм: 1⃣Инициализация и поиск совпадений Создайте массив res для хранения результатов. Для каждого элемента nums1[i] найдите его индекс j в массиве nums2. 2⃣Поиск следующего большего элемента После нахождения индекса j в nums2 начните поиск элемента справа от nums2[j], который больше nums1[i]. Если такой элемент найден, добавьте его в res. 3⃣Заполнение результата Если следующий больший элемент не найден, добавьте -1 в соответствующую позицию res. Верните массив res. 😎 Решение:
class Solution {
func nextGreaterElement(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
var res = [Int](repeating: -1, count: nums1.count)
for i in 0..<nums1.count {
var found = false
for j in 0..<nums2.count {
if nums2[j] == nums1[i] {
found = true
}
if found && nums2[j] > nums1[i] {
res[i] = nums2[j]
break
}
}
}
return res
}
}1 340
Задача: 1039. Minimum Score Triangulation of Polygon
Сложность: medium
У вас есть выпуклый n-сторонний многоугольник, каждая вершина которого имеет целочисленное значение. Вам дан целочисленный массив values, где values[i] - это значение i-й вершины (т.е. по часовой стрелке). Вы должны триангулировать многоугольник на n - 2 треугольника. Для каждого треугольника значение этого треугольника равно произведению значений его вершин, а общий балл триангуляции равен сумме этих значений для всех n - 2 треугольников в триангуляции. Верните наименьший возможный общий балл, который вы можете получить с помощью некоторой триангуляции многоугольника.
Пример:
Input: values = [1,2,3] Output: 6👨💻 Алгоритм: 1⃣Инициализация: Создаем двумерный массив dp, где dp[i][j] будет хранить минимальный возможный общий балл триангуляции многоугольника, состоящего из вершин от i до j. 2⃣Основное заполнение dp: Проходим по всем возможным длинам подмногоугольников, начиная с треугольников (длина 3) до всего многоугольника (длина n). Для каждого подмногоугольника находим минимальный возможный общий балл, проверяя все возможные треугольники, которые могут быть образованы из этого подмногоугольника. Заполнение dp для каждого подмногоугольника: Для каждого подмногоугольника от i до j, и для каждой возможной вершины k между i и j, обновляем значение dp[i][j], как сумму минимальных значений триангуляций левой и правой частей подмногоугольника, а также значения текущего треугольника, образованного вершинами i, k и j. 3⃣Возврат результата: Ответ будет в dp[0][n-1], который хранит минимальный возможный общий балл триангуляции для всего многоугольника. 😎 Решение:
class Solution {
func minScoreTriangulation(_ values: [Int]) -> Int {
let n = values.count
var dp = Array(repeating: Array(repeating: 0, count: n), count: n)
for length in 2..<n {
for i in 0..<(n - length) {
let j = i + length
dp[i][j] = Int.max
for k in (i + 1)..<j {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[j] * values[k])
}
}
}
return dp[0][n - 1]
}
}1 340
Задача: 55. Jump Game
Сложность: medium
Вам дан массив целых чисел nums. Изначально вы находитесь на первом индексе массива, и каждый элемент массива представляет вашу максимальную длину прыжка в этой позиции.
Верните true, если вы можете достичь последнего индекса, или false в противном случае.
Пример:
Input: nums = [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.👨💻Алгоритм: 1⃣Инициализация таблицы памяти: Изначально все элементы таблицы памяти имеют статус UNKNOWN, за исключением последнего, который является (тривиально) GOOD (может достичь сам себя). 2⃣Модификация алгоритма обратного трассирования: Измените алгоритм обратного трассирования таким образом, чтобы на рекурсивном шаге сначала проверялось, известен ли индекс (GOOD/BAD). Если индекс известен, тогда возвращается True/False. 3⃣Выполнение и сохранение результатов: Если индекс не известен, выполняйте шаги обратного трассирования, как ранее. После определения значения текущего индекса, сохраните его в таблице памяти. 😎 Решение:
enum Index {
case good, bad, unknown
}
class Solution {
var memo: [Index]
init(_ nums: [Int]) {
self.memo = Array(repeating: .unknown, count: nums.count)
self.memo[nums.count - 1] = .good
}
func canJumpFromPosition(_ position: Int, _ nums: [Int]) -> Bool {
if memo[position] != .unknown {
return memo[position] == .good
}
let furthestJump = min(position + nums[position], nums.count - 1)
for nextPosition in (position + 1)...furthestJump {
if canJumpFromPosition(nextPosition, nums) {
memo[position] = .good
return true
}
}
memo[position] = .bad
return false
}
func canJump(_ nums: [Int]) -> Bool {
return canJumpFromPosition(0, nums)
}
}1 340
Пожизненный PRO доступ на easyoffer — по цене одного года!
До 31 марта вы можете купить PRO навсегда. Запускаем акцию, чтобы ускорить развитие сервиса.
Что добавим в PRO в ближайшие полгода:
– Автоотклики
– Агрегатор вакансий
– Проход ATS без отсева
– Уникальные резюме и письма под каждую вакансию
Покупаешь один раз — пользуешься всю жизнь.
👉 Купить PRO со скидкой 70%: https://easyoffer.ru/pro
1 340
Задача: 895. Maximum Frequency Stack
Сложность: hard
Разработайте структуру данных, похожую на стек, чтобы заталкивать элементы в стек и вытаскивать из него самый частый элемент. Реализуйте класс FreqStack: FreqStack() строит пустой стек частот. void push(int val) заталкивает целое число val на вершину стека. int pop() удаляет и возвращает самый частый элемент в стеке. Если есть равенство в выборе самого частого элемента, то удаляется и возвращается элемент, который ближе всего к вершине стека.
Пример:
Input ["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"] [[], [5], [7], [5], [7], [4], [5], [], [], [], []] Output [null, null, null, null, null, null, null, 5, 7, 5, 4]👨💻 Алгоритм: 1⃣Создать два словаря: freq для хранения частоты каждого элемента и group для хранения стека элементов для каждой частоты. 2⃣При добавлении элемента увеличивать его частоту в freq и добавлять его в стек соответствующей частоты в group. 3⃣При извлечении элемента найти максимальную частоту, удалить элемент из стека соответствующей частоты и уменьшить его частоту в freq. Если стек для данной частоты становится пустым, удалить его. 😎 Решение:
class FreqStack {
private var freq: [Int: Int]
private var group: [Int: [Int]]
private var maxfreq: Int
init() {
freq = [:]
group = [:]
maxfreq = 0
}
func push(_ val: Int) {
let f = (freq[val] ?? 0) + 1
freq[val] = f
if f > maxfreq {
maxfreq = f
group[f] = []
}
group[f]?.append(val)
}
func pop() -> Int {
guard let val = group[maxfreq]?.popLast() else { return -1 }
freq[val, default: 0] -= 1
if group[maxfreq]?.isEmpty ?? false {
maxfreq -= 1
}
return val
}
}1 340
Задача: 1230. Toss Strange Coins
Сложность: medium
У вас есть несколько монет. Вероятность выпадения орла для i-й монеты равна prob[i].
Верните вероятность того, что количество монет, на которых выпал орел, равно target, если вы подбросите каждую монету ровно один раз.
Пример:
Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0 Output: 0.03125👨💻 Алгоритм: 1⃣Инициализация: Создайте переменную n и инициализируйте её размером массива prob. Создайте 2D массив dp размером n + 1 строк и target + 1 столбцов, где dp[i][j] хранит вероятность получить j орлов, используя первые i монет. Установите базовый случай dp[0][0] = 1. 2⃣Итерация: Используйте два вложенных цикла для заполнения массива dp. Внешний цикл итерируется от i = 1 до n. Для каждого i установите dp[i][0], что обозначает вероятность получить 0 орлов при использовании i монет: dp[i][0] = dp[i - 1][0] * (1 - prob[i - 1]). Внутренний цикл итерируется от j = 1 до target. Для каждого j вычислите dp[i][j] по формуле: dp[i][j] = dp[i - 1][j - 1] * prob[i - 1] + dp[i - 1][j] * (1 - prob[i - 1]). 3⃣Возврат результата: Верните значение dp[n][target], которое содержит искомую вероятность. 😎 Решение:
class Solution {
func probabilityOfHeads(_ prob: [Double], _ target: Int) -> Double {
let n = prob.count
var dp = Array(repeating: Array(repeating: 0.0, count: target + 1), count: n + 1)
dp[0][0] = 1.0
for i in 1...n {
dp[i][0] = dp[i - 1][0] * (1 - prob[i - 1])
for j in 1...target {
if j <= i {
dp[i][j] = dp[i - 1][j - 1] * prob[i - 1] + dp[i - 1][j] * (1 - prob[i - 1])
}
}
}
return dp[n][target]
}
}1 340
Задача: 259. 3Sum Smaller
Сложность: medium
Дан массив из n целых чисел nums и целое число target. Найдите количество троек индексов i, j, k, удовлетворяющих условию 0 <= i < j < k < n и nums[i] + nums[j] + nums[k] < target.
Пример:
Input: nums = [-2,0,1,3], target = 2 Output: 2 Explanation: Because there are two triplets which sums are less than 2: [-2,0,1] [-2,0,3]👨💻 Алгоритм: 1⃣Отсортируйте массив nums. 2⃣Для каждого элемента nums[i] от 0 до n-3 найдите количество пар индексов j и k (где i < j < k), таких что nums[i] + nums[j] + nums[k] < target. Используйте функцию twoSumSmaller, которая ищет количество пар с суммой меньше заданного значения. 3⃣В функции twoSumSmaller используйте бинарный поиск для поиска верхней границы индекса k и подсчета количества подходящих пар. 😎 Решение:
class Solution {
func threeSumSmaller(_ nums: [Int], _ target: Int) -> Int {
let nums = nums.sorted()
var sum = 0
for i in 0..<nums.count - 2 {
sum += twoSumSmaller(nums, i + 1, target - nums[i])
}
return sum
}
private func twoSumSmaller(_ nums: [Int], _ startIndex: Int, _ target: Int) -> Int {
var sum = 0
for i in startIndex..<nums.count - 1 {
let j = binarySearch(nums, i, target - nums[i])
sum += j - i
}
return sum
}
private func binarySearch(_ nums: [Int], _ startIndex: Int, _ target: Int) -> Int {
var left = startIndex
var right = nums.count - 1
while left < right {
let mid = (left + right + 1) / 2
if nums[mid] < target {
left = mid
} else {
right = mid - 1
}
}
return left
}
}1 340
Задача: 1255. Maximum Score Words Formed by Letters
Сложность: hard
Даны список слов, список отдельных букв (могут повторяться) и оценка каждого символа. Верните максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (words[i] не может быть использовано два или более раз). Не обязательно использовать все символы в буквах, каждая буква может быть использована только один раз. Оценка букв 'a', 'b', 'c', ... , 'z' задаются значениями score[0], score[1], ... , score[25] соответственно.
Пример:
Input: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0] Output: 23👨💻 Алгоритм: 1⃣Создайте функцию для вычисления оценки слова. 2⃣Используйте метод перебора подмножеств (или битовое представление всех подмножеств) для нахождения всех возможных комбинаций слов. Для каждой комбинации проверяйте, можно ли составить каждое слово из доступных букв. 3⃣Вычислите суммарную оценку для каждой допустимой комбинации слов и сохраните максимальную оценку. 😎 Решение:
class Solution {
func maxScoreWords(_ words: [String], _ letters: [Character], _ score: [Int]) -> Int {
var letterCount = [Character: Int]()
for ch in letters {
letterCount[ch, default: 0] += 1
}
func wordScore(_ word: String) -> Int {
var total = 0
for ch in word {
total += score[Int(ch.asciiValue! - Character("a").asciiValue!)]
}
return total
}
func canFormWord(_ word: String, _ letterCount: [Character: Int]) -> Bool {
var count = [Character: Int]()
for ch in word {
count[ch, default: 0] += 1
if count[ch]! > letterCount[ch, default: 0] {
return false
}
}
return true
}
var maxScore = 0
let n = words.count
for i in 1..<1<<n {
var currScore = 0
var usedLetters = [Character: Int]()
var valid = true
for j in 0..<n {
if (i & 1<<j) != 0 {
let word = words[j]
if canFormWord(word, letterCount) {
currScore += wordScore(word)
for ch in word {
usedLetters[ch, default: 0] += 1
}
} else {
valid = false
break
}
}
}
if valid {
maxScore = max(maxScore, currScore)
}
}
return maxScore
}
}1 340
Задача: 832. Flipping an Image
Сложность: easy
Дано бинарное изображение размером n x n, необходимо перевернуть изображение по горизонтали, затем инвертировать его и вернуть результат.
Перевернуть изображение по горизонтали означает, что каждая строка изображения будет развернута.
Например, переворот строки [1,1,0] по горизонтали дает [0,1,1].
Инвертировать изображение означает, что каждый 0 заменяется на 1, а каждый 1 заменяется на 0.
Например, инверсия строки [0,1,1] дает [1,0,0].
Пример:
Input: image = [[1,1,0],[1,0,1],[0,0,0]] Output: [[1,0,0],[0,1,0],[1,1,1]] Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]]. Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]👨💻 Алгоритм: 1⃣Переверните каждую строку по горизонтали, обменяв элементы слева направо и наоборот. 2⃣Инвертируйте каждую строку, заменив каждый 0 на 1 и каждый 1 на 0. 3⃣Верните преобразованное изображение. 😎 Решение:
class Solution {
func flipAndInvertImage(_ A: [[Int]]) -> [[Int]] {
var A = A
let C = A[0].count
for i in 0..<A.count {
for j in 0..<(C + 1) / 2 {
let temp = A[i][j] ^ 1
A[i][j] = A[i][C - 1 - j] ^ 1
A[i][C - 1 - j] = temp
}
}
return A
}
}