LeetCode刷题笔记——《剑指Offer》面试题（6）

算法
, , ,

两个面试案例

把字符串转换成整数

思路：需要考虑的点有：

  1. 输入字符串为空的情况
  2. 带正负号的情况
  3. 字符串中存在非数字的情况
  4. 考虑Integer溢出的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int strToInt(String str) {
        int l = 0;
        char[] ch = str.toCharArray();
        while (l<ch.length && ch[l]==' ') l++;//找到第一个不为空的字符
        if (ch.length==l) return 0;//如果字符串为空，返回0
        int sign = 1;
        if (ch[l]=='-') sign = -1;
        if (ch[l]=='-'||ch[l]=='+') l++;//标记正负号
        int res = 0, bound = Integer.MAX_VALUE/10;//防止数值越界的边界
        for (int i=l; i<ch.length; i++) {
            if (ch[i]<'0'||ch[i]>'9') break;//出现非法字符，跳出
            //防止大数越界（-2147483648～2147483647）
            if (res>bound || (res==bound && ch[i]>'7')) {
                return sign>0?Integer.MAX_VALUE: Integer.MIN_VALUE;
            }
            res = res*10 + ch[i] - '0';
        }
        return sign*res;
    }
}

二叉搜索树的最近公共祖先

思路：二叉搜索树的左子节点小于根节点，右子节点大于根节点。如果根节点的值大于一个节点值而小于另一个节点值，那根节点就是所求的公共祖先。根据此性质递归求解。

1
2
3
4
5
6
7
8
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null || root==p || root==q) return root;
        if (p.val<root.val && q.val<root.val) return lowestCommonAncestor(root.left, p, q);
        if (p.val>root.val && q.val>root.val) return lowestCommonAncestor(root.right, p, q);
        return root;
    }
}

二叉树的最近公共祖先

思路：

  1. 如果root节点为空，返回null。
  2. 如果root节点为p或者q中的一个，返回其自身。
  3. 递归搜索root的左右节点。如果返回值为空，则表明p和q均不在这一侧的节点中，返回另一侧节点的搜索结果。
  4. 如果左右两侧返回的结果都为空，说明不存在公共祖先，返回null。
  5. 如果左右节点都有返回值，说明p和q分别在root的左右两侧，返回root。
1
2
3
4
5
6
7
8
9
10
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null || root==p || root==q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left==null) return right;
        if (right==null) return left;
        return root;
    }
}