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

2019-08-26  本文已影响0人  傑jay

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

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

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

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

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.替换空格。

 //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. 从尾到头打印链表。

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.重建二叉树

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.用两个栈实现一个队列

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.重旋转数组的最小数字

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.斐波拉切数列

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. 递归方式实现：(运行时间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);
        }
    }
  1. 动态规划实现：（运行时间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. 位移(虽然速度快简单，但是为0或者值过大会溢出)(3ms,480k)
public:
    int jumpFloorII(int number) {
                int a=1; return a<<(number-1);
    }
  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.矩形覆盖

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;//返回新的第一项的值
      }
    }
};
上一篇下一篇

猜你喜欢

热点阅读