LeetCode Find Duplicate Subtrees

LeetCode Find Duplicate Subtrees
Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.
Two trees are duplicate if they have the same structure with same node values.
Example 1: 

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4

The following are two duplicate subtrees:

      2
     /
    4

and

    4

Therefore, you need to return above trees' root in the form of a list.


给定一棵二叉树,要求找出其中的重复子树,每组重复子树输出其中一个子树即可。
去重最好的办法就是hash,所以思想是把每个子树hash到一个unordered_map中,如果有多个子树hash到同一个桶,则出现了重复。
所以问题的关键是怎样对一个子树hash。我们可以把一棵子树表示成 (left_hash, root, right_hash),其中left_hash和right_hash分别是左子树和右子树的hash字符串,root表示当前根节点的hash字符串。所以这是一个递归定义。规定空节点的hash值为空串""。
根据子树hash的定义,叶子节点的hash值是("",val,"")。求解子树hash值的过程可以用中序遍历,左根右。为什么子树hash中需要逗号和括号呢,就是为了保证不同严格区分不同的子树,因为单纯的中序遍历是无法区分某些子树的,比如下面的两个子树,中序遍历结果都是2,1,无法区分;但是用本文的hash方法,得到的hash值分别是(2,1,)和(,2,1),这两个字符串是有区别的。

  1
 /
2

 2
  \
   1

在DFS的过程中,把每个子树的hash值记录到一个unordered_map中,然后遍历unordered_map,如果该桶放了多个子树,则取出其中一个即可。
完整代码如下:

class Solution {
private:
	string DFS(TreeNode* root, unordered_map<string, vector<TreeNode*>>& inorders) {
		if (root == NULL)return "";
		string left = DFS(root->left, inorders);
		string right = DFS(root->right, inorders);
		string cur = "(" + left + "," + to_string(root->val) + "," + right + ")";
		inorders[cur].push_back(root);
		return cur;
	}
public:
	vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
		unordered_map<string, vector<TreeNode*>> inorders;
		DFS(root, inorders);
		vector<TreeNode*> ans;
		for (auto &it : inorders) {
			if (it.second.size() > 1)
				ans.push_back(it.second[0]);
		}
		return ans;
	}
};

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

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 Palindromic Substrings

LeetCode Palindromic Substrings
Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:

  1. The input string length won't exceed 1000.

给定一个字符串,问该字符串中有多少个回文子串。
暴力解法就是枚举每个子串,判断子串是否是回文串。判断一个字符串是否是回文串,可以用首尾指针法,也可以用中心扩展法,方法很多,需要O(n)时间,所以暴力总时间是O(n^3)。
稍微高效一点的方法是,不枚举子串,直接对每个字符用中心扩展法,请看讨论区代码
我的解法是O(n^2)的DP方法,dp[i][j]表示子串[i,j]是否是回文串。首先对于长度为1的子串dp[i][i]=1肯定都是回文串;求dp[i][j]时,如果s[i]==s[j]且dp[i+1][j-1]是回文串,则dp[i][j]=1也是回文串。
最后统计一下dp数组中有多少个1就有多少个回文子串。
代码如下:

class Solution {
public:
	int countSubstrings(string s) {
		int ans = 0, n = s.size();
		vector<vector<int>> dp(n, vector<int>(n, 0));
		for (int i = 0; i < n; ++i) {
			dp[i][i] = 1;
			++ans;
		}
		for (int len = 2; len <= n; ++len) {
			for (int i = 0; i < n; ++i) {
				int j = i + len - 1;
				if (j >= n)break;
				if (s[i] == s[j] && (len == 2 || dp[i + 1][j - 1] == 1)) {
					dp[i][j] = 1;
					++ans;
				}
			}
		}
		return ans;
	}
};

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

LeetCode Maximum Length of Pair Chain

LeetCode Maximum Length of Pair Chain
You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.
Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.
Given a set of pairs, find the length longest chain which can be formed. You needn't use up all the given pairs. You can select pairs in any order.
Example 1:

Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]

Note:

  1. The number of given pairs will be in the range [1, 1000].

如果两个数对(a,b)和(c,d)满足b<c,则(c,d)可以跟在(a,b)的后面。给定一系列数对(s,t),问从这些数对中最多能取出多少个数对满足连续满足这种条件。
解法1,使用DP。首先对所有数对(x,y)先按x排序,x相同再按y排序。然后遍历数对,对于每个数对,有两种选择,不要或者要,对应dp[i][0]和dp[i][1],表示到i时能选出来的最多的满足条件的数对。
则dp[i][0]=max(dp[i-1][0], dp[i-1][1]),因为第i个数对不选,所以肯定等于前i-1个能选出来的最大数对,也就是max(dp[i-1][0], dp[i-1][1])。
如果第i个数对选,则要往前找到一个和i不冲突的数对j,接在j的后面,所以dp[i][1]=dp[j][1]+1。
代码如下:

