Java程序员必看：面试官最爱问的那些算法题

在Java编程的世界里，算法就像是一把万能钥匙，它能帮你打开无数扇通往高薪职位的大门。今天，我们就来聊聊那些在Java面试中频频出现的算法题，让你不再为面试时的紧张而烦恼。

1. 数组类问题：寻找数组中的最大值和最小值

假设你正在处理一个员工薪资数据的数组，如何快速找到其中的最大薪资和最低薪资呢？让我们来看看这个简单的例子：

public class ArrayMaxMin {
    public static void main(String[] args) {
        int[] salaries = {5000, 8000, 3000, 9000, 4000};
        
        int maxSalary = salaries[0];
        int minSalary = salaries[0];
        
        for(int salary : salaries){
            if(salary > maxSalary){
                maxSalary = salary;
            }
            if(salary < minSalary){
                minSalary = salary;
            }
        }
        
        System.out.println("最大薪资：" + maxSalary);
        System.out.println("最小薪资：" + minSalary);
    }
}

这段代码简单明了，通过一次遍历就完成了最大值和最小值的查找。记住，这种技巧在处理大数据量时非常高效。

2. 字符串操作：判断字符串是否是回文

面试官常常会问你如何判断一个字符串是不是回文。例如，“上海自来水来自海上”就是一个典型的回文。我们可以这样实现：

public class PalindromeCheck {
    public static boolean isPalindrome(String str){
        int left = 0;
        int right = str.length() - 1;
        
        while(left < right){
            if(str.charAt(left) != str.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
    
    public static void main(String[] args) {
        String testStr = "上海自来水来自海上";
        System.out.println(isPalindrome(testStr)); // 输出true
    }
}

这个方法通过双指针从两端向中间检查字符是否相同，效率非常高。

3. 排序算法：冒泡排序的实现

虽然现代编程语言都有内置的排序函数，但了解基本的排序算法还是很有必要的。比如冒泡排序，虽然效率不高，但简单易懂：

public class BubbleSort {
    public static void sort(int[] arr){
        int n = arr.length;
        for(int i = 0; i < n-1; i++){
            for(int j = 0; j < n-i-1; j++){
                if(arr[j] > arr[j+1]){
                    // swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        int[] numbers = {64, 34, 25, 12, 22, 11, 90};
        sort(numbers);
        for(int num : numbers){
            System.out.print(num + " ");
        }
    }
}

这段代码展示了冒泡排序的基本步骤，每次遍历都将最大的元素“冒泡”到数组的末尾。

4. 栈的应用：括号匹配检查

编写一个程序来检查输入的表达式中括号是否正确配对，比如“(a+b)(c+d)”是正确的，而“(a+b))(c+d)”则不是。这通常用栈来解决：

import java.util.Stack;

public class BracketChecker {
    public static boolean areBracketsBalanced(String expr){
        Stack<Character> stack = new Stack<>();
        
        for(char ch : expr.toCharArray()){
            if(ch == '(' || ch == '[' || ch == '{'){
                stack.push(ch);
            }
            else if(ch == ')' || ch == ']' || ch == '}'){
                if(stack.isEmpty()){
                    return false;
                }
                char top = stack.pop();
                if(!isMatching(top, ch)){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
    
    private static boolean isMatching(char a, char b){
        return (a == '(' && b == ')') || 
               (a == '[' && b == ']') ||
               (a == '{' && b == '}');
    }
    
    public static void main(String[] args) {
        String expr = "{(a+b)*(c+d)}";
        System.out.println(areBracketsBalanced(expr)); // 输出true
    }
}

在这个例子中，我们使用栈来保存左括号，并在遇到右括号时检查栈顶元素是否匹配。

5. 图论基础：最短路径问题

假如你在设计一款地图应用程序，需要计算两点之间的最短路径。经典的Dijkstra算法可以帮助我们解决这个问题：

import java.util.*;

public class DijkstraAlgorithm {
    private final Map<String, Map<String, Integer>> graph = new HashMap<>();
    
    public void addEdge(String from, String to, int cost){
        graph.computeIfAbsent(from, k -> new HashMap<>()).put(to, cost);
    }
    
    public Map<String, Integer> shortestPath(String start){
        Map<String, Integer> distances = new HashMap<>();
        Map<String, String> previous = new HashMap<>();
        PriorityQueue<Map.Entry<String, Integer>> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));
        
        graph.forEach((vertex, edges) -> {
            distances.put(vertex, vertex.equals(start) ? 0 : Integer.MAX_VALUE);
            priorityQueue.add(new AbstractMap.SimpleEntry<>(vertex, distances.get(vertex)));
        });
        
        while(!priorityQueue.isEmpty()){
            Map.Entry<String, Integer> currentEntry = priorityQueue.poll();
            String current = currentEntry.getKey();
            
            if(distances.get(current) == Integer.MAX_VALUE){
                break;
            }
            
            for(Map.Entry<String, Integer> neighborEntry : graph.getOrDefault(current, Collections.emptyMap()).entrySet()){
                String neighbor = neighborEntry.getKey();
                int alt = distances.get(current) + neighborEntry.getValue();
                if(alt < distances.get(neighbor)){
                    distances.put(neighbor, alt);
                    previous.put(neighbor, current);
                    priorityQueue.remove(new AbstractMap.SimpleEntry<>(neighbor, distances.get(neighbor)));
                    priorityQueue.add(new AbstractMap.SimpleEntry<>(neighbor, distances.get(neighbor)));
                }
            }
        }
        return distances;
    }
    
    public static void main(String[] args) {
        DijkstraAlgorithm dijkstra = new DijkstraAlgorithm();
        dijkstra.addEdge("A", "B", 1);
        dijkstra.addEdge("A", "C", 4);
        dijkstra.addEdge("B", "C", 2);
        dijkstra.addEdge("B", "D", 5);
        dijkstra.addEdge("C", "D", 1);
        
        Map<String, Integer> result = dijkstra.shortestPath("A");
        result.forEach((key, value) -> System.out.println(key + ": " + value));
    }
}

这个示例展示了如何构建一个图，并使用Dijkstra算法找到从起点到所有其他节点的最短路径。

总结

以上这些算法都是Java面试中常见的题目，掌握了它们，你就能够在众多求职者中脱颖而出。记住，练习是提高算法能力的关键，不断尝试新的问题，你会发现自己在不知不觉中已经成长为一个算法高手！