четверг, 21 марта 2024 г.

Популярные группы leetcode задач

Метки: , , , , , ,
Популярные группы leetcode задач с кратким описание и полным кодом.
Алгоритмы написаны на Scala 2.12 в java стиле.
Задача может быть сразу в нескольких разделах.

Связанные списки

Задачи, решаемые с помощью списков.

Fast and slow

Задачи для поиска цикла в списке.

Бинарный поиск

Разделяй и властвуй в сортированных данных.

2 pointers

2 указателя в массиве, которые двигаются навстречу друг другу.

Sliding window

Скользящее окно, которое постоянно движется направо, при этом левый край удаляется из окна, а правый добавляется.

Tree

Классические алгоритмы в двоичном дереве
Алгоритмы динамического программирования, использующий DFS для поиска новых вариантов сочетания данных.

Куча (Heap)

Heap (куча) - дерево, все ветви кроме терминальных имеют 2 предка и разница в уровне не более 1
max heap - heap, где дочерние элементы меньше или равны родителю

Stack

Последний пришел - первый ушел.

Очередь (que)

Первый пришел - первый ушел.

Динамическое программирование (back tracking + memorization)

Задачи, которые используют промежуточный результат предыдущего шага для расчета последующего.

Битовые операции

Манипуляции с бинарными данными.

Хэш массив

Мапы/Словари/Хэш массивы.

Матрицы

2х мерные массивы и всего 1 алгоритм работы с матрицами.

Сортировки

Общий обзор видов сортировки без привязки к литкоду
+ пара задач, где необходима сортировка.

Алгоритмы без задачи

Общий обзор раличных популярных алгоритмов или структур данных, без привязки к задачам.

Развернуть список

Reverse Linked List (стоимость: N)
Запоминаем некст, меняем некст на прев, прев = текущий, переходим по запомненому некст
Показать код v 
while(r != null) {
    //запоминаем след. для перехода
    val hnext = r.next
    //меняем некст на прев
    r.next = prev
    //запоминаем прев
    prev = r
    //переходим к следующему
    r = hnext
}

Получить сумму 2 списков

Add Two Numbers (N)
Движемся одновременно по 2 спискам, пока хотя бы 1 есть
записываем сумму % 10
запоминаем переполнение и переносим дальше по циклу через /10
если после цикла есть переполнение, то доблавляем его в список
Показать код v 
def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {
    val head = new ListNode()
    var overf: Int = 0
    var curr = head
    var l = l1
    var r = l2
    do {
        var res = (if(l==null) 0 else l.x) + (if(r==null) 0 else r.x) + overf
        overf = res/10
        curr.next = new ListNode(res%10)
        curr=curr.next

        l = if(l != null ) l.next else null
        r = if(r != null ) r.next else null
    }
    while(l != null || r != null) 
    if(overf>0) {
        curr.next = new ListNode(overf)
    }
    head.next 
}

Слияние сортированных списков

Merge k Sorted Lists (N)
цикл по спискам: ищем минимальный элемент на тек. позиции
вставляем найденное значение в новый список
смещаемся на след. элемент в найденном списке
ходим пока итем из списка с минимальным элементом != null
Показать код v 
def mergeKLists(lists: Array[ListNode]): ListNode = {
    var ret: ListNode = null
    var ret_head: ListNode = null
    
    if(lists.size == 0) return ret_head

    var it = true
    while(it) {
        var min = 0
        for(i <- 0 until lists.size) {
            if(lists(i) != null && ( lists(min) == null || lists(i).x < lists(min).x ) ) min = i
        }
        if(lists(min) == null) {
            it = false 
        } else {
            //print(lists(min).x + ", ")
            if(ret == null) {
                ret = new ListNode(lists(min).x) 
                ret_head = ret
            } else {
                ret.next = new ListNode(lists(min).x)
                ret = ret.next
            }
            lists(min) = lists(min).next 
        }
    }
    ret_head
}

Цикл в списке

Linked List Cycle (N)
2 указателя: sl.next и fl.next.next
если sl = fl - цикл
если дошли до конца: fl == null || fl.next == null - нет цикла
Показать код v 
def hasCycle(head: ListNode): Boolean = {
    var sl = head
    var fl = head

    while(fl != null && fl.next != null) {
        fl = fl.next.next
        sl = sl.next
        if(fl == sl) return true
    }
    return false

}

Середина списка

Middle of the Linked List (N)
когда фаст вконце, то слоу в середине
Показать код v 
def middleNode(head: ListNode): ListNode = {
    var fast = head
    var slow = head
    while(fast != null && fast.next != null) {
        fast = fast.next.next
        slow = slow.next
    }
    slow
}

Нахождение точки начала цикла

linked-list-cycle-ii (N)
ищется цикл - точка обнаружения может быть любая, но если нарисовать:
если X - расстояние до точки начала цикла, а Y - это растояние сколько прошел Slow после точки, то:
S = X + Y; F = 2 (X + Y), то чтобы Slow снова оказался в точке X , нужно пройти из точки X+Y еще X шагов.
Т.к. X это так же растояние от начала списка до точки начала цикла, то стартуем еще один цикл прохода сначала списка, и когда новый ходок встретится со Slow, это будет точка X (начало цикла)
Показать код v 
def getIntersectPoint(head: ListNode): ListNode = {
    var sl = head
    var fl = head

    while(fl != null && fl.next != null) {
        fl = fl.next.next
        sl = sl.next
        if(fl == sl) return sl
    }
    return null
}

def detectCycle(head: ListNode): ListNode = {
    val intrs = getIntersectPoint(head)
    if(intrs != null) {
        var ns = head
        var sl = intrs
        while(ns != sl) {
            ns = ns.next
            sl = sl.next
        }
        sl
    } else null
}

Поиск 1 дубликата в массиве

find-the-duplicate-number (N)
Если можно использовать доп. структуры или менять входной массив:
поразрядная сортировка; хэш массив; значение использовать как индекс - зайти и поменять знак, если уже минус, то это дубль
или через фаст/слоу, но след. индекс берется из значения, а точка начала цикла - это повтор числа (смотри подбробное описание в задаче linked-list-cycle-ii)
Показать код v 
def getIntersectPoint(nums: Array[Int]): Int = {
    var sl = 0
    var fl = 0

    do {
        sl = nums(sl)
        fl = nums(nums(fl))
    } while(sl != fl)
    sl
}

def findDuplicate(nums: Array[Int]): Int = {
    var intrs = getIntersectPoint(nums)
    var sl = 0
    while(intrs != sl) {
        sl = nums(sl)
        intrs = nums(intrs)
    }
    intrs
}

Бинарный поиск

Binary Search (LogN)
идем пока lo не встретистя с hi и определяем мед:
while(lo <= hi) med = lo + (hi-lo)/2
смещаем lo/hi на 1
if(nums(med) < target) lo = med + 1 else hi = med - 1
Показать код v 
def search(nums: Array[Int], target: Int): Int = {
    var lo = 0
    var hi = nums.size - 1
    var med = 0
    while(lo <= hi) {
        med = lo + (hi-lo)/2
        if(nums(med) == target) {
            return med
        } else if(nums(med) < target) {
            lo = med + 1
        } else {
            hi = med - 1
        }
    }
    if(med < nums.size && nums(med) == target) return med
    return -1
}

Угадай число

Guess Number Higher or Lower (LogN)
Тоже самое что в binary-search, только направление определяется вызовом g = guess(med)
Показать код v 
def guessNumber(n: Int): Int = {
    var lo = 1
    var hi = n
    var med = -1
    while(lo <= hi) {
        med = lo + (hi-lo)/2
        val g = guess(med)
        if ( g == 0 ) {
            return med
        } else if(g == -1) {
            hi = med - 1
        } else {
            lo = med + 1
        }
    }
    return med
}

Поиск в сортированной матрице

Search a 2D Matrix (LogN)
представляем что матрица это массив из объединенных частей
1 часть размером matrix(0).size (число частей не важно)
var hi = matrix(0).size * matrix.size -1
r = med / matrix(0).size //находим нужную часть (строка)
c = med % matrix(0).size //остаток от деления размера части = положение в части
Показать код v 
def searchMatrix(matrix: Array[Array[Int]], target: Int): Boolean = {
    var lo = 0
    var hi = matrix(0).size * matrix.size -1
    var med = -1
    var c = -1
    var r = -1
    while(lo <= hi) {
        med = lo + (hi-lo)/2
        r = med/matrix(0).size
        c = med % matrix(0).size

        if ( matrix(r)(c) == target ) {
            return true
        } else if(matrix(r)(c) < target) {
            lo = med + 1
        } else {
            hi = med - 1
        }
    }
    return matrix(r)(c) == target
}

