正文

Java算法从入门到精通推荐LeetCode和力扣平台看K神图解配合官方文档刷剑指Offer真题掌握动态规划贪心二叉树核心考点

/0 浏览量
0901

为什么现在学算法，Java依然是那个“稳得住”的选择？

如果你今天打开GitHub看贡献者排名，或者去大厂面试间门口蹲守，你会发现一个很有意思的现象：写算法题最多、刷题笔记最系统的，有一半以上是Java党。

这不是因为Java语法比别人短（恰恰相反，Python写两行，Java可能要写五行），而是因为Java这门语言的“严谨性”和“生态完整性”，特别适合用来建立算法思维。

我见过太多初学者，上来就搞Python，觉得简洁好上手。结果呢？遇到链表反转、二叉树遍历、动态规划状态转移的时候，发现语言本身的特性把思维干扰了。Java的强类型、显式内存管理（虽然GC帮你兜底了）、以及完整的集合框架，反而逼着你必须想清楚：这个对象是什么？这个边界在哪？这个指针会不会空？

所以，别纠结选什么语言。既然你选了Java，那就把它玩到极致。今天咱们不聊虚的，直接告诉你怎么从0开始，把算法这块硬骨头啃下来。

第一阶段：别一上来就硬刷，先把“武器库”磨锋利

很多小朋友或者刚转行的小伙伴，上来就打开LeetCode，看“两数之和”，嗯，好像很简单，做完了。然后看“三数之和”，懵了。接着看“动态规划”，彻底崩了。

这是典型的战术勤奋，战略懒惰。

在Java里，你手里有什么武器？你必须先把JDK自带的这些好东西摸透，不然你刷题就像拿着木棍去打铁。

1. 集合框架：你的基础装备箱

别只知道ArrayList和HashMap。在算法里，以下这些类出现频率极高，你必须像认识自己手指头一样认识它们：

  • PriorityQueue（优先队列）：这是Java提供的堆实现。当你需要做“Top K问题”、“中位数”、“合并K个有序链表”时，别自己手写堆了，直接用。默认是小顶堆，想变大顶堆，传个Collections.reverseOrder()。
  • Deque（双端队列）：实现LinkedList或ArrayDeque。BFS（广度优先搜索）、滑动窗口、单调栈，全靠它。记住，addFirst/pollFirst是从头操作，addLast/pollLast是从尾操作。
  • Map的各种实现：HashMap查O(1)，TreeMap按序遍历（红黑树），LinkedHashMap保持插入顺序。刷《剑指Offer》里的哈希表题时，要分清楚什么时候用哪个。

举个例子： 你想判断一个字符串里有没有重复字符，很多人第一反应是双重循环。太慢了，O(n²)。在Java里，一行代码搞定：

public boolean hasDuplicate(String s) {
    Set<Character> set = new HashSet<>();
    for (char c : s.toCharArray()) {
        if (!set.add(c)) return false; // add返回false说明已存在
    }
    return true;
}

看，这就是熟悉API的重要性。

2. 排序与搜索：内置工具别浪费

  • Arrays.sort()：对基本类型用双轴快速排序，对对象用TimSort。时间复杂度O(n log n)。
  • Collections.sort()：同上，针对List。
  • Arrays.binarySearch()：二分查找。注意！它只接受有序数组。如果数组无序，先sort，再search。

很多初学者喜欢手写二分，结果边界条件搞错（mid = (left + right) / 2 在left+right很大时会溢出，要用 left + (right - left) / 2）。其实，对于大多数面试题，如果题目允许，用Arrays.binarySearch是稳妥的；如果考察手写，那务必记住左右边界闭合/开区间的统一写法，不要混用。

第二阶段：力扣（LeetCode）和K神图解，怎么配合着用？

这里我要重点说一下“K神”（Krahets）。他在力扣和GitHub上的图解题解，被无数算法学习者奉为经典。为什么？因为他的图不是那种精美的PPT图，而是思路推导过程图。

1. 不要只“看”，要“复现”

K神的图解好在哪？好在他把抽象的思维过程可视化了。比如二叉树的递归遍历，他会画出一棵树，然后画一个栈，一步步演示递归调用时栈是怎么压入、怎么弹出的。

错误做法：看完图，觉得“哦，我明白了”，然后关掉页面，做下一题。 正确做法：关掉图解，自己在纸上（或者IDE里）把那个过程画出来。如果卡住了，再回去看。

算法思维是肌肉记忆，不是眼球记忆。你眼睛看懂了，手没懂，面试时一紧张还是废。

2. 力扣题目怎么选？

别从头到尾刷。那样效率极低，而且容易半途而废。建议按数据类型或算法思想分类刷。

