第七章 两个面试案例

时间:2021-12-06 04:24:17

7.1 案例一
 
面试题49:把字符串转换成整数
  • 题目:将一个字符串转换成一个整数,要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法 的数值则返回0
  • 思路:若为负数,则输出负数,字符0对应48,9对应57,不在范围内则返回false。
  • 代码实现
    • public class TestMain {
    • public static void main(String[] args) {
    • TestMain t = new TestMain();
    • System.out.println(t.StrToInt("12"));
    • }
    • public int StrToInt(String str) {
    • if (str == null || str.length() == 0)
    • return 0;
    • int mark = 0;
    • int start = 0;
    • int number = 0;
    • char[] chars = str.toCharArray();
    • if (chars[0] == '-') {
    • mark = 1;
    • start = 1;
    • } else if (chars[0] == '+') {
    • start = 1;
    • }
    • for (int i = start; i < chars.length; i++) {
    • if (chars[i] < 48 || chars[i] > 57) {
    • return 0;
    • }
    • number = number * 10 + chars[i] - 48;
    • }
    • return mark == 0 ? number : -number;
    • }
    • }
  • 测试用例:
    • 功能测试(输入的字符串表示正数、负数和0)。
    • 边界值测试(最大的正整数、最小的负整数)。
    • 特殊输入测试(输入字符串为NULL指针、输入字符串为空字符串、输入的字符串中有非数字字符等)。
 
