中级提升班-6题目一 字符串目录
修改前缀树、有序表、递归版本深度优先遍历
给你一个字符串类型的数组arr，譬如：
String[] arr = { “b\cst”, “d\”, “a\d\e”, “a\b\c” };
你把这些路径中蕴含的目录结构给画出来，子目录直接列在父目录下面，并比父目录
向右进两格，就像这样:
a
b
c
d
e
b
cst
d
同一级的需要按字母顺序排列，不能乱。
在施秉等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供成都做网站、成都网站设计、成都外贸网站建设 网站设计制作按需定制,公司网站建设,企业网站建设,成都品牌网站建设,网络营销推广,外贸营销网站建设,施秉网站建设费用合理。
- 建立Node节点，其string类型表示上一个横杠的值（为了方便打印），有序表表示该节点后续对应节点及其值
class Node {public:
string name;
mapmp;
Node(string name) {this->name = name;
}
};
vectorsplitStr(string str);
void printTree(Node* head, int level);
void getFolderTree(vectorarr) {Node* head = new Node("root");// 头节点
// 建树
for (string str : arr) {vectorres = splitStr(str);
Node* cur = head; // 不断回到头节点寻找
for (string s : res) {if (!cur->mp.count(s)) {// 当前节点没有s记录，则新建
cur->mp.insert({s, new Node(s) });
}
cur = cur->mp[s];// 有的话直接移到该节点，没有在新建后也移到该节点
}
}
// 深度优先遍历
printTree(head, 0);
}
void printTree(Node* head, int level) {if (level != 0) {for (int i = 1; i< level; i++) {cout<< " ";
}
cout<< head->name<< endl;
}
for (paircur : head->mp) {printTree(cur.second, level + 1);
}
}
vectorsplitStr(string str) {vectorres;
string cur = "";
for (char c : str) {if (c == '/') {res.push_back(cur);
cur = "";
}
else {cur += c;
}
}
res.push_back(cur);
return res;
}
题目二 BST和双链表转换
双向链表节点结构和二叉树节点结构是一样的，如果你把last认为是left，
next认为是next的话。
给定一个搜索二叉树的头节点head，请转化成一条有序的双向链表，并返回链
表的头节点。
自己尝试了下，利用辅助数组，记录节点，再把数组中的节点串起来,空间复杂度O(N)，过大，适合笔试做法
class TreeNode {public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int val) {this->val = val;
this->left = nullptr;
this->right = nullptr;
}
};
void process1(TreeNode* head, vector& res) {if (head == nullptr) {return;
}
process1(head->left, res);
res.push_back(head);
process1(head->right, res);
}
TreeNode* BSTtoDoubleListNode(TreeNode* head) {if (head == nullptr) {return nullptr;
}
vectorres;
process1(head, res);
TreeNode* pre = nullptr;
for (int i = 0; i< res.size() - 2; i++) {res[i]->left = pre;
res[i]->right = res[i + 1];
pre = res[i];
}
res[res.size() - 1]->right = nullptr;
return res[0];
}
法2：利用递归套路
- 第i个节点，要求左边返回头和尾，右边返回头和尾，再将左边的为、该节点、右边的头相连，再返回给上级
// 法2递归套路
struct ReturnType {TreeNode* start;
TreeNode* end;
ReturnType(TreeNode* start, TreeNode* end) {this->start = start;
this->end = end;
}
};
ReturnType process2(TreeNode* head) {if (head == nullptr) {return ReturnType(nullptr, nullptr);
}
ReturnType left = process2(head->left);
ReturnType right = process2(head->right);
if (left.end != nullptr) {left.end->right = head;
}
head->left = left.end;
head->right = right.start;
if (right.start != nullptr) {right.start->left = head;
}
return ReturnType(left.start != nullptr ? left.start : head, right.end != nullptr ? right.end : head);
}
TreeNode* BSTtoDoubleListNode2(TreeNode* head) {if (head == nullptr) {return nullptr;
}
return process2(head).start;
}
题目三 大BST节点个数
树形dp套路
找到一棵二叉树中，大的搜索二叉子树，返回大搜索二叉子树的节点个数。
class TreeNode {public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int val) {this->val = val;
this->left = nullptr;
this->right = nullptr;
}
};
struct ReturnType {int max;
int min;
int maxBSTSize;// 该树中大BST的个数
TreeNode* maxBSTHead;// 该树中大BST的头节点
ReturnType(int ma, int mi, int n, TreeNode* is) {this->max = ma;
this->min = mi;
this->maxBSTSize = n;
this->maxBSTHead = is;
}
};
ReturnType process(TreeNode* head) {if (head == nullptr) {return ReturnType(INT32_MIN, INT32_MAX, 0, nullptr);// 为了满足任何情况都为BST
}
ReturnType leftData = process(head->left);
ReturnType rightData = process(head->right);
int mi = min(head->val, min(leftData.min, rightData.min));
int ma = max(head->val, max(leftData.max, rightData.max));
// 如果只考虑与head节点无关，则maxBSTSize为左或者右的大值
int maxBSTSize = max(leftData.maxBSTSize, rightData.maxBSTSize);
// 如果只考虑与head节点无关，则maxBSTHead为大size的BST的头节点
TreeNode* maxBSTHead = maxBSTSize == leftData.maxBSTSize ? leftData.maxBSTHead : rightData.maxBSTHead;
// 接下来考虑情况三，即大BST与head节点有关
if (leftData.maxBSTHead == head->left && rightData.maxBSTHead == head->right) {if (leftData.max< head->val && rightData.min >head->val) {maxBSTSize = leftData.maxBSTSize + rightData.maxBSTSize + 1;
maxBSTHead = head;
}
}
return ReturnType(ma, mi, maxBSTSize, maxBSTHead);
}
TreeNode* getMaxBST(TreeNode* head) {return process(head).maxBSTHead;
}
题目四 给出先序中序遍历，求后序遍历
递归
已知一棵二叉树中没有重复节点，并且给定了这棵树的中序遍历数组和先序遍历
数组，返回后序遍历数组。
比如给定：
int[] pre = { 1, 2, 4, 5, 3, 6, 7 };
int[] in = { 4, 2, 5, 1, 6, 3, 7 };
返回：
{4,5,2,6,7,3,1}
- pre中第一个代表该树的最中间节点，放入pos中最后的位置
- 在in中找到a的位置，其作边为左树部分，右边为右树部分，根据其个数在pre和pos数组中划分搜索位置
- 不断如此递归，直到只剩单个时候填入即可
void process(vector& pre, vector& in, vector& pos, int prei, int prej, int ini, int inj, int posi, int posj, unordered_mapinmap) {if (posi >posj) {return;
}
if (posi == posj) {pos[posi] = pre[prei];
return;
}
pos[posj] = pre[prei];
int find = inmap[pre[prei]];
process(pre, in, pos, prei + 1, prei + find - ini, ini, find - 1, posi, posi + find - ini - 1, inmap);
process(pre, in, pos, prei + find - ini + 1, prej, find + 1, inj, posi + find - ini, posj - 1, inmap);
}
void preInPos(vectorpre, vectorin) {int size = pre.size() - 1;
vectorpos(pre.size());
unordered_mapinmap;
for (int i = 0; i< in.size(); i++) {inmap.insert({in[i], i });
}
process(pre, in, pos, 0, size, 0, size, 0, size, inmap);
for (int i = 0; i<= size; i++) {cout<< pos[i]<< " ";
}
}
题目五 路灯
贪心、动态规划
小Q正在给一条长度为n的道路设计路灯安置方案。
为了让问题更简单,小Q把道路视为n个方格,需要照亮的地方用’.‘表示, 不需要
照亮的障碍物格子用’X’表示。小Q现在要在道路上设置一些路灯, 对于安置在
pos位置的路灯, 这盏路灯可以照亮pos - 1, pos, pos + 1这三个位置。
小Q希望能安置尽量少的路灯照亮所有’.‘区域, 希望你能帮他计算一下最少需
要多少盏路灯。
输入描述：
输入的第一行包含一个正整数t(1<= t<= 1000), 表示测试用例数
接下来每两行一个测试数据, 第一行一个正整数n(1<= n<= 1000),表示道路
的长度。第二行一个字符串s表示道路的构造,只包含’.‘和’X’。
输出描述：
对于每个测试用例, 输出一个正整数表示最少需要多少盏路灯。
贪心策略：
- 最重要需要保证前面是否放路灯不会影响当前pos位置
- 若pos位置为X，则不放灯
- 若pos位置为‘.‘，下一个位置为X时，则一定要放，index跳到X后面一个；若下一个位置为‘.’，则当前pos不放，在下一个位置放，index + 3，到照明区域外
int light(string str) {if (str.length()< 1) {return 0;
}
int index = 0;
int light = 0;
while (index< str.length()) {if (str[index] == 'X') {index++;
}
else {// str[index] == '.'
light++;
if (index + 1 == str.length()) {break;
}
else {if (str[index + 1] == 'X') {index = index + 2;
}
else {index = index + 3;
}
}
}
}
return light;
}
题目六帖子打分(子数组)
子数组大累加和
为了保证招聘信息的质量问题，公司为每个职位设计了打分系统，打分可以为正数，也
可以为负数，正数表示用户认可帖子质量，负数表示用户不认可帖子质量．打分的分数
根据评价用户的等级大小不定，比如可以为 -1分，10分，30分，-10分等。假设数组A
记录了一条帖子所有打分记录，现在需要找出帖子曾经得到过最高的分数是多少，用于
后续根据最高分数来确认需要对发帖用户做相应的惩罚或奖励．其中，最高分的定义为：
用户所有打分记录中，连续打分数据之和的大值即认为是帖子曾经获得的最高分。例
如：帖子10001010近期的打
分记录为[1,1,-1,-10,11,4,-6,9,20,-10,-2],那么该条帖子曾经到达过的最高分数为
11+4+(-6)+9+20=38。请实现一段代码，输入为帖子近期的打分记录，输出为当前帖子
得到的最高分数。
方法一：利用遍历方法，时间复杂度O(N2)
方法二：
- 初始化变量cur = 0，max = 系统最小。
- 遍历数组，cur = cur + arr[i]，如果cur大于max则更新；若cur小于0，则让cur = 0，max不更新
证明：
- 若数组中均为负数，则cur不断取值不断被重置为0，max最终为负数中的大值
- 若数组中无正数，则当遇到cur小于0，被重置为0，max为0
- 当数组中有负有正，该方法能找到数组中累加和大且最长的一段子数组(i…j)。该子数组有两个性质，1）从i到j间任何位置的累加和必定>=0，若小于0，则舍弃则可以得到更大的；2）从任何一个位置开始到i-1，其累加和必定<0，若大于等于0，则加上该段才为大最长子数组，不符合。因此，遍历到i-1位置时，cur需要重置为0，再进行累加操作，且根据性质可以得到正确。
void SubArrayMaxSum1(vectorarr) {int ma = INT32_MIN;
int cur = 0;
for (int i = 0; i< arr.size(); i++) {cur = arr[i];
for (int j = i + 1; j< arr.size(); j++) {cur += arr[j];
ma = max(cur, ma);
}
}
cout<< ma<< endl;
}
void SubArrayMaxSum2(vectorarr) {int ma = INT32_MIN;
int cur = 0;
for (int i = 0; i< arr.size(); i++) {cur += arr[i];
ma = max(ma, cur);
cur = cur< 0 ? 0 : cur;
}
cout<< ma<< endl;
}
题目七 子矩阵
子矩阵大累加和、压缩数组
给定一个整型矩阵，返回子矩阵的大累计和。
流程：
- 设有3行矩阵，分别计算仅包含0行，01行，012行，1行，12行，2行的矩阵的大子数组累加和
- 计算第0行，相当于题目六中求子数组大累加和
- 计算第01行，需要将01行上下相加合并，后续计算与题目六子数组大累加和相同
void Problem07_SubMatrixMaxSum(vector>arr) {int cur = 0;
int ma = INT32_MIN;
for (int i = 0; i< arr.size(); i++) {vectorres(arr[0].size());
for (int j = i; j< arr.size(); j++) {cur = 0;
for (int k = 0; k< res.size(); k++) {res[k] += arr[j][k];
cur += res[k];
ma = max(ma, cur);
cur = cur< 0 ? 0 : cur;
}
}
}
cout<< ma<< endl;
}
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
当前文章：左神算法与数据结构——中级提升班-6-创新互联
本文URL：
http://cdkjz.cn/article/joccd.html
