Tag Archives: 设计

LeetCode Design Underground System

1396. Design Underground System

Implement the class UndergroundSystem that supports three methods:

1. checkIn(int id, string stationName, int t)

  • A customer with id card equal to id, gets in the station stationName at time t.
  • A customer can only be checked into one place at a time.

2. checkOut(int id, string stationName, int t)

  • A customer with id card equal to id, gets out from the station stationName at time t.

3. getAverageTime(string startStation, string endStation) 

  • Returns the average time to travel between the startStation and the endStation.
  • The average time is computed from all the previous traveling from startStation to endStation that happened directly.
  • Call to getAverageTime is always valid.

You can assume all calls to checkIn and checkOut methods are consistent. That is, if a customer gets in at time t1 at some station, then it gets out at time t2 with t2 > t1. All events happen in chronological order.

Example 1:

Input
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]

Output
[null,null,null,null,null,null,null,14.0,11.0,null,11.0,null,12.0]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15);
undergroundSystem.checkOut(27, "Waterloo", 20);
undergroundSystem.checkOut(32, "Cambridge", 22);
undergroundSystem.getAverageTime("Paradise", "Cambridge");       // return 14.0. There was only one travel from "Paradise" (at time 8) to "Cambridge" (at time 22)
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.0. There were two travels from "Leyton" to "Waterloo", a customer with id=45 from time=3 to time=15 and a customer with id=27 from time=10 to time=20. So the average time is ( (15-3) + (20-10) ) / 2 = 11.0
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.0
undergroundSystem.checkOut(10, "Waterloo", 38);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 12.0

Constraints:

  • There will be at most 20000 operations.
  • 1 <= id, t <= 10^6
  • All strings consist of uppercase, lowercase English letters and digits.
  • 1 <= stationName.length <= 10
  • Answers within 10^-5 of the actual value will be accepted as correct.

设计一个地铁记录系统。完整代码如下,使用system记录每条线路的用时和乘坐次数,使用starts记录每个人旅行起点。不用记录终点,因为checkout的时候,把起点取出计算用时即可。

class UndergroundSystem {
private:
	map<string, map<string, pair<int, int>>> system_; // start->end, total time, #travels
	map<int, pair<string, int>> starts_; // travel start station
public:
	UndergroundSystem() {

	}

	void checkIn(int id, string stationName, int t) {
		starts_[id] = make_pair(stationName, t);
	}

	void checkOut(int id, string stationName, int t) {
		string start_station = starts_[id].first;
		int start_time = starts_[id].second;
		starts_.erase(id);
		if (system_.find(start_station) == system_.end()
			|| system_[start_station].find(stationName) == system_[start_station].end()) {
			system_[start_station][stationName] = make_pair(0, 0);
		}
		system_[start_station][stationName].first += (t - start_time);
		system_[start_station][stationName].second += 1;
	}

	double getAverageTime(string startStation, string endStation) {
		return system_[startStation][endStation].first / double(system_[startStation][endStation].second);
	}
};

本代码提交AC,用时744MS。

LeetCode Design a Stack With Increment Operation

1381. Design a Stack With Increment Operation

Design a stack which supports the following operations.

Implement the CustomStack class:

  • CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack or do nothing if the stack reached the maxSize.
  • void push(int x) Adds x to the top of the stack if the stack hasn’t reached the maxSize.
  • int pop() Pops and returns the top of stack or -1 if the stack is empty.
  • void inc(int k, int val) Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, just increment all the elements in the stack.

Example 1:

