iOS面試題分享群：群號:129018636?
1.使用了第三方庫, 有看它們是怎么實現(xiàn)的嗎？
2.強連通量算法了解嘛？
3.遇到tableView卡頓嘛？會造成卡頓的原因大致有哪些？
4.M、V、C相互通訊規(guī)則你知道的有哪些？
5.NStimer準嗎？談?wù)勀愕目捶?？如果不準該怎樣實現(xiàn)一個精確的NSTimer?
1.使用了第三方庫, 有看他們是怎么實現(xiàn)的嗎？
例：SD、YY、AFN、MJ等！
<1>.SD為例：
1.入口 setImageWithURL:placeholderImage:options:
會先把 placeholderImage 顯示，然后 SDWebImageManager 根據(jù) URL 開始處理圖片。
2.進入 SDWebImageManagerdownloadWithURL:delegate:options:userInfo:，
交給 SDImageCache 從緩存查找圖片是否已經(jīng)下載 queryDiskCacheForKey:delegate:userInfo:.
3.先從內(nèi)存圖片緩存查找是否有圖片，
如果內(nèi)存中已經(jīng)有圖片緩存，SDImageCacheDelegate 回調(diào) imageCache:didFindImage:forKey:userInfo: 到 SDWebImageManager。
4.SDWebImageManagerDelegate 回調(diào) webImageManager:didFinishWithImage:
到 UIImageView+WebCache 等前端展示圖片。
5.如果內(nèi)存緩存中沒有，生成 NSInvocationOperation
添加到隊列開始從硬盤查找圖片是否已經(jīng)緩存。
6.根據(jù) URLKey 在硬盤緩存目錄下嘗試讀取圖片文件。
這一步是在 NSOperation 進行的操作，所以回主線程進行結(jié)果回調(diào) notifyDelegate:。
7.如果上一操作從硬盤讀取到了圖片，將圖片添加到內(nèi)存緩存中
（如果空閑內(nèi)存過小，會先清空內(nèi)存緩存）。
SDImageCacheDelegate 回調(diào) imageCache:didFindImage:forKey:userInfo:。
進而回調(diào)展示圖片。
8.如果從硬盤緩存目錄讀取不到圖片，
說明所有緩存都不存在該圖片，需要下載圖片，
回調(diào) imageCache:didNotFindImageForKey:userInfo:。
9.共享或重新生成一個下載器 SDWebImageDownloader 開始下載圖片。
10.圖片下載由 NSURLConnection 來做，
實現(xiàn)相關(guān) delegate 來判斷圖片下載中、下載完成和下載失敗。
11.connection:didReceiveData: 中
利用 ImageIO 做了按圖片下載進度加載效果。
12.connectionDidFinishLoading: 數(shù)據(jù)下載完成后交給 SDWebImageDecoder 做圖片解碼處理。
13.圖片解碼處理在一個 NSOperationQueue 完成，
不會拖慢主線程 UI。如果有需要對下載的圖片進行二次處理，
最好也在這里完成，效率會好很多。
14.在主線程 notifyDelegateOnMainThreadWithInfo:
宣告解碼完成，
imageDecoder:didFinishDecodingImage:userInfo:
回調(diào)給 SDWebImageDownloader。
15.imageDownloader:didFinishWithImage:
回調(diào)給 SDWebImageManager 告知圖片下載完成。
16.通知所有的 downloadDelegates 下載完成，
回調(diào)給需要的地方展示圖片。
17.將圖片保存到 SDImageCache 中，
內(nèi)存緩存和硬盤緩存同時保存。
寫文件到硬盤也在以單獨 NSInvocationOperation 完成，
避免拖慢主線程。
18.SDImageCache 在初始化的時候會注冊一些消息通知，
在內(nèi)存警告或退到后臺的時候清理內(nèi)存圖片緩存，
應(yīng)用結(jié)束的時候清理過期圖片。
19.SDWI 也提供了 UIButton+WebCache 和
MKAnnotationView+WebCache，方便使用。
20.SDWebImagePrefetcher 可以預(yù)先下載圖片，
方便后續(xù)使用。
2.強連通分量了解嘛？
概念：
有向圖強連通分量：在有向圖G中，如果兩個頂點vi,vj間（vi>vj）有一條從vi到vj的有向路徑，同時還有一條從vj到vi的有向路徑，則稱兩個頂點強連通(strongly connected)。如果有向圖G的每兩個頂點都強連通，稱G是一個強連通圖。有向圖的極大強連通子圖，稱為強連通分量(strongly connected components)。
定義：
有向圖強連通分量：
在有向圖G中，如果兩個頂點間至少存在一條路徑，稱兩個頂點強連通（strongly connected）。
如果有向圖G的每兩個頂點都強連通，則稱G是一個強連通圖。
非強連通圖有向圖的極大強連通子圖，成為強連通分量（strongly connected components）。
下圖中，子圖{1,2,3,4}為一個強連通分量，因為頂點1,2,3,4兩兩可達，{5}，{6}也分別是兩個強連通分量。
直接根據(jù)定義，用雙向遍歷取交際的方法求強連通分量，時間復(fù)雜度為O（N^2+M）。更好的方法是Kosaraju算法或者Tarjan算法。
兩者的時間復(fù)雜度都是O（N+M）。本文介紹的是Tarjan算法。
算法原理：（Tarjan）
need-to-insert-img
Tarjan算法是基于對圖深度優(yōu)先搜索的算法，每個強連通分量為搜索樹中的一顆子樹。
搜索時，把當前搜索樹中未處理的節(jié)點加入一個堆棧，回溯時可以盤對棧頂?shù)綏Ｖ械墓?jié)點是否為一個強連通分量。
定義DFN（u）為節(jié)點u搜索的次序編號（時間戳）。Low（u）為u或者u的子樹能夠追溯到的最早的棧中的節(jié)點的次序號。
由定義可以得出：
Low（u）= Min { DFN（u）， Low（v）} （（u，v）為樹枝邊，u為v的父節(jié)點DFN（v），（u，v）為指向棧中節(jié)點的后向邊（非橫叉邊））
當DFN（u）=Low（u）時，以u為根的搜索子樹上所有節(jié)點是一個強連通分量。
代碼實現(xiàn)：
need-to-insert-img
[cpp]：
#include?
#include?
#include?
#include?
using?namespace?std;
#define?MIN(a,b)?((a)<(b)?(a):(b))
#define?N?10005?????????????//?題目中可能的最大點數(shù)
stacksta;????????????????//?存儲已遍歷的結(jié)點
vectorgra[N];????????????//?鄰接表表示圖
int?dfn[N];?????????????????//?深度優(yōu)先搜索訪問次序
int?low[N];?????????????????//?能追溯到的最早的次序
int?InStack[N];?????????????//?檢查是否在棧中(2為在棧中，1為已訪問，且不在棧中，0為不在)
vector?Component[N];?????//?獲得強連通分量結(jié)果
int?InComponent[N];?????????//?記錄每個點在第幾號強連通分量里
int?index,ComponentNumber;??//?索引號，強連通分量個數(shù)
int?n,?m;???????????????????//?點數(shù)，邊數(shù)
void?init(void)
{
memset(dfn,?0,?sizeof(dfn));
memset(low,?0,?sizeof(low));
memset(InStack,?0,?sizeof(InStack));
index?=?ComponentNumber?=?0;
for?(int?i?=?1;?i?<=?n;?++?i)
{
gra[i].clear();
Component[i].clear();
}
while(!sta.empty())
sta.pop();
}
void?tarjan(int?u)
{
Instack[u]?=?2;
low[u]?=?dfn[u]?=?++?index;
sta.push(u);
for?(int?i?=?0;?i?<?gra[u].size();?++?i)
{
int?t?=?gra[u][i];
if?(dfn[t]?==?0)
{
tarjan(t);
low[u]?=?MIN(low[u],?low[t]);
}
else?if?(InStack[t]?==?2)
{
low[u]?=?MIN(low[u],?dfn[t]);
}
}
if?(low[u]?==?dfn[u])
{
++?ComponentNumber;
while?(!sta.empty())
{
int?j?=?sta.top();
sta.pop();
InStack[j]?=?1;
Component[ComponentNumber].push_back(j);
InComponent[j]=ComponentNumber;
if?(j?==?u)
binputak;
}
}
}
void?input(void)
{
for(int?i=1;i<=m;i++)
{
int?a,b;
scanf("%d%d",&a,&b);
gra[a].push_back(b);
}
}
void?solve(void)
{
for(int?i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);
if(ComponentNumber>1)
puts("No");
else
puts("Yes");
}
int?main()
{
while(scanf("%d%d",&n,&m),n+m)
{
init();
input();
solve();
}
}
3.遇到tableView卡頓嘛？會造成卡頓的原因大致有哪些？
可能造成tableView卡頓的原因有：
1.最常用的就是cell的重用， 注冊重用標識符
如果不重用cell時，每當一個cell顯示到屏幕上時，就會重新創(chuàng)建一個新的cell；
如果有很多數(shù)據(jù)的時候，就會堆積很多cell。
如果重用cell，為cell創(chuàng)建一個ID，每當需要顯示cell 的時候，都會先去緩沖池中尋找可循環(huán)利用的cell，如果沒有再重新創(chuàng)建cell
2.避免cell的重新布局
cell的布局填充等操作 比較耗時，一般創(chuàng)建時就布局好
如可以將cell單獨放到一個自定義類，初始化時就布局好
3.提前計算并緩存cell的屬性及內(nèi)容
當我們創(chuàng)建cell的數(shù)據(jù)源方法時，編譯器并不是先創(chuàng)建cell 再定cell的高度
而是先根據(jù)內(nèi)容一次確定每一個cell的高度，高度確定后，再創(chuàng)建要顯示的cell，滾動時，每當cell進入憑虛都會計算高度，提前估算高度告訴編譯器，編譯器知道高度后，緊接著就會創(chuàng)建cell，這時再調(diào)用高度的具體計算方法，這樣可以方式浪費時間去計算顯示以外的cell
4.減少cell中控件的數(shù)量
盡量使cell得布局大致相同，不同風格的cell可以使用不用的重用標識符，初始化時添加控件，
不適用的可以先隱藏
5.不要使用ClearColor，無背景色，透明度也不要設(shè)置為0
渲染耗時比較長
6.使用局部更新
如果只是更新某組的話，使用reloadSection進行局部更新
7.加載網(wǎng)絡(luò)數(shù)據(jù)，下載圖片，使用異步加載，并緩存
8.少使用addView 給cell動態(tài)添加view
9.按需加載cell，cell滾動很快時，只加載范圍內(nèi)的cell
10.不要實現(xiàn)無用的代理方法，tableView只遵守兩個協(xié)議
11.緩存行高：estimatedHeightForRow不能和HeightForRow里面的layoutIfNeed同時存在，這兩者同時存在才會出現(xiàn)“竄動”的bug。所以我的建議是：只要是固定行高就寫預(yù)估行高來減少行高調(diào)用次數(shù)提升性能。如果是動態(tài)行高就不要寫預(yù)估方法了，用一個行高的緩存字典來減少代碼的調(diào)用次數(shù)即可
12.不要做多余的繪制工作。在實現(xiàn)drawRect:的時候，它的rect參數(shù)就是需要繪制的區(qū)域，這個區(qū)域之外的不需要進行繪制。例如上例中，就可以用CGRectIntersectsRect、CGRectIntersection或CGRectContainsRect判斷是否需要繪制image和text，然后再調(diào)用繪制方法。
13.預(yù)渲染圖像。當新的圖像出現(xiàn)時，仍然會有短暫的停頓現(xiàn)象。解決的辦法就是在bitmap context里先將其畫一遍，導(dǎo)出成UIImage對象，然后再繪制到屏幕；
14.使用正確的數(shù)據(jù)結(jié)構(gòu)來存儲數(shù)據(jù)。
4.M、V、C相互通訊規(guī)則你知道的有哪些？
MVC 是一種設(shè)計思想，一種框架模式，是一種把應(yīng)用中所有類組織起來的策略，它把你的程序分為三塊，分別是：
M（Model）：實際上考慮的是“什么”問題，你的程序本質(zhì)上是什么，獨立于 UI 工作。是程序中用于處理應(yīng)用程序邏輯的部分，通常負責存取數(shù)據(jù)。
C（Controller）：控制你 Model 如何呈現(xiàn)在屏幕上，當它需要數(shù)據(jù)的時候就告訴 Model，你幫我獲取某某數(shù)據(jù)；當它需要 UI 展示和更新的時候就告訴 View，你幫我生成一個 UI 顯示某某數(shù)據(jù)，是 Model 和 View 溝通的橋梁。
V（View）：Controller 的手下，是 Controller 要使用的類，用于構(gòu)建視圖，通常是根據(jù) Model 來創(chuàng)建視圖的。
要了解 MVC 如何工作，首先需要了解這三個模塊間如何通信。
MVC通信規(guī)則
Controller to Model
可以直接單向通信。Controller 需要將 Model 呈現(xiàn)給用戶，因此需要知道模型的一切，還需要有同 Model 完全通信的能力，并且能任意使用 Model 的公共 API。
Controller to View
可以直接單向通信。Controller 通過 View 來布局用戶界面。
Model to View
永遠不要直接通信。Model 是獨立于 UI 的，并不需要和 View 直接通信，View 通過 Controller 獲取 Model 數(shù)據(jù)。
View to Controller
View 不能對 Controller 知道的太多，因此要通過間接的方式通信。
Target action。首先 Controller 會給自己留一個 target，再把配套的 action 交給 View 作為聯(lián)系方式。那么 View 接收到某些變化時，View 就會發(fā)送 action 給 target 從而達到通知的目的。這里 View 只需要發(fā)送 action，并不需要知道 Controller 如何去執(zhí)行方法。
代理。有時候 View 沒有足夠的邏輯去判斷用戶操作是否符合規(guī)范，他會把判斷這些問題的權(quán)力委托給其他對象，他只需獲得答案就行了，并不會管是誰給的答案。
DataSoure。View 沒有擁有他們所顯示數(shù)據(jù)的權(quán)力，View 只能向 Controller 請求數(shù)據(jù)進行顯示，Controller 則獲取 Model 的數(shù)據(jù)整理排版后提供給 View。
Model 訪問 Controller
同樣的 Model 是獨立于 UI 存在的，因此無法直接與 Controller 通信，但是當 Model 本身信息發(fā)生了改變的時候，會通過下面的方式進行間接通信。
Notification & KVO一種類似電臺的方法，Model 信息改變時會廣播消息給感興趣的人 ，只要 Controller 接收到了這個廣播的時候就會主動聯(lián)系 Model，獲取新的數(shù)據(jù)并提供給 View。
從上面的簡單介紹中我們來簡單概括一下 MVC 模式的優(yōu)點。
1.低耦合性
2.有利于開發(fā)分工
3.有利于組件重用
4.可維護性
5.NStimer準嗎？談?wù)勀愕目捶ǎ咳绻粶试撛鯓訉崿F(xiàn)一個精確的NSTimer?
1.不準
2.不準的原因如下：
1、NSTimer加在main runloop中，模式是NSDefaultRunLoopMode，main負責所有主線程事件，例如UI界面的操作，復(fù)雜的運算，這樣在同一個runloop中timer就會產(chǎn)生阻塞。
2、模式的改變。主線程的 RunLoop 里有兩個預(yù)置的 Mode：kCFRunLoopDefaultMode 和 UITrackingRunLoopMode。
當你創(chuàng)建一個 Timer 并加到 DefaultMode 時，Timer 會得到重復(fù)回調(diào)，但此時滑動一個ScrollView時，RunLoop 會將 mode 切換為 TrackingRunLoopMode，這時 Timer 就不會被回調(diào)，并且也不會影響到滑動操作。所以就會影響到NSTimer不準的情況。
PS:DefaultMode 是 App 平時所處的狀態(tài)，rackingRunLoopMode 是追蹤 ScrollView 滑動時的狀態(tài)。
方法一：
1、在主線程中進行NSTimer操作，但是將NSTimer實例加到main runloop的特定mode（模式）中。避免被復(fù)雜運算操作或者UI界面刷新所干擾。
self.timer = [NSTimer timerWithTimeInterval:1 target:self selector:@selector(showTime) userInfo:nil repeats:YES];
[[NSRunLoop currentRunLoop] addTimer:self.timer forMode:NSRunLoopCommonModes];
2、在子線程中進行NSTimer的操作，再在主線程中修改UI界面顯示操作結(jié)果；
- (void)timerMethod2 {
NSThread *thread = [[NSThread alloc] initWithTarget:self selector:@selector(newThread) object:nil];
[thread start];
}
- (void)newThread
{
@autoreleasepool
{
[NSTimer scheduledTimerWithTimeInterval:1.0 target:self selector:@selector(showTime) userInfo:nil repeats:YES];
[[NSRunLoop currentRunLoop] run];
}
}
總結(jié)：
一開始的時候系統(tǒng)就為我們將主線程的main runloop隱式的啟動了。
在創(chuàng)建線程的時候，可以主動獲取當前線程的runloop。每個子線程對應(yīng)一個runloop
方法二：
使用示例
使用mach內(nèi)核級的函數(shù)可以使用mach_absolute_time()獲取到CPU的tickcount的計數(shù)值，可以通過”mach_timebase_info”函數(shù)獲取到納秒級的精確度 。然后使用mach_wait_until(uint64_t deadline)函數(shù)，直到指定的時間之后，就可以執(zhí)行指定任務(wù)了。
關(guān)于數(shù)據(jù)結(jié)構(gòu)mach_timebase_info的定義如下：
struct mach_timebase_info {uint32_t numer;uint32_t denom;};
#include
#include
static const uint64_t NANOS_PER_USEC = 1000ULL;
static const uint64_t NANOS_PER_MILLISEC = 1000ULL * NANOS_PER_USEC;
static const uint64_t NANOS_PER_SEC = 1000ULL * NANOS_PER_MILLISEC;
static mach_timebase_info_data_t timebase_info;
static uint64_t nanos_to_abs(uint64_t nanos) {
return nanos * timebase_info.denom / timebase_info.numer;
}
void example_mach_wait_until(int seconds)
{
mach_timebase_info(&timebase_info);
uint64_t time_to_wait = nanos_to_abs(seconds * NANOS_PER_SEC);
uint64_t now = mach_absolute_time();
mach_wait_until(now + time_to_wait);
}
方法三：直接使用GCD替代！
轉(zhuǎn)載：http://www.itdecent.cn/p/0e9e7486e1a7
iOS面試題分享群：群號:129018636
