Tag Archives: 字符串

LeetCode Judge Route Circle

LeetCode Judge Route Circle
Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to the original place.
The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are R (Right), L (Left), U (Up) and D (down). The output should be true or false representing whether the robot makes a circle.
Example 1:

Input: "UD"
Output: true

Example 2:

Input: "LL"
Output: false

一个机器人,初始站在原点(0,0),UDLR分别表示上下左右,给定一个机器人行走的轨迹字符串,问最终机器人能回到原点吗。
简单题,直接判断走过的水平和垂直方向的差值是否为0,代码如下:

class Solution {
public:
	bool judgeCircle(string moves) {
		int horizon = 0, vertical = 0;
		for (auto c : moves) {
			if (c == 'U')++vertical;
			else if (c == 'D')--vertical;
			else if (c == 'L')--horizon;
			else if (c == 'R')++horizon;
		}
		return horizon == 0 && vertical == 0;
	}
};

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

LeetCode Replace Words

LeetCode Replace Words

In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, the root an, followed by other, which can form another word another.
Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the rootforming it. If a successor has many roots can form it, replace it with the root with the shortest length.
You need to output the sentence after the replacement.
Example 1:

Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Note:

  1. The input will only have lower-case letters.
  2. 1 <= dict words number <= 1000
  3. 1 <= sentence words number <= 1000
  4. 1 <= root length <= 100
  5. 1 <= sentence words length <= 1000

给定一个词典和一个句子,词典是一系列的词根,要求把句子中的每个词替换成其最短词根(如果有词根的话)。
简单题,明显是Trie树的应用。首先把词典中的所有词根建一个Trie树,然后对句子中的每个单词,去Trie树中查找,返回最先找到的词根(也就是最短的词根);如果该词不在Trie树中,则说明不存在词根,直接用原来的单词。
完整代码如下:

const int kMaxN = 26;
class Solution {
private:
	struct Node {
		bool is_word_;
		vector<Node*> children_;
		Node() :is_word_(false) {
			for (int i = 0; i < kMaxN; ++i)
				children_.push_back(NULL);
		}
	};
	Node *root_;
	void InsertWord(const string& word) {
		Node *cur = root_;
		for (const auto& c : word) {
			int idx = c - 'a';
			if (cur->children_[idx] == NULL)cur->children_[idx] = new Node();
			cur = cur->children_[idx];
		}
		cur->is_word_ = true;
	}
	void ConstructTree(const vector<string>& dict) {
		root_ = new Node();
		for (const auto& w : dict) {
			InsertWord(w);
		}
	}
	string SearchTree(const string& word) {
		Node *cur = root_;
		string ans = "";
		for (const auto& c : word) {
			int idx = c - 'a';
			if (cur->children_[idx] == NULL)return "";
			cur = cur->children_[idx];
			ans.push_back(c);
			if (cur->is_word_)return ans;
		}
		return "";
	}
public:
	string replaceWords(vector<string>& dict, string sentence) {
		ConstructTree(dict);
		string ans = "";
		int i = 0, n = sentence.size();
		for (int j = 0; j <= n; ++j) {
			if (j == n || sentence[j] == ' ') {
				string successor = sentence.substr(i, j - i);
				string root = SearchTree(successor);
				if (root == "")
					ans += successor + " ";
				else
					ans += root + " ";
				i = j + 1;
			}
		}
		return ans.substr(0, ans.size() - 1);
	}
};

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

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 Exclusive Time of Functions

LeetCode Exclusive Time of Functions
Given the running logs of n functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions.
Each function has a unique id, start from 0 to n-1. A function may be called recursively or by another function.
A log is a string has this format : function_id:start_or_end:timestamp. For example, "0:start:0" means function 0 starts from the very beginning of time 0. "0:end:0" means function 0 ends to the very end of time 0.
Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function's exclusive time. You should return the exclusive time of each function sorted by their function id.
Example 1:

