进阶算法03
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了进阶算法03，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3896字，纯文字阅读大概需要6分钟。
内容图文
给定一个数组，数组中有0，正数，负数，找到一个累加和为目标值的最长子数组，返回最长子数组的长度。
int maxLength(int *arr, int len, int target)
{
if (!arr || len == 0)
return 0;
int sum = 0;
int ret = 0;
map<int, int> m; //first:子数组arr[0...second]的和，second：末尾下标
m.insert(make_pair(0, -1));
for (int i = 0; i < len; i++)
{
sum += arr[i];
auto it = m.find(sum - target);
if (it != m.end())
ret = max(i - it->second, ret);
if (m.find(sum) == m.end())
m.insert(make_pair(sum, i));
}
return ret;
}
扩展：给定一个数组，数组中有奇数和偶数，找到一个最长子数组，其中包含的奇数和偶数个数相等，返回最长子数组的长度。
思路：奇数==-1，偶数==1，找到一个累加和为0的最长子数组
求一个二叉树中最大搜索二叉树的头部（1.是一棵搜索二叉树 2.包含节点最多）
三种情况：
1.这棵最大搜索二叉树在当前节点的左边
2.这棵最大搜索二叉树在当前节点的右边
3.以当前节点为头节点就是最大搜索二叉树
要搜集的信息：
1.左子树的最大搜索二叉树的大小
2.右子树的最大搜索二叉树的大小
3.左子树的最大搜索二叉树的头部
4.右子树的最大搜索二叉树的头部
5.左子树的最大二叉搜索树的最大值
6.右子树的最大二叉搜索树的最小值
化简后;
1.最大搜索二叉树的大小
2.最大搜索二叉树的头部
3.最大搜索二叉树的最大值
4.最大搜索二叉树的最小值
class Node
{
public:
int val;
Node *left;
Node *right;
Node(int data)
{
val = data;
left = NULL;
right = NULL;
}
};
class returnType
{
public:
int size;
Node *head;
int maxVal;
int minVal;
returnType(int a, Node *b, int c, int d)
{
size = a;
head = b;
maxVal = c;
minVal = d;
}
};
returnType process(Node *head)
{
if (!head)
return returnType(0, NULL, INT_MIN, INT_MAX);
returnType leftRetType = process(head->left);
returnType rightRetType = process(head->right);
int p1 = leftRetType.size;
int p2 = rightRetType.size;
int p3 = 0;
if (head->left == leftRetType.head &&
head->right == rightRetType.head &&
head->val > leftRetType.maxVal &&
head->val < rightRetType.minVal)
{
p3 = leftRetType.size + rightRetType.size + 1;
}
int size = max(max(p1, p2), p3);
Node *node = (leftRetType.size == size) ? leftRetType.head : rightRetType.head;
if (size == p3)
node = head;
int maxVal = max(max(leftRetType.maxVal, rightRetType.maxVal), head->val);
int minVal = min(min(leftRetType.minVal, rightRetType.minVal), head->val);
return returnType(size, node, maxVal, minVal);
}
Node *biggestSubBST(Node *head)
{
return process(head).head;
}
求一棵二叉树的最远距离（任意两个节点的距离，求最大）
三种情况：
1.最远距离产生自当前节点的左边
2.最远距离产生自当前节点的右边
3.最远距离包含当前节点
要搜集的信息：
1.最远距离的大小
2.深度
class Node
{
public:
int val;
Node *left;
Node *right;
Node(int data)
{
val = data;
left = NULL;
right = NULL;
}
};
class returnType
{
public:
int maxDis;
int height;
returnType(int a, int b)
{
maxDis = a;
height = b;
}
};
returnType process(Node *head)
{
if (!head)
return returnType(0, 0);
returnType leftRetType = process(head->left);
returnType rightRetType = process(head->right);
int p1 = leftRetType.maxDis;
int p2 = rightRetType.maxDis;
int p3 = leftRetType.height + rightRetType.height + 1;
int size = max(max(p1, p2), p3);
int height = max(leftRetType.height, rightRetType.height) + 1;
return returnType(size, height);
}
int maxDistance(Node *head)
{
return process(head).maxDis;
}
两种情况：
1.当前节点来
2.当前节点不来
要搜集的信息：
1.当前节点来的最大活跃度
2.当前节点不来的最大活跃度
//改写形式
class Node
{
public:
int activity;
vector<Node*> nexts;
Node(int data)
{
activity = data;
}
};
class returnType
{
public:
int comeActivity;
int notcomeActivity;
returnType(int a, int b)
{
comeActivity = a;
notcomeActivity = b;
}
};
returnType process(Node *head)
{
if (!head)
return returnType(0, 0);
int comeActivity = 0;
int notcomeActivity = 0;
for (int i = 0; i < head->nexts.size(); i++)
{
Node *node = head->nexts[i];
returnType ret = process(node);
comeActivity += ret.notcomeActivity;
notcomeActivity += max(ret.comeActivity, ret.notcomeActivity);
}
return returnType(comeActivity, notcomeActivity);
}
int maxActivity(Node *head)
{
returnType ret = process(head);
return max(ret.comeActivity, ret.notcomeActivity);
}
内容总结
以上是互联网集市为您收集整理的进阶算法03全部内容，希望文章能够帮你解决进阶算法03所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】