Поиск минимума в сортированном массиве, но часть хвоста вначале

Find Minimum in Rotated Sorted Array (LogN)
Часть хвоста массива (большие значения) перенесены вначало, по этому минимальное значение должно быть в hi
nums(med) > nums(hi) lo = med + 1 /* если нет, то мы в левой части */ else hi = med /* иначе в правой и меньшее слева */
Показать код v 
def findMin(nums: Array[Int]): Int = {
    var lo = 0
    var hi = nums.size - 1
    var med = 0
    while(lo < hi) { //ходим пока края не сойдутся
        med = lo + (hi-lo)/2
        //по этому med сверяем с правой частью
        if(nums(med) > nums(hi)) {
            lo = med + 1
        } else {
            hi = med
        }
    }
    return nums(hi)
}

Поиск числа в сортированном массиве, но часть хвоста вначале

Search in Rotated Sorted Array (LogN)
Начало как у Поиск минимума в сортированном массиве, но часть хвоста вначале.
Найденный минимум - это точка свапа значений. Проверяем таргет, в какой части - левой или правой, исходя из этого ставим lo и hi.
Дальше обычный бинарный поиск в найденных границах.
Показать код v 
def search(nums: Array[Int], target: Int): Int = {
    var lo = 0
    var hi = nums.size - 1
    var med = 0
    while(lo < hi) { //ходим пока края не сойдутся
        med = lo + (hi-lo)/2
        //по этому med сверяем с правой частью
        if(nums(med) > nums(hi)) {
            lo = med + 1
        } else {
            hi = med
        }
    }
    
    if( target <= nums(nums.size - 1) ) {
        lo = hi
        hi = nums.size - 1
    } else {
        lo = 0
        hi = hi - 1
    }
    
    while(lo <= hi) { //ходим пока края не сойдутся
        med = lo + (hi-lo)/2
        if(nums(med) == target) return med
        if(nums(med) < target) {
            lo = med + 1
        } else {
            hi = med - 1
        }
    }
    if(nums(med) == target) return med
    return -1
}

Поиск числа в сортированном массиве, но часть хвоста вначале (могут быть дубли)

Search in Rotated Sorted Array II (LogN)
После переноса и большом числе дублей, может оказаться что середина = началу = концу (пример: 3, 1, 2, 3, 3, 3, 3 ), т.е. это нарушение сортировки по возрастанию частей
По этому первым шагом нужно избавиться от дублей элементов слева или справа, чтобы восстановить сортированность:
while(nums(med) == nums(lo) && nums(med) == nums(hi)) { los = los + 1; his = his - 1 }
Далее эти отправные значения используются в алгоритме Поиск числа в сортированном массиве, но часть хвоста вначале
Показать код v 
def search(nums: Array[Int], target: Int): Boolean = {
    var lo = 0
    var hi = nums.size - 1
    var med = lo + (hi-lo)/2
    if(nums.size == 1) return nums(0) == target
    while(nums(med) == nums(lo) && nums(med) == nums(hi)) {
        lo = lo + 1
        hi = hi - 1
        if(hi < lo) return nums(0) == target
        med = lo + (hi-lo)/2
    }
    var lob = lo
    var hib = hi
    
    while(lo < hi) { //ходим пока края не сойдутся
        med = lo + (hi-lo)/2
        if(nums(med) > nums(hi)) {
            lo = med + 1
        } else {
            hi = med
        }
    }
    
    
    if( target <= nums(hib) ) {
        lo = hi
        hi = hib
    } else {
        lo = lob
        hi = hi
    }
    //println(lo, hi)
    
    while(lo <= hi) { //ходим пока края не сойдутся
        med = lo + (hi-lo)/2
        if(nums(med) == target) return true
        if(nums(med) < target) {
            lo = med + 1
        } else {
            hi = med - 1
        }
    }
    if(nums(med) == target) return true
    return false
}

Уникальное число в массиве, где все по 2

Single Number (N)
Самое простое - хэш массив
Без доп. места: XOR всех элементов - одинаковые схопнутся, останется 1 уникальный (nums.reduceLeft(_ ^ _))
Показать код v 
nums.reduceLeft(_ ^ _)

2 числа в массиве, которые дают таргет

Two Sum (N или N*LogN)
* Помещаем все числа в хэш массив
Цикл по каждому элементу: проверяем ниличе в хэш-массиве таргет-число
* Так же можно решить без использования доп. памяти, аналогично как 3Sum - через 2 Pointer:
сортируем, запускаем 2 указателя слева и справа пока не сойдутся
Если таргет больше, уменьшаем правый край, если меньше - увеличиваем левый, если равно - уменьшаем оба края.
Показать код v 
def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    val nums_map = nums.zipWithIndex.toMap
    for ( i <- 0 until nums.size ) {
        val i2 = nums_map.getOrElse( target - nums(i), -1 )
        if( i2 > i ) return Array(i, i2)
    }
    return Array(-1, -1)
}

3 числа в массиве, которые дают таргет

3Sum (N2)
Решается через 2 pointer:
Массив сортируется, делается цикл по каждому элементу с минимального.
Запускается 2 указателя с текущей позиции +1 и края.
Если таргет больше, уменьшаем правый край, если меньше - увеличиваем левый, если равно - уменьшаем оба края.
Для результата используется сет, чтобы исключить дубликаты. Можно не использовать сет, но тогда нужно скипать дубликаты: while(i<j && nums[i]==nums[i+1]) i++;
Показать код v 
def threeSum(nums: Array[Int]): List[List[Int]] = {
    val nums_sorted = nums.sorted
    var ret = Set[List[Int]]()
    for (i <- 0 until nums_sorted.size - 1) {
        var j = i + 1
        var k = nums_sorted.size - 1
        while(j < k) {
            val num = nums_sorted(i) + nums_sorted(j) + nums_sorted(k) 
            if(num == 0) {
                ret = ret + List(nums_sorted(i) , nums_sorted(j) , nums_sorted(k) )
                j += 1
                k -= 1
            } else if(num > 0) {
                k -= 1
            } else {
                j += 1
            }
        }
    }
    ret.toList
}

4 числа в массиве, которые дают таргет

4sum (N^(K-1))
Эта и последющие решаются как добавление еще 1 цикла к 2Sum
3 SUM + еще 1 цикл: for (i2 <- i+1 until nums_sorted.size - 1)
Показать код v 
def fourSum(nums: Array[Int], target: Int): List[List[Int]] = {
    val nums_sorted = nums.sorted
    var ret = Set[List[Int]]()
    for (i <- 0 until nums_sorted.size - 1) {
        for (i2 <- i+1 until nums_sorted.size - 1) {
            var j = i2 + 1
            var k = nums_sorted.size - 1
            while(j < k) {
                val num = nums_sorted(i).toLong + nums_sorted(i2) + nums_sorted(j) + nums_sorted(k) 
                if(num == target) {
                    ret = ret + List(nums_sorted(i), nums_sorted(i2) , nums_sorted(j) , nums_sorted(k) )
                    j += 1
                    k -= 1
                } else if(num > target) {
                    k -= 1
                } else {
                    j += 1
                }
            }
        }
    }
    ret.toList
}

Группы анаграм

Group Anagrams (N*LogN)
* Сортируем элементы, группируем по сортированному
* Группируем по буквам каждую строку. Используем эти группы как ключ для сбора итоговых групп анаграмм
Показать код v 
strs.groupBy(s => s.sorted).map(x=>x._2.toList).toList // n * m*log(m) //поразрядная сортировка: n * m
strs.groupBy(s => s.groupBy(x=>x).map(x=>(x._1, x._2.size)) ).map(x=>x._2.toList).toList //n*m

Проверка на анаграмму

Valid Anagram N
* Группируем и сравниваем маппы
* Можно отсортировать и сравнить
Показать код v 
def isAnagram(s: String, t: String): Boolean = {
    s.groupBy(x=>x) == t.groupBy(x=>x)
}

Все анаграммы P в S

Find All Anagrams in a String (N)
решается через sliding window:
завести массив/мапа P, где ключ - буква, значение = число повторов
размер окна = размеру P, правый край добавляем во вторую мапу окна, левый уменьшаем счетчик букв, если доходит до 0, то удаляем
сравниваем эти 2 маппы побуквенно. Сложность сравнения = числу букв алфавита = const (по этому общая сложность const*N = N)
Показать код v 
def findAnagrams(s: String, p: String): List[Int] = {
    var ans = List[Int]()
    if(p.size > s.size) return ans
    var freq_p = p.groupBy(x=>x).map(x=>(x._1, x._2.size))
    var window_s = Map[Char, Int]()

    for(i <- 0 until s.size) {
        if(i-p.size >= 0) {
            if(window_s.getOrElse(s(i-p.size), 0) - 1 == 0) {
                window_s = window_s - s(i-p.size)
            } else {
                window_s = window_s + ( s(i-p.size)-> (window_s.getOrElse(s(i-p.size), 0) - 1) )
            }
        }
        window_s = window_s + ( s(i)-> (window_s.getOrElse(s(i), 0) + 1) )

        if(freq_p == window_s) ans = ans :+ (i-p.size+1)
    }
    ans
}