Input
["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
Output
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
Explanation
CustomStack customStack = new CustomStack(3); // Stack is Empty []
customStack.push(1);                          // stack becomes [1]
customStack.push(2);                          // stack becomes [1, 2]
customStack.pop();                            // return 2 --> Return top of the stack 2, stack becomes [1]
customStack.push(2);                          // stack becomes [1, 2]
customStack.push(3);                          // stack becomes [1, 2, 3]
customStack.push(4);                          // stack still [1, 2, 3], Don't add another elements as size is 4
customStack.increment(5, 100);                // stack becomes [101, 102, 103]
customStack.increment(2, 100);                // stack becomes [201, 202, 103]
customStack.pop();                            // return 103 --> Return top of the stack 103, stack becomes [201, 202]
customStack.pop();                            // return 202 --> Return top of the stack 102, stack becomes [201]
customStack.pop();                            // return 201 --> Return top of the stack 101, stack becomes []
customStack.pop();                            // return -1 --> Stack is empty return -1.

Constraints:

  • 1 <= maxSize <= 1000
  • 1 <= x <= 1000
  • 1 <= k <= 1000
  • 0 <= val <= 100
  • At most 1000 calls will be made to each method of incrementpush and pop each separately.

设计一个栈Stack的数据结构,简单题,使用vector模拟。完整代码如下:

class CustomStack {
private:
	vector<int> container;
	int msz;
public:
	CustomStack(int maxSize) {
		msz = maxSize;
	}

	void push(int x) {
		if (container.size() < msz) {
			container.push_back(x);
		}
	}

	int pop() {
		if (container.size() > 0) {
			int val = container[container.size() - 1];
			container.pop_back();
			return val;
		}
		else {
			return -1;
		}
	}

	void increment(int k, int val) {
		for (int i = 0; i < k&&i < container.size(); ++i) {
			container[i] += val;
		}
	}
};

本代码提交AC,用时40MS。

LeetCode Design Twitter

LeetCode Design Twitter

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user’s news feed. Your design should support the following methods:
  1. postTweet(userId, tweetId): Compose a new tweet.
  2. getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user’s news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
  3. follow(followerId, followeeId): Follower follows a followee.
  4. unfollow(followerId, followeeId): Follower unfollows a followee.
Example:
Twitter twitter = new Twitter();
// User 1 posts a new tweet (id = 5).
twitter.postTweet(1, 5);
// User 1's news feed should return a list with 1 tweet id -> [5].
twitter.getNewsFeed(1);
// User 1 follows user 2.
twitter.follow(1, 2);
// User 2 posts a new tweet (id = 6).
twitter.postTweet(2, 6);
// User 1's news feed should return a list with 2 tweet ids -> [6, 5].
// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.getNewsFeed(1);
// User 1 unfollows user 2.
twitter.unfollow(1, 2);
// User 1's news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.
twitter.getNewsFeed(1);

设计一个Twitter系统,实现三个接口,postTweet发文,follow某人,unfollow某人,getNewsFeed从自己以及follow的人中取出最近发表的三篇推文,按时间从近到远排序。比较麻烦的是getNewsFeed函数的实现。 先来个暴力版本,用unordered_map<int, unordered_set<int>>保存某个人follow的所有人,这样follow和unfollow的操作都可以在O(1)实现。 用vector<Tweet>保存所有推文,而且是最新postTweet的推文都push_back到末尾,所以该容器保存了全局从远到近的所有推文。那么getNewsFeed时,直接从容器末尾往前遍历所有推文,判断该推文是否是自己或者自己follow的用户发表的,如果是,则收集起来,直到收集到10篇推文。 思路和实现都非常简单,代码如下: [cpp] class Twitter { private: struct Tweet { int userId; int tweetId; Tweet(int u, int t) :userId(u), tweetId(t) {}; }; vector<Tweet> Tweets; unordered_map<int, unordered_set<int>> following; public: /** Initialize your data structure here. */ Twitter() { } /** Compose a new tweet. */ void postTweet(int userId, int tweetId) { Tweets.push_back({ userId,tweetId }); } /** Retrieve the 10 most recent tweet ids in the user’s news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */ vector<int> getNewsFeed(int userId) { vector<int> ans; for (int i = Tweets.size() – 1; i >= 0; –i) { int &uid = Tweets[i].userId; if (uid == userId || following[userId].find(uid) != following[userId].end()) { ans.push_back(Tweets[i].tweetId); if (ans.size() == 10)break; } } return ans; } /** Follower follows a followee. If the operation is invalid, it should be a no-op. */ void follow(int followerId, int followeeId) { following[followerId].insert(followeeId); } /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */ void unfollow(int followerId, int followeeId) { following[followerId].erase(followeeId); } }; [/cpp] 本代码提交AC,用时143MS。 上面的版本比较慢,主要是每次getNewsFeed时都要遍历全局所有的推文。讨论区有一种做法是把每个人发表的推文也保存到一个unordered_map<int, vector<Tweet>>中,那么在getNewsFeed时,只需要拿出自己或自己follow的用户发表的推文,放到一个优先队列中,优先队列自动按时间先后顺序排序了,从优先队列中取出10条推文即可。 为了按时间排序,需要一个全局时间戳,并且重载优先队列的比较运算符。 代码如下: [cpp] class Twitter { private: int timestamp; struct Tweet { int tweetId; int timestamp; Tweet(int tid, int ts) :tweetId(tid), timestamp(ts) {}; bool operator<(const Tweet& t)const { return timestamp < t.timestamp; } }; unordered_map<int, vector<Tweet>> Tweets; unordered_map<int, unordered_set<int>> following; public: /** Initialize your data structure here. */ Twitter() :timestamp(0) { } /** Compose a new tweet. */ void postTweet(int userId, int tweetId) { Tweets[userId].push_back({ tweetId,timestamp++ }); } /** Retrieve the 10 most recent tweet ids in the user’s news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */ vector<int> getNewsFeed(int userId) { priority_queue<Tweet> pq; for (const auto& uid : following[userId]) { for (const auto& t : Tweets[uid]) { pq.push(t); } } for (const auto& t : Tweets[userId]) { pq.push(t); } vector<int> ans; while (!pq.empty() && ans.size() < 10) { ans.push_back(pq.top().tweetId); pq.pop(); } return ans; } /** Follower follows a followee. If the operation is invalid, it should be a no-op. */ void follow(int followerId, int followeeId) { if (followerId != followeeId)following[followerId].insert(followeeId); // map中不考虑自己follow自己,因为getNewsFeed单独考虑了 } /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */ void unfollow(int followerId, int followeeId) { following[followerId].erase(followeeId); } }; [/cpp] 本代码提交AC,用时33MS,快了好几倍!]]>

LeetCode Design Excel Sum Formula

LeetCode Design Excel Sum Formula Your task is to design the basic function of Excel and implement the function of sum formula. Specifically, you need to implement the following functions: Excel(int H, char W): This is the constructor. The inputs represents the height and width of the Excel form. H is a positive integer, range from 1 to 26. It represents the height. W is a character range from ‘A’ to ‘Z’. It represents that the width is the number of characters from ‘A’ to W. The Excel form content is represented by a height * width 2D integer array C, it should be initialized to zero. You should assume that the first row of C starts from 1, and the first column of C starts from ‘A’.   void Set(int row, char column, int val): Change the value at C(row, column) to be val.   int Get(int row, char column): Return the value at C(row, column).   int Sum(int row, char column, List of Strings : numbers): This function calculate and set the value at C(row, column), where the value should be the sum of cells represented by numbers. This function return the sum result at C(row, column). This sum formula should exist until this cell is overlapped by another value or another sum formula. numbers is a list of strings that each string represent a cell or a range of cells. If the string represent a single cell, then it has the following format : ColRow. For example, “F7” represents the cell at (7, F). If the string represent a range of cells, then it has the following format : ColRow1:ColRow2. The range will always be a rectangle, and ColRow1 represent the position of the top-left cell, and ColRow2 represents the position of the bottom-right cell.   Example 1:

Excel(3,"C");
// construct a 3*3 2D array with all zero.
//   A B C
// 1 0 0 0
// 2 0 0 0
// 3 0 0 0
Set(1, "A", 2);
// set C(1,"A") to be 2.
//   A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 0
Sum(3, "C", ["A1", "A1:B2"]);
// set C(3,"C") to be the sum of value at C(1,"A") and the values sum of the rectangle range whose top-left cell is C(1,"A") and bottom-right cell is C(2,"B"). Return 4.
//   A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 4
Set(2, "B", 2);
// set C(2,"B") to be 2. Note C(3, "C") should also be changed.
//   A B C
// 1 2 0 0
// 2 0 2 0
// 3 0 0 6
Note:
  1. You could assume that there won’t be any circular sum reference. For example, A1 = sum(B1) and B1 = sum(A1).
  2. The test cases are using double-quotes to represent a character.
  3. Please remember to RESET your class variables declared in class Excel, as static/class variables are persisted across multiple test cases. Please see here for more details.

本题要求设计一个简单的Excel表格求和功能。主要实现三个接口:
  • Get(int row, char column),获取坐标为(row,column)的cell的值
  • Set(int row, char column, int val),把坐标为(row,column)的值设置为val
  • Sum(int row, char column, List of Strings : numbers),numbers表示一系列求和公式,把公式计算结果填入坐标(row,column)中,并且当公式中的格子更新时,该公式计算出来的值也要更新。
本题的难点是,如果C3=A1+B2,如果更新了B2,下次get(C3)时,得到的结果也必须是用更新过的B2的值。而且还有可能A1的值也是用某个公式计算出来的。 当时比赛的时候,有一些思路,但是逻辑不是很清晰,后来参考这个题解,逻辑很清楚。 Excel包含两个成员,二维矩阵matrix表示一个excel表格,hashmap formula的key为某个格子,value为该格子对应的求和公式。如果某个格子的值是实实在在的值,不是用公式计算出来的,则不在这个hashmap中。
  • 对于get,如果坐标不在formula中,说明该格子是实实在在的值,直接返回matrix中的值。否则需要从formula中取出求和公式进行计算。
  • 对于set,直接把matrix对应坐标设置为value就好,注意的是,因为set之后就变成了实实在在的值,所以要清空formula中该格子的公式(如果有的话)。
  • 对于sum,计算字符串公式的值,把结果填入对应的格子,然后在formula中设置该格子的公式。
问题的难点是怎样对一个公式求值。说穿了其实就是不停的递归调用get函数,因为get函数如果该cell没有在formula中,则返回实实在在的值,否则递归计算formula的值。想象一下,就是不停的对一个坐标递归求值,直到不能递归时,返回matrix中的值,然后递归累加起来。想明白了其实很简单,代码注意把公共的计算部分抽象出来。 完整代码如下: [cpp] class Excel { private: vector<vector<int>> matrix; unordered_map<int, vector<string>> formula; // 把坐标hash成一个int int id(int r, char c) { return r * 27 + c – ‘A’ + 1; } void parse(string& s, int& r, char& c) { c = s[0]; r = stoi(s.substr(1)); } int get_cell(string& s) { int r; char c; parse(s, r, c); return get(r, c); } int get_range(string& s) { size_t pos = s.find(‘:’); string s1 = s.substr(0, pos), s2 = s.substr(pos + 1); int r1, r2; char c1, c2; parse(s1, r1, c1); parse(s2, r2, c2); int ans = 0; for (int i = r1; i <= r2; ++i) { for (char c = c1; c <= c2; ++c) { ans += get(i, c); } } return ans; } int get_cells(vector<string>& strs) { int ans = 0; for (auto& s : strs) { if (s.find(‘:’) == string::npos) ans += get_cell(s); else ans += get_range(s); } return ans; } public: Excel(int H, char W) { matrix.clear(); formula.clear(); for (int i = 0; i <= H; ++i) { matrix.push_back(vector<int>(W – ‘A’ + 1, 0)); } } void set(int r, char c, int v) { matrix[r][c - 'A'] = v; formula.erase(id(r, c)); // caution } int get(int r, char c) { if (formula.find(id(r, c)) == formula.end())return matrix[r][c - 'A']; return get_cells(formula[id(r, c)]); } int sum(int r, char c, vector<string> strs) { int ans = get_cells(strs); matrix[r][c - 'A'] = ans; formula[id(r, c)] = strs; return ans; } }; [/cpp] 本代码提交AC,用时6MS。]]>

LeetCode LRU Cache

146. LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

实现一个LUR cache。 我们知道数据的访问都有时间局部性和空间局部性,所以为了加快访问速度,把经常访问的数据放到高速缓存cache中,这样先查cache,不命中再查内存或者外存。 但是cache一般都很小,当新数据需要插入cache时,如果cache满,则需要替换掉cache中旧的元素。此时替换哪个元素就有很多策略了,可以把最久没访问的替换出去,也可以把访问频率最低的替换出去,还可以把最先进入的替换出去等等,各种策略就形成了不同的缓存替换算法。 LRU的意思是Least Recently Used (LRU),即把最近最久没访问的元素替换出去,是指时间上最久没访问的,而不是频率上访问最少的哦。 题目要求实现LRU的两个接口,分别是

  1. get(key),从LRU中获取key对应的value,如果LRU中不存在key,则返回-1
  2. put(key,value),把key和对应的value插入到LRU中,如果LRU满,则要替换掉最近最久没访问的元素

要求这两个操作都在O(1)时间内完成。 我们来分析一下应该用哪些数据结构使这两个操作都在O(1)时间内完成。首先get需要在O(1)时间内判断key是否在LRU中,所以可能需要用hash来存储<key,value>对。其次,需要缓存替换时,要在O(1)时间内把最久没访问的<key,value>删掉,同时插入新的<key,value>,删除和插入能在O(1)时间内完成的就是链表了。

综合上面的分析,我们可以用unordered_map+list来实现LRU,STL的list是一个双向链表。 参考这份代码。我们使用list<int> used来保存当前在LRU中的那些key,注意是key;用unordered_map<int, pair<int, list<int>::iterator>> cache来保存真实的缓存,cache的key就是LRU中现存的key,value是一个pair,保存了key对应的value,以及这个key在链表中的迭代器(指针)。

两个操作的实现如下:

put(key,value)。每当有新<key,value>进入时,如果key已经在cache中,则只需要更新key对应的value,同时,刚访问的元素下次很可能再次访问,所以需要把这个key提到链表的表头(为了不让这个key沉到表尾)。如果key不在cache中,但cache已满,则需要把链表尾部的key对应的数据在cache中删掉,同时也需要在链表中删掉这个尾节点;如果cache不满,则把新key插入到链表表头,同时把<key,value>插入到cache中,且key在链表中的位置是list.begin()。

get(key)。如果key不在cache中,直接返回-1。如果key在cache中,直接从cache中得到对应的value,同时根据迭代器,把key提到链表表头。 根据上述算法描述,我们需要抽象一个函数,moveToHead(list<int>::iterator &it),即把迭代器it指向的那个key移到表头,包括两个操作,把it从it位置删掉,把it的值插到表头。

完整代码如下:

class LRUCache {
private:
    unordered_map<int, pair<int, list<int>::iterator> > cache;
    list<int> used;
    int _capacity; // 把it节点**剪切**到表头
    void moveToHead(list<int>::iterator& it)
    {
        int key = *it;
        used.erase(it);
        used.push_front(key);
        cache[key].second = used.begin();
    }
public:
    LRUCache(int capacity)
        : _capacity(capacity)
    {
    }
    int get(int key)
    {
        if (cache.find(key) == cache.end())
            return -1;
        int value = cache[key].first;
        moveToHead(cache[key].second);
        return value;
    }
    void put(int key, int value)
    {
        if (cache.find(key) != cache.end()) {
            cache[key].first = value;
            moveToHead(cache[key].second);
        }
        else {
            if (used.size() == _capacity) {
                cache.erase(used.back());
                used.pop_back();
            }
            used.push_front(key);
            cache[key] = { value, used.begin() };
        }
    }
};

本代码提交AC,用时96MS。

我们还可以自己实现list,就是一个双向链表。这个双向链表包括头结点head和尾节点tail。为了插入删除的方便,我们设置了一个用不到的head和tail,所以真正的数据其实是在head和tail之间的,如下,节点1~3才是真正的数据节点

头 --> 节 --> 节 --> 节 --> 尾
节     点     点     点     节
点 <-- 1  <-- 2 <-- 3  <-- 点

这里我们抽象出了3个函数,removeFromList和moveToHead完成上一种实现中的moveToHead功能,即先把节点从原链表中删除(相当于摘下来),然后把这个节点安放到表头(上图节点1)。removeTail就是在需要替换时,删除表尾节点(上图节点3)。

完整代码如下:

class LRUCache {
private:
    struct Node {
        int key, value;
        Node *pre, *next;
        Node(int k, int v)
            : key(k)
            , value(v)
            , pre(NULL)
            , next(NULL){};
    };
    unordered_map<int, Node*> cache;
    Node *head, *tail;
    int _capacity; // 从原链表中删除节点node(摘下)
    void removeFromList(Node* node)
    {
        node->pre->next = node->next;
        node->next->pre = node->pre;
    }
    // 把节点node放到“表头”(安放)
    void moveToHead(Node* node)
    {
        node->next = head->next;
        head->next->pre = node;
        node->pre = head;
        head->next = node;
    }
    // 删除“尾节点”
    void removeTail()
    {
        Node* target = tail->pre;
        target->pre->next = target->next;
        target->next->pre = target->pre;
        delete target;
    }

public:
    LRUCache(int capacity)
        : _capacity(capacity)
    {
        head = new Node(0, 0); // 辅助头结点
        tail = new Node(0, 0); // 辅助尾节点
        head->next = tail;
        tail->pre = head;
    }
    int get(int key)
    {
        if (cache.find(key) == cache.end())
            return -1;
        int value = cache[key]->value;
        removeFromList(cache[key]);
        moveToHead(cache[key]);
        return value;
    }
    void put(int key, int value)
    {
        if (cache.find(key) != cache.end()) {
            cache[key]->value = value;
            removeFromList(cache[key]);
            moveToHead(cache[key]);
        }
        else {
            if (cache.size() == _capacity) {
                cache.erase(tail->pre->key);
                removeTail();
            }
            Node* node = new Node(key, value);
            cache[key] = node;
            moveToHead(node);
        }
    }
};

本代码提交AC,用时98MS。

LeetCode Design Compressed String Iterator

LeetCode Design Compressed String Iterator Design and implement a data structure for a compressed string iterator. It should support the following operations: next and hasNext. The given compressed string will be in the form of each letter followed by a positive integer representing the number of this letter existing in the original uncompressed string. next() – if the original string still has uncompressed characters, return the next letter; Otherwise return a white space. hasNext() – Judge whether there is any letter needs to be uncompressed. Note: Please remember to RESET your class variables declared in StringIterator, as static/class variables are persisted across multiple test cases. Please see here for more details. Example:

StringIterator iterator = new StringIterator("L1e2t1C1o1d1e1");
iterator.next(); // return 'L'
iterator.next(); // return 'e'
iterator.next(); // return 'e'
iterator.next(); // return 't'
iterator.next(); // return 'C'
iterator.next(); // return 'o'
iterator.next(); // return 'd'
iterator.hasNext(); // return true
iterator.next(); // return 'e'
iterator.hasNext(); // return false
iterator.next(); // return ' '

本题设计了一种压缩字符串格式,即把多个连续相同字符用单个字符已经频率代替了,比如”L1e2t1C1o1d1e1″展开其实就是”LeetCode”。现在要针对这种压缩字符串,设计一个迭代器,实现next和hasNext函数。 我一开始上暴力,即首先把压缩字符串展开成常规字符串,然后直接下标操作。代码如下: [cpp] class StringIterator { private: string line; int cur, n; public: StringIterator(string compressedString) { line = ""; cur = n = 0; vector<char> letters; vector<int> rep; string digits = ""; for (int i = 0; i < compressedString.size(); ++i) { if (isalpha(compressedString[i])) { letters.push_back(compressedString[i]); if (digits != "") { rep.push_back(atoi(digits.c_str())); digits = ""; } } else digits += string(1, compressedString[i]); } rep.push_back(atoi(digits.c_str())); for (int i = 0; i < letters.size(); ++i) { line += string(rep[i], letters[i]); } n = line.size(); } char next() { if (cur < n)return line[cur++]; else return ‘ ‘; } bool hasNext() { return cur < n; } }; [/cpp] 本代码MLE了。因为有个样例是“a1234567890b1234567890”,我表示无语,如果展开确实会MLE。 其实写上面的代码的时候我就知道可以优化,不对压缩字符串展开,而是表示成(a,1234567890)和(b,1234567890),next的时候只对频率递减。这样只需要存储少量字符以及对应的频率。 代码如下: [cpp] typedef long long ll; class StringIterator { private: int cur, n; vector<char> letters; vector<ll> rep; public: StringIterator(string compressedString) { cur = n = 0; string digits = ""; for (int i = 0; i < compressedString.size(); ++i) { if (isalpha(compressedString[i])) { letters.push_back(compressedString[i]); if (digits != "") { rep.push_back(atoll(digits.c_str())); digits = ""; } } else digits += string(1, compressedString[i]); } rep.push_back(atoi(digits.c_str())); n = letters.size(); } char next() { if (rep[cur] > 0) { char ans = letters[cur]; –rep[cur]; return ans; } else { if (cur == n – 1)return ‘ ‘; else { char ans = letters[++cur]; –rep[cur]; return ans; } } } bool hasNext() { return cur < n – 1 || (cur == n – 1 && rep[cur] > 0); } }; [/cpp] 本代码提交AC,用时13MS。]]>

LeetCode Implement Stack using Queues

225. Implement Stack using Queues

Implement the following operations of a stack using queues.

  • push(x) — Push element x onto stack.
  • pop() — Removes the element on top of the stack.
  • top() — Get the top element.
  • empty() — Return whether the stack is empty.

Example:

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);  
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false

Notes:

  • You must use only standard operations of a queue — which means only push to backpeek/pop from frontsize, and is empty operations are valid.
  • Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
  • You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack). 225. Implement Stack using Queues