推荐顺序（Java视角）：

  1. 数组与字符串（基础中的基础）

    • 重点题目：两数之和、三数之和、盛最多水的容器、字符串转换整数、最长无重复子串。
    • 技巧：双指针、滑动窗口。

  2. 链表

    • 重点题目：反转链表、环检测（快慢指针）、合并两个有序链表、LRU缓存。
    • 技巧：虚拟头节点（dummy node）是链表题的神器，能解决很多边界问题。

  3. 栈与队列

    • 重点题目：有效的括号、最小栈、用栈实现队列、滑动窗口最大值（单调队列）。

  4. 二叉树（核心考点，重中之重）

    • 重点题目：最大深度、对称二叉树、前中后序遍历（递归+迭代）、最近公共祖先、层序遍历。
    • 技巧：递归是二叉树最自然的表达方式。一定要掌握“根-左-右”、“左-根-右”、“左-右-根”的打印顺序。同时，一定要会迭代写法，因为面试官有时会要求不用递归。

  5. 回溯算法

    • 重点题目：全排列、组合总和、子集、N皇后。
    • 技巧：回溯就是DFS+状态重置。记住模板：选择->递归->撤销选择。

  6. 动态规划（难点，但不要怕）

    • 重点题目：斐波那契数列、爬楼梯、最大子序和、零钱兑换、编辑距离、0-1背包。
    • 技巧：先找状态转移方程，再确定边界条件。

  7. 贪心算法

    • 重点题目：分发饼干、跳跃游戏、柠檬水找零。
    • 技巧：贪心往往没有通用模板，需要具体问题具体分析，核心是证明“局部最优导致全局最优”。

  8. 图论

    • 重点题目：岛屿数量、课程表（拓扑排序）、网络延迟时间。
    • 技巧：图的遍历（BFS/DFS）、并查集。

第三阶段：剑指Offer真题，大厂面试的“通关密码”

《剑指Offer》这本书，几乎是每个想进互联网大厂的Java程序员必读的“圣经”。它里面的题目，很多是高频中的高频。

1. 为什么是剑指Offer，而不是直接刷LeetCode？

LeetCode题目海量，很多题目偏向思维技巧，或者冷门数据结构。而剑指Offer的题目，更贴近工程实践中的常见问题。比如：

  • 数据结构操作：链表反转、二叉树序列化/反序列化。
  • 数学问题：质数判断、大数相加、数值整数次方。
  • 字符串操作：替换空格、第一个不重复的字符。
  • 查找与排序：旋转数组的最小数字、矩阵中的路径。

这些题目，面试官非常喜欢问，因为能考察你对代码细节的把控能力。

2. 剑指Offer里，哪些题必须吃透？

