【算法笔记自学】第 9 章 提高篇(3)——数据结构专题(2)

9.1树与二叉树

#include <cstdio>int main() {int n, m;scanf("%d%d", &n, &m);printf(n == m + 1 ? "Yes" : "No");return 0;
}

9.2二叉树的遍历

#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 50;struct Node {int l, r;
} nodes[MAXN];vector<int> pre;void preOrder(int root) {if (root == -1) {return;}pre.push_back(root);preOrder(nodes[root].l);preOrder(nodes[root].r);
}int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d%d", &nodes[i].l, &nodes[i].r);}preOrder(0);for (int i = 0; i < (int)pre.size(); i++) {printf("%d", pre[i]);if (i < (int)pre.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 50;struct Node {int l, r;
} nodes[MAXN];vector<int> pre;void preOrder(int root) {if (root == -1) {return;}preOrder(nodes[root].l);pre.push_back(root);preOrder(nodes[root].r);
}int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d%d", &nodes[i].l, &nodes[i].r);}preOrder(0);for (int i = 0; i < (int)pre.size(); i++) {printf("%d", pre[i]);if (i < (int)pre.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 50;struct Node {int l, r;
} nodes[MAXN];vector<int> pre;void preOrder(int root) {if (root == -1) {return;}preOrder(nodes[root].l);preOrder(nodes[root].r);pre.push_back(root);
}int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d%d", &nodes[i].l, &nodes[i].r);}preOrder(0);for (int i = 0; i < (int)pre.size(); i++) {printf("%d", pre[i]);if (i < (int)pre.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;const int MAXN = 50;struct Node {int l, r;
} nodes[MAXN];vector<int> layer;void layerOrder(int root) {queue<int> q;q.push(root);while (!q.empty()) {int front = q.front();q.pop();layer.push_back(front);if (nodes[front].l != -1) {q.push(nodes[front].l);}if (nodes[front].r != -1) {q.push(nodes[front].r);}}
}int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d%d", &nodes[i].l, &nodes[i].r);}layerOrder(0);for (int i = 0; i < (int)layer.size(); i++) {printf("%d", layer[i]);if (i < (int)layer.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;const int MAXN = 50;struct Node {int l, r;
} nodes[MAXN];int getHeight(int root) {if (root == -1) {return 0;}int leftHeight = getHeight(nodes[root].l);int rightHeight = getHeight(nodes[root].r);return max(leftHeight, rightHeight) + 1;
}int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d%d", &nodes[i].l, &nodes[i].r);}printf("%d", getHeight(0));return 0;
}

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;const int MAXN = 50;struct Node {int l, r;
} nodes[MAXN];int layers[MAXN];void layerOrder(int root) {queue<int> q;q.push(root);int layer = 1;while (!q.empty()) {int cnt = q.size();for (int i = 0; i < cnt; i++) {int front = q.front();q.pop();layers[front] = layer;if (nodes[front].l != -1) {q.push(nodes[front].l);}if (nodes[front].r != -1) {q.push(nodes[front].r);}}layer++;}
}int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d%d", &nodes[i].l, &nodes[i].r);}layerOrder(0);for (int i = 0; i < n; i++) {printf("%d", layers[i]);if (i < n - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 50;struct Node {int l, r;
} nodes[MAXN];vector<int> pre, in, post;int buildTree(int preL, int preR, int inL, int inR) {if (preL > preR) {return -1;}int root = pre[preL];int inIndexOfRoot;for (int i = inL; i <= inR; i++) {if (in[i] == root) {inIndexOfRoot = i;break;}}int leftCount = inIndexOfRoot - inL;nodes[root].l = buildTree(preL + 1, preL + leftCount, inL, inIndexOfRoot - 1);nodes[root].r = buildTree(preL + leftCount + 1, preR, inIndexOfRoot + 1, inR);return root;
}void postOrder(int root) {if (root == -1) {return;}postOrder(nodes[root].l);postOrder(nodes[root].r);post.push_back(root);
}int main() {int n, x;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &x);pre.push_back(x);}for (int i = 0; i < n; i++) {scanf("%d", &x);in.push_back(x);}int root = buildTree(0, n - 1, 0, n - 1);postOrder(root);for (int i = 0; i < (int)post.size(); i++) {printf("%d", post[i]);if (i < (int)post.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 50;struct Node {int l, r;
} nodes[MAXN];vector<int> pre, in, post;int buildTree(int postL, int postR, int inL, int inR) {if (postL > postR) {return -1;}int root = post[postR];int inIndexOfRoot;for (int i = inL; i <= inR; i++) {if (in[i] == root) {inIndexOfRoot = i;break;}}int leftCount = inIndexOfRoot - inL;nodes[root].l = buildTree(postL, postL + leftCount - 1, inL, inIndexOfRoot - 1);nodes[root].r = buildTree(postL + leftCount, postR - 1, inIndexOfRoot + 1, inR);return root;
}void preOrder(int root) {if (root == -1) {return;}pre.push_back(root);preOrder(nodes[root].l);preOrder(nodes[root].r);
}int main() {int n, x;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &x);post.push_back(x);}for (int i = 0; i < n; i++) {scanf("%d", &x);in.push_back(x);}int root = buildTree(0, n - 1, 0, n - 1);preOrder(root);for (int i = 0; i < (int)pre.size(); i++) {printf("%d", pre[i]);if (i < (int)pre.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <map>
#include <vector>
using namespace std;const int MAXN = 50;struct Node {int l, r;
} nodes[MAXN];vector<int> pre, in, layer;int buildTree(vector<int> layer, int inL, int inR) {if (layer.empty()) {return -1;}int root = layer[0];map<int, bool> isLeft;int inIndexOfRoot;for (int i = inL; i <= inR; i++) {if (in[i] == root) {inIndexOfRoot = i;break;} else {isLeft[in[i]] = true;}}vector<int> leftLayer, rightLayer;for (int i = 1; i < layer.size(); i++) {if (isLeft[layer[i]]) {leftLayer.push_back(layer[i]);} else {rightLayer.push_back(layer[i]);}}nodes[root].l = buildTree(leftLayer, inL, inIndexOfRoot - 1);nodes[root].r = buildTree(rightLayer, inIndexOfRoot + 1, inR);return root;
}void preOrder(int root) {if (root == -1) {return;}pre.push_back(root);preOrder(nodes[root].l);preOrder(nodes[root].r);
}int main() {int n, x;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &x);layer.push_back(x);}for (int i = 0; i < n; i++) {scanf("%d", &x);in.push_back(x);}int root = buildTree(layer, 0, n - 1);preOrder(root);for (int i = 0; i < (int)pre.size(); i++) {printf("%d", pre[i]);if (i < (int)pre.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 50;struct Node {int data;int l, r;
} nodes[MAXN];int treePathSum = 0;void getTreePathSum(int root, int nodePathSum) {if (root == -1) {return;}nodePathSum += nodes[root].data;if (nodes[root].l == -1 && nodes[root].r == -1) {treePathSum += nodePathSum;} else {getTreePathSum(nodes[root].l, nodePathSum);getTreePathSum(nodes[root].r, nodePathSum);}
}int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &nodes[i].data);}for (int i = 0; i < n; i++) {scanf("%d%d", &nodes[i].l, &nodes[i].r);}getTreePathSum(0, 0);printf("%d", treePathSum);return 0;
}

#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 50;struct Node {int data;int l, r;
} nodes[MAXN];int treeWeightedPathLength = 0;void getTreeWeightedPathLength(int root, int nodePathLength) {if (root == -1) {return;}if (nodes[root].l == -1 && nodes[root].r == -1) {treeWeightedPathLength += nodes[root].data * nodePathLength;} else {nodePathLength++;getTreeWeightedPathLength(nodes[root].l, nodePathLength);getTreeWeightedPathLength(nodes[root].r, nodePathLength);}
}int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &nodes[i].data);}for (int i = 0; i < n; i++) {scanf("%d%d", &nodes[i].l, &nodes[i].r);}getTreeWeightedPathLength(0, 0);printf("%d", treeWeightedPathLength);return 0;
}