Input:
n = 2
logs =
["0:start:0",
 "1:start:2",
 "1:end:5",
 "0:end:6"]
Output:[3, 4]
Explanation:
Function 0 starts at time 0, then it executes 2 units of time and reaches the end of time 1.
Now function 0 calls function 1, function 1 starts at time 2, executes 4 units of time and end at time 5.
Function 0 is running again at time 6, and also end at the time 6, thus executes 1 unit of time.
So function 0 totally execute 2 + 1 = 3 units of time, and function 1 totally execute 4 units of time.

Note:

  1. Input logs will be sorted by timestamp, NOT log id.
  2. Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0.
  3. Two functions won't start or end at the same time.
  4. Functions could be called recursively, and will always end.
  5. 1 <= n <= 100

给定一个单核单线程的CPU,并且给出了该CPU跑不同函数的开始时间和结束时间,问每个函数单独运行的时间是多少。因为有些函数可能会调用其他函数,还可能递归调用自己,所以需要去掉调用其他函数的时间,只给出该函数自己运行的时间。
用Node记录每一个记录,Node包含四个属性:function_id,start_or_end,timestamp和exclude_time,前三个就是题目中描述的属性,最后一个exclude_time是指该函数调用其他函数花费的时间,需要减去的时间。
考虑到递归调用,递归返回之类的,马上想到函数调用的时候需要用堆栈保存现场,所以这里也用堆栈保存所有递归调用的函数。每次遇到新函数的start时,压栈,遇到end时,和栈顶求一下时间差,弹栈,并把时间差记录到结果数组中。同时,需要把这个函数用掉的时间累加到栈顶(也就是主调函数)Node的exclude_time中,这一点非常重要。
最后,因为一个函数可能出现多次,所以不论是对结果数组的赋值还是对exclude_time的赋值,都用+=,不能用赋值,否则会覆盖掉之前的数据。
完整代码如下:

class Solution {
private:
	struct Node {
		int id_;
		bool start_;
		int timestamp_;
		int exclude_time_;
	};
	void ParseLog(const string& log, Node& node) {
		size_t colon_pos = log.find(':');
		node.id_ = stoi(log.substr(0, colon_pos));
		if (log[colon_pos + 1] == 's')
			node.start_ = true;
		else
			node.start_ = false;
		colon_pos = log.find(':', colon_pos + 1);
		node.timestamp_ = stoi(log.substr(colon_pos + 1));
		node.exclude_time_ = 0;
	}
public:
	vector<int> exclusiveTime(int n, vector<string>& logs) {
		vector<int> ans(n);
		stack<Node> stk;
		for (const auto& log : logs) {
			Node node;
			ParseLog(log, node);
			if (node.start_) {
				stk.push(node);
			} else {
				Node start_node = stk.top();
				stk.pop();
				int cur_time = node.timestamp_ - start_node.timestamp_ + 1 - start_node.exclude_time_; // caution
				ans[node.id_] += cur_time; // caution
				if (!stk.empty())stk.top().exclude_time_ += cur_time + start_node.exclude_time_; // caution
			}
		}
		return ans;
	}
};

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

LeetCode Decode Ways II

LeetCode Decode Ways II
A message containing letters from A-Z is being encoded to numbers using the following mapping way:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers from 1 to 9.
Given the encoded message containing digits and the character '*', return the total number of ways to decode it.
Also, since the answer may be very large, you should return the output mod 109 + 7.
Example 1:

Input: "*"
Output: 9
Explanation: The encoded message can be decoded to the string: "A", "B", "C", "D", "E", "F", "G", "H", "I".

Example 2:

Input: "1*"
Output: 9 + 9 = 18

Note:

  1. The length of the input string will fit in range [1, 105].
  2. The input string will only contain the character '*' and digits '0' - '9'.

