48 旋转图像/ 96. 不同的二叉搜索树/49. 字母异位词分

48 旋转图像

• 相关标签： 数组

#include <math.h>

void swap(int *a, int *b) // 原理就是 ： 一个数 异或自己 就是变成 0
{
    *a^=*b; // a 和  b 异或， 异或的结果delta 存在 a 的位置上， 所以delta == a ^ b
    *b^=*a; // 拿 这个 delta 再去异或一下 b ， 那么b 的位置就变成了 b^a^b == a
    *a^=*b; // 再拿 a (现在在b 的位置上)， 去异或 a 的位置 a 的位置就变成 a^b^a == b
}


void rotate(int** matrix, int matrixSize, int* matrixColSize){
    if (matrix == NULL || matrixSize==0 || matrixColSize==NULL || *matrixColSize ==0) {
        return; // 二维数组 入口要判空 
    }
    // 1、 (i,j) -> (j,i)
    for (int i = 0; i < matrixSize; i++) {
        for (int j = i + 1; j < *matrixColSize; j++) {
            swap(&matrix[i][j], &matrix[j][i]); // 传地址进去
        }
    }

    // 2. (i,j) -> (i , n - j-1 )
    for (int i = 0; i < matrixSize; i++) {
        // 这边 1. 一定要除2.0 否则 整数除整数，C中会把小数截断、
        // 2 . ceil 返回的是和double 类型 要转成 int 
        for (int j = (int)ceil(*matrixColSize / 2.0); j < *matrixColSize; j++) {
            swap(&matrix[i][j], &matrix[i][*matrixColSize - j - 1]); // 左右坐标之和是 n-1 不是n
        }
    }
}

96. 不同的二叉搜索树

• 相关标签： 动态规划

// 递归

// 以 N = 3 为例
/*
头节点选 1 
    左 0 右2  == 2 
选2 
    左 1 右1  == 1
选3 
    左 2 右0  // == 2
    
    >> 左2 也就是 n 为2 的情况 == 2
        头选 1
         左 0 右 1  == 1
        选2
         左 1 右 0  == 1
    >> 左1, 0  也就是 N= 1 , 0 的情况  == 1 
*/


// 超时了！！！ 不能用递归
// int numTrees(int n){
//     if (n <= 1) {
//         return 1;
//     }
//     int res = 0;
//     for (int i = 1; i <= n; i++) { // 以 1 到 N  为头结点 的所有情况的 和
//         res += numTrees(i - 1) * numTrees(n - i);
//     }
//     return res;
// }

// 前面递归是 从n 往 1 撸的 超时了
// 现在用DP 从1 往 N 去记录 
/*

dp[n] = dp[0]*dp[n-1] + dp[1] * dp[n-2] +.... dp[n-2] * dp[1] + dp[n-1]*dp[0]

dp(1) = dp[0] = 1
dp[2] = dp[0]dp[1] + dp[1]dp[0]
dp[3] = dp[0]dp[2] + dp[1][1] + dp[2][0]
....

所以只要能从1 往 N 算的话 ， 就不会冗余计算了
*/
#define DPSIZE 1000
int numTrees(int n){
    int dp[DPSIZE] = {0};
    
    dp[0] = 1;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= i -1; j++) {
            dp[i] += dp[j] * dp[i - 1 - j];
        } 
    }
    
    return dp[n];
}

49. 字母异位词分组

• 相关标签： 字符串

1. hash 超时！
/**
 * 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().
 */



#define HMSIZE 10000000
int PRIMES[] = {2, 3, 5, 7, 11 ,13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 107};

int AnaVal(char *a)
{
    unsigned long long p1 = 1;
    for (int i = 0; i < strlen(a); i++) {
        p1 *= PRIMES[a[i] - 'a'];
    }
    return (int)(p1 % HMSIZE);
}

char *** groupAnagrams(char ** strs, int strsSize, int* returnSize, int** returnColumnSizes){
    int idx = 0;
    
    if (strs == NULL || strsSize == 0 || returnSize == NULL || *returnSize == 0) {
        return NULL;
    }
    // 1. 开一个 一位数组存储该单词 的 异或值
    int *grouped = (int *)malloc(sizeof(int) * strsSize);
    int numG = 0;
    int curVal = 0;
    int numGOfName[HMSIZE] = {0};
    memset(grouped, 0, sizeof(int) * strsSize);
    
    // 2. 统计一下多少组， 每组多少个
    int hm[HMSIZE] = {0};
    
    for (int i = 0; i < strsSize; i++) {
        grouped[i] = AnaVal(strs[i]);
        if (hm[grouped[i]] == 0) {
            numGOfName[numG] = grouped[i];
            numG++; // 记录组的个数
        }
        hm[grouped[i]]++;
    }
    
    // for (int i = 0; i < numG; i++) {
    //     printf("z id %d - z num %d\n",numGOfName[i], hm[numGOfName[i]] );
    // }
    
    // 3. 填写返回值
    char ***resArr = (char ***)malloc(sizeof(char **) * numG);
    *returnSize = numG;
    *returnColumnSizes = (int *)malloc(sizeof(int) * numG); // 外部 只是 写了个 int *returnColumnSizes = NULL; 这里需要自己申请这个数组
    for (int i = 0; i < numG; i++) {
        resArr[i] = (char **)malloc(sizeof(char *) * hm[numGOfName[i]]); 
        (*returnColumnSizes)[i] = 0;
    }
    
    for (int i = 0; i < strsSize; i++) {
        curVal = AnaVal(strs[i]);
        resArr[i][idx] = 
        
    }
    return resArr;
    
}