题目描述： 将给定的单链表L： L 0→L 1→…→L n-1→L n, 重新排序为： L 0→L n →L 1→L n-1→L 2→L n-2→… 要求使用原地算法，并且不改变节点的值 例如： 对于给定的单链表{1,2,3,4}，将其重新排序为{1,4,2,3}.   解题思路： 1、把链表分成两部分，如1->2->3->4->5->null，分成l1 : 1->2->3->null，和l2 : 4->5->null 2、将第二个链表反转， 所以l2  :  5->4->null 3、将2个链表合并  /** * Def...

题目描述： 求给定二叉树的最小深度。最小深度是指树的根结点到最近叶子结点的最短路径上结点的数量。   解题思路： 递归 与求最大深度稍有不同，需要考虑左子树为空或右子树为空的情况。  /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int run(TreeNode root) { if(root =...

非递归 需要利用栈 一开始将root入栈； 循环结束条件：栈空； 每次循环，先使栈顶元素出栈，将其数值加入list中，再将其右结点入栈，左结点入栈，因为前序遍历是先根再左后右，入栈顺序要先右后左；  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; } * } */ publi...

题目描述： 判断给定的二叉树是否是平衡的 在这个问题中，定义平衡二叉树为每个节点的左右两个子树高度差的绝对值不超过1的二叉树   平衡二叉树：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 解题思路： 主要方法是递归，平衡二叉树不仅左右两个子树的深度差不大于1，其左右子树也都是平衡二叉树。 判断以当前节点为根节点的树，其左右子树的深度差是否大于1 如果大于1，则证明不是平衡二叉树，直接返回false； 如果不大于1，则需要判断其左子树是否是平衡二叉树以及右子树是否是平衡二叉树（递归）；      /** * Definition for bina...

题目描述： 给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历） 例如： 给定的二叉树是{3,9,20,#,#,15,7},  3 / 9 20 / 15 7 该二叉树层序遍历的结果是 [ [3], [9,20],[15,7]]   解题思路： 使用队列，这个题与普通的层序遍历稍有不同，最后返回的结果是list的集合，每一个list是一层的遍历（从左到右） 普通的层序遍历（一个list)只需要使用队列，进出进出即可， 每出一个node将其值添加到list中，直到队列变为空。 而现在，我们需要知道每一层有多少个node，具体实现看一下代码。  import java.util...

import java.util.List; import java.util.ArrayList; import java.util.Stack; /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<Integer> inorderTraversal(TreeNode root...

二叉查找树    二叉查找树(Binary Search Tree)，(又:二叉搜索树，二叉排序树)它或者是一棵空树，或者是具有下列性质的二叉树: 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树     解题思路： 利用中序遍历，如果是二叉搜索树，其中序遍历的结果一定是升序的，只需要将中序遍历稍加改变，在每个元素出栈时与前一个元素比较，看其是否大于前一个元素。    import java.util.Stack; /** * Definition for binary tree *...

题目：牛客网链接 解题思路：（图片来源：https://www.cnblogs.com/hapjin/p/5572483.html）      import java.util.Scanner; public class Main { public static int longestCommonSubsquence(String str1, String str2){ //第一行和第一列要置0 int m = str1.length()+1; int n = str2.length()+1; int[][] dp = new int[m][n]; for(int i = 0; i < ...

题目：牛客网   解题思路：（图片来源：https://www.cnblogs.com/frankchenfu/p/7107019.html）   // write your code here import java.util.Scanner; public class Main { public static int longestupSubsquence(int[] arr){ int len = arr.length; if(len==0) return 0; int[] num = new int[len]; num[0]=1; for(int i = 1; i < len; ...

题目：牛客网   解题思路： 因为一次只能走1步或2步，所以n个阶梯的最后一步肯定是1步或2步，因此 f(n)=f(n-1)+f(n-2)，一开始尝试用递归的方法，但是超时，之后采用一个数组来存储f(1),f(2)....f(n),是一个斐波那契数列，这样就避免了重复的计算。   递归法：（超时） public static int climbStairs(int n) { if(n == 0){ return 0; } else if(n == 1){ return 1; } else if(n == 2){ return 2; } else{ return climbStairs(n-2)...

题目：牛客网    解题思路： 链接：https://www.nowcoder.com/questionTerminal/fe6b651b66ae47d7acce78ffdd9a96c7?f=discussion 来源：牛客网 递归法，问题转换为先固定第一个字符，求剩余字符的排列；求剩余字符排列时跟原问题一样。 (1) 遍历出所有可能出现在第一个位置的字符（即：依次将第一个字符同后面所有字符交换）； (2) 固定第一个字符，求后面字符的排列（即：在第1步的遍历过程中，插入递归进行实现）。 需要注意的几点： (1) 先确定递归结束的条件，例如本题中可设begin == str.size() - ...

题目：牛客网   解题思路： 链接：https://www.nowcoder.com/questionTerminal/2b7995aa4f7949d99674d975489cb7da?f=discussion 来源：牛客网 注意观察前后2行的位置关系 triangle[i][j]=min(triangle[i+1][j], triangle[i+1][j+1])+triangle[i][j] 给定一个三角形，找出从顶到底的最小路径和，每一步可以从上一行移动到下一行相邻的数字     [                              [2],            [2],    ...

题目：牛客网 解题思路： 输入有2个属性，分别是用户名和成绩 1、定义一个class Student ，包含两个属性，分别是name和score 2、定义一个list，其元素是Student类，按照输入的内容将用户添加到list中 3、使用Collections容器进行排序，因为要按照score属性进行排序，需要提供Comparator    package offer; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.Scanner;...

题目：牛客网 解题思路： 大数位数最多的数值最大，若位数相同则从第一位开始比较，相同位的数字大的数值大。 与成绩排序相似，对Comparator做相应的修改即可。 1、大数无法直接比较，需要用String来表示 2、将大数放到一个list中 3、使用Collections对list进行排序，Comparator:用位数即string的长度作为排序的依据  import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.Scanner; public c...