leetcode练习

傷城~ 2022-12-23 15:28 209阅读 0赞

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

函 数 名 : 547 朋友圈

功能描述 :

输入参数 : None

输出参数 : None

返 回 值 : None

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

void dfs(int\*\* M, int MSize, int i, int \*visit) \{

if (visit\[i\] == 1) \{

return;

visit\[i\] = 1;

for (int j = 0; j < MSize; j++) \{

if((M\[i\]\[j\] == 1) && (visit\[j\] == 0)) \{

dfs(M, MSize, j, visit);

int findCircleNum(int\*\* M, int MSize, int\* MColSize)\{

int count = 0;

int\* visit = (int \*)malloc(sizeof(int) \* MSize);

memset(visit, 0, sizeof(int) \* MSize);

for (int i = 0; i < MSize; i++) \{

if (visit\[i\] == 0) \{

dfs(M, MSize, i, visit);

count++;

return count;

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

函 数 名 : 200 岛屿

功能描述 :

输入参数 : None

输出参数 : None

返 回 值 : None

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

int dir\[4\]\[2\] = \{ \{0, 1\}, \{0, -1\}, \{1, 0\}, \{-1, 0\}\};

void dfs(char\*\* grid, int\*\* visited, int i, int j, int row, int col)

// 终止条件 1：访问边界超限

// 终止条件 2：邻居已都被访问过，或本身为0

if (i < 0 || i >= row || j < 0 || j >= col) \{

return;

if (grid\[i\]\[j\] == '0' || visited\[i\]\[j\] == 1) \{

return;

visited\[i\]\[j\] = 1;

int k, x, y;

for (k = 0; k < 4; k++) \{

x = i + dir\[k\]\[0\];

y = j + dir\[k\]\[1\];

dfs(grid, visited, x, y, row, col);

return;

int numIslands(char\*\* grid, int gridSize, int\* gridColSize)

int col = \*gridColSize;

int \*\*visited = (int \*\*)malloc(sizeof(int \*)\* gridSize);

int i, j;

for (i = 0; i < gridSize; i++) \{

visited\[i\] = (int \*)malloc(sizeof(int) \* col);

memset(visited\[i\], 0, sizeof(int) \* col);

int count = 0;

for (i = 0; i < gridSize; i++) \{

for (j = 0; j < col; j++) \{

if (grid\[i\]\[j\] == '1' && visited\[i\]\[j\] == 0) \{

dfs(grid, visited, i, j, gridSize, col);

count++;

return count;

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

函 数 名 : 水域大小

功能描述 :

输入参数 : None

输出参数 : None

返 回 值 : None

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

int dir\[8\]\[2\] = \{ \{0, 1\}, \{0, -1\}, \{1, 0\}, \{-1, 0\},

\{-1, -1\}, \{-1, 1\}, \{1, -1\}, \{1, 1\}\};

int sum = 0;

int cmp(const void\*a,const void\*b)//用来做比较的函数

return \*(int\*)a-\*(int\*)b;

\};

void dfs(int\*\* grid, int\*\* visited, int i, int j, int row, int col)

// 终止条件 1：访问边界超限

// 终止条件 2：邻居已都被访问过，或本身为0

if (i < 0 || i >= row || j < 0 || j >= col) \{

return;

if (grid\[i\]\[j\] != 0 || visited\[i\]\[j\] == 1) \{

return;

visited\[i\]\[j\] = 1;

sum++;

int k, x, y;

for (k = 0; k < 8; k++) \{

x = i + dir\[k\]\[0\];

y = j + dir\[k\]\[1\];

dfs(grid, visited, x, y, row, col);

return;

int\* pondSizes(int\*\* grid, int landSize, int\* landColSize, int\* returnSize)

if (grid == NULL) \{

\*returnSize = 0;

return NULL;

int col = \*landColSize;

int \*\*visited = (int \*\*)malloc(sizeof(int \*)\* landSize);

int i, j;

for (i = 0; i < landSize; i++) \{

visited\[i\] = (int \*)malloc(sizeof(int) \* col);

memset(visited\[i\], 0, sizeof(int) \* col);

int \*store = (int \*)malloc(sizeof(int) \* 100000);

memset(store, 0, sizeof(int) \* 100000);

int count = 0;

for (i = 0; i < landSize; i++) \{

for (j = 0; j < col; j++) \{

if (grid\[i\]\[j\] == 0 && visited\[i\]\[j\] == 0) \{

sum = 0;

dfs(grid, visited, i, j, landSize, col);

store\[count\] = sum;

count++;

qsort(store, count, sizeof(int), cmp);

\*returnSize = count;

return store;

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

函 数 名 : 129 根到叶子节点数字之和

功能描述 :

输入参数 : 二叉树、dfs

输出参数 : None

返 回 值 : None

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

/\*

struct TreeNode \{

int val;

struct TreeNode \*left;

struct TreeNode \*right;

\};

\*/

int sum = 0;

void dfs(struct TreeNode\* root, int num)

if (root->left == NULL && root->right == NULL) \{

num = num \* 10 + root->val;

sum += num;

printf("%d %d\\n", num, sum);

return;

num = num \* 10 + root->val;

if (root->left != NULL) \{

dfs(root->left, num);

if (root->right != NULL) \{

dfs(root->right, num);

int sumNumbers(struct TreeNode\* root)\{

sum = 0; // 后台多个用例，每次都要置0

if (root == NULL) \{

return 0;

dfs(root, 0);

return sum;

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

函 数 名 : 529 扫雷游戏

功能描述 :

输入参数 : None

输出参数 : None

返 回 值 : None

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

int dir\[8\]\[2\] = \{ \{0, 1\}, \{0, -1\}, \{1, 0\}, \{-1, 0\},

\{-1, -1\}, \{-1, 1\}, \{1, -1\}, \{1, 1\}\};

int isNeibor(char\*\* board, int i, int j, int row, int col) \{

int w, h;

int cnt = 0;

for (int k = 0; k < 8; k++) \{

w = i + dir\[k\]\[0\];

h = j + dir\[k\]\[1\];

if (w < 0 || w >= row || h < 0 || h >= col) \{

continue;

if (board\[w\]\[h\] == 'M') \{

cnt++;

return cnt;

void dfs(char\*\* board, char\*\* ret, int i, int j, int row, int col)

int w, h;

if (i < 0 || i >= row || j < 0 || j >= col) \{

return;

if (ret\[i\]\[j\] != 0) \{ // 已访问过

return;

int cnt = isNeibor(board, i, j, row, col);

if (board\[i\]\[j\] == 'E') \{

if (cnt != 0) \{ // E邻居有地雷

ret\[i\]\[j\] = '0' + cnt;

\} else \{

ret\[i\]\[j\] = 'B';

for (int k = 0; k < 8; k++) \{

w = i + dir\[k\]\[0\];

h = j + dir\[k\]\[1\];

dfs(board, ret, w, h, row, col);

\} else if (board\[i\]\[j\] == 'B') \{ // 空格

ret\[i\]\[j\] = 'B';

\} else if (board\[i\]\[j\] >= '1' && board\[i\]\[j\] <= '8') \{ // 数字

ret\[i\]\[j\] = board\[i\]\[j\];

\} else if (board\[i\]\[j\] == 'M') \{ // 地雷

ret\[i\]\[j\] = 'M';

\} else \{

ret\[i\]\[j\] = board\[i\]\[j\];

return;

void copy(char\*\* board, char\*\* ret, int row, int col)

int i, j;

for (i = 0; i < row; i++) \{

for (j = 0; j < col; j++) \{

ret\[i\]\[j\] = board\[i\]\[j\];

return;

void CopySimple(char\*\* board, char\*\* ret, int row, int col)

int i, j;

for (i = 0; i < row; i++) \{

for (j = 0; j < col; j++) \{

if (ret\[i\]\[j\] == 0) \{

ret\[i\]\[j\] = board\[i\]\[j\];

return;

char\*\* updateBoard(char\*\* board, int boardSize, int\* boardColSize, int\* click, int clickSize, int\* returnSize, int\*\* returnColumnSizes)

int row = boardSize;

int col = boardColSize\[0\];

int i;

\*returnColumnSizes = boardColSize;

char \*\*ret = (char \*\*)malloc(sizeof(char \*) \* row);

for (i = 0; i < row; i++) \{

ret\[i\] = (char \*)malloc(sizeof(char) \* col);

memset(ret\[i\], 0, sizeof(char) \* col);

// 地雷

if (board\[click\[0\]\]\[click\[1\]\] == 'M') \{

copy(board, ret, row, col);

ret\[click\[0\]\]\[click\[1\]\] = 'X';

\} else \{

dfs(board, ret, click\[0\], click\[1\], row, col);

CopySimple(board, ret, row, col);

\*returnSize = row;

return ret;

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

函 数 名 : 二叉树 检查平衡性

功能描述 :

输入参数 : None

输出参数 : None

返 回 值 : None

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

/\*\*

\* Definition for a binary tree node.

\* struct TreeNode \{

\* int val;

\* struct TreeNode \*left;

\* struct TreeNode \*right;

\* \};

\*/

int sub(int a, int b) \{

return a > b ? a - b: b - a;

int maxNum(int a, int b)

return a > b? a: b;

// 返回root节点深度

int dfs(struct TreeNode\* root, bool \*ret)

if (root == NULL) \{

return 0;

int left = dfs(root->left, ret);

int right = dfs(root->right, ret);

if (sub(left, right) > 1) \{

\*ret = false;

return maxNum(left, right)+1;

bool isBalanced(struct TreeNode\* root)\{

bool ret = true;

if (root == NULL) \{

return ret;

int cnt = dfs(root, &ret);

return ret;

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

函 数 名 : 使序列有序的最少交换次数

功能描述 : 给出一个序列，可交换任意两个数，使序列升序排列，求最少交换次数。

输入参数 : None

输出参数 : None

返 回 值 : None

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

\#include<iostream>

\#include<vector>

\#include<unordered\_map>

\#include<algorithm>

using namespace std;

int getMinSwaps(vector<int> &nums)\{

//排序

vector<int> nums1(nums);

sort(nums1.begin(),nums1.end());

unordered\_map<int,int> m;

int len = nums.size();

for (int i = 0; i < len; i++)\{