算法编程（一）

一、字符串转换成数字

    设计要求：将输入的任意字符串，转换成数字（int类型），如果转换失败则抛出异常。

    输入："1234"，"+1234"，"-1234"，"1234567890"，"1234ab"

    输出：1234，1234，-1234，异常，异常

 

    思路：字符串有字符序列组成，每个字符都对应ASCII值，比如字符'0'为48，‘1’为49...'9'为57，你或许不知道它们对应的具体值，但是需要知道字符‘0’~‘9’的ASCII值是连续的即可。任何数组字符与‘0’字符的ASCII值的差值即可以表示其实际数字，比如：'5' - '0' = 5。代码样例如下：

    需要注意：

    1）不合法字符，不能参与计算

    2）兼顾字符串开头的“+”、“-”字符

    3）因为int数字，有最大值、最小值边界，所以计算时如果越界应该抛出异常

 

public static int parseToInteger(String value) {
    if(value == null || value.isEmpty()) {
        throw new RuntimeException("null!");
    }
    //合法前缀“-”，“+”
    int start = 0;
    char[] chars = value.toCharArray();
    char first = chars[0];
    if(first == '-' || first == '+') {
        start = 1;
    }
    boolean negative = false;
    if (first == '-') {
        negative = true;
    }

    //合法数字字符的边界
    int zero = '0';
    int nigh = '9';
    int result = 0;
    for(int i= start; i < chars.length; i++) {
        char item = chars[i];
        if(item < zero || item > nigh) {
            throw new RuntimeException("Format error!");
        }
        int current = (item - '0');
        //检测边界，int的最大值与最小值
        if(negative) {
            if(Integer.MIN_VALUE + result * 10 + current > 0) {
                throw new RuntimeException("too small!");
            }
        } else {
            if (Integer.MAX_VALUE - result * 10 < current) {
                throw new RuntimeException("too big!");
            }
        }
        result = result * 10 + current;
    }

    return negative ? 0 - result : result;

}

 

二、从二维数组中判断“目标数字”是否存在

    有一个二维数组，元素值为整型数字；二维数组的数据特征为：每行、每列元素均是按照从小到大排列，数字可能重复。问题：指定一个目标数字，请判断二维数组中是否存在此值，如果存在则返回true，否则返回false。

 

    数据模型样例解释：

1 2 8 9
2 4 9 12
4 7 10 13
6 9 11 15

 

    比如上述二维数组，每行、每列都是有序的，假如目标数字为“7”，则判定结果应该为true；如果目标数字为“20”，那么判定结果应该为false。

    思路：这个题如果作为面试题，还是稍微有些复杂，涉及到查找路径问题。二维数组的每个元素都有特征：左边与上边的元素比它小，右边和下边的元素比它大。如果“目标数字”比当前元素小，那么查找方向应该往其左边或者上边，否则就是往其右边或者下面。我们暂定，查找路径优先“左右”，然后再“上下”（具体由你选定的起始点决定）。

假如在如下数组中查找“7”是否存在，我们将二维数组的“右上角”作为起始点（起始点的选择，可以随意，只是这样编程稍微简单）：
1 2 8 9
2 4 9 12
4 7 10 13
6 9 11 15

查找路径如下：
1 2 <- 8 <- 9
  \/
2 4      9      12  
  \/
4 7      10    13
6 9      11    15

 

   代码示例：

public static boolean find(int[][] arrays,int row,int column,int target) {
    try {
        int item = arrays[row][column];
        //System.out.println(item);//打印路径
        if (item == target) {
            return true;
        } else if (arrays[row][column] > target) {
            return find(arrays, row, column - 1, target);
        } else {
            return find(arrays, row + 1, column, target);
        }
    } catch (Exception e) {
        //
    }
    return false;
}

 

三、书写一段程序，将数组转换成单向链表，并反向输出此链表的数值

    考察2个点，第一：构建一个单向链表，第二：反向输出链表的数值。构建一个单向链表本身并不难，但易于出错，主要考察编程人员对数据结构的认识；难点就在于“如何反向输出单向链表的节点值”；单向链表只能向下驱动（next），所以我们即使找到了单向链表的尾部，仍然不能反向输出，因为无法“向上”查找。解题的关键可以根据实际情况而定，如果允许额外的使用其他数据结构，那么我们可以在遍历单向链表时将节点逐个加入到“栈”中（Stack，先进后出），然后使用stack的特性逐个输出即可（pop）；如果不允许使用额外的数据结构，那么我们可以考虑使用“递归”的方式（原理也类似于栈）遍历。

 

    输入：1，2，3，4，5，6

    输出：6，5，4，3，2，1

    代码样例：