Валидные скобки

Valid Parentheses (N)
при появлении открывающей, добавляем в стек закрывающую
при закрывающей: извлекаем из стека, сверяем наша ли (доп. проверка что стек не пустой)
(инвертированная логика лучше, потому что не требует доп проверок)
Показать код v 
def isValid(s: String): Boolean = {
    var st = new scala.collection.mutable.Stack[Char]()
    for (e <- s) {
        if(e == '(') st.push(')')
        else if(e == '{') st.push('}')
        else if(e == '[') st.push(']')
        else if(st.size == 0 || st.pop() != e) return false
    }
    return st.size == 0
}

Непрерывное число 1 в последовательности, но может быть K пропусков

Max Consecutive Ones III (N)
Данная задача есть в нескольких вариациях:
* ничего менять нельзя (k=0) - считаем непрерывное число 1, сбрасываем на 0 и обновляем максимум
* можно менять K нулей на 1 - решается через sliding window
идем в цикле - увеличиваем правый край окна, если видим 0 то увеличиваем правый край, уменьшаем K пока не станет меньше 0
если k меньше 0, и слева = 0 (т.е когда то K исчерпали), теперь увеличиваем и смещаем левую границу на +1
т.е. окно всегда расшряется и никогда не сужается, тем самым найдем максимум = nums.size - left
Показать код v 
def longestOnes(nums: Array[Int], k: Int): Int = {
    var left = 0
    var right = 0
    var k_cur = k

    for (right <- 0 until nums.size ) {    
        if(nums(right) == 0) {
            k_cur -= 1
        }
        if (k_cur < 0) {
            if(nums(left) == 0) {
                k_cur += 1
            }
            left += 1
        }
    }
    nums.size - left
}

Обход дерева в ширину (BFS)

(N)
Решается через очередь (первый зашел - последний вышел): добавляем корень в очередь
Пока очередь не пуста: извлекаем первого, добавляем в конец потомков, обрабатываем след. в очереди (сосед по уровню)
Показать код v 
var q = scala.collection.mutable.Queue[TreeNode](root)
while(q.size > 0) {
    for(i <- 0 until q.size) {
        val node = q.dequeue
        print(node.value + " ")
        //в случае графа добавляется проверка по visited и обходим массив соседей
        if(node.left != null) q.enqueue(node.left) 
        if(node.right != null) q.enqueue(node.right) 
    }
}

Обход дерева в глубину (DFS)

Binary Tree Inorder Traversal (N)
Решается через рекурсию или стек (первый зашел, первый вышел)
* Добавляем корень в стек. Идем влево, пока есть значения, добавляем в стек, когда дошли до низу, извлекаем верх стека, добавляем правую ветвь
* Но проще делается через рекурсию (вызов рекурсии кладет в стек, выход - извлекает). В зависимости куда поместить вставку значения ноды, будет разные обход:
- Перед рекурсивными вызовами - слева направо, сверху вниз
- Поменять местами вызовы - справо наплево - Между рекурсивными вызова left и right - лево: снизу-вверх, право: сверху-вниз
- вконце - снизу вверх
Показать код v 
def inorderTraversal(root: TreeNode): List[Int] = {
    var ret = List[Int]()
    def trav(n: TreeNode): Unit = {
        if(n != null) {
            trav(n.left)
            ret = ret :+ n.value
            trav(n.right)
        }
    }
    trav(root)
    ret
}

Число островов

Number of Islands (N^2)
решается через DFS - идем по каждой ячейке, если она 1, то увеличиваем счетчик и вызываем функцию проверки соседей:
если соседей нет (за границами) или или ячейка не продолжение острова (0), то прерываемся - конец острова
иначе помечаем текущую землю (1) водой (0) и уходим во все стороны рекурсивно (кроме диагоналей)
Показать код v 
def numIslands(grid: Array[Array[Char]]): Int = {
    var grid_mut = grid.toBuffer

    def checkIsland(i: Int, j: Int): Unit = {
        if(i < 0 || j < 0 || i >= grid_mut.size || j >= grid_mut(0).size || grid_mut(i)(j) == '0') return;
        grid_mut(i)(j) = '0'
        checkIsland(i+1, j)
        checkIsland(i, j+1)
        checkIsland(i-1, j)
        checkIsland(i, j-1)
    }

    var isl = 0
    for (i <- 0 until grid_mut.size) {
        for (j <- 0 until grid_mut(0).size) {
            if(grid_mut(i)(j) == '1') {
                checkIsland(i, j)
                isl += 1
            }
        }
    }


    isl
}

Удалить лишние скобки, чтобы получить валидную строку

Remove Invalid Parentheses (N*LogN)
* Функция для проверки валидности - просто подсчет, что число открывающих = числу закрывающих
* добавляем в очередь изначальную строку, идем и извлекаем из очереди
* если строка валидная, то дорабатываем очередь, но больше в нее ничего не добавляем (ставим флаг)
Это необходимо, т.к. мы нашли уже самый длинный вариант строки, если удалять буквы, то строка уже будет меньше. Нужно только проверить что в очереди (имеет ту же длину)
* если флаг не установлен, то запускаем цикл, где убираем 1 букву и добавляем в очередь строку без нее
(добавление только, если после удаления строка не пустая и ее еще не было в сете ранее добавленных visited)
Показать код v 
def removeInvalidParentheses(s: String): List[String] = {
    def isValid(s: String): Boolean = {
        var cnt = 0
            s.foreach(c=> {
                if(c == '(') cnt += 1
                else if(c == ')') {
                    cnt -= 1
                    if(cnt < 0) return false
                }
            })
        cnt == 0
    }
    var q = scala.collection.mutable.Queue[String](s)
    var visited = Set[String](s)
    var ret = Set[String]()
    var found = false

    while(q.size > 0) {
        val s2 = q.dequeue
        if(isValid(s2)) {
            ret = ret + s2
            found = true
        } 
        if(!found) {
            for(i <- 0 until s2.size) {
                val new_s = s2.substring(0,i)+s2.substring(i+1)
                if( (s2(i) == '(' || s2(i) == ')' ) && new_s != "" 
                && !visited.contains(new_s)) {
                    visited = visited + new_s
                    q.enqueue(new_s) 
                } 
            }
        }
    }
    if(ret.isEmpty) List("") else ret.toList

}

Сортировка пузырьком

(N^2)
перемещаем наибольший элемент вправо (сравниваем соседей во вложенном цикле)
повторяем еще раз, но не доходим до наибольшего элемента (отсортированных)
Показать код v 
public static <T extends Comparable<T>> void bubleSort(T[] arr) {
    //проходим по массиву
    for(int i = 0; i < arr.length - 1; i++) {        
        //проходим от начала массива до конца - i с поиском элемента для обмена
        //все что правее конец-i уже отсортированно
        for(int j = 0; j < arr.length - i - 1; j++) {
            //сравниваем текущий элемент с соседним: больший элемент смещаем вправо
            //за каждый проход наибольший элемент уходит в крайнее правое положение = конец-i
            if(arr[j].compareTo(arr[j+1]) > 0) {
                T buf = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = buf;
            }
        }
    }
} //bubleSort

Сортировка вставками

(N^2)
движеся вправо
для каждой итерации: обратно влево, пока не найдем элемент меньше текущего
попутно смещаем все элементы больше текущего вправо на 1
Показать код v 
public static <T extends Comparable<T>> void insertSort(T[] arr) {
    //движемся по массиву вправо
    for(int i = 0; i < arr.length; i++) {
        T val = arr[i];
        int key = i - 1;
        //движемся по массиву влево, пока не найдем элемент меньше текущего
        //все элементы > текущего смещаем вправа на один			
        while(key >= 0 && val.compareTo(arr[key]) < 0) {
            arr[key+1] = arr[key];
            key--;
        }
        //в найденное место: < текущего или первый (key=0), вставляем элемент i операции
        arr[key+1] = val;
    }
} //insertSort

Быстрая сортировка

