Java面试题总结之数据结构、算法和计算机基础（刘小牛和丝音的爱情故事1）mp.weixin.qq.com
全文字数： 1703
阅读时间： 大约6 分钟
丝音：你知道一个byte 几个bit位吗？
刘小牛：这个问题太简单了，一个Byte是8bit。
丝音：常用UNIX 命令有哪些(Linux 的常用命令)（至少10 个）？
刘小牛：unix常用命令有：
丝音：嗯嗯不错，下一个问题，后序遍历下列二叉树，访问结点的顺序是什么？
刘小牛：这问题也太简单了，访问顺序为：DJGEBKNIFCA 。：顺序为：DJGEBKNIFCA 。
丝音：哼，敢小瞧我们天堂的题，下一道题，排序都有哪几种方法？请列举说明，然后用JAVA 实现一个快速排序。
刘小牛：排序的方法有：插入排序（直接插入排序、希尔排序），交换排序（冒泡排序、快速排序），选择排序（直接选择排序、堆排序），归并排序，分配排序（桶排序、基数排序）；
/*
* 使用快速排序方法对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;
}
丝音：给你出一道难得吧，这个题有好多以前应聘的人都没答对呢，设有ｎ个人依围成一圈，从第１个人开始报数，数到第ｍ个人出列，然后从出列的下一个人开始报数，数到第ｍ个人又出列，…，如此反复到所有的人全部出列为止。设ｎ个人的编号分别为1，2，…，n，打印出出列的顺序；要求用java 实现。
刘小牛：这道题难不倒我，代码如下：
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);
}
}丝音：哇，你真厉害呀，最后一个问题，用程序实现1000 的阶乘。
刘小牛：这个问题有个陷阱，就是普通的数据类型存不了这么大的数，不过这难不倒我的，嘿嘿
Java的代码实现如下：
//首先导入大数包和输入包
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(); }
}
发布于 10:07