2021 - sf

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

(iOS 剑指offer集锦)[https://www.jianshu.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、计算n的阶乘

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

3、实现一个计算器
(https://www.jianshu.com/p/34002d66a43e)

1）将输入的运算式转化为由运算符和运算数组成的数组;

准备好运算数的栈和运算符的栈；
3）依次读入数组中的元素，若是运算数则直接压入运算数栈，若是运算符则将该运算符的优先级和运算符栈顶元素优先级比较，有以下情况：
a)若前者大，则该运算符直接入栈；
b)若后者大，则弹出栈顶运算符，并弹出两个运算数，将运算结果压入运算数栈；
c）若两者相等，则两者抵消。
如此直到运算符栈清空，得到最后结果。

4、有序数组合并

5、反转二叉树

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


- (void)exchangeNode:(TreeNode *)node {
    
    //判断是否存在node节点
    if(node) {
        //交换左右节点
        TreeNode *temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
 
- (TreeNode *)invertTree:(TreeNode *)root
{
    //边界条件 递归结束或输入为空情况
    if(!root) {
       return root;
    }
 
    //递归左右子树
    [self invertTree:root.left];
    [self invertTree:root.right];
    //交换左右子节点
    [self exchangeNode:root];
 
    return root;
}

6、二叉树先序遍历[https://www.jianshu.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];
    }
}

【算法，排序，字符串，数组，位操作，回朔，双指针，DFS深度优先，BFS广度优先，DP动态规划，分治；
kvo本质，kvc本质，block本质，分类本质】

7、数组中重复的数字
长度为n的数组中所有数字都在0到n-1范围内，某些数字是重复的。请找出数组任意一个重复的数字。

思路：遍历查找，如果i跟遍历值num相同，则是重复的值；如果不等，则交换第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 重复了,否则索引 i 和 number 两者的值
            if (number == [numbers[number] intValue]) {
                [temp addObject:numbers[i]];
                return temp.copy;
            }
            [self cs_swap:numbers i:i j:number];
        }
    }
    
    return nil;
}

// 交换数组中i 和 j 位置上的数字
+ (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、二维数组查找
在一个二维数组中，每一行从左到右递增排序，每一列从上到下递增排序。请完成一个函数，输入一个二维数组和一个整数，判断数组中是否含有该整数。

思路：二维数组行数，列数固定，从右上角开始找。
定义一个行，一个列，如果target比右上角小，列数减1，比右上角大，行数加1。逐步查询：
// 初始化一个二维数组
+ (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];
}

// 在二维数组 matrix 中查找目标数 target
+ (bool)find:(int)target matrix:(NSArray *)matrix {
    if (matrix == nil || matrix.count == 0) {
        return false;
    }
    NSUInteger rows = matrix.count;    // 行数
    NSArray *colArray = matrix[0];
    NSUInteger cols = colArray.count;  // 列数
    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++; // 行数+1
        } else {
            c--;    // 列数减1
        }
    }
    return false;
}