preface

Tao long and Tang Qiao’s way of interview, just out of the first time to start, but also while the company is not very busy, can calm down to read this book. The author thinks that the biggest highlight of this book is the algorithm foundation in chapter 2, so I want to record the learning process of the algorithm in the form of notes, and at the same time, I can read it in the first time when I forget.

This part of the code is explained via Swift, so it is also good for beginners who want to learn Swift. In this chapter algorithm problem author simple analysis, need to see detailed we can choose to buy the original book to learn.

1 dictionary and set: Given an array of integers and an object value, determine whether the sum of two numbers in the array equals the object value.

This kind of problem is relatively basic in LeetCode, and the swift code in the book is also relatively simple.

func twoSum (nums: [Int], _ target: Int) -> Bool {// initialize set var set = set <Int>() // iterate through array for num in nums {// determine whether set contains the target value minus the current value if set.contains(target -) Set.insert (num)} set.insert(num)} set.insert(num)}Copy the code

This method has a time of O(n), which is much better than the O(n^2) method of selecting a number and then iterating through the entire array.

1.2: Modify on the basis of this problem: given an integer array with the sum of only two numbers equal to the target value, find the ordinal number of these two numbers in the array.

The method in the book is to get the serial number easily, using a dictionary, looking at the code

Func twoSum (nums: [Int], _ target: Int) -> [Int] {var dict = [Int: For (I,num) in nums.enumerated() {// Fetch the previously saved index from the dict dictionary and check whether there is an index value if let lastIndex = Dict [target-num] {return [lastIndex, dict[target-num] { Dict [num] = I}} fatalError("No valid output!") )}Copy the code

Clever use of the dictionary features, with key to represent the value of the array, by judging whether the dictionary contains the key of the target value to take out the index.

2 String: Given a string, it is required to be reversed in word order.

If it is “hello world”, then the inverted result will be “world hello”. This is more general, but note the special handling of Spaces. Look at the code:

fileprivate func _reverse<T>(_ chars: inout[T], _ start: Int, _ end: Var start = start, end = end while start < end {//start end Start += 1 end -= 1}} fileprivate func swap<T>(_ chars: inout[T], _ p: Int, _ q: Int){// (chars[p], chars[q]) = (chars[q], chars[p])}Copy the code

The above method is the implementation of the string inversion, let’s look at the individual inversion of each word. It should be noted that the inversion of the word needs to be judged on the space, see the complete implementation code.

func reverseWords(s: String?) -> String? Guard let s = s else {return nil} var chars = Array(s.charters), _reverse(&chars, start, chars. Count - 1) for I in 0.. < chars. Count {/ / when I the last one is equal to the array or meet with space reverse string if I = = chars. Count - 1 | | chars [I + 1) = = "" {/ / will be inversion of each individual word _reverse(&chars, start, I) start = I + 2}} return String(chars)}Copy the code

Comments:

1: Take the input string “Hello World” as an example. Split the string into an array of small characters and then invert it into “dlroW olleH”.

2 “Then we segment the single word by judging the space and the last character in the character array, updating the start position.

In fact, Apple has provided us with a way to do this.

func reverseWords(s: String) -> String? Ponents (separatedBy:" ") // reverseString = chars.reversed().joined(separator:" ") return reverseString }Copy the code

It’s very simple, so I don’t want to repeat it. However, the time complexity of components and joined is higher than that of the preceding formula, which needs attention.

expand

If the string above is replaced by an integer, how can it be reversed?

Example: Given a 16-bit signed integer, ask to invert it to output (eg: input: 1234, output: 4321). Look at the code:

Func reverse(x:Int) -> Int {var I = 0 var t = x = 0 {I = 10 * 10 + t % I t/t = 10} if I < INT16_MIN | | I > INT16_MAX {/ / than 16-bit signed integer type 0 return 0} return I}Copy the code

This problem is also one of LeetCode’s more basic algorithms: integer inversion. Very simple, but you have to pay attention to the boundary conditions.

3 list

The author understands that a linked list is a series of storage structures that are not continuous and sequential in storage space. A linked list is formed by connecting nodes in turn. Each node has two parts: a data field and a pointer field for the next node.

Now how do you implement a linked list in Swift

1: generates a node

Class ListNode {var val: Int var next: ListNode? init(_ val: Int) { self.val = val self.next = nil } }Copy the code

2: implement head insertion method and tail insertion method head insertion method: the current node is inserted before the first node, tail insertion method: the current node is inserted after the last node in the linked list.

class List { var head: ListNode? var tail: ListNode? Func appendToHead(_ val: Int) {if head == nil {// Create head node head = ListNode(val) tail = head} else {let temp = ListNode(val) // Assign the current head address to the temp pointer field Temp. Next = head head = temp}} func appendToTail(_ val: Int) { if tail == nil { tail = ListNode(val) head = tail } else { tail! .next = ListNode(val) tail = tail! .next } } }Copy the code

Examples: 1 – > 2 – > 3 – > 5 – > 4 – > 2, when a given x = 3, return 1 – > 2 – > 2 – > 3 – > 5 – > 4. According to the solution idea given in the book, the complete linked list is divided into two new linked lists by conditional judgment (input parameter X), and then the two new linked lists are joined together into a complete linked list. Take a look at the code.

func partition(_ head: ListNode? , _ x: Int) -> ListNode? {// create 2 Dummy nodes let prevDummy = ListNode(0), postDummy = ListNode(0) var prev = prevDummy, Post = postDummy var node = head = nil {// Determine if data is less than x if node! .val < x {// less than x prev.next pointer field points to node prev.next = node prev = node! } else {// create a new list post. Next = node post = node! } // Determine the next node node = node! .next} // set tail next to nil to prevent composing ring post.next = nil // left and right concatenation (left tail points to right head) prev.next = postdummy. next return prevDummy.Copy the code

Dummy nodes are described in detail.

The code above introduces the Dummy node, which acts as a Dummy head node. The reason we introduced it is because we don’t know what the head of the new list to return is, it could be the first node of the original list, it could be in the middle of the original list, it could be at the end, or it could even be nil. The introduction of Dummy nodes neatly covers all of the above, and we can easily use dummy.next to return the desired header.

Comments:

1: create the left and right Dummy nodes, then check whether the node exists by using while.

2: If there is a relationship between the data val of the re-judgment node and the judgment condition X, if it is less than x, it will be linked to the left linked list, and if it is greater than x, it will be linked to the right linked list.

3: After executing the while, we have got the left and right lists. Finally, the left tail node points to the right head node to complete the link list.

Note: You need to set the end of the right list to nil to prevent loops. If the fast pointer and the slow pointer become equal, it means that the linked list has a ring. The specific will not be introduced here, it is relatively simple.

4 Stacks and queues

Let’s start with the basic concept of downstacks and queues: stack: First In Last Out, or FILO. The bottom person is the first to lie down and the last one to get up. Queue: A First In First Out structure, also known as FIFO. It’s like waiting in line for a ticket. The first person to come gets the ticket first.

Now that we know about stacks and heaps, let’s see how Swift writes out stacks and queues.

Protocol Stack {// AssociatedType: the associatedType is equivalent to the associatedType. When called, the associatedType Element can be set based on the Element specified by associatedType Var isEmpty: Bool {get} // stack size var size: Int {get} // stack top Element var peek: Element? {get} //mutating: If you want to modify the attributes of an instance of a protocol (enumeration), you need to use mutating to modify the instance of the protocol (enumeration), otherwise an error will be reported NewElement: Element) // Unstack mutating func pop() -> Element? }Copy the code

Implementation protocol method

Struct IntegerStack: Stack {// typeAlias: typeAlias Element = Int var isEmpty: struct IntegerStack: Stack {// typeAlias: typeAlias Element = Int var isEmpty: Bool {return stack.isEmpty} var size: Int {return stack.count} var peek: Element? {return stack.last} private var stack = [Element]() // Mutating func push(_ newElement: Element) {return stack.append(newElement)} //pop Remove the last Element in the stack mutating func pop() -> Element? { return stack.popLast() } }Copy the code

Note: the use of protocol to declare the stack properties and methods, and in the structure of the declaration array stack, the array data append and poplLast operation, complete the stack operation, relatively simple.

Let’s look at the implementation of queues:

Protocol Queue {associatedtype Element // whether the Queue isEmpty var isEmpty: Bool {get} var size: Int {get} // the first Element of the Queue var peek: Element? {get} // mutating func queue(_ newElement: Element) // mutating func dequeue() -> Element? }Copy the code

Implementation protocol method

struct IntegerQueue: Queue { typealias Element = Int var isEmpty: Bool {return left.isEmpty && right.isEmpty} var size: Int {return left.count + right.count} var peek: Element? {return left.isEmpty ? right.first : Var left = [Element]() private var right = [Element]() private var right = [Element]( Enqueue (_ newElement: Int) {right.append(newElement)} mutating func dequeue() -> Element? { if left.isEmpty { //reversed: Return left. PopLast ()} return left. PopLast ()}}Copy the code

Note: the above code uses two arrays to complete the enqueue and dequeue operations respectively, and uses right to store the enqueued elements. PopLast shows that the left isEmpty. If the left array points to the right array in reverse order, the popLast shows that the left array isEmpty. Size peek isEmpty also shows that the left array isEmpty. As for the writing method of using left and right arrays to form a queue in the book, THE author himself is not very clear, I hope that the students who know can give my younger brother some advice.

Later, the book mentioned the conversion between stack and queue, which is not introduced due to the length, but the general idea is to generate the corresponding structure through two stacks/queues, which is a writing method of changing the space complexity to the time complexity. Interested students can purchase the original book and peruse it.

Example: Give the path /a/./b/.. /b/c/, simplified to /c so let’s analyze this problem first, input string x, output string y. We then split the input string into an array of strings by **’/’, and iterate over the characters in the array (“.” for the current directory, “.. **” indicates the directory level above) will do, look at the code.

func simplifyPath(path: Var pathStack = [String]() var pathStack = [String]() var pathStack = [String]() "/") // Paths for path in paths {// If path is ".", it indicates the current directory. = "." else {// Skip loop continue} // When path equals ".." If path == ".." If (pathstack.count > 0){//pathStack has data, remove the last element pathstack.removelast ()}} else if path! Append (path)}} res let res = pathStack.reduce(""){let res = pathStack.reduce(""){ Total, dir in "\(total)/\(dir)"} // Return res.isempty? "/" : res }Copy the code

The above example is not very difficult, but it is not very easy to write the whole problem. There are a lot of boundary conditions to be aware of, and if you just follow the direction of solving the problem and ignore these boundary conditions during the interview, you will give the interviewer a bad impression.

5 binary tree

Concept: In a binary tree, each node has a maximum of two children, usually called the left child node and the right child node, and the order of the nodes cannot be arbitrarily reversed. The node at the first layer is called the root node. We calculate from the root node, and the maximum level to the node is the depth of the binary tree. First look at the node implementation code in the book:

Public class TreeNode {public var val: Int public var left: TreeNode? public var right: TreeNode? public init(_ val: Int){ self.val = val } }Copy the code

A complete binary tree node contains the data val, the left child, and the right child.

So with nodes let’s see how do we find the depth of a binary tree

func treeMaxDepth(root: TreeNode?) -> Int { guard let root = root else { return 0; Return Max (treeMaxDepth(root:root.left), treeMaxDepth(root: root.right)) + 1}Copy the code

Comments:

1: First determine whether the input binary tree node is nil, return 0 if it does not exist, and take the maximum value if there is recursive child node.

2:+1 represents each recursion level, and the binary tree depth is +1.

3: Function of Max: Compare the maximum depth of left and right child nodes and take the larger value.

Binary search tree

Binary Sort Tree A Binary Sort Tree is a Binary Sort Tree in which all the left child nodes are less than the root node and all the right byte points are greater than the root child node. Look at the code:

func isValidBST(root: TreeNode?) -> Bool { return _helper(node: root, nil, nil) } private func _helper(node: TreeNode? , _ min: Int? , _ max: Int?) -> Bool {// if node does not exist, the recursion ends. Let node = node else {return true} // The value of the right subtree must be greater than its root node value if let min = min, Node. val <= min {return false} // The value of the left subtree must be less than its root node if let Max = Max, Val >= Max {return false} return _helper(node: node.left, min, node.val) &&_helper (node: node.left, min, node.val) node.right, node.val, max) }Copy the code

Comments:

1: this place will first judge whether the current node exists. If it does not exist, it means that it has recursed to the last layer and returns true.

2: Then judge whether val of the right and left subtrees meet the judgment conditions. If they both meet the conditions, recurse at the next level.

3: Perform recursive operations at the same time.

Now that we know the basic concepts of binary trees and how to write swift, let’s look at how to implement binary tree traversal operations. Common binary tree traversals are pre-ordered, middle-ordered, back-ordered, and hierarchical traversal (breadth-first traversal).

The rules of several traversal methods are given:

Rules for front-order traversal are as follows: 1: access the root node. 2: pre-order traversal the left subtree. 3: pre-order traversal the right subtree

Middle-order traversal rules are as follows: 1: middle-order traversal the left subtree 2: access the root node 3: middle-order traversal the right subtree

Rules for post-order traversal: 1: post-order traversal of the left subtree 2: post-order traversal of the right subtree 3: access the root node

** hierarchy traversal rules :** traverses the nodes on a layer in order of layers, and then traverses the next layer, and so on until the last layer.

If you still don’t understand, you can read this introduction to binary tree traversal, which is quite straightforward.

About traversal part of the content because more, the author excerpt from the book queue implementation tree to introduce the realization of logic, see the following code:

func levelOrder(root: TreeNode?) -> [[Int]] {// Array of res returned after initialization var res = [[Int]]() // array of queue var queue = [TreeNode]() if let root = root Queue.append (root)} while queue.count > 0 {// Get the number of tiers let size = queue.count // Array of tiers var level = [Int]() for _ in 0 . < size {//removeFirst: remove the first element and return the removed element let node = queue.removeFirst() // add data level.append(node.val) // determine whether there are left and right child nodes If let left = node.left {queue.append(left)} if let right = node.right {queue.append(right)}} Res.append (level)} return res}Copy the code

Comments:

1: First we declare the array res, which is used to store the val array of each layer, and declare the queue array for later judgment.

2: Check whether the input parameter root exists. If so, store the root node in the queue array.

3:while checks whether the queue has data. If there is data, fetch the first data in the queue and delete it from the queue. Then determine the next level of data and iterate over it again.

4: Finally, save the val data of the node to level and add it to RES.

conclusion

The basic data structure of the algorithm part of the book is almost introduced, and the actual algorithm part will be introduced later. My general feeling is that this book is more suitable for beginner -> intermediate students, and definitely a good choice for beginner -> intermediate developers who want to improve themselves.