{"id":6886,"date":"2020-06-06T22:51:23","date_gmt":"2020-06-07T05:51:23","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6886"},"modified":"2020-06-06T22:51:56","modified_gmt":"2020-06-07T05:51:56","slug":"leetcode-1472-design-browser-history","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/desgin\/leetcode-1472-design-browser-history\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1472. Design Browser History"},"content":{"rendered":"\n<p>You have a&nbsp;<strong>browser<\/strong>&nbsp;of one tab where you start on the&nbsp;<code>homepage<\/code>&nbsp;and you can visit another&nbsp;<code>url<\/code>, get back in the history number of&nbsp;<code>steps<\/code>&nbsp;or move forward in the history number of&nbsp;<code>steps<\/code>.<\/p>\n\n\n\n<p>Implement the&nbsp;<code>BrowserHistory<\/code>&nbsp;class:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>BrowserHistory(string homepage)<\/code>&nbsp;Initializes the object with the&nbsp;<code>homepage<\/code>&nbsp;of the browser.<\/li><li><code>void visit(string url)<\/code>&nbsp;visits&nbsp;<code>url<\/code>&nbsp;from the current page. It clears up all the forward history.<\/li><li><code>string back(int steps)<\/code>&nbsp;Move&nbsp;<code>steps<\/code>&nbsp;back in history. If you can only return&nbsp;<code>x<\/code>&nbsp;steps in the history and&nbsp;<code>steps &gt; x<\/code>, you will&nbsp;return only&nbsp;<code>x<\/code>&nbsp;steps. Return the current&nbsp;<code>url<\/code>&nbsp;after moving back in history&nbsp;<strong>at most<\/strong>&nbsp;<code>steps<\/code>.<\/li><li><code>string forward(int steps)<\/code>&nbsp;Move&nbsp;<code>steps<\/code>&nbsp;forward in history. If you can only forward&nbsp;<code>x<\/code>&nbsp;steps in the history and&nbsp;<code>steps &gt; x<\/code>, you will&nbsp;forward only&nbsp;<code>x<\/code>&nbsp;steps. Return the current&nbsp;<code>url<\/code>&nbsp;after forwarding in history&nbsp;<strong>at most<\/strong>&nbsp;<code>steps<\/code>.<\/li><\/ul>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong>\n[\"BrowserHistory\",\"visit\",\"visit\",\"visit\",\"back\",\"back\",\"forward\",\"visit\",\"forward\",\"back\",\"back\"]\n[[\"leetcode.com\"],[\"google.com\"],[\"facebook.com\"],[\"youtube.com\"],[1],[1],[1],[\"linkedin.com\"],[2],[2],[7]]\n<strong>Output:<\/strong>\n[null,null,null,null,\"facebook.com\",\"google.com\",\"facebook.com\",null,\"linkedin.com\",\"google.com\",\"leetcode.com\"]\n<p><strong>Explanation:<\/strong>\nBrowserHistory browserHistory = new BrowserHistory(\"leetcode.com\");\nbrowserHistory.visit(\"google.com\");       \/\/ You are in \"leetcode.com\". Visit \"google.com\"\nbrowserHistory.visit(\"facebook.com\");     \/\/ You are in \"google.com\". Visit \"facebook.com\"\nbrowserHistory.visit(\"youtube.com\");      \/\/ You are in \"facebook.com\". Visit \"youtube.com\"\nbrowserHistory.back(1);                   \/\/ You are in \"youtube.com\", move back to \"facebook.com\" return \"facebook.com\"\nbrowserHistory.back(1);                   \/\/ You are in \"facebook.com\", move back to \"google.com\" return \"google.com\"\nbrowserHistory.forward(1);                \/\/ You are in \"google.com\", move forward to \"facebook.com\" return \"facebook.com\"\nbrowserHistory.visit(\"linkedin.com\");     \/\/ You are in \"facebook.com\". Visit \"linkedin.com\"\nbrowserHistory.forward(2);                \/\/ You are in \"linkedin.com\", you cannot move forward any steps.\nbrowserHistory.back(2);                   \/\/ You are in \"linkedin.com\", move back two steps to \"facebook.com\" then to \"google.com\". return \"google.com\"\nbrowserHistory.back(7);                   \/\/ You are in \"google.com\", you can move back only one step to \"leetcode.com\". return \"leetcode.com\"\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= homepage.length &lt;= 20<\/code><\/li><li><code>1 &lt;= url.length &lt;= 20<\/code><\/li><li><code>1 &lt;= steps &lt;= 100<\/code><\/li><li><code>homepage<\/code>&nbsp;and&nbsp;<code>url<\/code>&nbsp;consist of&nbsp; &#8216;.&#8217; or lower case English letters.<\/li><li>At most&nbsp;<code>5000<\/code>&nbsp;calls will be made to&nbsp;<code>visit<\/code>,&nbsp;<code>back<\/code>, and&nbsp;<code>forward<\/code>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Vector<\/strong><\/h2>\n\n\n\n<p>Time complexity: <br>visit: Amortized O(1)<br>back: O(1)<br>forward: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass BrowserHistory {\npublic:\n  BrowserHistory(string homepage) : \n    index_(0) {\n    urls_.push_back(std::move(homepage));    \n  }\n\n  void visit(string url) {\n    while (urls_.size() > index_ + 1)\n      urls_.pop_back();\n    ++index_;\n    urls_.push_back(std::move(url));\n  }\n\n  string back(int steps) {    \n    index_ = max(index_ - steps, 0);\n    return urls_[index_];\n  }\n\n  string forward(int steps) {\n    index_ = min(index_ + steps, static_cast<int>(urls_.size()) - 1);  \n    return urls_[index_];\n  }\nprivate:\n  int index_;\n  vector<string> urls_;\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You have a&nbsp;browser&nbsp;of one tab where you start on the&nbsp;homepage&nbsp;and you can visit another&nbsp;url, get back in the history number of&nbsp;steps&nbsp;or move forward in the&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[340],"tags":[20,251,179],"class_list":["post-6886","post","type-post","status-publish","format-standard","hentry","category-desgin","tag-array","tag-design","tag-simulation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6886","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6886"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6886\/revisions"}],"predecessor-version":[{"id":6888,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6886\/revisions\/6888"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6886"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6886"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6886"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}