iOS老司機整理, iOSer必會的經典算法_1

語言: CN / TW / HK

本文正在參加「金石計劃 . 瓜分6萬現金大獎」

前言

  • iOS日常開發中, 算法使用的多嗎? 實事求是的來説, 是不多的.
  • 那算法的學習對iOSer來説, 就不需要了嗎? 答案是很需要.
  • iOS的日常開發中, 用到的算法確實不多, 但是算法在iOS開發裏面的應用都被封裝在各種常用API的內部了.
  • 對算法的學習, 可以提高對iOS底層的理解與認識, 這些算法的知識是計算機技術領域通用的. 下面就iOS開發中一些經典的算法進行一個簡單的梳理.
  • 文章純手打, 拋磚引玉, 如有錯誤還請評論區指正, 先行謝過了:)

1. 字符串反轉

  • 編寫一個函數,其作用是將輸入的字符串反轉過來。輸入字符串以字符數組 s 的形式給出。不要給另外的數組分配額外的空間,你必須原地修改輸入數組、使用 O(1) 的額外空間解決這一問題。

示例 1:

輸入: s = ["h","e","l","l","o"] 輸出: ["o","l","l","e","h"]

示例 2:

輸入: s = ["H","a","n","n","a","h"] 輸出: ["h","a","n","n","a","H"]

  • 使用C語言的解答及思路: void reverseString(char* s, int sSize) { // 指向第一個字符 char *begin = s; // 指向最後一個字符 char *end = s + sSize - 1; while (begin < end) { // 交換前後兩個字符, 同時移動指針 char temp = *begin; *(begin++) = *end; *(end--) = temp; } }
  • 力扣鏈接

2. 單鏈表反轉

  • 給你單鏈表的頭節點 head ,請你反轉鏈表,並返回反轉後的鏈表。如: 輸入: head = [1,2,3,4,5] 輸出: [5,4,3,2,1] image.png
  • 採用頭插法的思路圖解:

image.png

  • 使用Swift語言的解答及思路: ``` /**
  • Definition for singly-linked list.
  • public class ListNode {
  • public var val: Int
  • public var next: ListNode?
  • public init() { self.val = 0; self.next = nil; }
  • public init(_ val: Int) { self.val = val; self.next = nil; }
  • public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
  • } */

class Solution {

// 遞歸遍歷
// func reverseList(_ head: ListNode?) -> ListNode? {
//     if head == nil || head?.next == nil {
//         return head
//     }

//     var newHead = reverseList(head?.next)
//     head?.next?.next = head
//     head?.next = nil

//     return newHead
// }

// 頭插法
func reverseList(_ head: ListNode?) -> ListNode? {
    var prev : ListNode? = nil // 新建上一個結點點, 初始為nil
    var current : ListNode? = head // 設置當前結點為傳入的結點

    while current != nil {// while遍歷當前結點
        let next : ListNode? = current?.next // 設置下一個結點為當前結點的next

        current?.next = prev // 當前結點的next節點指向上一個結點
        prev = current // 設置上一個結點為當前結點
        current = next // 設置當前結點為下一個結點
    }

    return prev // 返回頭插的結點
}

} ``` - 力扣鏈接

3. 有序數組合並

  • 如何將有序數組a和b的值合併到一個數組c當中, 且仍然保持有序?
  • 算法思路:
  • 利用雙指針. image.png
  • 使用C語言的解答及思路: ``` void mergeArray(int a[], int aLen, int b[], int bLen, int c[]) { // 遍歷數組a的指針 int p = 0; // 遍歷數組b的指針 int q = 0; // 記錄當前存儲位置 int i = 0;

    // 任一數組沒有到達邊界則進行遍歷 while (p < aLen && q < bLen) { // 如果a數組對應位置的值小於b數組對應位置的值 if (a[p] <= b[q]) { // 存儲a數組的值 c[i] = a[p]; // 移動b數組的遍歷指針 p++; } else { // 存儲b數組的值 c[i] = b[q]; // 移動b數組的遍歷指針 q++; }

    //指向合併結果的下一個存儲位置
    i++;
    

    }

    // 如果a數組有剩餘 while (p < aLen) { // 將a數組剩餘部分拼接到合併結果的後面 c[i] = a[p++]; i++; }

    // 如果b數組有剩餘 while (q < bLen) { // 將b數組剩餘部分拼接到合併結果的後面 c[i] = b[q++]; i++; } }

    // 驗證代碼: // 有序數組歸併     int a[5] = {1, 3, 5, 7, 12};     int b[7] = {2, 4, 6, 8, 9, 10, 11};

// 用於存儲歸併結果     int c[12];     // 歸併操作     mergeArray(a, 5, b, 7, c);     // 打印歸併結果     printf("merge result is ");     for (int i = 0; i < 12; i++) {         printf("%d ", c[i]);     } ``` - 結果打印: image.png

發文不易, 喜歡點讚的人更有好運氣👍 :), 定期更新+關注不迷路~

ps:歡迎加入筆者18年建立的研究iOS審核及前沿技術的三千人扣羣:662339934,坑位有限,備註“掘金網友”可被羣管通過~

本文正在參加「金石計劃 . 瓜分6萬現金大獎」