9.3树的遍历

#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 50;struct Node {vector<int> children;
} nodes[MAXN];vector<int> pre;void preOrder(int root) {pre.push_back(root);for (int i = 0; i < nodes[root].children.size(); i++) {preOrder(nodes[root].children[i]);}
}int main() {int n, k, child;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &k);for (int j = 0; j < k; j++) {scanf("%d", &child);nodes[i].children.push_back(child);}}preOrder(0);for (int i = 0; i < pre.size(); i++) {printf("%d", pre[i]);if (i < (int)pre.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 50;struct Node {vector<int> children;
} nodes[MAXN];vector<int> post;void postOrder(int root) {for (int i = 0; i < nodes[root].children.size(); i++) {postOrder(nodes[root].children[i]);}post.push_back(root);
}int main() {int n, k, child;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &k);for (int j = 0; j < k; j++) {scanf("%d", &child);nodes[i].children.push_back(child);}}postOrder(0);for (int i = 0; i < post.size(); i++) {printf("%d", post[i]);if (i < (int)post.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;const int MAXN = 50;struct Node {vector<int> children;
} nodes[MAXN];vector<int> layer;void layerOrder(int root) {queue<int> q;q.push(root);while (!q.empty()) {int front = q.front();q.pop();layer.push_back(front);for (int i = 0; i < nodes[front].children.size(); i++) {q.push(nodes[front].children[i]);}}
}int main() {int n, k, child;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &k);for (int j = 0; j < k; j++) {scanf("%d", &child);nodes[i].children.push_back(child);}}layerOrder(0);for (int i = 0; i < layer.size(); i++) {printf("%d", layer[i]);if (i < (int)layer.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;const int MAXN = 50;struct Node {int data;vector<int> children;
} nodes[MAXN];int treePathSum = 0;void getTreePathSum(int root, int nodePathSum) {nodePathSum += nodes[root].data;if (nodes[root].children.empty()) {treePathSum += nodePathSum;}for (int i = 0; i < nodes[root].children.size(); i++) {getTreePathSum(nodes[root].children[i], nodePathSum);}
}int main() {int n, k, child;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &nodes[i].data);}for (int i = 0; i < n; i++) {scanf("%d", &k);for (int j = 0; j < k; j++) {scanf("%d", &child);nodes[i].children.push_back(child);}}getTreePathSum(0, 0);printf("%d", treePathSum);return 0;
}

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;const int MAXN = 50;struct Node {int data;vector<int> children;
} nodes[MAXN];int treePathLength = 0;void getTreePathLength(int root, int edgeCount) {if (nodes[root].children.empty()) {treePathLength += nodes[root].data * edgeCount;}for (int i = 0; i < nodes[root].children.size(); i++) {getTreePathLength(nodes[root].children[i], edgeCount + 1);}
}int main() {int n, k, child;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &nodes[i].data);}for (int i = 0; i < n; i++) {scanf("%d", &k);for (int j = 0; j < k; j++) {scanf("%d", &child);nodes[i].children.push_back(child);}}getTreePathLength(0, 0);printf("%d", treePathLength);return 0;
}

