2021 - sf

作者: 世玉茹花 | 来源:发表于2021-06-01 17:34 被阅读0次

    (剑指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;
    }
    

    相关文章

      网友评论

          本文标题:2021 - sf

          本文链接:https://www.haomeiwen.com/subject/wbwksltx.html