85. 最大矩形 - 力扣（LeetCode）
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
解题思路
依次遍历矩阵的每一行，计算每列落在的该行的”1“的个数，那么，本题就转换成了”柱状图的最大面积“。
代码实现
int largestRectangleArea(int* heights, int heightsSize){
int ans[heightsSize+2];
ans[0] = 0;
ans[heightsSize+1] = 0;
for(int i = 0; i < heightsSize; i++){
ans[i+1] = heights[i];
}
int stack[heightsSize+2];
int top = -1;
stack[++top] = 0;
int max = 0;
for(int i = 1; i < heightsSize+2; i++){
while(ans[i] < ans[stack[top]]){
max = fmax(max,(i-stack[top-1]-1)*ans[stack[top]]);
--top;
}
stack[++top] = i;
}
return max;
}int maximalRectangle(char** matrix, int matrixSize, int* matrixColSize) {
if (matrixSize == 0 || *matrixColSize == 0) {
return 0;
}
int maxArea = 0; // 记录最大矩形面积
int heights[*matrixColSize]; // 用于记录每列的高度
memset(heights, 0, sizeof(heights)); // 将 heights 数组初始化为0
for (int i = 0; i < matrixSize; i++) { // 遍历矩阵的每一行
for (int j = 0; j < *matrixColSize; j++) { // 遍历矩阵的每一列
if (matrix[i][j] == '1') { // 如果当前位置是矩形的一部分
heights[j] += 1; // 将该列的高度加1
} else {
heights[j] = 0; // 如果当前位置没有矩形，则将该列的高度重置为0
}
}
maxArea = fmax(maxArea, largestRectangleArea(heights, *matrixColSize)); // 计算当前行对应的直方图的最大矩形面积，并更新最大面积值
}
return maxArea; // 返回最大矩形面积
}994. 腐烂的橘子 - 力扣（LeetCode）
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
- 值
0代表空单元格； - 值
1代表新鲜橘子； - 值
2代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1
解题思路
BFS+队列
1° 定义一个辅助队列，存储烂橘子的横纵坐标，以及腐烂传播的时间time
2° 遍历矩阵，将首批坏橘子入队，并初始化腐烂传播时间为0
3° 从队首开始传染，头指针head++，腐烂传播时间+1，被传染的新鲜橘子入队，尾指针tail++，并更新入队橘子的腐烂传播时间为当前橘子+1。再进行下一轮感染，直到头尾指针相遇，即最后一轮传染结束。
4° 再次遍历矩阵，若仍存在新鲜橘子，则返回-1，否则直接返回time
代码实现
typedef struct{
int x,y,time;
}Queue;
int orangesRotting(int** grid, int gridSize, int* gridColSize){
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
// 初始化当前坐标，移动后坐标，当前分钟数
int x, y, xx, yy, time = 0;
// 初始化队列的头尾指针
int front, rear = 0;
Queue *q = (Queue*)malloc(sizeof(Queue)*gridSize*gridColSize[0]);
// 首轮烂橘子入队，且感染时间为0
for(int i=0;i<gridSize;i++){
for(int j=0;j<gridColSize[0];j++){
if(grid[i][j]==2){
q[rear].x = i;
q[rear].y = j;
q[rear++].time = 0;
}
}
}
// 队列有烂橘子
while(front!=rear){
x = q[front].x;
y = q[front].y;
// 从队首烂橘子开始且队首出队
time = q[front++].time;
// 向4个方向腐蚀
for(int i=0;i<4;i++){
xx = x + dx[i];
yy = y + dy[i];
// 下标越界或移动后不是新鲜橘子跳出此次循环
if(xx<0 || xx>=gridSize || yy<0 || yy>=gridColSize[0] || grid[xx][yy]!=1)
continue;
// 筛选后，新鲜橘子被腐蚀，将其入队
grid[xx][yy] = 2;
q[rear].x = xx;
q[rear].y = yy;
// 注意感染时间+1
q[rear++].time = time + 1;
}
}
// 判断网格中是否还有新鲜橘子
for(int i=0;i<gridSize;i++){
for(int j=0;j<gridColSize[0];j++){
if(grid[i][j]==1)
return -1;
}
}
return time;
}37. 解数独 - 力扣（LeetCode）
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
解题思路
多重递归+回溯
1° 首先构造判断函数isValid，判断当前填充的数字是否满足题干中的三个条件，如不满足则返回false，否则为true
2° 构造回溯函数，依次遍历矩阵并对空白格 "." ，对其进行填充k（1-9），更新board[i][j] == k，如满足函数isValid，则进入下一层循环，否则将当前格子复原成空白格，若填充完，则返回true，否则为无解。若遍历完棋盘后，没有return false，说明也满足数独条件，直接 return true
代码实现
bool isValid(char**board, int row, int col, int k){
// 判断当前行是否有重复元素
for(int i = 0; i < 9; i++){
if(board[i][col]==k){
return false;
}
}
// 判断当前列是否有重复元素
for(int j = 0; j < 9; j++){
if(board[row][j]==k){
return false;
}
}
// 计算当前九宫格左上角的位置
int startRow = (row/3)*3;
int startCol = (col/3)*3;
// 判断当前元素所在的九宫格是否有重复元素
for(int i = startRow; i < startRow+3; i++){
for(int j = startCol; j < startCol+3; j++){
if(board[i][j]==k){
return false;
}
}
}
// 满足以上三个条件则是有效的
return true;
}
bool backtracking(char** board,int boardSize,int* boardColSize){
for(int i = 0; i < boardSize; i++){
for(int j = 0; j < boardColSize[0]; j++){
// 遇到数字就跳过
if(board[i][j]!='.'){
continue;
}
// 依次将1-9填入当前位置
for(int k = '1'; k <= '9'; k++){
// 判断当前位置是否满足条件，是则进入下一层
if(isValid(board, i, j, k)){
board[i][j] = k;
// 判断下一层递归之后是否找到一种解法，直至填充完所有
if(backtracking(board, boardSize, boardColSize)){
return true;
}
// 一旦不满足数独条件，则回溯至上一层，将当前位置清零
board[i][j] = '.';
}
}
// 填入的9个数都不满足，说明此解法无效
return false;
}
}
// 遍历完了棋盘，没有返回false，说明找到了解法
return true;
}
void solveSudoku(char** board, int boardSize, int* boardColSize){
backtracking(board, boardSize, boardColSize);
}