本题是LeetCode Decode Ways的升级版本,引入了一个星号'*',可以表示'1'-'9'这9个数字。给定一个加密的字符串,问有多少种解密方法。
这个题说难也难,说简单也简单,我居然跪在了int上,把dp数组由int改为long long就AC了!
和前一题的思路差不多,对于每个字符,都有两种可能的选择,要么该字符单独解码,要么和前一个字符组合起来解码。
设dp[i]表示前i个字符总的解密数。
对于当前字符是数字,前一个字符也是数字的情况,和前一题的思路完全一样,如果是'1'-'9',则可以自行解码,dp[i]+=dp[i-1];如果前一个字符和当前字符组合的数字范围在[10,26],可以和前一个字符组合解码,dp[i]+=dp[i-2]。
如果当前字符是数字,但前一个字符是*。如果要和前一个字符组合,当前字符如果在['0','6'],则前一个*可以取'1'或者'2',所以dp[i]+=dp[i-2]*2;如果当前字符是['7','9'],则前一个*只能取'1',所以dp[i]+=dp[i-2]。
对于*需要特殊处理。如果当前字符是*,前一个字符不是*,要和前一个字符组合,则如果前一个是'1',则当前*可以取['0','9'],所以dp[i]+=dp[i-2]*9;如果前一个是'2',则当前*可以取['0','6'],所以dp[i]+=dp[i-2]*6。其他情况都不能组合。
如果当前字符和前一个字符都是*的情况,要组合,则**的情况只有15种,注意不是26种,因为要去掉那些个位数和包含0的十位数的情况,剩下就只有15种了。所以dp[i]+=dp[i-2]*15。
完整代码如下:

const int MOD = 1000000007;
typedef long long ll;
class Solution {
public:
	int numDecodings(string s) {
		if (s == "" || s[0] == '0')return 0;
		s = "^" + s;
		int n = s.size();
		vector<ll> dp(n, 0);
		dp[0] = 1;
		if (s[1] == '*')dp[1] = 9;
		else dp[1] = 1;
		for (int i = 2; i < n; i++)
		{
			if (s[i] >= '1' && s[i] <= '9')
				dp[i] += dp[i - 1] % MOD; // 独自解析
			if ((s[i - 1] == '1' && s[i] >= '0' && s[i] <= '9') || (s[i - 1] == '2' && s[i] >= '0' && s[i] <= '6'))
				dp[i] += dp[i - 2] % MOD;
			if (s[i - 1] == '*'&&s[i] >= '0'&&s[i] <= '9') {
				if (s[i] >= '0'&&s[i] <= '6')dp[i] += dp[i - 2] * 2 % MOD;
				if (s[i] > '6')dp[i] += dp[i - 2] % MOD;
			}
			if (s[i] == '*') {
				dp[i] += dp[i - 1] * 9 % MOD; // 独自解析
				if (s[i - 1] != '*') {
					if (s[i - 1] == '1')dp[i] += dp[i - 2] * 9 % MOD;
					else if (s[i - 1] == '2')dp[i] += dp[i - 2] * 6 % MOD;
				}
				else {
					dp[i] += dp[i - 2] * 15 % MOD;
				}
			}
			dp[i] %= MOD;
		}
		return dp[n - 1];
	}
};

本代码提交AC,用时72MS。比赛的时候dp数组用int存的,死活WA,比赛结束那一秒,改成long long之后就AC了,但是比赛已经结束了。。。
看了下TOP代码,思路比我的稍微清晰一点,原理都是一样的,重构我的代码如下:

class Solution {
public:
	int numDecodings(string s) {
		if (s == "" || s[0] == '0')return 0;
		s = "^" + s;
		int n = s.size();
		vector<ll> dp(n, 0);
		dp[0] = 1;
		if (s[1] == '*')dp[1] = 9;
		else dp[1] = 1;
		for (int i = 2; i < n; i++) {
			char cur = s[i], pre = s[i - 1];
			ll &curCnt = dp[i], preCnt = dp[i - 1], prePreCnt = dp[i - 2];
			if (cur == '0') {
				if (pre == '1'|| pre == '2')curCnt += prePreCnt % MOD;
				else if (pre == '*')curCnt += prePreCnt * 2 % MOD;
				else return 0;
			}
			else if (cur == '*') {
				curCnt += preCnt * 9 % MOD;
				if (pre == '1')curCnt += prePreCnt * 9 % MOD;
				else if (pre == '2')curCnt += prePreCnt * 6 % MOD;
				else if (pre == '*')curCnt += prePreCnt * 15 % MOD;
			}
			else { // ['1','9']
				curCnt += preCnt % MOD;
				if(pre=='1')curCnt += prePreCnt % MOD;
				else if (pre == '2' && cur <= '6')curCnt += prePreCnt % MOD;
				else if (pre == '*') {
					if (cur <= '6')curCnt += prePreCnt * 2 % MOD;
					else curCnt += prePreCnt % MOD;
				}
			}
			curCnt %= MOD;
		}
		return dp[n - 1];
	}
};

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

LeetCode Solve the Equation

LeetCode Solve the Equation
Solve a given equation and return the value of x in the form of string "x=#value". The equation contains only '+', '-' operation, the variable xand its coefficient.
If there is no solution for the equation, return "No solution".
If there are infinite solutions for the equation, return "Infinite solutions".
If there is exactly one solution for the equation, we ensure that the value of x is an integer.
Example 1:

Input: "x+5-3+x=6+x-2"
Output: "x=2"

Example 2:

Input: "x=x"
Output: "Infinite solutions"

Example 3:

Input: "2x=x"
Output: "x=0"

Example 4:

Input: "2x+3x-6x=x+2"
Output: "x=-1"

Example 5:

Input: "x=x+2"
Output: "No solution"

解一个一元一次方程。简单题,首先把方程分解成等号两边两个子表达式,然后解析这两个子表达式,使成为la+lb*x=ra+rb*x,再转换为(lb-rb)x=ra-la,令lb-rb=b, ra-la=a,则最终的表达式等价于bx=a。
如果b等于0,且a也等于0,则有无穷多解。如果b等于0,但a不等于0,则无解。否则x=a/b。
所以问题的难点是怎样把一个表达式转换为a+bx的形式。也就是代码中的convert函数。遍历字符串,取出每个带符号的操作数,如果该操作数包含'x',则取出系数,加到b上;否则是常数项,加到a上。
有一个需要注意的点是包含'x'的操作数可能是'-x'或者'+x',提取系数时需要特殊判断。
代码如下:

class Solution {
private:
	void convert(string& s, int& a, int& b) {
		int aa = 0, bb = 0;
		s += "+";
		int start = 0, end = 0;
		for (end = 0; end < s.size(); ++end) {
			if (end != 0 && (s[end] == '+' || s[end] == '-')) { // -x=-1
				string tmp = s.substr(start, end - start);
				if (tmp.find('x') != string::npos) {
					if (tmp == "x" || tmp == "+x")bb += 1;
					else if (tmp == "-x")bb -= 1;
					else bb += stoi(tmp.substr(0, tmp.size() - 1));
				}
				else {
					aa += stoi(tmp);
				}
				start = end;
			}
		}
		a = aa;
		b = bb;
	}
public:
	string solveEquation(string equation) {
		size_t pos = equation.find('=');
		string left = equation.substr(0, pos), right = equation.substr(pos + 1);
		int la = 0, lb = 0, ra = 0, rb = 0;
		convert(left, la, lb);
		convert(right, ra, rb);
		int b = lb - rb, a = ra - la;
		if (b == 0) {
			if (a == 0)return "Infinite solutions";
			else return "No solution";
		}
		else {
			return "x=" + to_string(a / b);
		}
	}
};

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

LeetCode Design Log Storage System

