几道算法题(慢速更新中)

一

当前已经编程实现函数int rand100()，该函数可以返回0~99的随机整数，且可以保证等概率。利用该函数实现int rand10000()，要求等概率返回0~9999的随机整数

- (int)rand10000{
    // 思路  0 ~ 99 * 100 + 0 ~ 99
    return  rand100() * 100 + rand100();
}

二

汤姆现在要在家里举办宴会，他有很多根长度并不完全相同的筷子。现已知每根筷子的长度，每个客人都能拿到两根相同长度的筷子，求宴会最多可以招待多少名宾客的函数实现

思路:
首先把筷子按顺序排列,然后循环判断第n 根 和 第n + 1根 是否相等,相等的话记录一次,并且在原数组中删除避免重复记录

- (void)viewDidLoad {
    [super viewDidLoad];

    NSMutableArray *totalArray=[[NSMutableArray alloc]initWithObjects:
@"2",@"2",@"2",@"3",@"3",@"3",@"5",@"6",@"7", nil];

    //排序
    NSMutableArray *sortArray = [self sort:totalArray];

    NSLog(@" %ld",[self MaxPeopleNumberWithArray:sortArray]);
}

//冒泡排序
- (NSMutableArray *)sort:(NSMutableArray *)arr{
    for(NSInteger i = 0 ; i < arr.count - 1 ; i++){
        for (NSInteger j = 0; j < arr.count - i - 1; j++){
            if ([arr[j]integerValue] > [arr[j + 1]integerValue]){
                NSInteger temp  = [arr[j]integerValue];
                arr[j] = arr[j + 1];
                arr[j + 1] = [NSNumber numberWithInteger:temp];
            }
        }
    }
    return arr;
}

//得出 最多人数
- (NSInteger)MaxPeopleNumberWithArray:(NSMutableArray *)arr
{
    
       NSInteger number;
        for (NSInteger j = 0; j < arr.count  - 1; j++){
            if ([arr[j]integerValue] == [arr[j + 1]integerValue]){

         // 记录一次
        number += 1;
        //删除掉  避免如 3个连续的 被记录两次
        [arr removeObjectAtIndex:j];
            }
        }
    return number;
}

三

现有一个整数序列，你可以交换其中任意两个数以得到一个新序列，求共能得到多少种不同的序列（如果是3，3，3，3，那么无论怎么调换，都只存在一种序列）

思路:
只要前后不一致就是一种序列,需要考虑全部一样的情况

NSMutableArray *arr=[[NSMutableArray alloc]initWithObjects:
@"2",@"2",@"3", nil];
//  全一样的计数
    NSInteger a = 0 ;
//  不一样的序列计数
    NSInteger k;

    for (NSInteger i = 0 ; i < arr.count ; i++){
        for (NSInteger j = i + 1 ; j < arr.count ; j++){
            // 全相等  1种方法
            if (arr[i] == arr[j]){
                a = 1;
            } else if (arr[i] != arr[j]){
                //  有一处不相等就不会是1  先把一种方法清空
                a = 0;
                // 前后不相等就是一种方法  记录下来
                k++;
            }
        }
    }
    //等于1 说明全相等 打印1
    if ( a == 1 ) {
        NSLog(@"  %ld",a);
    } else {
        NSLog(@" %ld",k);
    }

四

现有一个M行N列的数组，要求按照反向斜对角线（右上角->左下角）的方式进行打印，编程实现int printMatrix[int arrMatrix[M][N]]
下面案例的输出顺序为：0-1-4-2-5-8-3-6-9-7-10-11

思路;
先按上面的表格打印出来,按照横纵坐标位置输入,而不是计算

    //  打印出 数组格式
    int m = 3;
    int n = 4;
    int a[m][n];
    //递增 内容
    int count = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            a[i][j] = count++;
            printf("%d    ",a[i][j]);
        }
        printf("\n");
    }
    
    printf("\n\n");
    
    // 按要求打印排列内容
    int k = 0;
    while (k < (m + n - 1)) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //k 递增  i j
                if (i + j == k) {
                    //为了更好理解  打印下 i  j 对应 上面格式内容
                    // 就是对应上面输出的m n 位置
                    printf("%d   i = %d  j = %d        "  , a[i][j],i,j);
                }
            }
        }
        printf("\n");
        k++;
    }