9.4二叉查找树(BST)

#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 50;struct Node {int data;int l, r;
} nodes[MAXN];int nodeCount = 0;int newNode(int data) {nodes[nodeCount].data = data;nodes[nodeCount].l = nodes[nodeCount].r = -1;return nodeCount++;
}int insert(int root, int data) {if (root == -1) {return newNode(data);}if (data < nodes[root].data) {nodes[root].l = insert(nodes[root].l, data);} else {nodes[root].r = insert(nodes[root].r, data);}return root;
}vector<int> pre;void preOrder(int root) {if (root == -1) {return;}pre.push_back(nodes[root].data);preOrder(nodes[root].l);preOrder(nodes[root].r);
}int main() {int n, data, root = -1;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &data);root = insert(root, data);}preOrder(root);for (int i = 0; i < (int)pre.size(); i++) {printf("%d", pre[i]);if (i < (int)pre.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <vector>
using namespace std;vector<int> in;bool isBST() {for (int i = 1; i < in.size(); i++) {if (in[i] <= in[i - 1]) {return false;}}return true;
}int main() {int n, x;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &x);in.push_back(x);}printf(isBST() ? "Yes" : "No");return 0;
}

9.5平衡二叉树(AVL树)

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;const int MAXN = 50;struct Node {int data;int height;int l, r;
} nodes[MAXN];int nodeCount = 0;int newNode(int data) {nodes[nodeCount].data = data;nodes[nodeCount].height = 1;nodes[nodeCount].l = nodes[nodeCount].r = -1;return nodeCount++;
}int getHeight(int root) {if (root == -1) {return 0;} else {return nodes[root].height;}
}void updateHeight(int root) {nodes[root].height = max(getHeight(nodes[root].l), getHeight(nodes[root].r)) + 1;
}int getBalanceFactor(int root) {return getHeight(nodes[root].l) - getHeight(nodes[root].r);
}int insert(int root, int data) {if (root == -1) {return newNode(data);}if (data < nodes[root].data) {nodes[root].l = insert(nodes[root].l, data);} else {nodes[root].r = insert(nodes[root].r, data);}updateHeight(root);return root;
}vector<int> balanceFactor;void inOrder(int root) {if (root == -1) {return;}inOrder(nodes[root].l);balanceFactor.push_back(getBalanceFactor(root));inOrder(nodes[root].r);
}int main() {int n, data, root = -1;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &data);root = insert(root, data);}inOrder(root);for (int i = 0; i < (int)balanceFactor.size(); i++) {printf("%d", balanceFactor[i]);if (i < (int)balanceFactor.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;const int MAXN = 50;struct Node {int data;int height;int l, r;
} nodes[MAXN];int nodeCount = 0;int newNode(int data) {nodes[nodeCount].data = data;nodes[nodeCount].height = 1;nodes[nodeCount].l = nodes[nodeCount].r = -1;return nodeCount++;
}int getHeight(int root) {if (root == -1) {return 0;} else {return nodes[root].height;}
}void updateHeight(int root) {nodes[root].height = max(getHeight(nodes[root].l), getHeight(nodes[root].r)) + 1;
}int getBalanceFactor(int root) {return getHeight(nodes[root].l) - getHeight(nodes[root].r);
}int insert(int root, int data) {if (root == -1) {return newNode(data);}if (data < nodes[root].data) {nodes[root].l = insert(nodes[root].l, data);} else {nodes[root].r = insert(nodes[root].r, data);}updateHeight(root);return root;
}bool isAVL(int root) {if (root == -1) {return true;}return isAVL(nodes[root].l) && isAVL(nodes[root].r) && abs(getBalanceFactor(root)) <= 1;
}int main() {int n, data, root = -1;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &data);root = insert(root, data);}printf(isAVL(root) ? "Yes" : "No");return 0;
}

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;const int MAXN = 50;struct Node {int data;int height;int l, r;
} nodes[MAXN];int nodeCount = 0;int newNode(int data) {nodes[nodeCount].data = data;nodes[nodeCount].height = 1;nodes[nodeCount].l = nodes[nodeCount].r = -1;return nodeCount++;
}int getHeight(int root) {if (root == -1) {return 0;} else {return nodes[root].height;}
}void updateHeight(int root) {nodes[root].height = max(getHeight(nodes[root].l), getHeight(nodes[root].r)) + 1;
}int getBalanceFactor(int root) {return getHeight(nodes[root].l) - getHeight(nodes[root].r);
}int L(int root) {int temp = nodes[root].r;nodes[root].r = nodes[temp].l;nodes[temp].l = root;updateHeight(root);updateHeight(temp);return temp;
}int R(int root) {int temp = nodes[root].l;nodes[root].l = nodes[temp].r;nodes[temp].r = root;updateHeight(root);updateHeight(temp);return temp;
}int insert(int root, int data) {if (root == -1) {return newNode(data);}if (data < nodes[root].data) {nodes[root].l = insert(nodes[root].l, data);updateHeight(root);if (getBalanceFactor(root) == 2) {if (getBalanceFactor(nodes[root].l) == 1) {root = R(root);} else if (getBalanceFactor(nodes[root].l) == -1) {nodes[root].l = L(nodes[root].l);root = R(root);}}} else {nodes[root].r = insert(nodes[root].r, data);updateHeight(root);if (getBalanceFactor(root) == -2) {if (getBalanceFactor(nodes[root].r) == -1) {root = L(root);} else if (getBalanceFactor(nodes[root].r) == 1) {nodes[root].r = R(nodes[root].r);root = L(root);}}}return root;
}vector<int> pre;void preOrder(int root) {if (root == -1) {return;}pre.push_back(nodes[root].data);preOrder(nodes[root].l);preOrder(nodes[root].r);
}int main() {int n, data, root = -1;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &data);root = insert(root, data);}preOrder(root);for (int i = 0; i < (int)pre.size(); i++) {printf("%d", pre[i]);if (i < (int)pre.size() - 1) {printf(" ");}}return 0;
}