我帮你列一个Java考生必看清单，并附上关键思路：

  • 第03题：数组中重复的数字

    • 思路：哈希表记录出现次数，或者利用“数字范围在0到n-1”的特性，将数字放到对应索引位置（原地交换）。
    • Java考点：Map的使用，或者数组下标操作。

  • 第04题：二维数组中的查找

    • 思路：从右上角（或左下角）开始查找。如果目标比当前值小，向左移动；如果大，向下移动。
    • Java考点：二维数组的遍历边界。

  • 第05题：替换空格

    • 思路：遍历字符串，遇到空格就替换成%20。
    • Java考点：StringBuilder的使用。注意，如果频繁操作字符串，千万别用+拼接，要用StringBuilder，否则是O(n²)。

  • 第14题：剪绳子

    • 思路：这是经典的动态规划或贪心问题。如果要剪成m段，求最大乘积。
    • 贪心策略：尽可能多剪长度为3的段。如果最后剩1，就和一个3合并成4（2*2 > 3*1）。
    • Java考点：大数取模（因为结果可能很大，题目要求取模1e9+7）。Java的BigInteger或者手动实现大数乘法。

  • 第15题：二进制中1的个数

    • 思路：n & (n-1)可以消除n最右边的1。循环消除直到n为0，统计次数。
    • Java考点：位运算。这是Java面试中考察位运算的经典题。

  • 第17题：打印从1到最大的n位数

    • 思路：看似简单，实则考察大数问题。当n很大时，整数会溢出。需要用字符串或数组模拟大数加法。
    • Java考点：大数处理思维。

  • 第22题：链表中倒数第k个节点

    • 思路：快慢指针。快指针先走k步，然后快慢指针一起走，快指针到末尾时，慢指针正好在倒数第k个。
    • Java考点：链表操作，指针移动。

  • 第24题：反转链表

    • 思路：迭代法，用三个指针（prev, curr, next）不断翻转指向。
    • Java考点：链表反转是基础中的基础，必须能徒手写出来，一行不错。

  • 第25题：合并两个排序的链表

    • 思路：双指针，比较两个链表当前节点的值，小的那个接入结果链表。
    • Java考点：链表操作，虚拟头节点。

  • 第30题：包含min函数的栈

    • 思路：用两个栈，一个存数据，一个存当前最小值。
    • Java考点：栈的应用，辅助栈思想。

  • 第33题：二叉搜索树的后序遍历序列

    • 思路：后序遍历的最后一个元素是根节点。左子树都小于根，右子树都大于根。递归验证。
    • Java考点：二叉搜索树性质，递归。

  • 第34题：二叉树中和为某一值的路径

    • 思路：DFS，记录路径，到达叶子节点时判断和是否相等。
    • Java考点：二叉树DFS，路径记录（回溯）。

  • 第35题：复杂链表的复制

    • 思路：哈希表存原节点和新节点的映射，或者“插空法”（在原节点后插入新节点，然后复制random指针，最后拆分）。
    • Java考点：链表操作，空间换时间 vs 时间换空间。

  • 第36题：二叉搜索树与双向链表

    • 思路：中序遍历二叉搜索树，得到有序序列，然后在遍历过程中修改指针。
    • Java考点：二叉树中序遍历，指针操作。

  • 第44题：数字序列中某一位的数字

    • 思路：数学规律。1位数有9个，2位数有90个… 先确定是在几位数里，再确定是第几个数，再确定是那个数的哪一位。
    • Java考点：数学建模能力。

  • 第50题：第一个只出现一次的字符

    • 思路：哈希表统计频率，或者利用数组（字符ASCII范围有限）做计数。
    • Java考点：哈希表，字符编码。

  • 第51题：数组中的逆序对

    • 思路：归并排序。在合并过程中，如果左半部分的元素大于右半部分的元素，说明存在逆序对。
    • Java考点：分治思想，归并排序变种。

  • 第52题：两个链表的第一个公共节点

    • 思路：如果两个链表有公共节点，那么从公共节点开始，后面的部分完全一样。可以用哈希表存节点，或者让长链表的指针先走长度差步数，然后一起走。
    • Java考点：链表操作，双指针。

  • 第53题：在排序数组中查找数字

    • 思路：二分查找，找到第一次出现和最后一次出现的位置。
    • Java考点：二分查找变种。

  • 第54题：二叉搜索树的第k大节点

    • 思路：中序遍历的倒序（右-根-左），第k个访问的节点就是答案。
    • Java考点：二叉树遍历。

  • 第55题：二叉树的深度 / 平衡二叉树

    • 思路：递归求深度。平衡树判断需要同时返回深度和是否平衡。
    • Java考点：二叉树递归，后序遍历。

  • 第56题：数组中数字出现的次数 / 只出现一次的数字

    • 思路：位运算。相同数字异或为0，所以所有数字异或的结果，就是只出现一次的那个数字（如果只有一个的话）。如果是两个，需要分组异或。
    • Java考点：位运算技巧。

  • 第57题：和为s的两个数字 / 和为s的连续正数序列

    • 思路：双指针（有序数组）或滑动窗口（连续序列）。
    • Java考点：双指针，滑动窗口。

  • 第58题：翻转单词顺序 / 左旋转字符串

    • 思路：先整体反转，再局部反转。
    • Java考点：字符串操作，反转技巧。

  • 第59题：队列的最大值

    • 思路：用两个栈实现队列，或者用双端队列（Deque）辅助记录最大值。
    • Java考点：栈与队列的互相实现，单调队列。

  • 第60题：n个骰子的点数

    • 思路：动态规划。dp[i][j]表示i个骰子，点数为j的概率（或组合数）。
    • Java考点：动态规划，多维DP。

  • 第61题：扑克牌中的顺子

    • 思路：排序，统计0（癞子）的个数，看能不能填补非0数字之间的空隙。
    • Java考点：排序，边界判断。

  • 第62题：圆圈中最后剩下的数字（约瑟夫环）

    • 思路：数学递推。f(n, m) = (f(n-1, m) + m) % n。
    • Java考点：递推公式，数学思维。

  • 第63题：股票的最大利润

    • 思路：动态规划。记录当前最小价格，计算当前价格与最小价格的差值的最大值。
    • Java考点：动态规划，一次遍历。

  • 第64题：求1+2+…+n

    • 思路：不能用乘除、if、while、for、switch、三元运算符。可以用短路求值（&&）或递归+异常处理。
    • Java考点：语言特性，短路求值。

  • 第65题：不用加减乘除做加法

    • 思路：位运算。a ^ b是不进位的和，a & b是进位。循环相加，直到进位为0。
    • Java考点：位运算，加法器原理。

  • 第66题：构建乘积数组

    • 思路：分别计算每个位置左边元素的乘积和右边元素的乘积，然后相乘。
    • Java考点：数组操作，前后缀积。

  • 第67题：把字符串转换成整数

    • 思路：手动实现Integer.parseInt。处理符号、空格、溢出、非法字符。
    • Java考点：字符串解析，边界条件（溢出判断）。

  • 第68题：二叉搜索树的最近公共祖先

    • 思路：利用BST性质。如果两个节点值都小于根，则在左子树；都大于根，则在右子树；否则根就是公共祖先。
    • Java考点：二叉搜索树，递归。

(注：剑指Offer第2版有67题，以上列举的是Java面试最高频的20+道核心题，涵盖了链表、树、DP、位运算、数学等。)

第四阶段：攻克核心考点——动态规划、贪心、二叉树

这部分是算法的“深水区”。很多初学者在这里卡住，觉得难。其实，只要掌握了模式，就不难。

1. 动态规划（DP）：从“背题”到“

-- 展开阅读全文 --