Tag Archives: 数据结构

LeetCode Design Search Autocomplete System

LeetCode Design Search Autocomplete System
Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character '#'). For each character they type except '#', you need to return the top 3 historical hot sentences that have prefix the same as the part of sentence already typed. Here are the specific rules:

  1. The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before.
  2. The returned top 3 hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same degree of hot, you need to use ASCII-code order (smaller one appears first).
  3. If less than 3 hot sentences exist, then just return as many as you can.
  4. When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list.

Your job is to implement the following functions:
The constructor function:
AutocompleteSystem(String[] sentences, int[] times): This is the constructor. The input is historical dataSentences is a string array consists of previously typed sentences. Times is the corresponding times a sentence has been typed. Your system should record these historical data.
Now, the user wants to input a new sentence. The following function will provide the next character the user types:
List<String> input(char c): The input c is the next character typed by the user. The character will only be lower-case letters ('a' to 'z'), blank space (' ') or a special character ('#'). Also, the previously typed sentence should be recorded in your system. The output will be the top 3 historical hot sentences that have prefix the same as the part of sentence already typed.
 
Example:
Operation: AutocompleteSystem(["i love you", "island","ironman", "i love leetcode"], [5,3,2,2])
The system have already tracked down the following sentences and their corresponding times:
"i love you" : 5 times
"island" : 3 times
"ironman" : 2 times
"i love leetcode" : 2 times
Now, the user begins another search:
Operation: input('i')
Output: ["i love you", "island","i love leetcode"]
Explanation:
There are four sentences that have prefix "i". Among them, "ironman" and "i love leetcode" have same hot degree. Since ' ' has ASCII code 32 and 'r' has ASCII code 114, "i love leetcode" should be in front of "ironman". Also we only need to output top 3 hot sentences, so "ironman" will be ignored.
Operation: input(' ')
Output: ["i love you","i love leetcode"]
Explanation:
There are only two sentences that have prefix "i ".
Operation: input('a')
Output: []
Explanation:
There are no sentences that have prefix "i a".
Operation: input('#')
Output: []
Explanation:
The user finished the input, the sentence "i a" should be saved as a historical sentence in system. And the following input will be counted as a new search.
 
Note:

  1. The input sentence will always start with a letter and end with '#', and only one blank space will exist between two words.
  2. The number of complete sentences that to be searched won't exceed 100. The length of each sentence including those in the historical data won't exceed 100.
  3. Please use double-quote instead of single-quote when you write test cases even for a character input.
  4. Please remember to RESET your class variables declared in class AutocompleteSystem, as static/class variables are persisted across multiple test cases. Please see herefor more details.

本题要求实现一个搜索引擎的自动补全功能,正好是我想在我的新闻搜索引擎里实现的功能。首先会给出一些历史数据,就是哪些句子被访问了多少次。现在模拟用户输入,每输入一个字符,给出以输入的所有字符为前缀的历史句子,并且只给出被访频率前3的句子作为自动补全的候选。
Trie树的应用题。Trie树的节点属性包含is_sentence_以该字符结尾是否是一个句子,cnt_该句子的频率。首先把历史数据插入到Trie树中,记录好相应的is_sentence_和cnt_。
用一个成员变量cur_sentence_记录当前输入的字符串前缀。查找的时候,用cur_sentence_在Trie树中找,先找到这个前缀,然后在26个字母+一个空格中递归查找所有孩子节点,把能形成句子的字符串及其频率插入到一个优先队列中。该优先队列先以句子频率排序,如果频率相等,再以字典序排列。这样我们直接从优先队列中取出前三个堆顶句子,就是自动补全的候选。
如果遇到#,说明输入结束,把cur_sentence_及其频率1也插入到Trie树中。注意插入之后树中节点的频率是累加的,即第34行。
注意AutocompleteSystem类初始化的时候需要清空cur_sentence_和Trie树,更多的细节请看代码中的caution。

