91. 解码方法/89. 格雷编码/78. 子集/5 N进制小数

91. 解码方法

/*
递归 


个位数 1 ~ 9 
十位数 10 ~ 26
超出时间限制
239 / 258 个通过测试用例
看来要DP

C  没有哈希函数 没办法 递归 + 记忆 。。。。
但是 这个题 可以用 L做 KEY 哈哈哈哈哈

*/
#define BUFLEN 3
#define STRLEN 10000
int stoInt(char *s, int len)
{
    char temp[BUFLEN] = {0};
    memcpy(temp, s, len);
    return atoi(temp);
}

int recur(char *s, int Idx, int hm[STRLEN])
{
    if (hm[Idx] != 0) {
        return hm[Idx]; // 已经有过了
    }

    if (Idx == strlen(s)) {
        return 1;
    }
    int ways = 0;

    //个位数
    int temp = 0;
    temp = stoInt(s + Idx, 1);
    if ( temp != 0) {
        ways += recur(s, Idx + 1, hm);
    } else {
        return 0; // == 0 over
    }
    if (temp < 3) {
        //十位数
        temp = stoInt(s + Idx, 2);
        if ( temp >= 10 && temp <= 26) {
            // printf("2 : %d \n", temp);
            ways += recur(s, Idx + 2, hm);
        }
    } 

    hm[Idx] = ways;
    return ways;

}

int numDecodings(char * s){
    if (s == NULL || strlen(s) == 0) {
        return 0;
    }
    int hm[STRLEN] = {0};
    return recur(s, 0, hm);;
}

89. 格雷编码

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

/*
递归

理解错题目了 

是个数学题。。。。就是 递增一个数，不断的和 》》 1 的自己异或
0 ^ 0 = 000 ^ 000 = 000
1 ^ 0 = 001 ^ 000 = 001
2 ^ 1 = 010 ^ 001 = 011 
3 ^ 1 = 011 ^ 001 = 010
4 ^ 2 = 100 ^ 010 = 110
5 ^ 2 = 101 ^ 010 = 111
6 ^ 3 = 110 ^ 011 = 101
7 ^ 3 = 111 ^ 011 = 100

*/

// void recur(int n, int* returnSize, int curIdx, int curValue, int *res)
// {
//     if (n == curIdx) {
//         printf(BYTE_TO_BINARY_PATTERN, BYTE_TO_BINARY(curValue));
//         res[++(*returnSize)] = curValue;
//         return;
//     }
//     if (n - curIdx == 1) {
//         recur(n, returnSize, curIdx + 1, curValue + V(1, curIdx), res);
//         recur(n, returnSize, curIdx + 1, curValue + V(0, curIdx), res);
//     } else {
//         recur(n, returnSize, curIdx + 2, curValue + V(0, curIdx), res);
//         recur(n, returnSize, curIdx + 2, curValue + V(1, curIdx), res);
//         recur(n, returnSize, curIdx + 2, curValue + V(3, curIdx), res);
//         recur(n, returnSize, curIdx + 2, curValue + V(2, curIdx), res);
//     }
// }

int* grayCode(int n, int* returnSize){
    int resLen = (1 << n);
    int *res = (int *)malloc(sizeof(int) * resLen);
    // (*returnSize) = -1;
    // recur(n, returnSize, 0, 0, res);
    for (int i = 0; i < resLen; i++) {
        res[i] = (i ^ (i>>1));
    }
    (*returnSize) = resLen;
    return res;
}

78. 子集

#define BUFLEN 10000

void recur( int* nums, int numsSize, int* returnSize, int* col, int cur, int* buf, int **res, int *bufLen)
{
    // printf("%d %d \n", cur, (*bufLen));
    // for (int i =0; i< (*bufLen); i++) {
    //     printf("%d ", buf[i]);
    // }
    // printf("end \n");
    memcpy(res[(*returnSize)], buf, (*bufLen) * sizeof(int));
    col[(*returnSize)] = (*bufLen);
    (*returnSize)++;

    for (int i = cur; i < numsSize; i++) {
        buf[(*bufLen)++] = nums[i];
        recur(nums, numsSize, returnSize, col, i + 1, buf, res, bufLen); // 每次递归 i+ i 而不是 cur + 1 
        (*bufLen)--;
    }
}

int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){

    int **res = (int **)malloc(sizeof(int *) * BUFLEN);
    (*returnColumnSizes) = (int *)malloc(sizeof(int) * BUFLEN);
    
    memset(res, 0, sizeof(int *) * BUFLEN);
    memset((*returnColumnSizes), 0, sizeof(int) * BUFLEN);
    (*returnSize) = 0;
    for (int i = 0; i < BUFLEN; i++) {
        res[i] = (int *)malloc(sizeof(int) * numsSize);
        memset(res[i], 0 , sizeof(int) * numsSize);
        (*returnColumnSizes)[i] = 0;
    }

    
    int *buf = (int *)malloc(sizeof(int) * numsSize);
    memset(buf, 0, sizeof(int) * numsSize);
    int bufLen = 0;
    
    recur(nums, numsSize, returnSize, *returnColumnSizes, 0, buf, res, &bufLen);
    free(buf);
    return res;
}

5 N进制小数

/*
 * Copyright (c) Huawei Technologies Co., Ltd. 2012-2018. All rights reserved.
 * Description: 项目 N进制小数 的源文件
 * Author: f00496942
 * Create: 2020-03-04
 */
#include <stdio.h>
#include "securec.h"

#define REMNUM 10


void code(double m, int n)
{
    int res[REMNUM] = {0};

    for (int i = 0; i < REMNUM; i++) {
        m *= n;
        res[i] = (int)(m);
        if (m > 1.0) {
            m -= res[i];
        }
    }

    printf("0.");
    for (int i = 0; i < REMNUM; i++) {
        printf("%d", res[i]);
    }
    printf("\n");
}

int main()
{   
    double m;
    int n;
    while (scanf_s("%lf %d", &m, &n) != EOF) {
        if (n == 0) {
            break;
        }
        code(m, n);
    }

    return 0;
}