bool cmp(const vector<int>& p1, const vector<int>& p2) {
	return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]);
}
class Solution {
public:
	int findLongestChain(vector<vector<int>>& pairs) {
		sort(pairs.begin(), pairs.end(), cmp);
		int n = pairs.size();
		vector<vector<int>> dp(n, vector<int>(2, 0));
		dp[0][0] = 0;
		dp[0][1] = 1;
		int ans = 1;
		for (int i = 1; i < n; ++i) {
			dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
			dp[i][1] = 1;
			int j = i - 1;
			while (j >= 0 && pairs[i][0] <= pairs[j][1]) {
				--j;
			}
			if (j >= 0) {
				dp[i][1] = max(dp[i][1], dp[j][1] + 1);
			}
			ans = max(ans, dp[i][0]);
			ans = max(ans, dp[i][1]);
		}
		return ans;
	}
};

本代码提交AC,用时49MS。
我隐隐觉得这种解法有问题,就是在求dp[i][1]的时候,应该要找i前面所有和i不冲突的j,求max,即dp[i][1]=max(dp[j][1]+1)。
所以解法2是无懈可击的DP解法。设dp[i]表示以数对i结尾能得到的最长的链式数对,则初始的时候,所有dp[i]=1。然后对于第i个数对,遍历i前面所有数对j,只要i和j能够链起来,则求dp[i]=max(dp[j]+1)。时间复杂度O(n^2),代码如下:

class Solution {
public:
	int findLongestChain(vector<vector<int>>& pairs) {
		sort(pairs.begin(), pairs.end(), [](const vector<int>& p1, const vector<int>& p2) {return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]); });
		int n = pairs.size(), ans = 1;
		vector<int> dp(n, 1);
		for (int i = 1; i < n; ++i) {
			for (int j = i - 1; j >= 0; --j) {
				if (pairs[i][0] > pairs[j][1]) {
					dp[i] = max(dp[i], dp[j] + 1);
				}
			}
			ans = max(ans, dp[i]);
		}
		return ans;
	}
};

本代码提交AC,用时122MS。
解法3,首先还是对所有数对排序,然后把这题看成类似于求最长上升子序列。即设dp[k]=构成链条长度为k时最小的结束时间。那么来了一个数对之后,如果该数对的开始时间大于dp末尾的结束时间,则说明该数对可以追加到dp中,链条长度加1,dp[k+1]=该数对的结束时间。否则,如果该数对的开始时间不大于dp末尾的结束时间,则需要像LIS一样,把该数对插入到dp中,因为dp是排好序的,所以二分插入即可。
该思路请参考:https://discuss.leetcode.com/topic/96814/python-straightforward-with-explanation-n-log-n/2。比较有意思的是,正如第一个评论人所说,因为提前对数对按结束时间排序了,所以后面的数对肯定是大于等于dp末尾的数对的,所以新来的数对只可能追加到dp的末尾,不可能插入到dp的其他位置,所以就可以省略二分插入的过程。完整代码简洁如下:

class Solution {
public:
	int findLongestChain(vector<vector<int>>& pairs) {
		sort(pairs.begin(), pairs.end(), [](const vector<int>& p1, const vector<int>& p2) {return p1[1] < p2[1]; });
		int ans = 0;
		for (int i = 0, j = 0; j < pairs.size(); ++j) {
			if (j == 0 || pairs[j][0] > pairs[i][1]) {
				++ans;
				i = j;
			}
		}
		return ans;
	}
};

本代码提交AC,用时45MS。
这个题可以把每个数对看成一个活动的开始和结束时间,把问题转换为从所有活动中选出尽量多的不重叠的活动,求最多的活动个数。活动选择问题可以用贪心求解,详细介绍和证明请看维基百科

LeetCode Set Mismatch

LeetCode Set Mismatch
The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.
Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.
Example 1:

Input: nums = [1,2,2,4]
Output: [2,3]

Note:

  1. The given array size will in the range [2, 10000].
  2. The given array's numbers won't have any order.

一个大小为n的数组,本来包含1~n这n个数,但是某个数x“突变”成y了,这就导致数组中丢了x,而y重复出现了两次,现在要找出丢掉的x和重复的y。
简单题,首先用hash可以找到重复的y,然后根据数学关系可以找到x,本来1~n的和是S=n*(n+1)/2,设现在的和是T,则有x=y-T+S。
代码如下:

class Solution {
public:
	vector<int> findErrorNums(vector<int>& nums) {
		vector<int> ans(2, 0);
		unordered_set<int> hash;
		int sum = 0, n = nums.size();
		for (const auto& num : nums) {
			if (hash.find(num) != hash.end())ans[0] = num;
			hash.insert(num);
			sum += num;
		}
		ans[1] = ans[0] - sum + n*(n + 1) / 2;
		return ans;
	}
};

