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

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

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; if (n == 0 || K > n) {  return ret; } PriorityQueue<Integer> pq = ...

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

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

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

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

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

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

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

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