五

假设北京和上海间有一趟专列，两个车站每小时整点都会朝着对方发一辆车。已知北京->上海的列车全程需要13.5小时；上海->北京的列车全程需要15.5小时。如果某人坐在其中一辆北京->上海的列车，请问途中会碰到多少辆迎面而来的列车
</br>
这个我没怎么看懂,应该不对吧,希望大神指教

  // 假设  13.5 的速度为 15.5   15.5的速度为 13.5
  // 北京  -  上海
    CGFloat a = 15.5;
  // 上海  -  北京
    CGFloat b = 13.5;
   // 总路程
    CGFloat distance = a * b;

    //碰见的时间
    CGFloat meetTimer = distance / (15.5 + 13.5) ;
    
    //如果双发都是同时发车那么会碰见14次,但是还要考虑之前的情况
    //碰见次数  因为不会是整数结果 说明 还会多遇见一次
    NSInteger meetNumber = meetTimer + 14 + 1;

    NSLog(@" %ld",meetNumber);

六

存在有序整数数组Array，现已知整数T，实现算法existSum(array, T)求数组中是否存在两个元素a + b = T，如果存在，输出a和b在数组中的位置

思路:
T是已知的,通过循环给b赋值,就可以得出a, 得出a后判断是否存在于数组中,存在即数组中存在a + b = T,打印ab位置

- (void)viewDidLoad {
   [super viewDidLoad];

    //数组 不能直接添加 NSInteger  用NSNumber 包含下
 NSArray *arr = [[NSArray alloc]initWithObjects:[NSNumber numberWithInteger:1],
                                                   [NSNumber numberWithInteger:2],
                                                   [NSNumber numberWithInteger:3],
                                                   [NSNumber numberWithInteger:4],
                                                   [NSNumber numberWithInteger:5],
                                                   [NSNumber numberWithInteger:6],
                                                   nil];
    //假设T 为7
    NSInteger T = 7;
    
    [self existSumWithArray:arr Number:T];
}

- (void)existSumWithArray:(NSArray *)arr Number:(NSInteger)number{
    
    NSInteger a,b;
  
    for (int i = 0 ; i < arr.count ; i++){
        //记录 用  避免类型转换带来的问题
        b =    [arr[i] integerValue];
        a = number - b;
    
        //判断数组中 是否包含 a
        if ([arr containsObject:[NSNumber numberWithInteger:a]]){
    //   indexOfObject   获取元素的下标
  
        NSLog(@"数组中包含  a + b = T, b = %ld 下标为%d , a  = %ld 下标为%ld",[arr[i] integerValue],i,a,[arr indexOfObject:[NSNumber numberWithInteger:a]]);

        }else {
            NSLog(@"当 b = %ld 时,数组不包含  a + b = T 的情况",[arr[i] integerValue]);
        }
    }
}

七

假设鸡蛋从X层楼高度摔下来刚好会碎（X-1层不会碎），那么我们称鸡蛋的临界点是X-1。现在有一栋100层高的楼房，你有两个鸡蛋。请问你如何进行最少的试验得出这个鸡蛋的临界点？

这个不是算法,但挺有意思的,说下我的思路:

他说的最少并不是一次,而是抽屉原理中的最少

比如 一副扑克,我想抽到两张相同花色的扑克,最少要抽5次,因为我要先抽到四种情况,红心,黑心,梅花,方片,再抽一张才会有相同花色,还是不理解可以百度一下抽屉原理

回到问题,常识也知道越高越容易摔碎,可以从100层往下一层一层的试,但这样太麻烦了,不妨设个x,在x层摔碎,我们会依次在x - 1层试,x - 2, x - 3等层试

用集合的方式算一下 记得加上没测的

x + x - 1 + x - 2 +..... +1 = 100
(x + 1)*x/2 = 100
x = 14

验证下
注意 这个14是一共要扔14次
数组是从14递减 再加上一位数得到当前位
14 27 39 50 60 69 77 84 90 95 99 100

比如我在27层扔,摔碎了,接下来我就在14层扔,碎了就往下一层扔,没碎就在上一层扔,数一下,无论上下都是14

再比如96层碎,我从14层开始试验,数一下也是14次

所以我们可以得出结论最少需要14次