时间: 2018-07-07 文章来源: 洋蜜蜂
在CS编程中，我们总是会与数学技巧、算法打交道，这个也是为什么CS专业一直在强调数学基础的重要性，学好CS前提也是数学扎实基础的延伸。今天洋蜜蜂的CS Tutor帮同学们列举出CS编程分析辅导中一些数学技巧与算法的运用，希望能够帮到大家理解。
①如何查找n-1个元素的产品
给定n个元素的数组，对于每个元素，找到“除相应元素之外的所有元素的乘积”的值。
例如，如果数组是 - 1 2 4 3 输出是： - 2x4x3 1x4x3 1x2x3 1x2x4 您不能使用模数运算符。
注意： - O（N ^ 2）是一个明显的逻辑。想想在O（N）中做到这一点。
所以我们可以打
void mult（int a []，int b []）
{
int i，mult_value = 1;
for（i = 0; i <MAX; i ++）
mult_value * = a [i];
for（i = 0; i <MAX; i ++）
b [i] = mult_value / a [i];
}
//时间复杂度因为它是O（n）+ O（n）= O（n）
②如何找出二叉树中的最大完整级别
给定二叉树，找到树完全填充的最大级别。
完全填充意味着当前级别的每个节点的父节点必须同时具有左子节点和右子节点。
编写一个迭代代码。（使用Queue的Level Order Traversal除外）。
下面是这个的递归代码： -
int TreeCompleteLevel（Tree * root）
{
if（！（root）||！（root-> left）||！（root-> right））
return 0;
int l = TreeCompleteLevel（root-> left）;
int r = TreeCompleteLevel（root-> right）;
返回1 + min（l，r）;
}
③如何结合两个字符串
如题，给出三个字符串s1，s2，s3。
检查s3是否可以通过s1和s2的交错形成。
对于ex s1 =“abc”s2 =“def”
s3 = adbcef返回true
而s3 =“aedbcf”返回false
下面是代码：
#include
//定义三个字符数组
#define true 1
#define false 0
int check（）
{
int i，j，k;
I = J = K = 0;
if（strlen（s1）+ strlen（s2）！= strlen（s3））
return false;
else
{
while（s3 [i]！='\ 0'）
{
if（i％2 == 0）
{
if（s3 [i]！= s1 [j ++]）
return false;
}
else
{
if（s3 [i]！= s2 [k ++]）
return false;
}
i ++;
}
}
返回true;
}
④阵数问题
线性时间和常数空间算法：
使用常量大小为2的交换空间。
现在可以看出，第一个和最后一个元素处于正确的位置。只需要更改中间的元素。
观察： - 阵列中的元素数量总是均匀的。
1-起始点到起点和终点的第二个最后一个元素。
2-在每个循环开始时，pair（swap [0]，swap [1]）包含分别位于pair（end，start）位置的元素。
3-迭代循环（start <= end）
这个问题也是面试时可能会提问到的，CS tutor提示大家多熟悉这类算法运用，有CS算法不太懂的同学可以找留学府辅导的。
代码展示：
void func(int arr[], int n)
{
assert(n>0);
if(n<=2) return;
int swap[2]={0};
int start=1,end=n-2; // 基于0的数组
swap[0]=arr[n/2];
swap[1]=arr[n/2+1];
while(start<=end)
{
swap(arr[start],swap[1]);
start++;
swap(arr[end],swap[0]);
end--;
}
}
⑤二叉树的直径
二叉树的直径定义为树的两个叶子之间的最长路径。
路径不必穿过树的根。它可以位于任何子树中，也可以通过root。
优化算法 -
使用自下而上编程获得线性时间解决方案。
基础案例 - 叶节点的高度为零。
辅助函数返回子树的直径，该子树作为参数传递并将其高度存储在传递的参数中。
现在树的直径是通过根的直径，左子树的直径和右子树的直径的最大值。
代码展示：
int DiameterOpt(Tree *root)
{
if(!root) return 0;
if(isleaf(root) ) return 1;
int height=0;
return helper(root,&height);
}
int helper(Tree *root,int *height)
{
if(!root){
*height=0;
return 0;
}
int ld=0,rd=0,lh=0,rh=0;
ld=helper(root->left, &lh);
rd=helper(root->right,&rh);
*height=1+ max(lh,rh);
return max( lh+rh+1, max( ld,rd ) );
}
介绍到这里相信同学们对于这几个算法运用也多了一份了解，学好CS课程后会跟更多的算法打交道，算法从根本上也是简化了我们的操作运算，留学府提醒，CS学不太好的同学可以找我们辅导。
洋蜜蜂辅导机构争当海外留学的引导者，创新式辅导模式与海外名校师资，旨在为学生学有所成，提供各方位的服务，包括课程辅导，选课咨询，写作辅导等服务。
更多课程资讯，详情可点开洋蜜蜂官网即可获得更多，如果有CS课程辅导需求，可以咨询24小时在线客服微信：yuff996，洋蜜蜂助你度过学习难关。
