11 算法
2021-03-27 本文已影响0人
i爱吃土豆的猫
LRU 算法
反转二叉树
image.png
声明节点属性
@interface TreeNode : NSObject
@property (nonatomic, assign) NSInteger val;
@property (nonatomic, strong) TreeNode *left;
@property (nonatomic, strong) TreeNode *right;
@end
实现代码:
- (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;
}
image.png
image.png
image.png
头插入发
链表反转
image.png
image.png
image.png
1.假设两个数组为A和B
2.A和B都是从小到大的顺序进行排列
1.我们可以直接比较两个数组的首元素，哪个小就把这个小元素放入可变数组。
2.把小元素所在的数组中的这个元素删除。
3.继续比较两个数组中的首元素，直到有一个数组为空。那么就停止进行比较。把另外一个不空的数组元素全部放入可变数组中即可。
复杂度
//(2).
//时间复杂度
//T(n) = O(f(n)):用"T(n)"表示，"O"为数学符号，f(n)为同数量级，一般是算法中频度最大的语句频度。
//时间复杂度:T(n) = O(index);
- (void)merge 1{
/*
有序数组A：1、4、5、8、10...1000000，有序数组B：2、3、6、7、9...999998，A、B两个数组不相互重复，请合并成一个有序数组C，写出代码和时间复杂度。
*/
//(1).
NSMutableArray *A = [NSMutableArray arrayWithObjects:@4,@5,@8,@10,@15, nil];
// NSMutableArray *B = [NSMutableArray arrayWithObjects:@2,@6,@7,@9,@11,@17,@18, nil];
NSMutableArray *B = [NSMutableArray arrayWithObjects:@2,@6,@7,@9,@11,@12,@13, nil];
NSMutableArray *C = [NSMutableArray array];
int count = (int)A.count+(int)B.count;
int index = 0;
for (int i = 0; i < count; i++) {
if (A[0]<B[0]) {
[C addObject:A[0]];
[A removeObject:A[0]];
}
else if (B[0]<A[0]) {
[C addObject:B[0]];
[B removeObject:B[0]];
}
if (A.count==0) {
[C addObjectsFromArray:B];
NSLog(@"C = %@",C);
index = i+1;
NSLog(@"index = %d",index);
return;
}
else if (B.count==0) {
[C addObjectsFromArray:A];
NSLog(@"C = %@",C);
index = i+1;
NSLog(@"index = %d",index);
return;
}
}
//(2).
//时间复杂度
//T(n) = O(f(n)):用"T(n)"表示，"O"为数学符号，f(n)为同数量级，一般是算法中频度最大的语句频度。
//时间复杂度:T(n) = O(index);
}
//合并方法 2
- (void)merge2{
//实例化数组 A
NSMutableArray *arrA = [NSMutableArray arrayWithArray:@[@1,@3,@5,@7,@9,@11]];
//实例化数组 B
NSMutableArray *arrB = [NSMutableArray arrayWithArray:@[@8,@15,@17,@20,@22,@35]];
NSMutableArray *marr = [NSMutableArray array];
for(int i = 0; i< 100 ; i++){
if (arrA[0] < arrB[0]){
[marr addObject:arrA[0]];
[arrA removeObject:arrA[0]];
}else{
[marr addObject:arrB[0]];
[arrB removeObject:arrB[0]];
}
NSLog(@"已经循环了--->>%d次",i);
if (arrA.count == 0){
[marr addObjectsFromArray:arrB];
NSLog(@"111新数组--->>%@",marr);
return;
}
if (arrB.count == 0){
[marr addObjectsFromArray:arrA];
NSLog(@"222新数组---->> %@",marr);
return;
}
}
}
能根据传入的数组准确的算出来 推荐的方法
- (NSArray *)mergeOrderArrayWithArray: (NSMutableArray *)array1 array2:(NSMutableArray *)array2 {
// 全为空不处理
if (array1.count == 0 && array2.count == 0) {
return @[];
}
// 一个为空返回另外一个
if (array1.count == 0) {
return array2;
}
if (array2.count == 0) {
return array1;
}
NSMutableArray *endArray = [NSMutableArray array];
while (1) {
if ([array1[0] integerValue] < [array2[0] integerValue]) {
[endArray addObject:array1[0]];
[array1 removeObjectAtIndex:0];
}else {
[endArray addObject:array2[0]];
[array2 removeObjectAtIndex:0];
}
if (array1.count==0) {
[endArray addObjectsFromArray:array2];
break;
}
if (array2.count==0) {
[endArray addObjectsFromArray:array1];
break;
}
}
return endArray;
}
image.png
image.png
image.png
- (NSArray <UIView *> *)findCommonSuperView:(UIView *)viewOne other:(UIView *)viewOther{
NSMutableArray *result = [NSMutableArray array];
// 查找第一个视图的所有父视图
NSArray *arrayOne = [self findSuperViews:viewOne];
// 查找第二个视图的所有父视图
NSArray *arrayOther = [self findSuperViews:viewOther];
int i = 0;
// 越界限制条件
while (i < MIN((int)arrayOne.count, (int)arrayOther.count)) {
// 倒序方式获取各个视图的父视图
UIView *superOne = [arrayOne objectAtIndex:arrayOne.count - i - 1];
UIView *superOther = [arrayOther objectAtIndex:arrayOther.count - i - 1];
// 比较如果相等 则为共同父视图
if (superOne == superOther) {
[result addObject:superOne];
i++;
}
// 如果不相等，则结束遍历
else{
break;
}
}
return result;
}
- (NSArray <UIView *> *)findSuperViews:(UIView *)view{
// 初始化为第一父视图
UIView *temp = view.superview;
// 保存结果的数组
NSMutableArray *result = [NSMutableArray array];
while (temp) {
[result addObject:temp];
// 顺着superview指针一直向上查找
temp = temp.superview;
}
return result;
}
image.png
image.png
image.png
image.png
image.png
