剑指 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 值。

用队列存放请求时间