const int N = 26;
class AutocompleteSystem {
private:
	struct Node {
		bool is_sentence_;
		int cnt_;
		vector<Node*> children_;
		Node() :is_sentence_(false), cnt_(0){
			for (int i = 0; i < N + 1; ++i)children_.push_back(NULL);
		}
	};
	Node *root;
	string cur_sentence_;
	struct Candidate {
		int cnt_;
		string sentence_;
		Candidate(int &cnt, string &sentence) :cnt_(cnt), sentence_(sentence) {};
		bool operator<(const Candidate& cand) const {
			return (cnt_ < cand.cnt_) || (cnt_ == cand.cnt_&&sentence_ > cand.sentence_); // caution
		}
	};
	void AddSentence(const string& sentence, const int& time) {
		Node *cur = root;
		for (const auto& c : sentence) {
			int idx = c - 'a';
			if (c == ' ')idx = N;
			if (cur->children_[idx] == NULL)cur->children_[idx] = new Node();
			cur = cur->children_[idx];
		}
		cur->is_sentence_ = true;
		cur->cnt_ += time; // caution
	}
	void FindSentences(Node *root, string &sentence, priority_queue<Candidate>& candidates) {
		if (root != NULL&&root->is_sentence_)candidates.push(Candidate(root->cnt_, sentence));
		if (root == NULL)return;
		for (int i = 0; i < N + 1; ++i) {
			if (root->children_[i] != NULL) {
				if (i == N)
					sentence.push_back(' ');
				else
					sentence.push_back('a' + i);
				FindSentences(root->children_[i], sentence, candidates);
				sentence.pop_back();
			}
		}
	}
	void StartWith(priority_queue<Candidate>& candidates) {
		Node *cur = root;
		for (const auto& c : cur_sentence_) {
			int idx = c - 'a';
			if (c == ' ')idx = N;
			if (cur->children_[idx] == NULL)return;
			cur = cur->children_[idx];
		}
		string sentence = cur_sentence_;
		FindSentences(cur, sentence, candidates);
	}
public:
	AutocompleteSystem(vector<string> sentences, vector<int> times) {
		root = new Node(); // caution
		cur_sentence_ = ""; // caution
		for (int i = 0; i < sentences.size(); ++i)AddSentence(sentences[i], times[i]);
	}
	vector<string> input(char c) {
		if (c == '#') {
			AddSentence(cur_sentence_, 1); // caution
			cur_sentence_ = ""; // caution
			return{};
		}
		else {
			cur_sentence_.push_back(c);
			priority_queue<Candidate> candidates;
			StartWith(candidates);
			if (candidates.empty())return{};
			vector<string> ans;
			while (!candidates.empty()) {
				ans.push_back(candidates.top().sentence_);
				candidates.pop();
				if (ans.size() == 3)break;
			}
			return ans;
		}
	}
};

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

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篇推文。
思路和实现都非常简单,代码如下:

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);
	}
};

本代码提交AC,用时143MS。
上面的版本比较慢,主要是每次getNewsFeed时都要遍历全局所有的推文。讨论区有一种做法是把每个人发表的推文也保存到一个unordered_map<int, vector<Tweet>>中,那么在getNewsFeed时,只需要拿出自己或自己follow的用户发表的推文,放到一个优先队列中,优先队列自动按时间先后顺序排序了,从优先队列中取出10条推文即可。
为了按时间排序,需要一个全局时间戳,并且重载优先队列的比较运算符。
代码如下:

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);
	}
};

本代码提交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中的值,然后递归累加起来。想明白了其实很简单,代码注意把公共的计算部分抽象出来。
完整代码如下:

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] = v;
		formula.erase(id(r, c)); // caution
	}
	int get(int r, char c) {
		if (formula.find(id(r, c)) == formula.end())return matrix[r];
		return get_cells(formula[id(r, c)]);
	}
	int sum(int r, char c, vector<string> strs) {
		int ans = get_cells(strs);
		matrix[r] = ans;
		formula[id(r, c)] = strs;
		return ans;
	}
};

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

LeetCode LRU Cache

LeetCode 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.
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函数。
我一开始上暴力,即首先把压缩字符串展开成常规字符串,然后直接下标操作。代码如下:

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;
	}
};

本代码MLE了。因为有个样例是“a1234567890b1234567890”,我表示无语,如果展开确实会MLE。
其实写上面的代码的时候我就知道可以优化,不对压缩字符串展开,而是表示成(a,1234567890)和(b,1234567890),next的时候只对频率递减。这样只需要存储少量字符以及对应的频率。
代码如下:

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);
	}
};

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

LeetCode Encode and Decode TinyURL

LeetCode Encode and Decode TinyURL

Note: This is a companion problem to the System Design problem: Design TinyURL.

TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.
Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.


实现短网址的功能,即把一个长的网址加密成短网址,并且能够把短网址还原为原来的长网址。
显然要用Hash,有多种方法,参考:https://leetcode.com/articles/encode-and-decode-tinyurl/
直接用一个计数器当key,相当于自己维护了一个长的url池,给每个url编了一个号。加密的时候把号码给他,解密的时候根据编号找到原始的url。代码如下:

class Solution {
private:
	unsigned long long m_ullCnt;
	unordered_map<unsigned long long, string> m_umHash;
public:
	Solution() :m_ullCnt(0) {};
	// Encodes a URL to a shortened URL.
	string encode(string longUrl) {
		m_umHash[m_ullCnt] = longUrl;
		return "http://tinyurl.com/" + to_string(m_ullCnt++);
	}
	// Decodes a shortened URL to its original URL.
	string decode(string shortUrl) {
		int id = atoi(shortUrl.substr(19).c_str());
		return m_umHash[id];
	}
};

本代码提交AC,用时9MS。
既然可以用计数器,也可以生成不重复的随机数作为key,不断random,和上面的解法类似。
还有一种生成key的方法,就是用STL自带的hash函数,把string hash成一个size_t作为key。注意要从短url中还原回hash值时,不能用atoi和atol,因为size_t可能是unsigned int,也可能和平台有关,所以必须用sscanf "%zu"的形式转换成size_t。
代码如下:

class Solution {
private:
	unordered_map<size_t, string> m_umHash;
public:
	// Encodes a URL to a shortened URL.
	string encode(string longUrl) {
		hash<string> h;
		m_umHash[h(longUrl)] = longUrl;
		return "http://tinyurl.com/" + to_string(h(longUrl));
	}
	// Decodes a shortened URL to its original URL.
	string decode(string shortUrl) {
		size_t id = 0;
		sscanf(shortUrl.substr(19).c_str(), "%zu", &id);
		return m_umHash[id];
	}
};

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

LeetCode Implement Stack using Queues

LeetCode 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.

Notes:

  • You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, 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).

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。

LeetCode Implement Queue using Stacks

LeetCode 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.

Notes:

  • You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, 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).

本题要求用堆栈来实现队列的功能。因为堆栈是后进先出,而队列是先进先出,顺序正好相反。比如进入队列的顺序是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。

LeetCode Min Stack

LeetCode Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) -- Push element x onto stack.
  • pop() -- Removes the element on top of the stack.
  • top() -- Get the top element.
  • getMin() -- Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

本题要实现一个最小栈,使得push, pop, top以及getMin都是以O(1)的时间完成。
这是一个非常经典的双栈法题目,我居然不知道。同时使用两个栈,一个普通的用于存放所有数据allStack,另一个只用于存储最小值序列minStack。
push的时候,每次都把x push进allStack。如果minStack为空,则是第一次push,要把x push进minStack;如果minStack非空,则当x小于等于minStack栈顶时,可以把x push进minStack。注意当x等于minStack栈顶的时候也是需要进栈的,因为有可能有重复元素,比如对0,1,0依次进栈,遇到后面的0时,minStack只有前一个0,此时如果后一个0不进栈,如果下一步是pop的话,就会把minStack中的上一个0 pop掉,那么此时getMin时就会出错,因为此时minStack里没东西了,但allStack还保留着0和1,正确的最小值应该是前一个0。
pop时,allStack正常pop。如果pop出来的值等于minStack的栈顶,则minStack也需要pop。
top就取allStack的top。
getMin就取minStack的top。
完整代码如下:

class MinStack {
private:
	stack<int> allStack, minStack;
public:
	/** initialize your data structure here. */
	MinStack() {
	}
	void push(int x) {
		if (minStack.empty()) {
			minStack.push(x);
		}
		else if (x <= minStack.top()) { // 注意是<=而不是<
			minStack.push(x);
		}
		allStack.push(x);
	}
	void pop() {
		int top = allStack.top();
		allStack.pop();
		if (top == minStack.top()) {
			minStack.pop();
		}
	}
	int top() {
		return allStack.top();
	}
	int getMin() {
		return minStack.top();
	}
};

本代码提交AC,用时29MS。
二刷。其实可以更简单一点,辅助的minStack大小始终和allStack一样,当新入元素小于minStack栈顶元素时,自然入minStack;否则,就把minStack栈顶的元素再入一次栈。这样就使得两个栈的大小一样,pop的时候可以同时pop,减少了各种if判断。
完整代码如下:

class MinStack {
private:
	stack<int> allStack, minStack;
public:
	/** initialize your data structure here. */
	MinStack() {
	}
	void push(int x) {
		if (minStack.empty() || x < minStack.top()) {
			minStack.push(x);
		} else {
			minStack.push(minStack.top());
		}
		allStack.push(x);
	}
	void pop() {
		allStack.pop();
		minStack.pop();
	}
	int top() {
		return allStack.top();
	}
	int getMin() {
		return minStack.top();
	}
};

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

LeetCode Binary Search Tree Iterator

LeetCode Binary Search Tree Iterator
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.


本题要求设计一个二叉搜索树的迭代器,迭代的输出当前树中最小值,并且要求next和hasNext是O(1)时间复杂度和O(h)空间复杂度,h为树的高度。
因为二叉搜索树的中序遍历是递增有序的序列,所以如果没有O(h)空间复杂度限制,则可以提前保存中序遍历结果,然后实现对数组的迭代器。但是这样的空间复杂度就是O(sizeof(tree)),不符合题意。
立马想到树的中序遍历的非递归实现,我们可以借助一个堆栈,先只把树的根和最左边的数压栈,这样栈顶元素就是树的最下角元素,也就是最小值。每调用一次next,返回当前栈顶元素,同时把栈顶元素的右孩子及右孩子的所有最左边的节点压栈。hasNext就好办,直接返回堆栈是否为空。
这样堆栈中最多会保存树高个数的节点,所以是O(h)的空间复杂度。完整代码如下:

class BSTIterator {
private:
	stack<TreeNode*> tree;
	void putAllLeft(TreeNode* root, stack<TreeNode*>& tree) {
		while (root != NULL) {
			tree.push(root);
			root = root->left;
		}
	}
public:
	BSTIterator(TreeNode *root) {
		putAllLeft(root, tree);
	}
	/** @return whether we have a next smallest number */
	bool hasNext() {
		return !tree.empty();
	}
	/** @return the next smallest number */
	int next() {
		TreeNode* top = tree.top();
		tree.pop();
		putAllLeft(top->right, tree);
		return top->val;
	}
};

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