LeetCode Implement Queue using Stacks正好相反,本题要用队列实现堆栈的效果。 队列是先进先出的,而堆栈是后进先出。如果用队列q保存数据,则要实现堆栈的pop效果时,需要获取到q的队尾元素,可以不断把q的数据从队首弹出,同时压回队尾,重复n-1次,此时队首元素就是原来的队尾元素了。堆栈的top效果和push的实现方法是类似的。 这种题目就是数据不断的倒腾。。。 完整代码如下:

class MyStack {
private:
    queue<int> m_q;
public: /** Initialize your data structure here. */
    MyStack() {} /** Push element x onto stack. */
    void push(int x) { m_q.push(x); } /** Removes the element on top of the stack and returns that element. */
    int pop()
    {
        int sz = m_q.size();
        for (int i = 0; i < sz – 1; ++i) {
            m_q.push(m_q.front());
            m_q.pop();
        }
        int front = m_q.front();
        m_q.pop();
        return front;
    } /** Get the top element. */
    int top()
    {
        int sz = m_q.size(), front = m_q.front();
        for (int i = 0; i < sz; ++i) {
            front = m_q.front();
            m_q.push(front);
            m_q.pop();
        }
        return front;
    } /** Returns whether the stack is empty. */
    bool empty() { return m_q.empty(); }
};

