
作者:吳白(簡書)
接上篇《那些著名或非著名的 iOS 面試題(上)》,本文繼續整理若干常見與不常見的 iOS 面試題。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */遞歸寫法:
public class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } root.left = invertTree(root.left); root.right = invertTree(root.right); TreeNode tmp = root.left; root.left = root.right; root.right = tmp; return root; } }Objective-C 實作:
/** * 翻轉二叉樹(又叫:二叉樹的鏡像) * * @param rootNode 根節點 * * @return 翻轉後的樹根節點(其實就是原二叉樹的根節點) */ + (BinaryTreeNode *)invertBinaryTree:(BinaryTreeNode *)rootNode { if (!rootNode) { return nil; } if (!rootNode.leftNode && !rootNode.rightNode) { return rootNode; } [self invertBinaryTree:rootNode.leftNode]; [self invertBinaryTree:rootNode.rightNode]; BinaryTreeNode *tempNode = rootNode.leftNode; rootNode.leftNode = rootNode.rightNode; rootNode.rightNode = tempNode; return rootNode; }非遞歸寫法(用佇列做層序遍歷):
+ (BinaryTreeNode *)invertBinaryTree:(BinaryTreeNode *)rootNode { if (!rootNode) { return nil; } if (!rootNode.leftNode && !rootNode.rightNode) { return rootNode; } NSMutableArray *queueArray = [NSMutableArray array]; //陣列當成佇列 [queueArray addObject:rootNode]; //壓入根節點 while (queueArray.count > 0) { BinaryTreeNode *node = [queueArray firstObject]; [queueArray removeObjectAtIndex:0]; //彈出最前面的節點,仿照佇列先進先出原則 BinaryTreeNode *pLeft = node.leftNode; node.leftNode = node.rightNode; node.rightNode = pLeft; if (node.leftNode) { [queueArray addObject:node.leftNode]; } if (node.rightNode) { [queueArray addObject:node.rightNode]; } } return rootNode; }示例程式碼參考:二叉樹
+ (AccountManager *)sharedManager { static AccountManager *sharedAccountManagerInstance = nil; static dispatch_once_t predicate; dispatch_once(&predicate, ^{ sharedAccountManagerInstance = [[self alloc] init]; }); return sharedAccountManagerInstance; }應用程式的五種狀態:
Not running 未運行:程式還沒啟動
Inactive 未啟用:程式在前台,但沒有收到事件。若無事件處理,通常就停在這個狀態
Active 啟用:程式在前台且正在接收事件,這才是前台的正常狀態
Background 後台:程式在後台且仍能執行程式碼。多數程式進入後會停留一會兒,之後轉為 Suspended;少數程式經特殊申請後可長期留在後台
Suspended 掛起:程式在後台無法執行程式碼。系統會自動轉入此狀態且不發通知。此時程式仍在記憶體中,一旦系統記憶體吃緊就會被清除,把資源讓給前台程式
iOS 的入口在 main.m:
int main(int argc, char *argv[]) { @autoreleasepool { return UIApplicationMain(argc, argv, nil, NSStringFromClass([AppDelegate class])); } }main 的兩個參數在 iOS 中並未使用,保留只是為了與標準 ANSI C 一致。UIApplicationMain 的前兩個參數同 main,重點在後兩個:分別代表主要類別(principal class)與代理類別(delegate class)。主要類別為 nil 時會從 Info.plist 取值,若其中沒有對應 key 則預設為 UIApplication;代理類別則在建立新專案時自動產生。
依 UIApplicationMain 的設定,程式會進入 AppDelegate.m——這個檔案關乎整個應用程式的生命週期:
1、application didFinishLaunchingWithOptions:程式啟動時執行,是啟動入口,整個生命週期只跑一次。若使用者直接啟動,launchOptions 內沒有資料;若透過其他方式(如推送、URL Scheme)啟動,則會帶入對應內容。
2、applicationWillResignActive:即將從活躍狀態切到非活躍狀態時呼叫,例如按 Home 鍵回首頁、在全屏與非全屏之間切換。
3、applicationDidEnterBackground:進入後台時呼叫。
4、applicationWillEnterForeground:即將回到前台(被啟用)時呼叫,與 applicationWillResignActive 相對。
5、applicationDidBecomeActive:已被啟用後呼叫,與 applicationDidEnterBackground 相對。
6、applicationWillTerminate:即將完全結束時呼叫,前提是設定了 UIApplicationExitsOnSuspend。
首次啟動:
iOS_didFinishLaunchingWithOptions iOS_applicationDidBecomeActive
按下 Home 鍵:
iOS_applicationWillResignActive iOS_applicationDidEnterBackground
點擊圖示回到程式:
iOS_applicationWillEnterForeground iOS_applicationDidBecomeActive
進入後台時,應該保存使用者資料或狀態;所有還沒寫入磁碟的內容都要趁此機會落盤,因為程式隨時可能在後台被殺掉,同時盡可能釋放記憶體。
- (void)applicationDidEnterBackground:(UIApplication *)application
這個方法大約給你 5 秒鐘完成上述工作。超時仍未完成,程式會被終止並從記憶體清除。
若確實需要更長時間的任務,可以在其中呼叫:
[application beginBackgroundTaskWithExpirationHandler:^{ NSLog(@"begin Background Task With Expiration Handler"); }];程式終止
符合以下任一情況時,程式一進入後台或掛起狀態就會被終止:① iOS 4.0 以前的系統;② App 是基於 iOS 4.0 之前 SDK 開發的;③ 裝置不支援多工;④ Info.plist 中含有 UIApplicationExitsOnSuspend 鍵。
系統最常在為其他 App 配置記憶體時因不足而回收,這時必須終止應用程式;偶爾也會因為 App 長時間無回應而終止。若 App 當時在後台且未被暫停,系統會先呼叫 - (void)applicationWillTerminate:(UIApplication *)application,讓你做點清理工作,例如保存資料或狀態。這個方法同樣有 5 秒限制,超時後程式會被直接從記憶體清除。
另外別忘了:使用者可以手動關閉應用程式。
一位工人替老闆工作七天,報酬是一根金條,每天相當於整根的 1/7。金條只能切兩次,如何按天支付?
這道題的關鍵在於:給出去的東西還能收回來,可以用找零的方式操作。
把金條切成 1/7、2/7、4/7 三段(正好兩刀)。第一天給 1/7;第二天給 2/7,收回 1/7;第三天再給 1/7;第四天給 4/7,收回 1/7 與 2/7;第五天給 1/7;第六天給 2/7,收回 1/7;第七天給 1/7。
Socket 是對 TCP/IP 協定的封裝,本身並不是協定,而是一組呼叫介面(API)——透過 Socket,我們才能使用 TCP/IP。
HTTP 協定:對應應用層
TCP 協定:對應傳輸層
IP 協定:對應網路層
三者層級不同,嚴格說沒有可比性,何況 HTTP 本就是建立在 TCP 連接之上。TCP/IP 屬傳輸層,解決資料如何在網路中傳輸;HTTP 屬應用層,解決如何包裝資料。
傳輸資料時可以只用傳輸層,但少了應用層就無法辨識內容;要讓資料有意義,就必須搭配應用層協定。可用的應用層協定很多,HTTP、FTP、TELNET 等,也可以自訂。Web 的做法是用 HTTP 封裝文字資訊,再交給 TCP/IP 完成實際傳輸。
SOCKET 原理
1、套接字(socket)概念
套接字是通訊的基石,是支援 TCP/IP 的網路通訊基本操作單元,可視為網路通訊端點的抽象表示,包含通訊所需的五種資訊:使用的協定、本機 IP、本機行程的協定埠、遠端 IP、遠端行程的協定埠。
應用層透過傳輸層通訊時,TCP 必須同時為多個應用程式行程提供服務,也就是多個連接或行程可能共用同一個 TCP 埠。為了區分不同的行程與連接,作業系統為應用層與 TCP/IP 的互動提供了 Socket 介面,讓應用層能分辨來自不同行程或網路連接的訊息,實現並發服務。
2、建立 socket 連接
建立 Socket 連接至少需要一對套接字:一個跑在用戶端(ClientSocket),一個跑在伺服器端(ServerSocket)。過程分三步:伺服器監聽、用戶端請求、連接確認。
伺服器監聽:伺服器端套接字不定位具體用戶端,而是處於等待狀態,即時監控網路狀態。
用戶端請求:用戶端套接字提出連接請求,必須先描述目標伺服器套接字的位址與埠號,再送出請求。
連接確認:伺服器端套接字收到請求後予以回應,建立新執行緒並把自己的描述回傳給用戶端;用戶端確認後雙方正式建立連接,而伺服器端套接字繼續監聽,等待其他用戶端。
3、Socket 連接與 TCP 連接
建立 Socket 連接時可以指定傳輸層協定(TCP 或 UDP)。使用 TCP 時,這個 Socket 連接就是一個 TCP 連接。
4、Socket 連接與 HTTP 連接
由於 Socket 連接通常就是 TCP 連接,一旦建立,雙方即可雙向傳輸資料直到連接斷開。但實務上用戶端到伺服器之間往往要穿越路由器、閘道、防火牆等多個節點,而多數防火牆預設會關閉長時間非活躍的連接,導致 Socket 斷線,因此需要透過輪詢告訴網路「這條連接還活著」。
HTTP 連接則是「請求—回應」模式:不但要先建立連接,還是用戶端發出請求後伺服器才回覆資料。很多時候我們需要伺服器主動推送、保持兩端資料即時同步。此時若雙方是 Socket 連接,伺服器可直接把資料送來;若是 HTTP 連接,伺服器只能等下一次請求。因此用戶端會定時發送請求,既維持連線,也順便「詢問」伺服器是否有新資料。
GET 用於取得資料,POST 通常用於把資料送到伺服器。
常見說法:
1、GET 透過 URL 或 Cookie 傳參,POST 把資料放在 BODY 中。
2、GET 的 URL 有長度限制,POST 的資料量則可以很大。
3、POST 比 GET 安全,因為資料不顯示在網址列上。
不過也有文章指出上述說法並不嚴謹,可另行參考相關討論。
由於打不出數學符號,只能貼圖。

時間複雜度
求時間複雜度
【1】若演算法的執行時間不隨問題規模 n 增長,即使裡頭有上千條語句,耗時也不過是一個較大的常數,此類演算法的時間複雜度為 O(1)。
x=91; y=100;while(y>0) if(x>100) {x=x-10;y--;} else x++;解答: T(n)=O(1)這段程式碼的運行與 n 無關,就算它再跑一萬年也一樣,屬於常數階。
【2】有多層迴圈時,時間複雜度由嵌套最深那層迴圈中最內層語句的執行頻度 f(n) 決定。
x=1; for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x++;
這裡頻度最高的是最內層語句。內迴圈次數雖與 n 沒有直接關係,卻取決於外層迴圈變數;而最外層次數直接與 n 相關,因此可以由內向外逐層統計,最終得到該段程式碼的時間複雜度:

【3】時間複雜度不僅取決於問題規模,也與輸入實例的初始狀態有關。
在陣列 A[0..n-1] 中查找給定值 K 的演算法大致如下:
i=n-1; while(i>=0&&(A[i]!=k)) i--; return i;
其中語句的頻度不只與 n 有關,還與 A 的元素值及 K 的取值相關:① 若 A 中沒有與 K 相等的元素,頻度 f(n)=n;② 若 A 的最後一個元素等於 K,頻度為常數 0。
空間複雜度
一個程式的空間複雜度,指的是運行它所需的記憶體大小。透過空間複雜度,我們能事先估算程式需要多少記憶體。程式執行時除了存放程式碼、常數、變數與輸入資料外,還需要工作單元與計算過程中的輔助空間,因此所需儲存空間分兩部分:
(1)固定部分:大小與輸入輸出資料的數量無關,主要包括程式碼空間與資料空間(常數、簡單變數),屬於靜態空間。
(2)可變部分:主要是動態配置的空間與遞歸堆疊所需的空間,大小與演算法本身有關。
以 f(n) 表示演算法所需的儲存空間,則 S(n)=O(f(n)),其中 n 為問題規模,S(n) 為空間複雜度。
完成一次完整的支付流程,大致步驟是:向支付寶申請並簽約,取得商戶 ID(partner)、帳號 ID(seller)與私鑰(privateKey);下載 SDK,產生訂單資訊,進行簽名加密後呼叫支付寶用戶端,由它與支付寶安全伺服器打交道;支付完成後用戶端會自動跳回原本的應用程式並展示結果。
整合時常見的兩個問題:
1)編譯時找不到 openssl/asn1.h