LeetCode Design Log Storage System
You are given several logs that each log contains a unique id and timestamp. Timestamp is a string that has the following format: Year:Month:Day:Hour:Minute:Second, for example, 2017:01:01:23:59:59. All domains are zero-padded decimal numbers.
Design a log storage system to implement the following functions:
void Put(int id, string timestamp): Given a log's unique id and timestamp, store the log in your storage system.
int[] Retrieve(String start, String end, String granularity): Return the id of logs whose timestamps are within the range from start to end. Start and end all have the same format as timestamp. However, granularity means the time level for consideration. For example, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", granularity = "Day", it means that we need to find the logs within the range from Jan. 1st 2017 to Jan. 2nd 2017.
Example 1:

put(1, "2017:01:01:23:59:59");
put(2, "2017:01:01:22:59:59");
put(3, "2016:01:01:00:00:00");
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Year"); // return [1,2,3], because you need to return all logs within 2016 and 2017.
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Hour"); // return [1,2], because you need to return all logs start from 2016:01:01:01 to 2017:01:01:23, where log 3 is left outside the range.

Note:

  1. There will be at most 300 operations of Put or Retrieve.
  2. Year ranges from [2000,2017]. Hour ranges from [00,23].
  3. Output for Retrieve has no order required.

设计一个日志系统,该系统有两个操作,put(id,timestamp)把timestamp时刻的日志id放到日志系统中,retrieve(start,end,gra)从系统中取出timestamp范围在[start,end]之间的日志id,时间的粒度是gra。
我设计的系统是这样的,为了方便retrieve,系统中的日志都按timestamp排序了。有趣的是,在zero-padded(每部分不足补前导0)的情况下,timestamp的字符串排序就是timestamp表示的时间的排序。
定义一个Node结构体,保持一个日志,信息包括日志id和timestamp。用一个链表存储所有Node,并且当新Node插入时,采用插入排序的方法使得链表始终有序。
retrieve的时候,根据粒度,重新设置start和end,比如样例中粒度为Year时,把start改为Year固定,其他时间最小

"2016:00:00:00:00:00"

把end改为Year固定,其他时间最大

"2017:12:31:23:59:59"

这样我只需要遍历链表,把所有timestamp字符串在这个范围内的日志id取出来就好了。其他粒度也是类似的。
完整代码如下:

class LogSystem {
private:
	struct Node {
		int id;
		string timestamp;
		Node(int i, string t) :id(i), timestamp(t) {};
	};
	list<Node> log;
	string start, end;
public:
	LogSystem() {
		start = "2000:00:00:00:00:00";
		end = "2017:12:31:23:59:59";
	}
	void put(int id, string timestamp) {
		Node node(id, timestamp);
		if (log.empty())log.push_back(node);
		else {
			auto it = log.begin();
			while (it != log.end() && (*it).timestamp <= timestamp)++it;
			log.insert(it, node);
		}
	}
	vector<int> retrieve(string s, string e, string gra) {
		if (gra == "Year") {
			s = s.substr(0, 4) + start.substr(4);
			e = e.substr(0, 4) + end.substr(4);
		}
		else if (gra == "Month") {
			s = s.substr(0, 7) + start.substr(7);
			e = e.substr(0, 7) + end.substr(7);
		}
		else if (gra == "Day") {
			s = s.substr(0, 10) + start.substr(10);
			e = e.substr(0, 10) + end.substr(10);
		}
		else if (gra == "Hour") {
			s = s.substr(0, 13) + start.substr(13);
			e = e.substr(0, 13) + end.substr(13);
		}
		else if (gra == "Minute") {
			s = s.substr(0, 16) + start.substr(16);
			e = e.substr(0, 16) + end.substr(16);
		}
		vector<int> ans;
		auto it = log.begin();
		while (it != log.end() && (*it).timestamp < s)++it;
		while (it != log.end() && (*it).timestamp <= e) {
			ans.push_back((*it).id);
			++it;
		}
		return ans;
	}
};

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

LeetCode Validate IP Address

