200. 岛屿数量/221. 最大正方形/93. 复原IP地址

200. 岛屿数量

• 相关标签： BFS DFS 并查集

// 这题就是个 图染色的问题 dfs 递归写吧 


void dfs(char **grid, int gridSize, int* gridColSize, int i, int j, int **visited)
{
    if (i < 0 || i >=gridSize || j < 0 || j >=  *gridColSize || visited[i][j] == 1 || grid[i][j] != '1') {
        return;
    }
    // 1. 标记为 visited 
    if (visited[i][j] == 0) {
        visited[i][j] = 1;
    }
    
    dfs(grid, gridSize, gridColSize, i - 1, j, visited);
    
    dfs(grid, gridSize, gridColSize, i + 1, j, visited);
    
    dfs(grid, gridSize, gridColSize, i, j - 1, visited);
    
    dfs(grid, gridSize, gridColSize, i, j + 1, visited);
    
    return ;
    
}

int numIslands(char** grid, int gridSize, int* gridColSize){
    if (grid == NULL || gridSize == 0 || gridColSize == NULL || *gridColSize == 0) {
        return 0;
    }

    int **visited = (int **)malloc(sizeof(int *) * gridSize);
    for (int i = 0; i < gridSize; i++) {
        visited[i] = (int *)malloc(sizeof(int) * (*gridColSize));
        memset(visited[i], 0, sizeof(int) * (*gridColSize));
    }

    int landNum = 0; 
    for (int i = 0; i < gridSize; i++) {
        for (int j =0; j < *gridColSize; j++) {
            if (grid[i][j] == '1' && visited[i][j] == 0) { //遍历数据 遇到1 就进去染色
                dfs(grid, gridSize, gridColSize, i, j, visited);
                landNum++;
            }
        }
    } 
    
//     for (int i = 0; i < gridSize; i++) {
//         for (int j =0; j < *gridColSize; j++) { 
//             printf("%d -", visited[i][j]);

//         } 
//         printf("\n");
//     }

    for (int i = 0; i < gridSize; i++) {
        free(visited[i]);
    }
    free(visited);
    return landNum;
}

221. 最大正方形

• 相关标签 ： 动态规划

/*
思路： 


1. 暴力 

for (i...m) 
    for (j...n)
        i,j 为 左上的 所有 边长的情况 

eg : 
0,0 为 i，j 
    00-11, 00-22, 00-33 每次都要遍历 n*n  
    
    有很多重叠的地方 重复遍历 
    
    有可能是DP 
    
DP ： DP[i][j] 表示什么？ 表示 从0,0 到 i,j 的 最大正方形 的 最大边长 

dp[i][j] = if 当前 是 0  ， 那么 00 - ij 就不可能是正方形 ， 最大边长为0  dp[i][j] == 0
            else : 看一下 上面 左边 和左上 最小的边长  ， 加上自身的 1  得到 当前的最大边长

*/



int lMin(int a, int b, int c) {
    int temp  = (a < b) ? a : b;
    return temp < c ? temp : c;
}


int maximalSquare(char** matrix, int matrixSize, int* matrixColSize){
    if( matrix == NULL || matrixSize ==0 || matrixColSize == NULL || *matrixColSize == 0) {
        return 0;
    }
    
    int **dp = (int **)malloc(sizeof(int *) * (matrixSize + 1));
    for (int i = 0; i < matrixSize + 1; i++) {
        dp[i] = (int *)malloc(sizeof(int) * (*matrixColSize + 1));
        memset(dp[i], 0, sizeof(int) * (*matrixColSize + 1));
    }
        
    int res = 0;
    
    for (int i = 0; i < matrixSize; i++) {
        for (int j =0; j < *matrixColSize; j++) {
            dp[i + 1][j + 1] =  (matrix[i][j] == '0') ? 0 : (lMin(dp[i][j], dp[i+1][j], dp[i][j+1]) + 1);
            if (dp[i + 1][j + 1] > res) {
                res = dp[i + 1][j + 1];
            }
        }
    }
    

    
    for (int i = 0; i < matrixSize + 1; i++) {
        free(dp[i]);
    }
    free(dp);
    return res * res;

}

93. 复原IP地址

• 相关标签 ： 字符串， 回溯算法

#define BUFLEN 10000
#define STRLEN 100
void helper(char **resArr, char *s, char *curIp, int curIdx, int index, int remain, int *returnSize)
{
    if (remain == 0) {
        if (index == strlen(s)) {
            resArr[*returnSize] = (char *)malloc(STRLEN);
            memset(resArr[*returnSize], 0 , STRLEN);
            memcpy(resArr[*returnSize], curIp, STRLEN);
            (*returnSize)++;
        }
        return;
    }
    int curVal = 0;
    char subStr[4] = {0};
    for (int i = 1; i <= 3; i++) {
        memcpy(subStr, s + index, i);
        // 首位为0 ， 只可能是0 
        if (subStr[0] == '0' && i > 1) {
            continue;
        }
        curVal = strtol(subStr, (char **)NULL, 10);
        if (curVal >= 0 && curVal <= 255) {
            if (remain == 1) {
                sprintf(curIp + curIdx, "%d", curVal);
            } else {
                sprintf(curIp + curIdx, "%d.", curVal);
            }
            helper(resArr, s, curIp, curIdx + strlen(subStr) + 1, index + i, remain - 1, returnSize);
        }
    }
    return;
}
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char ** restoreIpAddresses(char * s, int* returnSize){
    *returnSize = 0;
    if (s == NULL || strlen(s) < 4) {
        return NULL;
    }
    char **resArr = (char **)malloc(sizeof(char *) * BUFLEN);
    if (resArr == NULL) {
        return NULL;
    }
    memset(resArr, 0, sizeof(char *) * BUFLEN);

    char *curIp = (char *)malloc(STRLEN);
    if (curIp == NULL) {
        return NULL;
    }
    memset(curIp, 0, STRLEN);
    
    helper(resArr, s, curIp, 0, 0, 4, returnSize);
    
    free(curIp);
    printf("%d\n", *returnSize);
    return resArr;
}