Monthly Archives: July 2017

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。 [cpp] 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; } } }; [/cpp] 本代码提交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的赋值,都用+=,不能用赋值,否则会覆盖掉之前的数据。 完整代码如下: [cpp] 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; } }; [/cpp] 本代码提交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。 代码如下: [cpp] 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); } }; [/cpp] 本代码提交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了,则剩余的商品只能按原价购买,算出按原价购买的费用即可。 完整代码如下: [cpp] 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); } }; [/cpp] 本代码提交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。 完整代码如下: [cpp] 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]; } }; [/cpp] 本代码提交AC,用时72MS。比赛的时候dp数组用int存的,死活WA,比赛结束那一秒,改成long long之后就AC了,但是比赛已经结束了。。。 看了下TOP代码,思路比我的稍微清晰一点,原理都是一样的,重构我的代码如下: [cpp] 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]; } }; [/cpp] 本代码提交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’,提取系数时需要特殊判断。 代码如下: [cpp] 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); } } }; [/cpp] 本代码提交AC,用时3MS。]]>

LeetCode Average of Levels in Binary Tree

LeetCode Average of Levels in Binary Tree Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array. Example 1:

Input:
    3
   / \
  9  20
    /  \
   15   7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].
Note:
  1. The range of node’s value is in the range of 32-bit signed integer.

求二叉树每一层的平均数。简单题,BFS层次遍历。代码如下: [cpp] class Solution { public: vector<double> averageOfLevels(TreeNode* root) { if (root == NULL)return{}; vector<double> ans; queue<TreeNode*> q; q.push(root); while (!q.empty()) { double sum = 0; size_t n = q.size(); for (size_t i = 0; i < n; ++i) { TreeNode* f = q.front(); q.pop(); sum += f->val; if (f->left != NULL)q.push(f->left); if (f->right != NULL)q.push(f->right); } ans.push_back(sum / n); } return ans; } }; [/cpp] 本代码提交AC,用时15MS。]]>

LeetCode Continuous Subarray Sum

LeetCode Continuous Subarray Sum Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer. Example 1:

Input: [23, 2, 4, 6, 7],  k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.
Example 2:
Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.
Note:
  1. The length of the array won’t exceed 10,000.
  2. You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

给定一个非负整数数组和k,问数组中是否存在长度至少为2的连续子数组,子数组的和是k的n倍,n也是一个整数。 这个题之前好像在哪遇到过。遇到连续子数组的问题,首先要想到前缀和。因为这里要求和是k的n倍,有点麻烦。 首先我们需要知道一个数学知识,如果到i的前缀和accusum1和到j的前缀和accusum2除以k的余数相等,那么(i,j]的连续子数组的和就是k的整数倍。比如第一个样例中,连续子数组的和以及连续子数组的和除以k的余数:
  • [23,25,29,35,42]
  • [5,1,5,5,0]
