1、 实现二分查找算法，如：[2,5,7,9,11,13,14,16]，target为14，输出6。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func binarySearchWithoutRecursion(_ inputs: [Int], _ low: inout Int, _ high: inout  Int, _ target: Int) -> Int {
	while (low <= high) {
          let mid = low + (high - low) / 2;
          if (inputs[mid] > target) {
              high = mid - 1;
          } else if (inputs[mid] < target) {
                low = mid + 1;
          } else {
               //找到目标
               return mid;
          }
       }
       return -1;
}
        
func binarySearch(_ inputs: [Int], _ low: Int, _ high: Int, _ target: Int)  -> Int {
      let mid = low + (high - low) / 2;

      if(low > high) {
         return -1;
      } else{
           if(inputs[mid] == target) {
              return mid;
           } else if(inputs[mid] > target) {
               return binarySearch(inputs, low, mid-1, target);
           } else {
                return binarySearch(inputs, mid+1, high, target);
           }
      }
}

2、 冒泡排序：对以下一组数据进行降序排序。“24，17，85，13，9，54，76，45，5，63”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func bubbleSort(_ arr: inout [Int]) {
    let count = arr.count
    for index in 0..<count {
        var exchanged = false
        for j in 0..<(count - 1 - index) {
             if arr[j] < arr[j+1] {
                arr.swapAt(j, j+1)
                exchanged = true
             }
         }
         if !exchanged {
            break
         }
    }
}

// test result
var sortArr = [24, 17, 85, 13, 9, 54, 76, 45, 5, 63]
bubbleSort(&sortArr)
print(sortArr)

3、 选择排序：对以下一组数据进行升序排序。“86, 37, 56, 29, 92, 73, 15, 63, 30, 8”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func selectSort(_ arr: inout [Int]) {
    let count = arr.count
    var min = 0
    for index in 0..<count-1 {
        min = index
        for j in index+1..<count {
             if arr[min] > arr[j] {
                 min = j
             }
        }
        if min != index {
              arr.swapAt(index, min)
        }
     }
}
      
// test result       
var selectSortArr = [86, 37, 56, 29, 92, 73, 15, 63, 30, 8]
selectSort(&selectSortArr)
print(selectSortArr)

4、快速排序：对以下数据进行降序排序。“24，17，85，13，9，54，76，45，5，63”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func fastSort(_ arr: inout [Int],  _ left: Int, _ right: Int) {
    if(left >= right) {
        return
    }

    var i = left

    var j = right

    let key = arr[left]

    while (i < j) {
        while (i < j && key >= arr[j]) {
            j = j - 1
        }

        if (i < j) {
            arr[i] = arr[j]
        }
        
        while (i < j && key < arr[i]) {
            i = i + 1
        }

        if (i < j) {
            arr[j] = arr[i]
        }
    }

    arr[i] = key

    fastSort(&arr, left, i-1)

    fastSort(&arr, i+1, right)
}

5、如何实现一个数组每个元素依次向右移动k位，后面的元素依次往前面补。比如: [1, 2, 3, 4, 5] 移动两位变成[4, 5, 1, 2, 3]。
思路：三次反转
后K位反转：12354
前部分反转：32154
整体全部反转：45123

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func reversedK(_ arr: inout [Int], _ start: Int, _ end: Int) {
    var s = start, e = end
    while s < e {
       arr.swapAt(s, e)
       s += 1
       e -= 1
     }
}
        
func moveK(_ arr: inout [Int], _ k:Int) {
    let count = arr.count
    reversedK(&arr, count - k, count - 1)
    reversedK(&arr, 0, count - k - 1)
    reversedK(&arr, 0, count - 1)
}

// test result
var exampleArr = [1,2,3,4,5]
moveK(&exampleArr, 3)
print(exampleArr)

6、 给定一个字符串，输出本字符串中只出现一次并且最靠前的那个字符的位置？如“abaccddeeef”,字符是b,输出应该是2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func findChar(_ inputStr: String) -> Int {
	if inputStr.count == 1 {
         return 0
    	}
     var tempDic = Dictionary<Character, Int>()
     inputStr.forEach { (ch) in
          if tempDic[ch] != nil {
             tempDic[ch] = tempDic[ch]! + 1
          } else {
             tempDic[ch] = 1
          }
	}
            
     for index in 0..<inputStr.count {
          let ch = inputStr[inputStr.index(inputStr.startIndex,offsetBy: index)]
          if tempDic[ch] == 1 {
              return index
          }
       }
            
     return -1
}

