739. 每日温度/46. 全排列

739. 每日温度

• 相关标签 : 哈希表 栈

/*
暴力的话 就n2 能改定 
但是 可能会超时 pass 35/37
*/

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
// int* dailyTemperatures(int* T, int TSize, int* returnSize){
//     if (T == NULL || TSize == 0) { // 入参校验
//         return NULL;
//     }
//     int *res = (int *)malloc(sizeof(int) * TSize); //申请返回数组内存
//     if (res == NULL) {
//         return NULL;
//     }
//     memset(res, 0 , sizeof(int) * TSize);
    
//     int t_day;
//     for (int i = 0; i < TSize; i++) {
//         t_day = 0;
//         for (int j = i + 1; j < TSize; j++) {
//             t_day++;
//             if (T[j] > T[i]) {
//                 res[i] = t_day;
//                 break;
//             }

//         }
//     }
//     *returnSize = TSize;
//     return res;
// }



#define STACKSIZE 30000
int* dailyTemperatures(int* T, int TSize, int* returnSize){
    if (T == NULL || TSize == 0) { // 入参校验
        return NULL;
    }
    int *res = (int *)malloc(sizeof(int) * TSize); //申请返回数组内存
    if (res == NULL) {
        return NULL;
    }
    memset(res, 0 , sizeof(int) * TSize);
    int stack[STACKSIZE] = {0};
    int stacklen = -1;
    
    for (int i = TSize -1; i >=0; i--) {
        if (stacklen == -1) { // 栈为空
            res[i] = 0;
            stack[++stacklen] = i;
        } else {
            //由于是 倒序， 所以 新入栈的 应该比栈顶小， 才是 递增的情况， 如果
            if (T[i] >= T[stack[stacklen]]) { //大于等于 栈顶 往下pop  知道找到小于栈顶的  就可以计算距离了 或者没找到 就是 0
                while (stacklen != -1) {
                    stacklen--;
                    if (stacklen  == -1) {
                        res[i] = 0;
                        stack[++stacklen] = i;
                        break;
                    }
                    if(T[stack[stacklen]] > T[i]) {
                        res[i] = stack[stacklen] - i;
                        stack[++stacklen] = i;
                        break;
                    }
                }
            } else {
                    res[i] = 1;
                    stack[++stacklen] = i; 
            }

        }
    }
    

    *returnSize = TSize;
    return res;
}

46. 全排列

• 相关标签： 回溯算法

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */


int factorial(int n) 
{
    return (n == 1) ? 1 : n * factorial(n - 1);
}

void recur(int* nums, int numsSize, int *visited, int **res, int* returnSize, int** returnColumnSizes, int visitedLen, int *temp)
{
    
    if (visitedLen == numsSize) {
        res[*returnSize] = (int *)malloc(sizeof(int) * numsSize);
        memset(res[*returnSize], 0, sizeof(int) * numsSize);
        memcpy(res[*returnSize], temp, sizeof(int) * numsSize);
        printf("%d |", *returnSize);
        for (int i = 0; i < numsSize; i++) {
            printf("%d ", res[*returnSize][i]);
        }
        printf("\n");
        (*returnColumnSizes)[*returnSize] = numsSize; // [] 高于 * 也要加括号
        (*returnSize)++; // ++优先级 高于 *  要加 （）
        return;
    }
    
    for (int i = 0; i < numsSize; i++) {
        if (visited[i] == 0) { //没有被选择过
            visited[i] = 1;
            temp[visitedLen] = nums[i];
            recur(nums, numsSize, visited, res, returnSize, returnColumnSizes, visitedLen + 1, temp);
            visited[i] = 0;
        }
    }
    
    
}

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    
    int len = factorial(numsSize);
    
    *returnColumnSizes = (int *)malloc(sizeof(int)* len); // 这个是 列长度的数组 也需要 申请内村 否则会包内存异常
    memset(*returnColumnSizes, 0, sizeof(int)* len);
    int **res = (int **)malloc(sizeof(int *) * len);
    // 临时变量
    int *visited = (int *)malloc(sizeof(int) * numsSize);
    memset(visited, 0,  sizeof(int) * numsSize);
    int *temp = (int *)malloc(sizeof(int) * numsSize);
    memset(temp, 0,  sizeof(int) * numsSize);
    
    *returnSize = 0; // 这边要赋值为0  否则 也是 内存地址异常
    recur(nums, numsSize, visited, res, returnSize, returnColumnSizes, 0, temp);
    
    free(visited);
    free(temp);
    return res;
}