字符串问题-LeetCode 392、383、386、384、396、937（字符串）
字符串问题-LeetCode 392、383、386、384、396、937（字符串）
作者：TeddyZhang，公众号：算法工程师之路
字符串问题：
LeetCode # 392 383 386 384 396 937
1
编程题
【LeetCode #392】判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例 1: s = "abc", t = "ahbgdc"
解题思路：
使用两个索引，如果对应字符相同，两个索引同时++，然后如果不同，则t的索引++。
class Solution {
public:
bool isSubsequence(string s, string t) {
if (s == "") return true;
int c1 = , c2 = ;
while(c1 < s.length() && c2 < t.length()) {
if (s[c1] == t[c2]) {
c1 ++; c2 ++;
} else {
c2 ++;
}
}
return c1 == s.length();
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/is-subsequence
【LeetCode #383】赎金信
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成。如果可以构成，返回 true ；否则返回 false。 (题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。)
注意： 你可以假设两个字符串均只含有小写字母。 canConstruct("a", "b") -> false canConstruct("aa", "ab") -> false canConstruct("aa", "aab") -> true
解题思路：
使用ch_cnt数组用来记录每个字符出现的次数，只要ransomNote中字符的次数小于magazine中字符的次数就好了。与上一题不同的是，本题不需要考虑字符出现的顺序，而子串需要。
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int ch_cnt[] = {};
for(auto ch: magazine) {
ch_cnt[ch-'a']++;
}
for(auto ch: ransomNote) {
ch_cnt[ch-'a']--;
if (ch_cnt[ch-'a'] < ) return false;
}
return true;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/ransom-note
【LeetCode #386】字典序排数
给定一个整数 n, 返回从 1 到 n 的字典顺序。 例如， 给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。 请尽可能的优化算法的时间复杂度和空间复杂度。输入的数据 n 小于等于 5,000,000。
解题思路：由于STL中的map是自动按key排序的，因此字典序其实就是数字对应字符串的排序。
class Solution {
public:
vector<int> lexicalOrder(int n) {
map<string, int> nums;
vector<int> res;
for(int i = ; i <= n; i++) {
nums[to_string(i)] = i;
}
for(auto num: nums) {
res.push_back(num.second);
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/lexicographical-numbers
【LeetCode #384】打乱数组
打乱一个没有重复元素的数组。
class Solution {
public:
Solution(vector<int>& nums) : nums_(nums) {}
/** Resets the array to its original configuration and return it. */
vector<int> reset() {
return nums_;
}
/** Returns a random shuffling of the array. */
vector<int> shuffle() {
vector<int> tmp(nums_.begin(), nums_.end());
for(int i = ; i < tmp.size(); i++) {
int r = rand() % (i+);
if (r != i) {
swap(tmp[r], tmp[i]);
}
}
return tmp;
}
private:
vector<int> nums_;
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/shuffle-an-array/
【LeetCode #396】旋转函数
给定一个长度为 n 的整数数组 A 。 假设 Bk 是数组 A 顺时针旋转 k 个位置后的数组，我们定义 A 的“旋转函数” F 为： F(k) = 0 * Bk[0] + 1 * Bk[1] + … + (n-1) * Bk[n-1]。 计算F(0), F(1), …, F(n-1)中的最大值。 注意: 可以认为 n 的值小于 105。
解题思路：
这道题目是找规律题目，思路是首先计算得到F(0)，由于数组会过大导致越界，因此选择longlong类型，然后每个F(n)等于上一个F(n-1)的前n-1项和相加再减去最后一项数。
class Solution {
public:
long long res, maxi, total, n;
int maxRotateFunction(vector<int>& A) {
n = A.size();
for(int i = ; i < n; i++) {
res += A[i] * i;
total += A[i];
}
maxi = res;
for(int i = n-1; i > ; i--) {
maxi -= (n-1)*(long long)A[i];
maxi += total - A[i];
res = max(res, maxi);
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/rotate-function
【LeetCode #937】重新排列日志文件
你有一个日志数组 logs。每条日志都是以空格分隔的字串。 对于每条日志，其第一个字为字母数字标识符。然后，要么：
- 标识符后面的每个字将仅由小写字母组成，或；
- 标识符后面的每个字将仅由数字组成。
我们将这两种日志分别称为字母日志和数字日志。保证每个日志在其标识符后面至少有一个字。 将日志重新排序，使得所有字母日志都排在数字日志之前。字母日志按内容字母顺序排序，忽略标识符；在内容相同时，按标识符排序。数字日志应该按原来的顺序排列。 返回日志的最终顺序。
示例 ： 输入：["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"] 输出：["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]
解题思路：
题目有点长，大致意思就是：对数字日志和字母日志进行排序，对于数字日志，保持顺序不变，而对于字母日志，第一个日志为标识符，如果内容一样的话就按照标识符排序，否则忽略标识符，按照内容排序。 注意区别数字和字母日志的方法就是最后一个字母是否为数字字符！
class Solution {
public:
vector<string> reorderLogFiles(vector<string>& logs) {
vector<string> nums, txts;
for(auto log: logs) {
int len = log.length();
if (log[len - ] >= '0' && log[len - ] <= '9') {
nums.push_back(log);
} else {
txts.push_back(log);
}
}
// 比较器
auto cmp = [](const string& a, const string& b) {
string tmp1, tmp2;
int s1 = a.find(' ');
int s2 = b.find(' ');
tmp1 = a.substr(s1+, a.size()-s1-1);
tmp2 = b.substr(s2+, b.size()-s2-1);
if (tmp1 == tmp2) {
return a < b;
} else {
return tmp1 < tmp2;
}
};
sort(txts.begin(), txts.end(), cmp);
for(int i = ; i < nums.size(); i++) {
txts.push_back(nums[i]);
}
return txts;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reorder-data-in-log-files