文章目录

• 前言
• 💎一、题目一
• • 🏆1.题目描述
  • 🏆2.解题思路
  • 🏆3.代码详解
• 💎二、题目二
• • 🏆1.题目描述
  • 🏆2.解题思路
  • 🏆3.代码详解
• 💎三、星球推荐

前言

        初次使用 C++ 解题也是初次接触学习，如下面的第一题使用 C 语言一直出内存错误，换了 C++ 思路相同，直接过了。当时状态就很蒙蔽。用了 C++ 是真香。
刷题坚持每一天，以下题目引用自：力扣（LeetCode）

💎一、题目一

🏆1.题目描述

原题链接：1472. 设计浏览器历史记录

        你有一个只支持单个标签页的 浏览器 ，最开始你浏览的网页是 homepage ，你可以访问其他的网站 url ，也可以在浏览历史中后退 steps 步或前进 steps 步。
        请你实现 BrowserHistory 类：
        BrowserHistory(string homepage) ，用 homepage 初始化浏览器类。
        void visit(string url) 从当前页跳转访问 url 对应的页面 。执行此操作会把浏览历史前进的记录全部删除。
        string back(int steps) 在浏览历史中后退 steps 步。如果你只能在浏览历史中后退至多 x 步且 steps > x ，那么你只后退 x 步。请返回后退 至多 steps 步以后的 url 。
        string forward(int steps) 在浏览历史中前进 steps 步。如果你只能在浏览历史中前进至多 x 步且 steps > x ，那么你只前进 x 步。请返回前进 至多 steps步以后的 url 。

示例 1：
输入：
[“BrowserHistory”,“visit”,“visit”,“visit”,“back”,“back”,“forward”,“visit”,“forward”,“back”,“back”]
[[“leetcode.com”],[“google.com”],[“facebook.com”],[“youtube.com”],[1],[1],[1],[“linkedin.com”],[2],[2],[7]]
输出：
[null,null,null,null,“facebook.com”,“google.com”,“facebook.com”,null,“linkedin.com”,“google.com”,“leetcode.com”]
解释：
BrowserHistory browserHistory = new BrowserHistory(“leetcode.com”);
browserHistory.visit(“google.com”); // 你原本在浏览 “leetcode.com” 。访问 “google.com”
browserHistory.visit(“facebook.com”); // 你原本在浏览 “google.com” 。访问 “facebook.com”
browserHistory.visit(“youtube.com”); // 你原本在浏览 “facebook.com” 。访问 “youtube.com”
browserHistory.back(1); // 你原本在浏览 “youtube.com” ，后退到 “facebook.com” 并返回 “facebook.com”
browserHistory.back(1); // 你原本在浏览 “facebook.com” ，后退到 “google.com” 并返回 “google.com”
browserHistory.forward(1); // 你原本在浏览 “google.com” ，前进到 “facebook.com” 并返回 “facebook.com”
browserHistory.visit(“linkedin.com”); // 你原本在浏览 “facebook.com” 。 访问 “linkedin.com”
browserHistory.forward(2); // 你原本在浏览 “linkedin.com” ，你无法前进任何步数。
browserHistory.back(2); // 你原本在浏览 “linkedin.com” ，后退两步依次先到 “facebook.com” ，然后到 “google.com” ，并返回 “google.com”
browserHistory.back(7); // 你原本在浏览 “google.com”， 你只能后退一步到 “leetcode.com” ，并返回 “leetcode.com”

🏆2.解题思路

🔑思路：

​         这道题考的就是链表的向前向后遍历，插入，释放。仔细阅读题目会发现，也能理解。
        当调用visit函数时首先要判断是不是在表尾，在表尾则插入新节点，否则把当前节点之前的节点都要释放销毁，这就是把前进的历史纪录删除。
        其余两个back和forward则是向前前后遍历几个节点。

🏆3.代码详解

struct browser{    string val;    browser* prev;    browser* next;};class BrowserHistory {public:    browser *obj, *node;    BrowserHistory(string homepage) { node = new browser(); node->prev = nullptr; node->next = nullptr; node->val = homepage; obj = node;    } void visit(string url) { if(obj->next != nullptr){     browser* nowh = obj->next;     obj->next = nullptr;     while(nowh->next){  browser* fr;  fr = nowh;  nowh = nowh->next;  delete fr;     } delete nowh; } browser *lis = new browser(); lis->next = nullptr; lis->prev = obj; obj->next = lis; lis->val = url; obj = lis;    } string back(int steps) { while(steps && obj->prev ){     obj = obj->prev;     --steps; } return obj->val;    } string forward(int steps) { while(steps && obj->next ){     obj = obj->next;     --steps; } return obj->val;    }};

💎二、题目二

🏆1.题目描述

原题链接：430. 扁平化多级双向链表

        你会得到一个双链表，其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表，也包含这些特殊的节点。这些子列表可以有一个或多个自己的子列表，以此类推，以生成如下面的示例所示的 多层数据结构 。
        给定链表的头节点 head ，将链表 扁平化 ，以便所有节点都出现在单层双链表中。让 curr 是一个带有子列表的节点。子列表中的节点应该出现在扁平化列表中的 curr 之后 和 curr.next 之前 。
        返回 扁平列表的 head 。列表中的节点必须将其 所有 子指针设置为 null 。

示例 1：

输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：输入的多级列表如上图所示。
扁平化后的链表如下图：

🏆2.解题思路

🔑思路：

​         深度优先搜索，每次到最深处返回最深处的节点地址，然后和上一层的节点进行链接。循环到链表最后一个节点。

🏆3.代码详解

class Solution {public:    Node* dfs(Node* head) { Node* newhe = head, *back; while(newhe){     Node*son, *later = newhe->next;     if(newhe->child){  son = dfs(newhe->child);  newhe->child->prev = newhe;  newhe->next = newhe->child;  newhe->child = nullptr;  if(later){      son->next = later;      later->prev = son;  }     }     back = newhe;     newhe = newhe->next; } return back;    }    Node* flatten(Node* head) { if(head == nullptr) return nullptr; dfs(head); return head;    }};

💎三、星球推荐

        星球链接：英雄算法联盟

星球里有什么?
        【朋友圈】一个极致精准的自律、编程、算法的小圈子。
        【算法集训】以月为单位组织算法集训，每天四题，风雨无阻。
        【排行榜】每天、每周都会有榜单，激励大家不断进步，不断成长。
        【个人规划】每个人都写好自己的规划，也可以查看他人的规划，时刻警醒自己不掉队。
        【打卡挑战】每日一题打卡、每日早起打卡、算法集训打卡、规划完成情况打卡。
在星球里做什么?
        目前星球人数达到410+，在星球里你能够遇到一群志同道合之人，因为都是花钱进来的，你不会看到任何浑水摸鱼的人，每个人都有自己的每月规划，星主每月都会组织算法集训，每天一起刷题，你可以看到别人的解题报告，取其之长，补己之短。