public static void main(String[] args) {
    int[] source = {1,2,3,4,5,6,7};
    LinkedNodes linkedNodes = buildLinked(source);
    print(linkedNodes);
}

static class LinkedNodes {
    Node header = new Node();//header仅仅为标记性节点
    Node tail;
}
static class Node {
    Node next;
    int value;
}

public static LinkedNodes buildLinked(int[] source) {
    LinkedNodes linked = new LinkedNodes();
    for(int i = 0; i < source.length; i++) {
        Node node = new Node();
        node.value = source[i];
        if(i == 0) {
            linked.header.next = node;
            linked.tail = node;
        }else {
            linked.tail.next = node;
            linked.tail = node;
        }
    }

    return linked;

}

private static void print(LinkedNodes linkedNodes) {
    if(linkedNodes == null || linkedNodes.header.next == null) {
        return;
    }
    print(linkedNodes.header.next);
}

private static void print(Node node) {
    if(node == null) {
        return;
    }
    Node current = node.next;
    if(current != null) {
        print(current);
    }
    System.out.print(node.value + ",");
}

 

四、请将指定数组构建成一个二叉树，并使用“前序”遍历打印此树（或者：中序遍历、后序遍历）

    首先需要知道如何构建一个二叉树，二叉树的特征：每个节点最多有两个子节点，分别为左右节点，对于任何一个节点，其左节点都比自己小，右节点都比自己大。

    前序、中序、后序遍历的区别，主要是“中间”节点的位置（相对于左、右节点），比如前序遍历，表示中间节点在前面（中-->左-->右），中序遍历表示当前节点在“中间”（左-->中-->右）。

 

    第一：构建二叉树，主要考察编程技能和对数据结构的认识，第二：遍历的方式，如果了解了上面的原理，遍历的编程应该水到渠成。

 

    输入：一个数组，这个数组表示一个由宽度遍历后的满二叉树（特别注意，如果不是完全二叉树，实现方式完全不同）。

    输出：前序遍历

比如输入数组：[10,6,14,4,8,12,16]

构建的二叉树应该为：
   10
   |
 6    14
 |     |
4 8  12 16

 

    第一步，先将数组构建成一个二叉树（平衡二叉树，完全二叉树），非常棘手，既然是一个“平衡、完全二叉树”，我们可以从树的节点与数组的索引位置对应关系找突破口：

树节点与数组索引对应关系：

当前节点      左节点  右节点
10（0）       6（1）   14（2）
6（1）         4（3）    8 （4）
14（2）       12（5）  16（6）

如果当前节点对应数组的索引位置为N，可以得出：
左节点：2 * N + 1
右节点：2 * （N + 1）

 

    代码样例如下：

public static void main(String[] args) throws Exception{
    int[] source = {10,6,14,4,8,12,16};

    BinaryTree tree = new BinaryTree();
    BinaryTreeNode root = new BinaryTreeNode();
    tree.root = root;
    root.value = source[0];
    buildTree(root, source, 0);
}

static class BinaryTree {
    BinaryTreeNode root;
}
static class BinaryTreeNode {
    BinaryTreeNode left;
    BinaryTreeNode right;
    int value;
}

private static void buildTree(BinaryTreeNode current,int[] source,int currentIndex) {
    int leftIndex = currentIndex * 2 + 1;
    int rightIndex = (currentIndex + 1) * 2;
    int max = source.length;//可以不用每次都计算
    if(leftIndex < max) {
        BinaryTreeNode leftNode = new BinaryTreeNode();
        leftNode.value = source[leftIndex];
        current.left = leftNode;
        buildTree(leftNode, source, leftIndex);
    }

    if(rightIndex < max) {
        BinaryTreeNode rightNode = new BinaryTreeNode();
        rightNode.value = source[rightIndex];
        current.right = rightNode;
        buildTree(rightNode, source, rightIndex);
    }
}

 

    1）前序遍历代码样例：

public static void main(String[] args) throws Exception{
	//....
    front(tree.root);
}

private static void iterate(BinaryTreeNode current) {
    BinaryTreeNode left = current.left;
    System.out.print(current.value + ",");
    if(left != null) {
        iterate(left);
    }
    BinaryTreeNode right = current.right;
    if(right != null) {
        iterate(right);
    }
}

 

    2）中序遍历代码样例：

