189 8069 5689

左神算法与数据结构——中级提升班-6-创新互联

中级提升班-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不更新

证明：

  1. 若数组中均为负数，则cur不断取值不断被重置为0，max最终为负数中的大值
  2. 若数组中无正数，则当遇到cur小于0，被重置为0，max为0
  3. 当数组中有负有正，该方法能找到数组中累加和大且最长的一段子数组(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;
}
题目七 子矩阵 子矩阵大累加和、压缩数组

给定一个整型矩阵，返回子矩阵的大累计和。

流程：

  1. 设有3行矩阵，分别计算仅包含0行，01行，012行，1行，12行，2行的矩阵的大子数组累加和

在这里插入图片描述

  1. 计算第0行，相当于题目六中求子数组大累加和
  2. 计算第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://cdxtjz.cn/article/joccd.html

其他资讯