几个笔试题目总结

1、阿里某个笔试题，两个字符串text，query，找到text中包含的最长的query的字串：

public static String subStr(String text, String query) {if (text != null && query != null) {int length = query.length();for (int i = 0; i < length; i++) {for (int j = 0; j <= i; j++) {String sub = query.substring(j, length - i + j);if (text.contains(sub)) {return sub;}}}}return null;}

 

2、阿里某笔试题：找到一个二叉树中最大最小值对应节点的差值的绝对值，也就是节点所在层的差值，并不是本身数值的差值：

package mystudy;import java.io.UnsupportedEncodingException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;public class Tree {private TreeNode root;public Tree() {};public Tree(TreeNode root) {this.root = root;}public void initTree() {root = new TreeNode(8);root.setLeft(new TreeNode(5));root.getLeft().setLeft(new TreeNode(7));root.getLeft().setRight(new TreeNode(4));root.setRight(new TreeNode(9));root.getRight().setRight(new TreeNode(6));root.getRight().setLeft(new TreeNode(10));}public void preOrderTraverse() {preOrderTraverse(root);}public void preOrderTraverse(TreeNode node) {if (node != null) {System.out.println(node.getValue());preOrderTraverse(node.getLeft());preOrderTraverse(node.getRight());}}public void nPreOrderTraverse() {Stack stack = new Stack();TreeNode node = root;while (node != null || !stack.isEmpty()) {while (node != null) {System.out.println(node.getValue());stack.push(node);node = node.getLeft();}if (!stack.isEmpty()) {node = stack.pop();node = node.getRight();}}}public void inOrderTraverse() {inOrderTraverse(root);}public void inOrderTraverse(TreeNode node) {if (node != null) {inOrderTraverse(node.getLeft());System.out.println(node.getValue());inOrderTraverse(node.getRight());}}public void nInOrderTraverse() {Stack stack = new Stack();TreeNode node = root;while (node != null || !stack.isEmpty()) {while (node != null) {stack.push(node);node = node.getLeft();}if (!stack.isEmpty()) {node = stack.pop();System.out.println(node.getValue());node = node.getRight();}}}public void postOrderTraverse() {postOrderTraverse(root);}public void postOrderTraverse(TreeNode node) {if (node != null) {postOrderTraverse(node.getLeft());postOrderTraverse(node.getRight());System.out.println(node.getValue());}}public void nPostOrderTraverse() {Stack stack = new Stack();TreeNode node = root;TreeNode preNode = null;while (node != null || !stack.isEmpty()) {while (node != null) {stack.push(node);node = node.getLeft();}if (!stack.isEmpty()) {node = stack.peek();if (node.getRight() == null || node.getRight() == preNode) {node = stack.pop();System.out.println(node.getValue());preNode = node;node = null;} else {node = node.getRight();}}}}public void levelTraverse() {levelTraverse(root);}public void levelTraverse(TreeNode node) {if (node != null) {Queue queue = new LinkedList();queue.offer(node);while (!queue.isEmpty()) {TreeNode mNode = queue.poll();if (mNode != null) {System.out.println(mNode.getValue());if (mNode.getLeft() != null) {queue.offer(mNode.getLeft());}if (mNode.getRight() != null) {queue.offer(mNode.getRight());}}}}}public int treeDepth() {return treeDepth(root);}public int treeDepth(TreeNode node) {if (node == null) {return 0;}int leftDepth = treeDepth(node.getLeft());int rightDepth = treeDepth(node.getRight());return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;}public int minMaxSpan() {Queue queue = new LinkedList();if (root != null) {int visitedNum = 0, addedNum = 1, levelNum = 1, min, max, depth = 0, minLevel = 0, maxLevel = 0;min = max = root.getValue();queue.offer(root);while (!queue.isEmpty()) {TreeNode mNode = queue.poll();if (min > mNode.getValue()) {min = mNode.getValue();minLevel = depth;} else if (max < mNode.getValue()) {max = mNode.getValue();maxLevel = depth;}visitedNum++;if (mNode.getLeft() != null) {queue.offer(mNode.getLeft());addedNum++;}if (mNode.getRight() != null) {queue.offer(mNode.getRight());addedNum++;}if (visitedNum == levelNum) {depth++;levelNum = addedNum;}}System.out.println("min:" + min + "max:" + max + "minLevel:"+ minLevel + "maxLevel:" + maxLevel + "树的高度：" + depth);return Math.abs(minLevel - maxLevel);}return -1;}public class TreeNode {private TreeNode left;private TreeNode right;private int value;public TreeNode(TreeNode left, TreeNode right, int value) {this.left = left;this.right = right;this.value = value;}public TreeNode(int value) {this(null, null, value);}public TreeNode getLeft() {return left;}public void setLeft(TreeNode left) {this.left = left;}public TreeNode getRight() {return right;}public void setRight(TreeNode right) {this.right = right;}public int getValue() {return value;}public void setValue(int value) {this.value = value;}}/*** @param args* @throws UnsupportedEncodingException*/public static void main(String[] args) throws UnsupportedEncodingException {// TODO Auto-generated method stubTree tree = new Tree();tree.initTree();System.out.println("树中最大值最小值层数之差：" + tree.minMaxSpan());System.out.println("前序递归：");tree.preOrderTraverse();System.out.println("前序非递归：");tree.nPreOrderTraverse();System.out.println("中序递归：");tree.inOrderTraverse();System.out.println("中序非递归：");tree.nInOrderTraverse();System.out.println("后序递归：");tree.postOrderTraverse();System.out.println("后序非递归：");tree.nPostOrderTraverse();System.out.println("按层次遍历：");tree.levelTraverse();System.out.println("树的高度：" + tree.treeDepth());}}

以后不断补充。。。