9.6并查集

#include <cstdio>
#include <cstring>const int MAXN = 100;
int father[MAXN];int findFather(int x) {int xCopy = x;while (father[x] != x) {x = father[x];}int root = x;x = xCopy;while (father[x] != x) {int fatherX = father[x];father[x] = root;x = fatherX;}return root;
}void unionSet(int a, int b) {int faA = findFather(a);int faB = findFather(b);if (faA != faB) {father[faA] = faB;}
}void init(int n) {for (int i = 0; i < n; i++) {father[i] = i;}
}int main() {int n, m, a, b;scanf("%d%d", &n, &m);init(n);for (int i = 0; i < m; i++) {scanf("%d%d", &a, &b);unionSet(a - 1, b - 1);}int classCount = 0;for (int i = 0; i < n; i++) {if (father[i] == i) {classCount++;}}printf("%d", classCount);return 0;
}

#include <cstdio>
#include <cstring>const int MAXN = 100;
int father[MAXN];int findFather(int x) {int xCopy = x;while (father[x] != x) {x = father[x];}int root = x;x = xCopy;while (father[x] != x) {int fatherX = father[x];father[x] = root;x = fatherX;}return root;
}void unionSet(int a, int b) {int faA = findFather(a);int faB = findFather(b);if (faA != faB) {father[faA] = faB;}
}void init(int n) {for (int i = 0; i < n; i++) {father[i] = i;}
}int main() {int n, m, a, b;scanf("%d%d", &n, &m);init(n);for (int i = 0; i < m; i++) {scanf("%d%d", &a, &b);unionSet(a - 1, b - 1);}bool linked = true;for (int i = 1; i < n; i++) {if (findFather(i) != findFather(0)) {linked = false;}}printf(linked ? "Yes" : "No");return 0;
}
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;const int MAXN = 100;
int father[MAXN];
int score[MAXN];vector<int> classes;int findFather(int x) {int xCopy = x;while (father[x] != x) {x = father[x];}int root = x;x = xCopy;while (father[x] != x) {int fatherX = father[x];father[x] = root;x = fatherX;}return root;
}void unionSet(int a, int b) {int faA = findFather(a);int faB = findFather(b);if (faA != faB) {if (score[faA] < score[faB]) {father[faA] = faB;} else {father[faB] = faA;}}
}void init(int n) {for (int i = 0; i < n; i++) {father[i] = i;}
}int main() {int n, m, a, b;scanf("%d%d", &n, &m);init(n);for (int i = 0; i < n; i++) {scanf("%d", &score[i]);}for (int i = 0; i < m; i++) {scanf("%d%d", &a, &b);unionSet(a - 1, b - 1);}for (int i = 0; i < n; i++) {if (findFather(i) == i) {classes.push_back(score[i]);}}sort(classes.rbegin(), classes.rend());printf("%d\n", (int)classes.size());for (int i = 0; i < classes.size(); i++) {printf("%d", classes[i]);if (i < (int)classes.size() - 1) {printf(" ");}}return 0;
}

