题目 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。 题解 思路1 动态规划（/递归） 递归函数： F（n） = nums[i] i =0 或 F(n-1) < 0 F(n) = num[i] + F(n-1) i ≠0 或 F(n-1) >= 0 按照上述函数写法： 时间复杂度: O(N ^ 2)- 空间复杂...

题目描述 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 题解 写任意一个二叉搜索树的后序遍历序列出来分析： 二叉搜索树的定义是 左节点 < 根节点，右节点 > 根节点 对于后序遍历的序列T，最后一个元素X就是根节点 ，如果去掉X，那么T满足： T可以分成两段，前一段 < X ，后一段 > X ， 且这两段都满足后序序列 完美的递归定义 递归思路：  确定root 遍历，找到第一个大于root的值的位置 , 则该位置左边是左子树，右边是右子树 遍历右子树，如果都大于 root，则...

题目描述 从上往下打印出二叉树的每个节点，同层节点从左至右打印。 题解 不像前、中、后序遍历，它要求一层一层地遍历 利用一个辅助队列，弹出父节点的同时，将它的左右孩子加入队列 时间复杂度: O(N)- 空间复杂度: O(N) public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { ArrayList<Integer> res = new ArrayList<>(); if (root == null) return res; Deque<TreeNode> deque = n...

题目描述 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。 假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的） 题解 双指针 + 辅助栈 时间复杂度: O(N)- 空间复杂度: O(N) public boolean IsPopOrder(int[] pushA, int[] popA) { if (pushA.length == 0 || popA.length == 0) return f...

题目描述 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。 题解 要求O(1) 利用辅助栈存最小值  入栈时，如果该值 <= 最小值栈中的栈顶的值 ， 就将改值压入最小值栈 出栈，如果出栈元素 == 最小值栈顶元素，则把最小值栈的值一起出栈 private Stack<Integer> stack = new Stack<Integer>(); private Stack<Integer> minStack = new Stack<Integer>(); public void push...

题目描述 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10. 题解 画图出来分析会清晰很多 画图出来观察，每一圈的起点 总是位于 (0,0) 、(1,1)、（2,2）、（3,3）... 然后确定这个矩阵有多少圈 画图发现，最后一圈总是 start * start < rows && start * start < cols 圈数循环的终止条件有了，分...

题目描述 操作给定的二叉树，将其变换为源二叉树的镜像。 输入描述: 二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 5题解 这题不能想太多，会被绕死 直接遍历交换它们的左右孩子的位置就好 public void Mirror(TreeNode root) { if (root == null) return; if (root.left == null && root.right == null) return; /*交换子节点*/ TreeNode tmp = root.lef...

题目描述 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） 题解 树的遍历有递归和迭代 递归比较容易写，就递归吧 先在A树中递归查找B树的根节点 找到后，再递归判断两颗树的左右孩子是否相等，都相等则B是A的子结构 不等，继续在A中找下一个B的根节点 /*判断root2是否是root1的子树*/ public boolean HasSubtree(TreeNode root1, TreeNode root2) { if (root1 == null || root2 == null) return false; boolean res = false; ...

题目 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 示例: 给定 1->2->3->4, 你应该返回 2->1->4->3.题解 思路1 递归 时间复杂度: O(N)- 空间复杂度: O(1) public ListNode swapPairs(ListNode head) { ListNode pre = new ListNode(-1); return swap(pre,head); } /** * 递归交换两个节点 * @return 交换后的头节点 */ private L...

题目 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6题解 思路1 暴力迭代 数组每一个元素都和前一个元素进行合并 数组最后的那个元素即全部链表的合并结果，弊端就是数组所有的数据被破环掉了 时间复杂度: O(N)- 空间复杂度: O(1) public ListNode mergeKLists(ListNode[] lists) { if (lists.length == 0) ...

题目 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4题解 首先同时遍历两个链表，比较两个链表当前的值，小的值就作为新链表的元素，然后小的值的链表就走到下一个元素，大的值的链表还是当前元素。接着继续遍历，重复上述步骤，直到链表遍历完毕。这样就可以得到新的有序链表了。 需要注意的点：  这个题目，创建一个头结点来作为辅助，这样就不用判断新链表的头结点是l1的头结点还是l2的头结点了。 遍历到最后，一般会有一个链表...

题目描述 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。 题解 思路1 开一个辅助数组，简单实用 遍历3次 1 -- 将奇数放入辅助数组 2 -- 将偶数放入辅助数组 3 -- 辅助数组的值覆盖原数组 时间复杂度: O(n)- 空间复杂度: O(N) public void reOrderArray(int[] array) { int[] cp = new int[array.length]; int idx = 0; /*先存储奇数*/ for (int i = 0; ...

题目 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 示例： 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5.题解 思路1 dummyHead 和 双指针 fast 指针先走 n 步 接着 slow指针 和 fast指针一起走，直到fast指针走到最后 删除 slow指针所指节点 返回dummyHead.next , 不直接返回head ，因为可能删的就是head。 时间复杂度: O(N)- 空间复杂度: O(1) /** * Definition for s...

题目描述 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。  输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。  例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。  NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。 题解 思路1 直接遍历 时间复杂度: O(N)- 空间复杂度: O(1) 思路2 二分查找 分析：旋转数组可以看成是两个有序数组组成的，最小元素就是这两个数组的分界点 用两个指针进行二分查找，lo指针总是指向第一个数组的终点，hi指针总是指向第二个数组的起点 直到 lo 与 hi相邻，即 lo == hi...