剑指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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

剑指 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

剑指 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

剑指 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 == "/");
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

方法二：数组模拟栈

后缀表达式中数字的个数一定比运算符多一个，然后后缀表达式一定是奇数。如果后缀表达式有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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

剑指 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

剑指 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

枚举高

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

方法一：单调栈

维护一个严格单调递增的栈，

代码

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

剑指 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

剑指 Offer II 041. 滑动窗口的平均值

用一个sum变量维护窗口的值

用一个sum变量维护窗口的值，当窗口值的数量小于窗口的最大的大小时一直往里加

剑指 Offer II 042. 最近请求次数

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请实现 RecentCounter 类：

RecentCounter() 初始化计数器，请求数为 0 。
int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。

用队列存放请求时间