String-Medium

2020-04-25
Abstract：leetcode 字符串中等难度合集

6. ZigZag Conversion

image-20200425185253744

解法一

逻辑本质上相当于交替输出123212321这样的字符串，所以没什么可说的。。就是要注意一下numRows 为1时记得直接return，否则idx会越界

不过官方题解和我写的基本上一样呢 /惊/

class Solution {
public:
    std::vector<std::string> rows;
    string convert(string s, int numRows) {
        if(numRows == 1) return s;
        rows = std::vector<std::string>(numRows);
        bool turn = false;
        for (int i = 0, idx = 0;i<s.length();i++) {
            rows[idx] += s[i];
            if (idx == 0 || idx == numRows - 1) turn = !turn;
            idx += turn ? 1 : -1;
        }

        std::string ans;
        for (std::string row : rows) 
            ans += row;
        return ans;
    }
};

522. Longest Uncommon Subsequence II

image-20200426125725779

解法一：暴力搜索

递归搜索每个字符串的所有子序列，放入unordered_map中，如果出现次数为1，进行比较，求出最大值

class Solution {
public:
	int findLUSlength(vector<string>& strs) {
		unordered_map<string, int> map;
		for (string s : strs)
			mapAllSubseq(s, 0, "", map);

		int max = 0;
		for (auto& key : map) {
			if (key.second == 1)
				max = key.first.length() > max ? key.first.length() : max;
		}
        return max == 0 ? -1 : max;
	}

	void mapAllSubseq(string s, int idx, string res, unordered_map<string, int>& map) {
		if (idx == s.length()) {
			map[res]++;
			return;
		}
		mapAllSubseq(s, idx + 1, res, map);          // 放弃第idx位
		mapAllSubseq(s, idx + 1, res + s[idx], map); // 不放弃第idx位
	}
};

解法二：判断子序列

  • 首先，最大长度肯定是某一串的长度

  • 注意第二层循环要从0开始，因为在某串之前的串不一定比此串短，也有可能长度相等，否则会把重复串的长度当成解

class Solution {
public:
	bool isSubseq(string a, string b) {
        if(a.length() > b.length()) return false;
		for (int i = 0, idx = 0; i < b.length(); i++) {
			if (b[i] == a[idx])     idx++;
			if (idx  == a.length()) return true;
		}
		return false;
	}

	int findLUSlength(vector<string>& strs) {
        int max = 0;
		for (int i = 0, j; i < strs.size(); i++) {
			bool flag = true;
			for (j = 0; j < strs.size(); j++) {
				if (i == j)
					continue;
				if (isSubseq(strs[i], strs[j])) {
					flag = false;
					break;
				}
			}
			if (flag && strs[i].length() > max)
                max = strs[i].length(); 
		}
		return max == 0 ? -1 : max;
	}
};

解法三：先排序再判断子序列

先排序，那么按照解法二得到的第一个结果就是解，不需要继续遍历求max

由于排序的消耗比继续判断子序列的消耗要小，因此排序的结果略快一些

class Solution {
public:
	static int compare(string a, string b) {
		return a.length() > b.length();
	}

	bool isSubseq(string a, string b) {
		if (a.length() > b.length()) return false;
		for (int i = 0, idx = 0; i < b.length(); i++) {
			if (b[i] == a[idx])     idx++;
			if (idx == a.length()) return true;
		}
		return false;
	}

	int findLUSlength(vector<string>& strs) {
		std::sort(strs.begin(), strs.end(), compare);
		for (int i = 0, j; i < strs.size(); i++) {
			bool flag = true;
			for (j = 0; j < strs.size(); j++) {
				if (i == j)
					continue;
				if (isSubseq(strs[i], strs[j])) {
					flag = false;
					break;
				}
			}
			if (flag)
				return strs[i].length();
		}
		return -1;
	}
};

537. Complex Number Multiplication

image-20200426152212362

解法一：std::stoi() & std::to_string()

一开始以为要用字符串先模拟乘法再模拟加法，但是看大家都直接上库函数，那我也只好恭敬不如从命了

class Solution {
public:
    string complexNumberMultiply(string a, string b) {
	int i = 0, j = 0;
	for (i; a[i] != '+'; i++);
	for (j; b[j] != '+'; j++);
	int re_a = std::stoi(a.substr(0, i)),
		im_a = std::stoi(a.substr(i + 1, a.length() - 1)),
		re_b = std::stoi(b.substr(0, j)),
		im_b = std::stoi(b.substr(j + 1, b.length() - 1));
	std::string ans = std::to_string(re_a * re_b - im_a * im_b) + "+" 
					+ std::to_string(re_a * im_b + re_b * im_a)+ "i";
    return ans;
    }
};

43. Multiply Strings

image-20200427235742024

解法一：耿直模拟竖式

模拟竖式乘法，先模拟一位数乘N位数，再累加

