这是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;
}