1.输入一个链表,按链表从尾到头的顺序返回一个ArrayList。
链表:
一种重要的数据结构,HashMap等集合的底层结构都是链表结构。链表以结点作为存储单元,这些存储单元可以是不连续的。每个结点由两部分组成:存储的数值+前序结点和后序结点的指针。即有前序结点的指针又有后序结点的指针的链表称为双向链表,只包含后续指针的链表为单链表,本文总结的均为单链表的操作。
单链表结构:
Java中单链表采用创建Node实体类的方法,其中val为存储的数据,next为下一个节点的指针:
class Node {
int val;
Node next = null;
Node(int val) {
this.val = val;
}
}
java实现:
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
//创建集合储存链表
List<Integer> list=new ArrayList<Integer>();
while(listNode!=null){
list.add(listNode.val);
listNode = listNode.next ;
}
//使用集合工具类方法reverse()反转集合
Collections.reverse(list);
return (ArrayList<Integer>) list;
}
}
2.输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
二叉树:
二叉树是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。
下图展示了一棵普通二叉树:
二叉树特点
由二叉树定义以及图示分析得出二叉树有以下特点:
1)每个结点最多有两颗子树,所以二叉树中不存在度大于2的结点。
2)左子树和右子树是有顺序的,次序不能任意颠倒。
3)即使树中某结点只有一棵子树,也要区分它是左子树还是右子树。
满二叉树
满二叉树:在一棵二叉树中。如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。
满二叉树的特点有:
1)叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
2)非叶子结点的度一定是2。
3)在同样深度的二叉树中,满二叉树的结点个数最多,叶子数最多。
完全二叉树
对一颗具有n个结点的二叉树按层编号,如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树。
下图展示一棵完全二叉树:
二叉树遍历
-前序遍历
前序遍历通俗的说就是从二叉树的根结点出发,当第一次到达结点时就输出结点数据,按照先向左在向右的方向访问。
前序遍历输出为:ABDHIEJCFG
-中序遍历
中序遍历就是从二叉树的根结点出发,当第二次到达结点时就输出结点数据,按照先向左在向右的方向访问。
中序遍历输出为:HDIBJEAFCG
-后序遍历
后序遍历就是从二叉树的根结点出发,当第三次到达结点时就输出结点数据,按照先向左在向右的方向访问。
后序遍历输出为:HIDJEBFGCA
-层序遍历
层次遍历就是按照树的层次自上而下的遍历二叉树。
层次遍历结果为:ABCDEFGHIJ
例:
前序序列{1,2,4,7,3,5,6,8} = pre
中序序列{4,7,2,1,5,3,8,6} = in
- 根据当前前序序列的第一个结点确定根结点,为 1
- 找到 1 在中序遍历序列中的位置,为 in[3]
- 切割左右子树,则 in[3] 前面的为左子树, in[3] 后面的为右子树
- 则切割后的左子树前序序列为:{2,4,7},切割后的左子树中序序列为:{4,7,2};切割后的右子树前序序列为:{3,5,6,8},切割后的右子树中序序列为:{5,3,8,6}
- 对子树分别使用同样的方法分解,递归使用
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
//输入前序遍历Pre[],中序遍历in[]
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
//判断遍历数组是否有值
if(pre == null || in == null || pre.length == 0 || in.length == 0){
return null;
}
//调用建树方法
return buildTree(pre, in, 0, pre.length - 1, 0, in.length - 1);
}
/**
* @param pre 前序遍历数组
* @param in 中序遍历数组
* @param preStart 前序头下标
* @param preEnd 前序尾下标
* @param inStart 中序头下标
* @param inEnd 前序尾下标
* @return TreeNode 二叉树对象
*/
public TreeNode buildTree(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd){
//开始根节点
TreeNode root = new TreeNode(pre[preStart]);
int rootIn = 0;
//找中序遍历根节点位置
for(; rootIn < in.length; rootIn++){
if(in[rootIn] == root.val){
break;
}
}
//分左右树
int leftLength = rootIn - inStart;
int rightLength = inEnd - rootIn;
//左右树再分左右树,递归调用建树方法
if(leftLength > 0){
root.left = buildTree(pre, in, preStart + 1, preStart + leftLength, inStart, rootIn - 1);
}
if(rightLength > 0){
root.right = buildTree(pre, in, preStart + leftLength + 1, preEnd, rootIn + 1, inEnd);
}
//返回二叉树对象
return root;
}
//main函数测试
public static void main(String[] args) {
int[] pre={1,2,4,7,3,5,6,8};
int[] in={4,7,2,1,5,3,8,6};
TreeNode tree= new Solution().reConstructBinaryTree(pre, in);
System.out.println(" "+tree.val);
System.out.println(" "+tree.left.val+" "+tree.right.val);
System.out.println(" "+tree.left.left.val+" "+tree.right.left.val+" "+tree.right.right.val);
System.out.println(""+tree.left.left.right.val+" "+tree.right.right.left.val);
}
}
测试输出结果为:
2. 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
分析:
https://www.nowcoder.com/questionTerminal/54275ddae22f475981afa2244dd448c6?answerType=1&f=discussion来源:牛客网
队列的特性是:“先入先出”,栈的特性是:“先入后出”
当我们向模拟的队列插入数 a,b,c 时,假设插入的是 stack1,此时的栈情况为:
- 栈 stack1:{a,b,c}
- 栈 stack2:{}
当需要弹出一个数,根据队列的"先进先出"原则,a 先进入,则 a 应该先弹出。但是此时 a 在 stack1 的最下面,将 stack1 中全部元素逐个弹出压入 stack2,现在可以正确的从 stack2 中弹出 a,此时的栈情况为:
- 栈 stack1:{}
- 栈 stack2:{c,b}
继续弹出一个数,b 比 c 先进入,b 弹出,注意此时 b 在 stack2 的栈顶,可直接弹出,此时的栈情况为:
- 栈 stack1:{}
- 栈 stack2:{c}
此时向模拟队列插入一个数 d,还是插入 stack1,此时的栈情况为:
- 栈 stack1:{d}
- 栈 stack2:{c}
弹出一个数,c 比 d 先进入,c 弹出,注意此时 c 在 stack2 的栈顶,可直接弹出,此时的栈情况为:
- 栈 stack1:{d}
- 栈 stack2:{c}
根据上述栗子可得出结论:
- 当插入时,直接插入 stack1
- 当弹出时,当 stack2 不为空,弹出 stack2 栈顶元素,如果 stack2 为空,将 stack1 中的全部数逐个出栈入栈 stack2,再弹出 stack2 栈顶元素
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if (stack2.size()<=0) {
while (stack1.size()!=0) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
3. 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
(1)直接找:
因为是递增数组,所以前一个比后一个小,旋转后只有旋转的地方前面比后面大,所以直接找前面比后面小的下标,下标加1就是这个数组最小的数;
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if (array.length==0) {
return 0;
}
for (int i = 0; i < array.length-1; i++) {
if (array[i]>array[i+1]) {
return array[i+1];
}
}
return array[0];
}
public static void main(String[] args) {
int[] array={3,4,5,1,2};
int a= new Solution().minNumberInRotateArray(array);
System.out.println(a);
}
}
(2)使用数组排序后查找:
采用工具类Arrays的sort方法排序后,这个数组就是由小到大排序的,直接输出第一个数,就是最小数;
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if (array.length==0) {
return 0;
}
Arrays.sort(array);
return array[0];
}
public static void main(String[] args) {
int[] array={3,4,5,1,2};
int a= new Solution().minNumberInRotateArray(array);
System.out.println(a);
}
}
(3)使用Java中的PriorityQueue(优先队列)类:
将数组存入优先队列中,使用poll方法输出第一个数,优先队列自动进行排序,输出的数就是最小数;
import java.util.PriorityQueue;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if (array.length==0) {
return 0;
}
PriorityQueue<Integer> queue=new PriorityQueue<Integer>();
for (int i = 0; i < array.length; i++) {
queue.add(array[i]);
}
return queue.poll();
}
public static void main(String[] args) {
int[] array={3,4,5,1,2};
int a= new Solution().minNumberInRotateArray(array);
System.out.println(a);
}
}
(4)使用二分查找:
注:
非递减序列并不能找到最小值,因为对于{3, 3, 3, 3, 3, 1, 3} 和 {3, 1,3, 3, 3, 3, 3},二分法并不能判断范围向哪边收缩
二分查找用于查找有序的数组中的值,题目所给数组在两段范围内有序,我们可以将给定数组分为两种情况:
- 其实并没有旋转,例如 {1,2,3,4,5},旋转后也是 {1,2,3,4,5},这样可以直接使用二分查找
- 如题所示,旋转了一部分,例如 {1,2,3,4,5},旋转后为 {3,4,5,1,2},需要限定特殊条件后使用二分查找
当数组如情况 1,有个鲜明的特征,即数组左边元素 < 数组右边元素,这时我们直接返回首元素即可
当数组如情况 2,此时有三种可能找到最小值:
- 下标为 n+1 的值小于下标为 n 的值,则下标为 n+1 的值肯定是最小元素
- 下标为 n 的值小于下标为 n-1 的值,则下标为 n 的值肯定是最小元素
- 由于不断查找,数组查找范围内的值已经全为非降序(退化为情况1)
再讨论每次二分查找时范围的变化,由于情况数组的情况 1 能直接找到最小值,需要变化范围的肯定是情况 2:
- 当下标为 n 的值大于下标为 0 的值,从 0 到 n 这一段肯定是升序,由于是情况 2,最小值肯定在后半段
- 当下标为 n 的值小于下标为 0 的值,从 0 到 n 这一段不是升序,最小值肯定在这一段