AI 助理
备案控制台
开发者社区 人工智能 文章 正文

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

2022-10-30 137
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 《基础系列》

请编写一个完整的程序，实现如下功能：从键盘输入数字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;

    }

}
文章标签：
Java
机器学习/深度学习
搜索推荐
索引
算法
存储
龙哥手记
目录
相关文章
-dzk-
|
算法
【AcWing算法基础课】第五章 动态规划（未完待续）(3)
当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
-dzk-
123 0
前端技术栈
|
9月前
|
算法 前端开发
每天一算法，脑子不生锈（真押韵）
每天一算法，脑子不生锈（真押韵）
前端技术栈
69 0
游客ot6eft3qn37ga
|
6月前
|
算法
分享几道大厂面试算法题
分享几道大厂面试算法题
游客ot6eft3qn37ga
59 0
闻缺陷则喜何志丹
|
9月前
|
机器学习/深度学习 算法 机器人
【动态规划】【C++算法】741摘樱桃
【动态规划】【C++算法】741摘樱桃
闻缺陷则喜何志丹
83 1
前端技术栈
|
9月前
|
算法 前端开发 JavaScript
面试必会的几道算法
面试必会的几道算法
前端技术栈
47 0
程序员三木
|
9月前
|
机器学习/深度学习 算法 Java
「程序员必须掌握的算法」动态规划「中篇」
「程序员必须掌握的算法」动态规划「中篇」
程序员三木
54 0
游客d7sf7jc5pjjba
|
算法
算法_每日一题(9.6)
算法_每日一题(9.6)
游客d7sf7jc5pjjba
94 0
游客d7sf7jc5pjjba
|
算法
算法_每日一题(9.12)
算法_每日一题(9.12)
游客d7sf7jc5pjjba
83 0
游客d7sf7jc5pjjba
|
算法
算法_每日一题(9.14)
算法_每日一题(9.14)
游客d7sf7jc5pjjba
84 0
游客d7sf7jc5pjjba
|
算法
算法_每日一题(9.9)
算法_每日一题(9.9)
游客d7sf7jc5pjjba
64 0

热门文章

最新文章

  • 1
    解决kafka集群由于默认的__consumer_offsets这个topic的默认的副本数为1而存在的单点故障问题
  • 2
    使用 Docker 高效搭建本地开发环境（详细教程）
  • 3
    如何使用java代码导出word
  • 4
    《Python编程从0到1》笔记1——表达式的风格（前缀、中缀、后缀）
  • 5
    Nginx目录文件列表显示
  • 6
    中移动与阿里巴巴将在四大领域展开全面战略合作
  • 7
    mysql 主从复制配置
  • 8
    google guice @inject comments
  • 9
    html页面中event的常见应用
  • 10
    微软要在年内推出IPTV平台 抢占客厅市场
  • 1
    一级倒立摆平衡控制系统MATLAB仿真,可显示倒立摆平衡动画,对比极点配置,线性二次型,PID,PI及PD五种算法
    27
  • 2
    基于SOA海鸥优化算法的三维曲面最高点搜索matlab仿真
    33
  • 3
    基于PI控制的三相整流器控制系统的simulink建模与仿真,包含超级电容充电和电机
    42
  • 4
    MCMS：Star 28.1k,还在为CMS系统发愁？这款开源神器让内容管理变得像搭积木一样简单！
    34
  • 5
    XJ-Survey：这个让滴滴日均处理1.2亿次问卷请求的开源系统，今天终于公开了它的架构密码！
    37
  • 6
    CPU can only see the threads
    26
  • 7
    Java+机器学习基础：打造AI学习基础
    41
  • 8
    使用 pipx 安装并执行 Python 应用程序 (1)
    34
  • 9
    国产AI神器Deepseek，本地离线使用教程！
    54
  • 10
    短视频创作助手 | AI剧本生成与动画创作
    152

    • 相关课程

    更多
  • 天池leetcode编程基础课

    • 相关电子书

    更多
  • 面试常考算法
  • 超全算法笔试 模拟题精解合集
  • 超全算法笔试-模拟题精解合集
    • 下一篇
    PAI Model Gallery 支持云上一键部署 DeepSeek-V3、DeepSeek-R1 系列模型