面试题50:树中两个节点的最低公共祖先
  • 题目:求树中两个节点的最低公共祖先
  • (1)树是二叉搜索树
  • 思路:从树的根节点开始遍历,如果根节点的值大于其中一个节点,小于另外一个节点,则根节点就是最低公 共祖先。否则如果根节点的值小于两个节点的值,则递归求根节点的右子树,如果大于两个节点的值则递归求 根的左子树。如果根节点正好是其中的一个节点,那么说明这两个节点在一条路径上,所以最低公共祖先则是 根节点的父节点,时间复杂度是O(logn),空间复杂度是O(1)
  • 代码实现
    • class TreeNode {
    • public int value;
    • public TreeNode left;
    • public TreeNode right;
    • public TreeNode(int value) {
    • this.value = value;
    • }
    • public TreeNode() {
    • }
    • }
    • public class TestTree {
    • public static int n;
    • ArrayList<ArrayList<Integer>> resultList = new ArrayList<ArrayList<Integer>>();
    • ArrayList<Integer> list = new ArrayList<Integer>();
    • public static void main(String[] args) {
    • int[] array = new int[] { 7,1,0,3,2,0,0,5,0,0,8,0,9,0,0};
    • TestTree t = new TestTree();
    • TreeNode root = t.CreateTreeBinary(new TreeNode(), array);
    • System.out.println(t.getLowestCommonAncestor(root, root, new TreeNode(2), new TreeNode(5)).value);
    • }
    • public TreeNode CreateTreeBinary(TreeNode treeNode, int[] array) {
    • if (array[n] == 0) {
    • n++;
    • return null;
    • } else {
    • treeNode.value = array[n++];
    • treeNode.left = CreateTreeBinary(new TreeNode(0), array);
    • treeNode.right = CreateTreeBinary(new TreeNode(0), array);
    • return treeNode;
    • }
    • }
    • public static TreeNode getLowestCommonAncestor(TreeNode rootParent, TreeNode root,
    • TreeNode node1, TreeNode node2) {
    • if (root == null || node1 == null || node2 == null) {
    • return null;
    • }
    • if ((root.value - node1.value) * (root.value - node2.value) < 0) {
    • return root;
    • } else if ((root.value - node1.value) * (root.value - node2.value) > 0) {
    • TreeNode newRoot = ((root.value > node1.value) && (root.value > node2.value)) ? root.left
    • : root.right;
    • return getLowestCommonAncestor(root, newRoot, node1, node2);
    • } else {
    • return rootParent;
    • }
    • }
    • }
 
  • (2)若树是普通树,但有指向父节点的指针
  • 思路:两个节点如果在两条路径上,类似于求两个链表的第一个公共节点。由于每个节点的深度最多为logn,所以时间复杂度为O(logn),空间复杂度O(1)
  • 思路二:循环两次 第一次长度差 第二次求值
  • 代码实现
    • public BinaryTreeNode getLowestCommonAncestor1(BinaryTreeNode root, BinaryTreeNode node1, BinaryTreeNode node2) {
    • if (root == null || node1 == null || node2 == null) {
    • return null;
    • }
    • int depth1 = findTheDepthOfTheNode(root, node1, node2);
    • if (depth1 == -1) {
    • return node2.parentNode;
    • }
    • int depth2 = findTheDepthOfTheNode(root, node2, node1);
    • if (depth2 == -1) {
    • return node1.parentNode;
    • }
    • // p指向较深的节点q指向较浅的节点
    • BinaryTreeNode p = depth1 > depth2 ? node1 : node2;
    • BinaryTreeNode q = depth1 > depth2 ? node2 : node1;
    • int depth = Math.abs(depth1 - depth2);
    • while (depth > 0) {
    • p = p.parentNode;
    • depth--;
    • }
    • while (p != q) {
    • p = p.parentNode;
    • q = q.parentNode;
    • }
    • return p;
    • }
    • // 求node1的深度,如果node1和node2在一条路径上,则返回-1,否则返回node1的深度
    • public int findTheDepthOfTheNode(BinaryTreeNode root, BinaryTreeNode node1, BinaryTreeNode node2) {
    • int depth = 0;
    • while (node1.parentNode != null) {
    • node1 = node1.parentNode;
    • depth++;
    • if (node1 == node2) {
    • return -1;
    • }
    • }
    • return depth;
    • }
  • (3)若树是普通树,并没有指向父节点的指针
  • 思路:用栈来实现类似于指向父节点指针的功能,获取node节点的路径时间复杂度为O(n),所以总的时间复杂度是O(n),空间复杂度是O(logn)
  • 代码实现
    • public BinaryTreeNode getLowestCommonAncestor2(BinaryTreeNode root, BinaryTreeNode node1, BinaryTreeNode node2) {
    • if (root == null || node1 == null || node2 == null) {
    • return null;
    • }
    • Stack<BinaryTreeNode> path1 = new Stack<BinaryTreeNode>();
    • boolean flag1 = getThePathOfTheNode(root, node1, path1);
    • if (!flag1) {// 树上没有node1节点
    • return null;
    • }
    • Stack<BinaryTreeNode> path2 = new Stack<BinaryTreeNode>();
    • boolean flag2 = getThePathOfTheNode(root, node2, path2);
    • if (!flag2) {// 树上没有node2节点
    • return null;
    • }
    • if (path1.size() > path2.size()) { // 让两个路径等长
    • while (path1.size() != path2.size()) {
    • path1.pop();
    • }
    • } else {
    • while (path1.size() != path2.size()) {
    • path2.pop();
    • }
    • }
    • if (path1 == path2) {// 当两个节点在一条路径上时
    • path1.pop();
    • return path1.pop();
    • } else {
    • BinaryTreeNode p = path1.pop();
    • BinaryTreeNode q = path2.pop();
    • while (q != p) {
    • p = path1.pop();
    • q = path2.pop();
    • }
    • return p;
    • }
    • }
    • // 获得根节点到node节点的路径
    • public boolean getThePathOfTheNode(BinaryTreeNode root, BinaryTreeNode node, Stack<BinaryTreeNode> path) {
    • path.push(root);
    • if (root == node) {
    • return true;
    • }
    • boolean found = false;
    • if (root.leftNode != null) {
    • found = getThePathOfTheNode(root.leftNode, node, path);
    • }
    • if (!found && root.rightNode != null) {
    • found = getThePathOfTheNode(root.rightNode, node, path);
    • }
    • if (!found) {
    • path.pop();
    • }
    • return found;
    • }