剑指offer - 调整数组顺序使奇数位于偶数前面

发表于 2017-08-17 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/beb5aa231adc45b2a5dcc5b62c93f593

题意

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

题解

插入排序的思想，从前往后扫描，遇到偶数则往后寻找下一个奇数，然后将奇数调整到这些偶数的前面，最坏情况下，就是前半部分全为偶数，后半部分全为奇数，时间复杂度O(N*N)。

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        for(int i=0;i<array.size();i++){
            if(array[i]%2==0){
                int j=i+1;
                while(j<array.size()&&array[j]%2==0) j++;
                if(j==array.size()) break;
                int val = array[j];
                for(int k=j;k>i;k--)
                    array[k]=array[k-1];
                array[i]=val;
            }
        }
    }
};

发现一个STL方法，stable_partition，依据条件稳定划分，两组元素各维持相对顺序，即划分后，各组中元素的先后关系保持不变。
至于复杂度：

1
2

If enough extra memory is available, linear in the distance between first and last: Applies pred exactly once to each element, and performs up to that many element moves.
Otherwise, up to linearithmic: Performs up to N*log(N) element swaps (where N is the distance above). It also applies pred exactly once to each element.

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        stable_partition(array.begin(),array.end(),[](int x){return x%2;});
    }
};

当然可以用空间换时间，新建一个数组，从前往后扫描一遍，将奇数放到前面，然后从后往前扫一遍，将偶数放到后面，随后复制回去。

剑指offer - 表示数值的字符串

发表于 2017-08-16 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/6f8c901d091949a5837e24bb82a731f2

题意

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。

题解

比较清晰的方法就是一位一位来匹配。

class Solution
{
public:
    bool isNumeric(char* string)
    {
        int i=0;
        int len = strlen(string);
        if(string[i]=='+'||string[i]=='-'||isdigit(string[i]))
        {
            if(isdigit(string[i])) i--;
            int digitCount = 0;
            while(i<len&&isdigit(string[++i]))digitCount++;
            if(digitCount==0) return false;
            if(i==len) return true;
            else if(string[i]=='.')
            {
                digitCount=0;
                while(i<len&&isdigit(string[++i]))digitCount++;
                if(digitCount==0) return false;
                if(i==len) return true;
                else if(string[i]=='e'||string[i]=='E')
                {
                    i++;
                    if(string[i]=='+'||string[i]=='-'||isdigit(string[i]))
                    {
                        if(isdigit(string[i])) i--;
                        digitCount=0;
                        while(i<len&&isdigit(string[++i]))digitCount++;
                        if(digitCount==0) return false;
                        if(i==len) return true;
                        else return false;
                    }else return false;
                }else return false;
            }else if(string[i]=='e'||string[i]=='E')
            {
                i++;
                if(string[i]=='+'||string[i]=='-'||isdigit(string[i]))
                {
                    if(isdigit(string[i])) i--;
                    digitCount = 0;
                    while(i<len&&isdigit(string[++i])) digitCount++;
                    if(digitCount==0) return false;
                    if(i==len) return true;
                    else return false;
                }else return false;
            }else return false;
        }else return false;
    }
};

有个问题是，对于‘+.1’’1e+’这种情况，牛客上可能数据不充分。上述代码这种情况也正确。

剑指offer - 正则表达式匹配

发表于 2017-08-15 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/45327ae22b7b413ea21df13ee7d6429c

题意

请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配

题解

假设dp[i][j]=true表示 s[0..i-1] 匹配 p[0..j-1]
则有两种情况，

如果p[j-1]!=’*’
- 如果s[i-1]与p[j-1]匹配并且dp[i-1][j-1]为true，那么dp[i][j]为true
如果p[j-1]==’*’，假设p[j-2]=X
- X* 匹配0次的情况，如果dp[i][j-2]为true，dp[i][j]为true
- 如果匹配超过0次，如果dp[i-1][j]为true，也就是最后一位前面的位匹配，并且最后一位匹配，那么dp[i][j]为true。

class Solution {
public:
    bool match(char* str, char* pattern)
    {
        int m=strlen(str),n=strlen(pattern);
        vector< vector<bool> > dp(m+1,vector<bool>(n+1));
        //空和空匹配
        dp[0][0] = true;
        //匹配空模式串
        for(int i=1;i<=m;i++){
            dp[i][0]=false;
        }
        //空串匹配模式串
        for(int j=1;j<=n;j++){
            dp[0][j]=j>1&&pattern[j-1]=='*'&&dp[0][j-2];
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(pattern[j-1]!='*'){
                    dp[i][j]=dp[i-1][j-1]&&(pattern[j-1]==str[i-1]||pattern[j-1]=='.');
                }else{
                    dp[i][j]=dp[i][j-2]||(dp[i-1][j]&&(pattern[j-2]==str[i-1]||pattern[j-2]=='.'));
                }
            }
        }
        return dp[m][n];
    }
};

