IT enterprise algorithm and optimal solution of data structure problem — stack and queue

preface

Recently, WHILE reading a book related to algorithms, I came across this book, Code Interview Guide for Programmers: Optimal Solutions to The Problems of Algorithms and Data Structures in IT Famous Enterprises.

Design a stack with getMin functionality

• 【 title 】
  • Realize a special stack, on the basis of realizing the basic function of the stack, and then realize the operation of returning the smallest element in the stack.
• “Problem solving”
  • Since Swift does not provide a ready-made stack as a data structure, we implement a basic stack first, and then a stack that returns a minimal element. We implement this through protocols. First we define two protocols:

// We'll just focus on a few basic operations here
protocol Stack {
    associatedtype Element
    var isEmpty: Bool { get }
    var size: Int { get }
    var peek: Element? { get }
    mutating func push(_ newElement: Element)
    mutating func pop(a) -> Element?
}

// Get the minimum value
protocol getMin {
    associatedtype Element
    mutating func min(a) -> Element?
}
Copy the code

Use these two protocols to implement a stack containing Integer:

struct IntStack: Stack {
    typealias Element = Int
    
    private var stack = [Element] ()var isEmpty: Bool {
        return stack.isEmpty
    }
    
    var size: Int {
        return stack.count
    }
    
    var peek: Int? {
        return stack.last
    }
    
    mutating func push(_ newElement: Int) {
        stack.append(newElement)
    }
    
    mutating func pop(a) -> Int? {
        return stack.popLast()
    }
}
Copy the code

At this point, we have a stack with a few basic operations, and then we use this stack to implement a special stack that returns the minimum:

struct getMinStack: Stack.getMin {
    typealias Element = Int
    
    private var stackData = IntStack(a)private var stackMin = IntStack(a)var isEmpty: Bool {
        return stackData.isEmpty
    }
    
    var size: Int {
        return stackData.size
    }
    
    var peek: Int? {
        return stackData.peek
    }
    
    mutating func push(_ newElement: Int) {
        //stackData
        stackData.push(newElement)
        //stackMin
        if stackMin.isEmpty {
            stackMin.push(newElement)
        }else {
            if let minObject = min() {
                if newElement <= minObject {
                    stackMin.push(newElement)
                }
            }
        }
    }
    
    mutating func pop(a) -> Int? {
        return stackData.pop()
    }
    
    func min(a) -> getMinStack.Element? {
        if! stackMin.isEmpty {return stackMin.peek
        }else {
            return nil}}}Copy the code

Now let’s test it out:

let testArray = [3.4.5.7.6.9.2.10]
let minStack = getMinStack()
for num in testArray {
    minStack.push(num)
}
if! minStack.isEmpty {debugPrint(minStack.min()!2 / / output
}
Copy the code

A queue consisting of two stacks

• 【 title 】
  • Write a class that implements queues with two stacks and supports the basic operations of queues (Add, Poll, PEEK).
• “Answer”
  • Let’s define a Queue protocol based on the previous code

protocol Queue {
    associatedtype Element
    mutating func add(_ newElement: Element)
    mutating func poll(a) -> Element?
    mutating func peek(a) -> Element?
}
Copy the code

Implement a QueueFromStack structure:

struct QueueFromStack: Queue {
    typealias Element = Int
    var stackPush = IntStack(a)var stackPop = IntStack(a)mutating func add(_ newElement: Int) {
        stackPush.push(newElement)
    }
    
    mutating func poll(a) -> Int? {
        if stackPush.isEmpty && stackPop.isEmpty {
            debugPrint("Queue is empty!")
            return nil
        }else if stackPop.isEmpty {
            while !stackPush.isEmpty {
                stackPop.push(stackPush.pop()!)
            }
        }
        return stackPop.pop()
    }
    
    mutating func peek(a) -> Int? {
        if stackPush.isEmpty && stackPop.isEmpty {
            debugPrint("Queue is empty!")
            return nil
        }else if stackPop.isEmpty {
            while !stackPush.isEmpty {
                stackPop.push(stackPush.pop()!)
            }
        }
        return stackPop.peek
    }
}
Copy the code

Now let’s test it out:

let testArray = [1.2.3.4.5.6.7.8.9]
var queue = QueueFromStack(a)for num in testArray {
	queue.add(num)
}
        
debugPrint(queue.peek()!)/ / output 1
debugPrint(queue.poll()!)/ / output 1
debugPrint(queue.peek()!)2 / / output
Copy the code

Reverse a stack using only recursive functions and stack operations

• 【 title 】
  • When a stack is pushed 1, 2, 3, 4, and 5, the numbers from the top of the stack to the bottom are 5, 4, 3, 2, and 1, respectively. Transpose the stack, from the top of the stack to the bottom of the stack 1, 2, 3, 4, 5, which is the implementation of the stack elements in reverse order, but can only be implemented using recursive functions, no other data structure.
• “Problem solving”
  • Implement a function that removes the bottom element of the stack and returns the bottom element:

func getAndRemoveLastElement(stack: inout IntStack) -> Int {
    guard let result = stack.pop() else { return -1}
    if stack.isEmpty {
        return result
    }else {
        let last = getAndRemoveLastElement(stack: &stack)
        stack.push(result)// The stack element is removed from the bottom of the stack
        return last
    }
}
Copy the code

To reverse the stack, use the recursive function above:

func reverse(stack: inout IntStack) {
    if stack.isEmpty {
        // after getAndRemoveLastElement(stack:), each time you remove the bottom element of the stack, eventually the stack will be empty, and you'll get there
        return
    }
    /* Returns the bottom element 1->2->3 */
    let i = getAndRemoveLastElement(stack: &stack)
    reverse(stack: &stack)
    /* Now that the stack is empty, then push the bottom element of the stack in reverse order push I = 3 -> [3] push I = 2 -> [3, 2] push I = 3 -> [3, 2, 1] */
    stack.push(i)
}
Copy the code

Now let’s test it out:

let testArray = [1.2.3]
var stack = IntStack(a)for num in testArray {
    stack.push(num)
}
reverse(stack: &stack)
print(stack)/ / [3, 2, 1)
Copy the code

The cat and dog queue

• 【 title 】
  • The categories for pets, dogs and cats are as follows:

class Pet {
    private var type: String?
    init(type: String) {
        self.type = type
    }
    
    public func getType(a) -> String? {
        return type
    }
}

class Dog: Pet {
    init() {
        super.init(type: "Dog")}}class Cat: Pet {
    init() {
        super.init(type: "Cat")}}Copy the code

Implement a dog and cat queue structure, the requirements are as follows:

• Users can call the Add method to queue instances of cat or dog classes;
• You can call the pollAll method to eject all instances in the queue in the order in which they were queued.
• You can call the pollDog method to eject dog instances in the queue in the sequence in which they were added to the queue.
• You can call the pollCat method to eject the cat instances in the queue in the order in which they were added to the queue.
• The user can call the isEmpty method to check if there are still instances of dog or cat in the queue;
• A user can call the isDogEmpty method to check if there are instances of the dog class in the queue;
• The user can call the isCatEmpty method to check if there is an instance of cat in the queue.
• “Problem solving”

class PetEnterQueue {
    private var pet: Pet?
    private var count: Int?
    init(pet: Pet.count: Int) {
        self.pet = pet
        self.count = count
    }
    
    public func getPet(a) -> Pet? {
        return self.pet
    }
    
    public func getCount(a) -> Int? {
        return self.count
    }
    
    public func getEnterPetType(a) -> String? {
        return self.pet? .getType() } }class DogCatQueue {
    private var dogQ: LinkedList<PetEnterQueue>!
    private var catQ: LinkedList<PetEnterQueue>!
    private var count = 0
    
    init() {
        dogQ = LinkedList<PetEnterQueue>()
        catQ = LinkedList<PetEnterQueue>()
    }
    
    public func add(pet: Pet) {
        let timeInterval: TimeInterval = Date().timeIntervalSince1970
        let timeStamp = Int(timeInterval)
        if pet.getType() == "Dog" {
            dogQ.appendToTail(value: PetEnterQueue(pet: pet, count: timeStamp))
        }else if pet.getType() == "Cat" {
            catQ.appendToTail(value: PetEnterQueue(pet: pet, count: timeStamp))
        }else {
            fatalError("error， not dog or cat")}}public func pollAll(a) -> Pet? {
        if! dogQ.isEmpty && ! catQ.isEmpty {letdog = dogQ.last? .valueletcat = catQ.last? .valueif(dog? .getCount())! < (cat? .getCount())! {returndogQ? .last? .value.getPet() }else {
                returncatQ? .last? .value.getPet() } }else if! dogQ.isEmpty {returndogQ.last? .value.getPet() }else if! catQ.isEmpty {returncatQ? .last? .value.getPet() }else {
            fatalError("Error, queue is empty!)}}public func pollDog(a) -> Dog {
        if! isDogQueueEmpty() {returndogQ.first? .value.getPet()as! Dog
        }else {
            fatalError("Dog queue is empty!")}}public func pollCat(a) -> Cat {
        if! isCatQueueEmpty() {returncatQ.first? .value.getPet()as! Cat
        }else {
            fatalError("Cat queue is empty!")}}public func isEmpty(a) -> Bool {
        return dogQ.isEmpty && catQ.isEmpty
    }
    
    public func isDogQueueEmpty(a) -> Bool {
        return dogQ.isEmpty
    }
    
    public func isCatQueueEmpty(a) -> Bool {
        return catQ.isEmpty
    }
}	
Copy the code

Using one stack to sort another stack

• 【 title 】
  • If you want to sort a stack of integer elements from top to bottom, you can apply for only one stack. In addition, you can apply for new variables, but not additional data structures. How do I do that sort?
• “Problem solving”

func sortStackByStack(stack: IntStack) -> IntStack {
    var tempStack = stack
    // Apply the secondary stack
    var helpStack = IntStack(a)while! tempStack.isEmpty {// If all the elements of the original stack are pushed onto the secondary stack, the secondary stack is sorted from top to bottom, and the loop is stopped
        guard let cur = tempStack.pop() else { return tempStack }
        if helpStack.isEmpty {// The secondary stack is empty
            helpStack.push(cur)
        }else {// The secondary stack is not empty
            while helpStack.peek! <= cur {
                if let topElement = helpStack.pop() {
                    tempStack.push(topElement)
                }
            }
            helpStack.push(cur)
        }
    }
    // Pop the elements of the secondary stack one by one and push them back to the original stack (the original stack is empty), so the original stack is sorted from top to bottom
    while! helpStack.isEmpty {if let element = helpStack.pop() {
            tempStack.push(element)
        }
    }
    return tempStack
}
Copy the code

Now let’s test it out:

var stack = IntStack(a)let testArray = [3.4.5.7.6.9.2.10]
for num in testArray {
    stack.push(num)
}
print(sortStackByStack(stack: stack))//IntStack(stack: [2, 3, 4, 5, 6, 7, 9, 10])
Copy the code

A stack is used to solve the Hannotta problem

• 【 title 】
  • Now you can’t move directly from the leftmost tower to the right, and you can’t move directly from the leftmost tower to the left, you have to go through the middle. When the tower has N layers, print the optimal moving process and the optimal total moving steps. For example, if the number of towers is two, and the topmost tower is denoted as 1 and the lowest tower as 2, print:

  Move 1 from left to mid

  Move 1 from mid to right

  Move 2 from left to mid

  Move 1 from right to mid

  Move 1 from mid to left

  Move 2 from mid to right

  Move 1 from left to mid

  Move 1 from mid to right

  It will move 8 steps.

• 【 for 】
  • There are two ways to solve it.
  • Method 1: recursive method;
  • Method two: non-recursive method, using the stack to simulate the three towers of Hannott tower.
• Solution 1: Use recursion

func hanoiProblem(num: Int, left: String, mid: String, right: String) -> Int {
    if num < 1 {
        return 0
    }
    // Move from left to right
    return process(num, left, mid, right, from: left, to: right)}func process(_ num: Int, _ left: String, _ mid: String, _ right: String, from: String, to: String) -> Int {
    if num == 1 {/ / a layer
        if from == mid || to == mid {// Center -> left, center -> right, left -> center, right -> center
            print("Move 1 from \(from) to \(to)")
            return 1
        }else {// Left -> right -> left
            print("Move 1 from \(from) to \(mid)")
            print("Move 1 from \(mid) to \(to)")
            return 2}}/ / multi-layer
    if from == mid || to == mid {// Center -> left, center -> right, left -> center, right -> center
        let another = (from == left || to == left)?right : left
        let part1 = process(num - 1.left, mid, right, from: from, to: another)
        let part2 = 1
        print("Move \(num) from \(from) to \(to)")
        let part3 = process(num - 1.left, mid, right, from: another, to: to)
        return part1 + part2 + part3
    }else {// Left -> right -> left
        let part1 = process(num - 1.left, mid, right, from: from, to: to)
        let part2 = 1
        print("Move \(num) from \(from) to \(mid)")
        let part3 = process(num - 1.left, mid, right, from: to, to: from)
        let part4 = 1
        print("Move \(num) from \(mid) to \(to)")
        let part5 = process(num - 1.left, mid, right, from: from, to: to)
        return part1 + part2 + part3 + part4 + part5
    }
}
Copy the code

Now let’s test it out:

let num = hanoiProblem(num: 2.left: "Left", mid: "In".right: "Right")
print("It will move \(num) steps.")

Move 1 from left to middle Move 1 from middle to right Move 2 from left to middle Move 1 from right to middle Move 1 from middle to left Move 2 from middle to right Move 1 from middle to left Move 2 from middle to right Move 1 from left to middle Move 1 from middle to right It will Move 8 steps. */
Copy the code

• [Solution 2] : Do not use recursion, use stack

// The movement mode
public enum Action {
    case No  // Initial state
    case LToM/ / left - >
    case MToL/ / - > to the left
    case MToR/ / - > in the right
    case RToM/ / right - >
}
/* Adjacency irreversibility rule: If this step is left -> middle, then the next step cannot be middle -> left, because then it is not the optimal solution for the smallest number of moves
func hanoiProblem2(num: Int, left: String, mid: String, right: String) -> Int {
    / / the left the stack
    var lS = IntStack(a)/ / the stack in the middle
    var mS = IntStack(a)/ / right stack
    var rS = IntStack(a)// Put the largest integer at the bottom of each stack
    lS.push(Int.max)
    mS.push(Int.max)
    rS.push(Int.max)
    
    for i in (1. num).reversed() { lS.push(i) }var record = [Action.No]
    var step = 0
    whilerS.size ! = num +1 {// The loop stops when the right-hand stack is equal to (the number of stacks + 1), indicating that all stacks have been moved to the right-hand stack
        /* 1. The first action must be: left -> middle 2. According to the two principle of "adjacent irreversible" and "small pressure big", so the second action cannot be: left -> left and left -> middle 3. That left only in -> right, right -> in two ways of movement, and according to the "small pressure big" principle, there is only one of these two ways is in accordance with the requirements of summary, each step only one way, so each step according to the two principles to view all ways, just execute the way that meets the requirements */
        step += fStackTotStack(record: &record, preNoAct: .MToL, nowAct: .LToM, fStack: &lS, tStack: &mS, from: left, to: mid)
        step += fStackTotStack(record: &record, preNoAct: .LToM, nowAct: .MToL, fStack: &mS, tStack: &lS, from: mid, to: left)
        step += fStackTotStack(record: &record, preNoAct: .RToM, nowAct: .MToR, fStack: &mS, tStack: &rS, from: mid, to: right)
        step += fStackTotStack(record: &record, preNoAct: .MToR, nowAct: .RToM, fStack: &rS, tStack: &mS, from: right, to: mid)
    }
    return step
}

func fStackTotStack(record: inout [Action], preNoAct: Action, nowAct: Action, fStack: inout IntStack, tStack: inout IntStack, from: String, to: String) -> Int {
    guard let fTop = fStack.peek else { return 0 }
    guard let tTop = tStack.peek else { return 0 }
    if record[0] != preNoAct && fTop < tTop {// Adjacency irreversibility principle && small pressure big principle
        if let topElement = fStack.pop() {
            tStack.push(topElement)
        }
        guard let tTop2 = tStack.peek else { return 0 }
        print("Move \(tTop2) from \(from) to \(to)")
        record[0] = nowAct
        return 1
    }
    return 0
}
Copy the code

Now let’s test it out:

let step = hanoiProblem2(num: 3.left: "Left", mid: "In".right: "Right")
print("It will move \(step) steps.")
Move 1 from left to middle Move 1 from middle to right Move 2 from left to middle Move 1 from right to middle Move 1 from middle to left Move 2 from middle to right Move 1 from middle to left Move 2 from middle to right Move 1 From left to middle Move 1 from middle to right Move 3 from left to middle Move 1 from right to middle Move 1 from middle to left Move 2 from right to middle Move 1 From left to middle Move 1 from middle to right Move 2 from middle to left Move 1 from right to middle Move 1 from middle to left Move 3 from middle to right Move 1 from Move 1 from middle to right Move 2 from left to middle Move 1 from right to middle Move 1 from middle to left Move 2 from middle to right Move 1 from left to middle Move 1 from middle to left Move 1 from middle to right Move 1 from left to middle Move 1 from middle to right It will Move 26 steps. */
Copy the code

Generates an array of window maxima

• 【 title 】
  • There is an integer array arr and a window of size W that slides from the left to the right of the array, one position at a time. For example, if the array is [4,3,5,4,3,3,6,7] and the window size is 3:

[4 3 5] 4 3 3 6 7 The maximum value is 5

4 [3 5 4] 3 3 6 7 The maximum value in the window is 5

4 3 [5 4 3] 3 6 7 The maximum value in the window is 5

4 3 5 [4 3 3] 6 7 The maximum value in the window is 4

4 3 5 4 [3 3 6] 7 The maximum value in the window is 6

The maximum value in window 4, 3, 5, 4, 3 [3, 6, 7] is 7

If the array length is N and the window size is W, a total of N – W +1 Windows will be generated. Please implement a function.

Input: integer array arr, window size w.

Output: an array res of length N-w +1, where res[I] represents the maximum value for each window state. In this case, the result should return {5,5,5,4,6,7}.

• “Answer”

func getMaxWindow(array: Array<Int>, windowSize w: Int) -> Array<Int> {
    if array.isEmpty || w < 1 || array.count < w {
        return[]}2. The element in the first subscript stored in qmax is the largest element in the current subarray */
    var qmax = [Int] ()// Initialize an array of length (array.count -w + 1)
    var res = Array.init(repeating: 0.count: (array.count - w + 1))
    var index: Int = 0
    
    for i in (0..<array.count) {
        /************* Qmax entry rule ***************/
        / / qmax isn't empty
        while! qmax.isEmpty && array[qmax.last!]  <= array[i] { qmax.removeLast() }// If qmax is empty, just add the subscript
        / / if the array [qmax last!] > array[I], add the subscript directly to it
        qmax.append(i)
        
        /************* Qmax eject rule ***************/
        // If the subscript expires, delete the most recent expired element
        if let firstIndex = qmax.first {
            if firstIndex == (i - w) {
                qmax.removeFirst()
            }
        }
        
        /* This condition ensures that every element in the first window has been traversed. In this case, the subarray of the first window is [4, 3, 5], so I will know that 5 is the maximum value in the subarray until I reaches 2. Each subsequent move produces a maximum */
        if i >= w - 1 {
            if index <= res.count - 1 {// Make sure you don't cross the line
                if let fistIndex = qmax.first {
                    res[index] = array[fistIndex]
                }
                index += 1}}}return res
}
Copy the code

Now let’s test it out:

let array1 = [4.3.5.4.3.3.6.7]
print(getMaxWindow(array: array1, windowSize: 3))
let array2 = [44.31.53.14.23.93.46.27]
print(getMaxWindow(array: array2, windowSize: 4))
/ * printing results for: [5, 5, 5, 4, 6, 7] [53, 53, 93, 93, 93] * /
Copy the code

The number of subarrays whose maximum minus minimum is less than or equal to num

• 【 title 】
  • Given arr and num, return the number of subarrays that satisfy the following conditions:max(arr[i..j])-min(arr[i..j])<=numMax (arr[I..j]) represents the maximum value in the subarray ARr [I..j], and min (arr[I..j]) represents the minimum value in the subarray ARr [I..j].
• 【 for 】
  • If the array length is N, implement the time complexity of O (N) solution.
• “Answer”

func getNum(array: Array<Int>, num: Int) -> Int {
    if array.isEmpty || array.count= =0 {
        return 0
    }
    // The first element represents the subscript of the maximum value in the current subarray
    var qmax = [Int] ()// The first element represents the subscript of the minimum value in the current subarray
    var qmin = [Int] ()// Indicates the range of the array
    var i = 0
    var j = 0
    // The number of subarrays that satisfy the condition
    var res = 0
    
    while i < array.count {
        while j < array.count {
            while! qmin.isEmpty && array[qmin.last!]  >= array[j] { qmin.removeLast() } qmin.append(j)while! qmax.isEmpty && array[qmax.last!]  <= array[j] { qmax.removeLast() } qmax.append(j)// j stops expanding to the right
            ifarray[qmax.first!]  - array[qmin.first!]  > num {break
            }
            / / j expansion to the right
            j += 1
        }
        
        if let firstIndex = qmin.first {
            if firstIndex == i {
                qmin.removeFirst()
            }
        }
        
        if let firstIndex = qmax.first {
            if firstIndex == i {
                qmax.removeFirst()
            }
        }
        
        / / assuming I = 0, j = 5: [0.. 4], [0.. 3], [0.. 2], [0.. 1], [0.. 0], a total of (j - I) an eligible subarray
        Array [I..j-1]->array[I.. I] subarrays are all valid, so res += j-i
        res += (j - i)
       
        i += 1
    }
    return res
}
Copy the code

Now let’s test it out:

let array = [3.4.5.7]
print(getNum(array: array, num: 2))
/ * conform to the requirements of the array are: [3] [4] [5] [7] [3, 4] [5, 7] [4, 5] [3, 4, 5] * /
Copy the code

This is the end of this article, if you feel confused, you can directly through Xcode for step by step debugging, here is the code I wrote

Afterword.

This chapter only realized part of the title of the first chapter, and I will make it up later when I have time. As for the remaining chapters, I will make them up with my reading progress. If you enjoyed this article, please give it a thumbs up as a future inspiration. Thank you ！！！！