[leetcode每日一题] 3211. 生成不含相邻零的二进制字符串

xxingyu

喜欢我的暴搜吗 ^^

/*
 * @lc app=leetcode.cn id=3211 lang=cpp
 *
 * [3211] 生成不含相邻零的二进制字符串
 */
#include <bits/stdc++.h>
using namespace std;
// @lc code=start
class Solution {
 public:
  vector<string> validStrings(int n) {
    vector<string> ans;
    auto check = [&](string s) {
      int len = s.length();
      if (len <= 1) return true;
      int cnt = 0;
      if (s[0] == '0' && s[1] == '0') return false;
      if (s[len - 1] == '0' && s[len - 2] == '0') return false;
      for (int i = 1; i < len - 1; ++i) {
        if (s[i] == '0' && s[i - 1] == '0') return false;
        if (s[i] == '0' && s[i + 1] == '0') return false;
      }
      return true;
    };
    auto dfs = [&](auto&& self, string s) {
      if (s.length() > n) return;
      if (s.length() == n && check(s)) {
        ans.push_back(s);
        return;
      } else {
        self(self, s + "0");
        self(self, s + "1");
      }
    };
    dfs(dfs, "0");
    dfs(dfs, "1");
    return ans;
  }
};
// @lc code=end

Dr_du

题目不难，可以通过递归枚举所有情况，每个节点可能为0或1，如果填入0再进行判断。
详细见代码❤

class Solution {
public:
    //res记录结果
    vector<string> res;
    //记录搜索的过程
    string temp;
    vector<string> validStrings(int n) {
        temp.resize(n);
        dfs(0);
        return res;
    }

