剑指offer刷题记录(C++版本)（之一）

作者: 傑jay | 来源:发表于2019-08-26 21:25 被阅读0次

剑指offer刷题记(C++版本)

部分参考上文和牛客网讨论

为了在秋招的手撕代码环节中不出纰漏，把剑指offer从头刷一遍

1. 二维数组中查找数字。

题目：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路:从右上角即第0行第n列来入手，如果右上角的数字大于目标，那么最右边一列都不满足，则考虑前一列（col--），如果这个数小于目标，则最上面一行都不满足，则考虑下一行（row++），如果刚好是目标就可以输出了。

bool Find(int target, vector<vector<int> > array) {
        if(array.empty())    return false;     //空数组直接返回false
        int rows=array.size();   
        int cols=array[0].size();
        int row=0;
        int col=cols-1;
        while(row<rows&&col>=0)
        {
            if(array[row][col]==target)  return true;
            else if(array[row][col]>target)
            {
                col--;
            }
            else  row++;
        }
        return false;
    }

2.替换空格。

题目：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
思路:从后向前替换（从后往前，每个空格后面的字符只需要移动一次。从前往后，当遇到第一个空格时，要移动第一个空格后所有的字符一次；当遇到第二个空格时，要移动第二个空格后所有的字符一次；以此类推。所以总的移动次数会更多。本质上其实是先计算出替换后的长度后再使用原字符串填充，与前后填充的顺序无关），先遍历一遍统计空格的数目，然后扩张字符串使得可以放下替换后的字符，然后从后向前依次复制，非空格字符直接复制，空格字符用题目要求的替换。

 //C风格的字符串最后一个字符是\n，而且是记在字符串长度里的。
    void replaceSpace(char *str,int length) {
        int i=0;
        int cnt=0;
        if(length==0||str==nullptr) return ;     //空字符串 
        for(i=0;i<length;i++)      //统计空格数
        {
            if(str[i]==' ')
                cnt++;
        }
        if(cnt==0)  return;     //如果没有空格自然不用替换
        int newlength=length+2*cnt;     //新字符串的长度
        int index_new=newlength-1;
        int index_old=length-1;

        while(index_old>=0&&index_new>index_old)   //没有到头或者两个指针追上了
        {
            if(str[index_old]==' ')
            {
                //依次替换三个字符，并且把index_old--
                str[index_new--]='0';
                str[index_new--]='2';
                str[index_new--]='%';    
                index_old--;
            }
            else 
            {
                //如果不是空格直接复制就可以了
                str[index_new--]=str[index_old--];
            }
        }
    }

3. 从尾到头打印链表。

题目：输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
思路：1. 取出链表到一个新数组中 2.将数组倒置即可

vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> value;
        ListNode *p=NULL;
        p=head; #取链表头地址
        while(p!=NULL){
            value.push_back(p->val); //根据链表地址找到对应的值，使用push_back()函数为value数组尾端添加值
            p=p->next; //找到链表下一项的地址
        }
        //reverse(value.begin(),value.end()); //可使用C++自带的翻转函数对value值进行翻转
        int temp=0;
        int i=0,j=value.size()-1;
        while(i<j){
            temp=value[i];    //也可以用swap函数，swap(value[i],value[j]);
            value[i]=value[j];
            value[j]=temp;
            i++;
            j--;
        }
        return value;
    }

4.重建二叉树

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
知识点：关于二叉树的前序、中序、后序三种遍历
思路：本题的关键在于如何应用给定的中序遍历序列和前序遍历序列。先从实例分析如何重建二叉树
1. 前序遍历序列的第一个数“1”为根节点，处在中序遍历序列的第4位
2. 按照中序遍历序列，则{4,7,2}为左子树的中序遍历结果，{5,3,8,6}为右子树的中序遍历
3. 由于根节点处于中序遍历序列第4位，则前序序列第2位到第4位即{2,4,7}为左子树的前序遍历，第5位到末端{3,5,6,8}为右子树的前序遍历。
4. 由此又重新构成了两组新的前序和中序遍历序列，递归调用函数即可重建二叉树。
5. 注意当最后得到的子树只有一个节点时，返回节点即可

