|
C++常用数据结构
链表内存的申请与释放滑动窗口前缀和/积与后缀和/积差分数组线段树前缀树/字典树（Trie）单调栈单调队列并查集二叉树创建二叉树二叉树的遍历二叉树遍历的变体平衡二叉树（AVL）与二叉搜索树N叉树图拓扑排序链表链表（单链表）的基本操作及C语言实现链表中存放的不是基本数据类型，需要用结构体实现自定义：typedef struct Link{ char elem;//代表数据域 struct Link * next;//代表指针域，指向直接后继元素}link;12345next的值实际上就是下一个节点的地址，当前节点为末节点时，next的值设为空指针。像上面这种只包含一个指针域、由n个节点链接形成的链表，就称为线型链表或者单向链表，链表只能顺序访问，不能随机访问，链表这种存储方式最大缺点就是容易出现断链。头结点和头指针的区别：头指针是一个指针，头指针指向链表的头结点或者首元结点；头结点是一个实际存在的结点，它包含有数据域和指针域。两者在程序中的直接体现就是：头指针只声明而没有分配存储空间，头结点进行了声明并分配了一个结点的实际物理内存。单链表中可以没有头结点，但是不能没有头指针！单向链表+头指针+尾指针：struct ListNode { int val; ListNode next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode next) : val(x), next(next) {} };ListNode head = nullptr, tail = nullptr;//从尾部插入结点head = tail = new ListNode(num1);tail->next = new ListNode(num2);tail = tail->next;123456789101112注意：nullptr在C++11中就是代表空指针，不能被转换成数字。在编译器进行解释程序时，NULL会被直接解释成0。链表的题通常需要注意几点：舍得用变量，千万别想着节省变量，否则容易被逻辑绕晕head 有可能需要改动时，先增加一个 假head，返回的时候直接取 假head.next，这样就不需要为修改 head 增加一大堆逻辑了。while(p->next&&p->next->next)while(p->next&&p->next->val==x)p->next必须要写在前面ListNode k=new ListNode(0,head);//不要省建立头结点的功夫此外还需要注意，能用f作为判定条件，就尽量不要以f->next作为判定条件，若f直接为空指针，会直接炸掉。这里涉及到短路或、短路与的概念。//尽量不要以f->next作为判定条件，若f直接为空指针，会直接炸掉下面这个方法不好 while(f->next&&i<index-1) { f=f->next; i++; } //改成下面的样子比较好NodeList f =head;int i=0;while(f&&i<index-1){ f=f->next; i++;}if(!f)//超出链表范围则退出{ return;}if(f->next){ NodeList m=f->next; f->next=m->next; delete m;//delete与new匹配}1234567891011121314151617181920212223242526单向链表常用的初始化：//单向链表常用的初始化class MyLinkedList {private: struct NodeList { int val; NodeList next; NodeList():val(0),next(nullptr){}//{} NodeList(int n):val(n),next(nullptr){} };//; NodeList * head;public: MyLinkedList():head(nullptr) {}//默认构造函数，调用时不用加（） Main函数调用MyLinkedList list;//不需要（），加括号会被误认为调用函数123456789101112131415C++双向链表模板：//C++双向链表模板class MyList{private: struct ListNode { int val; ListNode next,prev; ListNode(int x):val(x),next(nullptr),prev(nullptr){} };private: //头节点尾节点都为空，表示为空链表 ListNode head,tail; int size=0;public: MyList():size(0),head(nullptr),tail(nullptr){}12345678910111213141516反转链表：从前往后挨着元素反转，并记录反转头prev，剩下未反转部分的头curr，以及下一个元素next。直到剩下未反转头curr为空。Prev初始值也为空，curr初始值为head。ListNode reverseList(ListNode head) { ListNode pre = nullptr; ListNode cur = head; ListNode nex ; while(cur) { nex = cur->next;//提前该语句 cur->next=pre; pre=cur; cur=nex; // nex = cur->next;//当cur为空指针时该语句会报错，运行超时，需要将该语句提前 } return pre; }123456789101112131415易错点是while判定条件里next需要提前写，将实际遍历的结点作为判定条件，否则容易runtime error。内存的申请与释放free和delete区别_prerfect_cat的博客free和mall匹配：释放malloc出来动态内存;delete和new匹配：释放new出来的动态内存空间。在类和对象的时候会有很大区别。在使用malloc和free来处理动态内存的时候，仅仅是释放了这个对象所占的内存，而不会调用这个对象的析构函数；使用new和delete就可以既释放对象的内存的同时，调用这个对象的析构函数。delete释放对象数组时：千万不能丢失”[]”
如果用new 创建对象数组，那么只能使用对象的无参数构造函数。例如Obj objects = new Obj[100];
// 创建100 个动态对象1在用delete 释放对象数组时，留意不要丢了符号‘[ ]’。
例如delete []objects; // 正确的用法delete objects; // 错误的用法12后者相当于delete objects[0]，漏掉了另外99 个对象。new出来的是一段空间的首地址。所以一般需要用指针来存放这段地址。 //可以在new后面直接赋值 int p = new int(3); //也可以单独赋值 //p = 3; //如果不想使用指针，可以定义一个变量，在new之前用“”表示new出来的内容 int q = new int; //当new一个数组时，同样用一个指针接住数组的首地址 int q = new int[3];12345678//这里是用一个结构体指针接住结构体数组的首地址//对于结构体指针，个人认为目前这种赋值方法比较方便struct student{ string name; int score;};student stlist = new student[3]{{“abc”, 90}, {“bac”, 78}, {“ccd”, 93}};12345678滑动窗口什么是滑动窗口？其实就是一个队列,比如下面例题中的字符串 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！如何移动？我们只要把队列的左边的元素移出就行了，直到满足题目要求！一直维持这样的队列，找出队列出现最长的长度时候，求出解！时间复杂度：O(n)3. 无重复字符的最长子串给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。示例：输入: s = “pwwkew”输出: 3解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。【分析】用滑动窗口，固定最左边 l，每次都从最右边 r 开始扩张，出现重复元素时，删除哈希集合中从 l 到重复元素下标之间的元素，将 l 进行更新，并继续向右扩张 r 。关键点：如果依次递增地枚举子串的起始位置，那么子串的结束位置也是递增的！因为当前结束位置前面都是无重复子串了，删掉最左边起始位置后，剩下的这一截更是无重复子串，所以每次移动右窗口指针时候只需要从上次结束位置开始就行。用哈希集合判断重复。 int lengthOfLongestSubstring(string s) { if(s.empty()) return 0; int n = s.size(); unordered_set st; int l = 0, maxlen = 0; for(int r = 0; r < n; ++r){ //删除哈希集合中从 l 到重复元素下标之间的元素，将 l 进行更新 while(st.find(s[r]) != st.end()){ st.erase(s[l]); ++l; } //每次右移r时，就更新一下最长长度， //以免出现整个字符串都无重复，遍历到头一直没更新长度的情况 maxlen = max(r - l + 1, maxlen); st.insert(s[r]); } return maxlen; }123456789101112131415161718也可以用哈希表实现，用哈希表记录每个元素出现的下标，可以精确知道删除重复元素时的循环次数。 int lengthOfLongestSubstring(string s) { if(s.empty()) return 0; int n = s.size(); unordered_map<char, int> mp; //每次固定l, 右移r，出现重复元素时再更新l int l = 0, maxlen = 0; for(int r = 0; r < n; ++r){ //若发现重复字符，则通过哈希表找到第一个重复下标 //删除从l到重复下标之间的哈希表元素，并将l重置为重复下标的下一个位置 if(mp.find(s[r]) != mp.end()){ int newl = mp[s[r]] + 1; for(int i = l; i < newl; i++){ mp.erase(s[i]); } l = newl; } //每次右移r时，就更新一下最长长度， //以免出现整个字符串都无重复，遍历到头一直没更新长度的情况 maxlen = max(r - l + 1, maxlen); mp[s[r]] = r;; } return maxlen; }123456789101112131415161718192021222376. 最小覆盖子串给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。注意：对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串，我们保证它是唯一的答案。示例 1：输入：s = “ADOBECODEBANC”, t = “ABC”输出：“BANC”【分析】滑动窗口我们可以用滑动窗口的思想解决这个问题。在滑动窗口类型的问题中都会有两个指针，一个用于「延伸」现有窗口的 r 指针，和一个用于「收缩」窗口的 l 指针。在任意时刻，只有一个指针运动，而另一个保持静止。我们在 s 上滑动窗口，通过移动 r 指针不断扩张窗口。当窗口包含 t 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。如何判断当前的窗口包含所有 t 所需的字符呢？我们可以用一个哈希表表示 t 中所有的字符以及它们的个数，用一个哈希表动态维护窗口中所有的字符以及它们的个数，如果这个动态表中包含 t 的哈希表中的所有字符，并且对应的个数都不小于 t 的哈希表中各个字符的个数，那么当前的窗口是「可行」的。注意：这里 t 中可能出现重复的字符，所以我们要记录字符的个数。举个例子：如果 s = X X ? X A B C X X X X s = {\rm XX \cdots XABCXXXX}s=XX?XABCXXXX，t = A B C t = {\rm ABC}t=ABC，那么显然 [ X X ? X A B C ] {\rm [XX \cdots XABC]}[XX?XABC] 是第一个得到的「可行」区间，得到这个可行区间后，我们按照「收缩」窗口的原则更新左边界，得到最小区间。 unordered_map<char, int> ori, cnt; bool check(){ for(const auto& f:ori){ if(cnt[f.first] < f.second){ return false; } } return true; } string minWindow(string s, string t) { for(const char& c:t){ ori[c]++; } int l = 0, r = 0, ansl = -1; int len = INT_MAX, n = s.size(); while(r < n){ if(ori.find(s[r]) != ori.end()){ cnt[s[r]]++; } ++r; while(check() && l <= r){ if(r - l < len){ len = r - l; ansl = l; } if(ori.find(s[l]) != ori.end()){ cnt[s[l]]–; } ++l; } } return ansl == -1 ? string() : s.substr(ansl, len); }12345678910111213141516171819202122232425262728293031323334353637383940其他滑动窗口例题：滑动窗口讲解438. 找到字符串中所有字母异位词30. 串联所有单词的子串76. 最小覆盖子串159. 至多包含两个不同字符的最长子串209. 长度最小的子数组239. 滑动窗口最大值567. 字符串的排列632. 最小区间727. 最小窗口子序列例题讲解：438. 找到字符串中所有字母异位词给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。示例 1:输入: s = “cbaebabacd”, p = “abc”输出: [0,6]解释: 起始索引等于 0 的子串是 “cba”, 它是"abc" 的异位词。 起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。【分析】在字符串 s 中构造一个长度为与字符串 p 的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗口为字符串 p 的异位词。在算法的实现中，可以使用数组来存储字符串 pp 和滑动窗口中每种字母的数量。【细节】当字符串 s 的长度小于字符串 p 的长度时，字符串 s 中一定不存在字符串 p 的异位词。但是因为字符串 s 中无法构造长度与字符串 p 的长度相同的窗口，所以这种情况需要单独处理。此外，比较两个数组是否相等时，可以直接用 “数组1 == 数组2” 来判断。 vector findAnagrams(string s, string p) { int m = p.size(), n = s.size(); if(n < m) return {}; vector ans; vector scount(26); vector pcount(26); for(int i = 0; i < m; ++i){ ++scount[s[i] - ‘a’]; ++pcount[p[i] - ‘a’]; } for(int l = 0; l + m <= n; ++l){ if(l != 0){ ++scount[s[l + m -1] - ‘a’]; --scount[s[l - 1] - ‘a’]; } //判断两个数组是否相等，可以直接用 == if(scount == pcount){ ans.emplace_back(l); } } return ans; }12345678910111213141516171819202122下面第30题的过渡版写法：用了一个哈希表来进出字符，初始时先存p的哈希值，再减去s中第一个窗口的哈希值，之后对s进行窗口滑动，以及哈希表字符进出，当字符键值为0时删除该字符，当哈希表为空时表示匹配成功，可以存入输出数组。 vector findAnagrams(string s, string p) { vector ans; unordered_map<char, int> mp; int m = p.size(), n = s.size(); //用字符串 p 来初始化哈希表 for(char &ch : p){ ++mp[ch]; } //字符串 s 的首个窗口 for(int i = 0; i < m && i < n; ++i){ if(–mp[s[i]] == 0){ mp.erase(s[i]); } } //对字符串 s 进行滑动窗口 for(int l = 0; l + m <= n; ++l){ if(l != 0){ //注意这里的++ 与 --特别容易搞混 if(–mp[s[l + m - 1]] == 0) mp.erase(s[l + m - 1]); if(++mp[s[l - 1]] == 0) mp.erase(s[l - 1]); } if(mp.empty()){ ans.emplace_back(l); } } return ans; }12345678910111213141516171819202122232425262730. 串联所有单词的子串给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。示例 1：输入：s = “barfoothefoobarman”, words = [“foo”,“bar”]输出：[0,9]解释：从索引 0 和 9 开始的子串分别是 “barfoo” 和 “foobar” 。 输出的顺序不重要, [9,0] 也是有效答案。【分析】记 words \textit{words}words 的长度为 m mm，words \textit{words}words 中每个单词的长度为 n nn，s ss 的长度为 ls \textit{ls}ls。首先需要将 s ss 划分为单词组，每个单词的大小均为 n nn （首尾除外）。这样的划分方法有 n nn 种，即先删去前 i ii （i = 0 ～ n ? 1 i = 0 \sim n-1i=0～n?1）个字母后，将剩下的字母进行划分，如果末尾有不到 n nn 个字母也删去。对这 n nn 种划分得到的单词数组分别使用滑动窗口对 words \textit{words}words 进行类似于「字母异位词」的搜寻。划分成单词组后，一个窗口包含 s ss 中前 m mm 个单词，用一个哈希表 differ \textit{differ}differ 表示窗口中单词频次和 words \textit{words}words 中单词频次之差。初始化 differ \textit{differ}differ 时，出现在窗口中的单词，每出现一次，相应的值增加 1，出现在 words \textit{words}words 中的单词，每出现一次，相应的值减少 1。然后将窗口右移，右侧会加入一个单词，左侧会移出一个单词，并对 differ \textit{differ}differ 做相应的更新。窗口移动时，若出现 differ \textit{differ}differ 中值不为 0 的键的数量为 0，则表示这个窗口中的单词频次和 words \textit{words}words 中单词频次相同，窗口的左端点是一个待求的起始位置。划分的方法有 n nn 种，做 n nn 次滑动窗口后，即可找到所有的起始位置。 vector findSubstring(string s, vector& words) { vector ans; int m = words.size(); int n = words[0].size(); int ls = s.size(); //注意添加&& i + m * n 长度限制 for(int i = 0; i < n && i + m * n <= ls; ++i){ unordered_map<string, int> mp; //现将 s 中前 m 个单词作为初始化窗口 for(int j = 0; j < m; ++j){ string str = s.substr(i + j * n, n);//注意添加起始位置，i + mp[str]++; } for(string &str : words){ if(–mp[str] == 0){ mp.erase(str); } } //向后边滑动窗口 for(int l = i; l + m * n <= ls; l += n){ if(l != i){ string str = s.substr(l - n, n); if(–mp[str] == 0){ mp.erase(str); } str = s.substr(l + (m - 1) * n, n); if(++mp[str] == 0){ // == 0 mp.erase(str); } } if(mp.empty()){ ans.emplace_back(l); } } } return ans; }12345678910111213141516171819202122232425262728293031323334353637前缀和/积与后缀和/积前缀和/积与后缀和/积不是什么数据结构，而是一种常用的技巧。常用于查询连续区间和是否为k，以及区间值运算等问题。前缀和经常和哈希表结合，这样可以将查询的操作提升到O(1), 但是使用前缀和会有一个问题，当我们的更新次数过多时，尤其是需要更新的元素比较靠前时，每一次更新的代价都会为O(n)，从而没有达到优化的效果。前缀和适用于元素不变动的数组！前缀和非常经典的一道好题：560. 和为 K 的子数组给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。示例 1：输入：nums = [1,1,1], k = 2输出：2示例 2：输入：nums = [1,2,3], k = 3输出：2【分析】前缀和 + 哈希表优化定义 pre [ i ] \textit{pre}[i]pre[i] 为 [ 0… i ] [0…i][0…i] 里所有数的和，我们需要统计符合条件的下标 j jj 的个数，其中 0 ≤ j ≤ i 0\leq j\leq i0≤j≤i 且 [ j . . i ] [j…i][j…i] 这个子数组的和恰好为 k kk 。考虑以 i ii 结尾的和为 k kk 的连续子数组个数时只要统计有多少个前缀和为 pre [ i ] ? k \textit{pre}[i]-kpre[i]?k 的 pre [ j ] \textit{pre}[j]pre[j] 即可。我们建立哈希表 mp \textit{mp}mp，以和为键，出现次数为对应的值，记录 pre [ i ] \textit{pre}[i]pre[i] 出现的次数，从左往右边更新 mp \textit{mp}mp 边计算答案，那么以 i ii 结尾的答案 mp [ pre [ i ] ? k ] \textit{mp}[\textit{pre}[i]-k]mp[pre[i]?k] 即可在 O ( 1 ) O(1)O(1) 时间内得到。最后的答案即为所有下标结尾的和为 k kk 的子数组个数之和。需要注意的是，从左往右边更新边计算的时候已经保证了mp [ pre [ i ] ? k ] \textit{mp}[\textit{pre}[i]-k]mp[pre[i]?k] 里记录的 pre [ j ] \textit{pre}[j]pre[j] 的下标范围是 0 ≤ j ≤ i 0\leq j\leq i0≤j≤i 。同时，由于pre [ i ] \textit{pre}[i]pre[i] 的计算只与前一项的答案有关，因此我们可以不用建立 pre \textit{pre}pre 数组，直接用 pre \textit{pre}pre 变量来记录 p r e [ i ? 1 ] pre[i-1]pre[i?1] 的答案即可。 int subarraySum(vector& nums, int k) { unordered_map<int, int> mp; mp[0] = 1; int pre = 0, ans = 0; for(int &a:nums){ pre += a; ans += mp[pre - k]; //if (mp.find(pre - k) != mp.end()) mp[pre]++; } return ans; }1234567891011前缀积与后缀积的经典例题：剑指 Offer 66. 构建乘积数组给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。示例:输入: [1,2,3,4,5]输出: [120,60,40,30,24]【分析】我们不必将所有数字的乘积除以给定索引处的数字得到相应的答案，而是利用索引左侧所有数字的乘积和右侧所有数字的乘积（即前缀与后缀）相乘得到答案。对于给定索引 i ii，我们将使用它左边所有数字的乘积乘以右边所有数字的乘积。由于输出数组不算在空间复杂度内，所以可以先利用输出数组作为前缀和数组，然后再在输出数组的基础上×后缀和（用一个变量表示即可），从而大大节省空间。算法1）初始化 ans 数组，对于给定索引 i，a n s [ i ] ans[i]ans[i] 代表的是 i 左侧所有数字的乘积。2）不用构造后缀和数组，而是用一个变量 r rr 表示索引 i 右侧数字的乘积。通过遍历来不断更新右侧元素的乘积 r 。更新数组 a n s [ i ] = a n s [ i ] ? r ans[i]=ans[i]rans[i]=ans[i]?r ，然后 r rr 更新为 r = r ? a [ i ] r=ra[i]r=r?a[i]。 vector constructArr(vector& a) { int n = a.size(); vector ans(n); if(a.empty()) return ans; // ans[i] 表示索引 i 左侧所有元素的乘积 // 因为索引为 ‘0’ 的元素左侧没有元素， 所以 ans[0] = 1 ans[0] = 1; for(int i = 1; i < n; ++i){ ans[i] = ans[i - 1] * a[i - 1]; } // r 为右侧所有元素的乘积 // 刚开始右边没有元素，所以 r = 1 int r = 1; for(int i = n - 1; i >= 0; --i){ // 对于索引 i，左边的乘积为 ans[i]，右边的乘积为 r ans[i] = r; // r 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 r 上 r = a[i]; } return ans; }123456789101112131415161718192021差分数组差分数组又叫插旗法，利用差分前缀和来求解公交车上下车和插旗问题等区间更新、区间重叠（活动安排）问题。差分数组是把原数组中后一个元素减前一个元素的差构成一个新的数组，作为辅助数组使用。通常用map 数据结构实现，如下图所示：差分数组有什么用？diff[0] = nums[0];diff[1] = nums[1] - nums[0];diff[2] = nums[2] - nums[1];…nums[0] = diff[0];nums[1] = diff[1] + nums[0] = diff[0] + diff[1];nums[2] = nums[1] + diff[2] = diff[0] + diff[1] + diff[2];…nums[n] = diff[0] + diff[1] +diff[2] +…+ diff[n]由上可知:根据差分数组各项的前缀和，即可还原出原数组的各值，差分数组常用于对区间内元素值的统一修改。 假设我们频繁得对原数组进行范围更新，则只需要更新差分数组端点值即可。应用举例1：假如把 nums 数组中 [0,3] 范围到元素值都加 2：常规方法：for( int i =0;i < 4;++i){ nums[i] += 2;}1234差分数组：map<int, int> diff;diff[0] += 2;// 0 往后到值全部加 2diff[4] -= 2;// 4 往后到值全部减 2123应用举例2：在区间 [10, 15) [12, 18) 内进行插旗，判断插旗区间是否有重叠。插旗子 计数：对于每个区间[start,end)，在 start 计数diff[start] 加 1，表示从start 开始插旗的数目加 1；从 end 计数diff[end] 减 1，表示从 end 开始插旗的数目减 1。若差分数组前缀和 >1 即表示到当前位置为止的插旗区有重叠。区间原数组nums 10 12 15 18差分数组diff 1 1 -1 -1【分析】建立差分数组diff，nums数组中的每个区间的start对应的差分数组计数 ++， end 对应的差分数组计数 – ，注意每个区间的start 和 end 是分别作为独立key 存储到查分数组中的，对应的value分别为++和–之后的值 ，而不是start 对应 key，end 对应value这样存储。所有区间的 start 和 end 存储到 map 中后，一起按照key从大到小的顺序排序//nums = {{10, 15}, {12, 18}}//建立差分数组diff，每个区间的start对应的差分数组计数 ++， end 对应的差分数组计数 --//注意每个区间的start 和 end 是分别作为独立key 存储到查分数组中的，对应的value分别为++和–之后的值//而不是start 对应 key，end 对应value这样存储。//所有区间的 start 和 end 存储到 map 中后，一起按照key从大到小的顺序排序map<int, int> diff;for(auto v:nums){ diff[v[0]] ++; diff[v[1]] --;}//遍历差分数组，用cnt进行插旗计数，大于1则说明区间重叠int cnt = 0;for(auto w:diff){ cnt += w.second; if(cnt > 1){ cout <<“插旗区间出现重叠” <<endl; break; }} 12345678910111213141516171819如果 两个Interval 不相交，则 连续两个 插旗计数的 和 必然等于零，一个+1，一个-1如果 两个 Interval 相交，则 连续两个插旗计数 的和 必然大于0，一个+1，一个+1732. 我的日程安排表 III当 k 个日程安排有一些时间上的交叉时（例如 k 个日程安排都在同一时间内），就会产生 k 次预订。给你一些日程安排 [start, end) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。实现一个 MyCalendarThree 类来存放你的日程安排，你可以一直添加新的日程安排。MyCalendarThree() 初始化对象。int book(int start, int end) 返回一个整数 k ，表示日历中存在的 k 次预订的最大值。示例：输入：[“MyCalendarThree”, “book”, “book”, “book”, “book”, “book”, “book”][[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]输出：[null, 1, 1, 2, 3, 3, 3]解释：MyCalendarThree myCalendarThree = new MyCalendarThree();myCalendarThree.book(10, 20); // 返回 1 ，第一个日程安排可以预订并且不存在相交，所以最大 k 次预订是1 次预订。myCalendarThree.book(50, 60); // 返回 1 ，第二个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。myCalendarThree.book(10, 40); // 返回 2 ，第三个日程安排 [10, 40)与第一个日程安排相交，所以最大 k 次预订是 2 次预订。 myCalendarThree.book(5, 15); // 返回 3，剩下的日程安排的最大 k 次预订是 3 次预订。myCalendarThree.book(5, 10); // 返回 3myCalendarThree.book(25, 55); // 返回 3题目翻译：有一个数组初始值全部为 0 ，每次调用 book 方法都把 [start,end) 范围内的所有元素加 1，并返回当前数组中的最大值。【解答】直接构建差分数组，更改区间值后再用前缀和还原出原数组即可。利用差分数组的思想，每当我们预定一个新的日程安排[start,end)，在 start 计数diff[start] 加 1，表示从start 预定的数目加 1；从 end 计数diff[end] 减 1，表示从 end 开始预定的数目减 1。从起点开始的计数累加值（前缀和）即为当前位置原数组的值（也就是该区间日程的安排次数）【注意点】book传入的区间是左闭右开 所以[5,10) 跟 [10,…) 不会有 overlap 交叉map 自带按key值的递增排序.代码class MyCalendarThree {public: MyCalendarThree() {} int book(int start, int end) { diff[start]++;// start 开始的值都加 1 diff[end]–;// end 开始的值都减 1 int res = 0; int cur = 0; for( auto & kv : diff ) { cur += kv.second;//前缀和还原原数组值 res = max(res,cur); } return res; }private: map<int,int> diff;//差分数组};123456789101112131415161718731. 我的日程安排表 II实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end。当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生三重预订。每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。请按照以下步骤调用MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)示例：MyCalendar();MyCalendar.book(10, 20); // returns trueMyCalendar.book(50, 60); // returns trueMyCalendar.book(10, 40); // returns trueMyCalendar.book(5, 15); // returns falseMyCalendar.book(5, 10); // returns trueMyCalendar.book(25, 55); //returns true解释：前两个日程安排可以添加至日历中。第三个日程安排会导致双重预订，但可以添加至日历中。第四个日程安排活动（5,15）不能添加至日历中，因为它会导致三重预订。第五个日程安排（5,10）可以添加至日历中，因为它未使用已经双重预订的时间10。第六个日程安排（25,55）可以添加至日历中，因为时间[25,40] 将和第三个日程安排双重预订； 时间 [40,50] 将单独预订，时间 [50,55）将和第二个日程安排双重预订。class MyCalendarTwo { map <int, int> differ;public: MyCalendarTwo() { } bool book(int start, int end) { differ[start]++; differ[end]–; int cur = 0; for(auto mp : differ){ if(mp.first == end){ break; } cur += mp.second; if(mp.first >= start){ if(cur >= 3){//注意：当三重订单时需要删除当前日程安排，否则将因为误添加订单，导致后面的订单数计算有误 differ[start]–; differ[end]++; return false; } } } return true; }};1234567891011121314151617181920212223242526272829补充题：729. 我的日程安排表 I实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成 重复预订 ，则可以存储这个新的日程安排。当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生 重复预订 。日程可以用一对整数 start 和 end 表示，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end 。实现 MyCalendar 类：MyCalendar() 初始化日历对象。boolean book(int start, int end) 如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true 。否则，返回 false 并且不要将该日程安排添加到日历中。示例：输入：[“MyCalendar”, “book”, “book”, “book”][[], [10, 20], [15, 25], [20, 30]]输出：[null, true, false, true]解释：MyCalendar myCalendar = new MyCalendar();myCalendar.book(10, 20); // return TruemyCalendar.book(15, 25); // return False，这个日程安排不能添加到日历中，因为时间 15 已经被另一个日程安排预订了。myCalendar.book(20, 30); // return True ，这个日程安排可以添加到日历中，因为第一个日程安排预订的每个时间都小于 20 ，且不包含时间 20 。【分析】二分查找按时间顺序维护日程安排，用 Set数据结构来保持元素排序和支持快速插入。class MyCalendar { //按时间顺序维护日程安排，则可以通过二分查找日程安排的情况来检查新日程安排是否可以预订 //需要一个数据结构能够保持元素排序和支持快速插入，可以用 Set 来构建 set<pair<int, int>> calendar;public: MyCalendar() {} bool book(int start, int end) { //每次查找起点大于等于 end 的第一个区间 //对于集合set而言没有下面这种用法 // auto it = lower_bound(calendar.begin(), calendar.end(), {end, 0}); //集合set需要这样调用二分查找函数 auto it = calendar.lower_bound({end, 0}); //同时紧挨着这个第一个区间的前一个区间的后端（注意不是前端）需要≤start if(it == calendar.begin() || (–it)->second <= start){ calendar.insert({start, end}); return true; } return false; }};123456789101112131415161718192021线段树除了查分数组之外，另一种维护区间更新的数据结构就是线段树，线段树除了可以快速的更新区间，还可以快速的查询区间最值。由于普通的线段树需要开4n的空间，所以为了让数据离散化可以选择动态开点。并且根节点的值就是所有区间的最大值，通常来说，时间提升了不少但整体空间复杂度提升。线段树最经典的应该是307.区域和检索。就是给你一个数组，会有简单的更新操作以及查询区域和的操作。查询操作指的是给你一个区间[L,R], 返回该区间[L,R]内所有元素的和。更新操作指的是，给你一个下标索引和一个值，将数组中该索引值对于的元素值改为新的给定值。线段树（处理区域和查询问题）：对于查询区间和，我们容易想到的一个点就是使用前缀和，这样我们就可以将查询的操作提升到O(1), 但是使用前缀和会有一个问题，当我们的更新次数过多时，尤其是需要更新的元素比较靠前时，每一次更新的代价都会为O(n)，从而没有达到优化的效果。但是对于元素不变动的数组前缀和还是有很不错的优势！线段树将此类问题的查询以及更新的时间复杂度都变成了O(logn)。当进行多次查询与更新时，线段树一定比前缀和更具优势。线段树的结构有点像堆，首先需要明确的是，我们用数组来表示树的结构，对于根树的根节点，它会在index=1的位置上(其实此处0也行，不过大家普遍用1,区别就是计算子节点的方式不同)，然后对于其节点的左右子节点的下标分别为 2×index 与 2×index+1。然后其子节点也是这样的规律。查询: 我们会根据区间从根节点向树的两边递归查寻。假设我们现在要查找此树的[2,4]的区间和，即[50,50,1]的和, 那么这个过程是什么样的呢？更新：假设我们要将其数组中的1更新为2，结构会发生什么变化？而有那些节点会做出改变呢？到此我们已经基本了解了线段树了，我们发现线段树让更新与查询的时间复杂度都变成了O(logn), 下面我们来代码层面的学习一下线段树。建树跑完以上代码后，我们的线段树数组如下: （可以发现根节点在索引为1的位置的确为284，是所有元素的和，读者可以根据树的结构，以及从开头介绍的左右子节点的计算方式一一检查是否正确检索检索需要讨论以下情况：情况一：情况二：情况二则是当前区间被我们的检索区间包围，即蓝色区间在绿色区间里面时，因此不必继续往下递归，可以直接返回当前节点值。这里比较容易想，读者可参考之前的线段树查询。思考一下，每一个节点表示的都是一个区间内所有元素的和，那么当整个当前区间都被我们的检索区间包围了，证明我们需要所有的元素，因此不必继续往下递归查询，可以返回其节点值。譬如之前例子中的区间[3,4]，代码输出中依然可以观察到这一点。代码如下:示例查询区间[2,4]的区域和结果如下: 50 + 50 + 1 = 101.为了可视化，我在其query方法中加入了几行输出。我们可以发现当递归到区间[3,4]时其实已经停止继续递归下去了，这正是我们想要的结果。更新更新与建树很像，当其递归到出口时就说明我们已经找到了要更新元素的节点。要注意更新完元素后，其包含此元素的区间节点都需要更新，代码中已加注释。我们做一次更新，将数组从[93,90,50,50,1]改到[93,90,50,50,2]，然后在做一次查询看结果是否正确:题目练习：732. 我的日程安排表 III当 k 个日程安排有一些时间上的交叉时（例如 k 个日程安排都在同一时间内），就会产生 k 次预订。给你一些日程安排 [start, end) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。【问题解读】首先我们来将问题转化一下，让题意更加明显，其实本题的本质就是给你一个区间，然后让你将其[start, end)内所有的元素值加上1，在进行了每一次的book更新的操作后，返回[0, 1 e 9 1e91e9]这个区间内的最大元素值是多少。本题的解法本质上其实也是运用了线段树的思想，但是从检查区域和，变为了检索线段树中叶子节点的最大值是多少。我们很容易的想到，对于其一段区间我们需要book时，我们可以将其区间内的所有元素都加上1。显而易见的是，我们无法真的去建树，以及真的去更新其元素值。对于第一个问题，由于此题的数据问题，我们可能造成内存溢出。因此我们用哈希表来表示我们的线段树，这样可以省去许多内存空间。对于其第二个问题，不需要真的去手动更新每个节点值。我们选择的是官解中的懒标记，及如果当前节点区间的被索引的区间覆盖时，我们则将表示此区间的节点值加1，表示此区间内的所有元素值都加了一位，这里很重要，读者需要多读几遍。 个人觉得懒标记最难理解的地方就在这里，详细可看思路步骤中的第二点解读。【思路步骤】1.需要两个哈希表，一个用于线段树，一个用于区间的懒标记使用。注意此时的线段树的节点拥有的是该区间内的所有元素中的最大值。（不要被上述区间和的例子干扰，注意本题问的是什么！区间和提供的是思路！)2.对于一个区间的更新，我们左右递归，下面分类讨论：1）当该区间不在检索区间内时，则start > r || end < l，不做更新，直接返回。2）当该区间被检索区间覆盖时，我们无需手动去更新该区间内所有元素值，只需要标记一下该区间内的所有元素都被加上了一位即可。显而易见，无论当前节点区间的最大值为多少，当该区间的所有元素值都加一时，其拥有的最大值自然也需要加一位。3）当该区间内有元素不在其检索区间时，递归左右两边去更新我们的线段树。3.返回根节点的最大值，即所有元素中的最大值。class MyCalendarThree {private: unordered_map<int, int> tree; unordered_map<int, int> lazy;public: MyCalendarThree() { } void update(int start, int end, int l, int r, int node) { if(start > r || end < l) { return; } else if(start <= l && r <= end) { // 当前区间被检索区间覆盖, 因此区间内所有元素都加一 // 自然而然，无论当前节点区间的最大值为多少，当该区间的所有 // 元素值都加一时，其拥有的最大值自然也需要加一位 ++tree[node]; ++lazy[node]; } else { int left_node = node2, right_node = node2 + 1; int mid = (l+r) >> 1; update(start, end, l, mid, left_node); update(start, end, mid+1, r, right_node); tree[node] = lazy[node] + max(tree[left_node], tree[right_node]); } } int book(int start, int end) { update(start, end-1, 0, 1e9, 1); return tree[1]; }};123456789101112131415161718192021222324252627282930313233复杂度分析时间复杂度：O ( n log ? C ) O(n \log C)O(nlogC)，其中 n 为日程安排的数量。由于使用了线段树查询，线段树的最大深度为 log ? C \log ClogC, 每次最多会查询 log ? C \log ClogC个节点，每次求最大的预定需的时间复杂度为 O ( log ? C + log ? C ) O(\log C + \log C)O(logC+logC)，因此时间复杂度为 O ( n log ? C ) O(n \log C)O(nlogC)，在此 C 取固定值即为 1 0 9 10^910 9 。空间复杂度：O ( n log ? C ) O(n \log C)O(nlogC)，其中 n 为日程安排的数量。由于该解法采用的为动态线段树，线段树的最大深度为 log ? C \log ClogC，每次预定最多会在线段树上增加log ? C \log ClogC个节点，因此空间复杂度为 O ( n log ? C ) O(n \log C)O(nlogC)，在此 C 取固定值即为 1 0 9 10^910 9 。前缀树/字典树（Trie）前缀树（Trie Tree），Trie [tra?] 读音和 try 相同，前缀树也叫字典树或单词查找树。Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。「前缀树」比较常用的应用场景：给定一个字符串集合构建一棵前缀树，然后给一个字符串，判断前缀树中是否存在该字符串或者该字符串的前缀。Trie 是一种非典型的多叉树模型，多叉好理解，即每个结点的分支数量可能为多个。为什么说非典型呢？因为它和一般的多叉树不一样，尤其在结点的数据结构设计上，比如一般的多叉树的结点是这样的：struct TreeNode { VALUETYPE value; //结点值 TreeNode children[NUM]; //指向孩子结点};1234而 Trie 的结点是这样的(假设只包含’a’~'z’中的字符)，可以理解为26叉树（有的分支为空，可以忽略）：struct TrieNode { bool isEnd; //该结点是否是一个串的结束 vector<TrieNode> children = vector<TrieNode>(26);//字母映射表 //TrieNode children[26]; //或者这样写};12345children 中保存了对当前结点而言下一个可能出现的所有字符的链接，因此我们可以通过一个父结点来预知它所有子结点的值：for (int i = 0; i < 26; i++) { char ch = ‘a’ + i; if (parentNode->children[i] == nullptr) { 说明父结点的后一个字母不可为 ch } else { 说明父结点的后一个字母可以是 ch }}12345678来看个例子，想象以下，包含三个单词 “sea”,“sells”,“she” 的 Trie 会长啥样呢？它的真实情况是这样的：Trie 中一般都含有大量的空链接，因此在绘制一棵单词查找树时一般会忽略空链接，同时为了方便理解我们可以画成这样：由于都是小写字母，所以对于每个节点，均有 26 个孩子节点，上图中没有画出来，省略了而已…，但是要记住：每个节点均有 26 个孩子节点还有一个点要明确：节点仅仅表示从根节点到本节点的路径构成的字符串是否有效而已对于上图中红色的节点，均为有效节点，即：从根节点到红色节点的路径构成的字符串均在集合中接下来我们一起来实现对 Trie 的一些常用操作方法：1.定义类 Trieclass Trie {private: bool isEnd; vector<Trie> children = vector<Trie>(26);//字母映射表public: //方法将在下文实现…};12345672.插入描述：向 Trie 中插入一个单词 word实现：这个操作和构建链表很像。首先从根结点的子结点开始与 word 第一个字符进行匹配，一直匹配到前缀链上没有对应的字符，这时开始不断开辟新的结点，直到插入完 word 的最后一个字符，同时还要将最后一个结点isEnd = true;，表示它是一个单词的末尾。void insert(string word) { Trie* node = this; for (char c : word) { if (node->children[c-‘a’] == nullptr) { node->children[c-‘a’] = new Trie(); } node = node->children[c-‘a’]; } node->isEnd = true;}123456789103.查找描述：查找 Trie 中是否存在单词 word实现：从根结点的子结点开始，一直向下匹配即可，如果出现结点值为空就返回 false，如果匹配到了最后一个字符，那我们只需判断 node->isEnd 即可。bool search(string word) { Trie* node = this; for (char c : word) { node = node->children[c - ‘a’]; if (node == nullptr) { return false; } } return node->isEnd;}123456789104.前缀匹配描述：判断 Trie 中是或有以 prefix 为前缀的单词实现：和 search 操作类似，只是不需要判断最后一个字符结点的isEnd，因为既然能匹配到最后一个字符，那后面一定有单词是以它为前缀的。bool startsWith(string prefix) { Trie* node = this; for (char c : prefix) { node = node->children[c-‘a’]; if (node == nullptr) { return false; } } return true;}12345678910总结：通过以上介绍和代码实现我们可以总结出 Trie 的几点性质：1.Trie 的形状和单词的插入或删除顺序无关，也就是说对于任意给定的一组单词，Trie 的形状都是唯一的。2.查找或插入一个长度为 L 的单词，访问 children 数组的次数最多为 L + 1 L+1L+1，和 Trie 中包含多少个单词无关。3.Trie 的每个结点中都保留着一个字母表，这是很耗费空间的。如果 Trie 的高度为 n nn，字母表的大小为 m mm，最坏的情况是 Trie 中还不存在前缀相同的单词，那空间复杂度就为 O ( m n ) O(m^n)O(m n )最后，关于 Trie 的应用场景，希望你能记住 8 个字：一次建树，多次查询。(慢慢领悟叭~~)
——————————————
|