# 挑战数据结构与算法面试题——80题全解析（一）

``````BSTreeNode* convert(BSTreeNode *root){
if (NULL == root ||
(NULL == root->m_pLeft && NULL == root->m_pRight)){
return root;
}

convert(root->m_pLeft);
BSTreeNode* p_left = root->m_pLeft;
while(p_left->m_pRight != NULL){
p_left = p_left->m_pRight;
}
root->m_pLeft = p_left;
p_left->m_pRight = root;

convert(root->m_pRight);
BSTreeNode* p_right = root->m_pRight;
while(p_right->m_pLeft != NULL){
p_right = p_right->m_pLeft;
}
root->m_pRight = p_right;
p_right->m_pLeft = root;

BSTreeNode *p = root;
while (NULL != p->m_pLeft){
p = p->m_pLeft;
}
return p;
}``````

``````template <class Type> class min_stack{
private:
stack<Type> s1;
stack<Type> s2;
public:
min_stack(){}
~min_stack(){}

Type min(){
if (!s2.empty()){
return s2.top();
}
}

void push(Type a){
s1.push(a);
if (s2.empty() || a <= s2.top()){
s2.push(a);
}
}

Type pop(){
if (!s1.empty() && !s2.empty()){// 非空
if (s1.top() == s2.top()){
s2.pop();
}
return s1.pop();
}
}
};``````

f(xi)={xif(xi−1)+xi if i=0orf(xi−1)⩽0 if f(xi−1)>0

``````int get_max_subarray(int *a, int length, bool &is_array_ok){
if (NULL == a || length <= 0){
is_array_ok = false;
return 0;
}

int *p_h_a = (int *)malloc(sizeof(int) * length);
// 遍历数组
int max_num = 0;
for (int i = 0; i < length; i++){
if (i == 0 || (i > 0 && p_h_a[i-1] <= 0)){
p_h_a[i] = a[i];
}else{
p_h_a[i] = p_h_a[i-1] + a[i];
}
if (max_num < p_h_a[i]) max_num = p_h_a[i];
}
free(p_h_a);

is_array_ok = true;
return max_num;
}``````

``````void print_vector(vector<BinaryTreeNode *> &v){
vector<BinaryTreeNode *>::iterator it;
for (it = v.begin(); it != v.end(); it ++){
printf("%d\t", (*it)->m_nValue);
}
printf("\n");
}

void pre_order_route(BinaryTreeNode *p, int num, vector<BinaryTreeNode *> &q, int &current){
if (NULL == p) return;

current += p->m_nValue;
q.push_back(p);

bool is_leaf = (NULL == p->m_pLeft) && (NULL == p->m_pRight);

if (current == num && is_leaf){
print_vector(q);
}

if (NULL != p->m_pLeft){
pre_order_route(p->m_pLeft, num, q, current);
}

if (NULL != p->m_pRight){
pre_order_route(p->m_pRight, num, q, current);
}

current -= (*(q.end() - 1))->m_nValue;
q.pop_back();
}

void print_route(BinaryTreeNode *root, int num){
vector<BinaryTreeNode *> q;// 用队列保存已经访问过的节点
int current = 0;
pre_order_route(root, num, q, current);
}``````

``````int swap(int *a, int start, int end, int point_index){
int par_point = a[point_index];
while (start < end){
if (a[start] >= par_point && a[end] <= par_point){
int tmp = a[start];
a[start] = a[end];
a[end] = tmp;
start ++;
end --;
}else if(a[start] < par_point){
start ++;
}else{
end --;
}
}
return start;
}

void get_min_k(int *a, int length, int k){
if (k > length || NULL == a || length <= 0) return;

int new_index = swap(a, 0, length-1, k);
while (true){
if (new_index == k-1) break;
else if (new_index > k-1){
new_index = swap(a, 0, new_index-1, k);
}else{
new_index = swap(a, new_index+1, length-1, k);
}
}
}``````

``````void get_min_k(int *a, int length, int k, set<int> &s){
if (k > length || NULL == a || length <= 0) return;

for (int i = 0; i < length; i++){
if (s.size() < k){
s.insert(a[i]);
}else{
set<int>::iterator it = --s.end();
if (a[i] < *it){
s.erase(*it);
s.insert(a[i]);
}
}
}
}``````

×
• 登录
• 注册

×