剑指offer - 删除链表的节点

发表于 2017-08-13 | 更新于 2020-09-15

题意

在O(1)时间内删除链表节点。

题解

由于要删除一个节点，需要知道上一个节点的地址，将上一个节点的地址的next指向要删除节点的next。
但是，如果我们不改变next值，而是将要删除节点的下个节点中的值复制到当前节点，然后删除下个几点，相当于间接删除掉了这个节点。
注意几点：
如果是尾节点，还是需要从头遍历到尾删除的。
如果只有一个节点删除后要返回NULL。

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {}
};
class Solution {
public:
    ListNode* deleteNode(ListNode* pHead,ListNode *node)
    {
        if(pHead==NULL) return NULL;
        if(pHead==NULL) return pHead;
        if(node->next==NULL){ //尾节点
            ListNode * p= pHead,*pre=NULL;
            while(p->next){
                pre = p;
                p=p->next;
            }
            if(pre==NULL) return NULL;  //只有一个节点
            pre->next = NULL;
        }else{
            node->val=node->next->val;
            node->next=node->next->next;
        }
        return pHead;
    }
};

扩展题目

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。

题解

比较恶心。
需要考虑各种情况。
有序的数列，记录相邻的重复的数的个数，为1，则加到链表中，否则不管。注意开头和结尾。

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {}
};
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if(pHead==NULL) return NULL;//链表为空
        ListNode *pre=pHead,*cur=pHead->next,*preSignal = NULL;
        if(cur==NULL) return pHead;//只有一个节点
        int num = pHead->val,numCount=1;
        do{
            if(num!=cur->val){
                if(numCount==1){
                    if(preSignal==NULL){
                        preSignal = pre;
                        pHead = preSignal;
                    }
                    else{
                        preSignal->next = pre;
                        preSignal = pre;
                    }
                }
                num=cur->val;
                numCount=1;
            }else{
                numCount++;
            }
            pre = cur;
            cur=cur->next;
        }while(cur);
        if(preSignal==NULL){
            if(numCount==1) //最后一个数不重复
                return pre;
            return NULL; //所有都重复
        }
        if(numCount==1)
            preSignal->next = pre;
        else
            preSignal->next = NULL;
        return pHead;
    }
};

剑指offer - 打印从1到最大的n位数

发表于 2017-08-13 | 更新于 2020-09-15

题意

输入n，按顺序打印从1到最大的n位10进制数，如n=3,则输出1,2,3…999。

题解

n表示的是位数，所以可能很大，直接整数表示肯定不行。
1.用字符串模拟加法，只需要模拟加一即可。

class Solution{
private:
    void addOne(vector<char> &orign){
        int p=0;
        while(orign[p]=='9'){
            orign[p]='0';
            p++;
        }
        orign[p]++;
    }
    void printStrNum(vector<char> &num){
        int p=num.size()-1;
        while(num[p]=='0') p--;
        for(int i=p;i>=0;i--){
            printf("%c",num[i]);
        }
        printf("\n");
    }
public:
    void print_1_to_max_n_digit_seq(int n){
        vector<char> num(n+1,'0');
        while(1){
            addOne(num);
            if(num[n]=='1') break;
            printStrNum(num);
        }
    }
};

2.递归输出每一位0-9

class Solution{
private:
    void printStrNum(vector<char> &num){
        int p=0;
        while(num[p]=='0') p++;
        for(int i=p;i<num.size();i++){
            printf("%c",num[i]);
        }
        if(p<num.size())printf("\n");
    }
    void dfs(vector<char> num,int index){
        if(index==num.size()){
            printStrNum(num);
            return ;
        }
        for(int i=0;i<10;i++){
            num[index]='0'+i;
            dfs(num,index+1);
        }
    }
public:
    void print_1_to_max_n_digit_seq(int n){
        vector<char> num(n,'0');
        dfs(num,0);
    }
};

剑指offer - 数值的整数次方

发表于 2017-08-12 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/1a834e5e3e1a4b7ba251417554e07c00

题意

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

题解

可用快速幂来降低复杂度。注意指数为负的情况。

class Solution {
public:
    double Power(double base, int exponent) {
        double ans = 1.0;
        bool positive = exponent>=0;
        exponent = abs(exponent);
        while(exponent){
            if(exponent&1){
                ans*=base;
            }
            base*=base;
            exponent>>=1;
        }
        if(!positive) return 1.0/ans;
        return ans;
    }
};

