3211. 生成不含相邻零的二进制字符串-C语言实现

这是LeetCode上的题目，看了很多解答，但没有找到C语言的实现

我也是做了很久，学习了网友的思路，自己用C语言实现

思路：

将数字按照相同长度取反

将取反后的数字与此数字右移一位的数字做与运算

如果与的结果大于0，则存在多个相邻的1（对应上面的取反，就是存在多个相邻的0），否则为符合要求的字符串

再做一个10进制转2进制字符串的工具函数

代码如下：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define BITSET(x,n) ((x>>n)& 0x01)//十进制转二进制字符串
int dec2bin(int x,int n,char *bin)
{if(!bin){return 0;}for(int i = 0;i < n;i++){if(BITSET(x,i)){bin[n - i -1] = '1';}elsebin[n - i -1] = '0';}// printf("bin is %s\n",bin);return 1;
}/*** Note: The returned array must be malloced, assume caller calls free().*/
char** validStrings(int n, int* returnSize) {int max = (1 << n) ;int mask = max - 1;char buf[max][n + 1];int cnt = 0;// char **save = (char **)malloc(max * sizeof(char*));memset(buf,0,sizeof(buf));for(int i = 0;i<max;i++){int f = mask ^ i;   //取反操作int andf = f >> 1;  //与自身的右移一位相与// printf("f= %x,andf=%x,and=%d\n",f,andf,f&andf);//如果与运算不等于0，则代表有连续的1，没有连续的1则必然为0if((f & andf) == 0){dec2bin(i,n,buf[cnt]);cnt++;// save[cnt] = (char*)malloc( 33);// memset(save[cnt],0,33);// strcpy(save[cnt],buf);}}*returnSize = cnt;char **save = (char **)malloc(cnt * sizeof(char*) + 1);for(int i=0;i<cnt;i++){save[i] = (char*)malloc(n + 1);if(!save[i])return NULL;memset(save[i],0,n + 1);strncpy(save[i],buf[i],n);}// printf("size = %d\n",cnt);return save;
}