9.7堆

#include <cstdio>
#include <algorithm>
using namespace std;const int MAXN = 1000 + 1;
int heap[MAXN];void downAdjust(int low, int high) {int i = low, j = i * 2;while (j <= high) {if (j + 1 <= high && heap[j + 1] > heap[j]) {j = j + 1;}if (heap[j] > heap[i]) {swap(heap[j], heap[i]);i = j;j = i * 2;} else {break;}}
}void createHeap(int n) {for (int i = n / 2; i >= 1; i--) {downAdjust(i, n);}
}int main() {int n;scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &heap[i]);}createHeap(n);for (int i = 1; i <= n; i++) {printf("%d", heap[i]);if (i < n) {printf(" ");}}return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;const int MAXN = 1000 + 1;
int heap[MAXN];void downAdjust(int low, int high) {int i = low, j = i * 2;while (j <= high) {if (j + 1 <= high && heap[j + 1] > heap[j]) {j = j + 1;}if (heap[j] > heap[i]) {swap(heap[j], heap[i]);i = j;j = i * 2;} else {break;}}
}void createHeap(int n) {for (int i = n / 2; i >= 1; i--) {downAdjust(i, n);}
}int deleteTop(int n) {if (n > 0) {heap[1] = heap[n--];downAdjust(1, n);}return n;
}int main() {int n;scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &heap[i]);}createHeap(n);n = deleteTop(n);for (int i = 1; i <= n; i++) {printf("%d", heap[i]);if (i < n) {printf(" ");}}return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;const int MAXN = 50 + 1;
int heap[MAXN];void downAdjust(int low, int high) {int i = low, j = i * 2;while (j <= high) {if (j + 1 <= high && heap[j + 1] > heap[j]) {j = j + 1;}if (heap[j] > heap[i]) {swap(heap[j], heap[i]);i = j;j = i * 2;} else {break;}}
}void createHeap(int n) {for (int i = n / 2; i >= 1; i--) {downAdjust(i, n);}
}void heapSort(int n) {createHeap(n);for (int i = n; i > 1; i--) {swap(heap[i], heap[1]);downAdjust(1, i - 1);}
}int main() {int n;scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &heap[i]);}heapSort(n);for (int i = 1; i <= n; i++) {printf("%d", heap[i]);if (i < n) {printf(" ");}}return 0;
}

