算法面试题

# 算法面试题

# 🧮 数据结构与算法

# 1. 数组与字符串

Q: 两数之和问题

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

时间复杂度: O(n)
空间复杂度: O(n)

Q: 最长无重复字符子串

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

public int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int left = 0, maxLen = 0;
    
    for (int right = 0; right < s.length(); right++) {
        while (set.contains(s.charAt(right))) {
            set.remove(s.charAt(left));
            left++;
        }
        set.add(s.charAt(right));
        maxLen = Math.max(maxLen, right - left + 1);
    }
    
    return maxLen;
}

# 2. 链表

Q: 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;
    
    while (current != null) {
        ListNode next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    
    return prev;
}

Q: 检测链表中的环

给定一个链表，判断链表中是否有环。

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    
    ListNode slow = head;
    ListNode fast = head.next;
    
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return true;
}

# 3. 树

Q: 二叉树的最大深度

给定一个二叉树，找出其最大深度。

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);
    
    return Math.max(leftDepth, rightDepth) + 1;
}

Q: 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

public boolean isValidBST(TreeNode root) {
    return validate(root, null, null);
}

private boolean validate(TreeNode node, Integer lower, Integer upper) {
    if (node == null) {
        return true;
    }
    
    int val = node.val;
    if (lower != null && val <= lower) return false;
    if (upper != null && val >= upper) return false;
    
    if (!validate(node.right, val, upper)) return false;
    if (!validate(node.left, lower, val)) return false;
    
    return true;
}

# 4. 动态规划

Q: 爬楼梯问题

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

public int climbStairs(int n) {
    if (n <= 2) {
        return n;
    }
    
    int first = 1, second = 2;
    for (int i = 3; i <= n; i++) {
        int third = first + second;
        first = second;
        second = third;
    }
    
    return second;
}

Q: 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

public int maxSubArray(int[] nums) {
    int maxSoFar = nums[0];
    int maxEndingHere = nums[0];
    
    for (int i = 1; i < nums.length; i++) {
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    
    return maxSoFar;
}

# 5. 排序算法

Q: 快速排序实现

public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

private int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    
    swap(arr, i + 1, high);
    return i + 1;
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

时间复杂度: 平均 O(n log n)，最坏 O(n²)
空间复杂度: O(log n)

# 💡 算法面试技巧

理解题目：仔细阅读题目，确认输入输出格式
举例分析：用具体例子分析问题
暴力解法：先想出暴力解法，再优化
时空复杂度：分析并说明算法的时间和空间复杂度
边界条件：考虑特殊情况和边界条件
代码规范：保持代码整洁，变量命名清晰

# 📚 推荐资源

LeetCode 热题 HOT 100
《剑指Offer》
《程序员代码面试指南》
《算法导论》

Java面试题系统设计题

Jeskson-微服务分布式

Choose mode