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<TreeNode> stack = new Stack<TreeNode>(); 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<TreeNode> stack = new Stack<TreeNode>(); 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<TreeNode> stack = new Stack<TreeNode>(); 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<TreeNode> queue = new LinkedList<TreeNode>(); 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<TreeNode> queue = new LinkedList<TreeNode>(); 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 stub Tree 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()); } }
以后不断补充。。。