本代码提交AC,用时3MS。

二刷。用两个queue来模拟stack,不如上面的解法好看:

class MyStack {
private:
	vector<queue<int>> vq_;
	int data_queue_id_;
public:
	/** Initialize your data structure here. */
	MyStack() {
		vq_.push_back(queue<int>());
		vq_.push_back(queue<int>());
		data_queue_id_ = 0;
	}

	/** Push element x onto stack. */
	void push(int x) {
		vq_[data_queue_id_].push(x);
	}

	/** Removes the element on top of the stack and returns that element. */
	int pop() {
		int another_id = 1 - data_queue_id_;
		int last_data = 0;
		while (!vq_[data_queue_id_].empty()) {
			last_data = vq_[data_queue_id_].front();
			vq_[data_queue_id_].pop();
			if (!vq_[data_queue_id_].empty()) {
				vq_[another_id].push(last_data);
			}
		}
		swap(another_id, data_queue_id_);
		return last_data;
	}

	/** Get the top element. */
	int top() {
		int another_id = 1 - data_queue_id_;
		int last_data = 0;
		while (!vq_[data_queue_id_].empty()) {
			last_data = vq_[data_queue_id_].front();
			vq_[data_queue_id_].pop();
			vq_[another_id].push(last_data);
		}
		swap(another_id, data_queue_id_);
		return last_data;
	}

