2022-01-05每日刷题打卡

2022-01-05每日刷题打卡

力扣——每日一题

1576. 替换所有的问号

给你一个仅包含小写英文字母和 ‘?’ 字符的字符串 s,请你将所有的 ‘?’ 转换为若干小写字母,使最终的字符串不包含任何 连续重复 的字符。

注意:你 不能 修改非 ‘?’ 字符。

题目测试用例保证 除 ‘?’ 字符 之外,不存在连续重复的字符。

在完成所有转换(可能无需转换)后返回最终的字符串。如果有多个解决方案,请返回其中任何一个。可以证明,在给定的约束条件下,答案总是存在的。

示例 1:

输入:s = “?zs”
输出:“azs”
解释:该示例共有 25 种解决方案,从 “azs” 到 “yzs” 都是符合题目要求的。只有 “z” 是无效的修改,因为字符串 “zzs” 中有连续重复的两个 ‘z’ 。

一开始是准备了一个26个字母的字符串,和一个随机数生成的函数,这个函数接收两个参数,这两个参数是‘?’符号左右两边的字母在26字母中的位置,然后我们随机生成0~25的数字,只要不等于这两个数就算生成成功,如果有相等的就把这个数再生成一遍,直到不相等为止,把随机数返回给主函数。

主函数里先判断一下s的长度,如果长度为1且那个字符就是‘?’,我们就随便返回一个字母即可,然后for循环开始遍历s,每次遇到’?‘符号时,把他左右两边的字母-’a’得到它们在26字母中的位置,并且通过这两个数调用生成随机数的函数,再通过得到的随机数根据一开始准备好的26字母字符串,以随机数作为下标从里面取一个字母赋给‘?’。遍历完后返回s即可。

class Solution {
public:
    int rand_num(int a,int b)
    {
        int c;
        do c=rand()%25;while(c==a||c==b);
        return c;
    }
    string modifyString(string s) {
        string word="abcdefghijklmnopqrstuvwxyz";
        int n =s.size();
        if(n==1&&s[0]=='?')return "a";
        for(int i=0;i<n;i++)
        {
            if(s[i]=='?')
            {
                if(i==0)s[i]=word[rand_num(-1,s[i+1]-'a')];
                else if(i==n-1)s[i]=word[rand_num(-1,s[i-1]-'a')];
                else s[i]=word[rand_num(s[i-1]-'a',s[i+1]-'a')];
            }
        }
        return s;
    }
};

但这解法有些许复杂了,我们还有更简单的方法。

我们知道,想要三个连续字符使得他们相邻的字符不出现重复,最多只需要三个字符(这里我们取‘a’,‘b’,‘c’),简单点可以是aba,最复杂也不过abc,所以我们不需要26个字母,只需要三个字母即可。

我们遍历s字符串,遇到’?'字符后开始for循环,在abc三个字符中循环,只要循环到的字符不同时等于’?‘字符相邻的字母,我们就把循环到的字符赋给’?‘。遍历结束后返回s。

class Solution {
public:
    string modifyString(string s) {
        int n =s.size();
        if(n==1&&s[0]=='?')return "a";
        for(int i=0;i<n;i++)
        {
            if(s[i]=='?')
            {
                for(char j='a';j<='c';j++)
                {
                    if(i==0&&j!=s[i+1])
                    {
                        s[i]=j;
                        break;
                    }
                    else if(i==n-1&&j!=s[i-1])
                    {
                        s[i]=j;
                        break;
                    }
                    else if(i!=0&&i!=n-1&&s[i-1]!=j&&s[i+1]!=j)
                    {
                        s[i]=j;
                        break;
                    }
                }
            }
        }
        return s;
    }
};

飞书——每日一题

79. 单词搜索

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

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

示例 1:

2022-01-05每日刷题打卡

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

深度优先搜索,先在主函数里确定出发点,遍历一遍board,看哪个格子里的元素和word的第一个元素相同,相同就以当前位置为起点开始dfs,准备两个方向数组,一个dx一个dy,两个一起再配合dfs函数里的for循环让元素在相邻上下左右的格子里移动,为确保格子不被重复利用,我们再准备一个和board相同大小的bool类型二维数组,初始都设置为false,当一个格子里的元素被利用过后,把bool数组里相应位置的元素改为true,以让我们知道这格子元素被利用过了。在dfs的for中,当遍历到board有元素和word当前遍历到的字符元素相等,就把那个位置送去下一次dfs,以此往复,当word被全部找到,返回true。要是在主函数里遍历所有起始点也找不到相同元素,返回false。

class Solution {
public:
    int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
    string str;
    vector<vector<char>>v;
    bool flag[7][7];
    bool a=false;
    bool exist(vector<vector<char>>& board, string word) {
        str=word;
        v=board;
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[0].size();j++)
            {
                if(board[i][j]==word[0])
                {
                    flag[i][j]=true;
                    dfs(1,i,j,board.size(),board[0].size());
                    if(a)return a;
                    flag[i][j]=false;
                }
            }
        }
        return a;
    }
    void dfs(int u,int i,int j,int n,int m)
    {
        if(a||u==str.size())
        {
            a=true;
            return;
        }
        for(int d=0;d<4;d++)
        {
            if(i+dx[d]>=0&&i+dx[d]<n&&j+dy[d]>=0&&j+dy[d]<m&&!flag[i+dx[d]][j+dy[d]]&&
                v[i+dx[d]][j+dy[d]]==str[u])
                {
                    u++;
                    flag[i+dx[d]][j+dy[d]]=true;
                    dfs(u,i+dx[d],j+dy[d],n,m);
                    if(a)return;
                    u--;
                    flag[i+dx[d]][j+dy[d]]=false;
                }
        }
    }
};
上一篇:企业官网小程序搭建教程-首页的搭建05


下一篇:剑指 Offer 05. 替换空格