文档章节

剑指offer

r
 ranjiewen
发布于 2016/11/03 23:52
字数 869
阅读 4
收藏 0

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

 

今天完成了剑指offer上的66道编程题,感觉自己还是很多代码实现能力和算法积累都还不够!还需要继续联系,坚持自己独立写代码实现。

最后将今天的两道题目奉上,都有异曲同工之妙:

矩阵中的路径:

#include<memory.h>

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

//思路
//深搜的基本题型,分别以每个格子为起点,往四个方向去遍历,直到找到符合题意的字符串即可
class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        if (matrix==nullptr||str==nullptr||rows<1||cols<1)
        {
            return false;
        }
        //建立一个标记数组,走过的位置为true,没走过的为false
        bool *vis = new bool[rows*cols];
        memset(vis,false,rows*cols);
        int pathLength = 0;
        for (size_t i = 0; i < rows; i++)
        {
            for (size_t j = 0; j < cols; j++)
            {
                if (hasPathCore(matrix,rows,cols,i,j,str,pathLength,vis))
                {
                    return true;
                }
            }
        }
        delete[]vis;
        return false;
    }
    //判断从一个元素出发是否能找到一条路径
    bool hasPathCore(char *matrix,int rows,int cols,int x,int y,char *str,int pathLength,bool *vis)
    {
        if (str[pathLength]=='\0')//嵌套调用出口
        {
            return true;
        }
        bool hasPath = false;//函数返回值
        if (x>=0&&x<=rows&&y>=0&&y<=cols&&matrix[x*cols+y]==str[pathLength]&&!vis[x*cols+y])//坐标范围判断,x=0开始,所以x*cols+y索引正确
        {
            ++pathLength;
            vis[x*cols + y] = true;
            hasPath = hasPathCore(matrix, rows, cols, x - 1, y, str, pathLength, vis)
                || hasPathCore(matrix, rows, cols, x + 1, y, str, pathLength, vis)
                || hasPathCore(matrix, rows, cols, x, y - 1, str, pathLength, vis)
                || hasPathCore(matrix, rows, cols, x, y + 1, str, pathLength, vis);
            if (!hasPath) //没有路径时,返回到原来位置
            {
                --pathLength;
                vis[x*cols + y] = false;
            }        
        }
        return hasPath;
    }
};

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

//思路
//深搜基础题,从0开始按照四个方向递归求解即可
class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        bool *vis = new bool[rows*cols];
        memset(vis,false,rows*cols);
        int result = movingCountCore(threshold,rows,cols,0,0,vis);
        delete[]vis;
        return result;
    }
    int movingCountCore(int threshold,int rows,int cols,int x,int y,bool *vis)
    {
        int count = 0;
        if (x >= 0 && x<rows && y >= 0 && y<cols && getSum(x) + getSum(y) <= threshold && !vis[x*cols + y])
        {
            vis[x*cols + y] = true;
            count = 1 + movingCountCore(threshold, rows, cols, x - 1, y, vis)
                + movingCountCore(threshold, rows, cols, x + 1, y, vis)
                + movingCountCore(threshold, rows, cols, x, y - 1, vis)
                + movingCountCore(threshold, rows, cols, x, y + 1, vis);
        }
        return count;
    }
    int getSum(int num)
    {
        int sum = 0;
        while (num)
        {
            sum += num % 10;//先取各位
            num /= 10;//从低到高位
        }
        return sum;
    }
};

 

本文转载自:http://www.cnblogs.com/ranjiewen/p/5901303.html

r
粉丝 1
博文 203
码字总数 28
作品 0
武汉
程序员
私信 提问

暂无文章

互联网公司为啥不使用mysql分区表?(一分钟系列)

缘起:有个朋友问我分区表在58的应用,我回答不出来,在我印象中,百度、58都没有听说有分区表相关的应用,业内进行一些技术交流的时候也更多的是自己分库分表,而不是使用分区表。于是去网上...

小海bug
30分钟前
8
0
Dev GridView显示筛选框

列表上方的筛选框,可根据任意列进行数据筛选 设置:GridView属性showAutoFilterRow为true

_Somuns
34分钟前
6
0
DevExpress WPF v19.2图表图形控件功能增强?速速种草

通过DevExpress WPF Controls,你能创建有着强大互动功能的XAML基础应用程序,这些应用程序专注于当代客户的需求和构建未来新一代支持触摸的解决方案。 无论是Office办公软件的衍伸产品,还是...

FILA6666
37分钟前
5
0
鹿班|一人设计10亿图片,这个“设计师”如何演进?

本文内容提炼: 1、如何建立图片数据与用户注意力之间的连接? 2、如何进行结构化规模化的图片生产? 2019 年双十一期间,鹿班面向集团电商场景输送了 10亿 规模的图片。从提升公域流量效率,...

阿里云官方博客
39分钟前
7
0
argo注册教程和攻略,argo共识币介绍注册帮助

ARGO移动云矿一家专注于加密的公司。Argo本周在伦敦证券交易所上市,融资2500万英镑(约3200万美元),总估值约6100万美元。 从历史上来看,整个行业的超级神话。 目前Argo公司已经在加拿大第...

区块链知识分享
39分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部