iOS算法
2020-10-20 本文已影响0人
Li_Po
-
字符串反转
//调用 char cha[] = "hello,word"; char_reverse(cha); printf("revers result is %s",cha); //实现 void char_reverse(char * cha){ char * begin = cha; char * end = cha + strlen(cha)-1; while (begin<end) { char temp = *begin; *(begin++) = *end; *(end--) = temp; } } -
链表反转
//调用 struct Node * head = constructList(); printList(head); struct Node * newH = reversList(head); printList(newH); //.h文件 struct Node { int data; struct Node * next; }; @interface ReversList : NSObject //链表反转 struct Node * reversList(struct Node * head); //构建链表 struct Node * constructList(void); //打印链表中的数据 void printList(struct Node * head); @end //.m文件 #import "ReversList.h" @implementation ReversList //链表反转 struct Node * reversList(struct Node * head){ //定义遍历指针,初始化为头节点 struct Node * p = head; //反转后的链表头部 struct Node * newHead = NULL; //遍历链表 while (p != NULL) { // 记录下一个节点 struct Node * temp = p->next; //当前节点指的next指向新的链表头部 p->next = newHead; //更改新链表头部为当前节点 newHead = p; //移动p指针 p = temp; } //返回反转后的头节点 return newHead; } //构建链表 struct Node * constructList(void){ //头节点定义 struct Node * head = NULL; //记录当前尾节点 struct Node * cur = NULL; for (int i=1; i<5; i++) { struct Node * node = malloc(sizeof(struct Node)); node->data = I; if (head == NULL) { //头节点为空，新节点即为头节点 head = node; }else{ //当前节点的next为新节点 cur->next = node; } //设置当前节点为新节点 cur = node; } return head; } //打印链表中的数据 void printList(struct Node * head){ struct Node * tmp = head; while (tmp != NULL) { printf("node id %d \n",tmp->data); tmp = tmp->next; } } @end -
有序数组合并
//有序数组合并 归并算法 调用 int a[5] = {1,4,6,7,9}; int b[8] = {2,3,5,6,8,10,11,12}; int result[13]; mergeList(a, 5, b, 8, result); for (int i=0; i<13; i++) { printf("%d,",result[I]); } //有序数组合并 归并算法 实现 void mergeList(int a[],int aLen,int b[],int bLen,int result[]){ int p = 0; int q = 0; int i = 0; while (p<aLen && q<bLen) { if (a[p]<=b[q]) { result[i] = a[p++]; }else{ result[i] = b[q++]; } I++; } while (p<aLen) { result[i] = a[p++]; I++; } while (q<bLen) { result[i] = b[q++]; I++; } } -
hash 哈希算法
char cha[] = "abaccdef"; char result = findFirstChar(cha); printf("this is %c",result); //hash 哈希算法 找出第一个只出现一次的字母 char findFirstChar(char * cha){ char result = '\0'; int array[256]; for (int i=0; i<256; i++) { array[i] = 0; } char *p = cha; while (*p != '\0') { array[*(p++)]++; } p = cha; while (*p != '\0') { if (array[*p]==1) { result = *p; break; } p++; } return result; } -
查找无需数组的中位数
1.排序算法+中位数
当数组个数n为基数时：中位数=array[(n/2)]
当数组个数n为偶数时：中位数=(array[(n/2-1)]+array[(n/2)])/2
2.利用快排思想
image.png
//利用快排思想求中位数
|2|4|6|8|
//调用
int list[9] = {12,3,10,8,6,7,11,13,9};
int median = medianFind(list, 9);
printf("the median is %d",median);
//求一个无需数组的我中位数
int medianFind(int a[],int len)
{
int low = 0;
int high = len-1;
int mid = (len-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[end]>=key) {
--high;
}
//找到之后交换左右的值
if (low<high) {
int tmp = a[low];
a[low] = a[high];
a[high] = tmp;
}
}
int tmp = a[high];
a[high] = a[end];
a[end] = tmp;
return low;
}
-
查找两个子视图共同所有的父视图
-(NSArray<UIView *> *)findCommonSuperView:(UIView *)view1 :(UIView *)view2{ NSArray * arr1 = [self findSuperView:view1]; NSArray * arr2 = [self findSuperView:view2]; NSMutableArray * results = [NSMutableArray array]; int I=0; while (i<MIN(arr1.count, arr2.count)) { if (arr1[arr1.count-i-1] == arr2[arr2.count-i-1]) { [results addObject:arr1[arr1.count-i-1]]; I++; }else{ break; } } return results; } -(NSArray<UIView *> *)findSuperView:(UIView *)view{ NSMutableArray * results = [NSMutableArray array]; UIView * v1 = view.superview; while (v1) { [results addObject:v1]; v1 = v1.superview; } return results; } -
m*n的矩阵点（m>0,n>0），m为x坐标，n为y坐标(x轴向右，y轴向下),从（0，0）位置，初始方向向右移动，移动到边或者下一节点已经走过时，需要改变方向，改变的顺序为顺时针。
求最后走到的点坐标。#import "matrixObject.h" @interface matrixObject() @property (nonatomic,strong)NSMutableArray * poinaArray; @end @implementation matrixObject - (instancetype)init { self = [super init]; if (self) { _poinaArray = [NSMutableArray array]; [self testSatrtArray:@[@0,@0] endArray:@[@3,@3]];//调用 } return self; } #pragma mark -- 递归 -(void)testSatrtArray:(NSArray *)startArray endArray:(NSArray *)pointArray{ //起点（startX，startY） 矩阵点（m,n） 移动的点（x,y） int x= [startArray[0] intValue]; int startX= [startArray[0] intValue]; int y = [startArray[1] intValue]; int startY = [startArray[1] intValue]; int m = [pointArray[0] intValue]; int n = [pointArray[1] intValue]; while (x<m && y<n) { NSString * pointStr = [NSString stringWithFormat:@"%d,%d",x,y]; if (![_poinaArray containsObject: pointStr]) { if (x<m && y<n) { //向右移动 x++ while (x<m) { [_poinaArray addObject:[NSString stringWithFormat:@"%d,%d",x,y]]; x++; } } if (x==m && y<n) { //向下移动 y++ while (y<n) { [_poinaArray addObject:[NSString stringWithFormat:@"%d,%d",x,y]]; y++; } } if (x==m && y==n) { //向左移动 x-- while (x>startX) { [_poinaArray addObject:[NSString stringWithFormat:@"%d,%d",x,y]]; x--; } } if (x==startX && y==n) { //向上移动 y-- while (y>startY) { [_poinaArray addObject:[NSString stringWithFormat:@"%d,%d",x,y]]; y--; } } }else{ ++x; ++y; --m; --n; if (x<m && y<n) { [self testSatrtArray:@[@(x),@(y)] endArray:@[@(m),@(n)]]; }else{ if (x==m && y==n) {//当起点和矩阵点相同时只记录原点 [_poinaArray addObject:[NSString stringWithFormat:@"%d,%d",x,y]]; } NSLog(@"最后走到的点坐标:%@",[_poinaArray lastObject]);//(1,2) NSLog(@"x:%d y:%d m:%d n:%d \n _poinaArray:(%@)",x,y,m,n,[_poinaArray componentsJoinedByString:@")("]); //x:2 y:2 m:1 n:1 //_poinaArray:(0,0)(1,0)(2,0)(3,0)(3,1)(3,2)(3,3)(2,3)(1,3)(0,3)(0,2)(0,1)(1,1)(2,1)(2,2)(1,2) break; } } }; } @end
