欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指offer题目答案集合

程序员文章站 2022-07-10 10:26:33
...
package org.nix.learn.offer;

import org.junit.jupiter.api.Test;
import sun.rmi.transport.tcp.TCPChannel;

import java.util.*;
import java.util.concurrent.*;

/**
 * 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,
 * 每一列都按照从上到下递增的顺序排序。请完成一个函数,
 * 输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
 *
 * @author zhangpei
 * @version 1.0
 * @date 2018/10/8
 */
public class Solution {

    public static boolean Find(int target, int[][] array) {
        int len = array.length;

        if (array[0].length == 0 || array[0][0] > target) {
            return false;
        }
        if (array[0][len - 1] < target) {
            if (serch(target, array, len, len)) {
                return true;
            }
        }
        for (int i = 1; i < len; i++) {
            // 找到在第一排找到一个大于他的值,那么存在
            // 等于他的值就在i-1列中的
            if (array[0][i] > target) {
                if (serch(target, array, len, i)) {
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean serch(int target, int[][] array, int len, int i) {
        for (int[] anArray : array) {
            if (anArray[i - 1] == target) {
                return true;
            }
            if (anArray[len - 1] > target) {
                for (int k = len - 1; k > 0; k--) {
                    if (anArray[k] == target) {
                        return true;
                    }
                }
            }
        }
        return false;
    }


    // -------------------------------------------------------

    /**
     * 请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
     *
     * @param str
     * @return
     */
    public String replaceSpace(StringBuffer str) {
        return str.toString().replace(" ", "%20");
    }

    // -------------------------------------------------------

    /**
     * 输入一个链表,按链表值从尾到头的顺序返回一个ArrayList
     */
    private class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode() {
        }
    }

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        while (listNode != null) {
            list.add(listNode.val);
            listNode = listNode.next;
        }
        int len = list.size();
        ArrayList<Integer> returnV = new ArrayList<>(len);
        for (int i = len - 1; i >= 0; i--) {
            returnV.add(list.get(i));
        }
        return returnV;
    }

    public ArrayList<Integer> printListFromTailToHeadTwo(ListNode listNode) {
        Stack<Integer> stack = new Stack<>();
        while (listNode != null) {
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        int len = stack.size();
        ArrayList<Integer> va = new ArrayList<>(len);
        while (true) {
            try {
                Integer value = stack.peek();
                if (value == null) {
                    return va;
                }
                va.add(stack.pop());
            } catch (Exception e) {
                return va;
            }
        }
    }

    // -------------------------------------------------------

    /**
     * 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
     * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
     */
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre.length == 0 || in.length == 0) {
            return null;
        }
        TreeNode node = new TreeNode(pre[0]);
        for (int i = 0; i < in.length; i++) {
            if (pre[0] == in[i]) {
                node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
            }
        }
        return node;
    }

    @Test
    public void reConstructBinaryTreeTest() {
        int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] in = {4, 7, 2, 1, 5, 3, 8, 6};
        reConstructBinaryTree(pre, in);
        System.out.println();
    }

    // -------------------------------------------------------

    /**
     * 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。
     * 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
     *
     * @param array
     * @return
     */
    public int minNumberInRotateArray(int[] array) {
        int len = array.length;
        if (len == 0) {
            return 0;
        }
        Integer integer = null;
        for (int value : array) {
            if (integer == null) {
                integer = value;
            } else {
                if (integer > value) {
                    return value;
                } else {
                    integer = value;
                }
            }
        }
        return 0;
    }

    @Test
    public void minNumberInRotateArray() {
        System.out.println(minNumberInRotateArray(new int[]{3, 4, 5, 1, 2}));
    }

    // -------------------------------------------------------

