|
/*******************************************************************************
函 数 名 : 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++){
m[nums1[i]] = i;//建立每个元素与其应放位置的映射关系
}
int loops = 0;//循环节个数
vector<bool> flag(len,false);
//找出循环节的个数
for (int i = 0; i < len; i++){
if (!flag[i]){//已经访问过的位置不再访问
int j = i;
while (!flag[j]){
flag[j] = true;
j = m[nums[j]];//原序列中j位置的元素在有序序列中的位置
}
loops++;
}
}
return len - loops;
}
int main()
{
vector<int> nums;
//3, 7, 1, 6, 2, 4, 8, 5
nums.push_back(3);
nums.push_back(7);
nums.push_back(1);
nums.push_back(6);
nums.push_back(2);
nums.push_back(4);
nums.push_back(8);
nums.push_back(5);
int res=getMinSwaps(nums);
system("pause");
return 0;
} | 
转播
