本文正在参与「金石方案 . 分割6万现金大奖」
前语
- iOS日常开发中, 算法运用的多吗? 脚踏实地的来说, 是不多的.
- 那算法的学习对iOSer来说, 就不需求了吗? 答案是很需求.
- iOS的日常开发中, 用到的算法确实不多, 但是算法在iOS开发里边的运用都被封装在各种常用API的内部了.
- 对算法的学习, 可以提高对iOS底层的理解与认识, 这些算法的常识是计算机技术领域通用的. 下面就iOS开发中一些经典的算法进行一个简单的整理.
- 文章纯手打, 抛砖引玉, 如有过错还请评论区纠正, 先行谢过了:)
1. 哈希算法, 在一个字符串中找到第一个, 只呈现一次的字符.
- 在字符串 s 中找出第一个只呈现一次的字符。假如没有，返回一个单空格。 s 只包含小写字母。
输入：s = "abaccdeff"
输出：'b'
输入：s = ""
输出：' '
- 算法思路:
- 字符(char)是一个长度为8的数据类型, 因而总共有256种或许.
- 每个字符依据其ASCII码值作为数组的下标对应数组的一个数字.
- 数组中存储的是每个字符呈现的次数.
- 运用C言语的回答:
char firstUniqChar(char* s){
char result = '\0';
// 1. 界说一个数组, 用来存储各个字母呈现的次数
int array[256];
// 2. 对数组进行初始化操作
for (int i = 0; i < 256; i++) {
array[i] = 0;
}
// 3. 界说一个指针, 指向当前字符串头部
char *p = s;
// 4. 遍历每个字符, 在字母对应存储方位, 进行呈现次数+1操作
while (*p != '\0') {
array[*(p++)]++;
}
// 5. 将P指针从头指向字符串头部
p = s;
// 6. 遍历每个字母呈现次数, 遇到第一个呈现次数为1的字符, 打印成果, 反之持续向后遍历
while (*p != '\0') {
if (array[*p] == 1) {
result = *p;
return result;
break;
}
p++;
}
return ' ';
}
- 力扣链接
2. 求无序数组当中的中位数
2.1 排序算法 + 中位数
- 冒泡排序 快速排序 堆排序
- 中位数
当n为奇数时, (n + 1)/2
当n为偶数时, (n/2 + (n/2 + 1))/2
2.2 运用快排思想(分治思想)
- 选取关键字, 高低指针替换扫描
-
- 找到第一个比关键字大的
-
- 找到第一个比关键字小的
- 恣意挑一个元素, 以该元素为支点, 区分集合为两部分.
- 假如左边集合长度恰为
(n-1)/2, 那么支点恰为中位数. - 假如
左边长度<(n-1)/2, 那么中位点在右侧; 反之, 中位数在左边. - 进入相应的一侧持续寻找中位点.
- 运用C言语的回答:
int findMedian(int a[], int aLen) {
int low = 0;
int high = aLen -1;
int mid = (aLen - 1) / 2;
int div = PartSort(a, low, high);
while (div != mid) {
if (mid < div) {
// 左半区间找
div = PartSort(a, low, div - 1);
}
else {
// 右半区间找
div = PartSort(a, div + 1, high);
}
}
// 找到了
return a[mid];
}
int PartSort(int a[], int start, int end) {
int low = start;
int high = end;
// 选取关键字
int key = a[end];
while (low < high) {
// 左边找比key大的值
while (low < high && a[low] <= key) {
++low;
}
// 右边找比key小的值
while (low < high && a[high] >= key) {
--high;
}
if (low < high) {
// 找到之后交流左右的值
int temp = a[low];
a[low] = a[high];
a[high] = temp;
}
}
int temp = a[high];
a[high] = a[end];
a[end] = temp;
return low;
}
- 验证代码:
// 无序数组查找中位数
int list[9] = {12, 3, 10, 8, 9, 7, 6, 11, 16};
int median = findMedian(list, 9);
printf("the median is %d \n", median);
3. 查找两个子视图的共同父视图
- 算法思路图解:
- 运用Objective-C言语的回答:
- (void)viewDidLoad {
[super viewDidLoad];
self.view.tag = 666;
UIView *view0 = [UIView new];
view0.tag = 777;
UIView *view1 = [UIView new];
view1.tag = 1;
UIView *view2 = [UIView new];
view2.tag = 2;
UIView *view3 = [UIView new];
view3.tag = 3;
[self.view addSubview:view0];
[view0 addSubview:view1];
[view1 addSubview:view2];
[view2 addSubview:view3];
UIView *view4 = [UIView new];
[view3 addSubview:view4];
UIView *view5 = [UIView new];
[view2 addSubview:view5];
NSArray *commonSuperViewArray = [self findCommonSuperView:view4 other:view5];
NSLog(@"commonSuperViewArray === %@", commonSuperViewArray);
}
// 查找两个视图的共同父视图
- (NSArray<UIView *> *)findCommonSuperView:(UIView *)oneView other:(UIView *)anotherView {
NSMutableArray *result = [NSMutableArray array];
// 查找第一个视图的一切父视图
NSArray *arrayOne = [self findSuperViews:oneView];
// 查找第一个视图的一切父视图
NSArray *arrayOther = [self findSuperViews:anotherView];
int i = 0;
// 越界限制条件
while (i < MIN(arrayOne.count, arrayOther.count)) {
// 倒序方法获取各个视图的父视图
UIView *superOne = [arrayOne objectAtIndex:arrayOne.count - i - 1];
UIView *superOhter = [arrayOther objectAtIndex:arrayOther.count - i - 1];
// 比较假如持平, 则为共同父视图
if (superOne == superOhter) {
[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;
}
发文不易, 喜爱点赞的人更有好运气 :), 定时更新+重视不走失~
ps：欢迎参与笔者18年树立的研究iOS审阅及前沿技术的三千人扣群：662339934，坑位有限，补白“网友”可被群管通过~
本文正在参与「金石方案 . 分割6万现金大奖」
