问题描述： {6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和 思路： 使用动态规划直接对原数组进行迭代式修改： 代码： import java.lang.Math; public class Solution { public int FindGreatestSumOfSubArray(int[] array) { int res = nums[0]; for(int i = 1; i < nums.length; i++) { ...

题目描述 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。 思路：用最大堆保存这k个数，每次只和堆顶比，如果比堆顶小，删除堆顶，新数入堆。 代码： import java.util.ArrayList; import java.util.PriorityQueue; import java.util.Comparator; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, ...

题目描述 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。 思路：1.使用sort函数排序，统计中间的数字出现的次数，超过一半，即为输出。2.如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多。在遍历数组时保存两个值：一是数组中一个数字，一是次数。遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，并将次数置为1。遍历结束后，所保存的数字即为所求。然后再判断它是否符...

题目描述 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 思路： 代码： import java.util.*; public class Solution { private ArrayList<String> ret = new ArrayList<>(); public ArrayList<String> Permutation(String str) { List<String> ...

题目描述 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。 思路：利用栈，循环条件（p不为空||栈不为空）先一直压栈树的左节点，弹出栈顶，将其作为双向链表的ROOT，之后弹栈一个元素，更改前面定好的指针，使用pre指向当前节点之前的节点，p指向当前弹出元素，改变前后双向指针的顺序，之后p指向当前弹栈元素的右节点。代码： import java.util.Stack; public class Solution { public TreeNode Convert(TreeNode root) { if(...

题目描述 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空） 思路： 1、复制每个节点，如：复制节点A得到A1，将A1插入节点A后面 2、遍历链表，A1->random = A->random->next; 3、将链表拆分成原链表和复制后的链表代码： public class Solution { public RandomListNode Clone(RandomListNo...

题目描述 输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前) 思路：递归，每次调用，目标数值-此时的节点，然后此时的节点调用原函数递归左右子树。调用结束后要回退————将list中的最后一个元素删除。在递归中如果出现目标值被减为0的情况，那么就存入最终的大list中。 代码： public class Solution { ArrayList<ArrayList<Integer>> listAll = new...

题目描述 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 思路： 已知条件：后序序列最后一个值为root；二叉搜索树左子树值都比root小，右子树值都比root大。1、确定root；2、遍历序列（除去root结点），找到第一个大于root的位置，则该位置左边为左子树，右边为右子树；3、遍历右子树，若发现有小于root的值，则直接返回false；4、分别判断左子树和右子树是否仍是二叉搜索树（即递归步骤1、2、3）。 代码： public class Solution { public bool...

题目描述 从上往下打印出二叉树的每个节点，同层节点从左至右打印。 思路：使用队列，入队一个节点，当他出队时，存入数组，同时，将他的左右节点放入队列。 代码： import java.util.Queue; import java.util.ArrayList; import java.util.LinkedList; public class Solution { public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { ArrayList<Integer> result ...

题目描述 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的） 思路：借助辅助栈。将输入序列压栈，每压栈一个，就判断对应的弹栈序列的peek是否于压栈的相同————相同就弹栈（并继续判断是否此序列和栈顶端是否相同），不同就继续压栈。最后，如果弹栈序列正确，辅助栈中应为空，否则，错误。 代码： import java.util.ArrayList...

题目描述 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。 思路：应用一个辅助栈，压的时候，如果A栈的压入比B栈压入大，B栈不压，，，，小于等于，AB栈同时压入，出栈，如果，AB栈顶元素不等，A出，B不出。 代码： import java.util.Stack; public class Solution { Stack<Integer> s1 = new Stack<Integer>(); Stack&l...

题目描述 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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. 思路：确定4个数 up,down,left,right 循环条件的出口是四个数，对应超过互相。 代码： import java.util.ArrayList; public class Solution { public ArrayList<Integer> printMatrix(int [...

题目描述 操作给定的二叉树，将其变换为源二叉树的镜像。 二叉树的镜像定义： 源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 5 思路：创建栈，弹出一个，就交换他的左右节点，然后压入这两个节点，直到null 代码: import java.util.Stack; public class Solution { public void Mirro...

题目描述 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） 思路：递归，直到子树为Null。 代码： public class Solution { public boolean HasSubtree(TreeNode root1,TreeNode root2) { if(root2 == null || root1 ==null){ return false; } if(root1.val == root2.val){ if(judge(roo...