题目：牛客网 解题思路： 先排序，在输出第三大的数值。使用了快排    package offer; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { public static int quickSort(int[] data, int k){ int begin = 0, end = data.length - 1; int pos = 0; while (begin <= end) { pos = partion(data, begin...

题目：牛客网 解题思路： 遍历字符串，对每一个字符判断是否为数字 如果是数字则更新记录长度加一，记录其位置，与最大长度作比较取大的长度 如果不是数字则记录长度更新为0  import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); while(in.hasNext()){ String str = in.nextLine(); int end...

题目：牛客网 解题思路：（来源：https://leetcode-cn.com/problems/palindrome-partitioning/solution/hui-su-you-hua-jia-liao-dong-tai-gui-hua-by-liweiw/） 搜索问题主要使用回溯法。 回溯法思考的步骤： 1、画递归树； 2、根据自己画的递归树编码。    import java.util.ArrayList; public class Main { public static boolean isPalindrome(String s) { if (null == s || s.le...

题目：牛客网 解题思路： 使用动态规划， 2个字符串中短字符串的长度作为数组(record)的行数 长字符串的长度作为数组(record)的列数 判断两个字符是否相等，若不相等，record[i][j]=0；若相等，需要注意row==0或col==0的情况，此时,record[i][j]==1； i!=0且j!=0的时候，record[i][j]=record[i-1][j-1]+1      a b c d e f   a 1 0 0 0 0 0   a 1 0 0 0 0 0   b 0 2 0 0 0 0   c 0 0 3 0 0 0         import java.util....

题目：牛客网   import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); while(in.hasNext()){ String str = in.nextLine(); String[] arr = str.split(" "); System.out.println(arr[arr.length-1].lengt...

题目：牛客网 解题思路： 从每个元素遍历gas数组，例如0->gas.len-1，1->gas.len-1->1，2->gas.len-1->2...，在遍历的过程中若cost[j] > gas[j]+more，则从元素i无法走完环形路，如果在一次循环中满足条件即flag==true,则直接返回下标，否则进入下一个元素的循环。  public class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { for(int i = 0 ; i < gas.length; i+...

题目：牛客网 解题思路： 利用递增栈，可参考https://blog.csdn.net/qq_17550379/article/details/85093224 这种解法显然很慢，我们有一种更好的思路就是通过递增栈。所谓的递增栈，就是栈中只存放递增序列。   我们首先将2加入到栈中，我们接着访问1，我们发现1比栈顶元素2小，所以我们将栈顶元素2弹出，并且记录此时的面积2。我们发现栈已经空了，所以我们要接着压栈。   接着我们通过不断遍历找到第二个递增栈。   我们接着访问2，我们发现此时2比栈顶元素6小，所以我们弹出栈顶元素6，并且记录此时的面积6*1=6。   此时栈中还有元素，我们发现此时...

题目：链接 解题思路： 链接：https://www.nowcoder.com/questionTerminal/c466d480d20c4c7c9d322d12ca7955ac 来源：牛客网主要思路是通过两次遍历找到所有可能的窗口（即从S中从start到end包含一个T），通过以下几个步骤实现：为了减少时间复杂度，用map记录T中所有字符出现的次数，使用count在S中寻找时计数，一旦找到一个T中的字符就count++，同时map中当前字符的次数减1，当count等于T的长度时，即找到了一个包含T的字符串，然后通过比较每个找到的字符串的长度，选择最短字符串，即为题中所求  public cl...

题目：牛客网 解题思路： 非递归借用栈     非递归：   import java.util.ArrayList; import java.util.Stack; /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public ArrayList<Integer> inorderTraversal(T...

题目：牛客网 解题思路： 链接：https://www.nowcoder.com/questionTerminal/32af374b322342b68460e6fd2641dd1b?f=discussion 来源：牛客网 要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。 如果P不存在左孩子和右孩子，则可以直接访问它； 或者P存在孩子，但是其孩子都已被访问过了，则同样可以直接访问该结点 若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了 每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。  import java.uti...

题目：牛客网 解题思路： 不需要辅助函数，简单易懂 后序遍历容器的最后一个数是根节点，中序遍历的根节点左边是左子树，右边是右子树， 后序遍历左子树节点值相邻，右子树节点值也相邻。由后序遍历最后一个值将中序遍历分成 左右两部分，再由这两部分的size将后序遍历分成左右两部分，递归即可  /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class S...

题目：牛客网  /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public static TreeNode buildTree(int[] preorder, int[] inorder) { if(inorder.length==0 || preorder.length == 0) return null; ...

题目：牛客网 解题思路： 递归 若当前结点无左右子树，则返回当前节点的值； 若当前结点有左右子树，则改变其左右子树的value值，将当前结点的value值乘10加到其左右子树的value值上，返回fun(left)+fun(right)； 若当前节点只有左子树或只有右子树，则改变其左或右子树的value值，将当前结点的value值乘10加到其左或右子树的value值上，返回fun(left)或fun(right)；    /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; ...

题目：牛客网 解题思路： （转载自：<a href="http://blog.csdn.net/linhuanmars/article/details/22969069" target="_blank">http://blog.csdn.net/linhuanmars/article/details/22969069）  * 这道题是求树的路径和的题目，不过和平常不同的是这里的路径不仅可以从根到某一个结点，  * 而且路径可以从左子树某一个结点，然后到达右子树的结点，就像题目中所说的可以起始和终结于任何结点。  * 在这里树没有被看成有向图，...