	/** Returns whether the stack is empty. */
	bool empty() {
		return vq_[data_queue_id_].empty();
	}
};

本代码提交AC,用时0MS。

LeetCode Implement Queue using Stacks

232. Implement Queue using Stacks 232. Implement Queue using Stacks

Implement the following operations of a queue using stacks.

  • push(x) — Push element x to the back of queue.
  • pop() — Removes the element from in front of queue.
  • peek() — Get the front element.
  • empty() — Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

Notes:

  • You must use only standard operations of a stack — which means only push to toppeek/pop from topsize, and is empty operations are valid.
  • Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
  • You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue). 232. Implement Queue using Stacks

本题要求用堆栈来实现队列的功能。因为堆栈是后进先出,而队列是先进先出,顺序正好相反。比如进入队列的顺序是1,2,3,但是进到堆栈stk1之后,从栈顶到栈底的顺序就变成了3,2,1,此时如果要实现队列出队的效果,就必须借助另一个堆栈stk2,把stk1的内容压入到stk2,这样从栈顶到栈底的顺序就和队列一样了,是1,2,3。 所以本题借助两个堆栈stk1和stk2,stk1就是常规的数据来了就压栈,当需要实现队列的pop效果时,就借助stk2倒腾一下,如果又要实现队列的push效果时,又要把stk2的数据捣腾回stk1。 总的来说,我们使用懒人规则,每次直到调用某个操作,且当前stk*不能满足要求时,才捣腾stk1和stk2。 完整代码如下:

