[5] Longest Palindromic Substring(2019 年 1 月 22 日, 复习)
[6] ZigZag Conversion(2019 年 1 月 22 日, 复习)
[8] String to Integer (atoi)(2019 年 1 月 22 日, 复习)
[10] Regular Expression Matching(2019 年 1 月 22 日, 复习)
[12] Integer to Roman(2019 年 1 月 22 日, 复习)
[13] Roman to Integer(2019 年 1 月 22 日, 复习)
罗马数字转换成整数.
题解: 用一个 map 来存储映射关系.
- class Solution {
- public:
- int romanToInt(string s) {
- const int n = s.size();
- initMap();
- int idx = 0;
- int ret = 0;
- while (idx <n) {
- if (idx + 1 == n) {
- string temp = string(1, s[idx]);
- ret += mp[temp];
- idx++;
- continue;
- }
- string str = s.substr(idx, 2);
- if (mp.find(str) != mp.end()) {
- ret += mp[str];
- idx += 2;
- } else {
- string temp = string(1, s[idx]);
- ret += mp[temp];
- idx++;
- }
- }
- return ret;
- }
- unordered_map<string, int> mp;
- void initMap() {
- mp["IV"] = 4, mp["IX"] = 9;
- mp["XL"] = 40, mp["XC"] = 90;
- mp["CD"] = 400, mp["CM"] = 900;
- mp["I"] = 1, mp["V"] = 5, mp["X"] = 10,
- mp["L"] = 50, mp["C"] = 100, mp["D"] = 500,
- mp["M"] = 1000;
- }
- };
- View Code
[14] Longest Common Prefix(2019 年 1 月 22 日, 复习)
给了一组单词, 由小写字母构成, 找他们的公共前缀, 返回这个字符串.
题解: 可以暴力解, 可以 trie 树.
- class Solution {
- public:
- string longestCommonPrefix(vector<string>& strs) {
- if(strs.empty()) return "";
- for(int i=0; i<strs[0].size(); ++i){
- for(int j=1; j<strs.size(); ++j){
- if(strs[0][i] != strs[j][i]){
- return strs[0].substr(0,i);
- }
- }
- }
- return strs[0];
- }
- };
- View Code
- class Solution {
- public:
- struct TrieNode {
- char c;
- vector<TrieNode*> children;
- bool isEndingChar = false;
- int cntChildrenNotNull = 0;
- TrieNode(char t): c(t) {
- children = vector<TrieNode*>(26, nullptr);
- }
- };
- class Trie {
- public:
- void insert(string s) {
- TrieNode * node = root;
- for (int i = 0; i <s.size(); ++i) {
- char c = s[i];
- if (node->children[c-'a'] == nullptr) {
- node->children[c-'a'] = new TrieNode(c);
- node->cntChildrenNotNull++;
- }
- node = node->children[c-'a'];
- }
- node->isEndingChar = true;
- return;
- }
- string getCommonPrefix() {
- TrieNode* node = root;
- string ret = "";
- while (node->cntChildrenNotNull == 1 && node->isEndingChar == false) {
- for (int i = 0; i <26; ++i) {
- if (node->children[i]) {
- node = node->children[i];
- break;
- }
- }
- ret += string(1, node->c);
- }
- return ret;
- }
- TrieNode* root = new TrieNode('/');
- };
- string longestCommonPrefix(vector<string>& strs) {
- const int n = strs.size();
- Trie trie;
- for (auto s : strs) {
- if (s.empty()) {
- return s;
- }
- trie.insert(s);
- }
- return trie.getCommonPrefix();
- }
- };
- View Code
[17] Letter Combinations of a Phone Number(2019 年 1 月 22 日, 复习)
给了一个座机电话, 给了一个数字的字符串 digits, 返回所有的数字对应的字母排列.
题解: map + dfs
- class Solution {
- public:
- vector<string> letterCombinations(string digits) {
- n = digits.size();
- if (n == 0) { return vector<string>{}; }
- initMap();
- string s = "";
- dfs(digits, 0, s);
- return ret;
- }
- int n;
- unordered_map<int, vector<string>> mp;
- vector<string> ret;
- void dfs(string digits, int cur, string& s) {
- if (cur == n) {
- ret.push_back(s);
- return;
- }
- int num = digits[cur] - '0';
- for (auto ele : mp[num]) {
- string ori = s;
- s += ele;
- dfs(digits, cur + 1, s);
- s = ori;
- }
- return;
- }
- void initMap() {
- mp[2] = {"a", "b", "c"};
- mp[3] = {"d", "e", "f"};
- mp[4] = {"g", "h", "i"};
- mp[5] = {"j", "k", "l"};
- mp[6] = {"m", "n", "o"};
- mp[7] = {"p", "q", "r", "s"};
- mp[8] = {"t", "u", "v"};
- mp[9] = {"w", "x", "y", "z"};
- }
- };
- View Code
[20] Valid Parentheses(2019 年 1 月 22 日, 复习)
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. 判断一个字符串中的括号是不是合法的.
题解: 用栈做.
代码不贴了.
[22] Generate Parentheses(2019 年 1 月 22 日, 复习)
[28] Implement strStr()(算法群, 2018 年 11 月 4 日, 练习 kmp)
实现在字符串 s 中找到 模式串 p, (kmp)
题解: 暴力 O(N*M) 可以解, kmp O(N+M) 也可以解 ,kmp 务必再深入理解一下 next 数组的求法. 不然面试不给笔记看就凉凉了.(还有一个注意点是 p 为空串的时候要特判)
- class Solution {
- public:
- int strStr(string haystack, string needle) {
- return kmp(haystack, needle);
- }
- int kmp(string& s, string& p) {
- const int n = s.size(), m = p.size();
- if (m == 0) {return 0;} //p empty
- vector<int> next = getNext(p);
- int i = 0, j = 0;
- while (i <n && j < m) {
- if (j == -1 || s[i] == p[j]) {
- ++i, ++j;
- } else {
- j = next[j];
- }
- }
- if (j == m) {
- return i - j;
- }
- return -1;
- }
- vector<int> getNext(string& p) {
- const int n = p.size();
- vector<int> next(n, 0);
- next[0] = -1;
- int j = 0, k = -1;
- while (j <n - 1) {
- if (k == -1 || p[j] == p[k]) {
- ++k, ++j;
- next[j] = p[j] == p[k] ? next[k] : k;
- } else {
- k = next[k];
- }
- }
- return next;
- }
- };
- kmp
- // 暴力解法 O(N*M)
- class Solution {
- public:
- int strStr(string haystack, string needle) {
- const int n = haystack.size(), m = needle.size();
- if (m == 0) {return 0;}
- for (int i = 0; i + m <= n; ) { // 判断条件要不要取等号, 然后下面做了 ++i, ++j, for 循环里面就别做了, 尴尬, 这都能错
- int j; int oldi = i;
- for (j = 0; j < m;) {
- if (haystack[i] == needle[j]) {
- ++i, ++j;
- } else {
- break;
- }
- }
- if (j == m) {
- return i - j;
- } else {
- i = oldi + 1;
- }
- }
- return -1;
- }
- };
暴力
[30] Substring with Concatenation of All Words
[32] Longest Valid Parentheses
[38] Count and Say
[43] Multiply Strings(2018 年 11 月 27 日, 高精度乘法)
给了两个 string 类型的数字, num1 和 num2, 用 string 的形式返回 num1 * num2.(num1, num2 的长度都小于等于 110)
题解: num3 = num1 * num2, num3 最大的长度为 num1.size() + num2.size(). 先翻转 num1, num2, 翻转以后从前往后乘. 可能最后结果有前置 0, 把前置 0 去除.
- class Solution {
- public:
- string multiply(string num1, string num2) {
- size1 = num1.size(), size2 = num2.size();
- v1 = str2vecAndReverse(num1), v2 = str2vecAndReverse(num2);
- vector<int> v3(size1 + size2, 0);
- for (int i = 0; i <size1; ++i) {
- for (int j = 0 ; j < size2; ++j) {
- v3[i+j] += v1[i] * v2[j];
- v3[i+j+1] += v3[i+j] / 10;
- v3[i+j] = v3[i+j] % 10;
- }
- }
- string ret = "";
- for (auto n : v3) {
- ret = to_string(n) + ret;
- }
- auto p = ret.find_first_not_of('0');
- if (p == string::npos) {
- ret = "0";
- } else {
- ret = ret.substr(p);
- }
- return ret;
- }
- vector<int> str2vecAndReverse(string num) {
- int size = num.size();
- vector<int> ret(size);
- for (int i = size - 1; i>= 0; --i) {
- ret[size-i-1] = num[i] - '0';
- }
- return ret;
- }
- int size1 = 0, size2 = 0;
- vector<int> v1, v2;
- };
- View Code
[44] Wildcard Matching
[49] Group Anagrams(2019 年 1 月 23 日, 谷歌 tag 复习)
给了一个单词列表, 给所有的异构词分组.
- Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
- Output:
- [
- ["ate","eat","tea"],
- ["nat","tan"],
- ["bat"]
- ]
题解: 我的解法, hashmap + sort. 不是最优秀的解法. 还有什么用 26 个素数代替法, 这个更快吧.
代码不贴了.
[58] Length of Last Word
[65] Valid Number
[67] Add Binary
[68] Text Justification
[71] Simplify Path
[72] Edit Distance
[76] Minimum Windows Substring
[87] Scramble String
[91] Decode Ways
[93] Restore IP Addresses
[97] Interleaving String
[115] Distinct Subsequences
[125] Valid Palindrome
[126] Word Ladder II
[151] Reverse Words in a String(2018 年 11 月 8 日, 原地翻转字符串)
- Input: "the sky is blue",
- Output: "blue is sky the".
题解: 用 stringstream 能做.
- class Solution {
- public:
- void reverseWords(string &s) {
- stringstream iss(s);
- string temp;
- iss>> s;
- while (iss>> temp) {
- s = temp + " " + s;
- }
- if (isspace(s[0])) {s = "";}
- return;
- }
- };
[157] Read N Characters Given Read4
[158] Read N Characters Given Read4 II - Call multiple times
[159] Longest Substring with At Most Two Distinct Characters(2019 年 1 月 29 日, 谷歌 tag 复习)
给定一个字符串 s, 返回它最长的子串的长度, 子串要求只能有两个 distinct characters.
题解: sliding Windows.(time complexity is O(N))
- class Solution {
- public:
- int lengthOfLongestSubstringTwoDistinct(string s) {
- const int n = s.size();
- int ans = 0;
- int begin = 0, end = 0, cnt = 0;
- unordered_map<char, int> mp;
- while (end <n) {
- mp[s[end]]++;
- if (mp[s[end]] == 1) {
- ++cnt;
- }
- if (cnt <= 2) {
- ans = max(ans, end - begin + 1);
- }
- while (cnt> 2) {
- mp[s[begin]]--;
- if (mp[s[begin]] == 0) {
- --cnt;
- }
- ++begin;
- }
- end++;
- }
- return ans;
- }
- };
- View Code
[161] One Edit Distance(2018 年 11 月 24 日, 刷题数)
给了两个字符串 s 和 t, 问 s 能不能通过 增加一个字符, 删除一个字符, 替换一个字符 这三种操作里面的任意一个变成 t. 能的话返回 true, 不能的话返回 false.
题解: 感觉是基础版的编辑距离. 直接通过模拟来做. beats 36%. 时间复杂度是 O(N).
- class Solution {
- public:
- bool isOneEditDistance(string s, string t) {
- if (s == t) {return false;}
- const int ssize = s.size(), tsize = t.size();
- int cnt = 0;
- if (ssize == tsize) { //check replace;
- int idx = findfirstidx(s, t);
- if (idx == ssize || s.substr(idx+1) == t.substr(idx+1)) {
- return true;
- }
- } else if (ssize == tsize - 1) { //check insert
- int idx = findfirstidx(s, t);
- if (idx == tsize || s.substr(idx) == t.substr(idx+1)) {
- return true;
- }
- } else if (ssize == tsize + 1){ //check delete
- int idx = findfirstidx(s, t);
- if (idx == ssize || s.substr(idx+1) == t.substr(idx)) {
- return true;
- }
- }
- return false;
- }
- inline int findfirstidx (string s, string t) {
- const int ssize = s.size(), tsize = t.size();
- int tot = min(ssize, tsize);
- for (int i = 0; i <tot; ++i) {
- if (s[i] != t[i]) {
- return i;
- }
- }
- return max(ssize, tsize);
- }
- };
- View Code
[165] Compare Version Numbers
[186] Reverse Words in a String II(2018 年 11 月 8 日, 原地翻转字符串)
Given an input string, reverse the string Word by Word.
- Example:
- Input: ["t","h","e","","s","k","y"," ","i","s"," ","b","l","u","e"]
- Output: ["b","l","u","e","","i","s"," ","s","k","y"," ","t","h","e"]
- Note:
- A Word is defined as a sequence of non-space characters.
- The input string does not contain leading or trailing spaces.
- The words are always separated by a single space.
题解: 无.
- class Solution {
- public:
- void reverseWords(vector<char>& str) {
- reverse(str.begin(), str.end());
- const int n = str.size();
- int p1 = 0, p2 = 0;
- while (p2 <n) {
- while (p1 < n && str[p1] == ' ') {p1++;}
- p2 = p1;
- while (p2 < n && str[p2] != ' ') {p2++;}
- reverse(str.begin() + p1, str.begin() + p2);
- p1 = p2;
- }
- return;
- }
- };
- View Code
[214] Shortest Palindrome(2018 年 11 月 2 日, 周五, 算法群)
给了一个字符串 S, 为了使得 S 变成回文串可以在前面增加字符, 在增加最少的字符的前提下返回新的回文 S.
题解: 我的做法跟昨天的题一样 (366) 就是找从第一个字符开始最长的回文串, 然后把后面的那小段翻转一下, 拼到前面. 时间复杂度是 O(N^2)
- // 类似的题目可以见 336 Palindrome Pairs
- class Solution {
- public:
- string shortestPalindrome(string s) {
- const int n = s.size();
- string ans = "";
- for (int j = n; j>= 0; --j) {
- if (isPalindrome(s, 0, j-1)) {
- string str = s.substr(j);
- reverse(str.begin(), str.end());
- ans = str + s;
- break;
- }
- }
- return ans;
- }
- bool isPalindrome(const string& s, int start, int end) { //[start, end]
- while (start <end) {
- if (s[start] != s[end]) {return false;}
- start++, end--;
- }
- return true;
- }
- };
- View Code
应该还有更好的解法:(学习学习学习).
[227] Basic Calculator II
[249] Group Shifted Strings
[271] Encode and Decode Strings
[273] Integer to English Words
[293] Flip Game
[336] Palindrome Pairs(2018 年 11 月 1 日, 周四, 算法群)
给了一组字符串 words, 找出所有的 pair (i,j), 使得 words[i] + words[j] 这个新的字符串是回文串.
题解: 这题 WA 出了天际. 因为 map 似乎一旦访问了某个不存在的 key, 这个 key 就变的存在了.. 一开始我想暴力, 暴力超时, 暴力时间的时间复杂度是 O(N^2*K). 后来认真思考了一下一个字符串是怎么变成回文的. 如果一个字符串 Word, 他的长度是 n, 如果它的前半段 Word[0..j] 是个回文串, 那么我们需要匹配它后面那段 Word[j+1..n-1], 我们把后半段 reverse 一下, 查找字符串集合 (map) 里面有没有对应的这段. 同理, 如果它的后半段 Word[j+1..n-1] 是个回文串, 那么我们把前半段 reverse 一下, 在 map 里面查找有没有前半段就可以了. 特别注意这个前半段和后半段都可以包含空串, 所以 j 的范围是[0, n].
- class Solution {
- public:
- vector<vector<int>> palindromePairs(vector<string>& words) {
- const int n = words.size();
- unordered_map<string, int> mp;
- for (int i = 0; i <n; ++i) {
- mp[words[i]] = i;
- }
- vector<vector<int>> ans;
- set<vector<int>> st;
- for (int i = 0; i <n; ++i) {
- string Word = words[i];
- int size = Word.size();
- for (int j = 0; j <= size; ++j) {
- if (isPalindrome(Word, 0, j-1)) {
- string str = Word.substr(j);
- reverse(str.begin(), str.end());
- //vector<int> candidate = vector<int>{mp[str], i}; 这个不能放在外面, 不然 mp[str]可能不存在
- if (mp.find(str) != mp.end() && mp[str] != i) {
- vector<int> candidate = vector<int>{mp[str], i};
- if (st.find(candidate) == st.end()) {
- ans.push_back(candidate);
- st.insert(candidate);
- }
- }
- }
- if (isPalindrome(Word, j, size-1)) {
- string str = Word.substr(0, j);
- reverse(str.begin(), str.end());
- //vector<int> candidate = vector<int>{i, mp[str]};
- if (mp.find(str) != mp.end() && mp[str] != i) {
- vector<int> candidate = vector<int>{i, mp[str]};
- if (st.find(candidate) == st.end()) {
- ans.push_back(candidate);
- st.insert(candidate);
- }
- }
- }
- }
- }
- return ans;
- }
- bool isPalindrome(const string& Word, int start, int end) { // [start, end]
- while (start <end) {
- if (Word[start++] != Word[end--]) { return false; }
- }
- return true;
- }
- };
- View Code
听说这题还能用 trie 解, 有空要看答案啊.
[340] Longest Substring with At Most K Distinct Characters(2019 年 1 月 29 日, 谷歌 tag 复习)
类似题: 159. Longest Substring with At Most 2 Distinct Characters, sliding Windows 一模一样的. 时间复杂度是 O(N)
- class Solution {
- public:
- int lengthOfLongestSubstringKDistinct(string s, int k) {
- const int n = s.size();
- if (n <= k) {return n;}
- int begin = 0, end = 0, cnt = 0;
- unordered_map<char, int> mp;
- int ans = 0;
- while (end <n) {
- mp[s[end]]++;
- if (mp[s[end]] == 1) {
- ++cnt;
- }
- if (cnt <= k) {
- ans = max(ans, end - begin + 1);
- }
- while (cnt> k) {
- mp[s[begin]]--;
- if (mp[s[begin]] == 0) {
- --cnt;
- }
- ++begin;
- }
- ++end;
- }
- return ans;
- }
- };
- View Code
[344] Reverse String(2018 年 12 月 3 日, 第一次 review,ko)
逆序一个字符串.
题解: 直接 reverse, 或者 2 pointers
- class Solution {
- public:
- string reverseString(string s) {
- int start = 0, end = s.size() - 1;
- while (start <end) {
- swap(s[start++], s[end--]);
- }
- return s;
- }
- };
- View Code
[345] Reverse Vowels of a String(2018 年 12 月 4 日, 第一次 review,ko)
逆序一个字符串的元音字母.
题解: 2 pointers
- class Solution {
- public:
- string reverseVowels(string s) {
- set<char> setVowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
- int left = 0, right = s.size()-1;
- while (left <right) {
- while (setVowels.find(s[left]) == setVowels.end()) {++left;}
- while (setVowels.find(s[right]) == setVowels.end()) {--right;}
- if (left < right) { // 这里需要再次判断
- swap(s[left++], s[right--]);
- }
- }
- return s;
- }
- };
- View Code
[383] Ransom Note
[385] Mini Parser
[387] First Unique Character in a String
[408] Valid Word Abbreviation
[434] Number of Segments in a String
[443] String Compression
[459] Repeated Substring Pattern
[468] Validate IP Address(2018 年 12 月 7 日)
判断一个字符串是不是有效的 IP 地址, 区分 IPv4 和 IPv6, 都不是的话返回 Neither.IPv4 的判断很简单, 就是用 '.' 隔开的四段数字, 然后每段数字都在 0~255 中间, 数字没有前导 0. IPv6 的判断比较麻烦, 是八段用 ':' 隔开是数字, 每段数字都是四位十六进制数. 四位数字如果有前置 0 的话, 可以省略, 以及大小写都可以忽略不同.
题解: 比较复杂的模拟题. 我用 getline 分割字符串, 注意如果 它已经有 7 个 ':' 分割八段十六进制数之后, 如果在尾部还有一个 ':' , 那么这个要特判.
- #define NEITHER "Neither"
- #define IPV4 "IPv4"
- #define IPV6 "IPv6"
- class Solution {
- public:
- string validIPAddress(string IP) {
- if (IP.find(':') != string::npos) {
- return checkIPV6(IP);
- }
- return checkIPV4(IP);
- }
- string checkIPV4(string IP) {
- int cnt = 0;
- string Word;
- stringstream ss;
- ss << IP;
- if (IP.front() == '.' || IP.back() == '.') {return NEITHER;}
- while (getline(ss, Word, '.')) {
- cnt++;
- if (Word.size()> 3 || Word.empty()) {return NEITHER;}
- for (int i = 0; i <Word.size(); ++i) {
- if (i == 0 && Word[i] == '0' && Word.size()> 1 || !isdigit(Word[i])) {
- return NEITHER;
- }
- }
- int num = stoi(Word);
- if (num <0 || num> 255) {return NEITHER;}
- }
- if (cnt != 4) {
- return NEITHER;
- }
- return IPV4;
- }
- string checkIPV6(string IP) {
- int cnt = 0;
- string Word;
- stringstream ss;
- ss <<IP;
- if (IP.front() == ':' || IP.back() == ':') {return NEITHER;}
- while (getline(ss, Word, ':')) {
- cnt++;
- printf("word = %s \n", Word.c_str());
- if (Word.size()> 4 || Word.empty()) {return NEITHER;}
- for (int i = 0; i <Word.size(); ++i) {
- char c = Word[i];
- if (!isalnum(c) || c> 'f' && c <= 'z' || c> 'F' && c <= 'Z') {
- return NEITHER;
- }
- }
- }
- if (cnt != 8) {
- return NEITHER;
- }
- return IPV6;
- }
- };
- View Code
[520] Detect Capital
[521] Longest Uncommon Subsequence I
[522] Longest Uncommon Subsequence II
[527] Word Abbreviation
[536] Construct Binary Tree from String
[537] Complex Number Multiplication(2018 年 11 月 27 日)
给了两个字符串, 代表两个 complex, 返回这两个 complex 的乘积(用字符串表示).
题解: 见 math 分类: https://www.cnblogs.com/zhangwanying/p/9790007.html
[539] Minimum Time Difference
[541] Reverse String II
[544] Output Contest Matches
[551] Student Attendance Record I
[553] Optimal Division
[555] Split Concatenated Strings
[556] Next Greater Element III
[557] Reverse Words in a String III
[564] Find the Closest Palindrome
[583] Delete Operation for Two Strings
[591] Tag Validator
[606] Construct String from Binary Tree
2018 年 11 月 14 日, 树的分类里面做了: https://www.cnblogs.com/zhangwanying/p/6753328.html
[609] Find Duplicate File in System
[616] Add Bold Tag in String
[632] Smallest Range
[635] Design Log Storage System
[647] Palindromic Substrings
[657] Robot Return to Origin
[678] Valid Parenthesis String
[680] Valid Palindrome II
[681] Next Closest Time(2019 年 1 月 29 日, 谷歌 tag 复习)
给了一个字符串, 代表时间, HH:MM, 返回用当前数字组成的合法的下一个时间. There is no limit on how many times a digit can be reused.
- Input: "19:34"
- Output: "19:39"
- Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later. It is not 19:33, because this occurs 23 hours and 59 minutes later.
- Input: "23:59"
- Output: "22:22"
- Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22. It may be assumed that the returned time is next day's time since it is smaller than the input time numerically.
题解: 思路就是先把所有的四个数字存下来, 从最小的 (分针) 开始往前找, 如果找到了比当前位置更大的一个数的话, 就用这个更大的数字去代替当前的数字.(前提是这个更大的数字代替完了之后这个时间得合法.)如果找到最大的位置都没有找到的话, 那就用最小的数字生成一个第二天的时间来作为新的数字.
- class Solution {
- public:
- string nextClosestTime(string time) {
- set<int> st;
- int minn = 10;
- for (int i = 0; i <5; ++i) {
- if (isdigit(time[i])) {
- int t = time[i] - '0';
- minn = min(t, minn);
- st.insert(t);
- }
- }
- if (st.size() == 1) {return time;} //invalid
- string ret = time;
- for (int i = 4; i>= 0; --i) {
- char c = ret[i];
- int t = c - '0';
- auto iter = upper_bound(st.begin(), st.end(), t);
- if (iter == st.end()) {continue;}
- if (i == 0 && *iter> 2) {
- continue;
- }
- if (i == 1 && *iter> 4 && ret[0] == '2') {
- continue;
- }
- if (i == 3 && *iter> 5) {
- continue;
- }
- ret[i] = (*iter) + '0';
- for (int k = i + 1; k <5; ++k) {
- if (isdigit(ret[k])) {
- ret[k] = minn + '0';
- }
- }
- break;
- }
- if (ret == time) {
- for (auto& c : ret) {
- if (isdigit(c)) {
- c = minn + '0';
- }
- }
- }
- return ret;
- }
- };
- View Code
[686] Repeated String Match
[696] Count Binary Substrings
[709] To Lower Case
[722] Remove Comments
[730] Count Different Palindromic Subsequences
[736] Parse Lisp Expression
[758] Bold Words in String
[761] Special Binary String
[767] Reorganize String
[770] Basic Calculator IV
[772] Basic Calculator III
[788] Rotated Digits
[791] Custom Sort String(2018 年 11 月 27 日)
给了两个字符串 S 和 T, S 中最多有 26 个小写字母, 给 T 重新排序, 如果字母 x, y 在 S 中出现, 且在 T 中出现, 如果在 S 中 x 出现在 y 之前, 那么在 T 中 x 也要出现在 y 之前. 没有在 S 中出现的字符就随便放哪里都可以.
题解: 直接 unordered_map
- class Solution {
- public:
- string customSortString(string S, string T) {
- const int n = T.size();
- unordered_map<char, int> mp;
- for (int i = 0; i <n; ++i) {
- mp[T[i]]++;
- }
- string ret;
- for (auto c : S) {
- if (mp.find(c) == mp.end() || mp[c] == 0) {continue;}
- ret += string(mp[c], c);
- mp[c] = 0;
- }
- for (auto ele : mp) {
- if (ele.second> 0) {
- ret += string(ele.second, ele.first);
- }
- }
- return ret;
- }
- };
- View Code
[800] Similar RGB Color
[804] Unique Morse Code Words
[809] Expressive Words
[816] Ambiguous Coordinates
[819] Most Common Word
[824] Goat Latin
[831] Masking Personal Information
[833] Find And Replace in String
[842] Split Array into Fibonacci Sequence
[848] Shifting Letters
[856] Score of Parentheses
[859] Buddy Strings
[890] Find and Replace Pattern
[893] Groups of Special-Equivalent Strings
[899] Orderly Queue
来源: http://www.bubuko.com/infodetail-2938766.html