private static void iterate(BinaryTreeNode current) {
    BinaryTreeNode left = current.left;
    if(left != null) {
        iterate(left);
    }
    System.out.print(current.value + ",");
    BinaryTreeNode right = current.right;
    if(right != null) {
        iterate(right);
    }
}

 

    与前序遍历的唯一差别，就是打印当前节点的时机，即先遍历完左节点之后才打印。那么“后序遍历”同理！

 

五、指定二叉树的“前序遍历”数组、“中序遍历”数组，请根据上述2个数组来重建此二叉树。

    从上题中我们已经知道，二叉树的三种遍历方式，这个题正好相反，我知道了二叉树的遍历的结果，我们要反向重建二叉树。（备注：前序 + 中序、中序 + 后续可以重建二叉树，只知道其中一种，是无法完全重建原有的二叉树）

    输入：二叉树的前序、中序遍历结果，比如前序、中序遍历结果分别为[1,2,4,7,3,5,6,8]、[4,7,2,1,5,3,8,6]。

    输出：无输出，构建一个二叉树。（备注：可以输出为此二叉树的“后序遍历”结果）

 

    这道题已经算是比较复杂了，通常现场面试、笔试的话已不太适合，比较耗时。主要考察对二叉树遍历的原理，以及反向思维。

前序：
1  2  4  7  3  5  6  8
中序：
4  7  2  1  5  3  8  6
构建结果：
        1
        |
   2        3
    /        |
   4     5     6
   \             /
    7          8


前序的特点就是“中”--“左”--“右”，对于任何二叉树包括其子二叉树，root节点总是位于第一个，比如本例中“1”就是此二叉树的root节点。

中序的特点就是“左”--“中”--“右”，对于二叉树包括其子二叉树，遍历结果中root节点值的左边一定是左子树，右边一定是右子树。

最终规律是：根据前序结果找到二叉树（递归是为二叉树子树）的root节点，根据中序结果找到“左子树”、“右子树”。

根据前序结果我们得出顶层的root节点是1，然后在中序结果中找到1的位置，1的两侧分别为root的“左子树”、“右子树”。

第一次拆分：
1  [2  4  7]  [3  5  6  8]
[4  7  2]  1  [5  3  8  6]
通常是根据”中序“找到左右子树后，分别计算左右子树的元素个数，比如本次拆分，左子树为3个元素，右子树为4个元素；然后在”前序“结果中，紧邻root的3个元素也是”左子树“，此后的四个元素是”右子树“。

然后递归：分别让它们的左子树和右子树，也按照上述原理，查找root，然后继续拆分子树....
左子树的前序：2 4 7
左子树的中序：4 7 2
此左子树的root节点为2，然后继续拆分...

右子树的前序：3 5 6 8
右子树的中序：5 3 8 6
此右子树的root节点为3，然后继续拆分...

 

    代码样例如下：

public static void main(String[] args) throws Exception{
    int[] preOrder = {1,2,4,7,3,5,6,8};//前序
    int[] inOrder = {4,7,2,1,5,3,8,6};//中序

    BinaryTree tree = new BinaryTree();
    BinaryTreeNode root = new BinaryTreeNode();
    tree.root = root;
    buildTree(root,preOrder,0,preOrder.length - 1,inOrder,0,inOrder.length - 1);
    iterate(root);
    System.out.println("");
    iterate1(root);
}

static class BinaryTree {
    BinaryTreeNode root;
}
static class BinaryTreeNode {
    BinaryTreeNode left;
    BinaryTreeNode right;
    int value;
}

private static void buildTree(BinaryTreeNode current,int[] preOrder,int preStart, int preEnd,int[] inOrder,int inStart,int inEnd) {

    int value = preOrder[preStart];
    current.value = value;
    if(preStart == preOrder.length -1 || inStart == inOrder.length - 1) {
        return;
    }
    int nextRoot = -1;

    for(int i = inStart; i <= inEnd; i ++ ) {
        if(inOrder[i] == value) {
            nextRoot = i;
            break;
        }
    }
    if (nextRoot == -1) {
        throw new RuntimeException("Error!");
    }

    int leftLength = nextRoot - inStart;
    if(leftLength > 0) {
        BinaryTreeNode left = new BinaryTreeNode();
        current.left = left;
        buildTree(left, preOrder, preStart + 1, preStart + leftLength, inOrder, inStart, nextRoot - 1);
    }

    int rightLength = inEnd  - nextRoot;
    if(rightLength > 0) {
        BinaryTreeNode right = new BinaryTreeNode();
        current.right = right;
        buildTree(right, preOrder, preEnd + 1 - rightLength, preEnd, inOrder, nextRoot + 1, inEnd);
    }

}