1.使用了第三方庫(kù), 有看它們是怎么實(shí)現(xiàn)的嗎活逆？
2.強(qiáng)連通量算法了解嘛露该？
3.遇到tableView卡頓嘛辛润？會(huì)造成卡頓的原因大致有哪些？
4.M健爬、V、C相互通訊規(guī)則你知道的有哪些么介？
5.NStimer準(zhǔn)嗎娜遵？談?wù)勀愕目捶ǎ咳绻粶?zhǔn)該怎樣實(shí)現(xiàn)一個(gè)精確的NSTimer?
1.使用了第三方庫(kù), 有看他們是怎么實(shí)現(xiàn)的嗎壤短？
1.入口 setImageWithURL:placeholderImage:options:
會(huì)先把 placeholderImage 顯示设拟，然后 SDWebImageManager 根據(jù) URL 開(kāi)始處理圖片。
2.進(jìn)入 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)存緩存中沒(méi)有，生成 NSInvocationOperation
添加到隊(duì)列開(kāi)始從硬盤(pán)查找圖片是否已經(jīng)緩存骡和。
6.根據(jù) URLKey 在硬盤(pán)緩存目錄下嘗試讀取圖片文件相赁。
這一步是在 NSOperation 進(jìn)行的操作，所以回主線程進(jìn)行結(jié)果回調(diào) notifyDelegate:慰于。
7.如果上一操作從硬盤(pán)讀取到了圖片钮科，將圖片添加到內(nèi)存緩存中
（如果空閑內(nèi)存過(guò)小，會(huì)先清空內(nèi)存緩存）婆赠。
SDImageCacheDelegate 回調(diào) imageCache:didFindImage:forKey:userInfo:绵脯。
進(jìn)而回調(diào)展示圖片。
8.如果從硬盤(pán)緩存目錄讀取不到圖片休里，
說(shuō)明所有緩存都不存在該圖片蛆挫，需要下載圖片，
回調(diào) imageCache:didNotFindImageForKey:userInfo:妙黍。
9.共享或重新生成一個(gè)下載器 SDWebImageDownloader 開(kāi)始下載圖片悴侵。
10.圖片下載由 NSURLConnection 來(lái)做，
實(shí)現(xiàn)相關(guān) delegate 來(lái)判斷圖片下載中拭嫁、下載完成和下載失敗可免。
11.connection:didReceiveData: 中
利用 ImageIO 做了按圖片下載進(jìn)度加載效果抓于。
12.connectionDidFinishLoading: 數(shù)據(jù)下載完成后交給 SDWebImageDecoder 做圖片解碼處理。
13.圖片解碼處理在一個(gè) NSOperationQueue 完成浇借，
不會(huì)拖慢主線程 UI捉撮。如果有需要對(duì)下載的圖片進(jìn)行二次處理，
最好也在這里完成逮刨，效率會(huì)好很多呕缭。
14.在主線程 notifyDelegateOnMainThreadWithInfo:
宣告解碼完成，
imageDecoder:didFinishDecodingImage:userInfo:
回調(diào)給 SDWebImageDownloader修己。
15.imageDownloader:didFinishWithImage:回調(diào)給 SDWebImageManager 告知圖片下載完成恢总。
16.通知所有的 downloadDelegates 下載完成，
回調(diào)給需要的地方展示圖片睬愤。
17.將圖片保存到 SDImageCache 中片仿，
內(nèi)存緩存和硬盤(pán)緩存同時(shí)保存。
寫(xiě)文件到硬盤(pán)也在以單獨(dú) NSInvocationOperation 完成尤辱，
避免拖慢主線程砂豌。
18.SDImageCache 在初始化的時(shí)候會(huì)注冊(cè)一些消息通知，
在內(nèi)存警告或退到后臺(tái)的時(shí)候清理內(nèi)存圖片緩存光督，
應(yīng)用結(jié)束的時(shí)候清理過(guò)期圖片阳距。
19.SDWI 也提供了 UIButton+WebCache 和
MKAnnotationView+WebCache，方便使用结借。
20.SDWebImagePrefetcher 可以預(yù)先下載圖片筐摘，
方便后續(xù)使用。
2.強(qiáng)連通分量了解嘛船老？
概念：
有向圖強(qiáng)連通分量：在有向圖G中咖熟，如果兩個(gè)頂點(diǎn)vi,vj間（vi>vj）有一條從vi到vj的有向路徑，同時(shí)還有一條從vj到vi的有向路徑柳畔，則稱兩個(gè)頂點(diǎn)強(qiáng)連通(strongly connected)馍管。如果有向圖G的每?jī)蓚€(gè)頂點(diǎn)都強(qiáng)連通，稱G是一個(gè)強(qiáng)連通圖薪韩。有向圖的極大強(qiáng)連通子圖确沸，稱為強(qiáng)連通分量(strongly connected components)。定義：有向圖強(qiáng)連通分量：在有向圖G中俘陷，如果兩個(gè)頂點(diǎn)間至少存在一條路徑罗捎，稱兩個(gè)頂點(diǎn)強(qiáng)連通（strongly connected）。
如果有向圖G的每?jī)蓚€(gè)頂點(diǎn)都強(qiáng)連通岭洲，則稱G是一個(gè)強(qiáng)連通圖。
非強(qiáng)連通圖有向圖的極大強(qiáng)連通子圖坎匿，成為強(qiáng)連通分量（strongly connected components）盾剩。
下圖中雷激，子圖{1,2,3,4}為一個(gè)強(qiáng)連通分量，因?yàn)轫旤c(diǎn)1,2,3,4兩兩可達(dá)告私，{5}屎暇，{6}也分別是兩個(gè)強(qiáng)連通分量。
強(qiáng)連通分量
直接根據(jù)定義驻粟，用雙向遍歷取交際的方法求強(qiáng)連通分量根悼，時(shí)間復(fù)雜度為O（N^2+M）。更好的方法是Kosaraju算法或者Tarjan算法蜀撑。
兩者的時(shí)間復(fù)雜度都是O（N+M）挤巡。本文介紹的是Tarjan算法。算法原理：（Tarjan）
Tarjan算法是基于對(duì)圖深度優(yōu)先搜索的算法酷麦，每個(gè)強(qiáng)連通分量為搜索樹(shù)中的一顆子樹(shù)矿卑。
搜索時(shí)，把當(dāng)前搜索樹(shù)中未處理的節(jié)點(diǎn)加入一個(gè)堆棧沃饶，回溯時(shí)可以盤(pán)對(duì)棧頂?shù)綏Ｖ械墓?jié)點(diǎn)是否為一個(gè)強(qiáng)連通分量母廷。
定義DFN（u）為節(jié)點(diǎn)u搜索的次序編號(hào)（時(shí)間戳）。Low（u）為u或者u的子樹(shù)能夠追溯到的最早的棧中的節(jié)點(diǎn)的次序號(hào)糊肤。
由定義可以得出：
Low（u）= Min { DFN（u）琴昆， Low（v）} （（u，v）為樹(shù)枝邊馆揉，u為v的父節(jié)點(diǎn)DFN（v）业舍，（u，v）為指向棧中節(jié)點(diǎn)的后向邊（非橫叉邊））
當(dāng)DFN（u）=Low（u）時(shí)把介，以u(píng)為根的搜索子樹(shù)上所有節(jié)點(diǎn)是一個(gè)強(qiáng)連通分量勤讽。
#include <string.h>
#include <vector>
#include <stack>
using namespace std;
#define MIN(a,b) ((a)<(b)?(a):(b))
#define N 10005 // 題目中可能的最大點(diǎn)數(shù)
stack<int>sta; // 存儲(chǔ)已遍歷的結(jié)點(diǎn)
vector<int>gra[N]; // 鄰接表表示圖
int dfn[N]; // 深度優(yōu)先搜索訪問(wèn)次序
int low[N]; // 能追溯到的最早的次序
int InStack[N]; // 檢查是否在棧中(2為在棧中，1為已訪問(wèn)拗踢，且不在棧中脚牍，0為不在)
vector<int> Component[N]; // 獲得強(qiáng)連通分量結(jié)果
int InComponent[N]; // 記錄每個(gè)點(diǎn)在第幾號(hào)強(qiáng)連通分量里
int index,ComponentNumber; // 索引號(hào)，強(qiáng)連通分量個(gè)數(shù)
int n, m; // 點(diǎn)數(shù)巢墅，邊數(shù)
int main()
{
while(scanf("%d%d",&n,&m),n+m)
{
init();
input();
solve();
}
}
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");
}
3.遇到tableView卡頓嘛诸狭？會(huì)造成卡頓的原因大致有哪些？
可能造成tableView卡頓的原因有：
1.最常用的就是cell的重用君纫， 注冊(cè)重用標(biāo)識(shí)符
如果不重用cell時(shí)驯遇，每當(dāng)一個(gè)cell顯示到屏幕上時(shí)，就會(huì)重新創(chuàng)建一個(gè)新的cell蓄髓；
如果有很多數(shù)據(jù)的時(shí)候叉庐，就會(huì)堆積很多cell。
如果重用cell会喝，為cell創(chuàng)建一個(gè)ID陡叠，每當(dāng)需要顯示cell 的時(shí)候玩郊，都會(huì)先去緩沖池中尋找可循環(huán)利用的cell，如果沒(méi)有再重新創(chuàng)建cell2.避免cell的重新布局
cell的布局填充等操作 比較耗時(shí)枉阵，一般創(chuàng)建時(shí)就布局好
如可以將cell單獨(dú)放到一個(gè)自定義類译红，初始化時(shí)就布局好3.提前計(jì)算并緩存cell的屬性及內(nèi)容
當(dāng)我們創(chuàng)建cell的數(shù)據(jù)源方法時(shí)，編譯器并不是先創(chuàng)建cell 再定cell的高度
而是先根據(jù)內(nèi)容一次確定每一個(gè)cell的高度兴溜，高度確定后侦厚，再創(chuàng)建要顯示的cell，滾動(dòng)時(shí)拙徽，每當(dāng)cell進(jìn)入憑虛都會(huì)計(jì)算高度刨沦，提前估算高度告訴編譯器，編譯器知道高度后斋攀，緊接著就會(huì)創(chuàng)建cell已卷，這時(shí)再調(diào)用高度的具體計(jì)算方法，這樣可以方式浪費(fèi)時(shí)間去計(jì)算顯示以外的cell4.減少cell中控件的數(shù)量
盡量使cell得布局大致相同淳蔼，不同風(fēng)格的cell可以使用不用的重用標(biāo)識(shí)符侧蘸，初始化時(shí)添加控件， 不適用的可以先隱藏
5.不要使用ClearColor鹉梨，無(wú)背景色讳癌，透明度也不要設(shè)置為0
渲染耗時(shí)比較長(zhǎng)
6.使用局部更新
如果只是更新某組的話，使用reloadSection進(jìn)行局部更新
7.加載網(wǎng)絡(luò)數(shù)據(jù)存皂，下載圖片晌坤，使用異步加載，并緩存
8.少使用addView 給cell動(dòng)態(tài)添加view
9.按需加載cell旦袋，cell滾動(dòng)很快時(shí)骤菠，只加載范圍內(nèi)的cell
10.不要實(shí)現(xiàn)無(wú)用的代理方法，tableView只遵守兩個(gè)協(xié)議
11.緩存行高
estimatedHeightForRow不能和HeightForRow里面的layoutIfNeed同時(shí)存在疤孕，這兩者同時(shí)存在才會(huì)出現(xiàn)“竄動(dòng)”的bug商乎。所以我的建議是：只要是固定行高就寫(xiě)預(yù)估行高來(lái)減少行高調(diào)用次數(shù)提升性能。如果是動(dòng)態(tài)行高就不要寫(xiě)預(yù)估方法了祭阀，用一個(gè)行高的緩存字典來(lái)減少代碼的調(diào)用次數(shù)即可
12.不要做多余的繪制工作鹉戚。
在實(shí)現(xiàn)drawRect:的時(shí)候，它的rect參數(shù)就是需要繪制的區(qū)域专控，這個(gè)區(qū)域之外的不需要進(jìn)行繪制抹凳。
例如上例中，就可以用CGRectIntersectsRect伦腐、CGRectIntersection或CGRectContainsRect判斷是否需要繪制image和text赢底，然后再調(diào)用繪制方法。13.預(yù)渲染圖像。
當(dāng)新的圖像出現(xiàn)時(shí)幸冻，仍然會(huì)有短暫的停頓現(xiàn)象嗅剖。解決的辦法就是在bitmap context里先將其畫(huà)一遍，導(dǎo)出成UIImage對(duì)象嘁扼，然后再繪制到屏幕；
14.使用正確的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)據(jù)黔攒。
4.M趁啸、V、C相互通訊規(guī)則你知道的有哪些督惰？
MVC 是一種設(shè)計(jì)思想不傅，一種框架模式，是一種把應(yīng)用中所有類組織起來(lái)的策略赏胚，它把你的程序分為三塊访娶，分別是：
M（Model）：實(shí)際上考慮的是“什么”問(wèn)題，你的程序本質(zhì)上是什么觉阅，獨(dú)立于 UI 工作崖疤。是程序中用于處理應(yīng)用程序邏輯的部分，通常負(fù)責(zé)存取數(shù)據(jù)典勇。
C（Controller）：控制你 Model 如何呈現(xiàn)在屏幕上劫哼，當(dāng)它需要數(shù)據(jù)的時(shí)候就告訴 Model，你幫我獲取某某數(shù)據(jù)割笙；當(dāng)它需要 UI 展示和更新的時(shí)候就告訴 View权烧，你幫我生成一個(gè) UI 顯示某某數(shù)據(jù)，是 Model 和 View 溝通的橋梁
V（View）：Controller 的手下伤溉，是 Controller 要使用的類般码，用于構(gòu)建視圖，通常是根據(jù) Model 來(lái)創(chuàng)建視圖的乱顾。要了解 MVC 如何工作板祝，首先需要了解這三個(gè)模塊間如何通信。
MVC通信規(guī)則
IMG_0997.jpgController to Model
可以直接單向通信糯耍。Controller 需要將 Model 呈現(xiàn)給用戶扔字，因此需要知道模型的一切，還需要有同 Model 完全通信的能力温技，并且能任意使用 Model 的公共 API革为。
Controller to View
可以直接單向通信。Controller 通過(guò) View 來(lái)布局用戶界面舵鳞。
Model to View
永遠(yuǎn)不要直接通信震檩。Model 是獨(dú)立于 UI 的，并不需要和 View 直接通信，View 通過(guò) Controller 獲取 Model 數(shù)據(jù)抛虏。
View to Controller
View 不能對(duì) Controller 知道的太多博其，因此要通過(guò)間接的方式通信。
Target action迂猴。首先 Controller 會(huì)給自己留一個(gè) target慕淡，再把配套的 action 交給 View 作為聯(lián)系方式。那么 View 接收到某些變化時(shí)沸毁，View 就會(huì)發(fā)送 action 給 target 從而達(dá)到通知的目的峰髓。這里 View 只需要發(fā)送 action，并不需要知道 Controller 如何去執(zhí)行方法息尺。代理:delegate
有時(shí)候 View 沒(méi)有足夠的邏輯去判斷用戶操作是否符合規(guī)范携兵，他會(huì)把判斷這些問(wèn)題的權(quán)力委托給其他對(duì)象，他只需獲得答案就行了搂誉，并不會(huì)管是誰(shuí)給的答案徐紧。
DataSoure。
View 沒(méi)有擁有他們所顯示數(shù)據(jù)的權(quán)力炭懊，View 只能向 Controller 請(qǐng)求數(shù)據(jù)進(jìn)行顯示并级，Controller 則獲取 Model 的數(shù)據(jù)整理排版后提供給 View。
Model 訪問(wèn) Controller
同樣的 Model 是獨(dú)立于 UI 存在的侮腹，因此無(wú)法直接與 Controller 通信死遭，但是當(dāng) Model 本身信息發(fā)生了改變的時(shí)候，會(huì)通過(guò)下面的方式進(jìn)行間接通信凯旋。Notification & KVO
一種類似電臺(tái)的方法呀潭，Model 信息改變時(shí)會(huì)廣播消息給感興趣的人 ，只要 Controller 接收到了這個(gè)廣播的時(shí)候就會(huì)主動(dòng)聯(lián)系 Model至非，獲取新的數(shù)據(jù)并提供給 View钠署。
從上面的簡(jiǎn)單介紹中我們來(lái)簡(jiǎn)單概括一下 MVC 模式的優(yōu)點(diǎn)。
1.低耦合性
2.有利于開(kāi)發(fā)分工
3.有利于組件重用
4.可維護(hù)性
5.NStimer準(zhǔn)嗎荒椭？談?wù)勀愕目捶ㄐ扯Γ咳绻粶?zhǔn)該怎樣實(shí)現(xiàn)一個(gè)精確的NSTimer?
1.不準(zhǔn)
2.不準(zhǔn)的原因如下：
1、NSTimer加在main runloop中趣惠，模式是NSDefaultRunLoopMode狸棍，main負(fù)責(zé)所有主線程事件，例如UI界面的操作味悄，復(fù)雜的運(yùn)算草戈，這樣在同一個(gè)runloop中timer就會(huì)產(chǎn)生阻塞。
2侍瑟、模式的改變唐片。主線程的 RunLoop 里有兩個(gè)預(yù)置的 Mode：kCFRunLoopDefaultMode 和 UITrackingRunLoopMode丙猬。
當(dāng)你創(chuàng)建一個(gè) Timer 并加到 DefaultMode 時(shí)，Timer 會(huì)得到重復(fù)回調(diào)费韭，但此時(shí)滑動(dòng)一個(gè)ScrollView時(shí)茧球，RunLoop 會(huì)將 mode 切換為 TrackingRunLoopMode，這時(shí) Timer 就不會(huì)被回調(diào)星持，并且也不會(huì)影響到滑動(dòng)操作抢埋。所以就會(huì)影響到NSTimer不準(zhǔn)的情況。
PS:DefaultMode 是 App 平時(shí)所處的狀態(tài)督暂，rackingRunLoopMode 是追蹤 ScrollView 滑動(dòng)時(shí)的狀態(tài)羹令。方法一：
1、在主線程中進(jìn)行NSTimer操作损痰，但是將NSTimer實(shí)例加到main runloop的特定mode（模式）中。避免被復(fù)雜運(yùn)算操作或者UI界面刷新所干擾酒来。
self.timer = [NSTimer timerWithTimeInterval:1 target:self selector:@selector(showTime) userInfo:nil repeats:YES];
[[NSRunLoop currentRunLoop] addTimer:self.timer forMode:NSRunLoopCommonModes];
2卢未、在子線程中進(jìn)行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é)：
一開(kāi)始的時(shí)候系統(tǒng)就為我們將主線程的main runloop隱式的啟動(dòng)了辽社。
在創(chuàng)建線程的時(shí)候，可以主動(dòng)獲取當(dāng)前線程的runloop翘鸭。每個(gè)子線程對(duì)應(yīng)一個(gè)runloop方法二：
使用示例
使用mach內(nèi)核級(jí)的函數(shù)可以使用mach_absolute_time()獲取到CPU的tickcount的計(jì)數(shù)值滴铅，可以通過(guò)”mach_timebase_info”函數(shù)獲取到納秒級(jí)的精確度 。然后使用mach_wait_until(uint64_t deadline)函數(shù)就乓，直到指定的時(shí)間之后汉匙，就可以執(zhí)行指定任務(wù)了。
關(guān)于數(shù)據(jù)結(jié)構(gòu)mach_timebase_info的定義如下：
#include <mach/mach.h>
#include <mach/mach_time.h>
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替代生蚁！
