iOS算法题

[ 题 : ] 栈-思路

//入栈 stack
- (void)stackPush:(NSObject *)obj {
    [_array addObject:obj];
}

//出栈 - 先进后出first in, last out
- (NSObject *)stackPop {
    if (_array.count > 0) {
        return [_array lastObject]; //最后加入的数据先取出
    }
    return nil;
}

[ 题 : ] 队列queue-思路

//加入队列
- (void)queuePush:(NSObject *)obj {
    [_array addObject:obj];
}

//出队列 - 先进先出first in, first out
- (NSObject *)queuePop {
    if (_array.count > 0) {
        return [_array firstObject];//最先加入的先取出
    }
    return nil;
}

[ 题 : ] 冒泡排序

【冒泡排序】：相邻元素两两比较，比较完一趟，最(大或小)值出现在末尾

(1) 升序冒泡排序思路 : 从左往右依次对比, 大的往后换位置, 循环5-1 = 4次
排序前 2,1,4,5,3 => 排序后 1,2,3,4,5

第1轮 : 2,1,4,5,3
(2,1)->2比1大, 要交换 : 1,2,4,5,3
(2,4)->2比4小, 不交换 : 1,2, 4,5,3
(4,5)->4比5小, 不交换 : 1,2, 4,5,3
(5,3)->5比3大, 要交换 : 1,2, 4,3,5
第1轮结束时:最后 1位最大值5已完成

第2轮 : 1,2,4,3,5
(1,2)->1比2小,不交换 : 1,2,4,3,5
(2,4)->2比4小,不交换 : 1,2, 4,3,5
(4,3)->4比3大,要交换 : 1,2, 3,4,5
第2轮结束时:倒数第2位值4已完成

(另外: 此处进行两轮其实已经结束了,所以不用在轮询了, 判断排好序就结束 )
依次类推.