    /**
     * 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
     */

    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
    }

    public int pop() {
        List<Integer> integers = new ArrayList<>(stack2.size());
        while (!stack2.empty()) {
            integers.add(stack2.pop());
        }
        while (!stack1.empty()) {
            stack2.push(stack1.pop());
        }
        for (int i = integers.size() - 1; i >= 0; i--) {
            stack2.push(integers.get(i));
        }
        return stack2.pop();
    }

    @Test
    public void stackTest() {
        for (int i = 0; i < 20; i++) {
            push(i);
        }
        for (int i = 0; i < 10; i++) {
            System.out.print(pop() + " ");
        }
        for (int i = 20; i < 40; i++) {
            push(i);
        }
        for (int i = 0; i < 30; i++) {
            System.out.print(pop() + " ");
        }
    }

    /**
     * 大家都知道斐波那契数列,现在要求输入一个整数n,
     * 请你输出斐波那契数列的第n项(从0开始,第0项为0)。
     * n<=39
     *
     * @param n
     * @return
     */
    public int fibonacci(int n) {

        if (n <= 0) {
            return 0;
        }

        if (0 < n && n <= 2) {
            return 1;
        }

        int v1 = 0;
        int v2 = 1;

        for (int i = 2; i < n; i++) {
            int temp = v1 + v2;
            v1 = v2;
            v2 = temp;
        }
        return v2 + v1;
    }

    @Test
    public void fidbonacciTest() {
        System.out.println(fibonacci(6));
    }

    /**
     * 一只青蛙一次可以跳上1级台阶,也可以跳上2级。
     * 求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)
     *
     * @param n
     * @return
     */
    public int jumpFloor(int n) {
        if (n <= 0) {
            return 0;
        }

        if (n <= 1) {
            return 1;
        }

        if (n == 2) {
            return 2;
        }

        int v1 = 1;
        int v2 = 2;

        for (int i = 3; i < n; i++) {
            int temp = v1 + v2;
            v1 = v2;
            v2 = temp;
        }
        return v2 + v1;
    }

    /**
     * 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
     * <p>
     * 链接:https://www.nowcoder.com/questionTerminal/22243d016f6b47f2a6928b4313c85387
     * 来源:牛客网
     * <p>
     * 因为n级台阶,第一步有n种跳法:跳1级、跳2级、到跳n级
     * 跳1级,剩下n-1级,则剩下跳法是f(n-1)
     * 跳2级,剩下n-2级,则剩下跳法是f(n-2)
     * 所以f(n)=f(n-1)+f(n-2)+...+f(1)
     * 因为f(n-1)=f(n-2)+f(n-3)+...+f(1)
     * 所以f(n)=2*f(n-1)
     *
     * @param target
     * @return
     */
    public int jumpFloorII(int target) {
        return (int) Math.pow(2, target - 1);
    }

    /**
     * 输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
     *
     * @param n
     * @return
     */
    public int numberOf1(int n) {
        long start = System.currentTimeMillis();
        int temp = n;
        int mi = 0;
        int bijiao;
        while (temp >= (bijiao = (int) Math.pow(2, mi))) {
            if (temp == bijiao) {
                return 1;
            }
            mi++;
        }
        mi--;
        int number = 0;
        while (temp != 0) {
            // 如果相减大于0说明符合要求
            int pow = (int) Math.pow(2, mi);
            if (temp - pow < 0) {
                mi--;
                continue;
            }
            temp = temp - pow;
            mi--;
            number++;
        }
        if (n < 0) {
            return ++number;
        }
        start = System.currentTimeMillis() - start;
        System.out.println(start);
        return number;
    }

    @Test
    public void numberOf1Test() {
        System.out.println(numberOf1(1000000000));
    }

    /**
     * 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
     *
     * @param base
     * @param exponent
     * @return
     */
    public double Power(double base, int exponent) {
        if (exponent == 0) {
            return 1;
        }
        if (base == 0) {
            return 0;
        }
        double temp = base;
        if (exponent > 0) {
            while (exponent > 1) {
                temp *= base;
                exponent--;
            }
        } else {
            while (exponent < 1) {
                temp /= base;
                exponent++;
            }
        }
        return temp;
    }

    /**
     * 输入一个链表,输出该链表中倒数第k个结点。
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode FindKthToTail(ListNode head, int k) {
        int size = 0;
        ListNode temp = head;
        while (temp != null) {
            temp = temp.next;
            size++;
        }
        System.out.println(size);
        size = size - k;
        System.out.println(size);
        if (size < 0) {
            return null;
        }
        while (size > 0) {
            head = head.next;
            size--;
        }
        return head;
    }

    @Test
    public void FindKthToTailTest() {
        ListNode node = new ListNode(1);
        node.next = new ListNode(1);
        node.next.next = new ListNode(3);
        node.next.next.next = new ListNode(4);
        node.next.next.next.next = new ListNode(5);
        node = deleteDuplication(node);
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }

    }

    /**
     * 输入一个链表,反转链表后,输出新链表的表头。
     *
     * @param head
     * @return
     */
    public ListNode ReverseList(ListNode head) {
        if (head == null) {
            return null;
        } else if (head.next == null) {
            return head;
        }
        ListNode node = ReverseList(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }

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

    /**
     * 输入一棵二叉树,求该树的深度。
     * 从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,
     * 最长路径的长度为树的深度。
     */
    public int TreeDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = TreeDepth(root.left);
        int rigth = TreeDepth(root.right);
        return left > rigth ? left + 1 : rigth + 1;
    }

    /**
     * 在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。
     * 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
     *
     * @param pHead
     * @return
     */
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null || pHead.next == null) {
            return pHead;
        }
        // 创建一个头节点 p1记录没有重复的节点
        ListNode p1 = new ListNode();
        p1.next = null;
        ListNode head = p1;
        // p2用于跳过重复的节点
        ListNode p2 = pHead;
        while (p2 != null) {
            if (p2.next != null && p2.val == p2.next.val) {
                while (p2.next != null && p2.val == p2.next.val) {
                    p2 = p2.next;
                }
                // 跳过重复的最后个节点
                p2 = p2.next;
                //防止链表尾部出现重复值,p2==null跳出循环而p1没有跳过尾部重复
                p1.next = p2;
            } else {
                // 如果没有重复
                p1.next = p2;
                p1 = p2;
                p2 = p2.next;
            }
        }
        // 返回时去掉头节点
        return head.next;
    }

    /**
     * HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。
     * 今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,
     * 当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,
     * 并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。
     * 给一个数组,返回它的最大连续子序列的和,你会不会被他忽悠住?(子向量的长度至少是1)
     *
     * @param array
     * @return
     */
    public int FindGreatestSumOfSubArray(int[] array) {
        if (array == null) {
            return 0;
        }
        int sum = array[0];
        int tempsum = array[0];
        int len = array.length;
        for (int i = 1; i < len; i++) {
            tempsum = tempsum < 0 ? array[i] : tempsum + array[i];
            sum = tempsum > sum ? tempsum : sum;
        }
        return sum;
    }

    /**
     * 写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。
     *
     * @param num1
     * @param num2
     * @return
     */
    public int Add(int num1, int num2) {
        if (num2 == 0) {
            return num1;
        }
        int tempNum2 = num2 > 0 ? num2 : -num2;
        for (int i = 0; i < tempNum2; i++) {
            if (num2 > 0) {
                num1++;
            } else {
                num1--;
            }
        }
        return num1;
    }

    /**
     * 从上往下打印出二叉树的每个节点,同层节点从左至右打印。
     * 公式: 父节点 i 左节点 2*i+1 右节点 2*i+2
     *
     * @param root
     * @return
     */
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                list.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return list;
    }
}

 

相关标签: offer