(N*LogN)
находим элемент в центре массива со средним значением
движемся с краев к центру (Two pointer), меняя значения местами, если влевой части значение больше середины или вправой больше
while(arr(i) < c) i += 1
if(i <= j) { свап ; i++; j-- }
при доходе до середины, запускам рекурсивно для левой и правой части (qsort( l, j) , qsort( i, r) -- индексы переходят середину)
- нестабильная, может быть переполнение стека, сильно зависит от выбора центра
Показать код v 
public static <T extends Comparable<T>> void QSort(T[] arr, int l, int r) {
    int i = l;
    int j = r;
    //средний элемент = левая граница + (правая граница - левая граница) / 2
    T c = arr[l + ( r - l ) / 2];
    
    // идем к центу, пока края не встретятся
    while(i < j) {
        //идем с левого края к центру, пока середина больше текущего значения (ищем элемент больше середины)
        while(arr[i].compareTo(c) < 0) {
            i++;
        }
        //с правого края к центру, пока середина меньше текущего значения (ищем элемент меньше середины)
        while(arr[j].compareTo(c) > 0) {
            j--;
        }
        //если левый индекс меньше правого индекса, то меняем местами и смещаемся
        if(i <= j) {
            T t = arr[j];
            arr[j] = arr[i];
            arr[i] = t;
            i++;
            j--;
        }
    }
    //рекурсивно запускаемся для левой и правой части
    if(l < j) {
        QSort(arr, l, j);
    }
    if(r > i) {
        QSort(arr, i, r);
    }
} //QSort

Сортировка слияением

(N*LogN)
+ внешняя сортировка (может использоваться для очень больших массивов)
+ может использговаться для связанных списков
- доп. память по ппрожуточные части
Алгоритм: разбиваем массив на 2 части пока в массиве не станет 1 элемент: val c = arr.size / 2
val (left, right) = arr.splitAt(c)
val l = mergSort(left)
val r = mergSort(right)
Потом мержим 2 сортированных массива:
merge(l, r)
Показать код v 
class MergeSort {
    //разбитие массива на 2 равные части
    public void sort(Comparable[] arr) {
        
        //если массив достаточно разбит, то прерываем рекурсию
        if(arr.length <= 1) return;
        
        //левая половина
        Comparable[] left = new Comparable[arr.length / 2];		
        System.arraycopy(arr, 0, left, 0, left.length);
        sort(left);
        //swop to disk
        
        //правая половина
        Comparable[] right = new Comparable[arr.length - left.length];
        System.arraycopy(arr, left.length, right, 0, right.length);
        sort(right);
            
        //слияние
        merge(left, right, arr);
    } //sort
    
    //слияние 2 упорядоченных массивов в один
    private void merge(Comparable[] left, Comparable[] right, Comparable[] arr) {
        int iFirst = 0;        
        int iSecond = 0;         
        int iMerged = 0;
            
        //бежим, пока не дойдем до конца одного из массивов
        while (iFirst < left.length && iSecond < right.length) {
            //если элемент в левом массиве больше, чем в правом
            if (left[iFirst].compareTo(right[iSecond]) < 0) {
                //то добавляем элемент из левого
                arr[iMerged] = left[iFirst];
                //и двигаемся в левом на 1
                iFirst++;
            } else {
                //иначе добавляем элемент из правого
                arr[iMerged] = right[iSecond];
                //двигаемся в правом на 1
                iSecond++;
            }
            //в любом случае увеличиваем результирующий массив
            iMerged++;
        }
        
        //оставшиеся элементы - больше последнего (максимального) элемента одного из массивов. Докопируем оставшиеся элементы.
        System.arraycopy(left, iFirst, arr, iMerged, left.length - iFirst);
        System.arraycopy(right, iSecond, arr, iMerged, right.length - iSecond);
    } //merge
} //MergeSort

Поразрядная сортировка

(N*Const)
делаем 2х мерный массив: 10 элементов, в каждом массив с остатком от деления
1 цикл по числу разрядов,
2.1 цикл по элементам с остатком от деления на номер разряда *10 (1 проход по последнему символу, потом по 2 и т.д.)
2.2 цикл в цикле по 2х мерному массиву, значения попорядку кладем обратно во входной массив (вконце 2х мерный массив чистим)
- тем самым отсортированные на прошлом шаге выстроены в нужном порядке, досортировываем след. разряд
Показать код v 
var m = new Array[Array[Int]](10).map(_=>Array[Int]())
for(i <- 1 to arr(0).toString.size) {
    for(e <- arr) {
        m(e % (i*10)) = m(e % (i*10)) :+ e
    }
    var a = 0
    for(j <- 0 until 10) {
        for(e <- m(j)) {
            arr(a) = e
            a += 1
        }
        m(j) = Array[Int]()
    }
}

Куча

(LogN)
Heap (куча) - дерево, все ветви кроме терминальных имеют 2 предка и разница в уровне не более 1
max heap - heap, где дочерние элементы меньше или равны родителю
* хранение дерева в массиве: в правой части (N/2) - листья, слева (n/2-1) - ветви
- сохранение дерева в массив идет по алгоритму BFS
- создание дерева из массива: левый дочерний элемент = 2*i+1 , правый = левый +1
двигаемя с середины вначало, чтобы сначала сформировались последние ветви с листьями,
и не нужно было обмениваться местами с родительскими ветвями
(если двигались бы с начала, то было бы много свапов, т.к. большие ветви добавлялись бы в верх дерева (для MINHEAP),
и происходил бы свап для выполнения условия минимума вкорне )
Есть сложное математическое доказательство, что heapify по массиву рабоатет в среднем за N
Показать код v 
//в худшем случае n*log(n) , в среднем N (!!!)
def heapify(n: Int,i: Int): Unit = {
    //i это новый кандидат на вершину (макс/мин)
    val l = 2*i+1
    val r = l+1
    var max = i
    //проверям вершину, что она действительно макс/мин
    if(l < n && arr(l) > arr(max)) max = l
    if(r < n && arr(r) > arr(max)) max = r
    //если нет (1 из сыновей больше/меньше), то свапаем х
    if(max != i) {
        val t = arr(i)
        arr(i) = arr(max)
        arr(max) = t
        //и проводим рекурсивно проверку на более низкого уровня
        //пока не найдем нужное место для числа
        heapify(n, max)
    }
}
//двигаемя с середины вначало, чтобы сначала сформировались последние ветви с листьями,
for(i <- arr.size/2-1 to 0 by -1) {
    heapify(arr.size, i)
}

Сортировка кучей

(N*LogN)
* Делаем из входных данных кучу:
for(i <- arr.size/2-1 to 0 by -1) {
heapify(arr.size, i)
}
* зная что в вершине (0) всегда макс/мин, свапаем его с концом массива
* продолжаем в цикле, вызываем heapify для массива -1 элемент, свапаем 0 элемент с конец-1
* и т.д. пока элементы не станут упорядочены
Показать код v 
for(i <- arr.size-1 to 0 by -1) {
    val t = arr(i)
    arr(i) = arr(0)
    arr(0) = t
    //размер массива = i (т.е. урезаем до текущей позиции)
    //максимальные элементы в нужном порядке (>i) - не трогаем
    heapify(i, 0)
}

Слияние пересекающихся интервалов

Merge Intervals (N*LogN)
сортируем интервалы по началу
заводим st,ed, если новое начало <= ed, то ed = max(ed, новый конец)
иначе добавляем интервал, смещаем st,ed
Показать код v 
def merge(intervals: Array[Array[Int]]): Array[Array[Int]] = {
    val sint = intervals.sortBy(f=>f(0))

    var ret = Array[Array[Int]]()

    var last_st = sint(0)(0)
    var last_ed = sint(0)(1)

    for(i <- 1 to sint.size - 1) {
        if(sint(i)(0) <= last_ed) {
            last_ed = Math.max( sint(i)(1), last_ed)
        } else {
            ret = ret :+ Array(last_st, last_ed)
            //println(sint(i)(0), sint(i)(1))
            last_st = sint(i)(0)
            last_ed = sint(i)(1)
        }
    }
    ret :+ Array(last_st, last_ed)
}

Топ K повторяющихся слов

Top K Frequent Words (N*LogN)
Аналалогичная задача: Top K Frequent Num
* наивное решение: делаем мапу , сортируем по повторениям, берем k первых
* так же, но используем поразрядную сортировку
* используем SortedMap (красно-черное дерево) вместо сортировки
* используем MaxHeap (scala.collection.mutable.PriorityQueue) вместо сортировки
heapify - при некоторых условиях строится за линейное время
val pq = PriorityQueue[Int]()(Ordering.by(v=>sm(v)))
Если нужна более сложная сортировка, то вместо значений используем case класс с релаизованным компаратором:
case class PValue(text: String, prio: Int) extends Ordered[PValue] {
import scala.math.Ordered.orderingToOrdered
def compare(that: PValue) = if(that.prio == prio) that.text.compare(text) else -1*that.prio.compare(prio)
}
Показать код v 
def topKFrequent(words: Array[String], k: Int): List[String] = {
    import collection.mutable.PriorityQueue

    var sm = Map[String, PValue]()
    words.foreach(n => {
        sm = sm + ( n -> ( PValue(n, sm.getOrElse(n,PValue(n,0)).prio + 1 ) ) )
    })
    val pq = PriorityQueue[String]()(Ordering.by(v=>sm(v)))
    sm.foreach(s => {
        pq.enqueue(s._1)
    })
    var ret = List[String]()
    for(i <- 1 to k) {
        if(pq.size > 0 ) ret = ret :+ pq.dequeue
    }
    ret
}

