剑指offer32-42字符串数组的应用
剑指 Offer II 032. 有效的变位词
给定两个字符串 s 和 t ，编写一个函数来判断它们是不是一组变位词（字母异位词）。t 是 s的变位词等价于「两个字符串不相等且两个字符串排序后相等」
注意：若 s 和 t 中每个字符出现的次数都相同且字符顺序不完全相同，则称 s 和 t 互为变位词（字母异位词）。
也就字母个数一样，就是顺序不一样
方法一：先排序再判断
方法二：哈希表
剑指 Offer II 033. 变位词组
给定一个字符串数组 strs ，将 变位词 组合在一起。 可以按任意顺序返回结果列表。
注意：若两个字符串中每个字符出现的次数都相同，则称它们互为变位词。
方法一：将排序后的值为键，将当前元素为值
字母异位词的两次词排序后的值是一样的，将这个值作为键，将排序前的值加入到键后的哈希表中
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for (string& str : strs) {
string key = str;
std::sort(key.begin(), key.end());
mp[key].emplace_back(str);
}
vector<vector<string>> ans;
for (auto it = mp.begin(); it != mp.end(); ++it) {
ans.emplace_back(it->second);
}
return ans;
}
};
剑指 Offer II 034. 外星语言是否排序
某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。
给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。
题目的意思是外星人的字母表和地球人的不一样，所以单词排序要按其他的字母表排序
比如apple和book，外星人字母表可能是先b后a，所以正常排序应该是book，apple。另外需要注意一点的是boos和books，books要大于book
方法一：直接遍历
首先对外星人字母表进行处理，依旧是用字母-'a’得到下标，然后下标对应的值为它的顺序
然后对两个字母公共的部分进行判断，
为了防止越界，让i从1开始，和0位置作比较，i最终结束条件为 words.size()
对于两个单词长度不一样的情况，只比较到长度小的长度。apples和book只比较到4
如果出现当前位置两个元素，后一个单词的元素大于当前元素，那么跳出循环，比如book和baok，a大于o，那么就对了，这两个单词就不用比较了，如果小于，那么直接返回false
在比较完两个单词后，还要看两个公共长度外的，长度大的是大的
class Solution {
public:
bool isAlienSorted(vector<string>& words, string order) {
vector<int> index(26);
for (int i = 0; i < order.size(); i++) {
index[order[i] - 'a'] = i;
}
for (int i = 1; i < words.size(); i++) {
bool valid = false;
for (int j = 0; j < words[i - 1].size() && j < words[i].size(); j++) {
int prev = index[words[i - 1][j] - 'a'];
int curr = index[words[i][j] - 'a'];
if (prev < curr) {
valid = true;
break;
}
else if (prev > curr) {
return false;
}
}
if (!valid) {
/* 比较两个字符串的长度 */
if (words[i - 1].size() > words[i].size()) {
return false;
}
}
}
return true;
}
};
剑指 Offer II 035. 最小时间差
给定一个 24 小时制（小时:分钟 “HH:MM”）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。
是时间的时间差，而不是某个项的时间差
方法：先排序，比较的时候将字符串转换为类似时间戳形式，用打擂得出最小值
对于首位的时间差可以通过往数组里加入一个首元素+24*60的形式
也可以到最后判断
class Solution {
int getMinutes(string& t) {
return (int(t[0] - '0') * 10 + int(t[1] - '0')) * 60 + int(t[3] - '0') * 10 + int(t[4] - '0');
}
public:
int findMinDifference(vector<string>& timePoints) {
int n = timePoints.size();
if (n > 1440) {
return 0;
}
sort(timePoints.begin(), timePoints.end());
int ans = INT_MAX;
int t0Minutes = getMinutes(timePoints[0]);
int preMinutes = t0Minutes;
for (int i = 1; i < n; ++i) {
int minutes = getMinutes(timePoints[i]);
ans = min(ans, minutes - preMinutes); // 相邻时间的时间差
preMinutes = minutes;
}
ans = min(ans, t0Minutes + 1440 - preMinutes); // 首尾时间的时间差
return ans;
}
};
剑指 Offer II 036. 后缀表达式
题目的意思就是求后缀表达式运算的结果
方法一：利用栈
不管哪个符号都是双目运算的，也就是碰见一个符号，一定是对前两个元素操作。
比如 a b * 一定是对a和b进行运算，而2 1 + 3 看结果是有括号也是要2和1运算完成后再与3进行乘，所以不需要顾忌
对于判断不是数字可以通过 !(token == “+” || token == “-” || token == "" || token == “/”);或者直接通过isdigit()方法
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> stk;
int n = tokens.size();
for (int i = 0; i < n; i++) {
string& token = tokens[i];
if (isNumber(token)) {
stk.push(atoi(token.c_str()));
}
else {
int num2 = stk.top();
stk.pop();
int num1 = stk.top();
stk.pop();
switch (token[0]) {
case '+':
stk.push(num1 + num2);
break;
case '-':
stk.push(num1 - num2);
break;
case '*':
stk.push(num1 * num2);
break;
case '/':
stk.push(num1 / num2);
break;
}
}
}
return stk.top();
}
bool isNumber(string& token) {
return !(token == "+" || token == "-" || token == "*" || token == "/");
}
};
方法二：数组模拟栈
后缀表达式中数字的个数一定比运算符多一个，然后后缀表达式一定是奇数。如果后缀表达式有n个字符，那么数字的个数一定是(n+1)/2,操作符的个数一定是(n-1)/2,在申请空间时，最坏情况下，操作数都在前面，在其他情况下每遇见一个操作符就会减少一个数字，所以最坏情况下需要申请空间为(n+1)/2
剑指 Offer II 037. 小行星碰撞
给定一个整数数组 asteroids，表示在同一行的小行星。
对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。
找出碰撞后剩下的所有小行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。
输入：asteroids = [5,10,-5]
输出：[5,10]
解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。
题目的正是指向右移动，负是指向左移动，正负符号后面的数字只是指行星的大小，并不是移动距离
分析：题目碰撞只可能是左正右负，如果是左负右正即一个往左跑，一个往右跑是不可能碰撞，而左负右负也不可能发生碰撞。因此只能是左正右负会发生碰撞。
可以用栈，也可以用数组，这里用数组处理
方法：用数组模拟栈
代码
class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
// 栈应用题
vector<int> s;
for (int c : asteroids) {
while (!s.empty() && s.back() > 0 && c < 0) { // 碰撞条件：左正右负
int a = s.back(), b = abs(c); // 根据规则，查看c的绝对质量
s.pop_back();
if (a > b) c = a; // 左球大于右球，右球被吃
else if (a < b) continue; // 右球大于左球，继续去给我往左碰
else c = 0; // 质量一样两者消失
}
// 如果最终不是两者消失的情况，那么要把一顿乱撞后剩余的球入栈
// 同时下边的条件正好也把质量为0的球忽略掉了，这种球没有用
if (c != 0) s.push_back(c);
}
return s;
}
剑指 Offer II 038. 每日温度
请根据每日 气温 列表 temperatures ，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
题目的意思是找比当前元素大的第一个元素的间隔，如果后面没有了那么就写0
方法一：暴力法
方法二：单调栈
后面出现较大的值会吃掉前面较小的值，直到第一个不比其自身小的值为止
代码
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> ans(n);
stack<int> s;
for (int i = 0; i < n; ++i) {
while (!s.empty() && temperatures[i] > temperatures[s.top()]) {
int previousIndex = s.top();
ans[previousIndex] = i - previousIndex;
s.pop();
}
s.push(i);
}
return ans;
}
};
剑指 Offer II 039. 直方图最大矩形面积
给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
题目意思就是求这些图形能勾勒出的最大面积，这个面积可能是多个矩形的公共部分，也可以直接是自己的面积
枚举法（时间复杂度为O(n^2)会超时）
枚举宽
两层for循环，第一层枚举左边界，第二层枚举右边界，在循环里面，每次循环都更新高的值，高的值为min(原先最小值，新建入右边界后的值)
代码
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
int ans = 0;
// 枚举左边界
for (int left = 0; left < n; ++left) {
int minHeight = INT_MAX;
// 枚举右边界
for (int right = left; right < n; ++right) {
// 确定高度
minHeight = min(minHeight, heights[right]);
// 计算面积
ans = max(ans, (right - left + 1) * minHeight);
}
}
return ans;
}
};
枚举高
for循环每个柱子，这样就先确定矩形的高了，接下来从柱子开始先向左延伸再向右延伸，一旦碰到高度比柱子矮的柱子就停止延伸。
代码
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
int ans = 0;
for (int mid = 0; mid < n; ++mid) {
// 枚举高
int height = heights[mid];
int left = mid, right = mid;
// 确定左右边界
while (left - 1 >= 0 && heights[left - 1] >= height) {
--left;
}
while (right + 1 < n && heights[right + 1] >= height) {
++right;
}
// 计算面积
ans = max(ans, (right - left + 1) * height);
}
return ans;
}
};
方法一：单调栈
维护一个严格单调递增的栈，
代码
class Solution1 {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
vector<int> left(n), right(n, n);
stack<int> mono_stack;
for (int i = 0; i < n; ++i) {
while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
right[mono_stack.top()] = i;
mono_stack.pop();
}
left[i] = (mono_stack.empty() ? -1 : mono_stack.top());
mono_stack.push(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;
}
};
剑指 Offer II 040. 矩阵中最大的矩形
给定一个由 0 和 1 组成的矩阵 matrix ，找出只包含 1 的最大矩形，并返回其面积。
注意：此题 matrix 输入格式为一维 01 字符串数组。
方法一：暴力法
两个for循环枚举左上角和右下角，但是复杂度过高
方法二：使用柱状图的优化暴力方法
求矩阵面积也就是求每行的直方图，如下图所示，每行都标出了它的高度，
以第三行为例 3 1 3 2 2就直接变成了上题的求面积的问题，因此这个题目可以抽象成求四行元素的直方图。
代码
class Solution {
public:
int maximalRectangle(vector<string>& matrix) {
if (matrix.size() == 0) {
return 0;
}
vector<int> heights(matrix[0].size(), 0);
int maxArea = 0;
for (int i = 0; i < matrix.size(); ++i) {
for (int j = 0; j < matrix[0].size(); ++j) {
if (matrix[i][j] == '0') {
heights[j] = 0;
}
else {
heights[j] += matrix[i][j] - '0';
}
}
maxArea = max(maxArea, largestRectangleArea(heights));
}
return maxArea;
}
int largestRectangleArea(vector<int>& heights) {
stack<int> sta;
sta.push(-1);
int maxArea = 0;
for (int i = 0; i < heights.size(); ++i) {
while (sta.top() != -1 && heights[sta.top()] >= heights[i]) {
int height = heights[sta.top()];
sta.pop();
int width = i - sta.top() - 1;
maxArea = max(maxArea, height * width);
}
sta.push(i);
}
while (sta.top() != -1) {
int height = heights[sta.top()];
sta.pop();
int width = heights.size() - sta.top() - 1;
maxArea = max(maxArea, height * width);
}
return maxArea;
}
};
剑指 Offer II 041. 滑动窗口的平均值
用一个sum变量维护窗口的值
用一个sum变量维护窗口的值，当窗口值的数量小于窗口的最大的大小时一直往里加
剑指 Offer II 042. 最近请求次数
写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请实现 RecentCounter 类：
RecentCounter() 初始化计数器，请求数为 0 。
int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。
用队列存放请求时间
