算法收录（持续更新）

这里会持续的发布我遇到过的算法题，欢迎在评论中一起探讨这些算法的实现。

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

  int rand10000 {
      return 100 * rand100() + rand100();
  }
  

---

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

  int getMax(int arrLength[N]) {
      assert(arrLength != NULL && N > 0)
      int count = 0;
      int maxLength = arrLength[0];

      for (int i = 1; i < N; i++) {
          if (maxLength < arrLength[i]) { maxLength = arrLength[i]; }
      }

      char * counter = (char *)malloc(sizeof(char) * (mexLength + 1));
      memset(counter, 0, mexLength+1)
      for (int i = 0; i < N; i++) {
          int idx = arrLength[i];
          if (counter[idx] == 0) {
              counter[idx] = 1;
          } else {
              count++;
              counter[idx] = 0;
          }
      }
      free(counter);
      return count;
  }

---

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

---

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

0	1	2	3
4	5	6	7
8	9	10	11

---

• 假设北京和上海间有一趟专列，两个车站每小时整点都会朝着对方发一辆车。已知北京->上海的列车全程需要13.5小时；上海->北京的列车全程需要15.5小时。如果某人坐在其中一辆北京->上海的列车，请问途中会碰到多少辆迎面而来的列车

---

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

  existSum(array: [Int], T: Int) -> (Int, Int)? {
      assert(array != nil)
      let mapper = [Int, Int]()
      let index = 0
      for index in 0..<array.count {
          if let idx = mapper[T - array[index]] {
              return (idx, index)
          }
          mapper[array[index]] = index
      }
      return nil
  }
  

---

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

  首先假设存在一个最大实验次数T，无论我们进行怎样的操作都不会大于这个T。最苦逼的情况下这个T等于99，即我们从第二层开始一直试到第一百层，这样毫无疑问没有任何的技巧性。 那么我们将这99次的实验次数分成多份来进行测试，保证在分了之后仍然保证测试次数是最少的。那么我们假设第一次鸡蛋扔在第T层，如果碎了，就从第一层开始一层层往上实验。假设第T层鸡蛋没有碎，下一次就从T+T-1层开始测试，如果鸡蛋碎了从T+1开始往上测试。于是我们得到了计算公式： T + T-1 + T-2 + T-3 + T-4 + .... + 2 + 1 >= 99 最终得出的T等于14