//冒泡排序 1
- (void)bublleSort:(NSMutableArray *)arr{
    for(int i = 0; i < arr.count - 1; i++) { //趟数
        for(int j = 0; j < arr.count - i - 1; j++) { //比较次数
            //如果左边 > 右边 就交换位置
            if(arr[j] > arr[j+1]){
                NSNumber *temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
            //else 直接下一次比较
        }
    }
}

//冒泡排序 2 -改良
- (void)bublleSortNew:(NSMutableArray *)arr{
    //加一个标识
    int endTag = 0;
    for(int i = 0; i < arr.count - 1; i++) { //趟数
        
        for(int j = 0; j < arr.count - i - 1; j++) { //比较次数
            //如果左边 > 右边 就交换位置
            if(arr[j] > arr[j+1]){
                NSNumber *temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                
                //发生了交换,更新tag值
                endTag = i;
            }
        }
        
        //如果没有发生交换,说明已经排好序了, 直接退出循环
        if (endTag < i) {
            break;
        }
    }
}

[ 题 : ] 选择排序

【选择排序】：最值出现在起始端(每次轮询右移一位)

(1) 升序排序思路 : 从左往右依次两两对比, 小的值 跟第1位换位置, 循环5-1 = 4次
排序前 2,1,4,5,3 => 排序后 1,2,3,4,5

(2)降序排序思路 : 从左往右依次两两对比, 大的值 跟第1位换位置, 循环5-1 = 4次
排序前 2,1,4,5,3 => 排序后 5,4,3,2,1

升序排序演练 :
第1轮 : 2,1,4,5,3
(2),(1)->2比1大, 要交换 : 1,2,4,5,3
(1),(4)->1比4小, 不交换 : 1,2, 4,5,3
(1),(5)->1比5小, 不交换 : 1,2, 4,5,3
(1),(3)->1比3小, 不交换 : 1,2, 4,5,3
第1轮结束时:最后 1位最小值1已完成

第2轮 : 1,2,4,5,3
第2轮结束时:没有交换(第2位是第二大)

第3轮 : 1,2,3,4,5
第3轮结束时: 排序完成(3和4交换位置)

(另外: 此处进行两轮其实已经结束了,所以不用在轮询了, 判断排好序就结束 )
依次类推.

//选择排序-升序 
- (void)selectSortAsc:(NSMutableArray *)arr{
    for(int i = 0; i < arr.count - 2; i++) { //趟数
        NSNumber *temp = arr[i];//参考的对象
        for(int j = i + 1; j < arr.count - 1; j++) { //比较次数
            //比参考值小 就交换位置
            if(arr[j] < temp){
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

降序同理

[ 题 : ] 二分法查找（折半查找）

从已排序的数中找到对应的值(即已知最大值,最小值, 找其中的值)

(假如A有68块钱)
A: 猜猜我有几块钱 ? 不超过100块 .
B: 30块?
A:不止(猜小了)
B:90块?
A:多了(猜大了)
...
....(猜了20次, B绝望了)...

二分法思路演练: (B每次都猜剩余区间的中间值)
(假如A有68块钱)
A: 猜猜我有几块钱 ? 不超过100块 .
B: 50 块? (100的一半 )
A:不止(猜小了)
B:75块? (51 -100的中间 , 50被排除了,现在最小值是51)
A:多了(猜大了)
B: 62 块? (50 -74的中间 )
A:不止(猜小了)
B:68块? (63 -74的中间 )
A:猜对了

题: arr = @[3,4,5,....200]; 找到 num = 120 的位置index

//二分查找 : 
- (int)midFind:(NSMutableArray *)arr num:(int)num {
    int min = 0;//最小值位置
    int max = (int)arr.count - 1;//最大值位置
    
    while (min <= max) {
        int mid = (min + max)/2;//中间位置
        if ([arr[mid] intValue] < num) {//猜小了
            min = mid + 1;//mid值被排除了,所以最小值是mid + 1
        } else if ([arr[mid] intValue] > num) {//猜大了
            max = mid - 1;//mid值被排除了,所以最大值是mid - 1
        } else {
            return mid;
        }
        
        //如果最小值=最大值也找不到的话,说明没有这个对象
        if (min == max && min != num) {
            return -1;
        }
    }
    return -1;
}

[ 题 : ] 递归

从0数到100

//从0数到100
[self recursionSort:0];

//递归
- (void)recursionSort:(int)num {
    if (num < 100) {
        num += 1;
        [self recursionSort:num];
    }
}

[ 题 : ] 快速排序

第一步: 随机取一个值作为参考值
第二步: 小于参考值的数都放左侧, 大于放右侧
第三步: 递归对左右两侧分别执行上述两步(排序数<2时退出)

演示简单排序: [6,5,7] 快速排序

第一步: 随机取一个值6 作为参考值
第二步: 小于6的数都放左侧, 大于6放右侧

图片.png

演示排序2 : [4,1,8,6,3,2,5,7,9] 快速排序

屏幕快照 2019-11-17 下午8.21.39.png

第一步:选取参考值(4).
第二步:创建三个数组分别存储,[<4] , [=4], [>4]
第三步:分别对[<4] , [>4] 递归调用该方法.
第四步:分别拼接返回.

调用:

NSArray *dataA = [self quickSorting:@[@4,@1,@8,@6,@3,@6,@3,@2,@5,@7,@9]];
    NSLog(@"quickSorting : %@",dataA);

OC算法:

/**
 :快速排序
 1.为了简化, 这里忽略一些判断,空值,count=0 等等
 要求 : 快速排序NSArray *dataA = [quickSorting:@[4,1,8,6,3,2,5,7,9]];
 */
- (NSMutableArray *)quickSorting:(NSArray *)array {
    if (array.count > 1) {
        //取随机数[0,count)
        long random = arc4random() % array.count;
        //基准数
        int baseNum = [array[random] intValue];
        //左侧待存放数组
        NSMutableArray *leftArr = @[].mutableCopy;
        //存放相等的数组
        NSMutableArray *sameArr = @[].mutableCopy;
        //右侧待存放数组
        NSMutableArray *rightArr = @[].mutableCopy;
        for (int i=0; i<array.count; i++) {
            if ([array[i] intValue] < baseNum) {
                //小于基准数
                [leftArr addObject:array[i]];
            } else if ([array[i] intValue] == baseNum) {
                //等于基准数
                [sameArr addObject:array[i]];
            } else if ([array[i] intValue] > baseNum) {
                //大于基准数
                [rightArr addObject:array[i]];
            }
        }
        
        //递归排序左侧数组- 个数>1
        NSMutableArray *sortLeftArr = leftArr.count > 1 ? [self quickSorting:leftArr] : leftArr;
        //递归排序右侧数组
        NSMutableArray *sortRightArr = rightArr.count > 1 ? [self quickSorting:rightArr] : rightArr;
        
        //拼接-左侧, 相等值
        [sortLeftArr addObjectsFromArray:sameArr];
        //拼接-右侧
        [sortLeftArr addObjectsFromArray:sortRightArr];
        
        //最后返回排序结果
        return sortLeftArr;
    }
    return [array mutableCopy];
}

[ 题 : ] 字符串翻转

字符串的逆序输出:
输入字符串为“hello world”,输出结果应当为“world hello”。

例如:

//翻转"123456789"
[self overturnStr:@"123456789"];

//字符串翻转
- (void)overturnStr:(NSString *)str {
    NSString *turnStr = @"";
    for (NSInteger i=str.length-1; i>=0; i--) {
        turnStr = [turnStr stringByAppendingString:[str substringWithRange:NSMakeRange(i, 1)]];
    }
    NSLog(@"翻转结果 : %@",turnStr);
}

[ 题 : ] 单链表结构

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

图片.png

[ 题 : ] 单链表翻转

图片.png

1.定义链表结点结构:
typedef struct Node
{
 int data;
 struct Node *next; //next指向下一个结点
} Node,*pnode;

2.递归实现逻辑
void reverse(Node node,Node pre) {
    if(node == null) return;

    Node next = node.next;
    node.next = pre;
    reverse(next, node();//递归
}

实现 :
void main(string[] args) {
    //生成链表
    Node p1 = new Node(1);
    Node p2 = new Node(2);
    Node p3 = new Node(3);

    p1.next = p2;
    p2.next = p3;

    //翻转实现
    reverse(p1, null);
}

[ 题 : ] 二叉树

二叉树 图片.png

(1)空二叉树——如图(a)；
(2)只有一个根结点的二叉树——如图(b)；
(3)只有左子树——如图(c)；
(4)只有右子树——如图(d)；
(5)完全二叉树——如图(e)。

其他术语 :
树的结点（node）：包含一个数据元素及若干指向子树的分支；
孩子结点（child node）：结点的子树的根称为该结点的孩子；
双亲结点：B 结点是A 结点的孩子，则A结点是B 结点的双亲；
兄弟结点：同一双亲的孩子结点； 堂兄结点：同一层上结点；
祖先结点: 从根到该结点的所经分支上的所有结点
子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙
结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；
树的深度：树中最大的结点层
结点的度：结点子树的个数
树的度： 树中最大的结点度。
叶子结点：也叫终端结点，是度为 0 的结点；
分枝结点：度不为0的结点；
有序树：子树有序的树，如：家族树；
无序树：不考虑子树的顺序；

[ 题 : ] 二叉树的深度(层数)

基本思路是递归，从根节点出发，求其左右子树的深度，取左右子树的深度+1的较大者为当前树的深度（求所有子树深度的时候使用递归）。如果到达叶子结点，那么返回0。

Python:

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if pRoot is None:
            return 0
        llength = self.TreeDepth(pRoot.left)
        rlength = self.TreeDepth(pRoot.right)
        return max(llength + 1, rlength + 1)

[ 题 : ] 二叉树的三种遍历方式(前,中,后)

图片.png

二叉树的三种遍历方式代码都是一样的,只是在获取该值的时机不一样:
每个结点都是三进三出

1.前序遍历 : 第一次被访问时(从其它结点第一次进入) , 获取该值88
2.中序遍历 : 第二次被访问时(从其它结点第二次进入) , 获取该值88
3.后序遍历 : 第三次被访问时(从其它结点第三次进入) , 获取该值88

存储结构

顺序存储方式 : 连续的存储地址, 下面以数组(分配连续存储空间)存放

typenode=record
data:datatype
l,r:integer;
end;
vartr:array[1..n]ofnode;

链表存储方式 : 结点之间存储地址不是连续的, 通过指针寻找

typebtree=^node；
node=record
data:datatye;
lchild,rchild:btree;
end;

L、D、R分别表示遍历左子树、访问根结点和遍历右子树

[ 题 : ] 遍历二叉树

void XXBL(tree *root){
    //左子树递归遍历
    if(root->lchild!=NULL) {
        XXBL(root->lchild);
    }
    //右子树递归遍历
    if(root->rchild!=NULL) {
        XXBL(root->rchild);
    }
}

[ 题 : ] 三种遍历

代码: 在上面遍历的基础上, 三种不同时机获取该值,分别为前,中,后

void XXBL(tree *root){
     
     方式1. 如果在此处打印就是 先序遍历
     print(root.data);

    //左子树递归遍历
    if(root->lchild!=NULL) {
        XXBL(root->lchild);
    }
    
    方式2. 如果在此处打印就是 中序遍历
    print(root.data);

    //右子树递归遍历
    if(root->rchild!=NULL) {
        XXBL(root->rchild);
    }

   方式3. 如果在此处打印就是 后序遍历
   print(root.data);
}

根据二叉树某两种遍历结果,反推二叉树

1.前序+中序 -> 可求 二叉树
2.后序+中序 -> 可求 二叉树
(前序+后序 -> 不可求 二叉树)

1.前序+中序 -> 求 二叉树结构:

1.前序遍历 = 根结点 + 左子树(前序遍历) + 右子树(前序遍历)
2.中序遍历 = 左子树(中序遍历) + 根结点 + 右子树(中序遍历)

解题思路:
第一步: 得到根结点:
前序遍历结果的第一个结点位置(0)就是根结点root,
然后在中序结果里根据根结点root找到中序结果里根结点的位置(2)
第二步: 在中序结果里, 以根结点为界限,拆分左右两边得到左子树中序lNode, 右子树中序rNode,
再以该两子树结果,到先序遍历结果中拆分找出左右先序结果
第三步: 递归上述两步

1.前序+中序 -> 可求 二叉树

public class Solution {

    public  static TreeNode reConstructBinaryTree(int [] prev,int [] in) {
    //不管什么遍历方式，结果长度肯定是一样的，都是总结点数
        if(prev.length!= in.length || prev.length<1){
            return null;
        }
    //只有一个节点，那就是根节点
        if(prev.length == 1){
            return new TreeNode(prev[0]);
        }
    //在中序遍历结果中找根节点
        int index = -1;
        for(int i=0;i<in.length;i++){
            if(in[i]==prev[0]){
                index=i;
                break;
            }
        }
    //没找到，说明数据有问题
        if(index==-1){
            return null;
        }
    //找到根节点了
        TreeNode root = new TreeNode(prev[0]);
    //得到左子树的前序遍历结果
        int[] lChildPrev = new int[index];
        System.arraycopy(prev,1,lChildPrev,0,index);
    //得到左子树的中序遍历结果
        int[] lChildin = new int[index];
        System.arraycopy(in,0,lChildin,0,index);
    //通过递归，得到左子树结构
        root.left=reConstructBinaryTree(lChildPrev,lChildin);
        
    //得到右子树的前序遍历结果
        int[] rChildPrev = new int[in.length-1-index];
        System.arraycopy(prev,index+1,rChildPrev,0,in.length-1-index);
    //得到右子树的中序遍历结果
        int[] rChildin = new int[in.length-1-index];
        System.arraycopy(in,index+1,rChildin,0,in.length-1-index);
    //通过递归，得到右子树结构
        root.right=reConstructBinaryTree(rChildPrev,rChildin);
    //得到完整的二叉树结构
        return root;
    }

    //测试
    public static void main(String[] args){
    int[] prev = {1,2,4,7,3,5,6,8};
    int[] in = {4,7,2,1,5,3,8,6};
    TreeNode root = reConstructBinaryTree(prev,in);
    prevPrintTreeNode(root);
    System.out.println();
    inPrintTreeNode(root);
    }
//测试结果
//1 2 4 7 3 5 6 8 
//4 7 2 1 5 3 8 6

}

2.后序+中序 -> 求 二叉树结构:

1.中序遍历 = 左子树(中序遍历) + 根结点 + 右子树(中序遍历)
2.后序遍历 = 左子树(前序遍历) + 右子树(前序遍历) + 根结点

解题思路:
跟前面思路类似, 只不过 根结点在后序遍历的最后一个位置 , 其他逻辑原理同(前+中)一样

[ 题 : ] 查找第一个只出现一次的字符

给定一个字符串，输出本字符串中只出现一次并且最靠前的那个字符的位置？

如“abaccddeeef”,字符是b,输出应该是2。

查询: "Badadd"

存储结构:
{
"B": {"count":"1","index":"0"},
"a": {"count":"2","index":"3"},
"d": {"count":"3","index":"5"},
}
返回位置 0 .

oc函数:

调用:
NSInteger index = [self searchStr:@"Badadd"];

实现:
//返回第一次出现一次的字符位置
- (NSInteger)searchStr:(NSString *)str {
    NSMutableDictionary *dic = @{}.mutableCopy;
    //赋值
    for (NSInteger i=0; i<str.length; i++) {
        NSString *subStr = [str substringWithRange:NSMakeRange(i, 1)];
        
        NSMutableDictionary *subDic = dic[subStr] ? dic[subStr] : @{}.mutableCopy;
        NSInteger count = [subDic[@"count"] integerValue] + 1;
        subDic[@"count"] = @(count);
        subDic[@"index"] = @(i);
    }
    //返回第一次出现一次的字符位置
    NSInteger index = 0;
    NSArray *keyArr = dic.allKeys;
    for (NSInteger i=0; i<keyArr.count; i++) {
        NSMutableDictionary *subDic = dic[keyArr[i]];
        if ([subDic[@"count"] integerValue] == 1) {
            index = [subDic[@"index"] integerValue];
        }
    }
    return index;
}

[ 题 : ] 打印2-100之间的素数

所谓素数是指除了1和它本身以外，不能被任何整数整除的数，例如17就是素数，因为它不能被2 ~ 16的任一整数整除。因此判断一个整数m是否是素数，只需把m被2 ~ m-1之间的每一个整数去除，如果都不能被整除，那么m就是一个素数

另外判断方法还可以简化。m不必呗2 ~ m-1之间的每一个整数去除，只需被2 ~ √m之间的每一个整数去除就可以了。如果m不能被2 ~ √m间任一整数整除，m必定是素数。

例如判别17是是否为素数，只需使17被2 ~ 4之间的每一个整数去除，由于都不能整除，可以判定17是素数。（原因：因为如果m能被2 ~ m-1之间任一整数整除，其二个因子必定有一个小于或等于√m，另一个大于或等于√m。例如16能被2,4,8整除，16=28,2小于4,8大于4，16=44,4=√16，因此只需判定在2 ~ 4之间有无因子即可）

#pragma mark- 9:求2-100间的 素数
- (void)Algorithm8 {
    for (int i = 2; i < 100; i++) {
        int r = isPrime(i);
        if (r == 1) {
            printf("%d ", i);
        }
    }
}

int isPrime(int n) {
    int i;
    for(i = 2; i <= sqrt(n); i++) {
        if(n % i == 0) {
            return 0;
        }
    }
    return 1;
}

[ 题 : ] 交换A和B的值

// 1.中间变量
void swap(int a, int b) {
   int temp = a;
   a = b;
   b = temp;
}

// 2.加法
void swap(int a, int b) {
   a = a + b;
   b = a - b;
   a = a - b;
}

// 3.异或（相同为0，不同为1. 可以理解为不进位加法）
void swap(int a, int b) {
   a = a ^ b;
   b = a ^ b;
   a = a ^ b;
}

[ 题 : ] 求最大公约数

最大公因数，也称最大公约数、最大公因子

例如 : 12、16的公约数有1、2、4，其中最大的一个是4，4是12与16的最大公约数，一般记为（12，16）= 4。

/** 1.直接遍历法 */
int maxCommonDivisor(int a, int b) {
    int max = 0;
    for (int i = 1; i <=b; i++) {
        if (a % i == 0 && b % i == 0) {
            //取余=0
            max = i;
        }
    }
    return max;
}
/** 2.辗转相除法 */
int maxCommonDivisor(int a, int b) {
    int r;
    while(a % b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return b;
}

[ 题 : ] 最小公倍数

例如 : 12、16的最小公倍数 : 12 = 3*4 , 16 = 4*4 , 3* 4 * 4 = 48 (包含所有因子) , 最小公倍数 = A * (B / 最大公约数) = B * (A / 最大公约数) = A * B / 最大公约数

//最小公倍数 
int minMultiple  = 12 * 16 *  maxCommonDivisor(12,16) ;