面试题3：数组中重复的数字（长度为n的数组里，所有数字都在0~n-1的范围里）
方案1：先将数组排序，再从头到尾扫描排序后的数组，时间复杂度最少为O(nlogn)，空间复杂度为O(1)；
方案2：利用哈希表，从头到尾扫描每个数字，用O(1)的时间来判断哈希表中是否包含改数字，若没有则加入哈希表，时间复杂度为O(n)，空间复杂度为O(n)；
方案3：时间复杂度为O(n)，空间复杂度为O(1)。
public class test3 {
public static void main(String[] args){
int[] a = new int[]{2,3,1,0,2,5,3};
int j = 0;
while (j < a.length) {
i++;
if (a[j] == j) {
j++;
continue;
}
if (a[j] == a[a[j]])
System.out.println(a[j++]);
else exch(a, j, a[j]);
}
}
public static void exch(int[] a, int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
扩展问题：不修改数组找出重复的数字（长度为n+1的数组里所有数字都在1~n的范围里）
方案1：创建一个长度为n+1的辅助数组，因此空间复杂度为O(n)；
方案2：利用二分查找的思想，如果输入长度为n的数组，那么函数find将调用O(logn)次，每次需要O(n)的时间，因此总的时间复杂度为O(nlogn)，空间复杂度为O(1)，相当于用时间换空间。（注：该方法最多只能找出一个重复数字）
public class test3 {
public static void main(String[] args) {
int[] a = new int[]{2,3,5,4,3,2,6,7};
resolve(a, 1, a.length-1);
}
public static void resolve(int[] a, int lo, int hi){
while (lo < hi){
int mid = lo + (hi-lo)/2;
if (find(a,lo,mid) != mid-lo+1) hi = mid;
else lo = mid+1;
}
if (find(a,lo,hi) != 1)
System.out.println(lo);
}
public static int find(int[] a, int lo, int hi){
int time = 0;
for (int i = 0; i < a.length; i++){
if (lo<=a[i]&&a[i]<=hi)
time++;
}
return time;
}
}
面试题4：二维数组中的查找
public class test4 {
public static void main(String[] args) {
int[][] a = new int[][]{{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
int target = 7;
resolve(a, target);
}
public static void resolve(int[][] a, int target){
for (int j = a[0].length-1; j >= 0; j--){
if (a[0][j] <= target){
for (int i = 0; i < a.length; i++){
if (a[i][j] == target){
System.out.println("true");
return;
}
}
System.out.println("false");
return;
}
}
}
}
面试题5：替换空格
public class test5 {
public static void main(String[] args) {
String str = "We are happy.";
str = str.replaceAll(" ","%20");
System.out.println(str);
}
}
面试题6：从尾到头打印链表
方案1：利用栈先入后出的性质
import java.util.Stack;
public class test6 {
private static Node first;
private class Node{
Object item;
Node next;
}
public static void main(String[] args){
resolve(first);
}
public static void resolve(Node h){
Stack<Node> stack = new Stack<>();
while (h != null){
stack.push(h);
}
for (Node x: stack){
System.out.println(x.item);
}
}
}
方案2：使用递归，递归在本质上就是一个栈结构
import java.util.Stack;
public class test6 {
private static Node first;
private static class Node{
Object item;
Node next;
}
public static void main(String[] args){
resolve(first);
}
public static void resolve(Node first) {
if (first.equals(null)) return;
resolve(first.next);
System.out.println(first.item);
}
}
面试题7：重建二叉树（根据前序遍历和中序遍历重建二叉树）
public class test7 {
private static Node root;
private static class Node{
int item;
Node left, right;
public Node(int item){
this.item = item;
}
}
public static void main(String[] args){
int[] pre = new int[]{1,2,4,7,3,5,6,8};
int[] mid = new int[]{4,7,2,1,5,3,8,6};
root = resolve(pre,0, pre.length-1, mid, 0, mid.length-1);
}
public static Node resolve(int[] pre, int startpre, int endpre, int[] mid, int startmid, int endmid){
if (startpre > endpre || startmid > endmid) return null;
Node h = new Node(pre[startpre]);
for (int i = startmid; i <= endmid; i++){
if (pre[startpre] == mid[i]) {
h.left = resolve(pre, startpre+1, startpre+i-startmid, mid, startmid, i-1);
h.right = resolve(pre, startpre+i-startmid+1, endpre, mid, i+1, endmid);
}
}
return h;
}
}
扩展：二叉树的前序、中序、后序遍历的递归、循环实现\
面试题8：二叉树的下一个节点（树中的节点有左、右、父节点）
public class test8 {
public static Node h;
public static void main(String[] args) {
resolve(h);
}
public static void resolve(Node h) {
Node temp = h;
if (temp.right != null) {
temp = h.right;
while (temp.left != null) {
temp = temp.left;
}
System.out.println(temp.item);
return;
}
while (temp.parent != null) {
if (temp.equals(temp.parent.left)) {
System.out.println(temp.parent.item);
return;
}
else if (temp.equals(temp.parent.right)) {
temp = temp.parent;
}
}
System.out.println("null");
}
}
面试题9：用两个栈实现队列
import java.util.Stack;
public class test9{
private Stack<Integer> stack1 = new Stack<>();
private Stack<Integer> stack2 = new Stack<>();
public void enqueue(int item){
stack1.push(item);
}
public int dequeue(){
if (!stack2.isEmpty()) return stack2.pop();
else {
for (int temp: stack1){
stack2.push(temp);
}
return stack2.pop();
}
}
}
扩展：用两个队列实现栈
import java.util.LinkedList;
import java.util.Queue;
public class test9 {
Queue<Integer> queue1 = new LinkedList<>();
Queue<Integer> queue2 = new LinkedList<>();
public void push(int item) {
queue1.add(item);
}
public int pop() {
int temp = queue1.poll();
while (queue1.size() != 0) {
queue2.add(temp);
temp = queue1.poll();
}
return temp;
}
}
面试题10：斐波那契数列
方案1：运用递归的方法，但效率低下，例如求解f(10)，需要先求解f(9)和f(8)，而求解f(9)则需要求解f(8)和f(7)，很多节点的求解是重复的。
方案2：从下往上计算，首先根据f(0)和f(1)计算f(2)，再根据f(1)和f(2)计算f(3)，以此类推。该方法的时间复杂度为O(n)。
public class test10 {
public static void main(String[] args){
resolve(4);
}
public static void resolve(int N){
int a = 0, b = 1;
if (N == 1) b = 0;
for (int i = 2; i < N; i++){
int temp = a+b;
a = b;
b = temp;
}
System.out.println(b);
}
}
面试题11：旋转数组的最小数字
类似于二分查找，维护lo、hi、mid三个索引
public class test11 {
public static void main(String[] args){
int[] a = new int[]{3,4,5,1,2};
resolve(a);
}
public static void resolve(int[] a){
int lo = 0, hi = a.length-1;
if (a[lo] < a[hi]) {
System.out.println(a[lo]);
return;
}
while (a[lo] >= a[hi]){
if (hi - lo == 1){
System.out.println(a[hi]);
return;
}
int mid = lo + (hi-lo)/2;
if (a[lo] == a[mid] && a[mid] == a[lo]){
inorder(a, lo, hi);
return;
}
if (a[mid] >= a[lo])
lo = mid;
else if (a[mid] <= a[hi])
hi = mid;
}
}
public static void inorder(int[] a, int lo, int hi){
int min = a[lo];
for (int i = min; i <= hi; i++){
if (a[i] < min)
min = a[i];
}
System.out.println(min);
}
}
面试题12：矩阵中的路径
回溯法
public class test12 {
public static void main(String[] args){
char[][] matrix = new char[][]{{'a','b','t','g'},{'c','f','c','s'},{'j','d','e','h'}};
char[] str = new char[]{'b','f','c','e'};
resolve(matrix, str);
}
public static void resolve(char[][] matrix, char[] str){
int row = matrix.length, col = matrix[0].length;
boolean[][] marked = new boolean[row][col];
for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
if (hasPath(matrix, row, col, i, j, str, 0, marked)) {
System.out.println("true");
return;
}
}
}
System.out.println("false");
}
public static boolean hasPath(char[][] matrix, int row, int col, int i, int j, char[] str, int length, boolean[][] marked){
if (i<0||i>=row||j<0||j>=col||matrix[i][j]!=str[length]||marked[i][j]) {
return false;
}
if (length == str.length-1) return true;
marked[i][j] = true;
if(hasPath(matrix,row,col,i,j+1,str,length+1,marked)||hasPath(matrix,row,col,i-1,col,str,length+1,marked)
||hasPath(matrix,row,col,i+1,j,str,length+1,marked)||hasPath(matrix,row,col,i,j-1,str,length+1,marked))
return true;
marked[i][j] = false;
return false;
}
}
面试题13：机器人的运动范围
回溯法
public class test13 {
public static void main(String[] args){
int m = 10, n = 10, k = 5;
boolean[][] marked = new boolean[m][n];
System.out.println(resolve(m, n, k,0, 0, marked));
}
public static int resolve(int m, int n, int k, int i, int j, boolean[][] marked){
if (marked[i][j] || i >= m || j >= n || sum(i) + sum(j) > k) return 0;
marked[i][j] = true;
int result = 1;
result += resolve(m, n, k, i+1, j, marked) + resolve(m, n, k, i, j+1, marked);
return result;
}
public static int sum(int i){
int sum = 0;
while (i % 10 != 0){
sum += i % 10;
i = i/10;
}
return sum;
}
}
面试题14：剪绳子
public class test14 {
public static void main(String[] args){
int N = 8;
resolve(N);
}
public static void resolve(int N){
int[] dp = new int[N+1];
dp[0] = 1;
for (int i = 0; i <= N; i++){
dp[i] = max(dp, i);
}
System.out.println(dp[N]);
}
public static int max(int[] dp, int i){
int max = i;
for (int j = 1; j < i; j++){
max = Integer.max(max, dp[j]*(i-j));
}
return max;
}
}
面试题15：二进制中1的个数
如果将输入数字不断右移计算1的个数直至数字变为0，则当该数字为负数时会进入死循环。
public class test15 {
public static void main(String[] args){
System.out.println(NumberOf1(9));
}
public static int NumberOf1(int n) {
int count = 0;
while (n != 0){
count++;
n = n&(n-1);
}
return count;
}
}
面试题16：数值的整数次方
public class test16 {
public static void main(String[] args){
System.out.println(Power(0,-4));
}
public static double Power(double base, int exponent){
double result;
if (base == 0.0 && exponent < 0)
throw new RuntimeException("InvalidInput");
if (exponent == 0)
return 1.0;
if (exponent < 0)
result = 1/PowerWithUnsignedExponent(base, -exponent);
else result = PowerWithUnsignedExponent(base, exponent);
return result;
}
public static double PowerWithUnsignedExponent(double base, int exponent){
if (exponent == 0) return 1;
if (exponent == 1) return base;
double result = PowerWithUnsignedExponent(base, exponent/2);
result *= result;
if ((exponent & 0x1) == 1){
result *= base;
}
return result;
}
}
面试题17：打印从1到最大的n位数
需要考虑大数问题
方案1：用字符串或者数组表示大数
public class test17 {
public static void main(String[] args){
int N = 8;
resolve(N);
}
public static void resolve(int N){
char[] number = new char[N];
for (int i = 0; i < number.length; i++){
number[i] = '0';
}
PrintNumber(number);
while (!Increment(number)){
PrintNumber(number);
}
}
public static boolean Increment(char[] number){
boolean isOverflow = false;
int takeover = 0;
for (int i = 0; i < number.length; i++ ){
if (number[i] == '9' && takeover==i) {
number[i] = '0';
takeover++;
}
else if (takeover == i){
number[i] += 1;
}
}
if (takeover == number.length){
isOverflow = true;
}
return isOverflow;
}
public static void PrintNumber(char[] number){
boolean flag = false;
for (int i = number.length-1; i >= 0; i--){
if (number[i] != '0' || i == 0)
flag = true;
if (flag) System.out.print(number[i]);
}
System.out.println();
}
}
方案2：把问题转换成数字排列的解法
递归法
public class test17 {
public static void main(String[] args) {
int N = 3;
char[] num = new char[N];
for (int i = 0; i < N; i++) {
num[i] = '0';
}
generate(num, N-1, false);
}
public static void generate(char[] num, int index, boolean flag) {
if (index < 0) {
return;
}
for (int i = 0; i <= 9; i++) {
num[index] = (char)('0'+i);
if (i != 0) {
print(num);
}
generate(num, index-1, true);
if (i == 9) {
num[index] = '0';
}
}
}
public static void print(char[] num) {
boolean flag = false;
for (int i = num.length-1; i >= 0; i--) {
if (num[i] == '0' && !flag && i == 0) {
System.out.println('0');
return;
}
if (num[i] == '0' && !flag) {
continue;
}
flag = true;
System.out.print(num[i]);
}
System.out.println();
}
}
面试题18：删除链表的节点
题目一：在O(1)时间内删除链表节点
删除节点n的方法为：将n+1节点的内容复制到n节点，再把节点n节点的next指向n+2节点，最后删除n+1节点，这样就不用遍历链表上节点n前面的节点。
public class test18 {
private static Node first;
private static class Node{
Object item;
Node next;
}
public static void main(String[] args){
Node h = new Node();
delete(h);
}
public static void delete(Node h){
if (h == null || first ==null) return;
if (h == first) first = null;
else if (h.next == null) {
Node current = first;
while (current.next != h){
current = current.next;
}
current.next = null;
}
else {
h.item = h.next.item;
h.next = h.next.next;
}
}
}
题目二：删除链表中重复的节点
public class test18 {
private static Node first;
private static class Node{
Object item;
Node next;
}
public static void main(String[] args){
deleteRepeat();
}
public static void deleteRepeat(){
if (first == null) return;
Node current = first;
while (current != null){
if (current.item == current.next.item){
Node t = current.next;
Object val = current.next.item;
while (t.next.item == val){
t = t.next;
}
current.item = t.next.item;
current.next = t.next.next;
}
current = current.next;
}
}
}
面试题19：正则表达式匹配
public class test19 {
public static void main(String[] args){
char[] pattern1 = new String("a.a").toCharArray();
char[] pattern2 = new String("ab*ac*a").toCharArray();
char[] str = new String("aaa").toCharArray();
match(str, pattern1);
match(str, pattern2);
}
public static void match(char[] str, char[] pattern){
if (str == null || pattern == null) return;
System.out.println(matchCore(str, 0, pattern, 0));
}
public static boolean matchCore(char[] str, int s, char[] pattern, int p){
if (s >= str.length && p >= pattern.length) return true; //模式串和字符串都匹配完了
if (s < str.length && p >= pattern.length) return false; //模式串完了，但字符串还有
//只要模式串还有字符匹配完，匹配过程就还没结束
if (p+1<pattern.length && pattern[p+1]=='*'){ //当前模式串的下一个字符是*时
if (s >= str.length) return matchCore(str, s, pattern, p+2); //字符串结束了
else {
if (pattern[p]==str[s] || pattern[p]=='.'){
return matchCore(str, s+1, pattern, p+2) || //匹配上*前的字符
matchCore(str, s+1, pattern, p) || //多次匹配上*前的字符
matchCore(str, s, pattern, p+2); //跳过*前的字符
}
else
return matchCore(str, s, pattern, p+2);
}
}
if (s==str.length) return false; //模式串还有字符没有匹配完，且字符非*，而字符串已经匹配完了时说明匹配失败
else if (str[s] == pattern[p] || pattern[p] == '.') //如果模式串下一个字符非*，但当前模式串和字符串匹配上则同时继续
return matchCore(str, s+1, pattern, p+1); //如果模式串下一个字符非*，且当前模式串和字符串匹配不上说明匹配失败
return false;
}
}
面试题20：表示数值的字符串
public class test20 {
static int inx;
public static void main(String[] args){
char[] str = new String("-1.4E-16").toCharArray();
System.out.println(isNumber(str));
}
public static boolean isNumber(char[] str){
if (str == null) return false;
boolean flag = scanInteger(str);
//判断小数部分
if (inx<str.length && str[inx]=='.'){
inx++;
flag = scanUnInteger(str)||flag;
}
//判断指数部分
if (inx<str.length && (str[inx]=='e') || str[inx]=='E'){
inx++;
flag = flag && scanInteger(str);
}
return flag && inx>=str.length;
}
//去掉符号
public static boolean scanInteger(char[] str){
if (inx<str.length && (str[inx]=='+' || str[inx]=='-')){
inx++;
}
return scanUnInteger(str);
}
//判断是否是无符号整数
public static boolean scanUnInteger(char[] str){
int inx1 = inx;
while (inx<str.length && str[inx]>='0' && str[inx]<='9'){
inx++;
}
return inx>inx1;
}
}
面试题21：调整数组顺序使奇数位于偶数前面
方案1：维护两个索引，分别寻找偶数和奇数，找到后交换位置
public class test21 {
public static void main(String[] args){
int[] a = new int[]{1,3,5,2,4};
resolve(a);
}
public static void resolve(int[] a){
if (a == null) return;
int lo = 0, hi = a.length-1;
while (lo < hi){
while (a[lo]%2!=0 && lo<hi){
lo++;
}
while (a[hi]%2==0 && lo<hi){
hi--;
}
exch(a,lo,hi);
}
for (int i = 0; i < a.length; i++){
System.out.println(a[i]);
}
}
public static void exch(int[] a, int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
方案2：将代码中的两处判断抽象出来成为一个进行逻辑判断的函数
public class test21 {
public static void main(String[] args){
int[] a = new int[]{1,3,5,2,4};
resolve(a);
}
public static void resolve(int[] a){
if (a == null) return;
int lo = 0, hi = a.length-1;
while (lo < hi){
while (fun(a,lo) && lo<hi){
lo++;
}
while (!fun(a,hi) && lo<hi){
hi--;
}
exch(a,lo,hi);
}
for (int i = 0; i < a.length; i++){
System.out.println(a[i]);
}
}
public static void exch(int[] a, int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static boolean fun(int[] a, int k){
return a[k]%2 != 0;
}
}
面试题22：链表中倒数第k个节点
维护两个链表头节点的链接，当第一个链接遍历链表直到第k个节点时，第二个链接也开始遍历。这样当第一个链接遍历到最后一个节点时，第二个链接就遍历到倒数第k个节点。此外，该方法还需要考虑到三个会导致程序崩溃的问题：1、输入的链表为空；2、输入的链表长度小于k；3、输入的k为0时，k-1为0xFFFFFFFF。
public class test22 {
private static class Node{
Object item;
Node next;
}
public static void main(String[] args){
int k = 3;
Node first = new Node();
resolve(first, k);
}
public static void resolve(Node first, int k){
if (first == null || k <= 0) return;
Node current1 = first;
Node current2 = first;
for (int i = 0; i < k-1; i++){
if (current1.next == null) return;
current1 = current1.next;
}
while (current1.next != null){
current1 = current1.next;
current2 = current2.next;
}
System.out.println(current2);
}
}
面试题23：链表中环的入口节点
public class test23 {
private static class Node{
Object item;
Node next;
}
public static void main(String[] args){
Node first = new Node();
Node entry;
Node h = meetingNode(first);
if (h != null) entry = entryNode(first, h);
}
public static Node meetingNode(Node first){
if (first == null) return null;
Node current1 = first;
Node current2 = first;
while (current1.next != null && current1.next.next != null){
current1 = current1.next.next;
current2 = current2.next;
if (current1 == current2)
return current1;
}
return null;
}
public static Node entryNode(Node first, Node h){
Node current = h.next;
int count = 1;
while (current != h){
count++;
current = current.next;
}
Node current1 = first;
Node current2 = first;
for (int i = 0; i < count; i++){
current1 = current1.next;
}
while (current1 != current2){
current1 = current1.next;
current2 = current2.next;
}
return current1;
}
}
面试题24：反转链表
public class test24 {
private static class Node{
Object item;
Node next;
}
public static void main(String[] args){
Node first = new Node();
reverse(first);
}
public static void reverse(Node first){
if (first == null) return;
Node current = first;
Node pre = null;
Node post = null;
while (current.next != null){
post = current.next;
current.next = pre;
pre = current;
current = post;
}
if (Head == null) Head = first;
System.out.print(Head);
}
}
面试题25：合并两个排序的链表
public class test25 {
public static class Node{
Comparable item;
Node next;
}
public static void main(String[] args){
Node a = new Node();
Node b = new Node();
Node c = Compare(a, b);
}
public static Node Compare(Node a, Node b){
if (a == null && b == null) return null;
Node currenta = a;
Node currentb = b;
Node c = null;
while (true){
if (currenta == null && currentb == null) break;
if (currenta == null && currentb != null){
if (c == null) c = currentb;
else c.next = currentb;
currentb = currentb.next;
}
else if (currentb == null && currenta != null){
if (c == null) c = currenta;
else c.next = currenta;
currenta = currenta.next;
}
else if (currenta.item.compareTo(currentb.item) < 0){
if (c == null) c = currenta;
else c.next = currenta;
currenta = currenta.next;
}
else {
if (c == null) c = currentb;
else c.next = currentb;
currentb = currentb.next;
}
}
return c;
}
}
也可以用递归的角度看这题
public class test25 {
public static class Node{
Comparable item;
Node next;
}
public static void main(String[] args){
Node a = new Node();
Node b = new Node();
Node c = merge(a, b);
}
public static ListNode merge(Node node1, Node node2) {
if (node1 == null || node2 == null) {
return node1==null?node2:node1;
}
Node current = null;
if (node1.getValue() <= node2.getValue()) {
current = node1;
current.setNext(merge(node1.getNext(), node2));
}
else {
current = node2;
current.setNext(merge(node1, node2.getNext()));
}
return current;
}
}
面试题26：树的子结构
public class test26 {
private static class Node{
Comparable item;
Node left, right;
}
public static void main(String[] args){
Node A = new Node();
Node B = new Node();
System.out.println(Judge(A,B));
}
public static boolean Judge(Node A, Node B){
if (A == null || B == null) return false;
boolean result = false;
int cmp = B.item.compareTo(A.item);
if (cmp == 0){
result = hasSubTree(A, B);
}
if (!result){
result = Judge(A.left, B) || Judge(A.right, B);
}
return result;
}
public static boolean hasSubTree(Node A, Node B){
if (B == null) return true;
if (A == null) return false;
int cmp = A.item.compareTo(B.item);
if (cmp != 0) return false;
else {
return hasSubTree(A.left, B.left) && hasSubTree(A.right, B.right);
}
}
}
面试题27：二叉树的镜像
public class test27 {
private static class Node{
int item;
Node left, right;
}
public static void main(String[] args){
Node a = new Node();
a = reverse(a);
}
public static Node reverse(Node a){
if (a == null) return null;
Node temp = reverse(a.left);
a.left = reverse(a.right);
a.right = temp;
return a;
}
}
面试题28：对称的二叉树
public class test28 {
private static class Node{
Comparable item;
Node left, right;
}
public static void main(String[] args){
Node a = new Node();
System.out.println(resolve(a, a));
}
public static boolean resolve(Node a, Node b){
if (a == null && b == null){
return true;
}
if (a == null || b == null){
return false;
}
if (!a.item.equals(b.item)){
return false;
}
return resolve(a.left, b.right) && resolve(a.right, b.left);
}
}
面试题29：顺时针打印矩阵
public class test29 {
public static void main(String[] args){
int[][] a={{1,2,3,4},{5,6,7,8},{9,10,11,12}};
Print(a);
}
public static void Print(int[][] a){
if (a == null) return;
int start = 0;
while (a[0].length > start*2 && a.length > start*2){
printCircle(a, start);
start++;
}
}
public static void printCircle(int[][] a, int start){
int row = a.length;
int col = a[0].length;
int endX = col - 1 - start;
int endY = row - 1 - start;
for (int i = start; i <= endX; i++){
System.out.println(a[start][i]);
}
if (start < endY){
for (int i = start+1; i <= endY; i++){
System.out.println(a[i][endX]);
}
}
if (start < endX && start < endY){
for (int i = endX-1; i >= start; i--){
System.out.println(a[endY][i]);
}
}
if (start < endX && start < endY-1){
for (int i = endY-1; i>= start+1; i--){
System.out.println(a[i][start]);
}
}
}
}
面试题30：包含min函数的栈
public class test30 {
public class Stack<Item extends Comparable<Item>>{
public Node first;
public int N;
private class Node{
Item item;
Node next;
}
public void push(Item item){
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
N++;
}
public Item pop(){
if (first == null) return null;
Item item = first.item;
first = first.next;
N--;
return item;
}
}
public class MyStack<Item extends Comparable<Item>>{
Stack<Item> stack1 = new Stack<>();
Stack<Item> stack2 = new Stack<>();
public void push(Item item){
stack1.push(item);
if (stack2.first == null || item.compareTo(stack2.first.item) < 0) stack2.push(item);
else stack2.push(stack2.first.item);
}
public Item pop(){
if (stack1.first == null || stack2.first == null) return null;
stack2.pop();
return stack1.pop();
}
public Item min(){
if (stack2.first == null) return null;
return stack2.first.item;
}
}
}
面试题31：栈的压入、弹出序列
import java.util.Stack;
public class test31 {
public static void main(String[] args){
int[] ori = new int[]{1,2,3,4,5};
int[] test = new int[]{4,3,5,1,2};
System.out.println(resolve(ori, test));
}
public static boolean resolve(int[] ori, int[] test){
if (ori == null || test == null) return false;
Stack<Integer> stack = new Stack<>();
int index1 = 0, index2 = 0;
while (true){
if (index2 == test.length-1) return true;
else if (index1 == ori.length) index1--;
if (ori[index1] == test[index2]){
index1++;
index2++;
}
else if (ori[index1] != test[index2]){
if (stack.isEmpty() || test[index2] != stack.peek()){
if (index1+1 == ori.length) return false;
stack.push(ori[index1++]);
}
else if (!stack.isEmpty() && test[index2] == stack.peek()){
stack.pop();
index2++;
}
}
}
}
}
面试题32：从上到下打印二叉树
树其实是图的一种退化形式，因此从上到下分层遍历二叉树，从本质上来说就是图的广度优先搜索。
import java.util.LinkedList;
import java.util.Queue;
public class test32 {
public class Node{
Object item;
Node left, right;
}
public void levelPrint(Node h){
if(h == null) return;
Queue<Node> queue = new LinkedList<>();
queue.add(h);
while (!queue.isEmpty()){
Node temp = queue.poll();
System.out.println(temp.item);
if (temp.left != null) queue.add(temp.left);
if (temp.right != null) queue.add(temp.right);
}
}
}
扩展问题：分行从上到下打印二叉树
多维护两个变量，nextLevel记录下一层公有多少个节点，toPrint记录当前层还有多少个节点没有打印，每打印完一个节点toPrint减1。当toPrint为0即当前层打印完时，nextLevel的值就是下一层的节点数，并赋给toPrint，nextLevel清0。
import java.util.LinkedList;
import java.util.Queue;
public class test32 {
public class Node{
Object item;
Node left, right;
}
public void levelPrint(Node h){
if(h == null) return;
Queue<Node> queue = new LinkedList<>();
int nextLevel = 0;
int toPrint = 1;
queue.add(h);
while (!queue.isEmpty()){
Node temp = queue.poll();
System.out.printf("%d ", temp.item);
if (temp.left != null) {
queue.add(temp.left);
++nextLevel;
}
if (temp.right != null){
queue.add(temp.right);
++nextLevel;
}
toPrint--;
if (toPrint == 0){
System.out.println();
toPrint = nextLevel;
nextLevel = 0;
}
}
}
}
扩展问题：之字形打印二叉树
用栈来解决，但如果只有一个栈，会出现下一层比当前层先打印的情况，因此要维护两个栈，分别存放当前层节点和下一层节点，并用变量记录当前层的奇偶性，每当当前层打印完即当前栈空时，便转换到另一个栈打印。
import java.util.Stack;
public class test32 {
public class Node{
Object item;
Node left, right;
}
public void levelPrint(Node h){
if (h == null) return;
Stack<Node> stack1 = new Stack<>();
Stack<Node> stack2 = new Stack<>();
stack1.add(h);
int nextLevel = 0;
int toPrint = 1;
boolean flag = false;
while (!stack1.isEmpty() || !stack2.isEmpty()) {
Stack<Node> full = flag?stack2:stack1;
Stack<Node> empty = flag?stack1:stack2;
Node temp = full.pop();
toPrint--;
System.out.print(temp.item+" ");
if (!flag) {
if (temp.left != null) {
empty.add(temp.left);
nextLevel++;
}
if (temp.right != null) {
empty.add(temp.right);
nextLevel++;
}
}
else {
if (temp.right != null) {
empty.add(temp.right);
nextLevel++;
}
if (temp.left != null) {
empty.add(temp.left);
nextLevel++;
}
}
if (toPrint == 0) {
System.out.println();
toPrint = nextLevel;
nextLevel = 0;
flag = !flag;
}
}
}
}
面试题33:二叉搜索树的后序遍历序列
public class test33 {
public static void main(String[] args){
int[] a = new int[]{5,7,6,9,11,10,8};
System.out.println(judge(a, 0, a.length-1));
}
public static boolean judge(int[] a, int start, int end){
if (a == null || start > end) return false;
if (start == end) return true;
int mid = start;
for (int i = start; i <= end; i++){
if (a[i] >= a[end]){
mid = i;
break;
}
}
if (judge(a,start,mid-1) && judge(a,mid,end-1)) return true;
else return false;
}
}