9.8哈夫曼树

#include <iostream>
#include <vector>
#include <queue>using namespace std;int minCostToMergeFruits(vector<int>& fruits) {// 使用优先队列(最小堆)来处理priority_queue<int, vector<int>, greater<int>> minHeap(fruits.begin(), fruits.end());int totalCost = 0;// 当堆中还有超过一个元素时,进行合并操作while (minHeap.size() > 1) {// 取出最小的两个果堆int first = minHeap.top();minHeap.pop();int second = minHeap.top();minHeap.pop();// 合并这两个果堆int mergedCost = first + second;totalCost += mergedCost;// 将新的合并后的果堆放回堆中minHeap.push(mergedCost);}return totalCost;
}int main() {int n;cin >> n;vector<int> fruits(n);for (int i = 0; i < n; ++i) {cin >> fruits[i];}int result = minCostToMergeFruits(fruits);cout << result << endl;return 0;
}

#include <cstdio>
#include <queue>
using namespace std;priority_queue<int, vector<int>, greater<int> > pq;int main() {int n, weight;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &weight);pq.push(weight);}int ans = 0;while (pq.size() > 1) {int top1 = pq.top();pq.pop();int top2 = pq.top();pq.pop();pq.push(top1 + top2);ans += top1 + top2;}printf("%d", ans);return 0;
}

