2021-12-08每日刷题打卡

08
十二月
2021

2021-12-08每日刷题打卡

力扣——剑指offer

剑指 Offer 12. 矩阵中的路径

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如,在下面的 3×4 的矩阵中包含单词 “ABCCED”(单词中的字母已标出)。

word2.jpg (322×242) (leetcode.com)

示例 1:

输入:board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出:true

这里我们再用dfs深度搜索时,要注意,因为题目没有固定开始遍历的位置,所以结果可能并不是以0 0为开头,所以为了准确,我们采用两层for循环,遍历所有坐标,以遍历到的坐标为开头进行深度搜索。每次dfs先判断坐标的值和word的首元素是否相同,如果不相同就可以直接返回false,如果相同,就把当前位置的上下左右四个位置的元素送去比较word的第二个元素。。。以此类推。

class Solution {
public:
    int n,m;
    bool exist(vector<vector<char>>& board, string word) {
        n=board.size(),m=board[0].size();
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(dfs(board,word,0,i,j))return true;
        return false;
    }
    bool dfs(vector<vector<char>>& v,string word,int u,int x,int y)
    {
        if(x>=n||y>=m||x<0||y<0||v[x][y]!=word[u])return false;;
        if(u==word.size()-1)return true;
        v[x][y]='\0';
        bool res=dfs(v,word,u+1,x+1,y)||dfs(v,word,u+1,x,y+1)||dfs(v,word,u+1,x,y-1)||dfs(v,word,u+1,x-1,y);
        v[x][y]=word[u];
        return res;
    }
};

剑指 Offer 13. 机器人的运动范围

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

示例 1:

输入:m = 2, n = 3, k = 1
输出:3

深度遍历,开辟一个m*n大小的数组,初始设为0,一个变量ans计算到达过的格子。dfs一开始先判断遍历到的格子坐标是否超过界限,然后判断数组对应位置的数是否为0,如果为0说明还没遍历到,如果为1说明已经遍历过了直接结束这次遍历,然后再判断位数和是否小于等于k,如果不小于等于,直接结束遍历,如果小于等于,ans++,把数组对应位置的数设置为1,然后把当前位置上下左右四个位置的坐标送去下一次遍历。当所有遍历都结束后,返回ans。

class Solution {
public:
    int s[110][110];
    int movingCount(int m, int n, int k) {
        int ans=0;
        dfs(ans,m,n,0,0,k);
        return ans;
    }
    void dfs(int& ans,int m,int n,int x,int y,int k)
    {
        if(x<0||x>=m||y<0||y>=n||s[x][y]==1||get_num(x)+get_num(y)>k)return ;
        ans++;
        s[x][y]=1;
        dfs(ans,m,n,x+1,y,k);
        dfs(ans,m,n,x-1,y,k);
        dfs(ans,m,n,x,y+1,k);
        dfs(ans,m,n,x,y-1,k);
    }
    int get_num(int num)
    {
        int a=0;
        while(num!=0)
        {
            a+=num%10;
            num/=10;
        }
        return a;
    }
};

力扣——动态规划

746. 使用最小花费爬楼梯

数组的每个下标作为一个阶梯,第 i 个阶梯对应着一个非负数的体力花费值 cost[i](下标从 0 开始)。

每当你爬上一个阶梯你都要花费对应的体力值,一旦支付了相应的体力值,你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时,你可以选择从下标为 0 或 1 的元素作为初始阶梯。

示例 1:

输入:cost = [10, 15, 20]
输出:15
解释:最低花费是从 cost[1] 开始,然后走两步即可到阶梯顶,一共花费 15 。

开辟一个和cost一样大小的状态数组dp,我们设状态为:dp[i]表示移动到第i个阶梯时所用的最小体力。初始先设置dp[0]=cost[0],dp[1]=cost[1],因为要到达开头这两个位置,所需要的最小体力就是cost对应的体力(一步走到0上,或一步走到1上)然后走到第2个位置时就要判断,是从第0个位置跳过来用的体力少,还是从第1个位置走过来用的体力少,选较小的那个加上自己这一格的体力,就是到达当前位置所需要的最少体力,即dp[i]=min(dp[i-1],dp[i-2])+cost[i]。最后返回结果时,我们可以是从倒数第二个位置直接走到结尾,也可以是从倒数第一个位置走到结尾,选择两者中较小的那一个返回即可。

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n=cost.size();
        vector<int>dp(n,0);
        dp[0]=cost[0];
        dp[1]=cost[1];
        for(int i=2;i<n;i++)
        {
            dp[i]=min(dp[i-1],dp[i-2])+cost[i];
        }
        return min(dp[n-1],dp[n-2]);
    }
};

网友评论

共有访客发表了评论
请登录后再发布评论,和谐社会,请文明发言,谢谢合作! 立即登录 注册会员