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：

输入：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;
                }
        }
    }
};