LeetCode Reverse Words in a String III Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order. Example 1:

Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Note: In the string, each word is separated by single space and there will not be any extra space in the string.

---

给定一个句子，要求把句子中的每个单词都逆序。 简单题，找空格，然后对每个单词reverse，直接调string::reverse或者自己写都可以。 代码如下： [cpp] class Solution { public: string reverseWords(string s) { int i = 0, j = 0, n = s.size(); while (j < n) { while (j < n&&s[j] != ‘ ‘)++j; reverse(s.begin() + i, s.begin() + j); i = ++j; } return s; } }; [/cpp] 本代码提交AC，用时23MS。]]>

LeetCode Complex Number Multiplication Given two strings representing two complex numbers. You need to return a string representing their multiplication. Note i² = -1 according to the definition. Example 1:

Input: "1+1i", "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.

Example 2:

Input: "1+-1i", "1+-1i"
Output: "0+-2i"
Explanation: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i, and you need convert it to the form of 0+-2i.

Note:

1. The input strings will not have extra blank.
2. The input strings will be given in the form of a+bi, where the integer a and b will both belong to the range of [-100, 100]. And the output should be also in this form.

---

给定两个复数字符串，要求计算它们的乘积。 简单题，展开之后是：(a1+a2i)(b1+b2i)=(a1*b1-a2*b2)+(a1*b2+a2*b1)i。所以只需要提取出a1,a2,b1,b2，然后代入公式计算到c1和c2，最后用to_string转换为字符串即可。 代码如下： [cpp] class Solution { void str2cpx(const string& s, int& c1, int&c2) { int i = 0, j = 0; while (s[j] != ‘+’)++j; c1 = atoi(s.substr(i, j – i).c_str()); i = ++j; while (s[j] != ‘i’)++j; c2 = atoi(s.substr(i, j – i).c_str()); } public: string complexNumberMultiply(string a, string b) { int a1 = 0, a2 = 0, b1 = 0, b2 = 0, c1 = 0, c2 = 0; str2cpx(a, a1, a2); str2cpx(b, b1, b2); c1 = a1*b1 – a2*b2; c2 = a1*b2 + a2*b1; return to_string(c1) + "+" + to_string(c2) + "i"; } }; [/cpp] 本代码提交AC，用时3MS。]]>

LeetCode Longest Absolute File Path Suppose we abstract our file system by a string in the following manner: The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:

dir
    subdir1
    subdir2
        file.ext

The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext. The string "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" represents:

dir
    subdir1
        file1.ext
        subsubdir1
    subdir2
        subsubdir2
            file2.ext

The directory dir contains two sub-directories subdir1 and subdir2. subdir1 contains a file file1.ext and an empty second-level sub-directory subsubdir1. subdir2contains a second-level sub-directory subsubdir2 containing a file file2.ext. We are interested in finding the longest (number of characters) absolute path to a file within our file system. For example, in the second example above, the longest absolute path is "dir/subdir2/subsubdir2/file2.ext", and its length is 32 (not including the double quotes). Given a string representing the file system in the above format, return the length of the longest absolute path to file in the abstracted file system. If there is no file in the system, return 0. Note:

• The name of a file contains at least a . and an extension.
• The name of a directory or sub-directory will not contain a ..

Time complexity required: O(n) where n is the size of the input string. Notice that a/aa/aaa/file1.txt is not the longest file path, if there is another path aaaaaaaaaaaaaaaaaaaaa/sth.png.

---

给定一个文件系统的树形结构，要求以O(n)的复杂度找出最长路径的文件的路径长度，这里的长度包括分隔符’/’。 一开始我没有清晰的思路，后来在暗时间会拿出来思考，今天早上刷牙的时候想到了大概的解法。 遍历一次字符串，用一个vector保存当前看到的文件系统的最深层次，用level保存当前进入到的文件系统的深度。vector初始为空，level初始为0。每次我们找’\n’，因为’\n’表示一层文件系统的结束。每层文件系统level都从0开始。 比如第一个例子（如下），看到dir时，vector还是空的，所以vector.push_back(dir)。回车之后是’\t’，此时的level为0，且vector[0]有东西，说明要进入vector[0]表示的文件夹的下一层，level++。又遇到subdir1，此时的level=1了，已经大于等于vector的长度，说明目前进入到的深度已经超过了vector的表示范围，所以vector.push_back(subdir1)。 遇到’\n’又重新开始了，level为0。遇到’\t’，vector有，进入vector[0]，level++。遇到subdir2，此时level=1，但vector[1]有东西，此时需要把vector[1]覆盖为subdir2，因为目前看到的第1层已经是新的了。 遇到’\n’又重新开始，level为0。后面连遇到两个’\t’，且vector中都有对应，说明是在之前的路径里面，即dir/subdir2/。最后遇到file.ext文件，就能算到该文件的路径长度了。

dir
    subdir1
    subdir2
        file.ext