LeetCode Validate IP Address
Write a function to check whether an input string is a valid IPv4 address or IPv6 address or neither.
IPv4 addresses are canonically represented in dot-decimal notation, which consists of four decimal numbers, each ranging from 0 to 255, separated by dots ("."), e.g.,172.16.254.1;
Besides, leading zeros in the IPv4 is invalid. For example, the address 172.16.254.01 is invalid.
IPv6 addresses are represented as eight groups of four hexadecimal digits, each group representing 16 bits. The groups are separated by colons (":"). For example, the address 2001:0db8:85a3:0000:0000:8a2e:0370:7334 is a valid one. Also, we could omit some leading zeros among four hexadecimal digits and some low-case characters in the address to upper-case ones, so 2001:db8:85a3:0:0:8A2E:0370:7334 is also a valid IPv6 address(Omit leading zeros and using upper cases).
However, we don't replace a consecutive group of zero value with a single empty group using two consecutive colons (::) to pursue simplicity. For example, 2001:0db8:85a3::8A2E:0370:7334 is an invalid IPv6 address.
Besides, extra leading zeros in the IPv6 is also invalid. For example, the address 02001:0db8:85a3:0000:0000:8a2e:0370:7334 is invalid.
Note: You may assume there is no extra space or special characters in the input string.
Example 1:

Input: "172.16.254.1"
Output: "IPv4"
Explanation: This is a valid IPv4 address, return "IPv4".

Example 2:

Input: "2001:0db8:85a3:0:0:8A2E:0370:7334"
Output: "IPv6"
Explanation: This is a valid IPv6 address, return "IPv6".

Example 3:

Input: "256.256.256.256"
Output: "Neither"
Explanation: This is neither a IPv4 address nor a IPv6 address.

给定一个字符串,判断这个字符串是否符合IPv4或者IPv6的格式。
简单的字符串题目。对于IPv4,需要满足:

  1. 只包含数字和点号
  2. 包含4个part,每个part用点号分隔
  3. 每个part不能有前导0,且数值范围是[0,255]

对于IPv6,需要满足:

  1. 只包含数字、冒号和a~f或者A~F
  2. 包含8个part,每个part用冒号分隔
  3. 每个part可以有前导0,但长度不超过4

把这些规则理清楚,用C++ string写代码,如下:

class Solution {
private:
	bool checkIPv4Part(const string& part) {
		size_t len = part.size();
		if (len < 1 || len > 3)return false;
		if (len > 1 && part[0] == '0')return false;
		for (const auto& c : part) {
			if (!(c >= '0'&&c <= '9'))return false;
		}
		int v = stoi(part);
		return v >= 0 && v <= 255;
	}
	bool isIPv4(string& IP) {
		IP += ".";
		int parts = 0;
		size_t start = 0;
		while (true) {
			size_t pos = IP.find('.', start);
			if (pos == string::npos)break;
			if (!checkIPv4Part(IP.substr(start, pos - start)))return false;
			++parts;
			start = pos + 1;
		}
		return parts == 4;
	}
	bool checkIPv6Part(const string& part) {
		size_t len = part.size();
		if (len < 1 || len > 4)return false;
		for (const auto& c : part) {
			if (!((c >= '0'&&c <= '9') || (c >= 'a'&&c <= 'f') || (c >= 'A'&&c <= 'F')))return false;
		}
		return true;
	}
	bool isIPv6(string& IP) {
		IP += ":";
		int parts = 0;
		size_t start = 0;
		while (true) {
			size_t pos = IP.find(':', start);
			if (pos == string::npos)break;
			if (!checkIPv6Part(IP.substr(start, pos - start)))return false;
			++parts;
			start = pos + 1;
		}
		return parts == 8;
	}
public:
	string validIPAddress(string IP) {
		if (IP.find('.') != string::npos)
			return isIPv4(IP) ? "IPv4" : "Neither";
		else return isIPv6(IP) ? "IPv6" : "Neither";
	}
};

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