public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
    int vinlen=vin.size();
            if(vinlen==0)
                return NULL; //判断中序长度，其实就是为了在函数无子树时返回空，为递归做准备
            vector<int> left_pre,right_pre,left_vin,right_vin;
            TreeNode* head=new TreeNode(pre[0]); //创建根节点，根节点肯定是前序遍历的第一个数
            int gen=0;
            for(int i=0;i<vinlen;i++)//找到中序遍历根节点所在位置,存放于变量gen中
           {
                if (vin[i]==pre[0])
                {
                    gen=i;
                    break;
                }
            }
            //对于中序遍历，根节点左边的节点位于二叉树的左边，根节点右边的节点位于二叉树的右边
            //利用上述这点，对二叉树节点进行归并
            for(int i=0;i<gen;i++)
            {
                left_vin.push_back(vin[i]); //中序前gen个为左子树中序
                left_pre.push_back(pre[i+1]);//前序第2个到1+gen个为左子树前序
            }
            for(int i=gen+1;i<vinlen;i++)
            {
                right_vin.push_back(vin[i]);
                right_pre.push_back(pre[i]);
            }
            //和shell排序的思想类似，取出前序和中序遍历根节点左边和右边的子树
            //递归，再对其进行上述所有步骤，即再区分子树的左、右子子数，直到叶节点
           head->left=reConstructBinaryTree(left_pre,left_vin);
           head->right=reConstructBinaryTree(right_pre,right_vin);
          return head;
    }

5.用两个栈实现一个队列

题目：用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。
知识点：队列和栈的区别，简而言之就是栈为先进后出，队列为先进先出
思路：栈为先进后出，要实现队列的Push功能不需要进行改变，而为了实现出的功能，则需要将整个栈倒过来出栈，从而达到Pop效果。因此划分两个栈，stack1,stack2。
- 入队时，判断stack1是否为空，如不为空，将元素压入stack1；如为空，先将stack2元素倒回stack1，再将新元素压入stack1。
- 出队时，判断stack2是否为空，如不为空，则直接弹出顶元素；如为空，则将stack1的元素逐个“倒入”stack2，把stack1最后一个元素弹出并出队。

