算法笔试题记录

将字符串转换为整数，如果没有合法则返回0. 

例如：
“10”->10
“-1”->-1
“1.0”->1
“1asdf”->0
“123948111111111111”->2147483647(最大整数)
“-123948111111111111”->-2147483647（最小负整数）

 public static Integer IntegerValue(String input,int radix) {
        int i = 0;
        int len = input.length();
        char ch = input.charAt(i);
        boolean negative = false;
        int dotIndex = -1;
        if (ch == '-') {
            negative = true;
        }
        Integer result = 0;
        //检查是否合法整数
        while (i < len-1) {
            i++;
            ch = input.charAt(i);
            int in = Character.digit(ch, radix);
            if (ch == '.') {
                if (dotIndex < 0) {
                    dotIndex = i;
                    continue;
                } else {
                    return result;
                }
            }
            if (in < 0 || in > 9) {
                return result;
            }
        }
        //找到小数点
        if (dotIndex > 0) {
            input = input.substring(0, dotIndex);
        }
        //转换整数
        for (int j = 0; j < input.length(); j++) {
            if (j==0&&negative) {
                continue;
            }
            int nu = Character.digit(input.charAt(j), 10);
            result *= radix;
            if(result>Integer.MAX_VALUE/radix){
                result=Integer.MAX_VALUE;
                break;
            }
            else {
                result+=nu;
            }
        }
        return negative ? -result : result;
    }

二叉树 遍历 根、中、后、层序遍历

public  class BinaryNode<AnyType> {
    BinaryNode(AnyType theElement) {
        this(theElement, null, null);
    }
    BinaryNode(AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt) {
        element = theElement;
        left = lt;
        right = rt;
    }
    AnyType element;
    BinaryNode<AnyType> left;
    BinaryNode<AnyType> right;
}


public class BinaryOrder {

    private BinaryNode<Integer> root;

    public void insert(Integer x) {
        root = insert(x, root);
    }

    private BinaryNode<Integer> insert(Integer x, BinaryNode<Integer> t) {
        if (t == null) {
            return new BinaryNode(x, null, null);
        }

        int compareResult = x.compareTo(t.element);

        if (compareResult < 0) {
            t.left = insert(x, t.left);
        } else if (compareResult > 0) {
            t.right = insert(x, t.right);
        } else {
            ;
        }
        return t;
    }

    /**
     * 前序遍历
     */
    public void preOrder(BinaryNode<Integer> Node) {
        if (Node != null) {
            System.out.print(Node.element + " ");
            preOrder(Node.left);
            preOrder(Node.right);
        }
    }

    /**
     * 中序遍历
     */
    public void midOrder(BinaryNode<Integer> Node) {
        if (Node != null) {
            midOrder(Node.left);
            System.out.print(Node.element + " ");
            midOrder(Node.right);
        }
    }

    /**
     * 后序遍历
     */
    public void posOrder(BinaryNode<Integer> Node) {
        if (Node != null) {
            posOrder(Node.left);
            posOrder(Node.right);
            System.out.print(Node.element + " ");
        }
    }

    /*
     * 层序遍历
     * 递归
     */
    public void levelOrder(BinaryNode<Integer> Node) {
        if (Node == null) {
            return;
        }

        int depth = depth(Node);

        for (int i = 1; i <= depth; i++) {
            levelOrder(Node, i);
        }
    }

    private void levelOrder(BinaryNode<Integer> Node, int level) {
        if (Node == null || level < 1) {
            return;
        }

        if (level == 1) {
            System.out.print(Node.element + "  ");
            return;
        }

        // 左子树
        levelOrder(Node.left, level - 1);

        // 右子树
        levelOrder(Node.right, level - 1);
    }

    public int depth(BinaryNode<Integer> Node) {
        if (Node == null) {
            return 0;
        }

        int l = depth(Node.left);
        int r = depth(Node.right);
        if (l > r) {
            return l + 1;
        } else {
            return r + 1;
        }
    }