class MyQueue {
private:
    stack<int> stk1, stk2; // 输入来源1,2,3,stk1从栈底到栈顶的顺序是1,2,3,stk2从栈底到栈顶的顺序是3,2,1
public: /** Initialize your data structure here. */
    MyQueue() {} /** Push element x to the back of queue. */
    void push(int x)
    {
        while (!stk2.empty()) {
            stk1.push(stk2.top());
            stk2.pop();
        }
        stk1.push(x);
    } /** Removes the element from in front of queue and returns that element. */
    int pop()
    {
        while (!stk1.empty()) {
            stk2.push(stk1.top());
            stk1.pop();
        }
        int top = stk2.top();
        stk2.pop();
        return top;
    } /** Get the front element. */
    int peek()
    {
        while (!stk1.empty()) {
            stk2.push(stk1.top());
            stk1.pop();
        }
        return stk2.top();
    } /** Returns whether the queue is empty. */
    bool empty() { return stk1.empty() && stk2.empty(); }
};

本代码提交AC,用时3MS。
二刷。其实push的时候可以不需要把stk2的数据倒腾回stk1,stk2的数据始终是队列头的,stk1的数据始终是队列尾的,代码如下:

class MyQueue {
private:
    stack<int> stk1, stk2;
    void adjust()
    {
        while (!stk1.empty()) {
            stk2.push(stk1.top());
            stk1.pop();
        }
    }
public: /** Initialize your data structure here. */
    MyQueue() {} /** Push element x to the back of queue. */
    void push(int x) { stk1.push(x); } /** Removes the element from in front of queue and returns that element. */
    int pop()
    {
        if (stk2.empty())
            adjust();
        int ans = stk2.top();
        stk2.pop();
        return ans;
    } /** Get the front element. */
    int peek()
    {
        if (stk2.empty())
            adjust();
        int ans = stk2.top();
        return ans;
    } /** Returns whether the queue is empty. */
    bool empty() { return stk1.empty() && stk2.empty(); }
};

本代码提交AC,用时3MS。