void push(int node) {
        if(stack1.empty()){ //栈1空有可能数据全在栈2
            while(!stack2.empty()){
                stack1.push(stack2.top());
                stack2.pop();
            }
        }
        stack1.push(node);
    }

    int pop() {
        if(stack2.empty()){ //栈2空有可能数据全在栈1
            while(!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int t=stack2.top();
        stack2.pop();
        return t;
    }

6.重旋转数组的最小数字

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
知识点：剑指Offer中有这道题目的分析。这是一道二分查找的变形的题目。
旋转之后的数组实际上可以划分成两个有序的子数组：前面子数组的大小都大于后面子数组中的元素
注意到实际上最小的元素就是两个子数组的分界线。本题目给出的数组一定程度上是排序的，因此我们试着用二分查找法寻找这个最小的元素。
思路：
1. 我们用两个指针left,right分别指向数组的第一个元素和最后一个元素。按照题目的旋转的规则，第一个元素应该是大于最后一个元素的（没有重复的元素）。
  但是如果不是旋转，第一个元素肯定小于最后一个元素。
2. 找到数组的中间元素。
  中间元素大于第一个元素，则中间元素位于前面的递增子数组，此时最小元素位于中间元素的后面。我们可以让第一个指针left指向中间元素。
  移动之后，第一个指针仍然位于前面的递增数组中。
  中间元素小于第一个元素，则中间元素位于后面的递增子数组，此时最小元素位于中间元素的前面。我们可以让第二个指针right指向中间元素。
  移动之后，第二个指针仍然位于后面的递增数组中。
  这样可以缩小寻找的范围。
3. 按照以上思路，第一个指针left总是指向前面递增数组的元素，第二个指针right总是指向后面递增的数组元素。
  最终第一个指针将指向前面数组的最后一个元素，第二个指针指向后面数组中的第一个元素。
  也就是说他们将指向两个相邻的元素，而第二个指针指向的刚好是最小的元素，这就是循环的结束条件。
  到目前为止以上思路很耗的解决了没有重复数字的情况，这一道题目添加上了这一要求，有了重复数字。
  因此这一道题目比上一道题目多了些特殊情况：
  我们看一组例子：｛1，0，1，1，1｝和｛1，1， 1，0，1｝都可以看成是递增排序数组｛0，1，1，1，1｝的旋转。
  这种情况下我们无法继续用上一道题目的解法，去解决这道题目。因为在这两个数组中，第一个数字，最后一个数字，中间数字都是1。
  第一种情况下，中间数字位于后面的子数组，第二种情况，中间数字位于前面的子数组。
  因此当两个指针指向的数字和中间数字相同的时候，我们无法确定中间数字1是属于前面的子数组（绿色表示）还是属于后面的子数组（紫色表示）。
  也就无法移动指针来缩小查找的范围。因此采用遍历的方式取得最小值

public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int size = rotateArray.size();
        if(size == 0){
            return 0;
        }//if
        int left = 0,right = size - 1;
        int mid = 0;
        // rotateArray[left] >= rotateArray[right] 确保旋转
        while(rotateArray[left] >= rotateArray[right]){
            // 分界点
            if(right - left == 1){
                mid = right;
                break;
            }//if
            mid = left + (right - left) / 2;
            // rotateArray[left] rotateArray[right] rotateArray[mid]三者相等
            // 无法确定中间元素是属于前面还是后面的递增子数组
            // 只能顺序查找
            if(rotateArray[left] == rotateArray[right] && rotateArray[left] == rotateArray[mid]){
                return MinOrder(rotateArray,left,right);
            }//if
            // 中间元素位于前面的递增子数组
            // 此时最小元素位于中间元素的后面
            if(rotateArray[mid] >= rotateArray[left]){
                left = mid;
            }//if
            // 中间元素位于后面的递增子数组
            // 此时最小元素位于中间元素的前面
            else{
                right = mid;
            }//else
        }//while
        return rotateArray[mid];
    }
private:
    // 顺序寻找最小值
    int MinOrder(vector<int> &num,int left,int right){
        int result = num[left];
        for(int i = left + 1;i < right;++i){
            if(num[i] < result){
                result = num[i];
            }//if
        }//for
        return result;
    }

7.斐波拉切数列

题目：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39 。
知识点：斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368........这个数列从第3项开始，每一项都等于前两项之和。
思路：
1. 最容易想到的方法就是递归，写法简单，但是递归在大数量之下的计算量无法想象，响应时间肯定满足不了要求。
2. 所以循环迭代虽然是最简单但最靠谱的方法。由此，需要时间基本上没有优势，如何节省资源就成了本题的关键问题

public:
    int Fibonacci(int n) {
        int f = 0, g = 1; //假设存在0项为0,0+1=1；依然满足条件
        while(n-->0) { //防止输入负数
            g += f; //求和得到第三项的值
            f = g - f; //为了得到第二项的值，用新得到的第三项值g减去第一项值f得到新的f值即为第二项值
        }
        return f;//返回新的第一项的值
    }

上面的代码非常的巧妙，即先算出n+1项裴波那切数列值，反过来求第n项并输出，代码简洁且功能正常

8.跳台阶问题

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
思路：非常明显的递归问题，跳上n级台阶的方法即跳上(n-1)级台阶的方法加上跳上(n-2)级台阶的方法。因此构成了类裴波那切数列，因此解题思路又同上题了。
然后通过实际的情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2，f(n) = f(n-1)+f(n-2) ,(n>2,n为整数)
两种方式实现：

递归方式实现：(运行时间578ms,占用内存488k)

public:
    int jumpFloor(int number) {
        if (number <= 0) {
            return false;
        } else if (number == 1) {
            return 1;
        } else if (number ==2) {
            return 2;
        } else {
            return  jumpFloor(number-1)+jumpFloor(number-2);
        }
    }

动态规划实现：（运行时间3ms，占用内存460k）

public:
    int jumpFloor(int number) {
        int f = 1, g = 1; //假设存在0项为0,1+1=2；依然满足条件
        while(number-->0) { //防止输入负数
            g += f; //求和得到第三项的值
            f = g - f; //为了得到第二项的值，用新得到的第三项值g减去第一项值f得到新的f值即为第二项值
        }
        return f;//返回新的第一项的值
    }

对比可见，动态规划不仅时间大大缩短，而且占用内存更小，而且不需要判断语句，代码优化可以说非常关键

9.变态跳台阶问题

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路：
F(N)=F(N-1)+F(N-2)+F(N-3)+...+F(1)
把N-1带入则可以得到：
F(N-1)=F(N-2)+F(n-3)+...+F(1)
两式相减呢？：
F(N)=2*F(N-1)
则这是一个等比数列啊,且F(1)=1，所以最后的结果就是一个幂次。
F(N)=2^(N-1)
所以本题其实有非常多的写法：

位移(虽然速度快简单，但是为0或者值过大会溢出)(3ms,480k)

public:
    int jumpFloorII(int number) {
                int a=1; return a<<(number-1);
    }

调用math模块，直接使用幂函数pow() 函数(3ms,488k)
double pow(double x, double y);用来计算以x 为底的 y 次方值，然后将结果返回。设返回值为 ret，则 ret = x^y。

#include <math.h>
class Solution {
public:
    int jumpFloorII(int number) {
    return pow(2,(number-1));
    }
};

3.不调用math函数的话，递归累乘即可(3ms,476k)

class Solution {
public:
    int jumpFloorII(int number) {
        if (number <= 0) {
            return -1;
        } else if (number == 1) {
            return 1;
        } else {
            return 2 * jumpFloorII(number - 1);
        }
    }
};

可见由于幂为基本运算，无论采取哪种方法，时间均拉不开差距

10.矩形覆盖

题目：我们可以用2x1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2x1的小矩形无重叠地覆盖一个2xn的大矩形，总共有多少种方法？
思路：仔细想这个问题其实跟跳台阶一样，如果还剩两块砖没铺，即如果剩一块砖，就只有一种铺法如果剩下2x2的方块没铺，就会有2种铺法，一种跟剩一块砖一样（例如竖着铺两次），另外一种即跟剩一块砖情况垂直（例如横着铺两次）。因此实际上还是f(n) = f(n-1)+f(n-2)
代码跟题8相同,需要注意测试用例设置了n=0

class Solution {
public:
    int rectCover(int number) {
      if(number==0)
      {
          return 0;
      }
      else
      {
        int f = 1, g = 1; //假设存在0项为1,1+1=2；依然满足条件
        while(number-->0) { //防止输入负数
            g += f; //求和得到第三项的值
            f = g - f; //为了得到第二项的值，用新得到的第三项值g减去第一项值f得到新的f值即为第二项值
        }
        return f;//返回新的第一项的值
      }
    }
};

剑指offer刷题记录(C++版本)（之一）

1. 二维数组中查找数字。

2.替换空格。

3. 从尾到头打印链表。

4.重建二叉树

5.用两个栈实现一个队列

6.重旋转数组的最小数字

7.斐波拉切数列

8.跳台阶问题

9.变态跳台阶问题

10.矩形覆盖

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读