iOS老司機整理, iOSer必會的經典演算法_1
本文正在參加「金石計劃 . 瓜分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]
- 採用頭插法的思路圖解:
- 使用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當中, 且仍然保持有序?
- 演算法思路:
- 利用雙指標.
-
使用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]);
}
```
- 結果列印:
發文不易, 喜歡點讚的人更有好運氣👍 :), 定期更新+關注不迷路~
ps:歡迎加入筆者18年建立的研究iOS稽核及前沿技術的三千人扣群:662339934,坑位有限,備註“掘金網友”可被群管通過~
本文正在參加「金石計劃 . 瓜分6萬現金大獎」
- iOS老司機聊聊實際專案開發中的<<人月神話>>
- iOS老司機可落地在中大型iOS專案中的5大接地氣設計模式合集
- iOS老司機的跨端跨平臺Hybrid開發Tips
- iOS老司機的2022年回顧, 聊聊寒冬下的實用<<談判力>>
- iOS老司機可落地的中大型iOS專案中的設計模式優化Tips_橋接模式
- iOS老司機的多執行緒PThread學習分享
- iOS老司機整理, iOSer必會的經典演算法_2
- iOS老司機的<<藍海轉型>>讀書分享
- iOS老司機的<<程式設計師的自我修養:連結、裝載與庫>>讀書分享
- iOS老司機的接地氣演算法Tips
- iOS老司機的RunLoop原理探究及實用Tips
- iOS老司機整理, iOSer必會的經典演算法_1
- iOS老司機的App啟動優化Tips, 讓啟動速度提升10%
- iOS老司機的網路相關Tips
- 戀上資料結構與演算法
- iOS老司機帶你一起把App的崩潰率降到0.1%以下
- 探究Swift的String底層實現
- iOS老司機萬字整理, 可能是最全的Swift Tips
- iOS老司機可落地的中大型iOS專案中的設計模式優化Tips
- 聊一聊Swift中的閉包