#include <iostream>
#include <string>
#include <queue>
using namespace std;const int MAXC = 26;
int charCnt[MAXC] = {0};priority_queue<int, vector<int>, greater<int> > pq;int main() {string s;cin >> s;for (int i = 0; i < s.length(); i++) {charCnt[s[i] - 'A']++;}for (int i = 0; i < MAXC; i++) {if (charCnt[i] > 0) {pq.push(charCnt[i]);}}int ans = 0;while (pq.size() > 1) {int top1 = pq.top();pq.pop();int top2 = pq.top();pq.pop();pq.push(top1 + top2);ans += top1 + top2;}printf("%d", ans);return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/375374.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

高精度定位与AI技术的深度融合——未来智慧世界的钥匙

引言在当今迅速发展的科技时代&#xff0c;精确定位和人工智能&#xff08;AI&#xff09;技术正在快速推动各领域的创新与变革。高精度定位结合AI技术所产生的融合效应&#xff0c;正在加速智慧城市、智能驾驶、智能物流以及许多其他领域的实现。这篇文章将详细探讨高精度定位…

科技云报道:产业为根大模型应用为擎,容联云推动企业营销服场景重塑

科技云报道原创。 “没有应用&#xff0c;光有一个基础模型&#xff0c;不管是开源还是闭源&#xff0c;一文不值。”在2024世界人工智能大会&#xff08;WAIC 2024&#xff09;现场&#xff0c;百度创始人、董事长兼首席执行官李彦宏直言。 国产大模型的种类越发丰富&#x…

【爬虫】解析爬取的数据

目录 一、正则表达式1、常用元字符2、量词3、Re模块4、爬取豆瓣电影 二、Xpath1、Xpath解析Ⅰ、节点选择Ⅱ、路径表达式Ⅲ、常用函数 2、爬取豆瓣电影 解析数据&#xff0c;除了前面的BeautifulSoup库&#xff0c;还有正则表达式和Xpath两种方法。 一、正则表达式 正则表达式…

RK3588开发笔记(四):基于定制的RK3588一体主板升级镜像

若该文为原创文章&#xff0c;转载请注明原文出处 本文章博客地址&#xff1a;https://hpzwl.blog.csdn.net/article/details/140288662 长沙红胖子Qt&#xff08;长沙创微智科&#xff09;博文大全&#xff1a;开发技术集合&#xff08;包含Qt实用技术、树莓派、三维、OpenCV…

Java---SpringBoot详解一

人性本善亦本恶&#xff0c; 喜怒哀乐显真情。 寒冬暖夏皆有道&#xff0c; 善恶终归一念间。 善念慈悲天下广&#xff0c; 恶行自缚梦难安。 人心如镜自省照&#xff0c; 善恶分明照乾坤。 目录 一&#xff0c;入门程序 ①&#xff0c;创建springboot工程&#…

Apache配置与应用(优化apache)

Apache配置解析&#xff08;配置优化&#xff09; Apache链接保持 KeepAlive&#xff1a;决定是否打开连接保持功能&#xff0c;后面接 OFF 表示关闭&#xff0c;接 ON 表示打开 KeepAliveTimeout&#xff1a;表示一次连接多次请求之间的最大间隔时间&#xff0c;即两次请求之间…

秋招Java后端开发冲刺——Mybatis使用总结

一、基本知识 1. 介绍 MyBatis 是 Apache 的一个开源项目&#xff0c;它封装了 JDBC&#xff0c;使开发者只需要关注 SQL 语句本身&#xff0c;而不需要再进行繁琐的 JDBC 编码。MyBatis 可以使用简单的 XML 或注解来配置和映射原生类型、接口和 Java POJO&#xff08;Plain …

【网络安全科普】网络安全指南请查收

随着社会信息化深入发展&#xff0c;互联网对人类文明进步奖发挥更大的促进作用。但与此同时&#xff0c;互联网领域的问题也日益凸显。网络犯罪、网络监听、网络攻击等是又发生&#xff0c;网络安全与每个人都息息相关&#xff0c;下面&#xff0c;一起来了解网络安全知识吧。…

开放式耳机哪款性价比高?这五款超值精品不容错过

喜欢进行户外运动的小伙伴们&#xff0c;应该都很需要一款既可以匹配运动场景&#xff0c;又兼顾音质体验的无线蓝牙耳机吧。而开放式耳机拥有佩戴舒适牢固&#xff0c;不堵塞耳部&#xff0c;不影响外部声音传入耳部的优点&#xff0c;完全可以成为运动健身人士户外运动的好伴…

『C + ⒈』‘\‘

&#x1f942;在反斜杠(\)有⒉种最常用的功能如下所示&#x1f44b; #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> int main(void) {int a 10;int b 20;int c 30;if (a 10 &&\b 20 &&\c 30){printf("Your print\n");}else{prin…

Java 多继承与接口

Java 多继承与接口 1、为什么Java不支持多继承&#xff1f;2、使用接口实现多继承2.1 接口的定义与实现 3、接口的优点4、结论 &#x1f496;The Begin&#x1f496;点点关注&#xff0c;收藏不迷路&#x1f496; 多继承是指一个类可以继承多个父类&#xff0c;从而获得多个父类…

Spring Boot Vue 毕设系统讲解 3

目录 项目配置类 项目中配置的相关代码 spring Boot 拦截器相关知识 一、基于URL实现的拦截器&#xff1a; 二、基于注解的拦截器 三、把拦截器添加到配置中&#xff0c;相当于SpringMVC时的配置文件干的事儿&#xff1a; 项目配置类 项目中配置的相关代码 首先定义项目认…

java使用poi-tl模版引擎导出word之if判断条件的使用

文章目录 模版中if语句条件的使用1.数据为False或空集合2.非False或非空集合 模版中if语句条件的使用 如果区块对的值是 null 、false 或者空的集合&#xff0c;位于区块中的所有文档元素将不会显示&#xff0c;这就等同于if语句的条件为 false。语法示例&#xff1a;{{?stat…

Anthropic发布新工具改进大语言模型;商汤科技发布全球首个支持泰文的AI大模型

&#x1f989; AI新闻 &#x1f680; Anthropic发布新工具改进大语言模型 摘要&#xff1a;Anthropic 公司推出多项基于 Claude 3.5 Sonnet 大语言模型的新工具&#xff0c;提升提示词生成和测试能力。新增的“评估”单元帮助开发者自动化生成和微调提示&#xff0c;改进任务…

Kubernetes基于helm部署jenkins

Kubernetes基于helm安装jenkins jenkins支持war包、docker镜像、系统安装包、helm安装等。在Kubernetes上使用Helm安装Jenkins可以简化安装和管理Jenkins的过程。同时借助Kubernetes&#xff0c;jenkins可以实现工作节点的动态调用伸缩&#xff0c;更好的提高资源利用率。通过…

LabVIEW远程实验数据采集系统

随着科学研究的不断发展&#xff0c;实验室对远程数据采集和监控的需求越来越高。传统的数据采集方式往往需要实验人员亲临现场&#xff0c;费时费力&#xff0c;且数据实时性较差。为了解决这些问题&#xff0c;基于LabVIEW开发了一套远程实验数据采集系统&#xff0c;实现对实…

PPTP、L2TP、IPSec、IPS 有什么区别?

随着互联网的发展&#xff0c;保护网络通信的安全越来越重要。PPTP、L2TP、IPSec、IPS是常见的网络安全协议和技术&#xff0c;在保护网络通信安全方面发挥着不同的作用和特点。下面介绍PPTP、L2TP、IPSec、IPS之间的区别。 点对点隧道协议&#xff08;PPTP&#xff09;是一种用…

JVM是如何管理内存的?图文详解GC垃圾回收算法

前言&#xff1a;在C/C中对于变量的内存空间一般都是由程序员手动进行管理的&#xff0c;往往会伴随着大量的 malloc 和 free 操作&#xff0c;常常会有很多问题困扰开发者&#xff0c;这个代码会不会发生内存泄漏&#xff1f;会不会重复释放内存&#xff1f;但是在Java开发中我…

各地户外分散视频监控点位,如何实现远程集中实时监看?

公司业务涉及视频监控项目承包搭建&#xff0c;此前某个项目需求是为某林业公司提供视频监控解决方案&#xff0c;需要实现各地视频摄像头的集中实时监看&#xff0c;以防止国家储备林的盗砍、盗伐行为。 公司原计划采用运营商专线连接各个视频监控点位&#xff0c;实现远程视…

Redis的缓存雪崩,击穿,穿透的介绍

1.缓存雪崩 为保证缓存中的数据与数据库的数据一致,会给Redis里的数据设置一个过期时间,当缓存数据过期后,用户访问的数据如果不在缓存里,业务系统需要重新生成新的缓存,因为就会访问数据库,并将数据更新到Redis里,这样后续请求就可以直接命中缓存. 当大量缓存在同一时间过期或…