java研发岗经典编程题

### Java研发岗经典编程题详解 #### 一、第一个只出现一次的字符 **题目描述：** 在给定的字符串中找到第一个仅出现一次的字符。例如，对于字符串 "abaccdeff"，应返回 'b'。 **解题思路：** 本题的关键在于如何高效地统计每个字符在字符串中的出现次数，并且快速定位到第一个只出现一次的字符。通过使用哈希表（在Java中可以使用`LinkedHashMap`），我们可以实现这一目标。具体步骤如下： 1. **初始化哈希表：** 创建一个哈希表，用于存储每个字符及其出现的次数。 2. **第一次遍历：** 遍历字符串，将每个字符的出现次数记录在哈希表中。 3. **第二次遍历：** 再次遍历字符串，检查每个字符在哈希表中的出现次数，找出第一个出现次数为1的字符并返回。 **时间复杂度分析：** - 第一次遍历的时间复杂度为 O(n)，其中 n 是字符串的长度。 - 第二次遍历的时间复杂度同样是 O(n)。 - 因此，总的时间复杂度为 O(2n) ≈ O(n)。 **空间复杂度分析：** - 哈希表的空间复杂度为 O(m)，其中 m 是字符集的大小。对于ASCII字符集而言，m = 256，因此空间复杂度为 O(256) ≈ O(1)。 **Java代码示例：** ```java import java.util.LinkedHashMap; public class FirstNotRepeatingChar { public Character firstNotRepeating(String str) { if (str == null) return null; char[] strChar = str.toCharArray(); LinkedHashMap<Character, Integer> hash = new LinkedHashMap<>(); // 第一次遍历，统计每个字符的出现次数 for (char item : strChar) { if (hash.containsKey(item)) { hash.put(item, hash.get(item) + 1); } else { hash.put(item, 1); } } // 第二次遍历，查找第一个只出现一次的字符 for (char key : hash.keySet()) { if (hash.get(key) == 1) { return key; } } return null; } public static void main(String[] args) { String str = "abaccdeff"; FirstNotRepeatingChar test = new FirstNotRepeatingChar(); System.out.println(test.firstNotRepeating(str)); } } ``` #### 二、深入浅出经典面试题之——反转字符串 **题目描述：** 反转一个给定的字符串。例如，字符串 "hello" 反转后变为 "olleh"。 **解题思路：** 反转字符串可以通过多种方式实现，这里介绍一种简单的方法：使用数组或字符数组来进行原地反转。 1. **初始化变量：** 定义两个指针，一个指向字符串的开头，另一个指向字符串的结尾。 2. **交换字符：** 当两个指针未相遇时，交换它们所指向的字符，并移动指针。 3. **重复步骤2，直至两指针相遇或交错。** **时间复杂度分析：** - 由于只需要遍历字符串的一半，时间复杂度为 O(n/2) ≈ O(n)。 **空间复杂度分析：** - 由于是在原数组上进行操作，无需额外空间，因此空间复杂度为 O(1)。 **Java代码示例：** ```java public class ReverseString { public String reverse(String str) { if (str == null || str.length() <= 1) return str; char[] chars = str.toCharArray(); int left = 0; int right = chars.length - 1; while (left < right) { char temp = chars[left]; chars[left] = chars[right]; chars[right] = temp; left++; right--; } return new String(chars); } public static void main(String[] args) { ReverseString reverse = new ReverseString(); System.out.println(reverse.reverse("hello")); // 输出: olleh } } ``` 以上两个题目是Java研发岗位常见的编程题类型，通过对这些经典问题的理解和实践，可以帮助候选人更好地准备面试，并提高解决实际问题的能力。