Медиана в любой момент для расширяющегося стрима

Find Median from Data Stream (LogN)
* наивная реализация - сортированный массив с бинарным поиском для вставки (logN)
поиск медианы - const
* через 2 кучи - вставка в кучу в среднем const
Левая (макс. вначале) - с числами меньше медианы
Правая (мин. вначале) - числа больше медианы.
Добавляем значение в левый список, из нее же извлекаем максимум и вставляем в правую.
Доп. проверяем, чтобы лев. была меньше правой, если нет, то еще раз переносим в правую максимум.
Медиану берем из левой (const), если размеры одинаковые, то берем среднее из лев+прав
Показать код v 
val min = scala.collection.mutable.PriorityQueue[Int]() //макс вначале
val max = scala.collection.mutable.PriorityQueue[Int]()(Ordering.Int.reverse) //мин вначале

def addNum(num: Int) {
    //вставляем новое значение в 1 очередь (где меньшие числа)
    min.enqueue(num)
    //чтобы число элементов в очередях было одинаковое
    //и чтобы все большие элементы оказались справа
    //вытолкнем максимум из меньших вправую очередь
    max.enqueue(min.dequeue)
    //доп. проверка для выравнивания
    if(min.size < max.size) {
        //минимальный эл. справа, переносим в список минимальных
        min.enqueue(max.dequeue)
    }
}

def findMedian(): Double = {
    //если число эл. в очередях одинаковое, то берем среднее от 2
    if(min.size == max.size) {
        //просто смотрим - не извлекаем
        (min.dequeue + max.dequeue) / 2.0
    } else {
        //иначе в левой части должно быть больше элементов
        min.dequeue
    }
}

Контейнер с максимальным объемом воды

Container With Most Water (N)
while(l < r)
h = Math.max( h, (r-l)*Math.min(height(l),height(r)) ) //объем
if(height(l) < height(r)) l++ //если левый меньше, то ищем выше в левой части, смещая ее на 1
иначе r--, если равно, то смещаем оба
Показать код v 
def maxArea(height: Array[Int]): Int = {
    var l = 0
    var r = height.size - 1
    var h = 0
    while(l < r) {
        h = Math.max( h, (r-l)*Math.min(height(l),height(r)) )
        if(height(l) < height(r)) {
            l += 1
        } else if(height(l) > height(r)) {
            r -= 1
        } else {
            l += 1
            r -= 1
        }
    }
    h
}

Группы неповторяющихся подстрок в строке

Partition Labels (N)
//проверяем последнее вхождение каждой буквы (делаем маппу )
m += (s(i)->Math.max( m.getOrElse(s(i),-1), i))
//находим максимум всех вхождений букв до (max = max(max, cur))
last = Math.max(last, m(s(i)))
//если текущая позиция == максимуму от всех букв до,
//то значит дальше ни одна буква до уже не встерчается - это граница партиции
if(last == i) println(last - start + 1)
Пример: "ababcbacadefegdehijhklij" - не повторяющиеся партиции: "ababcbaca", "defegde", "hijhklij"
Показать код v 
def partitionLabels(s: String): List[Int] = {
    //последнее вхождение каждой буквы
    var ret = List[Int]()
    var m = Map[Char, Int]()
    for(i <- 0 until s.size) {
        m += (s(i)->Math.max( m.getOrElse(s(i),-1), i))
    }
    var last = -1
    var start = 0
    //максимум вхождения всех букв до (включая предыдущие)
    for(i <- 0 until s.size) {
        last = Math.max(last, m(s(i)))
        //если текущая позиция == максимум вхожденя всех букв до, то дальше эти буквы не встречаются - это граница партиции
        if(last == i) {
            ret = ret :+ (last - start + 1)
            start = last + 1
        }
    }
    ret
}

Непрерывное число одинаковых букв в строке, где можно сделать K замен одинаковых букв

Longest Repeating Character Replacement (N)
усложненная весия Непрерывное число 1 в последовательности, но может быть K пропусков
Но строка состоит из разных букв. Во время сведения 2 пойнтеров создаем маппу с частотой букв и определяем максимально повторяемую букву.
Если ширина окна - самая повторяемая буква > K, то левый край смещаем и уменьшем частоту левой буквы.
??? Макс.счетчик иногда будет содержать ошибки, но максимальное окно будет содержать максимально повторяемый символ, в этот момент mostFreqLetter имеет верное значение.
Показать код v 
def characterReplacement(s: String, k: Int): Int = {
    var freq = Map[Char, Int]()
    var left = 0
    var mostFreqLetter = 0
    var max = 0
    for(right <- 0 until s.size) {
        freq = freq + (s(right) -> (freq.getOrElse(s(right), 0) + 1))
        mostFreqLetter = Math.max(mostFreqLetter, freq(s(right)) )
        if(right-left+1 - mostFreqLetter > k) {
            freq = freq + (s(left) -> (freq.getOrElse(s(left), 0) - 1))
            left += 1
        }
        max = Math.max(right-left+1, max)
    }
    max
}

Медиана скользящего окна, размером K

Sliding Window Median (NLogN)
* Можно решить через сортированный массив, до K, добавляем, после левый край удаляем, правый добавляем через бинарный поиск
Тогда операции добавление, удаление = N (т.к. требует смещения элементов), получение медианы = const * Можно решить через 2 TreeSet по аналогии с Медиана в любой момент для расширяющегося стрима
(Но PriorityQueue заменено на TreeSet, т.к. удаление элемента из PriorityQueue = N).
Данный способ даст logN время вставки и удаления, и const время поиска медианы
Особенности:
* Т.к. в значениях могут быть дубли, то в TreeSet храним индексы, а сортировку задаем по значению
implicit val valOrd: Ordering[Int] = (x: Int, y: Int) => {
    if(nums(x) != nums(y)) {
        nums(x).compare(nums(y))
    } else {
        x.compare(y)
    }
}
* Вначале добавляем в меньший сет и балансируем, чтобы число элементов в левом <= правого.
* Левую сортируем по убыванию, чтобы вначале был макс.
Левый край удаляем из обоих сетов
Правое значение добавляем в правый сет, переносим минимум в левый
* Еще раз балансируем
* Медиана будет на середине 2 этих куч
Показать код v 
val nums = Array(5,2,2,7,3,7,9,0,2,3)
val k = 9

implicit val valOrd: Ordering[Int] = (x: Int, y: Int) => {
    if(nums(x) != nums(y)) {
        nums(x).compare(nums(y))
    } else {
        x.compare(y)
    }
}

var min = scala.collection.immutable.TreeSet[Int]()(valOrd.reverse)
var max = scala.collection.immutable.TreeSet[Int]()(valOrd)
var ret = Array[Double]()

def balance() = {
    while(min.size > max.size) {
        val max_left = min.head
        min = min - max_left
        max = max + max_left //move min right
    }
}

def getMedian() = {
    if(min.size == max.size) (nums(min.head)/ 2.0+nums(max.head)/ 2.0) 
    else nums(max.head).toDouble
}

for(i <- 0 until k) {
    min = min + i
}
balance()
ret = ret :+ getMedian()
//print(getMedian() + " ")
//println(min.map(x=>nums(x)), max.map(x=>nums(x)))

for(i <- k until nums.size) {
    min = min - (i-k)
    max = max - (i-k)

    max = max +i //добавляем в правую часть
    val max_r = max.head
    max = max - max_r
    min = min + max_r //в левую переносим минимум из правой

    balance() //балансируем

    //print(getMedian() + " ")
    ret = ret :+ getMedian()
    //println(min.map(x=>nums(x)), max.map(x=>nums(x)))
}
ret

Максимум скользящего окна, размером K

