93.复原IP地址
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "[email protected]" 是 无效的 IP 地址。
注意**：
1、sprintf：sprintf 没有办法拷贝char*格式的东西，需要用strcpy
2、一个个输入字符，最后形成字符串：老老实实开辟（len+1）的空间，一个个输入字符，最后添加or不添加‘\0’都可以，可以提前添加'\0'终止字符串的创建
3、为什么不能用ascii码做？
用ascii比较字符串大小的时候：需要保证两个都是‘\0’结尾
而strncpy是截取了一段，需要补上‘\0’
void bp(char *s,int *returnSize,char **ans,char*path,int p,int count,int index,int totallen){
if(count ==5){
ans[*returnSize]=(char*)malloc(sizeof(char)*(totallen+4));
path[p-1]='\0';
strcpy(ans[*returnSize], path);
printf("%s\n",path);
(*returnSize)++;
return;
}
char *d=(char *)malloc(sizeof(char)*5);
//printf("i=%d ,count=%d,p=%d,totallen=%d\n",index,count,p,totallen);
//printf("%d",(4-count)*3+index+1);
if(index<totallen && (4-count)+index+1<=totallen && totallen<=(4-count)*3+index+1){
//strncpy(d,s+index,1);
printf("1111");printf("i=%d ,count=%d,p=%d,totallen=%d\n",index,count,p,totallen);
path[p]=s[index];
path[p+1]='.';
//sprintf(path+p, "%s.", d);
bp(s, returnSize, ans,path, p+2, count+1,index+1,totallen);
}
if( index+1<totallen && s[index]!='0' && (4-count)+index+2<=totallen && totallen<=(4-count)*3+index+2 ){
//strncpy(d,s+index,2);
//sprintf(path+p, "%s.", d)；——感觉sprintf用不了的原因应该是？？？？？？？？
printf("2222");printf("i=%d ,count=%d,p=%d,totallen=%d\n",index,count,p,totallen);
path[p]=s[index];
path[p+1]=s[index+1];
path[p+2]='.';
bp(s, returnSize, ans,path, p+3, count+1,index+2,totallen);
}
if(index+2<totallen && s[index]!='0' && (4-count)+index+3<=totallen && totallen<=(4-count)*3+index+3 ){
printf("3333");printf("i=%d ,count=%d,p=%d,totallen=%d\n",index,count,p,totallen);
strncpy(d,s+index,3);
printf("%d",strcmp(d,"255"));
//(s[index]-'0')*100+(s[index+1]-'0')*10+s[index+2]-'0'<=255
//sprintf(path+p, "%s.", d);
if((s[index]-'0')*100+(s[index+1]-'0')*10+s[index+2]-'0'<=255) 为什么不能用strcmp和字符串比较的方法？
{path[p]=s[index];
path[p+1]=s[index+1];
path[p+2]=s[index+2];
path[p+3]='.';
bp(s, returnSize, ans,path, p+4, count+1,index+3,totallen);}
}
}
char** restoreIpAddresses(char* s, int* returnSize) {
char **ans=(char **)malloc(sizeof(char*)*200);
*returnSize=0;
int len=strlen(s);
if(len >12 || len<4) return NULL;
char *path=(char *)malloc(sizeof(char)*(len+5));
int p=0;
bp(s, returnSize, ans, path, 0, 1, 0, len);
return ans;
}78.子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例: 输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
void bp(int *nums,int numsSize,int *returnSize,int **ans,int *path,int p,int **returnColumnSizes,int count,int start){
if(count>=numsSize ){
ans[*returnSize]=(int*)malloc(sizeof(int )*p);
memcpy(ans[*returnSize], path,sizeof(int)*p);
(*returnColumnSizes)[*returnSize]=p;
(*returnSize)++;
return;
}
for(int i=start;i<numsSize;i++){
bp(nums, numsSize, returnSize, ans, path, p, returnColumnSizes, count+1,i+1);//放或不放
path[p]=nums[i];
bp(nums, numsSize, returnSize, ans, path, p+1, returnColumnSizes, count+1,i+1);
}
}
int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
int **ans=(int**)malloc(sizeof(int *)*pow(2,numsSize));
*returnSize=0;
int *path=(int*)malloc(sizeof(int)*numsSize);
int p=0;
*returnColumnSizes=(int *)malloc(sizeof(int)*pow(2,numsSize));
bp(nums, numsSize,returnSize, ans, path, p, returnColumnSizes, 0,0);
return ans;
}90.子集II
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
- 输入: [1,2,2]
- 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
分析：
防止重复——从小到大排列——数出重复的个数，然后再进行插入
int cmp(const void* a, const void* b){ return *(int*)a - *(int*)b;}
void bp(int *nums,int numsSize,int *returnSize,int **ans,int *path,int p,int **returnColumnSizes,int start){
if(start>=numsSize ){
ans[*returnSize]=(int*)malloc(sizeof(int )*p);
memcpy(ans[*returnSize], path,sizeof(int)*p);
(*returnColumnSizes)[*returnSize]=p;
(*returnSize)++;
return;
}
int j=start;
while (j<numsSize-1 && nums[j]==nums[j+1]){//重复的个数有j-start个，有j-start+1个i
j++;
}
printf("%d %d \n",start,j);
//分别放入0个~j-start+1个i
for (int k=0;k<=j-start+1;k++){
int in;
for (in=0;in <k;in++){
path[p+in]=nums[j];
}
bp(nums, numsSize, returnSize, ans, path, p+k, returnColumnSizes,j+1);
}
}
int** subsetsWithDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
qsort(nums, numsSize, sizeof(int), cmp);
int **ans=(int**)malloc(sizeof(int *)*pow(2,numsSize));
*returnSize=0;
int *path=(int*)malloc(sizeof(int)*numsSize);
int p=0;
*returnColumnSizes=(int *)malloc(sizeof(int)*pow(2,numsSize));
bp(nums, numsSize,returnSize, ans, path, 0, returnColumnSizes, 0);
return ans;
}