注意：本文主讲算法相关面试问题，包括字符串反转、链表反转、有序数组合并、Hash算法、查找两个子视图的共同父视图、求无序数组当中的中位数。
一、字符串反转
问题:给定字符串"hello, world", 实现将其反转.输出结果: dlrow,oleh
字符串反转
答:
void char_reverse(char* cha) {
// 指向第一个字符
char* begin = cha;
// 指向最后一个字符
char* end = cha + strlen(cha) - 1;
while (begin < end) {
// 交换前后两个字符,同时移动指针
char temp = *begin;
*(begin++) = *end;
*(end--) = temp;
}
}
//1.字符串反转
char ch[] = "hello,world";
char_reverse(ch);
printf("reverse result is %s \n", ch);
//打印 reverse result is dlrow,olleh
二、链表反转
链表头插法思想
链表反转
- ReverseList.h
//ReverseList.h
// 定义一个链表
struct Node {
int data;
struct Node *next;
};
@interface ReverseList : NSObject
// 链表反转
struct Node* reverseList(struct Node *head);
// 构造一个链表
struct Node* constructList(void);
// 打印链表中的数据
void printList(struct Node *head);
@end
- ReverseList.m
//ReverseList.m
@implementation ReverseList
struct Node* reverseList(struct Node *head) {
// 定义遍历指针，初始化为头结点
struct Node *p = head;
// 反转后的链表头部
struct Node *newH = NULL;
// 遍历链表
while (p != NULL) {
// 记录下一个结点
struct Node *temp = p->next;
// 当前结点的next指向新链表头部
p->next = newH;
// 更改新链表头部为当前结点
newH = p;
// 移动p指针
p = temp;
}
// 返回反转后的链表头结点
return newH;
}
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;
}
// 当前结点的next为新结点
else{
cur->next = node;
}
// 设置当前结点为新结点
cur = node;
}
return head;
}
void printList(struct Node *head){
struct Node* temp = head;
while (temp != NULL) {
printf("node is %d \n", temp->data);
temp = temp->next;
}
}
@end
- 执行调用
//单链表反转
struct Node* head = constructList();
printList(head);
printf("-----------\n");
struct Node* newHead = reverseList(head);
printList(newHead);
三、有序数组合并
有序数组合并
// 将有序数组a和b的值合并到一个数组result当中，且仍然保持有序
void mergeList(int a[], int aLen, int b[], int bLen, int result[]) {
int p = 0; // 遍历数组a的指针
int q = 0; // 遍历数组b的指针
int i = 0; // 记录当前存储位置
// 任一数组没有到达边界则进行遍历
while (p < aLen && q < bLen) {
// 如果a数组对应位置的值小于b数组对应位置的值
if (a[p] <= b[q]) {
// 存储a数组的值
result[i] = a[p];
// 移动a数组的遍历指针
p++;
}else{
// 存储b数组的值
result[i] = b[q];
// 移动b数组的遍历指针
q++;
}
// 指向合并结果的下一个存储位置
i++;
}
// 如果a数组有剩余
while (p < aLen) {
// 将a数组剩余部分拼接到合并结果的后面
result[i] = a[p++];
i++;
}
// 如果b数组有剩余
while (q < bLen) {
// 将b数组剩余部分拼接到合并结果的后面
result[i] = b[q++];
i++;
}
}
- 执行调用
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);
//打印归并结果
printf("merge result is ");
for (int i = 0; i < 13; i++) {
printf("%d ", result[i]);
}
//输出 merge result is 1 2 3 4 5 6 6 7 8 9 10 11 12
四、Hash算法
问题:在一个字符串中找到第一个只出现一次的字符
如:输入"abaccdeff" , 则输出b
算法思想:
- 字符(char)是一个长度为8的数据类型,因此总共有可能256中可能.
- 每个字母根据其ASCII码值作为数组的下标对应数组的一个数字.
- 数组中存储的是每个字符出现的次数.
哈希表
例: 给定值是字母a, 对应ASCII值是97, 数组索引下标为97.
哈希函数: 建立字母或字符到它所存储位置index的一个映射关系. f(key)
存储和查找都通过该函数, 有效提高查找效率.
f(char) => index
//查找第一个只出现一次的字符
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') {
// 在字母对应存储位置 进行出现次数+1操作
array[*(p++)]++;
}
// 将P指针重新指向字符串头部
p = cha;
// 遍历每个字母的出现次数
while (*p != '\0') {
// 遇到第一个出现次数为1的字符，打印结果
if (array[*p] == 1) {
result = *p;
break;
}
// 反之继续向后遍历
p++;
}
return result;
}
- 执行结果
char cha[] = "abaccdeff";
char fc = findFirstChar(cha);
printf("this char is %c \n", fc);
//输出this char is b
五、查找两个子视图的共同父视图
- 倒序比较找到第一个不一样的
- (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;
}
六、求无序数组当中的中位数
方案:
- 1>排序算法+中位数
- 2>利用快排思想(分治思想)
排序算法+中位数
- 排序算法: 冒泡排序, 快速排序, 堆排序...
- 中位数:
当n为奇数时, (n+1)/2 ;
当n为偶数时, (n/2 + (n/2 + 1)) / 2 ;
快排思想
快排思想
- 快排思想: 选取关键字, 高低交替扫描
任意挑一个元素, 以该元素为支点, 划分集合为两部分.
如果左侧集合长度恰为 (n- 1)/2, 那么支点恰为中位数.
如果左侧长度恰 < (n- 1)/2, 那么中位点在右侧; 反之, 中位数在左侧.
进入相应的一侧继续寻找中位点
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,6,7,11,13,9};
// 3 6 7 8 9 10 11 12 13
// ^
int median = findMedian(list, 9);
printf("the median is %d \n", median);
// the median is 9
