小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. 剑指offer
  6. 正文

《剑指Offer》题目解析(3)

2019年3月4日 1007点热度 0人点赞 0条评论

题目1:机器人的运动范围

题目描述

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

题目解析

这个题可以看做是广度搜索优先(BFS)的一个拓展或者说是改编。如果说没有“不能进入行坐标和列坐标的数位之和大于****k****的格子”这个条件,那么它就是一个纯粹的BFS问题,设置上这个,就基本上就相当于只是多了一个条件。所以我们需要做的就是以下几个工作:

1.设置标志位。bool flags=new bool[rowscols]。

2.将移动一步单独设置为一个子函数,在这个函数里面,原始的判断条件只是:

if(i>=0 && i< rows && j >=0 && j<cols && flags[i*cols+j]==false)

而现在则变成了:

if(i>=0 && i< rows && j >=0 && j<cols && (gssum(i) + gssum(j) <= threshold) && flags[i*cols+j]==false)

代码

int movingCount(int threshold, int rows, int cols)
    {
        bool *flags=new bool[rows*cols];//所有格子的标志位默认设置为false
        for(int i=0;i<rows*cols;i++)
            flags[i]=false;
        int count = movingstep(threshold, rows, cols, 0, 0, flags);;//记录可访问格子数量
        return count;
    }
    int movingstep(int threshold, int rows, int cols, int i, int j, bool *flags)
    {
        int count = 0;
        if(i>=0 && i< rows && j >=0 && j<cols && (gssum(i) + gssum(j) <= threshold) && flags[i*cols+j]==false)
        {
            flags[i*cols+j]=true;
            count = 1 + movingstep(threshold, rows, cols, i+1, j, flags)+movingstep(threshold, rows, cols, i-1, j, flags)+movingstep(threshold, rows, cols, i, j+1, flags)+movingstep(threshold, rows, cols, i, j-1, flags);
        }
        return count;

    }

    int gssum(int i)
    {
        int sum = 0;
        while(i)
        {
            sum += i % 10;;
            i /= 10;
        }
        return sum;
    }

题目2:把字符串转换成整数

题目描述

将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能,但是string不符合数字要求时返回0),要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。

题目解析

本题目其实是一个很简单的题目,只需要很细心判断以下几处问题即可:

1.不考虑最前面的空格;

2.若除去空格后的第一位为“+”或“-”,则分别将标志位做不同的设置,若为数字,直接将标志位设置为同“+”,若为其它则直接返回0;

3.后续几位直接判断是否为0~9之间的数字,由于是字符串格式,所以为ascii码,这样,我们在转换成int格式的时候,直接用该字符减去’0’即可。

代码

 int StrToInt(string str) {
        int len=str.length();
        if(len==0)
            return 0;
        int i = 0;
        int res = 0;
        int fla = 1;
        //滤掉前面的空格
        while(str[i]==' '){
            i++;
        }
        //进行符号判断
        if(str[i]=='+'){
            i++;
        }else if(str[i]=='-'){
            i++;
            fla=-1;
        }
        while(str[i]!='\0'){
            //对字符进行是否为数字的判断
            if(str[i]>='0'&&str[i]<='9'){
                res=res*10+fla*(str[i]-'0');
                i++;
            }else{
                res=0;
                break;
            }

        }
        return res;
    }

题目3:表示数值的字符串

题目描述

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

题目解析

表示数值的字符串遵循的规则;

1.在数值之前可能有一个“+”或“-”,接下来是0到9的数位表示数值的整数部分,如果数值是一个小数,那么小数点后面可能会有若干个0到9的数字。

2表示数值的小数部分,如果用科学计数法表示,接下来是一个‘e’或者‘E’,以及紧跟着一个整数(可以有正负号)表示指数。

代码

bool isNumeric(char* string)
    {
        if(string == NULL)
            return false;
        if(*string == '+' || *string =='-')
            string++;
        if(*string =='\0')
            return false;
        int dot = 0;//小数点的个数
        int num = 0;//数字的个数
        int ex = 0;//e指数的个数
        while(*string !='\0')
        {
            if((*string >= '0') && (*string <='9'))
            {
                num++;
                string++;
            }
            //小数点开始
            else if(*string =='.')
            {
                if(dot> 0 || ex > 0)
                    return false;
                dot++;
                string++;
            }
            //指数e
            else if((*string =='e') ||(*string == 'E'))
            {
                if(num ==0 || ex > 0)
                    return false;
                string++;
                ex++;
                if(*string == '+' || *string =='-')
                    string ++;
                if(*string=='\0')
                    return false;

            }
            else
                return false;
        }
        return true;



    }

题目4:链表中环的入口节点

题目描述

给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。

题目解析

