共计 3643 个字符，预计需要花费 10 分钟才能阅读完成。
在一个二维数组中，每一行都按照从左到右的顺序排序，每一列都按照从上到下的顺序排序。请实现一个函数用于判断数组中是否包含指定的数。
函数原型：bool find_in_matrix(int matrix[N][M], int value);
说明：查找成功时返回 true, 返回失败时返回 false.
template<typename T, int N, int M>
bool find_in_matrix(T matrix[N][M], T value) // O(N + M)
{
if((matrix[0][0] <= value) && (value <= matrix[N-1][M-1]) )
{
int r = 0;
int c = M – 1;
while((r < N) && (c >= 0) )
{
if(value == matrix[r] )
{
return true;
}
else if(value < matrix[r] )
{
c–;
}
else
{
r++;
}
}
}
return false;
}
写一个函数，打印二叉树中某层的所有节点
二叉树节点定义:
struct Node
{
int v;
Node* left;
Node* right;
};
函数原型：void print_node_at_level(Node* node, int level);
说明：将 level 层的节点所保存的值打印在同一行
void print_node_at_level(Node* node, int level)
{
if(node != NULL)
{
if(level == 0)
{
cout<<node->v<<” “;
}
else
{
print_node_at_level(node->left, level-1);
print_node_at_level(node->right, level-1);
}
}
}
void print_node_at_level_ex(Node* node, int level)
{
if(node != NULL)
{
list<Node*> nl;
list<int> ll;
nl.push_back(node);
ll.push_back(0);
while(nl.size() > 0 )
{
Node* n = nl.front();
int cl = ll.front();
nl.pop_front();
ll.pop_front();
if(cl == level)
{
cout<<n->v<<” “;
}
else if(cl < level)
{
if(n->left != NULL)
{
nl.push_back(n->left);
ll.push_back(cl+1);
}
if(n->right != NULL)
{
nl.push_back(n->right);
ll.push_back(cl+1);
}
}
}
}
}
编写一个函数用于删除二叉树中的度数为 1 的所有节点
要求：节点删除后其唯一的子节点代替它的位置
struct Node
{
int v;
Node* left;
Node* right;
};
void print_div(int p)
{
for(int i=0; i<p; i++)
{
cout<<“-“;
}
}
void print_tree(Node* node, int p)
{
if(node != NULL)
{
print_div(p);
cout<<node->v<<endl;
if((node->left != NULL) || (node->right != NULL) )
{
print_tree(node->left, p+1);
print_tree(node->right, p+1);
}
}
else
{
print_div(p);
cout<<endl;
}
}
void print_tree(Node* node)
{
print_tree(node, 0);
}
void delete_one_degree_node(Node*& node)
{
if(node != NULL)
{
if((node->left != NULL) && (node->right != NULL) )
{
delete_one_degree_node(node->left);
delete_one_degree_node(node->right);
}
else if((node->left != NULL) && (node->right == NULL) )
{
node = node->left;
delete_one_degree_node(node);
}
else if((node->left == NULL) && (node->right != NULL) )
{
node = node->right;
delete_one_degree_node(node);
}
}
}
输入一个数组，数组里面可能有正数也有负数。数组中一个或连续的多个元素组成一个子数组。求所有子数组的和的最大值。
要求：
时间复杂度为 O(n)
template<typename T>
bool max_sub_array_sum(T array[], int len, T& max_sum)
{
int ret = (len > 0) && (array != NULL);
if(ret)
{
T sum = array[0];
T cur = array[0];
for(int i=1; i<len; i++)
{
cur = cur + array[i];
if(cur < array[i] )
{
cur = array[i];
}
if(cur > sum)
{
sum = cur;
}
}
max_sum = sum;
}
return ret;
}
在一个整型数组中只可能有 0，1，2 三种数字重复出现，编写一个函数对这样的数组进行排序。
void swap(int& a, int& b)
{
int c = a;
a = b;
b = c;
}
void three_element_sort(int array[], int len)
{
int* ts = new int[len];
int p = 0;
if(ts != NULL)
{
for(int i=0; i<3; i++)
{
for(int j=0; j<len; j++)
{
if(array[j] == i )
{
ts[p++] = i;
}
}
}
for(int i=0; i<len; i++)
{
array[i] = ts[i];
}
delete[]ts;
}
}
void three_element_sort_ex(int array[], int len)
{
int p0 = 0;
int p2 = len – 1;
while(array[p0] == 0 ) p0++;
while(array[p2] == 2 ) p2–;
for(int i=p0; i<=p2;)
{
if(array[i] == 0 )
{
swap(array[i], array[p0++]);
while(array[p0] == 0 ) p0++;
if(i < p0) i = p0;
}
else if(array[i] == 2 )
{
swap(array[i], array[p2–]);
while(array[p2] == 2 ) p2–;
}
else
{
i++;
}
}
}
求 1 + 2 + 3 + … + n 的和
要求：
不能使用 if, while, for, switch, ?: 等条件语句，不能使用 ==,！=, <=, >, <= 等比较运算符，也不能调用外部库函数。
只能使用加减法操作操作符，不能使用乘除法操作符
class Sum
{
private:
static int N;
static int S;
Sum();
public:
static int Calculate(int n);
};
int Sum::N = 0;
int Sum::S = 0;
Sum::Sum()
{
S = S + N;
N = N – 1;
}
int Sum::Calculate(int n)
{
int ret = 0;
Sum* p = NULL;
N = n;
S = 0;
p = new Sum[N];
ret = S;
delete[]p;
return ret;
}
int main()
{
cout<<Sum::Calculate(10)<<endl;
cout<<Sum::Calculate(100)<<endl;
return 0;
}
typedef int(Func)(int);
int end_func(int n);
int recusive_func(int n);
Func* Array[] =
{
end_func, // 0
recusive_func // 1
};
int end_func(int n)
{
return n;
}
int recusive_func(int n)
{
return n + Array[!!(n-1)](n-1);
}
int sum(int n)
{
return recusive_func(n);
}
int main()
{
cout<<sum(10)<<endl;
cout<<sum(100)<<endl;
return 0;
}
template<int N>
class Sum
{
public:
static const int Value = N + Sum<N-1>::Value;
};
template<>
class Sum<0>
{
public:
static const int Value = 0;
};
int main()
{
cout<<Sum<10>::Value<<endl;
cout<<Sum<100>::Value<<endl;
return 0;
}
