主要算法大纲
问题一： 请实现字符串反转的算法。
主要思路：两个指针分别指向字符串的一头一尾地址，然后交换两个指针的内容，交换完毕后，指针从两端向中间移动，重复交换和移动操作。直到 begin 指针的地址大于等于 end 指针，就结束程序完成交互。
// code
void characterReverse(char* cha) {
char* begin = &cha[0];
char* end = cha + strlen(cha) - 1;
while (begin < end) {
char temp = *begin;
*(begin++) = *end;
*(end--) = temp;
}
}
// usage
- (void)learnCharacterReverse {
char cha[]= "Hello,World";
characterReverse(cha);
printf("reverse result is %s \n", cha);
}
问题二： 请实现链表的反转。
主要思路：创建两个指针，一个用来存放反转的新链表，一个用来存当前链表。利用头插法，把旧链表上的数据一个个插入新链表的头部。特别注意一点在于，要先存链表的下一个结点，不然插入之后会丢失链表数据。
// .h
#import <Foundation/Foundation.h>
struct Node {
int data;
struct Node* next;
};
@interface ChainReverse : NSObject
// 链表反转
struct Node* chain_reverse(struct Node* head);
// 构建一个列表
struct Node* constructionChains(void);
// 打印链表
void printChain(struct Node *head);
@end
// .m文件
#import "ChainReverse.h"
@implementation ChainReverse
// 链表反转
struct Node* chain_reverse(struct Node* head) {
// 定义遍历指针,初始化头结点
struct Node* p = head;
// 反转后的链表头部
struct Node *newH = NULL;
// 遍历链表
while (p != NULL) {
// 先记录下一个结点
struct Node* temp = p->next;
// 当前结点的 nex 执行新链表的头部
p->next = newH;
// 更改新链表头部为当前结点
newH = p;
// 移动 p 指针
p = temp;
}
return newH;
};
// 构建一个列表
struct Node* constructionChains(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;
node->next = NULL;
if (head == NULL) {
head = node;
} else {
cur->next = node;
}
cur = node;
}
return head;
}
// 打印链表
void printChain(struct Node *head) {
struct Node* cur = NULL;
cur = head;
while (cur != NULL) {
printf("%i \n", cur->data);
cur = cur->next;
};
printf("===============\n");
}
@end
// 用法
- (void)learnChainReverse {
struct Node* head = constructionChains();
printChain(head);
struct Node* newHead = chain_reverse(head);
printChain(newHead);
}
问题三：请实现两个有序数组合并成一个有序数据的算法。
算法思路：分别从两个有序数组头部开始取数组，对比大小，把小的值插入新数组，然后小的值所在数据角标+1，如此重复，直到其中一方数组没有数据了，把另一个数组剩余的值全部插入新数组，完成合并。
// 将有序数据 a 和 b 的值合并到一个数据 result当中,且仍然保持有序
void mergeList(int a[], int aLen, int b[], int bLen, int result[]) {
int p = 0; // 记录数组 a 的位置
int q = 0; // j遍历数组 b 的位置
int i = 0; // 记录当前存储 z 位置
while (p < aLen && q < bLen) {
if (a[p] < b[q]) {
result[i] = a[p];
p++;
} else {
result[i] = b[q];
q++;
}
i++;
}
while (p < aLen) {
result[i] = a[p];
p++;
i++;
}
while (q < bLen) {
result[i] = b[q];
q++;
i++;
}
}
问题四：请用哈希算法来实现查找字符串中第一个只出现一次的字符。
算法思路：所谓 hash 算法，就是利用哈希函数做一个映射，从而由 key 经过 f(key) 高效的找到结果。所以我们可以把字符当成 ASCII 码作为 key 并且当成一个数组的脚本，数组的 value 就是出现的次数。
char findFirstChar(char *cha) {
// 用来移动的指针
char *p = cha;
// 初始化一个数组
int array[256];
for (int i = 0 ; i < 256; i++) {
array[i] = 0;
}
// 结果存放处
char result = '\0';
// 遍历并且给数组赋值
while (*p != '\0') {
array[*(p++)]++;
}
p = cha;
// 查找value 为 1 的字符
while (*p != '\0') {
if (array[*p] == 1) {
result = *p;
break;
}
p++;
}
return result;
}
问题五：查找两个子视图的共同父视图。
算法思路：先遍历找出两个子视图的所有父视图，存于两个数组；将两个数组进行反序，然后从下标 0 的位置开始对比两个数组，将相同的视图存在另一个新数组中，直到两个数组第一次出现不同视图，就可以终止循环。
- (void)learnFindCommonSupperView {
NSMutableArray *mutableArray_A = [NSMutableArray new];
NSMutableArray *mutableArray_B = [NSMutableArray new];
NSMutableArray *mutableArray_Common = [NSMutableArray new];
UIView *currentA = self.labelA;
while (currentA.superview != nil) {
[mutableArray_A addObject:currentA.superview];
currentA = currentA.superview;
}
UIView *currentB = self.labelB;
while (currentB.superview != nil) {
[mutableArray_B addObject:currentB.superview];
currentB = currentB.superview;
}
// 步骤的关键在于反序查找,直到第一个不同的视图终止
mutableArray_A = [[[mutableArray_A reverseObjectEnumerator] allObjects] mutableCopy];
mutableArray_B = [[[mutableArray_B reverseObjectEnumerator] allObjects] mutableCopy];
for (int i = 0; i < mutableArray_A.count && i < mutableArray_B.count; i++) {
UIView *a = mutableArray_A[i];
UIView *b = mutableArray_B[i];
if (a == b) {
[mutableArray_Common addObject:a];
// 为了标记已经找到的共同父视图,标记为红色
a.backgroundColor = [UIColor redColor];
a.layer.borderWidth = 1;
a.layer.borderColor = [UIColor whiteColor].CGColor;
} else {
break;
}
}
NSLog(@"一共有 %lu 个父视图", (unsigned long)mutableArray_Common.count);
}