Sliding Window Maximum (N)
* можно решить через сортированный массив за NlogK
* Более эффективный вариант - двунаправленная очередь размером K
- Удаляем из головы (первые попавшие), если они выходят за окно
- Удаляем из конца (последние попавшие), если конец меньше нового добавляемного элемента (повторяем в цикле)
-- после этого очередь или будет пуста, или в ней будет 1 макс. элемент в голове
(Вероятно, можно использовать просто массив, где слева максимум, справа последнее вошеднее число)
- добавляем новый элемент - он будет или 1 или вонце очреди вторым
- голова очереди = макс, добавляем ее в результат
Показать код v 
var q = scala.collection.mutable.ArrayDeque[Int]()
var ret = Array[Int]()
//идем по массиву
for (i <- 0 until nums.size) {
    //если индекс выходит за пределы окна i - k + 1 - удаляем его
    if(!q.iterator.isEmpty && q.head < i-k+1) {
        q.removeHead()
    }
    //в цикле удаляем все элементы справа, кто меньше нового элемента
    //  тем самым мы всегда будем иметь 1 элемент с максимумом в списке
    while(!q.iterator.isEmpty && nums(q.last) < nums(i) ) {
        q.removeLast()
    }
    //добавляем новый элемент
    q = q :+ i
    if(i >= k-1) {
        //добавляем элемент из списка в результат
        ret = ret :+ nums(q.head)
    }
}

Проверка идентичности деревьев

Same Tree (N)
Обычный BFS, но передаем в рекурсии tuple из 2 ветвей.
Внутри проверки: 1 нул, другое не нул; оба не нул, но отличие в значении
Показать код v 
var same = true
def trav(n: (TreeNode, TreeNode)): Unit = {
    if(!same || (n._1 == null && n._2 == null)) return;
    if((n._1==null) != (n._2==null)) same = false
    else if(n._1.value != n._2.value) same = false
    else if(n._1 != null && n._2 != null) {
        trav((n._1.left, n._2.left))
        trav((n._1.right, n._2.right))
    }
}
trav((p,q))
same

Проверка дерева на симметричность

Symmetric Tree (N)
Обычный BFS, но идем одновременно по левой ветви и по правой, для этого передаем tuple
Проваливание глубже по _1 идет стандартно: сначала по левой части, потом по правой; у _2 - наоборот: право, затем лево
Внутри проверки: 1 нул, другое не нул; оба не нул, но отличие в значении
Показать код v 
def isSymmetric(root: TreeNode): Boolean = {
    if(root == null) return true
    var sym = true
    def trav(n: (TreeNode, TreeNode)): Unit = {
        if(!sym || (n._1 == null && n._2 == null)) return;
        if((n._1==null) != (n._2==null)) sym = false
        else if(n._1.value != n._2.value) sym = false
        else if(n._1 != null && n._2 != null) {
            trav((n._1.left, n._2.right))
            trav((n._1.right, n._2.left))
        }
    }
    trav((root.left,root.right))
    sym
}

Проверка на сбалансированность дерева (отличие глубины <= 1)

Balanced Binary Tree (N)
Т.к. нам нужно сравнивать 2 ветви, то начинать нужно снизу
if(n == null) return 0
и постепенно подниматься наверх увеличивая и сравнивая глубину.
return Math.max(l, r) + 1
Показать код v 
var balanced = true
def trav(n: TreeNode): Int = {
    if(n == null) return 0
    var l = trav(n.left)
    val r = trav(n.right)
    if(balanced && Math.abs(l-r) > 1 ) balanced = false
    Math.max(l, r) + 1
}
trav(p)
balanced

Ветви дерева, которые дают targetSum

Path Sum II (N)
Т.к. нужно дойти до конца ветви, то идем сверху-вниз (пока есть дочерние элементы)
Передаем в параметрах текущую сумму и лист с путем до суммы
Если сумма равна таргету, то добавляем путь в результат
Показать код v 
def pathSum(root: TreeNode, targetSum: Int): List[List[Int]] = {
    var ret = List[List[Int]]()
    if(root == null) return ret
    def trav(n: TreeNode, sm: Int, l: List[Int]): Unit = {
        if(n.left != null) trav(n.left, sm + n.left.value, l :+ n.left.value)
        if(n.right != null) trav(n.right, sm + n.right.value, l :+ n.right.value)
        if(n.left == null && n.right == null && targetSum == sm) {
            //println(n.value, sm, l)
            ret = ret :+ l
        }
    }
    trav(root, root.value, List(root.value))
    ret
}

Число неполных путей в дереве, которые дают targetSum

Path Sum III (N)
Начало решения похоже на Ветви дерева, которые дают targetSum
Вместо сохранения листа с путем, сохраняем ключ: сумма -> счетчик числа путей.
Проверяем переданную сумма - таргет. Если пути с новой суммой не было, то создаем = 1, иначе +1
Показать код v 
def trav(n: TreeNode, csm: Int, psm: Map[Int, Int]): Unit = {
    if(n == null) return;
    val nsm = csm + n.value 
    var psm2 = psm
    //если текущая сумма - таргет, есть в маппе, то значит есть часть пути, которая дает target
    cnt += psm2.getOrElse(nsm-targetSum,0)
    //добавляем в мапу новое значение, если уже есть то +1 повтор
    psm2 = psm2 + (nsm -> psm2.getOrElse(nsm,0)+1 )    
    
    if(n.left != null) trav(n.left, nsm, psm2)
    if(n.right != null) trav(n.right, nsm, psm2)
}
trav(root, 0, Map(0->1))

B* дерево

(N*LogN)
Подробное описание: Oracle: реализация btree индекса
Визуализация: B+ Tree Visualization
состоит из блоков, где каждый элемент блока имеет ссылки на меньший (слева) и больший/равный (справа) блок ниже
блок/лист ограничен размером и при достижении его разбивается на 50/50 (или 90/10 вконце)
средний/последний элемент переносится вверх и блок разбивается на 2 части:
элемент разделения уходит направо, перенесенный наверх элемент рекурсивно разделяет верхний блок (если нужно) - т.е. разделение идет снизу вверх
минусы:
дорого удалять; занимает много места, т.к. блоки редко заполнены на максимум; дорого разделять (вставлять)
плюсы:
быстрый доступ из-за малой высоты; оптимзированы под кэш и быстрое чтение с диска блоками
отличие от просто b дерева
* элементы ветвления дублируются в листовых блоках
* между листьями есть ссылки вперед/назад

Log-structured merge-tree

(N*LogN)
Lsm - Log-structured merge-tree — журнально-структурированное дерево со слиянием
Подробное описание: LSM дерево: быстрый доступ по ключу в условиях интенсивной вставки
дерево для элементов в памяти (т.к. допустимы дубли и нужно последовательное чтение)
массив в памяти с выгруженными деревьями из памяти с доп. метаданными: макс/мин значения ключа
поиск идет по дереву в памяти, если не найдено, то проверяются массив выгруженных
+ есть доп. процесс сжатия дубликатов в выгруженных деревьях

Trie - префиксное дерево

(N*LogN)
Подробное описание: Trie.scala
используется для поиска частоты слова в тексте
нода где лежит хэш массив из букв слова, при добавлении похожего слова:
* счетчик букв увеличиваем на 1
* на последней совпадающей букве добавляем хэш массив на новые буквы
т.е. это получается хэш массив - хэш массивов с точек разветвления (смены буквы)
Показать код v 
class TrieNode {
    var cnt: Int = 0
    var abc: Map[Char, TrieNode] = Map()
}

class Trie {
    val root: TrieNode = new TrieNode()
    
    //вставить строку в дерево
    def insert(str: String): Unit = {
        var cur_node = root
        for(c <- str) {
            //ищем по букве
            if(!cur_node.abc.contains(c)) {
                //если буква не найдена, то добавляется мапа
                cur_node.abc = cur_node.abc ++ Map(c -> new TrieNode())
            }
        
            cur_node = cur_node.abc(c)
            cur_node.cnt += 1
    
        }
    } //insert
    
    //поиск строки в дереве: найденная строка, число повторов в тексте
    def find(str: String): (String, Int) = {
        var cur_node = root
        var prev = ""
        for(c <- str) {
            prev += c
            if(!cur_node.abc.contains(c)) {
                return (prev, cur_node.cnt)
            } else {
                cur_node = cur_node.abc(c)
            }
        }
        return (prev, cur_node.cnt)
    }
}

Кодирование хаффмана (сжатие)

(N*LogN)
кодирование хаффмана (сжатие) - это разновидность Trie - префиксное дерево (обычно решается через Кучу, но можно и через trie)
создается дерево, где самые часто встечающиеся буквы свеху закодированы максимально короткой фразой
при архивации происходит замена буквы на более которкие аналоги, если нет соответствия, то берется само значение

Максимальный по сумме подмассив

