几道算法题很简单哈（二）-阿里云开发者社区

请编写一个完整的程序，实现如下功能：从键盘输入数字n，程序自动计算n!并输出。（注1：n！=1*2*3...*n, 注2：请使用递归实现）

思路说明：因为n! = (n-1)! * n，所以要求n!首先要求出(n-1)!，而(n-1)! = (n-1-1)! * (n-1)，以此类推，直到n = 1为止。

importjava.util.Scanner;

publicclassTestFactorial {

publicstaticvoidmain(String[] args) {

System.out.print("请输入一个整数：");

Scanner sc = newScanner(System.in);

intn = sc.nextInt();

System.out.println(n + "的阶乘是："+ factorial(n));

}

/**求阶乘的方法*/

publicstaticintfactorial(intn) {

if(n == 1){

return1;

}

returnfactorial(n - 1) * n;

}

请用递归的方法计算斐波那契数列的同项F（n），已知F0=0,F1=1,F(n)=F(n-1)+F(n-2)(n>=2,n∈N*).

思路说明：斐波那契数列的排列是：0，1，1，2，3，5，8，13，21，34，55，89，144……，特别指出的是0不是第一项而是第0项；因为F(n)=F(n-1)+F(n-2)，所以要求F(n)首先要求出F(n-1)和F(n-2)，而F(n-1)=F(n-1-1)+F(n-1-2)，以此类推，直到,F(2)=F(1)+F(0)为止，已知F(1) = 1，F(0) = 0。现在有整数数组{11,66,22,0,55,32}，请任意选择一种排序算法，用Java程序实现

冒泡思路说明：

(1) 最开始将数组看做一个无序数列(个数是数组的长度)与一个有序数列(0个)的组合；

(2) 每一趟比较完后, 找到了无序数列的最大值, 将其放到有序数列中(有序数列个数+1)；

(3) N个数, 比较N-1趟；

(4) 每一趟挨个进行比较：从数组的第一个元素开始, 到无序数列的最后一个为止；

(5) 如果前边一个大于后边一个, 那么交换位置；

(6) 每趟比较的次数与趟数有关；

(7) 根据每趟比较是否发生了交换判断数据是否已经有序，从而进行优化。

publicclassTestSort {

publicstaticvoidmain(String[] args) {

int[] arr = {11, 66, 22, 0, 55, 32};

// 调用排序方法

sort(arr);

// 输出排除后的数组

for(intnum : arr) {

System.out.print(num + "\t");

}

publicstaticvoidsort(int[] arr) {

// 定义标记

booleanflag = false;

inttemp;

// 排序

// 外层循环控制的是比较的趟数

for(inti = 0; i < arr.length - 1; i++) {

// 每一趟比较之前初始化, 否则会保留上一堂比较的结果

flag = false;

// 内层循环控制的是每趟比较的次数

for(intj = 0; j < arr.length - 1- i; j++) {

// 挨个进行比较: 从数组的第一个元素开始, 到无序数列的最后一个

if(arr[j] > arr[j + 1]) {

// 交换

temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

//如果发生交换，改变flag的值

flag = true;

}

if(!flag) {

break;

}

请根据注释，编码实现下面类的方法

// 这个类用于存取一组权限，每个权限用非负整数表示的.这组枳限存储在

// righiString属性中。如果权限N权限存在，rightString第N个字符为“1”,否则，为空格。

classRightStore {

publicString righString = "";

// 如果传入的权限right存在，该方法返回true.否期，为false.,

// right为传入的权限的整数值.

publicbooleangetRight(intright) {

returntrue;

}

// 该方法存储或消除传入的权限.如果value为true,存储传入的权限,

// 否则淸除该权限.

// right为传入的权限的整数值.

publicvoidsetRight(intright, booleanvalue) {

}

思路说明：我们首先要读懂这道题的意思：righString这个字符串是用来存储一系列权限的，并且权限的取值只有两种：有和没有；在righString中使用字符‘1’表示有权限，字符空格‘ ’表示没有权限。举个例子：如果righString的长度为3，第一位表示对订单系统是否有权限，第二位表示对人员管理系统是否有权限，第三位表示对库存系统是否有权限。而方法中的int right参数则表示的是字符串的第几位。

上边这些搞明白之后，方法的编写就简单多了。

publicclassRightStore {

publicString righString = "";

publicbooleangetRight(intright) {

//先求得第right个字符

charch = righString.charAt(right - 1);

//如果ch为'1'，返回true，否则返回false

returnch == '1';

}

publicvoidsetRight(intright, booleanvalue) {

//如果value为true,存储传入的权限，否则消除权限（改为空格）

righString.replace(righString.charAt(right - 1), value ? '1': ' ');

}

二分法查询（递归实现）

思路说明：假设在一个已经排好序的有序序列(N个元素，升序排列)，首先让序列中的中间的元素与需要查找的关键字进行比较，如果相等，则查找成功，否则利用中间位置将序列分成两个子序列，如果待查找的关键字小于中间的元素，则在前一个子序列中同样的方法进一步查找，如果待查找的关键字大于中间的元素，则在后一个子序列中同样的方法进一步查找，重复以上过程一直到查找结束！

importjava.util.Scanner;

publicclassTestBinarySearchRecursion {

publicstaticvoidmain(String[] args) {

int[] a = { 1, 3, 5, 7, 9, 11, 13};

System.out.print("请输入要查找的元素：");

inte = newScanner(System.in).nextInt();

intindex = binarySearch(a, 0, a.length - 1, e);

System.out.println(index != -1? "元素索引为"+ index : "没有该元素");

}

privatestaticintbinarySearch(int[] a, intlow, inthigh, inte) {

intmid = 0;

if(low <= high) {

mid = (low + high) / 2;

if(a[mid] == e) {

returnmid;

} elseif(a[mid] > e) {

returnbinarySearch(a, low, mid - 1, e);

} else{

returnbinarySearch(a, mid + 1, high, e);

}

return-1;

}

编写一段Java程序，把一句英语中的每个单词中的字母次序倒转，单词次序保持不变，例入输入为“There is a dog.”,输出结果应该是“erehT si a god.”要求不使用Java的库函数，例如String类的split，reverse方法。

函数形如：

publicstaticString reverseWords(String input) {

String str = "";

returnstr;

}

思路说明：将字符串转化成字符数组，然后根据数组中空格的位置判断每个单词所占的索引范围，根据得到的索引将数组中的每个单词逆序后拼接到新的字符串中。

publicclassTestStringReverse{

publicstaticvoidmain(String[] args) {

String input = "There is a dog";

System.out.println("逆转后的字符串为："+ reverseWords(input));

}

publicstaticString reverseWords(String input) {

String str = "";

//将字符串转化成字符数组

char[] arr = input.toCharArray();

//index用来记录每个单词的起始索引

intindex = 0;

//遍历字符数组，将空格前边的单词挨个拼接到str中

for(inti = 0; i < arr.length; i++) {

if(arr[i] == ' '){

//根据空格的位置将空格前边一个单词密续追加到str中

for(intj = i - 1; j >= index; j--){

str += arr[j];

}

//单词拼接完成后，拼接一个空格

str += ' ';

//让index指向下一个单词的起始位置

index = i + 1;

}

//将最后一个单词拼接上

for(inti = arr.length - 1; i >= index; i--){

str += arr[i];

}

returnstr;

}

手写9x9乘法表，冒泡排序

9x9乘法表:

classDemo {

publicstaticvoidmain(String[] args) {

for(intx = 0;x <= 9; x++) {

for(inty = 1;y <= x; y++) {

System.out.print(y+"*"+x+"="+x*y+"\t");

}

System.out.println();

}

冒泡排序:

publicclassBubbleSort{

publicstaticvoidmain(String[] args){

intscore[] = {67, 69, 75, 87, 89, 90, 99, 100};

for(inti = 0; i < score.length -1; i++){//最多做n-1趟排序

for(intj = 0;j < score.length - i - 1; j++){//对当前无序区间score[0......length-i-1]进行排序(j的范围很关键，这个范围是在逐步缩小的)

if(score[j] < score[j + 1]){ //把小的值交换到后面

inttemp = score[j];

score[j] = score[j + 1];

score[j + 1] = temp;

}

System.out.print("第"+ (i + 1) + "次排序结果：");

for(inta = 0; a < score.length; a++){

System.out.print(score[a] + "\t");

}

System.out.println("");

}

System.out.print("最终排序结果：");

for(inta = 0; a < score.length; a++){

System.out.print(score[a] + "\t");

}

题目：给定一个整数数组，找到是否该数组包含任何重复数字。你的函数应该返回true只要有任何数字在该数组中重复出现，否则返回false。

publicclassSolution {

publicbooleancontainsDuplicate(int[] nums) {

Set<Integer> numSet = newHashSet<Integer>();

for(inti=0;i<nums.length;i++){·

if(numSet.contains(nums[i]))

returntrue;

else

numSet.add(nums[i]);

}

returnfalse;

}

几道算法题很简单哈（二）

热门文章

最新文章

相关课程

相关电子书