脚塌实地之常见算法
2020-03-19 本文已影响0人
lmfei
长期更新，记录自己看到的算法题
常见排序法
冒泡排序（O(n2)）
- (NSArray<NSNumber *> *)bubbleSort: (NSArray<NSNumber *> *)nums {
if (nums == nil || nums.count == 0) {
return nums;
}
NSMutableArray *results = [NSMutableArray arrayWithArray:nums];
for (int i=0; i<nums.count; i++) {
for (int j = 0; j<nums.count-1-i; j++) {
if ([results[j] integerValue] > [results[j+1] integerValue]) {
[results exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
return [results copy];
}
调用
//冒泡排序
NSArray *ary = @[@12, @23, @4, @18, @28, @19, @89, @45];
NSLog(@"%@", [[LSortSummary alloc] bubbleSort:ary]);
算法解析：从小到大排序，通过相邻两个数进行比较，然后将较大的数放到后面，需要比较nums.count次
选择排序（O(n2)）
- (NSArray <NSNumber *>*)selectionSort:(NSArray<NSNumber *> *)nums {
if (nums == nil || nums.count == 0) {
return nums;
}
NSMutableArray *results = [NSMutableArray arrayWithArray:nums];
for (int i = 0; i < nums.count; i++) {
NSInteger minIndex = i;
for (int j=i+1; j < nums.count; j++) {
if ([results[minIndex] integerValue] > [results[j] integerValue]) {
minIndex = j;
}
}
[results exchangeObjectAtIndex:minIndex withObjectAtIndex:i];
}
return results;
}
调用
NSArray *ary = @[@12, @23, @4, @18, @28, @19, @89, @45];
//选择排序（O(n2)）
NSLog(@"%@", [[LSortSummary alloc] selectionSort:ary]);
算法解析-冒泡排序就是每次循环选择最值，然后放在最前面，下次循环就从排序好的下一个数进行，哦了
插入排序
- (NSArray <NSNumber *>*)insertSort:(NSArray <NSNumber *> *) nums {
if (nums == nil || nums.count == 0) {
return nums;
}
NSMutableArray *ary = [NSMutableArray arrayWithArray:nums];
for (int i=0; i < nums.count - 1; i++) {
NSNumber *current = ary[i+1];
//方案1
for (int j = i; j >= 0; j--) {
if ([current integerValue] < [ary[j] integerValue]) {
ary[j+1] = ary[j];
if (j==0) {
ary[0] = current;
}
}else {
ary[j+1] = current;
break;
}
}
//方案2
// int preIndex = i;
// while (preIndex >= 0 && [current integerValue] < [ary[preIndex] integerValue] ) {
// ary[preIndex+1] = ary[preIndex];
// preIndex--;
// }
// ary[preIndex+1] = current;
}
return [ary copy];
}
算法解析-用第n个元素（n从1开始），和前面每一个元素比，比它大的往后移一位，找到比它小的则将此值放在它后面，直到最后一个元素
希尔排序
- (NSArray <NSNumber *>*)shellSort:(NSArray <NSNumber *> *) nums {
NSInteger len = nums.count;
NSInteger gap = len/2;
NSNumber *tmp;
NSMutableArray *ary = [NSMutableArray arrayWithArray:nums];
//@[@12, @23, @4, @18, @28, @19, @89, @45];
while (gap > 0) {
for (NSInteger i = gap; i < len; i++) {
tmp = ary[i];
NSInteger preIndex = i - gap;
while (preIndex >= 0 && [ary[preIndex] integerValue] > [tmp integerValue] ) {
ary[preIndex + gap] = ary[preIndex];
preIndex -= gap;
}
ary[preIndex + gap] = tmp;
}
gap /= 2;
}
return [ary copy];
}
算法解析-以n/2为间隔将数组分为n/2组，然后每组进行插入排序，在将数组以n/2/2为间隔分组，对每组继续进行插入排序，直到n/2/2/../2小于0即排序完成
归并排序（nlog(n)）
- (NSArray <NSNumber *> *)mergeSort:(NSArray <NSNumber *> *)nums {
if (nums == nil || nums.count < 2) return nums;
NSInteger mid = nums.count/2;
NSArray *ary1 = [nums subarrayWithRange:NSMakeRange(0, mid-1)];
NSArray *ary2 = [nums subarrayWithRange:NSMakeRange(mid, nums.count-mid)];
return [self mergeAry1:ary1 Ary2:ary2];
}
- (NSArray <NSNumber *>*)mergeAry1:(NSArray <NSNumber *>*)nums1 Ary2:(NSArray <NSNumber *>*)nums2 {
NSMutableArray *resultAry = [NSMutableArray arrayWithCapacity:nums1.count+nums2.count];
for (int i=0,j=0,index=0; index < resultAry.count; index++) {
if (i > nums1.count) {
resultAry[index] = nums2[j++];
} else if (j > nums2.count) {
resultAry[index] = nums1 [i++];
} else if (nums1[i] > nums2[j]) {
resultAry[index] = nums1[i++];
} else {
resultAry[index] = nums2[j++];
}
}
return resultAry;
}
算法解析-将数组分成n/2份，在对子数组分成n/2份，一直分到n/2小于2为止，然后对子数组进行排序，在将排好序的子数组进行合并，以达到排序效果
快速排序（nlogn）
void quickSort(int ary[], int low, int high) {
if (low < high) {
int index = getIndex(ary, low, high);
quickSort(ary, low, index-1);
quickSort(ary, index+1, high);
}
}
int getIndex (int ary[], int low, int high) {
int tmp = ary[low];
while (low < high) {
//从后往前比
while (low < high && tmp <= ary[high]) {
high--;
}
//从前往后比
ary[low] = ary[high];
while (low < high && tmp >= ary[low]) {
low++;
}
ary[high] = ary[low];
}
//找到该数的位置
ary[low] = tmp;
return low;
}
调用
int nums[] = {12, 23, 4, 18, 28, 19, 89, 45};
int len = sizeof(nums)/sizeof(nums[0]);
//快速排序
quickSort(nums, 0, len -1);
NSLog(@"快速排序");
for (int i=0; i < len; i++) {
printf("%d\n",nums[i]);
}
算法解析-以第一个数为基数，然后定义一个low执行第一个数，定义一个high指向最后一个数，然后从后到前比对，如果比基数大，则high减1，继续往前比，如果比基数小，则将high这个位置的数赋值给low位置，然后从low位置往后比，如果比tmp大，则low加一继续比；如果比tmp小，则将low这个位置的数赋值给high位置，直到low等于high，则找到该基数在数组中的位置，并将基数放到该位置，数组被这个基数分成两部分，继续上面的步骤，直到数组变成有序的即完成
(LeetCode-swift)求二叉树的直径，给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
/**
* Definition for a binary tree node.
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* }
* }
*/
class Solution {
var maxDepth: Int = 0;
func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
maxDepth = 1;
getDepth(root);
return maxDepth - 1;
}
func getDepth(_ root: TreeNode?) -> Int {
if root == nil { return 0; }
var L: Int = getDepth(root!.left);
var R: Int = getDepth(root!.right);
maxDepth = max(maxDepth, L+R+1);
return max(L, R)+1;
}
}
算法解析：求二叉树的直径，就是求任意节点的左儿子向下遍历经过最多的节点数加上右儿子向下遍历经过最多的节点数之和再加1，然后在求他们的边用上边的值减一，然后取其中最大值，即为直径
字符串反转
void reverseString(char *data) {
char *begin = data;
char *end = data + strlen(data) - 1;
while (begin < end) {
char tmpChar = *begin;
*(begin++) = *end;
*(end--) = tmpChar;
}
}
调用
//字符串反转
char data[] = "abcdef";
NSLog(@"-----------反转前-----------");
NSLog(@"%s",data);
reverseString(data);
NSLog(@"-----------反转后-----------");
NSLog(@"%s", data);```
打印结果
2020-03-08 20:39:11.841307+0800 20200308-数据结构&算法[42672:1811064] -----------反转前-----------
2020-03-08 20:39:11.841878+0800 20200308-数据结构&算法[42672:1811064] abcdef
2020-03-08 20:39:11.842346+0800 20200308-数据结构&算法[42672:1811064] -----------反转后-----------
2020-03-08 20:39:11.842499+0800 20200308-数据结构&算法[42672:1811064] fedcba
算法解析：声明两个指针，分别指向首尾位置，然后交换两个指针指向地址的值，然后首指针向后偏移，尾指针向前偏移，直到两个指针位置相交，即字符串反转完毕。
链表反转
struct LNode *constructList(void){
//头结点
struct LNode *head = NULL;
//记录当前尾结点
struct LNode *curEnd = NULL;
for (int i=0; i < 4; i++) {
struct LNode *tmpNode = malloc(sizeof(struct LNode));
tmpNode->value = i;
//头结点为空，该结点即为头结点
if (head == NULL) {
head = tmpNode;
}
else {
curEnd->next = tmpNode;
}
curEnd = tmpNode;
}
return head;
}
struct LNode *reverseList(struct LNode *node) {
struct LNode *oldCurNode = node;
struct LNode *newCurNode = NULL;
while (oldCurNode != NULL) {
struct LNode *tmpNode = oldCurNode->next;
oldCurNode->next = newCurNode;
newCurNode = oldCurNode;
oldCurNode = tmpNode;
}
return newCurNode;
}
void listLog(struct LNode *head){
struct LNode *tmp = head;
while (tmp != NULL) {
NSLog(@"结点value：%ld", tmp->value);
tmp = tmp->next;
}
}
调用
//链表反转
struct LNode *list = constructList();
NSLog(@"-----------反转前-----------");
listLog(list);
list = reverseList(list);
NSLog(@"-----------反转后-----------");
listLog(list);
打印结果
2020-03-08 20:34:32.386620+0800 20200308-数据结构&算法[42527:1805622] -----------反转前-----------
2020-03-08 20:34:32.388044+0800 20200308-数据结构&算法[42527:1805622] 结点value：0
2020-03-08 20:34:32.388135+0800 20200308-数据结构&算法[42527:1805622] 结点value：1
2020-03-08 20:34:32.388555+0800 20200308-数据结构&算法[42527:1805622] 结点value：2
2020-03-08 20:34:32.389019+0800 20200308-数据结构&算法[42527:1805622] 结点value：3
2020-03-08 20:34:32.389095+0800 20200308-数据结构&算法[42527:1805622] -----------反转后-----------
2020-03-08 20:34:32.389400+0800 20200308-数据结构&算法[42527:1805622] 结点value：3
2020-03-08 20:34:32.389561+0800 20200308-数据结构&算法[42527:1805622] 结点value：2
2020-03-08 20:34:32.389657+0800 20200308-数据结构&算法[42527:1805622] 结点value：1
2020-03-08 20:34:32.389734+0800 20200308-数据结构&算法[42527:1805622] 结点value：0
算法解析-使用一个指针指向原始的链表头oldCurNode，再使用一个指针指向新的链表newCurNode，初始化为NULL，然后以第一个指针不为NULL为条件循环链表，每次使用一个临时指针tmpNode指向结点的下一个结点，然后将oldCurNode的next指向newCurNode，再将newCurNode指针指向oldCurNode，再将oldCurNode指向tmpNode，依此循环，循环结束链表反转成功
合并两个有序数组
void mergeOrderlyArray(int a[], int aLen, int b[], int bLen, int result[]) {
int aIndex = 0;
int bIndex = 0;
int i=0;
while (aIndex < aLen && bIndex < bLen){
if (a[aIndex] < b[bIndex]){
result[i++] = a[aIndex++];
}
else {
result[i++] = b[bIndex++];
}
}
while (aIndex < aLen) {
result[i++] = a[aIndex++];
}
while (bIndex < bLen) {
result[i++] = b[bIndex++];
}
}
调用
//有序数组合并
int a[] = {1, 3, 5, 7, 9, 11, 13, 15};
int b[] = {2, 4, 6, 8, 10, 12};
int aLen = sizeof(a)/sizeof(a[0]);
int bLen = sizeof(b)/sizeof(b[0]);
int result[aLen + bLen];
mergeOrderlyArray(a, aLen, b, bLen, result);
NSLog(@"输出结果为：");
for (int i = 0; i <aLen+bLen ; i++) {
NSLog(@"%d", result[i]);
}
打印结果
2020-03-08 21:10:01.265918+0800 20200308-数据结构&算法[43573:1842805] 输出结果为：
2020-03-08 21:10:01.266357+0800 20200308-数据结构&算法[43573:1842805] 1
2020-03-08 21:10:01.266472+0800 20200308-数据结构&算法[43573:1842805] 2
2020-03-08 21:10:01.266538+0800 20200308-数据结构&算法[43573:1842805] 3
2020-03-08 21:10:01.266598+0800 20200308-数据结构&算法[43573:1842805] 4
2020-03-08 21:10:01.266659+0800 20200308-数据结构&算法[43573:1842805] 5
2020-03-08 21:10:01.266716+0800 20200308-数据结构&算法[43573:1842805] 6
2020-03-08 21:10:01.266775+0800 20200308-数据结构&算法[43573:1842805] 7
2020-03-08 21:10:01.266871+0800 20200308-数据结构&算法[43573:1842805] 8
2020-03-08 21:10:01.267045+0800 20200308-数据结构&算法[43573:1842805] 9
2020-03-08 21:10:01.267207+0800 20200308-数据结构&算法[43573:1842805] 10
2020-03-08 21:10:01.267371+0800 20200308-数据结构&算法[43573:1842805] 11
2020-03-08 21:10:01.267545+0800 20200308-数据结构&算法[43573:1842805] 12
2020-03-08 21:10:01.267728+0800 20200308-数据结构&算法[43573:1842805] 13
2020-03-08 21:10:01.267909+0800 20200308-数据结构&算法[43573:1842805] 15
算法解析-声明aIndex、bIndex、i分别指向a、b、result当前索引，同时遍历两个数组，当两个数组都尾遍历完时，将较小的值写入result当前i的位置，然后将i加1，再将较小值数组的index加1，直至一个数组遍历完，再遍历另一个未遍历完的数组，将值一次写入result中
获取字符串中第一个只出现一次的字符
char getFirstAndOneChar(char *data) {
char *p = data;
int dAry[256];
char result = '\0';
for (int i = 0; i < 256; i++) {
dAry[i] = 0;
}
while (*p!='\0') {
dAry[*(p++)]++;
}
p = data;
while (*p!='\0') {
if (dAry[*p] == 1) {
result = *p;
break;
}
p++;
}
return result;
}
调用
//查找只出现一次的第一个字符
char a[] = "abcdefadef";
NSLog(@"%c", getFirstAndOneChar(a));
打印
2020-03-09 22:17:11.311768+0800 20200308-数据结构&算法[72399:2684575] b
算法解析-利用哈希函数的思想，以字符的ASCll码为index，出现的次数为value，得到每个字符出现的个数的数组，在通过遍历这个数组找到一个值为1的字符
寻找两个View最近的父View
- (UIView *)findFirstSurperView:(UIView *)viewA With:(UIView *)viewB {
NSArray *aryA = [self getAllSurperView:viewA];
NSArray *aryB = [self getAllSurperView:viewB];
int i = 0;
NSMutableArray *comSurperAry = [NSMutableArray array];
while (i < MIN(aryA.count, aryB.count)) {
if (aryA[aryA.count - i - 1] == aryB[aryB.count - i -1]) {
[comSurperAry addObject:aryA[aryA.count-i-1]];
i++;
}else {
break;
}
}
return [comSurperAry lastObject];
}
- (NSArray *)getAllSurperView:(UIView *)viewP {
NSMutableArray *tmpAry = [NSMutableArray array];
UIView *tmpView = viewP.superview;
while (tmpView) {
[tmpAry addObject:tmpView];
tmpView = tmpView.superview;
}
return [tmpAry copy];
}
调用
//查找寻找两个View最近的父View
UIView *viewA = [[UIView alloc]initWithFrame:CGRectMake(0, 0, 300, 500)];
viewA.backgroundColor = [UIColor redColor];
[self.view addSubview:viewA];
UIView *viewB = [[UIView alloc]initWithFrame:CGRectMake(0, 0, 100, 500)];
viewB.backgroundColor = [UIColor grayColor];
[viewA addSubview:viewB];
UIView *viewC = [[UIView alloc]initWithFrame:CGRectMake(0, 0, 50, 500)];
viewC.backgroundColor = [UIColor blueColor];
[viewB addSubview:viewC];
UIView *viewD = [[UIView alloc]initWithFrame:CGRectMake(200, 0, 100, 500)];
viewD.backgroundColor = [UIColor orangeColor];
[viewA addSubview:viewD];
UIView *viewE = [[UIView alloc]initWithFrame:CGRectMake(0, 0, 50, 200)];
viewE.backgroundColor = [UIColor grayColor];
[viewD addSubview:viewE];
UIView *viewF = [[UIView alloc]initWithFrame:CGRectMake(0, 0, 30, 100)];
viewF.backgroundColor = [UIColor blackColor];
[viewE addSubview:viewF];
UIView *result = [[LFindFirstCommonSurperView alloc] findFirstSurperView:viewC With:viewF];
NSLog(@"result:%@", result);
打印
po viewA
<UIView: 0x7fd8fbf12400; frame = (0 0; 300 500); layer = <CALayer: 0x6000000b9600>>
2020-03-09 22:54:45.526154+0800 20200308-数据结构&算法[73247:2718821] result:<UIView: 0x7fd8fbf12400; frame = (0 0; 300 500); layer = <CALayer: 0x6000000b9600>>
算法解析-找两个视图的父视图，最简单的方法就是从底层view一层一层往上找，没有相同祖先的view是不会在一个view上的
生活如此美好，今天就点到为止。。。
