• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

剑指 Offer 面试题06-10

互联网 diligentman 1周前 (10-17) 12次浏览
剑指 Offer 面试题06-10

点击关注我们获取更多面试编程题









剑指 Offer 面试题06-10

剑指 Offer 面试题06-10

      剑指 Offer 上面的编程题目越来越受大厂面试官喜爱,熟练地掌握里面的题目是非常有必要的,尤其是那些想进大厂的程序员

剑指 Offer 面试题06-10




06





面试题6-从尾到头打印链表

    输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。

输入:head = [1,3,2]输出:[2,3,1]


解答情况

1 经典解法-使用栈来解决

   栈有先进后出的特性,遍历链表,逐个压栈,然后依次取出栈中的元素,放入到一个新的数组

剑指 Offer 面试题06-10

public int[] reversePrint(ListNode head) {    Stack<ListNode> stack = new Stack<>();    ListNode temp = head;    while (temp != null) {        stack.push(temp);        temp = temp.next;    }    int size = stack.size();    int[] res = new int[size];    for (int i = 0; i < size; i++) {        res[i] = stack.pop().val;    }    return res;}

2 使用链表的反转

       关于链表的反转其实解法也比较多,这里先列出简单的两种,一个是递归的,一个是非递归的。

      2.1 递归方法:

public ListNode reverseList(ListNode head) {    if (head == null || head.next == null)        return head;    ListNode tempList = reverseList(head.next);    head.next.next = head;    head.next = null;    return tempList;}

      2.2 非递归方法

public ListNode reverseList(ListNode head) {    ListNode pre = null;    while (head != null) {        ListNode next = head.next;        head.next = pre;        pre = head;        head = next;    }    return pre;}

3 链表的逆序输出,同时把元素存入到数组中


       链表的逆序输出很简单,如下代码所示就是链表的逆序输出。


public void reversePrint(ListNode head) {    if (head == null)        return;    reversePrint(head.next);    System.out.println(head.val);}

      但是题目要求的是返回一个新的数组,因此需要改造成如下方法:


public int[] reversePrint(ListNode head) {    int cout = length(head);    int[] res = new int[cout];    reversePrintHelper(head, res, cout - 1);    return res;}
//计算链表的长度public int length(ListNode head) { int cout = 0; ListNode dummy = head; while (dummy != null) { cout++; dummy = dummy.next; } return cout;}
public void reversePrintHelper(ListNode head, int[] res, int index) { if (head == null) return; reversePrintHelper(head.next, res, index - 1); res[index] = head.val;    }




07





面试题7-重建二叉树

    输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。


例如,给出

前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树:

    3   /   9  20    /     15   7


解答情况

先序遍历:根节点→左子树→右子树。

中序遍历:左子树→根节点→右子树。

后续遍历:左子树→右子树→根节点。


剑指 Offer 面试题06-10

    经验总结:二叉树的问题一般都是分治思想,递归去做。因为二叉树本身就是递归定义的。

1. 最容易理解的方式-截取数组的方式