剑指offer - 二进制中1的个数

发表于 2017-08-12 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/8ee967e43c2c4ec193b040ea7fbb10b8

题意

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

题解

先来看这个
8 —> 1000
7 —> 0111
12 —> 1100
11 —> 1011
可以发现，n-1的二进制表示中，是将n中的最后一个1后面的所有位取反，这与二进制计算是想吻合的。
然后我们可以利用这一性质，依次将n中的1找出来，怎么找呢？
取反之后与原式相与，然后原来的1以及后面的0就全变为0了。
这样我们就可以统计出共有多少个1了。

class Solution {
public:
     int  NumberOf1(int n) {
        int ans=0;
        while(n){
            n&=(n-1);
            ans++;
        }
        return ans;
     }
};

剑指offer - 剪绳子

发表于 2017-08-12 | 更新于 2020-09-15

题意

给你一根长度为n的绳子，请把绳子剪成m段（n,m均大于1），每段长度记为k[0],k[1],…k[m]。请问k[0]k[1]…k[m]可能的最大乘积是多少。例如绳长为8，剪成三段2,3,3，此时最大乘积是18。

题解

我们考虑第一刀，总共有n-1个位置可以选择，得到的两端绳子长度一共有n-1种。设f(n)为长度为n的绳子剪成m段的最大乘积，假设第一刀剪成i和n-i两端，那么f(n)就等于，f(i)*f(n-i),采用动态规划可以免去重复的多余计算。
需要注意的是，m大于1，也就是说不可以不剪，但是计算f(n)时，我们考虑的是第一刀之后，也就是剪成的两端可以不用再剪。也就是实际上

class Solution {

public:
    int maxMul(int n){
        int dp[n+1];
        dp[0]=0;
        dp[1]=0;
        for(int l=2;l<=n;l++){
            dp[l]=0;
            for(int i=1;i<=l/2;i++){
                dp[l]=max(max(dp[i],i)*max(dp[l-i],l-i),dp[l]);
            }
        }
        return dp[n];
    }
};

剑指offer - 机器人的运动范围

发表于 2017-08-12 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/6e5207314b5241fb83f2329e89fdecc8

题意

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

题解

同样是DFS。

class Solution {
private:
    int dirx[4]={0,1,0,-1};
    int diry[4]={1,0,-1,0};
    vector< vector<bool> > vis;
public:
    int movingCount(int threshold, int rows, int cols)
    {
        vis.resize(rows,vector<bool>(cols));
        return dfs(rows,cols,threshold,0,0);
    }
private:
    int dfs(int rows,int cols,int k,int x,int y){
        if(getCount(x)+getCount(y)>k) return 0;
        int ans = 1;
        vis[x][y]=1;
        for(int i=0;i<4;i++){
            int nx = x+ dirx[i];
            int ny = y+ diry[i];
            if(judgeIn(rows,cols,nx,ny)&&!vis[nx][ny])
                ans+=dfs(rows,cols,k,nx,ny);
        }
        return ans;
    }
    int getCount(int n){
        int ans=0;
        while(n){
            ans+=n%10;
            n/=10;
        }
        return ans;
    }
    int judgeIn(int rows,int cols,int x,int y){
        return 0<=x&&x<rows&&0<=y&&y<cols;
    }
};

剑指offer - 矩阵中的路径

发表于 2017-08-12 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc

题意

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。

例如矩阵

中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

题解

经典的DFS。

class Solution {
private:
    vector< vector<char> > g;
    vector< vector<int> > vis;
    int dirx[4]={0,1,0,-1};
    int diry[4]={1,0,-1,0};
    int len;
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        len = strlen(str);
        g.resize(rows,vector<char>(cols));
        vis.resize(rows,vector<int>(cols));
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                g[i][j]=matrix[i*cols+j];
            }
        }
        //枚举起点
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(dfs(i,j,str,0))
                    return true;
            }
        }
        return false;
    }
private:
    bool dfs(int x,int y,char * str,int pos){
        if(str[pos]!=g[x][y]) return false;
        if(pos==len-1) return true;
        vis[x][y]=1;
        for(int i=0;i<4;i++){
            int nx = x+dirx[i];
            int ny = y+diry[i];
            if(judgeIn(nx,ny)&&!vis[nx][ny]&&dfs(nx,ny,str,pos+1))
                return true;
        }
        vis[x][y]=0;
        return false;
    }
    bool judgeIn(int x,int y){
        return 0<=x&&x<g.size()&&0<=y&&y<g[0].size();
    }
};