NC22. 合并两个有序的数组（easy） 方法一：直接合并排序法 方法二：双指针法 方法三：逆向双指针法(最优解) 方法一：直接合并排序法 思路：这个思路很直接，m是A数组中初始的元素个数，n是B数组中初始的元素个数。且A数组的长度是m+n，因此，我们可以直接通过for将B数组中的元素放到A数组中，由于最终结果需要一个有序的升序数组，我们还需要对新的A数组进行排序，得到最终的答案。于是，我们可以写出以下代码： import java.util.Arrays; pub...

NC45. 实现二叉树先序，中序和后序遍历（medium） 方法一：递归法 方法二：迭代法 方法一：递归法 思路：三种遍历方法最常用的就是递归法，写法非常对称，只需要调整当前层的添加顺序即可，于是，我们可以写出以下代码： import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public cl...

NC88. 寻找第K大（medium） 方法一：栈法 方法一：栈法 思路：同牛客-NC119-最小的K个数，求第K大等价于在小根堆中求第N-K+1小，所有改变遍历次数即可： import java.util.*; public class Solution { public int findKth(int[] a, int n, int K) { // write code here // 特判 int ret = 0...

NC19. 子数组的最大累加和问题（easy） 方法一：直接遍历法（最优解） 方法一：直接遍历法（最优解） 思路：这里注意题目对时间、空间复杂度的要求，所以我们不能使用动态规划来写（虽然后面提交了也没有超时）。我们首先默认数组中的第0个元素是最大的，然后从下标1开始，遵循以下规则：（1）保证每个位置的值至少比原始的大；（2）每次遍历都更新ret，用于保存当前最大的累加和。于是，可以写出以下代码： import java.util.*; public class Solution { ...

NC141. 判断回文（easy） 方法一：双指针法 方法一：双指针法 思路：使用两个指针left和right，left从左往右遍历，right从后往前遍历，遇到相同字符就将left向后移动，同时right向前移动。不相等时，直接返回，不需要再遍历（因为此时已经不再是回文字符了）。当退出while循环时，说明整个字符就是回文字符。于是，可以写出以下代码： import java.util.*; public class Solution { /** * 代码中的类名、方法...

NC17. 最长回文子串（medium） 方法一：中心扩散法 方法一：中心扩散法 思路：这里借鉴了weiwei大佬的题解，自己在这写一遍加深印象。 首先， 中心扩散法的基本思想是：遍历每一个下标，以这个下标为中心，利用 回文串中心对称的特点，往两边扩散，看最多能扩散多远。 枚举中心位置时间复杂度为O(N) ，从中心位置扩散得到回文子串的时间复杂度为O(N)，因此，总的时间复杂度为O(N2)。 值得注意的是，回文串在长度为奇数和偶数的时候，中心位置是不一样的，具体来说： 奇数回文串的中心是...

NC137. 表达式求值（medium） 方法一：双栈法(表达式计算的通用解法) 方法一：双栈法(表达式计算的通用解法) 思路：这里借鉴了三叶大佬的题解，自己在这写一遍加深印象。 对于<mark>任何表达式</mark>而言，我们可以使用两个栈nums和ops： nums：存放所有的数字 ops：存放所有的数字之外的操作 然后从前往后遍历，对遍历的字符分情况讨论： 空格：跳过 (：直接加入ops中，等待与之匹配的) )：使用现有的nums和ops进行计算，...

NC8. 二叉树根节点到叶子节点和为指定值的路径（medium） 方法一：DFS法 方法一：DFS法 思路：前序遍历的增强版，要找出根到叶节点的节点值之和等于sum的路径，所以dfs方法需要带一些标记数据，这里包括包含当前节点时的cur_sum和将当前节点纳入考虑的select列表。（注意这里有个Java常问的知识点：深浅拷贝，我被这个东西坑了，一直得不到正确的答案，这里必须对select列表进行深拷贝，因为浅拷贝生成的列表会指向之前的列表，后续对该列表的改变都会映射到之前的列表中导致最终达到...

NC40. 两个链表生成相加链表（medium） 方法一：链表反转求和法 方法一：链表反转求和法 思路：先将这两个链表进行反转，再逐一遍历求和，注意进位，最后将新链表反转即可得到答案。 import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param head1 ListNode类...

NC1. 大数加法（medium） 方法一：模拟进位法 方法一：模拟进位法 思路：上一题两个链表生成相加链表，我写的三个ArrayList发挥作用了哈（思路很像），但这里可千万别把每一个位置计算得到的值放到ArrayList中，会超时的，样例中有特别特别大的数。那只能另辟蹊径，用StringBuffer直接存储每一位计算得到的值，将int变成character进行存储，从而巧妙地避免了大数越界的问题。于是，我们直接上代码： import java.util.*; public class...

卷，给我疯狂卷！算法题往死里刷！面经往死里背！