public TreeNode buildTree(int[] preorder, int[] inorder) {    //把前序遍历的值和中序遍历的值放到list    List<Integer> preorderList = new ArrayList<>();    List<Integer> inorderList = new ArrayList<>();    for (int i = 0; i < preorder.length; i++) {        preorderList.add(preorder[i]);        inorderList.add(inorder[i]);    }    return helper(preorderList, inorderList);}
private TreeNode helper(List<Integer> preorderList, List<Integer> inorderList) { if (inorderList.size() == 0) return null; //前序遍历的第一个值就是根节点 int rootVal = preorderList.remove(0); //创建跟结点 TreeNode root = new TreeNode(rootVal); //查看根节点在中序遍历中的位置,然后再把中序遍历的数组劈两半,前面部分是 //根节点左子树的所有值,后面部分是根节点右子树的所有值 int mid = inorderList.indexOf(rootVal); //[0,mid)是左子树的所有值,inorderList.subList(0, mid)表示截取inorderList //的值,截取的范围是[0,mid),包含0不包含mid。 root.left = helper(preorderList, inorderList.subList(0, mid)); //[mid+1,inorderList.size())是右子树的所有值, // inorderList.subList(mid + 1, inorderList.size())表示截取inorderList //的值,截取的范围是[mid+1,inorderList.size()),包含mid+1不包含inorderList.size()。 root.right = helper(preorderList, inorderList.subList(mid + 1, inorderList.size())); return root;}

2. 中级方式,不使用ArrayList,直接使用数组,使用数组边界的方式

注意如下几个变量:

左子树的长度是通过中序遍历的数组算出来的,

pivotIndex: 中序遍历中,根节点的位置

pivotIndex – inL:左子树的长度

import java.util.HashMap;import java.util.Map;
class TreeNode { int val; TreeNode left; TreeNode right;
TreeNode(int x) { val = x; }}

public class Solution {
// 使用全局变量是为了让递归方法少传一些参数,不一定非要这么做
private Map<Integer, Integer> reverses; private int[] preorder;
public TreeNode buildTree(int[] preorder, int[] inorder) { int preLen = preorder.length; int inLen = inorder.length;
// 可以不做判断,因为题目中给出的数据都是有效的 if (preLen != inLen) { return null; }
this.preorder = preorder;
// 以空间换时间,否则,找根结点在中序遍历中的位置需要遍历 reverses = new HashMap<>(inLen); for (int i = 0; i < inLen; i++) { reverses.put(inorder[i], i); }
return buildTree(0, preLen - 1, 0, inLen - 1); }
/** * 根据前序遍历数组的 [preL, preR] 和 中序遍历数组的 [inL, inR] 重新组建二叉树 * * @param preL 前序遍历数组的区间左端点 * @param preR 前序遍历数组的区间右端点 * @param inL 中序遍历数组的区间左端点 * @param inR 中序遍历数组的区间右端点 * @return 构建的新二叉树的根结点 */ private TreeNode buildTree(int preL, int preR, int inL, int inR) { if (preL > preR || inL > inR) { return null; } // 构建的新二叉树的根结点一定是前序遍历数组的第 1 个元素 int pivot = preorder[preL]; TreeNode root = new TreeNode(pivot);
int pivotIndex = reverses.get(pivot);
// 这一步得画草稿,计算边界的取值,必要时需要解方程,并不难 root.left = buildTree(preL + 1, preL + (pivotIndex - inL), inL, pivotIndex - 1); root.right = buildTree(preL + (pivotIndex - inL) + 1, preR, pivotIndex + 1, inR); return root; }}

3. 高级方式

 

3.1 使用栈的方式


       如果使用栈来解决首先要搞懂一个知识点,就是前序遍历挨着的两个值比如m和n,他们会有下面两种情况之一的关系。


1,n是m左子树节点的值。

2,n是m右子树节点的值或者是m某个祖先节点的右节点的值。


  • 对于第一个知识点我们很容易理解,如果m的左子树不为空,那么n就是m左子树节点的值。

  • 对于第二个问题,如果一个结点没有左子树只有右子树,那么n就是m右子树节点的值,如果一个结点既没有左子树也没有右子树,那么n就是m某个祖先节点的右节点,我们只要找到这个祖先节点就好办了。

public TreeNode buildTree(int[] preorder, int[] inorder) {    if (preorder.length == 0)        return null;    Stack<TreeNode> s = new Stack<>();    //前序的第一个其实就是根节点    TreeNode root = new TreeNode(preorder[0]);    TreeNode cur = root;    for (int i = 1, j = 0; i < preorder.length; i++) {        //第一种情况        if (cur.val != inorder[j]) {            cur.left = new TreeNode(preorder[i]);            s.push(cur);            cur = cur.left;        } else {            //第二种情况            j++;            //找到合适的cur,然后确定他的右节点            while (!s.empty() && s.peek().val == inorder[j]) {                cur = s.pop();                j++;            }            //给cur添加右节点            cur = cur.right = new TreeNode(preorder[i]);        }    }    return root;}

3.2 使用递归的方式-双指针的方式


private int in = 0;private int pre = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) { return build(preorder, inorder, Integer.MIN_VALUE);}
private TreeNode build(int[] preorder, int[] inorder, int stop) { if (pre >= preorder.length) return null; if (inorder[in] == stop) { in++; return null; }
TreeNode node = new TreeNode(preorder[pre++]); node.left = build(preorder, inorder, node.val); node.right = build(preorder, inorder, stop); return node;}





08





面试题8-二叉树的下一个节点

       给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

 

解答情况

方法一:暴力算法


  先找到根节点,然后求出整个二叉树的中序遍历,然后找下一个节点

public class Solution {    static ArrayList<TreeLinkNode> list = new ArrayList<>();    public TreeLinkNode GetNext(TreeLinkNode pNode){        // 第一步找出根节点        TreeLinkNode par = pNode;        while(par.next != null){            par = par.next;        }        // 第二步 中序遍历        InOrder(par);        // 第三部 找到下一个节点        for(int i=0;i<list.size();i++){            if(pNode == list.get(i)){                return i == list.size()-1?null:list.get(i+1);            }        }        return null;    }    void InOrder(TreeLinkNode pNode){        if(pNode!=null){            InOrder(pNode.left);            list.add(pNode);            InOrder(pNode.right);        }    }}

      

时间复杂度:剑指 Offer 面试题06-10
空间复杂度:剑指 Offer 面试题06-10

方法二:分析中序遍历下一个节点的特点


以该二叉树为例,中序遍历为:{D,B,H,E,I,A,F,C,G}

剑指 Offer 面试题06-10

仔细观察,可以把中序下一结点归为几种类型:
  1. 有右子树,下一结点是右子树中的最左结点,例如 B,下一结点是 H
  2. 无右子树,且结点是该结点父结点的左子树,则下一结点是该结点的父结点,例如 H,下一结点是 E
  3. 无右子树,且结点是该结点父结点的右子树,则我们一直沿着父结点追朔,直到找到某个结点是其父结点的左子树,如果存在这样的结点,那么这个结点的父结点就是我们要找的下一结点。例如 I,下一结点是 A;例如 G,并没有符合情况的结点,所以 G 没有下一结点

public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode) { // 1. if (pNode.right != null) { TreeLinkNode pRight = pNode.right; while (pRight.left != null) { pRight = pRight.left; } return pRight; } // 2. if (pNode.next != null && pNode.next.left == pNode) { return pNode.next; } // 3. if (pNode.next != null) { TreeLinkNode pNext = pNode.next; while (pNext.next != null && pNext.next.right == pNext) { pNext = pNext.next; } return pNext.next; } return null; }}

时间复杂度:剑指 Offer 面试题06-10
空间复杂度:剑指 Offer 面试题06-10

       


09





面试题9-用两个栈实现队列

        用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )



解答情况

  加入队尾 appendTail()函数:将数字 val 加入栈 A 即可。

  删除队首deleteHead()函数:有以下三种情况。

  • 当栈 B 不为空:B中仍有已完成倒序的元素,因此直接返回 B 的栈顶元素。

  • 否则,当 A 为空:即两个栈都为空,无元素,因此返回 -1−1 。

  • 否则:将栈 A 元素全部转移至栈 B 中,实现元素倒序,并返回栈 B 的栈顶元素。

剑指 Offer 面试题06-10

class CQueue {        //成员变量    Stack<Integer> A,B;
//构造方法 public CQueue() { A = new Stack<>(); B = new Stack<>(); }
public void appendTail(int value) { A.push(value); }
public int deleteHead() { if(B.isEmpty()){ if(A.isEmpty()){ return -1; } while(!A.isEmpty()){ B.push(A.pop()); } } return B.pop(); }}




10





面试题10-I 斐波那契数列

   写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:

F(0) = 0,   F(1) = 1F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

   斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

   答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1

 

解答情况

解题思路:

斐波那契数列的定义是 f(n + 1) = f(n) + f(n – 1),生成第 n 项的做法有以下几种:

1.  递归法:

  • 原理:把 f(n) 问题的计算拆分成 f(n-1) 和 f(n-2) 两个子问题的计算,并递归,以 f(0) 和 f(1) 为终止条件。

  • 缺点:大量重复的递归计算,例如 f(n) 和 f(n – 1) 两者向下递归需要 各自计算 f(n – 2) 的值。

2.  记忆化递归法:

  • 原理:在递归法的基础上,新建一个长度为 n 的数组,用于在递归时存储 f(0) 至 f(n) 的数字值,重复遇到某数字则直接从数组取用,避免了重复的递归计算。

  • 缺点:记忆化存储需要使用 O(N) 的额外空间。

3.  动态规划:

  • 原理:以斐波那契数列性质 f(n + 1) = f(n) + f(n – 1)为转移方程。

  • 从计算效率、空间复杂度上看,动态规划是本题的最佳解法。

动态规划解析:

  • 状态定义:设 dp 为一维数组,其中 dp[i] 的值代表 斐波那契数列第 i 个数字 。

  • 转移方程:dp[i + 1] = dp[i] + dp[i – 1] ,即对应数列定义 f(n + 1) = f(n) + f(n – 1);

  • 初始状态:dp[0] = 0, dp[1] = 1 ,即初始化前两个数字;

  • 返回值:dp[n],即斐波那契数列的第 n 个数字。


class Solution {    public int fib(int n) {        int a = 0, b = 1, sum;        for(int i = 0; i < n; i++){            sum = (a + b) % 1000000007;            a = b;            b = sum;        }        return a;    }}
       


10





面试题10-II 青蛙跳台阶问题

     一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

 

解答情况

   剑指 Offer 面试题06-10

     

     设跳上 n 级台阶有 f(n)种跳法。在所有跳法中,青蛙的最后一步只有两种情况:跳上 1 级或 2 级台阶。

  • 当为 1 级台阶:剩 n-1 个台阶,此情况共有 f(n-1) 种跳法;

  • 当为 2 级台阶:剩 n-2 个台阶,此情况共有 f(n-2) 种跳法。


f(n) 为以上两种情况之和,即 f(n)=f(n-1)+f(n-2) ,以上递推性质为斐波那契数列。

class Solution {    public int fib(int n) {        int a = 0, b = 1, sum;        for(int i = 0; i < n; i++){            sum = (a + b) % 1000000007;            a = b;            b = sum;        }        return a;    }}
       

END



剑指 Offer 面试题06-10




本文分享自微信公众号 – Java学习进阶手册(javastudyup)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。


喜欢 (0)