本次作业完成了力扣《面试经典 150 题》「数组 / 字符串」部分的全部题目。
力扣 面试经典 150 题 - 数组 / 字符串
LeetCode 42. 接雨水
思路
观察示例说明图片可以发现，第 $i$ 格雨水高度为第 $1\sim i - 1$ 格柱子的最大值和第 $i + 1\sim n$ 格柱子的最大值两个值中的最小值，如果直接为每个格子计算去计算这两个值，复杂度为 $\mathrm O(n^2)$，不能满足数据范围的要求。
不能发现，柱子高度的最大值这一信息是可以传递的，当计算出第 $1 \sim i - 1$ 格柱子高度的最大值后，可以 $\mathrm O(1)$ 计算出 $1 \sim i$ 格柱子高度的最大值。因此，我们便可以以 $\mathrm O(n)$ 的时间复杂度预处理出每个格子左侧的最大值和右侧的最大值。然后，我们再进行一次遍历计算出每个格子的雨水高度即可，总时间复杂度为 $\mathrm O(n)$。
代码
提交记录：12 ms (84.64%) / 20.06 MB (5.55%)
class Solution {
public:
int trap(vector<int>& height) {
vector<int> hmax = {0};
int ans = 0;
for (int i = height.size() - 1; i > -1; --i) hmax.emplace_back(max(hmax.back(), height[i]));
for (int i = 0, nowmax = 0; i < height.size(); ++i) ans += max(0, min(nowmax, hmax[height.size() - i]) - height[i]), nowmax = max(nowmax, height[i]);
return ans;
}
};
LeetCode 13. 罗马数字转整数
思路
首先我们可以先将罗马数字转换为 ASCII 码，再使用字符数组将单个罗马数字转换为数字。接着，我们可以从右往左扫描，不难发现除了 IV 这类情况外，右边的罗马数字对应的数值一定比左边的小，而出现左边较小的情况时，我们发现其数值对答案的贡献刚好是负的，因此我们可以直接根据这一规律计算出答案。
代码
提交记录：4 ms (94.08%) / 6.00 MB (86.34%)
class Solution {
public:
int romanToInt(string s) {
int ans = 0, c2i[] = {0, 0, 100, 500, 0, 0, 0, 0, 1, 0, 0, 50, 1000, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 10};
for (int i = s.length() - 1, lst = 0; i > -1; lst = c2i[s[i--] - 'A'])
ans += c2i[s[i] - 'A'] * (c2i[s[i] - 'A'] < lst? -1 : 1);
return ans;
}
};
LeetCode 12. 整数转罗马数字
思路
我们发现整数到罗马数字的转换是可以按位进行的，因此我们可以从低位到高位依次计算出每一位的罗马数字，再将其拼接起来即可。对于每一位，我们可以特判其是否为 4 或 9，如果是则直接拼接这种特殊情况对应的罗马数字，否则便正常用代表该位上的 $5$ 和 $1$ 的罗马数字拼接即可。
代码
提交记录：0 ms (100.00%) / 5.99 MB (72.73%)
class Solution {
public:
string intToRoman(int num) {
string ans, ch[][2] = {{"I", "V"}, {"X", "L"}, {"C", "D"}, {"M"}};
for (int i = 0, x = num % 10; num; ++i, num /= 10, x = num % 10)
if (x % 5 == 4) ans += (x > 5 ? ch[i + 1][0] + ch[i][0] : ch[i][1] + ch[i][0]);
else {
for (; x % 5; --x) ans += ch[i][0];
if (x > 0) ans += ch[i][1];
}
reverse(ans.begin(), ans.end());
return ans;
}
};
LeetCode 58. 最后一个单词的长度
思路
我们可以从后往前扫描，遇到第一个非空格字符时开始计数，直到遇到空格字符或到达字符串开头为止。
代码
提交记录：0 ms (100.00%) / 6.61 MB (24.99%)
class Solution {
public:
int lengthOfLastWord(string s) {
int ans = 0;
for (int i = s.length() - 1, now = 1; i > -1; --i)
if (s[i] != ' ') now = 0, ++ans;
else if (!now) break;
return ans;
}
};
LeetCode 14. 最长公共前缀
思路
我们可以从前往后扫描，每次扫描时记录当前最长公共前缀，当扫描到第 $i$ 个字符串时，我们可以将当前的最长公共前缀与第 $i$ 个字符串的前缀进行比较，如果不相同则将当前最长公共前缀缩短为两者的最长公共前缀，直到扫描完所有字符串为止。
代码
提交记录：0 ms (100.00%) / 9.02 MB (65.97%)
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
for (int i = 0; ; ++i)
for (int j = 0; j < strs.size(); ++j)
if (i == strs[j].length() || j && strs[j][i] != strs[j - 1][i]) return strs[0].substr(0, i);
}
};
LeetCode 151. 反转字符串中的单词
思路
直接使用 Python 的 split 函数分割字符串，再使用 join 函数拼接，最后使用数组切片方法反转即可。
代码
提交记录：32 ms (98.84%) / 15.75 MB (45.39%)
class Solution:
def reverseWords(self, s: str) -> str:
return ' '.join(s.split()[::-1])
LeetCode 6. N 字形变换
思路
根据规则简单模拟，使用 turn 表示字形变换的方向，now 表示当前字符需要放到答案里的字符串编号，放置结束后，使用 C++ 的 accumulate 函数连接字符串即可。
代码
提交记录：8 ms (91.47%) / 10.23 MB (46.04%)
class Solution {
public:
string convert(string s, int numRows) {
vector<string> ans(numRows, "");
for (int i = 0, now = 0, turn = 1; i < s.length(); now += numRows == 1 ? 0 : turn, turn *= (now && now < numRows - 1) ? 1 : -1, ++i) ans[now] += s[i];
return accumulate(ans.begin(), ans.end(), string(""));
}
};
LeetCode 28. 找出字符串中第一个匹配项的下标
思路
使用 C++ 的 find 函数即可。
代码
提交记录：0 ms (100.00%) / 6.31 MB (46.35%)
class Solution {
public:
int strStr(string haystack, string needle) {
return haystack.find(needle);
}
};
LeetCode 68. 文本左右对齐
思路
我们可以先计算出每一行可以放置的单词数量，再根据每一行可以放置的单词数量计算出每个单词之间需要放置的空格数量，最后再根据每一行可以放置的单词数量特判一下是否为最后一行即可。需要注意的是，如果一行只能放置一个单词，那么我们需要在单词后面补齐空格。
代码
提交记录：0 ms (100.00%) / 7.37 MB (61.00%)
class Solution {
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
int nowLength = words[0].length(), startIndex = 0;
vector<string> ans; // 答案
auto placeWords = [&](int i, int spaceNum, int spaceLeft, int isLeft) { // 将 startIndex ~ i - 1 放置到一行中
ans.emplace_back(""); // 新建一行
string& _ans = ans.back(); // 引用当前行
for (int j = startIndex, space; space = spaceNum + (spaceLeft > 0 ? 2 : 1), j < i; ++j, --spaceLeft) { // 如果还有剩余空格，那么每个单词之间至少需要放置一个空格
_ans += words[j]; // 放置单词
if (j + 1 < i) while(space--) _ans += " "; // 放置空格
}
nowLength = isLeft ? maxWidth - nowLength : 0; // 如果是最后一行，那么剩余空格全部放置在最后
while(nowLength--) _ans += " "; // 放置剩余空格
if (i != words.size()) nowLength = words[i].length(), startIndex = i; // 如果不是最后一行，那么更新当前行的长度和起始下标
};
for (int i = 1; i < words.size(); ++i) // 遍历每个单词
if (nowLength + words[i].length() + 1 <= maxWidth) nowLength += words[i].length() + 1; // 如果当前行可以放置下这个单词，那么更新当前行的长度
else placeWords(i, i - 1 - startIndex ? (maxWidth - nowLength) / (i - startIndex - 1) : 0, i - 1 - startIndex ?(maxWidth - nowLength) % (i - startIndex - 1) : 0, !(i - 1 - startIndex)); // 否则，将 startIndex ~ i - 1 放置到一行中
placeWords(words.size(), 0, 0, 1); // 将最后一行放置到答案中
return ans;
}
};
