yoruru的努力日記

1472. Design Browser History

You have a browser of one tab where you start on the homepage and you can visit another url, get back in the history number of steps or move forward in the history number of steps.

Implement the BrowserHistory class:

• BrowserHistory(string homepage) Initializes the object with the homepage of the browser.
• void visit(string url) Visits url from the current page. It clears up all the forward history.
• string back(int steps) Move steps back in history. If you can only return x steps in the history and steps > x, you will return only x steps. Return the current url after moving back in history at most steps.
• string forward(int steps) Move steps forward in history. If you can only forward x steps in the history and steps > x, you will forward only x steps. Return the current url after forwarding in history at most steps.

 

Example:

Input:
["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]]
Output:
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

Explanation:
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // You are in "leetcode.com". Visit "google.com"
browserHistory.visit("facebook.com");     // You are in "google.com". Visit "facebook.com"
browserHistory.visit("youtube.com");      // You are in "facebook.com". Visit "youtube.com"
browserHistory.back(1);                   // You are in "youtube.com", move back to "facebook.com" return "facebook.com"
browserHistory.back(1);                   // You are in "facebook.com", move back to "google.com" return "google.com"
browserHistory.forward(1);                // You are in "google.com", move forward to "facebook.com" return "facebook.com"
browserHistory.visit("linkedin.com");     // You are in "facebook.com". Visit "linkedin.com"
browserHistory.forward(2);                // You are in "linkedin.com", you cannot move forward any steps.
browserHistory.back(2);                   // You are in "linkedin.com", move back two steps to "facebook.com" then to "google.com". return "google.com"
browserHistory.back(7);                   // You are in "google.com", you can move back only one step to "leetcode.com". return "leetcode.com"

 

Constraints:

• 1 <= homepage.length <= 20
• 1 <= url.length <= 20
• 1 <= steps <= 100
• homepage and url consist of  '.' or lower case English letters.
• At most 5000 calls will be made to visit, back, and forward.

---

SOL：

這一題的困難點有兩個，一是要先讀懂題目是要做一個瀏覽紀錄，二是因為要可以back, and forward ，所以不能只用 stack + top來解決問題。

stack除了網址資料 char **urls; 之外裡面會存有三個index的紀錄：

1. 目前所在的頁面： int current;

2. stack中儲存的歷史紀錄：int count; 在 visit 時才會有改變，並且 visit新頁面 時會清除新頁面之後的所有頁面。

3. 整個stack可儲存的容量：int capacity; 若存滿了會增加一倍的容量 (realloc)。但因為題目有講，At most 5000 calls will be made to visit, back, and forward. 所以也可以直接設成5001即可。

typedef struct {
    char** urls;  // 存储URL的数组
    int count;    // 记录当前URL的数量
    int capacity; // 存储URL的数组的容量
    int current;  // 当前浏览的URL的索引
} BrowserHistory;

BrowserHistory* browserHistoryCreate(char* homepage) {
    BrowserHistory* history = (BrowserHistory*) malloc(sizeof(BrowserHistory));
    history->urls = (char**) malloc(sizeof(char*) * 1001); // 初始化为1001
    history->count = 1;
    history->capacity = 1001;
    history->current = 0;
    history->urls[0] = strdup(homepage); // 复制主页URL
    return history;
}

void browserHistoryVisit(BrowserHistory* obj, char* url) {
    obj->current++; // 将当前URL索引增加
    // 如果当前URL索引已经超出了记录数，说明需要增加数组大小
    if (obj->current == obj->count) {
        obj->count++;
        // 如果数组已经满了，需要增加数组大小
        if (obj->count > obj->capacity) {
            obj->capacity *= 2;
            obj->urls = (char**) realloc(obj->urls, sizeof(char*) * obj->capacity);
        }
    }
    // 复制新的URL
    obj->urls[obj->current] = strdup(url);
    // 释放前一个URL后面的URL
    for (int i = obj->current + 1; i < obj->count; i++) {
        free(obj->urls[i]);
    }
    obj->count = obj->current + 1;
}

char* browserHistoryBack(BrowserHistory* obj, int steps) {
    obj->current = obj->current - steps;
    if (obj->current < 0) {
        obj->current = 0;
    }
    return obj->urls[obj->current];
}

char* browserHistoryForward(BrowserHistory* obj, int steps) {
    obj->current = obj->current + steps;
    if (obj->current >= obj->count) {
        obj->current = obj->count - 1;
    }
    return obj->urls[obj->current];
}

void browserHistoryFree(BrowserHistory* obj) {
    // 释放所有的URL
    for (int i = 0; i < obj->count; i++) {
        free(obj->urls[i]);
    }
    free(obj->urls);
    free(obj);
}

另外這兩天chatgpt很不穩，常常error。原本給的第一版答案run之後有bug，但我也沒想幫它debug，所以直接重生成一版，就是上面那一版正確答案啦。兩版比較之後，我覺得舊版的問題應該是出在於沒有current(top)這個index，所以topsize一個人要負擔current+count兩個角色會容易有取值out of index。