    //dfs(i)为搜索到了第i位
    void dfs(int n)
    {
        //终止条件
        if (n == temp.size())
        {
            res.push_back(temp);
            return;
        }
        //第i个位置可能为0或1
        for (int i = 0; i <= 1; i++)
        {
            //如果第i个位置不是第0个（防止出现访问下标-1）并且当前位置和前一位都为0
            if (i == 0 && n > 0 && temp[n - 1] == '0')
                continue;
            //加入的数记得转为字符
            temp[n] = i + '0';
            //搜索下一位
            dfs(n + 1);
        }
    }

ssssshi

我是弱弱，用0-2的n次方之后转化二进制来生成所有的01字符，再将其中00不相邻数组以字符串的形式存入结构体，并将他的十进制与0的个数同时存入，然后排序，排序时1优先0的个数，其次10进制大小，正如我先前所说我是弱弱所以写的比较麻烦

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

typedef struct zifu
{
    string chang;
    int cnt;
    int n;
} zif;

int pan(int arr[], int n)
{
    for(int i = 0; i < n - 1; i++)
    {
        if(arr[i] == 0 && arr[i + 1] == 0) return 0;
    }
    return 1;
}

bool pai(const zif &a, const zif &b)
{
    if(a.cnt == b.cnt) return a.n < b.n;
    return a.cnt > b.cnt;
}

class Solution {
public:
    vector<string> validStrings(int n) {
        int cnt, arr[1200000];
        int l = pow(2, n), l2 = pow(2, n) - 1;
        zif s[1210000];
        int si = 0;
        for(int i = 0; i < l; i++)
        {
            cnt = 0;
            int i2 = i, i3 = 0;
            while(i2)
            {
                arr[i3++] = i2 % 2;
                if(i2 % 2 == 0) cnt++;
                i2 /= 2;
            }
            while(i3 < n)
            {
                cnt++;
                arr[i3++] = 0;
            }
            if(pan(arr, n))
            {
                s[si].n = i;
                s[si].cnt = cnt;
                s[si].chang = ""; 
                for(int i4 = n - 1; i4 >= 0; i4--)
                {
                    s[si].chang += arr[i4] + '0';
                }
                si++;
            }
        }
        sort(s, s + si, pai);
        vector<string> result;
        for(int i = 0; i < si; i++)
        {
            result.push_back(s[i].chang);
        }
        return result;
    }
};

ygxdsh

简单dfs

class Solution {
public:
    vector<string> aa;
    string s;
    void dfs(int a,int n)
    {
        if(a>n)
        {
            aa.push_back(s);
            return;
        }
        if(a==1||s[a-2]=='1')
        {
            s[a-1]='0';
            dfs(a+1,n); 
        }
        s[a-1]='1';
        dfs(a+1,n);
    }
    vector<string> validStrings(int n) {
        for(int i=0;i<n;i++) s+=' ';
        dfs(1,n);
        return aa;
    }
};

tjp

我的是当之无愧的最无脑的，因为不会递推和dfs，我先生成了两个字符串，一个是1010···，另一个0101···，
然后循环，每次把其中的一个0变成1，循环了四次，两种字符串，每种从头到尾和从尾到头，最后把所有的结果存到一个set里再用迭代器输出

#include<iostream>  
#include<string>  
#include<set>
using namespace std;

int main() {
    int n;
    cin >> n;  set<string>myset;
    string x1(n,' ');
    string x2(n,' ');
    
    if (n == 1) {
        cout<< "[" << "0" << "," << "1" << "]";  
    }
    else {

        for (int i = 0; i < n; i++) {
            x1[i] = (i % 2 == 0) ? '0' : '1';
            x2[i] = (i % 2 == 0) ? '1' : '0';
        }
        myset.insert(x1);myset.insert(x2);string x3 = x1, x4 = x2;
        for (char& c : x1)
        {
            if (c == '0') {
                c = '1';
                myset.insert(x1);
            }
            continue;
        }
        for (char& c : x2)
        {
            if (c == '0') {
                c = '1';
                myset.insert(x2);
            }
            else continue;
        }
        for (auto c=x3.end()-1;c!=x3.begin();c--)
        {
            if (*c == '0') {
                *c = '1';
                myset.insert(x3);
            }
            else continue;
        }
        for (auto c = x4.end() - 1;c != x4.begin();c--)
        {
            if (*c == '0') {
                *c = '1';
                myset.insert(x4);
            }
            else continue;
        }
    }
    cout << "[";int cnt = 0;
    for (auto p = myset.begin();p != myset.end();p++)
    {
        cout << '"' << *p << '"';cnt++;if(cnt<myset.size()) { cout << ","; }
    }
    cout << "]";
    return 0;

Mr-Hate

先把字符串初始为1，然后递归在不同位填入0。
递归的第二个参数：填入0的位置。如果第i位填入了0，下次填入0的位置就是i+2。如果填入的是1，就在第i+1位填入0，如此递归枚举出所有的情况。

class Solution {
public:
    vector<string> ans;
    void dfs(string& str,int i){
        if(i>=str.size()){
            return ;
        }
        str[i]='0';
        ans.push_back(str);
        dfs(str,i+2);
        str[i]='1';
        dfs(str,i+1);
    }
    vector<string> validStrings(int n) {
        string str(n,'1');
        ans.push_back(str);
        dfs(str,0);
        return ans;
    }
};

Koarz

class Solution {
    void help(std::string &s, int n, std::vector<string> &res) {
        char c[]{'1', '0'};
        for (auto &v : c) {
            if (!s.empty() && v == '0' && *s.rbegin() == '0') {
                break;
            }
            s += v;
            if (s.size() == n) {
                res.push_back(s);
            } else {
                help(s, n, res);
            }
            s.pop_back();
        }
    }
public:
    vector<string> validStrings(int n) {
        std::string s;
        std::vector<std::string> res;
        help(s, n, res);
        return res;
    }
};

Yln_wlp

class  Solution {
    vector<string>res;//创建字符串数组
    int n;
public:
    vector<string> validStrings(int n) {
        this->n = n;//this指针给n赋值
        dfs(0,1,"");//初始为空字符串，长度为0
        return res;
    }
    void dfs(int i,int pre,string s){//i为当前字符长度，pre为上一个加的字符
        if(i==n){
            res.push_back(s);//将满足条件的字符串加到数组中
            return;//递归终止条件
        }
        if(pre==1){//上一个字符为1时，下一个0和1都可以
            dfs(i+1,0,s+'0');
            dfs(i+1,1,s+'1');
        }
        else{
            dfs(i+1,1,s+'1');//否则只能为1
        }
    }
};