其实我的思路是把每个访问过的结点做标记,然后不断往下走后,遇到的第一个标记过的点,就是还的入口结点,如果没有遇到,则就不存在环,返回null。但是这种方法比较复杂,而且很难找到标志每个结点的特点在哪里。

所以可以这样考虑。如图4.1所示。
约束条件

图4.1 示意图

我们假设x为AB之间的距离,a为从b到c的距离(顺时针移动),c为环的长度。我们可以设置两个指针,一个快一个慢,然后快的是慢的速度的两倍。设快指针为f,慢指针为s,则当快指针和慢指针相遇的时候,s=x+mc+a,f=x+nc+a,m和n为某不同的常数,s=f。所以x=(n-2m)c-a=(n-2m-1)c+c-a。n-2m-1可为0。这里为了处理方便,省略前面这个类似于周期的东西,只留下c-a。c-a是什么?c-a就是图4.1中灰色的这条线。也就是说,AB之间的距离=灰色的线。这样,我们可以再重新将f这个指针(也可以是s)指向A,那么当f和s相遇的时候,所在的结点就是入口结点。

代码

ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if((pHead==NULL)||(pHead->next==NULL)||(pHead->next->next==NULL))
            return NULL;
        ListNode* fast = pHead->next->next;
        ListNode* slow = pHead->next;
        //先判断有没有环
        while(fast!=slow)
        {
            if((fast->next !=NULL) &&(fast->next->next!=NULL)){
                fast=fast->next->next;
                slow=slow->next;
            }
            else{
                return NULL;
            }
        }
        //如果能执行到这一步,说明有环,且此时fast==slow。
        //然后把fast调整到头部,此时fast和slow第一次相遇的位置就是入口地址
        fast=pHead;
        while(fast!=slow)
        {
            fast=fast->next;
            slow=slow->next;
        }
        return slow;

    }

题目5:把二叉树打印成多行

题目描述

从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。

题目解析

如果不加上“打印成多行”,那么这就是一个层序遍历,利用队列实现即可。而加上这个要求之后,只需要增加两个参数设置,当参数达到阈值后,输出第一行。

代码

 vector<vector<int> > Print(TreeNode* pRoot) {
            vector<vector<int> > vect;//最后输出的结果
            if(pRoot==NULL)
                return vect;//若pRoot为空,直接返回空
            //接下来总体上就是一个层序遍历的变体,所以可以使用层序遍历进行修改完成此题目
            //层序遍历可以利用队列来实现。
            //首先新建一个队列,然后将链表的头push进去,然后弹出,获得头的值,然后再分别push进去其左右两个结点。然后弹出头上的
            //然后判断其左右结点是否有,有就push进去。这样层序遍历其实就是用队列来输入输出。
            queue<TreeNode*> tmp;
            tmp.push(pRoot);
            while(!tmp.empty())
            {
                int l=0;
                int h=tmp.size();
                vector<int> t;
                while(l++<h)//按行输出
                {
                    TreeNode* k = tmp.front();
                    tmp.pop();
                    t.push_back(k->val);
                    if(k->left)
                        tmp.push(k->left);
                    if(k->right)
                        tmp.push(k->right);
                }
                vect.push_back(t);
            }
            return vect;
        }

题目6:按之字形顺序打印二叉树

题目描述

请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

题目解析

这个题目是对于题目5的拓展,我们依旧可以借鉴层序遍历,但是这里我们要使用的是两个堆栈。总体上是一样的。

假设我们输出第一行,那么按照顺序输出以后,push进堆栈的顺序要和之前的相反,这样push进入第二个堆栈。当用第二个堆栈输出的时候,就要先左后右push进入第一个堆栈。

代码

vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> > res;//结果存放
        stack<TreeNode*> stackl,stackr;//从右往左和从左往右输出结果的堆栈
        if(pRoot!=NULL)
        {
            stackl.push(pRoot);//跟层序遍历类似,先把根节点push进去
        }
        struct TreeNode* node;//中介的结点,类似于层序遍历
        while(!stackl.empty() || !stackr.empty())
        {
            vector<int> tmp;
            if(!stackl.empty()){
                while(!stackl.empty())
                {
                    node=stackl.top();
                    stackl.pop();
                    tmp.push_back(node->val);
                    if(node->left!=NULL)
                        stackr.push(node->left);
                    if(node->right!=NULL)
                        stackr.push(node->right);
                }
                res.push_back(tmp);

            }
            else if(!stackr.empty()){
                while(!stackr.empty()){
                    node=stackr.top();
                    stackr.pop();
                    tmp.push_back(node->val);
                    if(node->right!=NULL)
                        stackl.push(node->right);
                    if(node->left!=NULL)
                        stackl.push(node->left);
                }
                res.push_back(tmp);
            }
        }
        return res;

    }

