Java训练题9

53 阅读 0 评论 35 点赞

我是靠谱客的博主冷傲汉堡，最近开发中收集的这篇文章主要介绍Java训练题9，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

文章目录

- 一、选择题
- 二、编程题

一、选择题

1、请指出冒泡排序平均时间复杂度（A ）
A. n^2
B. nlogn
C. n
D. logn
答案解析：A
冒泡排序算法如下：

public void bubbleSort1(int[] array){
for (int i = 0; i < array.length-1 ;
i++) {
for (int j = 0; j < array.length-i-1; j++) {
if(array[j+1]<array[j]){//A || B 
swap(array,j+1,j);
}
}
}
}

其中算法有内外两层循环，设数组的长度为n
其时间复杂度为：
(n-1)*(n-1+n-2+…1)
取渐近值，即整个表达式中最大的项，得到时间复杂度为 n^2
2、确定如下关于求n!算法的时间复杂度是（A ）

long fac(int n) {
return (n > 1 ? n * fac(n - 1) : 1);
}

A. O(n)
B. O(nlog(n))
C. O(n^2)
D. O(n^3)
答案解析：A
输入为n时，
当n>1的时候，程序不断地递归调用函数本身
当程序执行到n=1的时候，才会直接返回1
所以当输入n时，递归栈的最大调用深度为n，即它的时间复杂度为O(n)
3、判断对错。List，Set，HashMap都继承自Collection接口（ B）
A. 对
B. 错
答案解析：B
在集合框架中，List和Set继承自Collection接口；
HashMap继承自Map接口
4、下面哪些类实现或者继承了Collection接口？【多选】（B C ）
A. HashMap
B. ArrayList
C. Vector
D. Iterator
答案解析：B C
ArrayList和Vector继承了Collection接口；
HashMap继承了Map接口；
Iterator 属于迭代器接口
5、关于容器下面说法正确的是（D ）
A. 列表(List)和集合(Set)存放的元素都是可重复的。
B. 列表(List)和集合(Set)存放的元素都是不可重复的。
C. 映射(Map)<key,value>中key是可以重复的。
D. 映射(Map)<key,value>中value是可以重复的。
答案解析：D
列表（List）中的元素可以重复；
集合(Set)存放的元素不可以重复；
映射(Map)<key,value>中key是唯一的，不可以重复的

二、编程题

1、从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。OJ链接

示例：
输入：head = [1,3,2]
输出：[2,3,1]

【解题思路】：
栈的特点是后进先出，即最后压入栈的元素最先弹出。考虑到栈的这一特点，使用栈将链表元素顺序倒置。从链表的头节点开始，依次将每个节点压入栈内，然后依次弹出栈内的元素并存储到数组中。
1、创建一个栈，用于存储链表的节点
2、创建一个指针，初始时指向链表的头节点
3、当指针指向的元素非空时，重复下列操作：
3.1、将指针指向的节点压入栈内
3.2、将指针移到当前节点的下一个节点
4、获得栈的大小 size，创建一个数组 print，其大小为 size
5、创建下标并初始化 index = 0
6、重复 size 次下列操作：
6.1、从栈内弹出一个节点，将该节点的值存到 print[index]
6.2、将 index 的值加 1

class Solution {
public int[] reversePrint(ListNode head) {
Stack<ListNode> stack=new Stack<>();
ListNode temp=head;
while(temp!=null){
stack.push(temp);
temp=temp.next;
}
int size=stack.size();
int[] print=new int[size];
for(int i=0;i<size;i++){
print[i]=stack.pop().val;
}
return print;
}
}

2、移除未排序链表重复节点
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。OJ链接

示例1：
输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]
实例2:
输入：[1, 1, 1, 1, 2]
输出：[1, 2]

【解题思路】：
我们对给定的链表进行一次遍历，并用一个哈希集合（HashSet）来存储所有出现过的节点。由于在大部分语言中，对给定的链表元素直接进行「相等」比较，实际上是对两个链表元素的地址（而不是值）进行比较。因此，我们在哈希集合中存储链表元素的值，方便直接使用等号进行比较。
具体地，我们从链表的头节点 head 开始进行遍历，遍历的指针记为 pos。由于头节点一定不会被删除，因此我们可以枚举待移除节点的前驱节点，减少编写代码的复杂度。

class Solution {
public ListNode removeDuplicateNodes(ListNode head) {
if (head == null) {
return head;
}
Set<Integer> occurred = new HashSet<Integer>();
occurred.add(head.val);
ListNode pos = head;
// 枚举前驱节点
while (pos.next != null) {
// 当前待删除节点
ListNode cur = pos.next;
if (occurred.add(cur.val)) {
pos = pos.next;
} else {
pos.next = pos.next.next;
}
}
pos.next = null;
return head;
}
}