如果下标从0开始,则下标为0和2的accusum%k都等于5,说明(0,2]的连续子数组的和是k的整数倍。accusum(0,2]=2+4=6,确实是6的整数倍。 这个道理其实很好理解,accusum0%k=5,到了accusum2%k还等于5,说明中间只加了整数倍的k,才导致余数没变,因为整数倍的k 模k是等于0的。 知道了这个道理就好办了,我们用map保存accusum%k的值和计算到现在的accusum的下标,如果后来遇到一个accusum模k的余数在map中,说明找到了一个可能,我们再判断一下他们之间的距离是否至少为2即可。 还有一个特殊的地方需要注意的是,如果k等于0,则不能取模运算。 最后还要注意的一点是,第12行,把当前余数和下标插入map是在else分支的,只有当map中不存在这个余数才插入,否则不插入。比如上面的例子,我们遇到多个accusum模k的余数是5,但是我们map中保存的应该是第0个下标,后续的余数等于5的下标不能更新0这个下标,因为这样才能使得后续的余数相等的下标和map中的下标的差越大,即更好的满足距离至少为2的约束。 完整代码如下: [cpp] class Solution { public: bool checkSubarraySum(vector<int>& nums, int k) { unordered_map<int, int> reminders; reminders[0] = -1; int accusum = 0; for (int i = 0; i < nums.size(); ++i) { accusum += nums[i]; if (k != 0)accusum %= k; // 注意k为0时,不能取模 if (reminders.find(accusum) != reminders.end()) { if (i – reminders[accusum] >= 2)return true; } else reminders[accusum] = i; // 注意必须是在else分支 } return false; } }; [/cpp] 本代码提交AC,用时26MS。]]>

LeetCode Add and Search Word – Data structure design

211. Add and Search Word – Data structure design 211. Add and Search Word – Data structure design

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z. 211. Add and Search Word – Data structure design


实现一个字典,要求可以插入单词和搜索单词,并且支持一种正则表达式,即点号’.’表示任意一个字符。 本题明显是用Trie树来做,插入和搜索普通字符串的方法和Trie树是一模一样的。 唯一需要注意的是搜索带点号的字符串,此时用递归来做,递归的出口是,当遍历到字符串的最后一个字符时,根据是否为点号进行判断。递归向下的过程也是分是否为点号的,如果是点号,则需要尝试26种递归路径。想清楚这个逻辑之后,代码就很好写了。 完整代码如下:

const int N = 26;
class WordDictionary {
private:
    struct Node {
        bool isWord;
        vector<Node*> children;
        Node(bool i)
            : isWord(i)
        {
            for (int i = 0; i < N; ++i)
                children.push_back(NULL);
        };
    };
    Node* root;
    bool search(const string& word, int i, Node* root)
    {
        if (root == NULL)
            return false;
        int idx = word[i] – ‘a’;
        if (i == word.size() – 1) {
            if (word[i] != ‘.’)
                return root->children[idx] != NULL && root->children[idx]->isWord;
            else {
                for (int j = 0; j < N; ++j) {
                    if (root->children[j] != NULL && root->children[j]->isWord)
                        return true;
                }
                return false;
            }
        }
        if (word[i] != ‘.’)
            return search(word, i + 1, root->children[idx]);
        else {
            for (int j = 0; j < N; ++j) {
                if (search(word, i + 1, root->children[j]))
                    return true;
            }
            return false;
        }
    }
public: /** Initialize your data structure here. */
    WordDictionary() { root = new Node(false); } /** Adds a word into the data structure. */
    void addWord(string word)
    {
        Node* cur = root;
        for (const auto& c : word) {
            int idx = c – ‘a’;
            if (cur->children[idx] == NULL)
                cur->children[idx] = new Node(false);
            cur = cur->children[idx];
        }
        cur->isWord = true;
    } /** Returns if the word is in the data structure. A word could contain the dot character ‘.’ to represent any one letter. */
    bool search(string word)
    {
        Node* cur = root;
        return search(word, 0, cur);
    }
};

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

LeetCode Range Sum Query – Mutable

LeetCode Range Sum Query – Mutable Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive. The update(i, val) function modifies nums by updating the element at index i to val. Example:

Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
Note:
  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly.

给定一个一维数组,要求实现范围求和,即求[i,j]之间的元素的和。sumRange(i,j)求i~j的元素和,update(i,val)更新下标为i的元素值为val。 第一敏感使用线段树,很久之前在hihoCoder上遇到过。 建树的方法是类似于树的后序遍历,即左右根。不断把[start,end]二分,构建左右子树,然后构建当前节点,当前节点的sum等于左右子树的sum的和。在递归的时候,递归到start==end时,说明只有一个元素了,此时sum就等于该元素。 查询的方法和建树方法类似,判断区间[i,j]和区间[start,end]的关系,假设start和end的中点是mid,如果j<=mid,递归在左子树查询;如果i>mid,递归在右子树查询;否则在[i,mid]和[mid+1,j]查询然后求和。 更新的方法和查询的方法类似,也是不断判断i和mid的关系,在左子树或者右子树递归更新,当找到该叶子节点时,更新它的sum,返回父节点也更新sum等于新的左右子树的sum的和。 完整代码如下: [cpp] class NumArray { private: struct Node { int start, end, sum; Node *left, *right; Node(int s, int e) :start(s), end(e), sum(0), left(NULL), right(NULL) {}; }; Node *root; Node* constructTree(vector<int> &nums, int start, int end) { Node* node = new Node(start, end); if (start == end) { node->sum = nums[start]; return node; } int mid = start + (end – start) / 2; node->left = constructTree(nums, start, mid); node->right = constructTree(nums, mid + 1, end); node->sum = node->left->sum + node->right->sum; return node; } int sumRange(int i, int j, Node *root) { if (root == NULL)return 0; if (i == root->start&&j == root->end)return root->sum; int mid = root->start + (root->end – root->start) / 2; if (j <= mid)return sumRange(i, j, root->left); else if (i > mid)return sumRange(i, j, root->right); else return sumRange(i, mid, root->left) + sumRange(mid + 1, j, root->right); } void update(int i, int val, Node *root) { if (root->start == root->end && root->start == i) { root->sum = val; return; } int mid = root->start + (root->end – root->start) / 2; if (i <= mid)update(i, val, root->left); else update(i, val, root->right); root->sum = root->left->sum + root->right->sum; } public: NumArray(vector<int> nums) { root = NULL; if (!nums.empty())root = constructTree(nums, 0, nums.size() – 1); } void update(int i, int val) { if (root == NULL)return; update(i, val, root); } int sumRange(int i, int j) { if (root == NULL)return 0; return sumRange(i, j, root); } }; [/cpp] 本代码提交AC,用时172MS。]]>