解法:Build Settings > Search Paths > Header Search Paths 加入 $(SRCROOT)/支付寶集成/Classes/Alipay。

2)連結時找不到 SystemConfiguration.framework

解法:

呼叫支付寶用戶端進行支付(若使用者沒安裝,則在應用程式內放一個 WebView,引導網頁支付):
// 注意:如果是通過網頁支付完成,那麼會回呼該block:callback [[AlipaySDK defaultService] payOrder:orderString fromScheme:@"jingdong" callback:^(NSDictionary *resultDic) { }];在 AppDelegate.m 中:
// 當通過別的應用程式,將該應用程式打開時,會呼叫該方法 - (BOOL)application:(UIApplication *)app openURL:(NSURL *)url options:(NSDictionary *)options{ // 當使用者通過支付寶用戶端進行支付時,會回呼該block:standbyCallback [[AlipaySDK defaultService] processOrderWithPaymentResult:url standbyCallback:^(NSDictionary *resultDic) { NSLog(@"result = %@",resultDic); }]; return YES;}當伺服器端向 APNS 推送訊息給一台離線裝置時,Apple 伺服器的 QoS 元件會保留一份最新的通知,等裝置上線後再送達。
基本流程:
1、用戶端的 App 把裝置 UDID 與 App 的 bundle ID 送給 APNS 註冊,APNS 回傳加密後的 device Token
2、App 取得 device Token 後上傳到自家伺服器
3、需要推送時,伺服器把內容與 device Token 一起送給 APNS
4、APNS 再把內容送到用戶端
建立憑證的流程:
1、開啟鑰匙圈,產生 CertificateSigningRequest.certSigningRequest
2、上傳 CSR 到 developer,匯出 .cer
3、用 CSR 匯出 P12
4、準備好裝置 token 值(去除空格)
5、用 OpenSSL 合成伺服器端要用的推送憑證
App 端程式碼
1、註冊遠程通知
- (BOOL)application:(UIApplication *)application didFinishLaunchingWithOptions:(NSDictionary *)launchOptions//中註冊遠程通知 { [[UIApplication sharedApplication] registerForRemoteNotificationTypes:(UIRemoteNotificationTypeAlert | UIRemoteNotificationTypeBadge | UIRemoteNotificationTypeSound)]; }2、實作幾個代理方法:
//獲取deviceToken令牌 -(void)application:(UIApplication *)application didRegisterForRemoteNotificationsWithDeviceToken:(NSData *)deviceToken { //獲取裝置的deviceToken唯一編號 NSLog(@"deviceToken=%@",deviceToken); NSString *realDeviceToken=[NSString stringWithFormat:@"%@",deviceToken]; //去除<> realDeviceToken = [realDeviceToken stringByReplacingOccurrencesOfString:@"<" withString:@""]; realDeviceToken = [realDeviceToken stringByReplacingOccurrencesOfString:@">" withString:@""]; NSLog(@"realDeviceToken=%@",realDeviceToken); [[NSUserDefaults standardUserDefaults] setValue:realDeviceToken forKey:@"DeviceToken"]; //要發送給伺服器 } //獲取令牌出錯 -(void)application:(UIApplication *)application didFailToRegisterForRemoteNotificationsWithError:(NSError *)error { //註冊遠程通知裝置出錯 NSLog(@"RegisterForRemoteNotification error=%@",error); } //在應用在前台時受到訊息呼叫 -(void)application:(UIApplication *)application didReceiveRemoteNotification:(NSDictionary *)userInfo { //列印推送的訊息 NSLog(@"%@",[[userInfo objectForKey:@"aps"] objectForKey:@"alert"]): }配置後台模式
一般我們用開發版本的 Provisioning 做推送測試,沒問題後換成發布版本通常也不會出錯。保險起見,可以在越獄手機上安裝用發布憑證打包的 ipa(建議用 debug 版並列印取得的 deviceToken),安裝後在 Xcode > Window > Organizer 找到對應裝置查看 console,即可找到列印出的 deviceToken。接著在後台推送程式中使用發布版憑證並搭配該 deviceToken 進行推送服務。
要留意的是,開發與發布憑證取得的 deviceToken 並不相同。
1)在 protocol 中使用 property,只會產生 setter 與 getter 的方法宣告。我們使用屬性的目的,是希望遵循該協定的物件去實作它。
2)category 使用 @property 同樣只產生方法宣告。若真的需要為 category 加上屬性實作,得借助執行期的兩個函數:
①objc_setAssociatedObject ②objc_getAssociatedObject