代码如下。需要注意一点，如果一个string为”dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext”，里面的’\n’和’\t’虽然看起来是两个字符\加n或者t，但是实际是一个char为’\n’或’\t’，内存中只用一个字符char来表示，所以直接判断input[i]==’\n’即可。 [cpp] class Solution { public: int lengthLongestPath(string input) { vector<string> paths; int maxLen = 0, n = input.size(), i = 0, j = 0; while (j < n) { bool isfile = false; int curLen = 0, level = 0; while (j < n&&input[j] != ‘\n’) { if (input[j] == ‘.’)isfile = true; else if (input[j] == ‘\t’) { if (paths.size() <= level)paths.push_back(input.substr(i, j – i)); curLen += paths[level++].size() + 1; // +1指分隔符’/’ i = j + 1; } ++j; } if (paths.size() <= level)paths.push_back(input.substr(i, j – i)); else paths[level] = input.substr(i, j – i); curLen += paths[level++].size(); // 末尾不需要分隔符’/’ i = ++j; if (isfile)maxLen = max(maxLen, curLen); } return maxLen; } }; [/cpp] 本代码提交AC，用时3MS。]]>

LeetCode Longest Word in Dictionary through Deleting Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string. Example 1:

Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
Output:
"apple"

Example 2:

Input:
s = "abpcplea", d = ["a","b","c"]
Output:
"a"

Note:

1. All the strings in the input will only contain lower-case letters.
2. The size of the dictionary won’t exceed 1,000.
3. The length of all the strings in the input won’t exceed 1,000.

---

给定一个字典d和字符串s，问d中哪些字符串可以通过s删除若干个字符得到，要求输出满足条件的最长字符串，如果有多个，则输出字典序最小的。 本题有两个考点，一是判断t是否能通过删除s中的若干个字符得到。使用两个指向s,t的指针i,j，j不断后移找t[i]，找到之后i,j都后移。最终如果找到t中所有字符，则成功，否则失败。 另一个考点是，找出所有满足条件的字符串之后，怎样找到长度最长且字典序最小的字符串。这可以通过自定义string的比较函数，然后sort得到。具体看代码： [cpp] bool comp(const string& s1, const string& s2) { return s1.size() > s2.size() || (s1.size() == s2.size() && s1 < s2); } class Solution { private: bool convert(const string& src, const string& dest){ int m = src.size(), n = dest.size(); if (m < n)return false; int i = 0, j = 0; while (i < m) { while (i < m && src[i] != dest[j])++i; if (i >= m)break; ++i; ++j; if (j == n)break; } return j == n; } public: string findLongestWord(string s, vector<string>& d) { vector<string> cand; for (int i = 0; i < d.size(); ++i) { if (convert(s, d[i]))cand.push_back(d[i]); } sort(cand.begin(), cand.end(), comp); if (cand.size() > 0)return cand[0]; else return ""; } }; [/cpp] 本代码提交AC，用时135MS。]]>

LeetCode Is Subsequence Given a string s and a string t, check if s is subsequence of t. You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100). A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not). Example 1: s = "abc", t = "ahbgdc" Return true. Example 2: s = "axc", t = "ahbgdc" Return false. Follow up: If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

---

给定两个字符串s和t，判断s是否是t的子序列。子序列的概念和子串不一样，如果s是t的子串，则s必须是t中连续的一段；而如果是子序列的话，则s只需要是t中若干个字符，但这些字符顺序必须和t中的一样。 比如t=”abcdefghijk”，则”cdef”既可以是t的子串，也可以是t的子序列；而”bfjk”只能是t的子序列。 本题很简单，维护两个指针i,j，分别指向s和t，从t中不断找字符s[i]，没找到只递增j，找到的话同时递增i和j。如果最后i到达s的末尾了，说明s是t的子序列，否则不是。 代码如下： [cpp] class Solution { public: bool isSubsequence(string s, string t) { int m = s.size(), n = t.size(); if (m > n)return false; int i = 0, j = 0; while (i < m&&j < n) { while (j < n&&s[i] != t[j])++j; if (j >= n)return false; ++i; ++j; } return i == m; } }; [/cpp] 本代码提交AC，用时73MS。]]>

LeetCode Minimum Time Difference Given a list of 24-hour clock time points in “Hour:Minutes” format, find the minimum minutes difference between any two time points in the list. Example 1:

Input: ["23:59","00:00"]
Output: 1

Note:

1. The number of time points in the given list is at least 2 and won’t exceed 20000.
2. The input time is legal and ranges from 00:00 to 23:59.

---

给定一个时间字符串数组，问数组中任意两个时间之差最小是多少分钟。 本题的基本思路是把数组中所有的时间表示转换为分钟，然后排序求相邻两个分钟之间的最小差。 本题的一个小难点是时间是循环的，比如01:30和06:30差5小时，但01:30和23:30差几小时呢？如果顺着看差22小时，好像比前一个差要大，但是逆着看，实际上只差2小时。所以分立0点两边的两个时间差其实有两个。处理办法是把0~12点之间的时间转换为两个分钟数，一个是0~12以内的，另一个是12~24以内的。 代码如下： [cpp] class Solution { private: void convertToMinutes(const string& s, vector<int>& minutes) { int pos = s.find(‘:’); int hour = atoi(s.substr(0, pos).c_str()), minute = atoi(s.substr(pos + 1).c_str()); int m = hour * 60 + minute; minutes.push_back(m); if (hour < 12)minutes.push_back(m + 24 * 60); } public: int findMinDifference(vector<string>& timePoints) { vector<int> minutes; for (int i = 0; i < timePoints.size(); ++i) { convertToMinutes(timePoints[i], minutes); } sort(minutes.begin(), minutes.end()); int ans = INT_MAX; for (int i = 1; i < minutes.size(); ++i) { ans = min(ans, minutes[i] – minutes[i – 1]); } return ans; } }; [/cpp] 本代码提交AC，用时19MS。]]>