数据结构与算法
剑指offer
JZ4:重建二叉树
解法：递归，时间复杂度：O(n)，空间复杂度：O(n)
public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
TreeNode treeNode = null;
if (pre.length == 0 || vin.length == 0 || pre.length != vin.length || pre == null || vin == null) {
return null;
}
else {
treeNode = new TreeNode(pre[0]);
for (int i =0; i < pre.length; i++)
{
if (pre[0] == vin[i]){
treeNode.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(vin,0,i));
treeNode.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length), Arrays.copyOfRange(vin,i+1,vin.length));
}
}
}
return treeNode;
}
JZ5：用两个栈实现队列
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
// 入栈
public void push(int node) {
stack1.push(node);
}
//出栈
public int pop() {
if (stack2.isEmpty())
while (!stack1.isEmpty()){
stack2.push(stack1.pop());
}
return stack2.pop();
}
JZ6：旋转数组的最小数字
解法：二分查找，时间复杂度：O(log n)，空间复杂度：O(1)
public int minNumberInRotateArray(int[] array) {
if (array == null || array.length == 0) {
return 0;
}
if (array.length == 1 || array[array.length - 1] > array[0]) {
return array[0];
}
int left = 0; int right = array.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (array[mid] > array[mid + 1]) {
return array[mid + 1];
}
if (array[mid - 1] > array[mid]) {
return array[mid]; }
if (array[mid] > array[0]) {
left = mid + 1;
}
else { right = mid - 1; }
}
return -1;
}
试题
1、Java 有没有goto?
答：goto 是java 中的保留字，现在没有在java 中使用
2、在JAVA 中，如何跳出当前的多重嵌套循环？
答：在最外层循环前加label 标识,然后用break:label 方法即可跳出多重循环。
3、&和&&的区别
答：&是位运算符，表示按位与运算，&&是逻辑运算符，表示逻辑与（and）。
4、heap 和stack 有什么区别？
答：栈是一种线形集合，其添加和删除元素的操作应在同一段完成，栈按照后进先出的方式进行处理；堆是栈的一个组成元素。
5、swtich 是否能作用在byte 上，是否能作用在long 上，是否能作用在String上?
答：switch（expr1）中，expr1 是一个整数表达式。因此传递给switch 和case语句的参数应该是int、short、char 或者byte。long,string 都不能作用于swtich。
6、用最有效率的方法算出2 乘以8 等于几?
答：2 << 3
7、有没有length()这个方法? String 有没有length()这个方法？
答：数组没有length()这个方法，有length 的属性。String 有length()这个方法。
8、构造器Constructor 是否可被override?
答：构造器Constructor 不能被继承，因此不能重写Overriding，但可以被重载Overloading。
9、JVM JDK 和 JRE 是什么？
Java 虚拟机（JVM）是运? Java 字节码的虚拟机。JVM 有针对不同系统的特定实现（Windows，Linux，macOS），?的是使?相同的字节码，它们会给出相同的结果。字节码和不同系统的 JVM 实现是 Java 语?“?次编译，随处可以运?”的关键所在。
JDK 是 Java Development Kit，它是功能?全的 Java SDK。它拥有 JRE 所拥有的?切，还有编译器（javac）和?具（如 javadoc 和 jdb）。它能够创建和编译程序。
JRE 是 Java 运?时环境。它是运?已编译 Java 程序所需的所有内容的集合，包括 Java 虚拟机（JVM），Java 类库，java 命令和其他的?些基础构件。但是，它不能?于创建新程序。
10、Java 和 C++的区别与联系?
- 都是?向对象的语?，都?持封装、继承和多态
- Java 不提供指针来直接访问内存，程序内存更加安全
- Java 的类是单继承的，C++ ?持多重继承；虽然 Java 的类不可以多继承，但是接?可以多继承。
- Java 有?动内存管理机制，不需要程序员?动释放??内存
- 在 C 语?中，字符串或字符数组最后都会有?个额外的字符‘\0’来表示结束。但是，Java 语?中没有结束符这?概念。
11、什么是 Java 程序的主类 ？应?程序和?程序的主类有何不同?
?个程序中可以有多个类，但只能有?个类是主类。在 Java 应?程序中，这个主类是指包含main（）?法的类。?在 Java ?程序中，这个主类是?个继承?系统类 JApplet 或 Applet 的?类。应?程序的主类不?定要求是 public 类，但?程序的主类要求必须是 public 类。主类是 Java程序执?的??点。
12、下面一段代码会输出什么？
public class Main {
public static void main(String[] args) {
Integer i1 = 100;
Integer i2 = 100;
Integer i3 = 200;
Integer i4 = 200;
System.out.println(i1==i2);
System.out.println(i3==i4);
}
}
答：
true
false
查看源码：
public static Integer valueOf(int i) {
if(i >= -128 && i <= IntegerCache.high)
return IntegerCache.cache[i + 128];
else
return new Integer(i);
}
private static class IntegerCache {
static final int high;
static final Integer cache[];
static {
final int low = -128;
// high value may be configured by property
int h = 127;
if (integerCacheHighPropValue != null) {
// Use Long.decode here to avoid invoking methods that
// require Integer's autoboxing cache to be initialized
int i = Long.decode(integerCacheHighPropValue).intValue();
i = Math.max(i, 127);
// Maximum array size is Integer.MAX_VALUE
h = Math.min(i, Integer.MAX_VALUE - -low);
}
high = h;
cache = new Integer[(high - low) + 1];
int j = low;
for(int k = 0; k < cache.length; k++)
cache[k] = new Integer(j++);
}
private IntegerCache() {}
}
从这2段代码可以看出，在通过valueOf方法创建Integer对象的时候，如果数值在[-128,127]之间，便返回指向IntegerCache.cache中已经存在的对象的引用；否则创建一个新的Integer对象。上面的代码中i1和i2的数值为100，因此会直接从cache中取已经存在的对象，所以i1和i2指向的是同一个对象，而i3和i4则是分别指向不同的对象。
13、以下代码输出什么
public class Main {
public static void main(String[] args) {
Double i1 = 100.0;
Double i2 = 100.0;
Double i3 = 200.0;
Double i4 = 200.0;
System.out.println(i1==i2);
System.out.println(i3==i4);
}
}
答：
false
false
在某个范围内的整型数值的个数是有限的，而浮点数却不是。