本代码提交AC,用时59MS。
还有一种空间复杂度O(1)的方法,不过需要改变原有数组。
因为数组元素是1~n的,所以遍历数组,把数值-1当作下标访问数组,使该处的元素变为原来的相反数,如果遇到某个数y-1访问的那个数是负数,说明y重复了,之前有一个y把y-1处的数变成了负数。
遍历完一遍之后,丢失的那个数x指向的x-1处的数应该是正数,因为x丢掉了,没有经过上面的过程,所以再遍历一遍可以找到x。
整个过程不需要借助额外的空间,代码如下:

class Solution {
public:
	vector<int> findErrorNums(vector<int>& nums) {
		vector<int> ans(2, 0);
		for (int i = 0; i < nums.size(); ++i) {
			int idx = nums[i] < 0 ? -nums[i] : nums[i];
			if (nums[idx - 1] < 0) {
				ans[0] = idx;
			} else {
				nums[idx - 1] = -nums[idx - 1];
			}
		}
		for (int i = 0; i < nums.size(); ++i) {
			if (nums[i] > 0) {
				ans[1] = i + 1;
				break;
			}
		}
		return ans;
	}
};

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

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 Maximum Average Subarray I

LeetCode Maximum Average Subarray I
Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.
Example 1:

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

Note:

  1. 1 <= k <= n <= 30,000.
  2. Elements of the given array will be in the range [-10,000, 10,000].

给定一个数组,问长度为k的子数组的最大平均数是多少。简单题,因为平均数等于和除以k,k相同,也就相当于求长度为k的最长连续子串的和。
解法是维护一个长度为k的滑动窗口,求滑动窗口内的最大连续子数组的和,然后除以k。
代码如下:

class Solution {
public:
	double findMaxAverage(vector<int>& nums, int k) {
		int n = nums.size();
		if (n < k)return 0;
		int i = 0, sum = 0, ans = INT_MIN;
		for (int j = 0; j < k; ++j)sum += nums[j];
		for (int j = k; j < n; ++j) {
			ans = max(ans, sum);
			sum += nums[j] - nums[i];
			++i;
		}
		ans = max(ans, sum);
		return ans / double(k);
	}
};

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

LeetCode Shopping Offers

LeetCode Shopping Offers
In LeetCode Store, there are some kinds of items to sell. Each item has a price.
However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.
You are given the each item's price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers.
Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer.
You could use any of special offers as many times as you want.
Example 1:

Input: [2,5], [[3,0,5],[1,2,10]], [3,2]
Output: 14
Explanation:
There are two kinds of items, A and B. Their prices are $2 and $5 respectively.
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B.
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.

Example 2:

Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
Output: 11
Explanation:
The price of A is $2, and $3 for B, $4 for C.
You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C.
You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C.
You cannot add more items, though only $9 for 2A ,2B and 1C.

Note:

  1. There are at most 6 kinds of items, 100 special offers.
  2. For each item, you need to buy at most 6 of them.
  3. You are not allowed to buy more items than you want, even if that would lower the overall price.

给定每个商品的单价和需要购买的数量,并且有一些special offer,相当于捆绑销售的优惠套餐。问刚好买到给定数量的商品,所花的最低费用是多少。
注意给定的限制条件中商品最多只有6种,且每件最多只购买6件,所以可以考虑用暴力方法。
把special offer看成一个背包问题里的“商品”,对于每个special offer,我们有两种选择,可以用或者不用。如果需要的needs数组每一项都大于等于某个special offer的每一项,即可以用该special offer,我们比较用和不用该special offer的最终花费,取花费低的。如果用该special offer,则needs数组需要减掉sp捆绑的每件商品的件数,然后继续递归该sp是否可用,相当于完全背包,不计件数的。如果该sp不能用,则递归考虑下一个sp。最后如果递归考虑完所有sp了,则剩余的商品只能按原价购买,算出按原价购买的费用即可。
完整代码如下:

class Solution {
private:
	int dot(vector<int>& price, vector<int>& needs) {
		int ans = 0;
		for (int i = 0; i < needs.size(); ++i) {
			ans += price[i] * needs[i];
		}
		return ans;
	}
	int shopping(vector<int>& price, vector<vector<int>>& special, vector<int>& needs, int idx) {
		if (idx == special.size())return dot(price, needs); // 原价购买
		int i = 0, n = special[idx].size();
		vector<int> small_needs = needs;
		for (i = 0; i < n - 1; ++i) {
			if (special[idx][i] > needs[i])break;
			small_needs[i] -= special[idx][i];
		}
		if (i == n - 1)return min(shopping(price, special, small_needs, idx) + special[idx][n - 1], shopping(price, special, needs, idx + 1));
		else return shopping(price, special, needs, idx + 1);
	}
public:
	int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
		return shopping(price, special, needs, 0);
	}
};

本代码提交AC,用时6MS。
参考:https://leetcode.com/articles/shopping-offers/,下次记得看到这种数据量非常小的题,首先尝试暴力方法!

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。