##Algorithms and Data Structures compendium.
###General
- Priority Queue could be usefull to find N bigest(Max-Priority Queue) or smallest(Min-Priority Queue) elements of array.
- Use loop two-pointer technique for polindrome cheking.
- Check if a number is prime
extension Int {
func isPrime() -> Bool {
guard self >= 2 else { return false }
guard self != 2 else { return true }
guard self % 2 != 0 else { return false }
return !stride(from: 3, through: Int(sqrt(Double(self))), by: 2).contains { self % $0 == 0 }
}
}###Array
- swap elements in array
private func swap<T>(_ array: inout [T], _ index1: Int, _ index2: Int ) {
guard index1 != index2 else { return }
let temp = array[index1]
array[index1] = array[index2]
array[index2] = temp
}###Loops
let array = [1,2,3,4,5,6,7,8,9,10]- while loop
var i = 0
while i < array.count {
print(array[i])
i += 1
}- while loop with next element
var i = 0
while i < array.count {
let current = array[i]
var next: Int? = nil
if i < array.count - 1 { // check if next item exists
next = array[i+1]
}
print("current: \(current), next: \(next)")
i += 1
}- for loop
for i in 0..<array.count {
print(array[i])
}- for loop with next element
for i in 0..<array.count {
let current = array[i]
var next: Int? = nil
if i < array.count - 1 { // check if next item exists
next = array[i+1]
}
print("current: \(current), next: \(next)")
}- loop two-pointer technique
var leftIndex = 0
var rightIndex = array.count-1
while leftIndex <= rightIndex {
leftIndex += 1
rightIndex -= 1
}- reversed for loop
for i in (0..<5).reversed() {
}- nested for loops
for i in 0..<array.count {
for j in i+1..<array.count {
}
}###Binary Representation
- Odd numbers always have a last bit of 1.
- Subtracting 1, from an odd number, changes the last bit from 1 to 0.
- Dividing by 2 removes the last bit from the number.
###Binary Search
func binarySearch(nums: [Int], target: Int) -> Int {
var low: Int = 0
var heigh: Int = nums.count-1
while low <= heigh {
let mid = low + (heigh - low)/2
if nums[mid] == target {
return mid
} else if nums[mid] > target {
heigh = mid - 1
} else {
low = mid + 1
}
}
return -1###Hash
- Find frequency of elements in array
func itemsFrequency<T: Hashable>(in array: [T]) -> [T: Int] {
var itemsFrequencyMap: [T: Int] = [:]
for item in array {
if let currentFrequency = itemsFrequencyMap[item] {
itemsFrequencyMap[item] = currentFrequency + 1
} else {
itemsFrequencyMap[item] = 1
}
}
return itemsFrequencyMap
}###LinkedList
class ListNode<T: Hashable> {
var val: T
var next: ListNode?
init(_ val: T) { self.val = val; self.next = nil; }
init(_ val: T, _ next: ListNode?) { self.val = val; self.next = next; }
}- LinkedList to ArrayList
func array<T: Hashable>(from head: ListNode<T>?) -> [Int] {
var array = [T]()
var head = head
while head != nil {
array.append(head!.val)
head = head?.next
}
return array
}- Fast and Slow (also known as the tortoise and hare algorithm) It uses two pointers to determine traits about directional data structures.
Problem 1: Middle of Linked List
func middleNode<T: Hashable>(_ head: ListNode<T>?) -> ListNode<T>? {
var slow: ListNode<T>? = head
var fast: ListNode<T>? = head
while (fast != nil && fast?.next != nil) {
slow = slow?.next
fast = fast?.next?.next
}
return slow
}Problem 2: Detect Cycle in Linked List
func detectCycle<T: Hashable>(_ head: ListNode<T>?) -> Bool {
guard let head = head else { return false }
var slow: ListNode<T>? = head
var fast: ListNode<T>? = head.next
while (slow != fast) {
if (fast == nil || fast?.next == nil) {
return false;
}
slow = slow?.next
fast = fast?.next?.next
}
return true
}- Node print prettifier
extension ListNode: CustomStringConvertible {
public var description: String {
guard let next = next else { return "\(val)" }
return "\(val) -> " + String(describing: next)
}
}- Reverse Linked List
func reverseList(_ head: ListNode?) -> ListNode? {
var prev: ListNode? = nil
var curr = head
while curr != nil {
let next = curr?.next
curr?.next = prev
prev = curr
curr = next
}
return prev
}