题目:题干解析:题目给定n个非负整数,假设有n个宽度为1,高度为heights[i]的矩形拼接在一起,题目要求我们返回能够完全被覆盖的矩形的最大值.首先我们证明这个矩形的高一定是heights中的一个元素,因为如果不是那么要让其完全被覆盖其高度一定就小于height,因此存在另一个矩形,其高度就是height宽度与其相同,则该矩形面积会更大,因此符合题意的矩形高度一定为height数组中的一个元素.算法思路:本题其实有三种解决方法,分别为一,二,三次遍历实现,目前我只弄懂了三次遍历实现的方法,因此只讲解此方法.我们已知符合题意得矩形高度一定为数组中的一个元素,因此我们遍历整个数组针对每个元素进...

题干分析:题目要求我们针对一个只含有'('和')'字符的字符串中选取最长的可匹配的括号字串,返回子串的长度.首先关于括号匹配,由于匹配的括号一定为一对,因此我们可以确定这个返回值是个偶数(虽然基本没啥用)算法思路:我们有至少两个思路.方法一便是直接模拟,我们创建一个既能存储整数,又能存储字符的栈(可以使用结构体),我们扫描整个字符串,遇到'('便压栈,遇到')':  首先判断栈顶是否为'(', 如果是,则匹配成功,将栈顶元素弹出,创建一个整数2表示已匹配字符串长度,然后持续弹出栈顶为数字的元素并相加,直到栈顶再次为字符,保证整数合并; 如果栈顶不是'('但是是数字,我们弹出该数字暂存,然后判断...

题干分析:题目要求我们生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同二叉搜索树。可以按任意顺序返回答案。二叉搜索树定义如下：节点的左子树只包含 严格小于 当前节点的数。节点的右子树只包含 严格大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。算法逻辑:针对编码为1~n,根节点编码为i的二叉搜索树可以看作左子树编码为1~(i-1)的二叉搜索树与右子树为(i+1)~n编码的二叉树拼在编码为i的根节点形成,因此我们通过引入构建编码为start~end的所有二叉搜索树辅助函数进构建,每次循环从i=start到i=end每次循环进行笛卡尔组合所有可能的左右子树.实现代...

题干分析:题目要求我们针对一个只有两个节点发生错误互换的二叉搜索树进行修复.二叉搜索树定义如下：节点的左子树只包含 严格小于 当前节点的数。节点的右子树只包含 严格大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。针对二叉搜索树,其中序遍历序列应为一个严格递增序列.依题意得,这个二叉搜索树有且仅有两个节点发生了互换,因此中序遍历序列应当也只有两个序列值不符合严格递增规定.算法思路:我们只需针对两个不符合严格递增节点进行值互换即可,但注意这两个节点是否相邻有两种情况:情况1:不相邻: 例如中序序列为 1, 8, 3, 4, 5, 6, 7, 2, 9,其中2与8发生了互换,中序遍历时...

题干解析:检验一棵树是否为二叉树,检验成功则返回true,不成功则为false有效 二叉搜索树定义如下：节点的左子树只包含 严格小于 当前节点的数。节点的右子树只包含 严格大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。针对二叉树搜索树有一个众所周知的结论(不知道的现在就知道了):对二叉搜索树进行中序遍历得到的节点值数组为严格递增数组.应用此结论,题目就变成了中序遍历此树,遍历的同时判断序列是否严格递增算法思路:递归中序遍历,每次与前一个节点最大值进行比较,如果大于则继续递归,小于则结束递归,返回false实现代码: /** * Definition for a binary t...

题目链接:洛谷P2168题干解析:总体需求: 题目要求我们针对n种不同的单词,使用k进制编码进行编号,使编码后的文本长度最小.对于任意两个不同的单词,其编码不能有公共前缀.追加需求: 在确保总长最小的情况下使最长编码尽可能最短.这是典型的哈夫曼编码压缩的实现,同时需要我们建立的哈夫曼树高度尽可能小.此后此题基本上没有其他限制,模拟实现即可.算法思路:由于题目允许k进制编码,传统的二叉哈夫曼树并不完全契合本题情况,以下实现通过模拟k叉树进行实现.首先建立哈夫曼树过程:由于k叉哈夫曼树子叶节点数m应满足: (m - 1) mod (k - 1) = 0,即(m - 1)能被k - 1整除(建立的k...

/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ ListNode* deleteDuplicates(ListNode* head) { // write code here if (...

/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ ListNode* reverseKGroup(ListNode* head, int k) { //...

/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ #include <bits/types/struct_tm.h> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNod...

/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ #include <set> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param lists ListNode类vector * @return ListNode类 */ ListNode* mergeKLists(vector<ListNode...

#include <climits> #include <deque> #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param num int整型vector * @param size int整型 * @return int整型vector */ vector<int> maxInWindows(vector<int>& num, int size) { // write code h...

class Solution { public: void push(int node) { while (!stack2.empty()) { stack1.push(stack2.top()); stack2.pop(); } stack1.push(node); } int pop() { while (!stack1.empty()) { stack2.push(stack1.top()); stack1.pop(); } int data = stack2.top(); stack2.pop(); return data; } private: stack<int> st...