# Analysis of leetcode problem solving ideas 542 - 551 questions

1. 01 matrix
Given a matrix consisting of 0 and 1, find the distance from each element to the nearest 0. The distance between two adjacent elements is 1.

The solution is obtained by dynamic programming

```class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix.size();
// Initialize the array of dynamic programming, and set all distance values to a large number
vector<vector<int>> dist(m, vector<int>(n, INT_MAX / 2));
// If the element of (i, j) is 0, the distance is 0
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 0) {
dist[i][j] = 0;
}
}
}
// Only move horizontally to the left and vertically upward. Pay attention to the calculation order of dynamic programming
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i - 1 >= 0) {
dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1);
}
if (j - 1 >= 0) {
dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1);
}
}
}
// Only move horizontally to the right and vertically down. Pay attention to the calculation order of dynamic programming
for (int i = m - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (i + 1 < m) {
dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1);
}
if (j + 1 < n) {
dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1);
}
}
}
return dist;
}
};

```
1. Diameter of binary tree
Given a binary tree, you need to calculate its diameter and length. The diameter length of a binary tree is the maximum of any two node path lengths. This path may or may not pass through the root node.

Depth first traversal

```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
int ans;
int depth(TreeNode* rt){
if (rt == NULL) {
return 0; // Null node accessed, return 0
}
int L = depth(rt->left); // The depth of the subtree with the left son as the root
int R = depth(rt->right); // The depth of the subtree whose right son is the root
ans = max(ans, L + R + 1); // Calculation d_node is L+R+1 and updates ans
return max(L, R) + 1; // Returns the depth of the subtree whose node is the root
}
public:
int diameterOfBinaryTree(TreeNode* root) {
ans = 1;
depth(root);
return ans - 1;
}
};

```
1. Remove box
Give some boxes of different colors. The color of the box is represented by numbers, that is, different numbers represent different colors. You will go through several rounds of operations to remove the box until all the boxes are removed. In each round, you can remove k consecutive boxes with the same color (k > = 1), and after this round, you will get k * k points. When you remove all the boxes, find the maximum sum of points you can get.

This problem can be solved by dynamic programming. dp[l][r][k] represents the interval from L to r, and the maximum integral sum when there are k same elements after r. This is necessary because the score depends not only on the subsequence, but also on the impact of the previous movement on the current array, which may make the final subsequence not a continuous substring

```class Solution {
public:
int dp;

int removeBoxes(vector<int>& boxes) {
memset(dp, 0, sizeof dp);
return calculatePoints(boxes, 0, boxes.size() - 1, 0);
}

int calculatePoints(vector<int>& boxes, int l, int r, int k) {
if (l > r) {
return 0;
}
if (dp[l][r][k] == 0) {
dp[l][r][k] = calculatePoints(boxes, l, r - 1, 0) + (k + 1) * (k + 1);
for (int i = l; i < r; i++) {
if (boxes[i] == boxes[r]) {
dp[l][r][k] = max(dp[l][r][k], calculatePoints(boxes, l, i, k + 1) + calculatePoints(boxes, i + 1, r - 1, 0));
}
}
}
return dp[l][r][k];
}
};

```
1. Number of provinces

Take DFS/BFS traversal

```class Solution {
public:
void dfs(vector<vector<int>>& isConnected, vector<int>& visited, int provinces, int i) {
for (int j = 0; j < provinces; j++) {
if (isConnected[i][j] == 1 && !visited[j]) {
visited[j] = 1;
dfs(isConnected, visited, provinces, j);
}
}
}

int findCircleNum(vector<vector<int>>& isConnected) {
int provinces = isConnected.size();
vector<int> visited(provinces);
int circles = 0;
for (int i = 0; i < provinces; i++) {
if (!visited[i]) {
dfs(isConnected, visited, provinces, i);
circles++;
}
}
return circles;
}
};

```
1. Student attendance record
If A student has no more than one 'A' (absence) and no more than two consecutive 'L' (late) in his attendance record, the student will be rewarded.
You need to judge whether the student will be rewarded according to his attendance record.

Go through it and judge it

```class Solution {
public:
bool checkRecord(string s)
{
int absent = 0, lateContinue = 0;

for (auto c : s)
{
if (c == 'A')
{
lateContinue = 0;
absent++;
if (absent > 1) return false;
}
else if (c == 'L')
{
lateContinue++;
if (lateContinue > 2)
return false;
}
else
{
lateContinue = 0;
}
}

return true;
}
};
```

Posted by SecureMind on Tue, 19 Apr 2022 07:22:34 +0930