Kosmos

我以兴趣为饵,钓起生活的大鱼

目录
剑指offer_Part1
/    

剑指offer_Part1 有更新!

友情提示:代码在这里
本文参照该仓库学习,大家可以star

数组中重复的数字

在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字是重复的,也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

要求是时间复杂度 O(N),空间复杂度 O(1)。因此不能使用排序的方法,也不能使用额外的标记数组。
对于这种数组元素在 [0, n-1] 范围内的问题,可以将值为 i 的元素调整到第 i 个位置上进行求解。
以 (2, 3, 1, 0, 2, 5) 为例,遍历到位置 4 时,该位置上的数为 2,但是第 2 个位置上已经有一个 2 的值了,因此可以知道 2 重复

public boolean duplicate(int numbers[],int length,int [] duplication) {

        if(numbers==null || length ==0)
        {
            return false;
        }
        for(int i=0;i<numbers.length;i++)
        {
            while(numbers[i] != i)
            {
                if(numbers[i] == numbers[numbers[i]])
                {
                    duplication[0] =numbers[i];
                    return true;
                }
                Util.swap(numbers,i,numbers[i]);
            }
        }
        return false;
    }

二维数组中的查找

给定一个二维数组,其每一行从左到右递增排序,从上到下也是递增排序。给定一个数,判断这个数是否在该二维数组中。

该二维数组中的一个数,它左边的数都比它小,下边的数都比它大。因此,从右上角开始查找,就可以根据 target 和当前元素的大小关系来缩小查找区间,当前元素的查找区间为左下角的所有元素。

 public boolean Find(int target, int [][] array) {

        if(array==null||array.length==0||array[0].length == 0)
        {
            return false;
        }
        int rows = array.length-1;
        int cols = array[0].length-1;
        int row = 0,col = cols;
        while(row<=rows&&col>=0)
        {
            if(target < array[row][col])
            {
                col--;
            }else if(target >array[row][col])
            {
                row++;
            }else{
                return true;
            }
        }
        return false;
    }

替换空格

将一个字符串中的空格替换成 “%20”。

在字符串尾部填充任意字符,使得字符串的长度等于替换之后的长度。因为一个空格要替换成三个字符(%20),因此当遍历到一个空格时,需要在尾部填充两个任意字符。

令 P1 指向字符串原来的末尾位置,P2 指向字符串现在的末尾位置。P1 和 P2 从后向前遍历,当 P1 遍历到一个空格时,就需要令 P2 指向的位置依次填充 02%(注意是逆序的),否则就填充上 P1 指向字符的值。

从后向前遍是为了在改变 P2 所指向的内容时,不会影响到 P1 遍历原来字符串的内容。

public String replaceSpace(StringBuffer str) {

        int perlength = str.length()-1;

        for(int i=0;i<=perlength;i++)
        {
            if(str.charAt(i) == ' ')
            {
                str.append("  ");
            }
        }
        int nowlength = str.length()-1;
        while(perlength>=0&&nowlength>=perlength)
        {
            if(str.charAt(perlength)==' ')
            {
                str.setCharAt(nowlength--,'0');
                str.setCharAt(nowlength--,'2');
                str.setCharAt(nowlength--,'%');
            }else{
                str.setCharAt(nowlength--,str.charAt(perlength));
            }
            perlength--;
        }

        return str.toString();
    }

从尾到头打印链表

从尾到头反过来打印出每个结点的值。
使用递归

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {

        ArrayList<Integer> ret = new ArrayList<>();
        if(listNode==null)
        {
            return ret;
        }
        if(listNode.next == null)
        {
            ret.add(listNode.val);
        }else{
            ret = printListFromTailToHead(listNode.next);
            ret.add(listNode.val);
        }
        return ret;
    }

使用头插法
使用栈(最简单)

7 重建二叉树

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

前序遍历的第一个值为根节点的值,使用这个值将中序遍历结果分成两部分,左部分为树的左子树中序遍历结果,右部分为树的右子树中序遍历的结果。

8 二叉树的下一个结点

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

如果一个节点的右子树不为空,那么该节点的下一个节点是右子树的最左节点

否则,向上找第一个左链接指向的树包含该节点的祖先节点。

9 用两个栈实现队列

用两个栈来实现一个队列,完成队列的 Push 和 Pop 操作。

in 栈用来处理入栈(push)操作,out 栈用来处理出栈(pop)操作。一个元素进入 in 栈之后,出栈的顺序被反转。当元素要出栈时,需要先进入 out 栈,此时元素出栈顺序再一次被反转,因此出栈顺序就和最开始入栈顺序是相同的,先进入的元素先退出,这就是队列的顺序。

10 斐波那契数列

求斐波那契数列的第 n 项,n <= 39。
如果使用递归求解,会重复计算一些子问题。例如,计算 f(10) 需要计算 f(9) 和 f(8),计算 f(9) 需要计算 f(8) 和 f(7),可以看到 f(8) 被重复计算了。
递归是将一个问题划分成多个子问题求解,动态规划也是如此,但是动态规划会把子问题的解缓存起来,从而避免重复求解子问题。
考虑到第 i 项只与第 i-1 和第 i-2 项有关,因此只需要存储前两项的值就能求解第 i 项,从而将空间复杂度由 O(N) 降低为 O(1)。

10-2 矩形覆盖

我们可以用 21 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 21 的小矩形无重叠地覆盖一个 2*n 的大矩形,总共有多少种方法?找规律 f(n) = f(n-1)+f(n-2)

10-3 跳台阶

一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
找规律 f(n) = f(n-1)+f(n-2)

10-4 变态跳台阶

一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级… 它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
动态规划
数学推导

11 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。

例如数组 {3, 4, 5, 1, 2} 为 {1, 2, 3, 4, 5} 的一个旋转,该数组的最小值为 1。

在一个有序数组中查找一个元素可以用二分查找,二分查找也称为折半查找,每次都能将查找区间减半,这种折半特性的算法时间复杂度都为 O(logN)。

本题可以修改二分查找算法进行求解:

当 nums[m] <= nums[h] 的情况下,说明解在 [l, m] 之间,此时令 h = m;(由于之前有顺序性)
否则解在 [m + 1, h] 之间,令 l = m + 1。

如果数组元素允许重复的话,那么就会出现一个特殊的情况:nums[l] == nums[m] == nums[h],那么此时无法确定解在哪个区间,需要切换到顺序查找。例如对于数组 {1,1,1,0,1},l、m 和 h 指向的数都为 1,此时无法知道最小数字 0 在哪个区间。


标题:剑指offer_Part1
作者:ellenbboe
地址:https://zdone.top/articles/2019/04/05/1561009671258.html
有错的话联系我或者直接评论-.-

评论