但是我写的比较烂…正解请看优化版

class Solution {
public:
	string multiply(string num1, string num2) {
		std::string res = "0";
		if (num1 == "0" || num2 == "0") return "0";
		for (int i = num2.length() - 1; i > -1; i--) {
			std::string val = multi(num1, num2[i]);
			for (int k = 0; k < num2.length() - i - 1; k++)
				val += '0';
			res = add(res, val);
		}
		return res;
	}

	std::string multi(const std::string& a, char b) {
		if (b == '0') return "0";
		int y = b - '0', carry = 0;
		std::string res = "";
		for (int i = a.length() - 1; i > -1; i--) {
			int x = a[i] - '0';
			int val = x * y + carry;
			if (val > 9) {
				carry = val / 10;
				val = val % 10;
			}
			else carry = 0;
			res = std::to_string(val) + res;
		}
		if (carry > 0) res = std::to_string(carry) + res;
		return res;
	}

	std::string add(const std::string& a, const std::string& b) {
		int carry = 0, i = a.length() - 1, j = b.length() - 1;
		std::string res = "";
		while (i >= 0 || j >= 0) {
			int x = i >= 0 ? a[i--] - '0' : 0;
			int y = j >= 0 ? b[j--] - '0' : 0;
			int sum = x + y + carry;
			if (sum > 9) {
				carry = 1;
				sum -= 10;
			}
			else carry = 0;
			res = std::to_string(sum) + res;
		}
		if (carry > 0) res = '1' + res;
		return res;
	}
};

解法二：优化版竖式

131. Palindrome Partitioning

image-20200504015642936

解法一：回溯法

class Solution {
public:
    vector<vector<string>> res;
    vector<string> tmp;
    vector<vector<string>> partition(string s) {
        getPartition(s);
        return res;
    }

    void getPartition(string s){
        if(s.empty()) {
            res.push_back(tmp);
            return;
        }
        for(int i = 0; i < s.length(); i++){
            string sub = s.substr(0, i + 1);
            if(isPalindrome(sub)){
                tmp.push_back(sub);
                getPartition(s.substr(i + 1, s.length()));
                tmp.pop_back();
            }
        }
    }

    bool isPalindrome(const string& s){
        if(s.empty()) return false;
        int lo = 0, hi = s.length() - 1;
        while(lo <= hi)
            if(s[lo++] != s[hi--]) 
                return false;
        return true;
    }
};

解法二：优化版

179. Largest Number

image-20200506134117681

解法一：字典逆序

本质就是排字典序，可以自己写一个，也可以直接用string重载的比较运算符

class Solution {
public:
    static bool compare(const string a, const string b){
        int len = std::min(a.length(), b.length());
        for (int i = 0; i < len; i++)
            if(a[i] != b[i]) return a[i] > b[i];
        if (a.length() > b.length()) 
            return compare(a.substr(len, a.length()),b); 
        else if (a.length() < b.length()) 
            return compare(a, b.substr(len, b.length()));
        return 0;
    }
    
    string largestNumber(vector<int>& nums) {
        vector<string> numbers = vector<string>(nums.size());
        for(int i = 0; i < nums.size(); i++) 
            numbers[i] = to_string(nums[i]);
        std::sort(numbers.begin(), numbers.end(), compare);
        string res = "";
        for(string s : numbers)
            res += s;
        bool zero = true;
        for(char c : res) if(c != '0') zero = false;
        if(zero) return "0";
        return res;
    }

};

解法二：string自带的比较运算

static bool compare(const string a, const string b){
    return a + b > b + a;
}

187. Repeated DNA Sequences

image-20200506144355883

解法一：unordered_set & unordered_map

不必多说，注意长度小于10时直接return

unordered_set：

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        if(s.length() < 10) return {};
        unordered_set<string> set, ans;
        vector<string> res;
        for (int start = 0; start < s.length() - 9; start++) {
            string curr = s.substr(start, 10);
            if(set.find(curr) == set.end()) 
                set.insert(curr);
            else
                ans.insert(curr);
        }

        for (auto k : ans)
            res.push_back(k);
        return res;
    }
};

unordered_map：

// ....
map[curr]++;
// ....
for (auto k : map)
    if(k.second > 0) res.push_back(k.first);
return res;

解法二：

49. Group Anagrams

image-20200509024036177

解法一：排序 + unordered_map

用排序来判断异位词，用哈希存各异位词的分组

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string, vector<string>> map;
        for(int i = 0; i < strs.size(); i++) {
            string s = strs[i];
            std::sort(s.begin(), s.end());
            map[s].push_back(strs[i]);
        }

        for(auto k : map)
            res.push_back(k.second);
        return res;
    }
};

151. Reverse Words in a String

image-20200510174413303

解法一：模拟

水平有限，写得很乱。。

