某文本编辑器把用户输入的字符依次压入栈 S。用户依次输入 A , B , C , D 后,用户按了两次撤销(每次撤销,弹出栈顶一个字符)。此时栈从栈底到栈顶的内容是:( )。
A. A B
B. A B C
C. A B D
D. B C
假设循环队列数组长度为 N ,其中队空判断条件为:front == rear,队满判断条件为:(rear + 1) %N == front,出队对应的操作为:front = (front + 1) % N,入队对于的操作为:rear = (rear + 1) %N。循环队列长度 N = 6,初始 front = 1, rear = 1,执行操作序列为:入队,入队,入队,出队,入队,入队,则最终 (front, rear) 的值是( )。
A. (2, 5)
B. (2, 0)
C. (3, 5)
D. (3, 0)
struct Symbol {
char ch;
long long freq;
string code;
};
struct Node {
long long w;
int l, r;
int sym;
Node(long long _w = 0, int _l = -1, int _r = -1, int _sym = -1)
: w(_w), l(_l), r(_r), sym(_sym) {}
};
static int PopMinNode(const vector<Node> &nodes,
const vector<int> &leafIdx, int n, int &pA,
const vector<int> &internalIdx, int &pB) {
if (pA < n && (pB >= (int)internalIdx.size() ||
nodes[leafIdx[pA]].w <= nodes[internalIdx[pB]].w)) {
return(leafIdx[pA++]);
} else {
return(internalIdx[pB++]);
}
}
static void DFSBuildCodes(int u, const vector<Node> &nodes, Symbol sym[], string &path) {
if (u == -1) return;
if (nodes[u].sym != -1)
{
sym[nodes[u].sym].code = path;
return;
}
path.push_back('0');
DFSBuildCodes(nodes[u].l, nodes, sym, path);
path.pop_back();
path.push_back('1');
DFSBuildCodes(nodes[u].r, nodes, sym, path);
path.pop_back();
}
int BuildHuffmanCodes(Symbol sym[], int n) {
for (int i = 0; i < n; i++)
sym[i].code.clear();
if (n <= 0) return(-1);
if (n == 1) {
sym[0].code = "0";
return(0);
}
vector<Node> nodes;
nodes.reserve(2 * n);
vector<int> leafIdx(n);
for (int i = 0; i < n; i++) {
leafIdx[i] = (int)nodes.size();
nodes.push_back(Node(sym[i].freq, -1, -1, i));
}
sort(leafIdx.begin(), leafIdx.end(),
[&](int a, int b) {
if (nodes[a].w != nodes[b].w)
return(nodes[a].w < nodes[b].w);
return(nodes[a].sym < nodes[b].sym);
});
vector<int> internalIdx;
internalIdx.reserve(n);
int pA = 0, pB = 0;
for (int k = 1; k < n; k++) {
int x = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);
int y = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);
int z = (int)nodes.size();
________________________
}
int root = internalIdx.back();
string path;
DFSBuildCodes(root, nodes, sym, path);
return(root);
}
A. nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, -1));
internalIdx.push_back(z);
B. nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, -1));
leafIdx.push_back(z);
C. internalIdx.push_back(z);
nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, x+y));
D. nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, x+y));
leafIdx.push_back(z);
TreeNode* op(TreeNode* root, int x) {
if (!root) return(new TreeNode(x));
if (x < root->val)
root->left = op(root->left, x);
else
root->right = op(root->right, x);
return(root);
}