Maximum Subarray (N)
Решается через Sliding window.
Идем по массиву, если новое число больше накопленной суммы и сумма меньше 0, то сбрасываем сумму на текущий элемент (сдвигаем левый край окна)
Иначе (число меньше суммы или число больше 0) добавляем к сумме.
На каждом шаге определяем максимум
Показать код v 
def maxSubArray(nums: Array[Int]): Int = {
    var ret_sum = Int.MinValue
    var max_value = ret_sum
    for(i <- 0 until nums.length) {
        if(nums(i) > ret_sum && ret_sum < 0) {
            ret_sum = nums(i)
        } else {
            ret_sum = nums(i) + ret_sum
        }
        max_value = Math.max(max_value, ret_sum)
    }
    max_value
}

Лучшее время для 1 продажи акций

Best Time to Buy and Sell Stock (N)
* Чем то похоже на задачу Контейнер с максимальным объемом воды
Двигаем Sliding window с левого края, правый край всегда увеличивается, а левый приравнивается правому, если он больше правого.
Запоминаем максимум на каждом шагу
* Другой подход: определяем минимум сначала, вычитаем текущее значение, сравниваем с максимумом
Показать код v 
def maxProfit(prices: Array[Int]): Int = {
    var l = 0 
    var r = 1
    var ret = 0
    while(l<r && r < prices.size) {
        ret = Math.max(ret, prices(r) - prices(l))
        if(prices(l) > prices(r)) {
            l = r
        }
        r += 1
    }
    ret
}

Лучшее время для нескольких покупок и продажи акций

Best Time to Buy and Sell Stock II | Best Time to Buy and Sell Stock with Transaction Fee (N)
Решается через динамическое программирование (когда новое сотстояние системы, зависит от запомненного предыдущего) и машины состояний (State machine)
Рисуем возможные состояния системы и переходы между:
1. B/S - может остаться в том же состоянии (действие NO)
2. S - чтобы перейти в состояние (S - факт продажи) = B (из состояния после покупки) - P (цена продажи)
3. B - чтобы перейти в состояние (B - факт покупки) = S (из состояния после продажи) + P (цена покупки) - Fi (налог на продажу)
Переводим это в код:
buy = Math.max(p_buy, p_sell + price)
sell = Math.max(p_sell, p_buy - price)
Показать код v 
def maxProfit(prices: Array[Int]): Int = {
    var p_buy = 0
    var p_sell = -prices(0)
    var buy = 0
    var sell = 0
    for (price <- prices) {
        buy = Math.max(p_buy, p_sell + price)
        sell = Math.max(p_sell, p_buy - price)

        p_buy = buy
        p_sell = sell
    }
    buy
}

Лучшее время для нескольких покупок и продажи акций с кулдауном после покупки

Best Time to Buy and Sell Stock with Cooldown (N)
Принцип решения как у Лучшее время для нескольких покупок и продажи акций. Меняется конечный автомат состояний:
B = max(B, R) //перейти в состояние после покупки можно после кулдауна
S = max(S, B-P) //перейти в состояние после продажи, можно после покупки - цена
R = S+P //в состояние кулдауна переходим из состояние продажи + цена продажи

Показать код v 
def maxProfit(prices: Array[Int]): Int = {
    var buy = 0
    var sell = 0
    var rest = 0

    var p_buy = 0
    var p_sell = -prices(0)
    var p_rest = Integer.MIN_VALUE
    for (price <- prices) {
        buy = Math.max(p_buy, p_rest)
        sell = Math.max(p_sell, p_buy - price)
        rest = p_sell + price

        p_buy = buy
        p_sell = sell
        p_rest = rest
    }
    Math.max(buy,rest)
}

N чисел фибоначи

Fibonacci Number (N)
все задачи, у которых след. решение зависит от предыдущих шагов (back tracking + memorization) накопительно решается одинаково:
массив промежуточных значений записываем решение в след. ячейку массива, после считывает пред. накопленные значения
В данном случае решается через стек, сразу записываем значение для 0 и 1, след. шагами извлкаем 2 последних числа.
И снова записываем последнее и сумму последнего и предпоследнего
Показать код v 
def fib(n: Int): Int = {
    var stack = scala.collection.mutable.Stack[Int]()
    stack.push(0)
    for (i <- 1 to n) {
        if(i==1) {
            stack.push(1)
        } else {
            val n1 = stack.pop()
            val n2 = stack.pop()
            stack.push(n1)
            stack.push(n1+n2)
        }
    }
    stack.pop()
}

Число различных путей до конца лестницы длиной N

Climbing Stairs (N)
Решается через back tracking + memorization - след. шаг = сумме 2 предыдущих шагов
Для 1 и 2 шага задаются начальные значения.
Показать код v 
var sm = 0
var arr = Array[Int]()
for (i <- 1 to n) {
    if(i == 1) {
        sm = 1
    } else if(i == 2) {
        sm = 2
    } else {
        sm = arr(arr.size-1) + arr(arr.size-2) //сумма предыдущих шагов
    }
    arr = arr :+ sm
}
arr.last

Минимальная стоимость подъема по лестнице

Min Cost Climbing Stairs (N)
Решается через back tracking + memorization - задается стоимость 1 ступеньки
Дальнейшие шаги = текущая стоимость + мин (пред. стоимость ; пред.предыдущая стоимость) //минимальное от 2 предыдущих шагов, т.к. можно шагнуть 1 или 2 ступеньки
Показать код v 
var arr = Array[Int]()
for (i <- 0 until cost.size) {
    var sm = 0
    if(i <= 1) {
        sm = cost(i) //1 шаг = 1 стоимости 
    } else {
        sm = cost(i) + Math.min(arr(arr.size-1), arr(arr.size-2)) //минимальное от предыдущих 2 шагов и текущего
    }
    arr = arr :+ sm
}
Math.min(arr(arr.size-1), arr(arr.size-2))

Число уникальных путей робота на поле

Unique Paths (N)
Робот может ходить только вправо и вниз
Решается через back tracking + memorization: создаем обновляемую матрицу, инициализируем ее 1
Шагаем по клеткам и число путей до тек. ячейки = число путей до ячейки выше + левее.
Стартуем с позиции 1,1
Показать код v 
var arr = Array.ofDim[Int](m, n).map(m=>m.map(x=>1))
for(i <- 1 until m) {
    for(j <- 1 until n) {
        //след. шаг это пред. шаг по вертикали и горизонтали
        arr(i)(j) = arr(i-1)(j) + arr(i)(j-1)
    }
}
arr(arr.size-1)(arr(0).size-1)

Все возможные подмассивы массива

Subsets (N^2)
Решается через back tracking + memorization: шагаем по входным данным и промежуточному результату
Первый шаг: пустой массив, потом добавляем промежуточный результат + входное число
Показать код v 
var ret = List(List[Int]()) //начинаем с пустого
for(n <- nums) { //для каждой цифры на входе
    for(v <- ret) { //для каждого промежуточного результата
        ret = ret :+ (v :+ n) //расширяем промежуточный результат на число из входа и добавляем в результат
    }
}

Все возможные перестановки числе в массиве

Permutations (N^3)
* Начало как у Все возможные подмассивы массива (back tracking + memorization):
шагаем по входным данным и промежуточному результату
Первый шаг: первое число кладем в результат
Добавляется доп цикл по каждому числу текущего результата из цикла выше
Добавляем в результат начало из результата (2) до точки цикла 3, число из входа(цикл 1) + остаток из результата (2) после точки 3
Показать код v 
var ret = List(List[Int](nums(0)))
for (n <- nums.slice(1, nums.size)) {
    for(v <- ret) {
        for (i <- 0 to v.size) {
            ret = ret :+ (((v.take(i) :+ n ) ++ v.slice(i, v.size)))  //цифру в произвольное место
        }
    }
}
ret.filter(_.size == nums.size)
* Альтернативный вариант решения черзе BFS описан в geeksforgeeks Для каждой позиции входного массива, свапаем ее с beg (изначально =0) и повторяем рекурсивно для beg+1.
После рекурсивного вызова возвращаем назад
Тем самым будут перебраны все варианты перестановок.
Показать код v 
var res = List[List[Int]]()
def dfs(num: Array[Int], beg: Int): Int = {
    if(beg >= num.size) {
        res = res :+ num.toList
        return 0
    }
    for(i <- beg until num.size) { //для каждой позиции
        var t = num(beg) //свапаем с начальной
        num(beg) = num(i)
        num(i) = t

        dfs(num, beg+1) //рекурсивно повторяем для след. элемента (проваливаемся вниз по дерево)

        t = num(beg) //возвращаем назад (поднимаемся вверх по дереву)
        num(beg) = num(i)
        num(i) = t
    }
    1
}
dfs(nums, 0)

Все варианты валидных скобок размером N