class Solution {
public:
    string reverseWords(string s) {
        int i = 0, j = s.length() - 1;
        while(i <= j && s[i] == ' ') i++;
        while(j > 0  && s[j] == ' ') j--;
        if(i > j) return "";
        s = s.substr(i, j - i + 1);
        return reverse(s);
    }

    string reverse(string s) {
        string res = "", tmp = "";
        for(int i = 0; i < s.length(); i++) {
            if (s[i] == ' ') {
                if(tmp.empty()) continue;
                res = res.empty() ? tmp : tmp + " " + res;
                tmp.clear();
            }
            else tmp += s[i];
            if(i == s.length() - 1)
                res = res.empty() ? tmp : tmp + " " + res;
        }
        return res;
    }
};

165. Compare Version Numbers

image-20200512145627513

解法一：分割转整数

一开始开以为是字典序比较，没想到是整数比较

class Solution {
public:
    int compareVersion(string version1, string version2) {
        vector<int> v1 = split(version1), v2 = split(version2);
        for(int i = 0; i < v1.size() || i < v2.size(); i++) {
           int n1 = i < v1.size() ? v1[i] : 0;
           int n2 = i < v2.size() ? v2[i] : 0;
           if(n1 > n2) return 1;
           else if(n1 < n2) return -1;
        }  
        return 0;
    }

    vector<int> split(std::string s) {
        string tmp = "";
        vector<int> v;
        for(int i = 0; i < s.length(); i++) {
            if(s[i] == '.') {
                if(!tmp.empty()) {
                    v.push_back(stoi(tmp));
                    tmp.clear();
                }
            }
            else tmp += s[i];
            if(i == s.length() - 1 && !tmp.empty())
                v.push_back(stoi(tmp));  
        }
        return v;
    }
};

394. Decode String

image-20200515192458782

解法一：递归法

  • 正常情况下直接加入结果
  • 如果遇到数字，先解析数字
  • 然后匹配对应的 “]”，将括号中间的子串递归地解码，然后重复cnt次
class Solution {
public:
    // 将字符串重复k次
    string genString(int k, string a) {
        string res;
        for(int i = 0; i < k; i++)
            res += a;
        return res;
    }
    
    // 计算对应的']'的索引
    int matchIndex(string s, int k, int start) {
        for(int i = start; i < s.length(); i++) {
            if(s[i] == ']') {
                if(k == 1) return i;
                else --k;
            }
            else if(s[i] == '[')
                return matchIndex(s, k + 1, i + 1);
        }
        return -1;
    }

    string decodeString(string s) {
        string res;
        for(int i = 0; i < s.length(); i++) {
            if(isdigit(s[i])) {
                // 解析数字
                int cnt = s[i] - '0';
                while(isdigit(s[i + 1])){
                    i++;
                    cnt = cnt * 10 + s[i] - '0';
                }

                int idx = matchIndex(s, 1, i + 2);           // 找到右括号所在的位置
                string recur = s.substr(i + 2, idx - i - 2);
                recur = decodeString(recur);                 // 递归求解
                res += genString(cnt, recur);                // 生成
                i = idx;                                     // i移动到右括号处 
                continue;
            }
            else if(i < s.length()) res += s[i];
        }
        return res;
    }
};

647. Palindromic Substrings

image-20200519134014730

解法一：中心扩展法

同最长回文子串，单个字符也算，所以cnt初始为1

class Solution {
public:
    int countSubstrings(string s) {
        int res = 0;
        for(int i = 0; i < s.length(); i++) {
            res += countPalindrome(s, i, i);
            if(i != s.length() - 1 && s[i] == s[i + 1])
                res += countPalindrome(s, i, i + 1);
        }
        return res;
    }

    int countPalindrome(string s, int i, int j) {
        int cnt = 1;
        while(i > 0 && j < s.length() - 1) {
            if(s[i - 1] != s[j + 1])
                return cnt;
            cnt++; i--; j++;
        }
        return cnt;
    }
};

1371. Find the Longest Substring Containing Vowels in Even Counts

image-20200520131929011

解法一：状压DP

只想到了vector来点乘的方法，此为官方解

  • 用一个5位bit表示各字符的状态
  • c为元音时异或对应的位
  • 当前缀存在一个相同状态时，更新最大长度，而不更新当前位置
  • 否则记录当前位置
class Solution {
public:
    int findTheLongestSubstring(string s) {
        int res = 0, status = 0, n = s.length();
        vector<int> dp(1 << 5, -1);
        dp[0] = 0;
        vector<int> vowel = {'a','e','i','o','u'};
        for(int i = 0; i < s.length(); i++) {
            for(int k = 0; k < 5; k++)
                if(s[i] == vowel[k]) status ^= 1 << k;
            
            if(dp[status] != -1)
                res = std::max(res, i - dp[status] + 1);
            else
                dp[status] = i + 1;
        }
        return res;
    }
};
© 2020 Overyam - Powered by Hexo - Theme Chan