魅族 手机 java官网依旧换新分类java怎么做出来的

来源：蜘蛛抓取(WebSpider) 时间：2017-11-02 17:37 标签： 魅族java面试
2041人阅读
谈面试（8）
java（171）
1.一个台阶总数为n，可以跳上1级台阶，也可以跳上2级。求跳上一个n级的台阶总共有多少种跳法。时间复杂度是多少？
对于本题,前提只有 一次 1阶或者2阶的跳法。
a.如果两种跳法，1阶或者2阶，那么假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1);
b.假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)
c.由a\b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2)&
d.然后通过实际的情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2
e.可以发现最终得出的是一个斐波那契数列：
&&&&&&&&&&&&&&| 1, (n=1)
f(n) =&&&&&| 2, (n=2)
&&&&&& & & &&&| f(n-1)+f(n-2) ,(n&2,n为整数)
publicclassSolution
&&&&publicintJumpFloor(inttarget)
&if(target
&&& &return-1;
&}&elseif(target
&&& &return1;
&}&elseif(target
&&& &return2;
&&& &return&JumpFloor(target-1)+JumpFloor(target-2);
这中方法会有重复计算，所以效率和性能很低，比如f(5)+f(4)。 f(5)在递归的时候，会计算f(4)以及f(3)，计算f(5)+f(4)
中的f(4)时候，又会计算f(4)。而底层的f(3)是计算重复率最高的。每次递归下去都会计算f(3)。
&&&&&&&&&&&
& & &&f(10)
&&&&&&&&&&&&&&&/&&&&&&&&\
&&&&&&&&&&&&f(9)&&&&&&&&&f(8)
&&&&&&&&&&/&&&&&\&&&&&&&/&&&&\
&&&&&&&f(8)&&&&&f(7)&&f(7)&&&f(6)
&&&&&&/&&&\&&&&&/&&&\&
&&&f(7)&&f(6)&&f(6) f(5)
我们不难发现在这棵树中有很多结点会重复的，而且重复的结点数会随着n的增大而急剧增加。这意味这计算量会随着n的增大而急剧增大。事实上，用递归方法计算的时间复杂度是以n的指数的方式递增的。大家可以求Fibonacci的第100项试试，感受一下这样递归会慢到什么程度。在我的机器上，连续运行了一个多小时也没有出来结果。所以这个时间复杂度是0(2^n)。这个可是指数级的增长啊！！！！！！
经过优化，我们只要计算一次就可以了 。。这里由于这个是斐波那契数列的模型。故代码如下：
public class Main {
public static void main(String args[]){
System.out.println(JumpFloor(5));
static int
JumpFloor(int n){
int prev = 0;
int cur = 1;
for(int i = 1; i &= i++){
cur = prev +
经过改进后的代码的时间复杂度为0（n）.
2.如下图，有一棵二叉树，根节点为root，现在要从root开始查找某个结点x，要求，必须层序遍历，不得在一层的 节点未全部访问前跳到下一层。
现在我们要找的是X结点。
这里使用的是队列思想实现，代码如下：
import java.util.LinkedL
import java.util.Q
public class test {
public static void main(String args[]) {
TreeNode A=new TreeNode(1);
TreeNode B=new TreeNode(2);
TreeNode C=new TreeNode(3);
A.lchild=B;A.rchild=C;
TreeNode D=new TreeNode(4);
TreeNode E=new TreeNode(5);
B.lchild=D;B.rchild=E;
TreeNode F=new TreeNode(0);//F节点表示的值为0，也就是为空。
TreeNode G=new TreeNode(7);
C.lchild=F;C.rchild=G;
TreeNode targetNode=levelTraverse(A,5);
System.out.println();
System.out.println(targetNode.toString());
// 层次遍历
static TreeNode levelTraverse(TreeNode root,int x) {
System.out.println(& 层序遍历：&);
System.out.print(root.data + & &);
Queue&TreeNode& queue = new LinkedList&TreeNode&();
queue.offer(root);
while (!queue.isEmpty()) {
if(queue.peek().data==x) return queue.peek();
if(queue.peek().lchild!=null) {
System.out.print(queue.peek().lchild.data + & &);
queue.offer(queue.peek().lchild);
if(queue.peek().rchild!=null) {
System.out.print(queue.peek().rchild.data + & &);
queue.offer(queue.peek().rchild);
queue.poll();
System.out.println();
System.out.println(&二叉树共& + getDepth(root) + &层&+&\n没找到要查找的元素!&);
return new TreeNode(-1);//-1表示没有找到这个树节点
static int getDepth(TreeNode root){
if(root==null){
int left=getDepth(root.lchild);
int right=getDepth(root.rchild);
return Math.max(left, right)+1;
class TreeNode {
// 构造方法
public TreeNode(int data) {
this.data =
public String toString(){
return&我是值为&+data+&的树节点!&;
层序遍历：
1 2 3 4 5 0 7&
我是值为5的树节点!
如果将要找的值变为 8（是不存在的。）
则输出结果为：
层序遍历：
1 2 3 4 5 0 7&
二叉树共3层
没找到要查找的元素!
我是值为-1的树节点!
接下来，做了这两道题目后，面试官开始对我狂轰滥炸，且等我娓娓道来。
//第一行 & &1个字节
//第二行 & & 8个字节
(short)a/b*2;//第三行 & &2个字节
问，第三行的结果是什么类型的？
答案：是double类型的。因为输出来是22.0。无论是(int)a/b*2或者是(short)a/b*2都是22.0。
2.问如何给hashMap是不是同步安全的，如果不是如何使安全。
hashMap这个对Map接口的实现不是同步的。如果多个线程同时访问此映射，而其中至少一个线程从结构上修改了该映射，则它必须 保持外部同步。（结构上的修改是指添加或删除一个或多个映射关系的操作；仅改变与实例已经包含的键关联的值不是结构上的修改。）这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用
Collections.synchronizedMap 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的不同步访问，如下所示：
Map m = Collections.synchronizedMap(new HashMap(...));
上面是第一种
第二种方法：
&&&&&&&&&&创建一个带有默认初始容量 (16)、加载因子 (0.75) 和 concurrencyLevel (16) 的新的空映射。
此类支持获取的完全并发和更新的所期望可调整并发的哈希表。
3.hashset中判别重复的原则？
作为key的对象将通过计算其散列函数来确定与之对应的value的位置，因此任何作为key的对象都必须实现hashCode和equals方法。这两个方法继承自类Object。如果两个对象相同，obj1.equals（obj2）=true。则他们的hashCode必须相同。
4.arrayList和LinkedList的底层原理，查找谁快，任意插入删除元素谁快。
答：前者实质是数组。后者实质是链表 实现的，可以用作双向链表，队列，堆栈，双端队列（它实现了Queue接口）。
& 前者查找快，后者任意插入删除元素谁快。
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：294339次
积分：5346
积分：5346
排名：第5469名
原创：240篇
转载：29篇
评论：31条
(1)(1)(2)(2)(2)(1)(9)(3)(1)(5)(25)(18)(19)(165)(17)
(window.slotbydup = window.slotbydup || []).push({
id: '4740887',
container: s,
size: '250,250',
display: 'inlay-fix'

我要回帖

更多关于 魅族java面试 的文章

 

随机推荐