    public static void main(String[] args) {
        int[] input = {4, 2, 6, 1, 3, 5, 7, 8, 10};
        BinaryOrder tree = new BinaryOrder();
        for (int i = 0; i < input.length; i++) {
            tree.insert(input[i]);
        }
        System.out.print("前序遍历 ：");
        tree.preOrder(tree.root);
        System.out.print("\n中序遍历 ：");
        tree.midOrder(tree.root);
        System.out.print("\n后序遍历 ：");
        tree.posOrder(tree.root);
        System.out.print("\n递归层序遍历：");
        tree.levelOrder(tree.root);
    }
}

结果：

前序遍历 ：4 2 1 3 6 5 7 8 10 
中序遍历 ：1 2 3 4 5 6 7 8 10 
后序遍历 ：1 3 2 5 10 8 7 6 4 
递归层序遍历：4  2  6  1  3  5  7  8  10  Disconnected from the target VM, address: '127.0.0.1:57491', transport: 'socket'

查找最大重复字符串

public class MaxRepeatStr {

        // 求解字符串中的最长重复子串
        public static String maxRepat(String input) {
            // 参数检查
            if (input == null || input.length() == 0) {
                return null;
            }
            // 重复子串的最长长度
            int max = 0;
            // 最长重复子串的起始位置
            int first = 0;
            int k = 0;
            for (int i = 1; i < input.length(); i++) {
                for (int j = 0; j < input.length() - i; j++) {
                    if (input.charAt(j) == input.charAt(i + j)) {
                        k++;
                    } else {
                        k = 0;
                    }
                    if (k > max) {
                        max = k;
                        first = j - k + 1;
                    }
                }
            }
            if (max > 0) {
                System.out.println(max);
                return input.substring(first, first + max);
            }
            return null;
        }


        public static String maxRepeat(String input){
            int first = 0, max = 0, k = 0;
            for (int i = 0; i < input.length(); i++) {
                for (int j = i + 1; j < input.length(); j++) {
                    if (input.charAt(j - i - 1) == input.charAt(j)) {
                        k++;
                    }
                    else {
                        k=0;
                    }
                    if (k > max) {
                        max = k;
                        first = j - k + 1;
                    }
                }
            }

            if (max > 0) {
                System.out.println(max);
                return input.substring(first, first + max);
            }
            return null;
        }
        public static void main(String[] args) {
            String str1 = "abcdababc";
            System.out.println("max:"+ maxRepat(str1));
            System.out.println("maxRepeat:"+maxRepeat(str1));
        }

}

有n个台阶（n>=2）,每次上1个或者2个台阶，问有多少种上楼梯方法？

斐波那契数列

public static int fn(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        return fn(n - 1) + fn(n - 2);
    }

  public static void remove7() {
        Integer [] nums=new Integer[100];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = i;
            System.out.println("index:"+i+",value:"+nums[i]);
        }
        int k=0;
        for (int i = 0; i < nums.length-k; i++) {
            if (i != 0 & i % 7 == 0) {
                k++;
            }
            if (k > 0) {
                nums[i] = nums[i + k];
            }
        }
        if(k>0){
            for(int i=1;i<=k;i++){
                nums[nums.length-i]=null;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            System.out.println("index:"+i+",value:"+nums[i]);
        }
    }

给定一个正数数字组，求所有相邻数字ip段组合。

分析：ip有4个段组成，每个段最大值不超过255.

 public static void segment(int index, Integer[] arr, int segment, String ipStr) {
        int end = index + 3;
        Integer ip=0;
        for (int i = index; i <end&&i<arr.length; i++) {
            ip = ip*10+ arr[i];
            String seg = ipStr.length()==0?String.valueOf(ip):ipStr+"."+String.valueOf(ip);
            if (ip > 255) {
                break;
            }
            if (segment == 4) {
                System.out.println(seg);
                continue;
            }
            segment(i+1, arr, segment+1, seg);
        }
    }