Java面试题总结之数据结构、算法和计算机基础（刘小牛和丝音的爱情故事1）

/*
 * 使用快速排序方法对arr[0:n- 1]排序
从a[ 0 :n- 1 ]中选择一个元素作为middle，该元素为支点；
把余下的元素分割为两段left 和right，使得left 中的元素都小于等于支点，
而right 中的元素都大于等于支点；
递归地使用快速排序方法对left 进行排序；
递归地使用快速排序方法对right 进行排序；
所得结果为left + middle + right。
 
 */
public class QuickSort {
   public static void main(String[] args) {
      int[] arr = {5,2,4,9,7,16,26,3};
      sort(arr, 0, arr.length - 1);
   }
 
   public static void sort(int arr[], int left, int hight) {
      int l = left;
      int h = hight;
      int k = arr[left];
      while (l < h) {
        //  从后往前比较
        //  如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，
        // 然后再从前往后比较
        while (l < h && arr[h] > k) {
           h--;//  h=6
        }
        // 交换位置
        if (l < h) {
           int temp = arr[h];
           arr[h] = arr[l];
           arr[l] = temp;
           // 进行过一次替换后，没必要将替换后的两值再次比较，所以i++直接下一位与k对比
           l++;
        }
        //  从前往后比较 如果没有比关键值大的，比较下一个，
        // 直到有比关键值大的交换位置
        while (l < h && arr[l] <= k) {
           l++;
        }
        // 交换位置
        if (l < h) {
           int temp = arr[h];
           arr[h] = arr[l];
           arr[l] = temp;
           h--;
        }
        //  此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，
        // 但是左右两边的顺序还有可能是不一样的，进行下面的递归调用
      }
      print(arr);
      System.out.print("l=" + (l + 1) + ",h=" + (h + 1) + ",k=" + k + "\n");
      //  递归，先判断l>low再次进行左边排序
      if (l > left) {
        //  左边序列。第一个索引位置到关键值索引-1
        sort(arr, left, l - 1);
      }
      // 左边依次排序执行完递归后，弹栈进行右边排序
      if (h < hight) {
        //  右边序列。从关键值索引+1到最后一个
        sort(arr, l + 1, hight);
      }
   }
 
   //  打印数组的方法
   public static void print(int[] arr) {
      System.out.print("[");
      for (int i = 0; i < arr.length; i++) {
        if (i != (arr.length - 1)) {
           System.out.print(arr[i] + ",");
        } else {
           System.out.print(arr[i] + "]");
           System.out.println();
        }
      }
   }
 
}

/**
     * 1、偶数不可能是质数
     * 2、对于大于2的数，如果一个数a大于数b的一半，那么b不可能被a整除
     */
    public boolean isPrimeNum(int num) {
        // 2特殊处理
        if (num == 2) {
            return true;
        }
        // 识别小于2的数和偶数
        if (num < 2 || num % 2 == 0) {
            return false;
        }
        int max = num / 2;
        for (int i = 3; i < max; i += 2) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

public class CountGame {
    //判断第n个人是否已经出列
    private static boolean same(int[] p, int l, int n) {
       for (int i = 0; i < l; i++) {
           if (p[i] == n) {
              return true;
           }
       }
       return false;
    }
 
    public static void play(int playerNum, int step) {
       //按出列顺序排列的新数组
       int[] p = new int[playerNum];
       //当前报数的人
       int counter = 1;
       while (true) {
           if (counter > playerNum * step) {
              break;
           }
           //从1开始报数
           for (int i = 1; i < playerNum + 1; i++) {
              while (true) {
                  //如果报数的人已经出去，则跳过
                  if (same(p, playerNum, i) == false){
                     break;
                  }
                  else{
                     i = i + 1;
                  }
              }
              if (i > playerNum){
                  break;
              }
              //如果当前报数的人是第m个人，则第M个人出列
              if (counter % step == 0) {
                  System.out.print(i + " ");
                  p[counter / step - 1] = i;
              }
              counter += 1;
           }
       }
       System.out.println();
    }
 
    public static void main(String[] args) {
       //一共10个人，输到第7个人出列
       play(10, 7);
    }
}

//首先导入大数包和输入包
import java.math.BigInteger;
import java.util.Scanner;
 
//计算n!(1*2*...*n)
public class BigIntegerTestDrive {
    public static void main(String[] args) {
       // 输入n
       Scanner in = new Scanner(System.in);
       int n = in.nextInt();
 
       // 输入初始值
       int pre_answer = 1;
       // 将初始值由int类型转变为String类型
       String x = String.valueOf(pre_answer);
       // 将String类型的的初始值，传递给BigInteger类型，
       BigInteger answer = new BigInteger(x);
 
       // 循环迭代逐次相乘
       for (int i = 1; i <= n; i++) {
 
           // 因为BigInteger类型只能和该类型的变量相乘，因此还需将每次的中间乘数也依次变为BigInteger类型
           String var = String.valueOf(i);
           BigInteger variable = new BigInteger(var);
 
           // 调用相乘函数进行相乘运算
           answer = answer.multiply(variable);
 
       }
       // 输出最终答案
       System.out.println(answer);
       in.close();
 
    }
}