没有合适的资源?快使用搜索试试~ 我知道了~
首页Java实现二维数组查找特定整数算法
Java实现二维数组查找特定整数算法
需积分: 1 0 下载量 80 浏览量
更新于2024-07-20
收藏 434KB DOC 举报
本资源是关于Java编程的《剑指offer》中的一个问题集,主要针对数组的搜索问题,特别是二维数组的查找。题目3要求设计一个函数,判断给定的二维数组(每一行按从左到右递增,每一列按从上到下递增)中是否存在指定的整数。函数的输入包括一个m x n的矩阵和一个整数t,输出为" Yes"表示找到该整数,"No"表示未找到。 题目3描述了经典的二分查找思想在二维数组中的应用,由于二维数组的特殊性,不能直接用线性搜索,需要利用每一行和每一列的递增特性进行辅助判断。在解决这个问题时,可以采用层次遍历的方式,首先在一维数组(每一列)上执行二分查找,找到可能包含目标值的那一列,然后在这一列的子数组(那一行)中再进行一次线性搜索。这样可以在一定程度上缩小搜索范围,提高查找效率。 其他题目也涉及到了类似的数据结构和算法问题,例如动态规划(如题目9、9-1、9-2、10等)、栈的操作(如题目11、12),以及递归和回溯(如题目14、15)。随着难度逐渐提升,还有涉及哈希表(如题目18、19)、树和图的搜索(如题目21、22)、字符串处理(如题目23、24)、排序算法(如题目25、26)、链表操作(如题目27、28)、位运算(如题目29、30)、递归调用优化(如题目31、32)等。这些题目旨在考察Java开发者对基础数据结构和算法的理解与熟练运用。 总结来说,《剑指offer》Java版提供了丰富的编程面试题库,涵盖了多种常见算法和数据结构,有助于提高面试者的问题解决能力和代码优化技巧。通过解答这些问题,程序员可以巩固基础知识,提升编程能力,并为实际工作中的问题解决打下坚实的基础。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/9629543/bg6.jpg)
public static int findMin(int array[]){
if(array==null||array.length==0)
return -1;
int n=array.length;
int i=0;
for(i=1;i<n;i++)
if(array[i]<array[i-1])
return i;
if(i==n)
return 0;
return -1;
}
}
题目 9 描述:
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列
的第n项。斐波那契数列的定义如下:
0,n=0
f(n)=1,n=1
f(n-1)+f(n-2),n>1
输入:
输入可能包含多个测试样例,对于每个测试案例,
输入包括一个整数n(1<=n<=70)。
输出:
对应每个测试案例,
输出第n项斐波那契数列的值。
样例输入:
3
样例输出:
2
public class Offer09 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
System.out.println(function(n));
}
}
public static long function(int n){
// if(n==0) return 0;
// if(n==1) return 1;
// return function(n-1)+function(n-2);
// }
long s=0,s0=0,s1=1;
if(n==0) return s;
if(n==1) return s=1;
for(int i=2;i<=n;i++){
s = s0+s1;
s0 = s1;
s1 = s;
}
return s;
//
// Scanner cin=new Scanner(System.in);
// BigInteger a[]=new BigInteger[71];
// a[0]=BigInteger.ZERO;
// a[1]=BigInteger.ONE;
// for(int i=2;i<=70;i++){
// a[i]=a[i-1].add(a[i-2]);
// }
// int b;
// while(cin.hasNext())
// {
// b=cin.nextInt();
// System.out.println(a[b]);
// }
}
}
题目 9-1 描述:
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台
阶总共有多少种跳法。
输入:
输入可能包含多个测试样例,对于每个测试案例,
输入包括一个整数n(1<=n<=70)。
输出:
对应每个测试案例,
输出该青蛙跳上一个n级的台阶总共有多少种跳法。
样例输入:
5
样例输出:
8
public class Offer09_1 {
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
System.out.println(func(n));
}
}
public static long func(int n){
long m=0;
long x=1,y=2;
if(n==1) return m=1;
if(n==2) return m=2;
for(int i=3;i<=n;i++){
m=x+y;
x=y;
y=m;
}
return m;
}
}
题目 9-2 描述:
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该
青蛙跳上一个n级的台阶总共有多少种跳法。
输入:
输入可能包含多个测试样例,对于每个测试案例,
输入包括一个整数n(1<=n<=50)。
输出:
对应每个测试案例,
输出该青蛙跳上一个n级的台阶总共有多少种跳法。
样例输入:
6
样例输出:
32
public class Offer09_2 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
![](https://csdnimg.cn/release/download_crawler_static/9629543/bg7.jpg)
System.out.println(func(n));
}
}
public static long func(int n){// 当n=n时,共有n
种跳的方式,第一次跳出一阶后,后面还有F(n-1)中跳法;第一次
跳出二阶后,后面还有F(n-2)中跳法...第一次跳出n阶后, 后面还
有 F(n-n)中跳法.
long m=0;
//F(n)=F(n-1)+F(n-2)+...+F(n-n)=F(0)+F(1)+...+F(n-
1)
if(n==0) return m; //又因为F(n-1)=F(0)+...
+F(n-2)
if(n==1) return m=1; //两式相减得:
F(n)-F(n-1)=F(n-1) =====》 F(n)=2*F(n-1) n >= 2
return 2*func(n-1);
}
}
题目 9-3 描述:
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的
小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
输入:
输入可能包含多个测试样例,对于每个测试案例,
输入包括一个整数n(1<=n<=70),其中n为偶数。
输出:
对应每个测试案例,
输出用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有的方法数。
样例输入:
4
样例输出:
5
public class Offer09_3 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
System.out.println(function(n));
}
}
private static long function(int n) {
if(n<=0) return 0;
int f0 = 0, f1 = 1;
int fn = f0 + f1;
for(int i=2; i<=n;i++){
f0 = f1;
f1 = fn;
fn = f0 + f1;
}
return fn;
}
}
题目 10 描述:
输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
输入:
输入可能包含多个测试样例。
对于每个输入文件,第一行输入一个整数T,代表测试样例的数量。对于每个
测试样例输入为一个整数。
。n保证是int范围内的一个整数。
输出:
对应每个测试案例,
输出一个整数,代表输入的那个数中1的个数。
样例输入:
3
4
5
-1
样例输出:
1
2
32
public class Offer10 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int [] m=new int[n];
while(sc.hasNext()){
for(int i=0;i<n;i++){
m[i]=sc.nextInt();
}
for(int i=0;i<n;i++){
fun(m[i]);
}
}
}
static void fun(int n){
int sum=0;
for(int i=0;i<32;i++){
sum +=(n&1); // n&1==1等价于 n
%2==1,
n =n>>1; //n>>=1 等价于 n/=
2,但是相对而言,位运算的效率高。
}
System.out.println(sum);
}
}
题目 11 描述:
给定一个double类型的浮点数base和int类型的整数exponent。求base的
exponent次方。
输入:
输入可能包含多个测试样例。
对于每个输入文件,第一行输入一个整数T,表示测试案例的数目,接下来的
T行每行输入一个浮点数base和一个整数exponent,两个数中间用一个空格
隔开。
输出:
对应每个测试案例,
输出一个浮点数代表答案,保留两位小数即可。
样例输入:
5
1.0 10
0.0 -5
1.0 0
1.2 5
2.0 -1
样例输出:
1.00e+00f
INF
1.00e+00f
2.49e+00f
5.00e-01f
import java.io.BufferedReader;
import java.io.IOException;
剩余30页未读,继续阅读
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://profile-avatar.csdnimg.cn/d61a6c28060f43f899b7875f4d4d1112_qq_27904175.jpg!1)
lingkongduijue
- 粉丝: 1
- 资源: 2
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 多模态联合稀疏表示在视频目标跟踪中的应用
- Kubernetes资源管控与Gardener开源软件实践解析
- MPI集群监控与负载平衡策略
- 自动化PHP安全漏洞检测:静态代码分析与数据流方法
- 青苔数据CEO程永:技术生态与阿里云开放创新
- 制造业转型: HyperX引领企业上云策略
- 赵维五分享:航空工业电子采购上云实战与运维策略
- 单片机控制的LED点阵显示屏设计及其实现
- 驻云科技李俊涛:AI驱动的云上服务新趋势与挑战
- 6LoWPAN物联网边界路由器:设计与实现
- 猩便利工程师仲小玉:Terraform云资源管理最佳实践与团队协作
- 类差分度改进的互信息特征选择提升文本分类性能
- VERITAS与阿里云合作的混合云转型与数据保护方案
- 云制造中的生产线仿真模型设计与虚拟化研究
- 汪洋在PostgresChina2018分享:高可用 PostgreSQL 工具与架构设计
- 2018 PostgresChina大会:阿里云时空引擎Ganos在PostgreSQL中的创新应用与多模型存储
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)