题目7:二叉搜索树的第k个节点

题目描述

给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。

题目解析

这个题看着挺唬人,实际非常简单。由于二叉搜索树本身就是具有顺序特点的二叉树,因此这个题实际上是中序遍历二叉搜索树,然后输出中序遍历的第k个值。

代码

class Solution {
private:
    int count;
public:
    void inorder(TreeNode* root, TreeNode* &ans)
    {
        if(root)
        {
            inorder(root->left,ans);
            count--;//记录是第几个值
            if(!count)
                ans=root;
            inorder(root->right,ans);
        }
    }
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        if(pRoot==NULL || k<1)
            return NULL;
        TreeNode* ans = NULL;
        count = k;
        inorder(pRoot, ans);
        return ans;
    }


};

题目8:翻转单词顺序

题目描述

牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上。同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思。例如,“student. a am I”。后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行,你能帮助他么?

题目解析

这个题目其实最容易想到的就是,我们可以整个句子翻转过来,这样做的结果是,每个单词正好也都是反序的,我们只需要再调用一次翻转,将单词翻转就变成了正序。

代码

void ReversedWord(string &str, int st, int en)
    {
        while(st < en)
        {
            swap(str[st++],str[en--]);
        }
    }
    string ReverseSentence(string str) {
        int len = str.size();
        int st = 0;
        int en = 0;
        ReversedWord(str,0,len-1);//先整体翻转
        int i=0;
         while(i < len)
         {
             while(i < len && str[i] == ' ') //空格跳过
                i++;
            en = st = i; //记录单词的第一个字符的位置
            while(i < len && str[i] != ' ') //不是空格 找单词最后一个字符的位置
            {
                i++;
                en++;
            }
            ReversedWord(str, st, en - 1); //局部翻转
         }

        return str;
    }

题目9:扑克牌顺子

题目描述

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿!!“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何, 如果牌能组成顺子就输出true,否则就输出false。为了方便起见,你可以认为大小王是0。

题目解析

顺子要求:

1.牌面不重复;

2.牌面是连续的。

为了满足以上条件,所以做了以下两个步骤:

1.设置flag。只要不重复,很多都会用到flag,由于扑克牌里面有14种牌,所以flag数组长度为14,默认为0,有重复就加1。

2.寻找最大最小值,计算它们的差值,判断结果。由于牌面不重复,又由于只有五张,所以max-min<5的时候(其实就是为4的时候),肯定是连续的,若大了,肯定不连续。

代码

 bool IsContinuous( vector<int> numbers ) {
        if(numbers.empty())
            return false;
        int count[14]={0};
        int max = -1;
        int min = 14;
        for(int i=0;i<numbers.size();i++)
        {
            count[numbers[i]]++;
            if(numbers[i]==0)
                continue;
            if(count[numbers[i]]>1)
                return false;
            if(numbers[i] > max)
                max = numbers[i];
            if(numbers[i] < min)
                min = numbers[i];
        }
        if(max - min <5)
            return true;
        return false;
    }

题目10:矩阵中的路径

题目描述

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

题目解析

类似于题目3,在此就不具体说了。

代码

private:
    bool isPath(char *matrix, vector<char> flags, char* str, int i, int j, int rows, int cols)
    {
        if(i<0|| i>=rows || j<0 || j>=cols)
            return false;
        if(matrix[i*cols+j] == *str && flags[i*cols+j]==0)
        {
            flags[i*cols+j]=1;
            if(*(str+1)==0)
                return true;
            bool cond = isPath(matrix,flags,(str+1),i,j-1,rows,cols) ||
                isPath(matrix,flags,(str+1),i-1,j,rows,cols)||
                isPath(matrix,flags,(str+1),i,j+1,rows,cols)||
                isPath(matrix,flags,(str+1),i+1,j,rows,cols); 
            if(cond==false)
                flags[i*cols+j]=0;
            return cond;

        }
        else
            return false;
    }
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        vector<char> flags(rows*cols,0);
        bool con = false;
        for(int i=0;i<rows;i++)
            for(int j =0;j<cols;j++)
            {
                con = (con||  isPath(matrix,flags,str,i,j,rows,cols) );
            }
            return con;

    }
本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 剑指offer
最后更新:2019年3月4日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
作品声明 玩转你的Gravatar全球通用头像 《剑指Offer》题目解析(6) WordPress将文章同步到新浪微博的几种方法(三种) Java语言程序设计(进阶)(第四章)整理 数字信号处理慕课学习知识点总结
标签聚合
Java leetcode 生活 Python linux python学习 学习 高中 鸟哥的linux私房菜 算法
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号