LeetCode二维数组例题（原地旋转和对角线遍历）-c语言

LeetCode二维数组例题（原地旋转和对角线遍历）-c语言

二维数组例题

• • 二维数组 矩阵旋转（原地旋转）
  • 对角线遍历

二维数组 矩阵旋转（原地旋转）

**方法一：**四个角是一个循环，引申到四个块是循环
n为偶数时，枚举n2/4个位置

n为奇数时，枚举（n2-1）/4个位置

void rotate(int** matrix, int matrixSize, int* matrixColSize) {
    for (int i = 0; i < matrixSize / 2; ++i) {
        for (int j = 0; j < (matrixSize + 1) / 2; ++j) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[matrixSize - j - 1][i];
            matrix[matrixSize - j - 1][i] = matrix[matrixSize - i - 1][matrixSize - j - 1];
            matrix[matrixSize - i - 1][matrixSize - j - 1] = matrix[j][matrixSize - i - 1];
            matrix[j][matrixSize - i - 1] = temp;
        }
    }
}

方法二先竖直翻转，再逆对角线翻转

//c语言没有swap函数 要手写
void swap(int *a,int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
void rotate(int** matrix, int matrixSize, int* matrixColSize){
    for(int i = 0;i < matrixSize;i++)
    {
        for(int j = 0;j < matrixSize/2;j++)
        {
            swap(&matrix[i][j],&matrix[i][matrixSize-j-1]);//这里传的是取地址符
        }
    }
    for(int i = 0;i < matrixSize-1;i++)
    {
        for(int j = 0;j < matrixSize-i;j++)//注意两个for循环条件
        {
            swap(&matrix[i][j],&matrix[matrixSize-j-1][matrixSize-i-1]);
        }
    }    
}

对角线遍历

当下标和为偶数时向右上遍历，当下标和为奇数时向左下遍历（我的代码中从0开始遍历）

int* findDiagonalOrder(int** mat, int matSize, int* matColSize, int* returnSize){
    if(matSize == 0){    //矩阵为空，返回0
        *returnSize = 0;
        return 0;
    }
    int arr = matSize*(*matColSize);
    int brr = matSize+(*matColSize)-1;
    printf("%d",brr);
    int* result = (int*)malloc(sizeof(int) * arr);
    int i,j;
    *returnSize = 0;
    for(int k = 0;k < brr;k++)
    {
        printf("%d",k);
        if(k % 2 == 0)
        {
            for(j = 0;j < *matColSize;j++)
            {
                if(k - j < 0)
                {
                    break;
                }
                if(k - j >= matSize)
                {
                    continue;
                }
                result[(*returnSize)] = mat[k-j][j];
                (*returnSize)++;
            }
        }
        else
        {
            for(i = 0;i < matSize;i++)
            {   
                if(k - i < 0)
                {
                    break;
                }
                if(k - i >= (*matColSize))
                {
                    continue;
                }
                result[(*returnSize)] = mat[i][k-i];
                (*returnSize)++;
            }
        }
    }
    return result;
}//时间较长

int* findDiagonalOrder(int** mat, int matSize, int* matColSize, int* returnSize){
    if(matSize == 0)
    {                                       //矩阵为空，返回0
        *returnSize = 0;
        return 0;
    }
    *returnSize = matSize * (*matColSize);
    int* ans = (int*)malloc(sizeof(int) * (*returnSize));
    int i=0, j=0, n=0;
    while(n < (*returnSize))
    {                               //循环遍历矩阵
        ans[n] = mat[i][j];                                
        if((i + j) % 2 == 0)
        {                               //下标和为偶数，向右上遍历
            if(j < (*matColSize)-1){
                j++;
                if(i > 0)                                   //边界情况
                    i--;
            }
            else                                           //边界情况
                i++;
        }
        else
        {                                              //下标和为奇数，向左下遍历
            if(i < matSize-1)
            {
                i++;
                if(j > 0)                                   //边界情况
                    j--;
            }
            else                                           //边界情况
                j++;
        }
        n++;
    }
    return ans;
}