剑指offer刷题记录

为了能从书中学一些代码规范之类的东西，有一些代码是跟着书上写的，有的是自己写的

数组

数组中重复的数字

题目描述：

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

//做法一：哈希表
//时间复杂度：O(n) ,空间复杂度O（n）
class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int numbers[], int length, int* duplication) {
         int a[1<<11]={1};
        for(int i=0;i<length;++i)
        {
            if(a[numbers[i]]==-1) 
            {
                *duplication=numbers[i];
                return true;
                break;
            }
            a[numbers[i]]=-1;
        }
        return false;
    }
};

//做法二：
//时间复杂度：O(n) ,空间复杂度O（1）
class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int numbers[], int length, int* duplication) {
        if(numbers == nullptr || length <= 0){
            return false;
        }
        for(int i=0;i<length;++i){
            if(numbers[i] < 0 || numbers[i] > length-1){
                return false;
            }
        }
        for(int i=0;i<length;++i){
            while(numbers[i]!=i){
                int temp = numbers[i];
                
                if(numbers[i] == numbers[temp]){
                    *duplication = numbers[i];
                    return true;
                }
                
                numbers[i] = numbers[temp];
                numbers[temp] = temp;
            }
        }
        return false;
    }
};

二维数组中的查找

题目描述：

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        bool found = false;
        int rows = array.size();
        int cols = array[0].size();
        
        int i = 0;            //行
        int j = cols -1;        //列
        
        while(i<rows && j>=0){
            
            if(array[i][j] > target){
                j--;
            }else if(array[i][j] < target){
                i++;
            }else {
                return true;
            }
        }
        return false;
    }
};

字符串

替换空格

题目描述：

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

class Solution {
public:
    void replaceSpace(char *str,int length) {
        
        if(str == nullptr || length<= 0){
            return ;
        }
        
        int originalLength = 0;            //字符串实际长度
        int numberOfBlank = 0;             //空格长度
        
        for(int i=0;str[i]!='\0';++i){
            ++originalLength;
            if(str[i]==' '){
                ++numberOfBlank;
            }
        }
        
        int newLength = originalLength + numberOfBlank * 2;
        
        if(newLength>length){
            return ;
        }
        
        int p1 = originalLength;
        int p2 = newLength;
        
        while(p1 >= 0 && p2>p1){

            if(str[p1]==' '){
                str[p2--] = '0';
                str[p2--] = '2';
                str[p2--] = '%';
                p1--;
            }else {
                str[p2--] = str[p1--];
            }
            
        }
        return ;
    }
};

链表

从尾到头打印链表

题目描述：

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> a;
        std:: stack<ListNode*> nodes;
        ListNode* pNode = head;
        while(pNode != nullptr){
            nodes.push(pNode);
            pNode = pNode->next;
        }
        while(!nodes.empty()){
            pNode = nodes.top();
            a.push_back(pNode->val);
            nodes.pop();
        }
        return a;
    }
};

树

重建二叉树

题目描述：

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

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* R(vector<int> pre,int abegin,int aend, vector<int> vin,int bbegin,int bend){
        
        if(abegin>=aend || bbegin>=bend){
            return NULL;
        }
        TreeNode* root = new TreeNode(pre[abegin]);
        int pivot;
        for(pivot=bbegin;pivot<bend;pivot++){
            if(vin[pivot] == pre[abegin]){
                break;
            }
        }
        root->left = R(pre,abegin+1,abegin+(pivot-bbegin)+1,vin,bbegin,pivot);
        root->right = R(pre,abegin+(pivot-bbegin)+1,aend,vin,pivot+1,bend);
        return root;
    }
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        return R(pre,0,pre.size(),vin,0,vin.size());
    }
};

栈和队列：