7、如何实现链表翻转（链表逆序）？

思路：每次把第二个元素提到最前面来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Node {
  var value: Int
  var next: Node?
        
  init(value: Int, next: Node? = nil) {
      self.value = value
      self.next = next
   }
}
    
func createLinkList(length: Int) -> Node? {
     if length <= 0 {
        return nil
     }
     let head = Node.init(value: 0)
     var number = 1, p = head, q = head
     while number <= length {
         p = Node.init(value: number)
         q.next = p
         q = p
         number += 1
      }
     return head
}
    
func printLinkList(head:Node?) {
   if head == nil {
      return
    }
    var p = head
    while p != nil {
       print("num = \(p!.value)")
       p = p?.next
    }
}
    
func reverseFuncLinkList(head:Node?) -> Node? {
   if head == nil {
      return head
   }
        
   var p = head
   var q: Node?
   while p != nil {
       let pNext = p?.next
       p?.next = q
       q = p
       p = pNext
    }
    return q
}

// create link list
var head = createLinkList(length: 5)
printLinkList(head: head)

// reverse link list
head = reverseFuncLinkList(head: head)
printLinkList(head: head)

8、链表：删除链表中的重复元素，每个重复元素需要出现一次。

给定链表：1->2->2->3->4->5->5

输出结果应当为 1->2->3->4->5

请实现下面的deleteRepeatElements函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func deleteRepeatElements(head:Node?) -> Node? {
    if head == nil {
       return head
    }
    var pNode = head
    while pNode != nil && pNode?.next != nil {
    	 if pNode?.value == pNode?.next?.value {
        	let tempNode = pNode?.next
        	pNode?.next = tempNode?.next
   	 } else {
       	pNode = pNode?.next
    	 }
    }
    return head
}

9、链表：删除链表中重复的元素，只保留不重复的结点。

给定链表：1->1->2->3->4->4->5

输出结果：2->3->5

请实现下面的deleteRepeatElements函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func deleteRepeatElements(head:Node?) -> Node? {
        if head == nil {
            return head
        }
        
        // 头结点有可能被删除
        let pHead = Node.init(value: 0)
        pHead.next = head
        var cur = pHead
        
        while cur.next != nil && cur.next?.next != nil {
            if cur.next?.value == cur.next?.next?.value {
                var tempNode = cur.next
                // 找到下一个没有重复的节点
                while tempNode != nil && tempNode?.next != nil && tempNode?.value == tempNode?.next?.value {
                    tempNode = tempNode?.next
                }
                cur.next = tempNode?.next
            } else {
                cur = cur.next!
            }
        }
        
        return pHead.next
}

10、链表：两个数相加，如给定[3,6,8]、[5,8,1]，输出：[8,4,0,1]，链表节点中的value范围是0-9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func addTwoNums(_ node1: Node?, _ node2: Node?) -> Node? {
        let node3:Node? = Node.init(value: 0)
        var pNode = node1
        var qNode = node2
        var rNode = node3
        
        var q = 0, r = 0
        while pNode != nil && qNode != nil {
            let sumRes = (pNode?.value ?? 0) + (qNode?.value ?? 0) + q
            (q, r) = sumRes.quotientAndRemainder(dividingBy: 10)
            rNode?.next = Node.init(value: r)
            pNode = pNode?.next
            qNode = qNode?.next
            rNode = rNode?.next
        }
        
        if q > 0 {
            rNode?.next = Node.init(value: q)
        }
        
        return node3?.next
}

参考资料

完整优秀版请移步小专栏：
Swift算法面试题2022（附答案）

更多好文推荐，扫描下方的二维码，关注《iOS开发秘籍》公众号，点关注不迷路！
在这里插入图片描述

本文内容中部分来自网络，后续会持续更新完善。欢迎一起学习交流！

如需转载，请注明出处

Swift算法面试题2022（附答案）