(劍指offer)[https://github.com/CyC2018/CS-Notes/blob/master/notes/劍指%20offer%20題解.md#1-前言]

(iOS 劍指offer集錦)[http://www.reibang.com/p/ae89e1c08329]

1栅屏、M*N格子走多少步典予？

遞歸算法：
-(int)totalMethod:(int)m and:(int)n{
    if(m == 0 && n == 0){
        return 0;
    }
    
    if (m ==0 || n == 0) {
        return 1;
    }
    
    return [self totalMethod:n-1 and:m] + [self totalMethod:n and:m-1];
}

2匙隔、計(jì)算n的階乘

-(long long)totalN:(int)n{
    if(n <= 1){
        return 1;
    }
    return n*[self totalN:n-1];
}

3涉馅、實(shí)現(xiàn)一個(gè)計(jì)算器
(http://www.reibang.com/p/34002d66a43e)

1）將輸入的運(yùn)算式轉(zhuǎn)化為由運(yùn)算符和運(yùn)算數(shù)組成的數(shù)組;

準(zhǔn)備好運(yùn)算數(shù)的棧和運(yùn)算符的棧般贼；
3）依次讀入數(shù)組中的元素，若是運(yùn)算數(shù)則直接壓入運(yùn)算數(shù)棧祠肥，若是運(yùn)算符則將該運(yùn)算符的優(yōu)先級(jí)和運(yùn)算符棧頂元素優(yōu)先級(jí)比較纸镊，有以下情況：
a)若前者大，則該運(yùn)算符直接入棧檐晕；
b)若后者大暑诸，則彈出棧頂運(yùn)算符，并彈出兩個(gè)運(yùn)算數(shù)辟灰，將運(yùn)算結(jié)果壓入運(yùn)算數(shù)棧个榕；
c）若兩者相等，則兩者抵消芥喇。
如此直到運(yùn)算符棧清空西采，得到最后結(jié)果。

4继控、有序數(shù)組合并

5械馆、反轉(zhuǎn)二叉樹

@interface TreeNode : NSObject
@property (nonatomic, assign) NSInteger val;
@property (nonatomic, strong) TreeNode *left;
@property (nonatomic, strong) TreeNode *right;


- (void)exchangeNode:(TreeNode *)node {
    
    //判斷是否存在node節(jié)點(diǎn)
    if(node) {
        //交換左右節(jié)點(diǎn)
        TreeNode *temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
 
- (TreeNode *)invertTree:(TreeNode *)root
{
    //邊界條件 遞歸結(jié)束或輸入為空情況
    if(!root) {
       return root;
    }
 
    //遞歸左右子樹
    [self invertTree:root.left];
    [self invertTree:root.right];
    //交換左右子節(jié)點(diǎn)
    [self exchangeNode:root];
 
    return root;
}

6、二叉樹先序遍歷[http://www.reibang.com/p/a270d117e116]

+ (void)preOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler {
    if (rootNode) {
        
        if (handler) {
            handler(rootNode);
        }
        
        [self preOrderTraverseTree:rootNode.leftNode handler:handler];
        [self preOrderTraverseTree:rootNode.rightNode handler:handler];
    }
}

【算法武通，排序霹崎，字符串，數(shù)組冶忱，位操作尾菇，回朔，雙指針，DFS深度優(yōu)先错沽，BFS廣度優(yōu)先簿晓，DP動(dòng)態(tài)規(guī)劃，分治千埃；
kvo本質(zhì)憔儿，kvc本質(zhì)，block本質(zhì)放可，分類本質(zhì)】

7谒臼、數(shù)組中重復(fù)的數(shù)字
長(zhǎng)度為n的數(shù)組中所有數(shù)字都在0到n-1范圍內(nèi)，某些數(shù)字是重復(fù)的耀里。請(qǐng)找出數(shù)組任意一個(gè)重復(fù)的數(shù)字蜈缤。

思路：遍歷查找，如果i跟遍歷值num相同冯挎，則是重復(fù)的值底哥；如果不等，則交換第i的值和num的值房官。
+ (NSArray *)duplicate:(NSArray *)nums {
    if (nums == nil || nums.count == 0) {
        return nil;
    }
    
    NSMutableArray *numbers = [NSMutableArray arrayWithArray:nums];
    NSMutableArray *temp = [NSMutableArray array];
    
    for (int i = 0; i < numbers.count; i++) {
        while ([numbers[i] intValue] != i) {
            int number = [numbers[i] intValue];
            // 檢查 number 與第 number 位置上的值是否相等,如果相等,說明該 number 重復(fù)了,否則索引 i 和 number 兩者的值
            if (number == [numbers[number] intValue]) {
                [temp addObject:numbers[i]];
                return temp.copy;
            }
            [self cs_swap:numbers i:i j:number];
        }
    }
    
    return nil;
}

// 交換數(shù)組中i 和 j 位置上的數(shù)字
+ (void)cs_swap:(NSMutableArray *)numbers i:(int)i j:(int)j {
    if (i >= numbers.count || j >= numbers.count) {
        return;
    }
    NSNumber *number = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = number;
}

8趾徽、二維數(shù)組查找
在一個(gè)二維數(shù)組中，每一行從左到右遞增排序翰守，每一列從上到下遞增排序孵奶。請(qǐng)完成一個(gè)函數(shù)，輸入一個(gè)二維數(shù)組和一個(gè)整數(shù)蜡峰，判斷數(shù)組中是否含有該整數(shù)了袁。

思路：二維數(shù)組行數(shù)，列數(shù)固定湿颅，從右上角開始找载绿。
定義一個(gè)行，一個(gè)列肖爵，如果target比右上角小卢鹦，列數(shù)減1，比右上角大劝堪，行數(shù)加1冀自。逐步查詢：
// 初始化一個(gè)二維數(shù)組
+ (bool)findNumber:(int)number numbers:(NSArray *)numbers {
    if (numbers == nil) {
        NSArray *number1 = @[@1,@4,@7,@11,@15];
        NSArray *number2 = @[@2,@5,@8,@12,@19];
        NSArray *number3 = @[@3,@6,@9,@16,@22];
        NSArray *number4 = @[@10,@13,@14,@17,@24];
        NSArray *number5 = @[@18,@21,@23,@26,@30];
        numbers = @[number1,number2,number3,number4,number5];
    }
    return [self find:number matrix:numbers];
}

// 在二維數(shù)組 matrix 中查找目標(biāo)數(shù) target
+ (bool)find:(int)target matrix:(NSArray *)matrix {
    if (matrix == nil || matrix.count == 0) {
        return false;
    }
    NSUInteger rows = matrix.count;    // 行數(shù)
    NSArray *colArray = matrix[0];
    NSUInteger cols = colArray.count;  // 列數(shù)
    int r = 0;  // 第 r 行
    int c = (int)cols - 1; // 第 c 列 從右上角開始
    
    while (r <= rows - 1 && c >= 0) {
        if (target == [matrix[r][c] integerValue]) {
            NSLog(@"target = %d, row = %d, col = %d",target,r,c);
            return true;
        } else if (target > [matrix[r][c] integerValue]) {
            r++; // 行數(shù)+1
        } else {
            c--;    // 列數(shù)減1
        }
    }
    return false;
}