笔试算法题(06):最大连续子数组和 & 二叉树路径和值
2024-08-30 05:32:27
出题:预先输入一个整型数组,数组中有正数也有负数;数组中连续一个或者多个整数组成一个子数组,每个子数组有一个和;求所有子数组中和的最大值,要求时间复杂度O(n);
分析:
- 时间复杂度为线性表明只允许一遍扫描,当然如果最终的最大值为0表明所有元素都是负数,可以用线性时间O(N)查找最大的元素。具体算法策略请见代码和注释;
- 子数组的起始元素肯定是非负数,如果添加的元素为正数则记录最大和值并且继续添加;如果添加的元素为负数,则判断新的和是否大于0,如果小于0则以下一个元素作为起始元素重新开始,如果大于0并且比最大和值小则不更新最大和值,并且继续添加元素;
- 当然还有分治的解法,将数组分成A和B两个部分,则子数组最大和有三种可能,来自A,来自B和来自A和B的跨界处,时间复杂度为O(NlogN);
- 如果数组为循环数组,则说明子数组最大和允许出现在array[n-1]和array[0]作为一部分的组合。这样题目分解为两个子题目,一个子题目就是 目标值没有跨过array[n-1]和array[0],其实也就是原来的题目;另一个子题目就是目标值为array[i]到array[n-1]和 array[0]到array[j]的组合,时间复杂度仍旧为O(N);
解题:
/**
* 子数组累加和必定是从非负数的元素开始
* 如果子数组和小于0则缺省最大值为0
* */
int MaxSubArray(int *array, int count) {
int max=;
int curMax=;
for(int i=;i<count;i++) {
curMax+=array[i];
/**
* 跳过负数元素,所以目标子数组必定以非负数元素开始
* */
if(curMax < ) {
curMax=;
continue;
}
/**
* 一旦遇到负数元素,除当前负数元素的其他元素的和作为
* 最大值;由于不能保证之后的元素不会让子数组和变得更大
* ,所以累加继续
* */
if(array[i]<) {
if(max<(curMax-array[i])) {
max=curMax-array[i];
}
} else {
if(max<curMax) {
max=curMax;
}
}
}
return max;
} int MaxDif(int *array, int length) {
/**
* 定义局部stack数组存储相邻元素差值
* 循环获取相邻元素差值
* */
int difarray[length-];
for(int i=;i<length-;i++) {
difarray[i]=array[i]-array[i+];
printf("\n%d",difarray[i]);
}
/**
* sum记录最大和值
* tempsum记录当前元素的和值
* 如果元素为+++++++,则从开始相加到最后
* 如果元素为-------,则sum保持为0
* 如果元素为++++---,则sum保持为前半正数
* 如果元素为----+++,则sum保持为后半正数
* 还有其他满足条件的情况
* */
int tempsum=, sum=;
for(int i=;i<length-;i++) {
tempsum+=difarray[i];
if(tempsum<)
tempsum=;
else if(tempsum>sum)
sum=tempsum;
}
return sum;
} int main() {
int array[]={,-,,,-,-,-};
printf("the max sub array sum: %d",MaxSubArray(array,));
return ;
}
出题:输入一个整数和一颗二元树(节点值为整数),从树的根节点开始往下访问每一个节点,直到叶子节点最终形成一条路径。打印出所有节点和与整数值相等路径;
分析:深度优先搜索,使用Stack结构记录路径;
解题:
/**
* 使用path记录路径
* */
void SpecialDfs(Node *current, MyStack *path, int sum, int target) {
path->push(current->value);
sum+=current->value;
bool isLeaf=true; if(current->left != NULL) {
SpecialDfs(current->left, path, sum, target);
isLeaf=false;
} if(current->right != NULL) {
SpecialDfs(current->right, path, sum, target);
isLeaf=false;
} if(isLeaf && sum == target) {
path->showStack();
}
path->pop(NULL);
}
最新文章
- ES6环境搭建及react-router学习
- C#使用HttpWebRequest 进行请求,提示 基础连接已经关闭: 发送时发生错误。
- Pyhton 利用threading远程下发文件和远程执行linux系统命令
- AlertDialog错误
- 自定义底部工具栏及顶部工具栏和Fragment配合使用demo
- Python程序的常见错误(收集篇)
- HDU 5869 Different GCD Subarray Query 离线+树状数组
- RouteOS软路由HotSpot热点认证网关添加白名单和黑名单
- Weka链接Mysql数据库
- 【转】在Tomcat配置JNDI数据源的三种方式
- 程序员带你学习安卓开发,十天快速入-对比C#学习java语法
- JavaSE思维导图(七)
- CSS 之 光进入光
- MySQL 5.7 安装完成后,立即要调整的性能选项
- CentOS 6.5 搭建 Zabbix
- 我的jquery validate 笔记
- Innodb与Myisam引擎的区别与应用场景
- Lecture4_1&;4_2.多维随机变量及其概率分布
- 20165223 week4测试补交与总结
- 搭建Elasticsearch平台
热门文章
- webpack 4.0 相关
- Gym 100531G Grave(水题)
- How to Compare Means (均值比较)
- -Dmaven.multiModuleProjectDirectory system property is not set. Check $M2_HOME environment variable and mvn script match问题处理
- Web自动化测试框架-PO模式
- 【LeetCode 33】Search in Rotated Sorted Array
- Android 中保存数据到文件中
- 掌握Spark机器学习库-05-spark中矩阵与向量的使用
- linux下php访问sql server设置
- SceneAction$$FastClassByCGLIB$$7330f7b9.invoke(int, Object, Object[]) line: not available