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