LeetCode Remove K Digits

LeetCode Remove K Digits
Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
Note:

  • The length of num is less than 10002 and will be ≥ k.
  • The given num does not contain any leading zero.

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

给定一个数字字符串,要求从中删除k个数字,使得最终结果最小,返回最小的数字字符串。
使用栈和贪心的思路。为了使结果尽量小,我们从左往右扫描字符串,把字符存到一个栈中,如果当前字符比栈顶小,则可以把栈顶数字删掉,这样相当于用当前字符代替栈顶字符所在位置,使得结果更小了。否则把当前字符压栈,注意此时不能把当前字符删掉,因为可能后面还有更大的字符出现。
如果这样过了一遍之后,还是没删够k个字符,此时,字符串从左往右肯定是非降序的。所以我们依次弹栈,把栈顶的元素删掉,直到删够k个字符。
最后还要判断一下剩余字符串是否为空,并删除前导零。完整代码如下:

class Solution {
public:
	string removeKdigits(string num, int k) {
		if (k >= num.size())return "0";
		string ans = "";
		for (const auto& c : num) {
			if (ans.empty() || k == 0)ans.push_back(c);
			else {
				while (!ans.empty() && ans.back() > c) {
					ans.pop_back();
					if (--k == 0)break;
				}
				ans.push_back(c);
			}
		}
		while (k-- > 0 && !ans.empty()) ans.pop_back();
		while (!ans.empty() && ans[0] == '0')ans.erase(ans.begin());
		return ans.empty() ? "0" : ans;
	}
};

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

LeetCode Next Greater Element III

LeetCode Next Greater Element III
Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.
Example 1:

Input: 12
Output: 21

Example 2:

Input: 21
Output: -1

给定一个数n,要求用和n一样的数字,重组成一个比n大的最小的数。如果不存在这样的数,输出-1。
比如样例1,n=12,则同样用数字1和2,重组出比12大的最小的数就是21。如果n本身等于21,则无法用数字1和2重组出比21更大的数了。
首先很容易想到无解的情况,比如n=76543210,因为n的数字从左到右是非升序的,所以n本身已经是最大的了,无法重组出比n更大的数。所以隐隐约约感觉可以从左往右找第一个上升的位置。
再来,n=76546743,如果从左往右找第一个上升的位置,则是i=3的数字4,4->6是上升的,所以可以考虑从4后面找比4大的最小的数,也就是6,交换4和6,变成76564743,因为原来为4的位置已经变成更大的6了,所以6后面最小即可,对6后面的数排序,变成了76563447。
但是76563447并不是比n大的最小的数,另外还有76547346,也就是不变4,而是变i=4的数字6。所以换一种思路,我们从右往左找第一个下降的位置,比如这里是i=5的数字7,然后从该位置往右找一个比i-1的数6大的最小的数7,交换他们的位置,同时把i-1右边的数从小到大排序。
再比如n=12443322,从右往左找第一个下降的位置是i=2,数字为4,从该位置找一个比i-1的数2大的最小的数是i=4的数3,交换他们n=1344222,再对i-1右边的数从小到大排序,得到n=1322244。
完整代码如下,另外需要注意结果不能超出int范围,所以先转换为long long,再和INT_MAX比较。

class Solution {
public:
	int nextGreaterElement(int n) {
		string s = to_string(n);
		int m = s.size();
		for (int i = m - 1; i > 0; --i) {
			if (s[i] > s[i - 1]) {
				int pos = i;
				for (int j = i; j < m; ++j) {
					if (s[j] > s[i - 1] && s[j] < s[pos]) {
						pos = j;
					}
				}
				swap(s[pos], s[i - 1]);
				sort(s.begin() + i, s.end());
				long long ans = stoll(s);
				if (ans <= INT_MAX)return ans;
				else return -1;
			}
		}
		return -1;
	}
};

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