算法相关
- 字符串反转
- 链表反转
- 有序数组合并
- Hash算法
- 查找两个子视图的共同父视图
- 求无序数组当中的中位数
github地址
1.字符串反转
给定字符串 “Hello,world”实现将其反转。输出“dlrow,olleh”。
思路：字符串数组中从开始收尾交换，一直到中间元素，实现数组反转；
1
2
3
4
5
6
7
8
9
10
|
char ch[] = "hello,world";
char *begin = ch;
char *end = ch + strlen(ch) - 1;
while (begin < end) {
char temp = *begin;
*(begin++) = *end;
*(end--) = temp;
}
printf("reverseString:%s\n", ch);
|
2.链表反转
反转前1->2->3->4->NULL
反转后4->3->2->1->NULL
思路：因为链表是从头到尾遍历，想要反转，最方便的就是构造链表从尾部到头部的顺序构造。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
/** 定义一个链表 */
struct Node {
NSInteger data;
struct Node * next;
};
- (void)listReverse
{
struct Node * p = [self constructList];
[self printList:p];
//反转后的链表头部
struct Node * newH = NULL;
//头插法
while (p != NULL) {
//记录下一个结点
struct Node * temp = p->next;
//当前结点的next指向新链表的头部
p->next = newH;
//更改新链表头部为当前结点
newH = p;
//移动p到下一个结点
p = temp;
}
[self printList:newH];
}
/**
打印链表
@param head 给定链表
*/
- (void)printList:(struct Node *)head
{
struct Node * temp = head;
printf("list is : ");
while (temp != NULL) {
printf("%zd ",temp->data);
temp = temp->next;
}
printf("\n");
}
/** 构造链表 */
- (struct Node *)constructList
{
//头结点
struct Node *head = NULL;
//尾结点
struct Node *cur = NULL;
for (NSInteger i = 0; i < 10; 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;
}
|
3.有序数组合并
将有序数组 和 合并为
思路：两个数组一起遍历，选择合适的（比较小的）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
- (void)orderListMerge
{
int aLen = 5,bLen = 9;
int a[] = {1,4,6,7,9};
int b[] = {2,3,5,6,8,9,10,11,12};
[self printList:a length:aLen];
[self printList:b length:bLen];
int result[14];
int p = 0,q = 0,i = 0;//p和q分别为a和b的下标，i为合并结果数组的下标
//任一数组没有达到s边界则进行遍历
while (p < aLen && q < bLen) {
//如果a数组对应位置的值小于b数组对应位置的值,则存储a数组的值，并移动a数组的下标与合并结果数组的下标
if (a[p] < b[q]) result[i++] = a[p++];
//否则存储b数组的值，并移动b数组的下标与合并结果数组的下标
else result[i++] = b[q++];
}
//如果a数组有剩余，将a数组剩余部分拼接到合并结果数组的后面
while (++p < aLen) {
result[i++] = a[p];
}
//如果b数组有剩余，将b数组剩余部分拼接到合并结果数组的后面
while (q < bLen) {
result[i++] = b[q++];
}
[self printList:result length:aLen + bLen];
}
- (void)printList:(int [])list length:(int)length
{
for (int i = 0; i < length; i++) {
printf("%d ",list[i]);
}
printf("\n");
}
|
4.HASH算法
思路：字符（char）是一个长度为8的数据类型，因此总共有256中可能。每个字母根据其ASC||码值作为组数下标对应数组中的一个数字。数组中存储每次字符出现的次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
- (void)hashTest
{
NSString * testString = @"hhaabccdeef";
char testCh[100];
memcpy(testCh, [testString cStringUsingEncoding:NSUTF8StringEncoding], [testString length]);
int list[256];
for (int i = 0; i < 256; i++) {
list[i] = 0;
}
char *p = testCh;
char result = '\0';
while (*p != result) {
list[*(p++)]++;
}
p = testCh;
while (*p != result) {
if (list[*p] == 1) {
result = *p;
break;
}
p++;
}
printf("result:%c",result);
}
|
5.查找两个子视图的共同父视图
思路:分别记录两个子视图的所有父视图并保存到数组中，然后倒序寻找,直至找到第一个不一样的父视图。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
- (void)findCommonSuperViews:(UIView *)view1 view2:(UIView *)view2
{
NSArray * superViews1 = [self findSuperViews:view1];
NSArray * superViews2 = [self findSuperViews:view2];
NSMutableArray * resultArray = [NSMutableArray array];
int i = 0;
while (i < MIN(superViews1.count, superViews2.count)) {
UIView *super1 = superViews1[superViews1.count - i - 1];
UIView *super2 = superViews2[superViews2.count - i - 1];
if (super1 == super2) {
[resultArray addObject:super1];
i++;
}else{
break;
}
}
NSLog(@"resultArray:%@",resultArray);
}
- (NSArray <UIView *>*)findSuperViews:(UIView *)view
{
UIView * temp = view.superview;
NSMutableArray * result = [NSMutableArray array];
while (temp) {
[result addObject:temp];
temp = temp.superview;
}
return result;
}
|
6.求无序数组中的中位数
中位数：当数组个数n为奇数时，为(n + 1)/2，即是最中间那个数字；当n为偶数时，为(n/2 + (n/2 + 1))/2,即是中间两个数字的平均数。
思路:
1.排序算法+中位数
首先用冒泡排序、快速排序、堆排序、希尔排序等排序算法将所给数组排序，然后取出其中位数即可。
2.利用快排思想