Java面试题冲刺第二十三天–算法(2)

Java面试题冲刺第二十三天--算法(2)

本文将介绍算法练习题目以及解题思路，帮助考生提升算法编程实战水平。以下为本文题目及解法。

题目1：二叉树的遍历

题目描述

有一个二叉树，请实现一个函数按照中序遍历，将节点中的数字打印出来，每个数字后面都跟着一个空格。

解题思路

二叉树的中序遍历是指：先遍历左子树，然后访问根结点，最后遍历右子树。对于这个题目，可以分为以下步骤：

1. 如果当前节点是null，则返回
2. 遍历左子节点
3. 打印当前节点的值及一个空格
4. 遍历右子节点

根据上述思路可得，这个题目可以通过递归的方式来实现。具体的代码实现如下：

public static void inOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    inOrder(root.left);
    System.out.print(root.val + " ");
    inOrder(root.right);
}

示例说明

以以下二叉树为例：

      1
     / \
    2   3
   / \
  4   5

中序遍历输出结果为：4 2 5 1 3

题目2：字符串中第一个只出现一次的字符

题目描述

在一个字符串中找到第一个只出现一次的字符，并返回它的位置。字符串只包含 ASCII 码字符。

解题思路

该题目可以通过遍历字符串并使用hash表记录每个字符出现的次数来解决。具体思路如下：

1. 创建一个hash表用于记录每个字符出现的次数（表的key为字符，value为此字符出现次数）
2. 遍历字符串，在hash表中记录每个字符出现次数
3. 再次遍历字符串，找到hash表中value为1的字符

代码实现如下：

public static int firstNotRepeatingChar(String str){
    if(str == null || str.length() == 0){
        return -1;
    }
    Map<Character,Integer> map = new HashMap<Character,Integer>();
    for(char c:str.toCharArray()){
        if(map.containsKey(c)){
            map.put(c,map.get(c)+1);
        } else {
            map.put(c,1);
        }
    }
    for(int i = 0;i < str.length();i++){
        if(map.get(str.charAt(i)) == 1){
            return i;
        }
    }
    return -1;
}

示例说明

如果输入字符为："abaccdeff"，则输出为：1，即字符"b"第一次出现且只出现一次的位置。