剑指offer面试题 java解答46-50

面试题46：求1+2+3+…+n

public class Test46 { public static int sum = 0; public static boolean Sum_Solution(int n) { sum += n; return n != 1 && Sum_Solution(n - 1); } public static void main(String[] args) { Sum_Solution(100); System.out.println(Test46.sum); } }

面试题47：不用加减乘除做加法

public class Test47 { public static int Add(int num1,int num2){ int sum,carry; do { sum=num1^num2; carry=(num1&num2)<<1; num1=sum; num2=carry; } while (num2!=0); return sum; } public static void main(String[] args) { int sum=Add(5, 17); System.out.println(sum); } }

面试题48：不能被继承的类 Java中被final修饰的类不能被继承 面试题49：把字符串转换成整数

public class Test49 { public static int StrToInt(String s)throws NumberFormatException { if (s == null) { throw new NumberFormatException("null"); } int result = 0; boolean negative = false; int i = 0, len = s.length(); int limit = -Integer.MAX_VALUE; int digit=0; if (len > 0) { char firstChar = s.charAt(0); if (firstChar < '0') { // Possible leading "+" or "-" if (firstChar == '-') { negative = true; limit = Integer.MIN_VALUE; } else if (firstChar != '+') throw new NumberFormatException(s); if (len == 1) // Cannot have lone "+" or "-" throw new NumberFormatException(s); i++; } while (i < len) { if (s.charAt(i)>='0'&&s.charAt(i)<='9') { result *= 10; digit=s.charAt(i)-'0'; }else { throw new NumberFormatException(s); } if (result < limit + digit) { throw new NumberFormatException(s); } result -= digit; i++; } } else { throw new NumberFormatException(s); } return negative ? result : -result; } public static void main(String[] args) { int n=StrToInt("+367889"); System.out.println(n); } }

面试题50：树中两个结点的最低公共祖先

import java.util.Iterator; import java.util.LinkedList; import java.util.List; public class Test50 { private class Node<T> { public T value; public Node<T> lChild; public Node<T> rChild; public Node(T value) { this.value = value; } } public Node root = null; private int pos = 0; public <T> void creatBiTree(T[] value) { pos = 0; root = creatBiTree(root, value); } private <T> Node creatBiTree(Node node, T[] value) { T t = value[pos]; pos++; if (t == null) { return null; } else { node = new Node<T>(t); node.lChild = creatBiTree(node.lChild, value); node.rChild = creatBiTree(node.rChild, value); } return node; } public boolean GetNodePath(Node root, Node p, List<Node> list) { if (root == p) { list.add(root); return true; } list.add(root); boolean found = false; if (root.lChild != null) found = GetNodePath(root.lChild, p, list); if (!found && root.rChild != null) found = GetNodePath(root.rChild, p, list); if (!found) { list.remove(list.size() - 1); } return found; } public Node GetLastCommonParent(Node root, Node pNode1,Node pNode2){ if (root==null||pNode1==null||pNode2==null) { return null; } LinkedList<Node> path1=new LinkedList<Node>() ; LinkedList<Node> path2=new LinkedList<Node>() ; GetNodePath(root, pNode1, path1); GetNodePath(root, pNode2, path2); Iterator<Node> iterator1= path1.iterator(); Iterator<Node> iterator2= path2.iterator(); Node pLastNode=null; while (iterator1.hasNext()&&iterator2.hasNext()) { Node iterator1Node=iterator1.next(); Node iterator2Node=iterator2.next(); if (iterator1Node==iterator2Node) { pLastNode=iterator1Node; } } return pLastNode; } public static void main(String[] args) { Object[] a = {'A','B','D','F',null,null,'G',null,null,'E','H',null,null,'I',null, null,'C',null,null}; Test50 t = new Test50(); //以二叉树作为测试例子 t.creatBiTree(a); Node pNode1=t.root.lChild.lChild.lChild; Node pNode2=t.root.lChild.rChild.lChild; Node resultNode=t.GetLastCommonParent(t.root, pNode1, pNode2); System.out.println(resultNode.value); } }