用两个栈实现一个队列：

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

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

    int pop() {
        
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int num = stack2.top();
        stack2.pop();
        return num;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

递归和循环

斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

n<=39

class Solution {
public:
    int Fibonacci(int n) {
        int maxn = 40;
        int dp[maxn];
        dp[1] =1;
        dp[2] =1;
        for(int i=3;i<=n;++i){
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

class Solution {
public:
    int jumpFloor(int number) {
        int maxn = 100;
        int dp[maxn];
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3;i<=number;++i)
        {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[number];
    }
};

变态跳台阶

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

class Solution {
public:
    int jumpFloorII(int number) {
        int maxn = 100;
        long long int dp[maxn];
        dp[1] =1;
        dp[2] =2;
        for(int i=3;i<=number;++i){
            dp[i] = 1;
            for(int j= 1;j<i;++j){
                dp[i]+=dp[j];
            }
        }
        return dp[number];
    }
};

矩形覆盖

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

class Solution {
public:
    int rectCover(int number) {
        int maxn = 100;
        int dp[maxn] ;
        dp[1] =1;
        dp[2] =2;
        for(int i = 3;i <= number ; ++i){
            dp[i] = dp[i-1]+ dp[i-2];
        }
        return dp[number];
    }
};

位运算

二进制中1的个数

class Solution {
public:
     int  NumberOf1(int n) {
         int cnt = 0;
         int t = 32;
         while(t--){
             if(n&1)
             {
                 cnt++;
             }
             n = n>>1;
         }
         return cnt;
     }
};

查找和排序

旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int low = 0;
        int high = rotateArray.size()-1;
        int mid;
        
        if (rotateArray.empty()) return 0;
        
        while(low<high){
            
            mid = low + (high-low)/2;
            
            if (rotateArray[low] < rotateArray[high]) return rotateArray[low];
           
            if( rotateArray[low] < rotateArray[mid]){
                low = mid+1;
            }else if(rotateArray[mid] < rotateArray[high])
            {
                high = mid;
            }else {
                low++;
            }
        }
        return rotateArray[low];
    }
};

回溯法

矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
例如
a b c e
s f c s
a d e e
矩阵中包含一条字符串"bccced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

class Solution {
public:
    bool hashPathCore(const char* matrix,int rows,int cols,int row,int col,char* str,int& pathLen,bool* visited){
        
        if( str[pathLen] =='\0'){
            return true;
        } 
        
        bool hasPath = false;
        
        if(row>=0 && row<rows && col>=0 && col<cols && str[pathLen] == matrix[row*cols+col] && !visited[row*cols+col] ){
            ++pathLen;
            visited[row*cols+col]=true;
            hasPath = hashPathCore(matrix,rows,cols,row-1,col,str,pathLen,visited) 
            || hashPathCore(matrix,rows,cols,row,col-1,str,pathLen,visited)
            || hashPathCore(matrix,rows,cols,row+1,col,str,pathLen,visited)
            || hashPathCore(matrix,rows,cols,row,col+1,str,pathLen,visited);
            if(!hasPath){
                --pathLen;
                visited[row*cols+col]=false;
            }
        }
        return hasPath;
    }
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        if(matrix == nullptr || rows <1 || cols<1 || str == nullptr){
            return false;
        }
        bool *visited = new bool[rows * cols];
        memset(visited,0,rows * cols);
        
        int pathLen = 0;
        for(int row = 0;row<rows;++row){
            for(int col = 0;col<cols;++col){
                if(hashPathCore(matrix,rows,cols,row,col,str,pathLen,visited)){
                    return true;
                }
            }
        }
        return false;
    }
};

机器人的运动范围

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。
例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 =
19。请问该机器人能够达到多少个格子？

class Solution {
public:
    int cnt = 0;
    int map[1005][1005];
    void init(){
        for(int i=0;i<1005;++i){
            for(int j=0;j<1005;++j){
                map[i][j]=0;
            }
        }
    }
    int cul(int num){
        int ans = 0;
        while(num){
            ans+=num%10;
            num/=10;
        }
        return ans;
    }
    void dfs(int k,int x,int y,int rows,int cols){
        int t = cul(x)+cul(y);
        if( map[x][y] == 1 ){
            return ;
        }
        if(x<0 || x>=cols || y<0 || y>=rows)
        {
            return ;
        }
        if(t>k){
            return ;
        }
        cnt++;
        map[x][y] =1;
        dfs(k,x+1,y,rows,cols);
        dfs(k,x-1,y,rows,cols);
        dfs(k,x,y+1,rows,cols);
        dfs(k,x,y-1,rows,cols);
    }
    int movingCount(int threshold, int rows, int cols)
    {
        init();
        dfs(threshold,0,0,rows,cols);
        return cnt;
    }
    
};