Generate Parentheses (N*LogN)
Решается через dfs (dfs(l: Int, r: Int, s: String)): в левую часть рекурсии добавляем открывающие скобки (l < n), в правую закрывающие (r < l)
Добавляем, пока размер строки не будет = нужному * 2 (левая + правая).
Показать код v 
def generateParenthesis(n: Int): List[String] = {
    var ret = List[String]()
    def dfs(l: Int, r: Int, s: String): Int = {
        if(s.size == n*2) { //если рзамер строк = число скобок *2 (т.к. левая и правая)
            ret = ret :+ s //добавляем в резальтат
            return 0
        }
        if(l < n) //если левых скобок меньше чем нужно, то добавляем
            dfs(l+1, r, s + "(")
        if(r < l) //если правых меньше, чем левых, тоже добавляем
            dfs(l, r+1, s + ")")
        
        1
    }
    dfs(0,0, "")
    ret
}

Комбинации массива, которые в сумме дают таргет

Combination Sum (N*LogN)
Решение похоже на Все возможные перестановки числе в массиве - решается черзе dfs.
Цикл по каждому числу, если оно меньше таргета, то рекурсивно вызываем dfs:
передаем числа после текущего и таргет-текущее число + формируем список кандидатов
если таргет при вызове = 0, то выходим из рекурсии, добавляем в ответ
Показать код v 
def combinationSum(candidates: Array[Int], target: Int): List[List[Int]] = {
    var ret = List[List[Int]]()
    def dfs(cand: Array[Int], t: Int, path: List[Int]): Int = {
        if(t<=0) {
            ret = ret :+ path
            return 0
        }
        for(i <-0 until cand.size) {
            if(cand(i)<=t) {
                dfs(cand.slice(i, cand.size), t-cand(i), path:+cand(i))
            }
        }
        1
    }
    dfs(candidates, target, List[Int]())
    ret
}

Количество простых чисел до числа

Count Primes (N log (log N))
Решето эратосфена (back tracking + memorization)
Создаем массив длинной в число, с признаком простого, заполняем 1
Если след. число в массиве, то оно простое, все множетили помечаем сложными:
Стартуем с 2 до n/число+1, результат умножения ставим = 0
Показать код v 
var arr = Array.fill(n+1){true}
var ret = 0
for (i <- 2 to n) {
    if(arr(i)) {
        ret += 1
        for(j <- 2 to n/i+1) {
            if(i*j <= n) arr(i*j) = false
        }
    }
}

Поворот изображения на 90 градусов.

Rotate Image (N)
Делается в 2 захода:
* транспонируем - меняем колонки со строками
matrix(col)(row) = matrix(row)(col)
* меняем колонки местами
matrix(row)(col) = matrix(row)(matrix(row).size - col-1)
Показать код v 
for (row <- 0 until matrix.size) {
    for(col <- row until matrix(row).size) {
        val t = matrix(col)(row)
        matrix(col)(row) = matrix(row)(col)
        matrix(row)(col) = t
    }
}
for (row <- 0 until matrix.size) {
    for(col <- 0 until matrix(row).size/2) {
        val t = matrix(row)(col)
        matrix(row)(col) = matrix(row)(matrix(row).size - col-1)
        matrix(row)(matrix(row).size - col-1) = t
    }
}

Число степень 2?

Power of Two (1)
степень 2 - это 1, 10, 100 и т.д., по этому -1 обнуляет первый бит, а остальные делает 1
и 100 & 011 всегда дает 0:
(n & n-1) == 0
Показать код v 
def isPowerOfTwo(n: Int): Boolean = {
    n > 0 && (n & n-1) == 0
}

Число степень 4?

Power of four (1)
Решается аналогично Число степень 2? + доп. проверка:
у степени 4 в четных позициях 0
(n & Integer.parseInt("01010101010101010101010101010101", 2) )
Показать код v 
(n > 0) && 
((n & n-1) == 0) && 
(n & Integer.parseInt("01010101010101010101010101010101", 2) ) != 0

Число единиц в каждом бите числа

Counting Bits (N)
Решается через back tracking + memorization.
Начинаем с 0 - запоминаем в результат, что в нем 0 бит
Следующим шаги это число единиц от предыдущего шага = число без последнего бита i >> 1 (или i/2)
+ число единиц в последнем бите: i&1 (или i%2 )
Показать код v 
var ret = Array[Int](0)
for (i <- 1 to n) {
    //ret = ret :+ ( ret(i>>1) + (i&1))
    ret = ret :+ ( ret(i/2) + i%2)
}
ret

Поменять биты местами (лево-право) в числе

Reverse Bits (N)
Проходимся по каждому из 32 бит
Расширяем результат на 1 бит справа и добавляем крайний правый бит входного числа.
Сдвигаем вправа входное число на 1 бит
Показать код v 
var n2 = x
var res = 0
for (i <- 0 until 32) {
    res = (res << 1) | (n2 & 1) //расширяем влево результат и берем крайний правый бит
    n2 = n2 >> 1 //удаляем крайний правый бит
}
res

Инвертировать биты на месте в числе

(N)
Инвертировать лидирующие 0 не надо, по этому первым шагом делаем маску из 1 длиной в число бит входного числа.
Для этого делаем И входного числа с маской из 1 (~0) и смещаем на 1 разряд, пока результат не станет = 0 (конец числа достигнут)
while((mask & n) != 0) mask = mask << 1
Далее инвертируем входное число и отсекаем лидирующие 1 нашей маской
Показать код v 
var mask: Int = ~0
//смещаем маску из 1 вправа, пока and не даст 0 - т.е. мы дошли до края числа
//получаем маску 111000 (где 0 это размер бвышего числа)
while((mask & n) != 0) mask = mask << 1
//инвертируем число и накладываем маску xor, чтобы отсечь единицы слева
~n ^ mask

Число различных битов в 2 числах

Hamming Distance (N)
Делаем XOR 2 чисел, где в битах 1, там разные значения
В цикле по каждому из 32 битов смотрим 1 в правом конце (&1), смещаем вправо на 1 разряд число
Показать код v 
var res = x ^ y
var cnt = 0
for(i <- 0 until 32) {
    cnt += res & 1 // подсчитываем их
    res = res >> 1 //постепенно смещая
}
cnt

Число различных битов в N чисел

Total Hamming Distance (N)
Нужно сделать тоже самое, что в Число различных битов в 2 числах, но для массива чисел
Расстояние хамминга для массива битов = число 0 * число 1.
Для определения этого числа для каждого бита смещаем до него и берем его значение: (nums[i] >> j) & 1
Показать код v 
public int totalHammingDistance(int[] nums) {
    int total = 0, n = nums.length;
    for (int j=0;j<32;j++) {
        int bitCount = 0;
        for (int i=0;i<n;i++) 
            bitCount += (nums[i] >> j) & 1;
        total += bitCount*(n - bitCount); //число 0 * число 1
    }
    return total;
}

Алгоритм дейкстры

(N^2)
Wiki сет уже посчитанных точек
1. начинаем с 1 точки = путь до нее = 0 (до соседей = бесконечность)
2. берем последовательно соседей начиная с минимально (минимальная куча) - записываем расстояния до них , если оно получается меньше текущего
точка считается обработанной, когда все входящие в нее ребра обработаны

Фильтр блума

Bloom filter (N)
Блум фильтр состоит из массива бит произвольной длинны
Определяется hash_num функций хэширования. Каждая хэш функция устанавливает свой бит в фильтре.
Показать код v 
//хэшировани = номер бита в битовом массиве
public long hashCode(String s, int hash_num) {
    long result = 1;
    
    //для каждого байта в строке
    for (int i = 0; i < s.length(); ++i) {
    //применяем хэш функцию под номером hash_num и обрезаем по маске
    
    //простая хэш функция = ascii значение буквы * примесь * номер функции * хэш от предыдущей функции & обрезка по маске
    //1 = (1 * 1 + 58)
    //1 = ( 0001 * 0001 + 11 0001 ) & 1111 1111 1111 1111 
    result = ((hash_num + seed) * result + s.charAt(i)) & this.hashMask;
    }
}
//добавить элемент в блум фильтр
public void add(String s) {
  //++ счетчик элементов
  cnt++;
  //для каждой хэш функции
  for(int i = 1; i <= hash_nums; i++) {
    //расчитаем номер индекса в битовой карте и установим его
    long index = hashCode(s, i);
    setBit(index);
  }
} //add

Приблизительный distinct

Aprox count distinct (N)
От каждого значения берется произвольная хэш функция
У каждого хэш значения определяется ранк первого ненулевого бита справа.
Вероятность того, что мы встретим хеш с рангом 1 равна 0.5, с рангом 2 — 0.25, с рангом r — 1 / 2^ранг
Если запоминать наибольший обнаруженный ранг R, то 2^R сгодится в качестве грубой оценки количества уникальных элементов среди уже просмотренных.

Комментариев нет:

Отправить комментарий

Подписаться на: Комментарии к сообщению (Atom)