Schwertlilien
归档分类标签关于
搜索
归档分类标签关于
Schwertlilien
As a recoder: notes and ideas.

刷题日记-1

力扣刷题
力扣
版权声明: 署名-非商业性使用-禁止演绎 4.0
全文约2.9K字
阅读次数:

开始佛系找工作（？）

主要是今天接到字节的电话，不知何时会等到一个面试，遂开始写点题。

然后下午的时候确定了时间，咱就是说，有一个死缓期，还是刷点题吧（）。

Q2-重新排列数组

给你一个数组 nums，数组中有 2n 个元素，按 [x1,x2,...,xn,y1,y2,...,yn] 的格式排列。

请你将数组按 [x1,y1,x2,y2,...,xn,yn] 格式重新排列，返回重排后的数组。

示例 1：解释：由于 x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 ，所以答案为 [2,3,5,4,1,7]

1
2
输入：nums = [2,5,1,3,4,7], n = 3
输出：[2,3,5,4,1,7]

示例 2：

1
2
输入：nums = [1,2,3,4,4,3,2,1], n = 4
输出：[1,4,2,3,3,2,4,1]

示例 3：

1
2
输入：nums = [1,1,2,2], n = 2
输出：[1,2,1,2]

提示：

  • 1 <= n <= 500
  • nums.length == 2n
  • 1 <= nums[i] <= 10^3

我的解答

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> shuffle(vector<int>& nums, int n) {
        vector<int> ans;
        for(int i=0,j=n;i<n;i++,j++){
            ans.push_back(nums[i]);
            ans.push_back(nums[j]);
        }
        return ans;
    }
};

Q3-最大连续1的个数

给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。

示例 1：

1
2
3
输入：nums = [1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.

示例 2:

1
2
输入：nums = [1,0,1,1,0,1]
输出：2

提示：

  • 1 <= nums.length <= 105
  • nums[i] 不是 0 就是 1.

我的解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int max_len=0;
        int cur_len=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==1){
                cur_len++;
                max_len = max_len<cur_len?cur_len:max_len;
            }
            if(nums[i]==0){
                cur_len=0;
            }
        }
        return max_len;
    }
};

Q4-有多少小于当前数字的数字

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。

以数组形式返回答案。

示例 1：

1
2
3
4
5
6
7
8
输入：nums = [8,1,2,2,3]
输出：[4,0,1,1,3]
解释： 
对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。 
对于 nums[1]=1 不存在比它小的数字。
对于 nums[2]=2 存在一个比它小的数字：（1）。 
对于 nums[3]=2 存在一个比它小的数字：（1）。 
对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。

示例 2：

1
2
输入：nums = [6,5,4,8]
输出：[2,1,0,3]

示例 3：

1
2
输入：nums = [7,7,7,7]
输出：[0,0,0,0]

提示：

  • 2 <= nums.length <= 500
  • 0 <= nums[i] <= 100

我的解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> ans(nums.size());
        vector<int> sorted_nums = nums;
        sort(sorted_nums.begin(),sorted_nums.end());
        
        unordered_map<int,int> firstPos;
        for(int i=0;i<sorted_nums.size();i++){
            if(!firstPos.count(sorted_nums[i])){
                firstPos[sorted_nums[i]]=i;
            }
        }
        for(int i=0;i<nums.size();i++){
            ans[i]=firstPos[nums[i]];
        }
        return ans;
    }
};

Q5-函数的独占时间⚠️

有一个 单线程 CPU 正在运行一个含有 n 道函数的程序。每道函数都有一个位于 0 和 n-1 之间的唯一标识符。

函数调用 存储在一个 调用栈 上 ：当一个函数调用开始时，它的标识符将会推入栈中。而当一个函数调用结束时，它的标识符将会从栈中弹出。标识符位于栈顶的函数是 当前正在执行的函数 。每当一个函数开始或者结束时，将会记录一条日志，包括函数标识符、是开始还是结束、以及相应的时间戳。

给你一个由日志组成的列表 logs ，其中 logs[i] 表示第 i 条日志消息，该消息是一个按 "{function_id}:{"start" | "end"}:{timestamp}" 进行格式化的字符串。例如，"0:start:3" 意味着标识符为 0 的函数调用在时间戳 3 的 起始开始执行 ；而 "1:end:2" 意味着标识符为 1 的函数调用在时间戳 2 的 末尾结束执行。注意，函数可以 调用多次，可能存在递归调用 。

函数的 独占时间 定义是在这个函数在程序所有函数调用中执行时间的总和，调用其他函数花费的时间不算该函数的独占时间。例如，如果一个函数被调用两次，一次调用执行 2 单位时间，另一次调用执行 1 单位时间，那么该函数的 独占时间 为 2 + 1 = 3 。

以数组形式返回每个函数的 独占时间 ，其中第 i 个下标对应的值表示标识符 i 的函数的独占时间。

示例 1：

img

1
2
3
4
5
6
7
输入：n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
输出：[3,4]
解释：
函数 0 在时间戳 0 的起始开始执行，执行 2 个单位时间，于时间戳 1 的末尾结束执行。 
函数 1 在时间戳 2 的起始开始执行，执行 4 个单位时间，于时间戳 5 的末尾结束执行。 
函数 0 在时间戳 6 的开始恢复执行，执行 1 个单位时间。 
所以函数 0 总共执行 2 + 1 = 3 个单位时间，函数 1 总共执行 4 个单位时间。

示例 2：

1
2
3
4
5
6
7
8
9
输入：n = 1, logs = ["0:start:0","0:start:2","0:end:5","0:start:6","0:end:6","0:end:7"]
输出：[8]
解释：
函数 0 在时间戳 0 的起始开始执行，执行 2 个单位时间，并递归调用它自身。
函数 0（递归调用）在时间戳 2 的起始开始执行，执行 4 个单位时间。
函数 0（初始调用）恢复执行，并立刻再次调用它自身。
函数 0（第二次递归调用）在时间戳 6 的起始开始执行，执行 1 个单位时间。
函数 0（初始调用）在时间戳 7 的起始恢复执行，执行 1 个单位时间。
所以函数 0 总共执行 2 + 4 + 1 + 1 = 8 个单位时间。

示例 3：

1
2
3
4
5
6
7
8
9
输入：n = 2, logs = ["0:start:0","0:start:2","0:end:5","1:start:6","1:end:6","0:end:7"]
输出：[7,1]
解释：
函数 0 在时间戳 0 的起始开始执行，执行 2 个单位时间，并递归调用它自身。
函数 0（递归调用）在时间戳 2 的起始开始执行，执行 4 个单位时间。
函数 0（初始调用）恢复执行，并立刻调用函数 1 。
函数 1在时间戳 6 的起始开始执行，执行 1 个单位时间，于时间戳 6 的末尾结束执行。
函数 0（初始调用）在时间戳 7 的起始恢复执行，执行 1 个单位时间，于时间戳 7 的末尾结束执行。
所以函数 0 总共执行 2 + 4 + 1 = 7 个单位时间，函数 1 总共执行 1 个单位时间。

提示：

  • 1 <= n <= 100
  • 2 <= logs.length <= 500
  • 0 <= function_id < n
  • 0 <= timestamp <= 109
  • 两个开始事件不会在同一时间戳发生
  • 两个结束事件不会在同一时间戳发生
  • 每道函数都有一个对应 "start" 日志的 "end" 日志

我的解答

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
class Solution {
public:
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        vector<int> ans(n,0);
        stack<int> save_id;
        int prev_time=0;

        for(int i=0;i<logs.size();i++){
            int p1 = logs[i].find(':');
            int p2 = logs[i].find(':', p1 + 1);

            int id = stoi(logs[i].substr(0, p1));
            string type = logs[i].substr(p1 + 1, p2 - p1 - 1);
            int time = stoi(logs[i].substr(p2 + 1));

            if(type=="start"){
                if(!save_id.empty()){
                    int update_id=save_id.top();
                    ans[update_id]+=time-prev_time;
                }
                  
                save_id.push(id);
                prev_time=time;
            }else{//"end":有程序结束，需要pop
                if(!save_id.empty()){
                    save_id.pop();
                    ans[id]+=time-prev_time+1;
                }
                prev_time = time+1;
            }
        }

        return ans;
    }
};

Q6-柱形图中的最大矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

img

1
2
3
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

img

1
2
输入： heights = [2,4]
输出： 4

提示：

  • 1 <= heights.length <=105
  • 0 <= heights[i] <= 104

我的解答

暴力解法

思路：矩形面积=高x宽。将高固定，遍历数组，确定i时对应的num为固定高，然后以这个i为终点，找到左右两边第一个比num小的数字。不包括左右两边的边界，此时确定的宽是max宽。也就是当高为i对应num时的max_area。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int max_area=0;
        for(int i=0;i<heights.size();i++){
            int cur_height=heights[i];//固定高，找到最大宽。
            int left = i-1;
            int right = i+1;
            while(left>=0&&heights[left]>=cur_height){
                left--;
            }
            while(right<heights.size()&&heights[right]>=cur_height){
                right++;
            }
            int now_area=cur_height*(right-left-1);
            if(max_area<now_area){
                max_area=now_area;
            }
        }
        return max_area;
    }
};

单调栈

思路：在上面的情况中，每次固定height的时候都会从新左右搜索。但是我之前左右搜索，是有些信息可以保存下来，免得重复的左右搜索的。这个信息就是：一个单调递增的数组，其紧挨着的就是这个高的left边界。然后设定一个现在找到的数字要是小于stack.top()的判定条件，那么我们找到了right边界，这样就能计算当前的矩形面积了。

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
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int total_len = heights.size();
        heights.push_back(-1);
        int max_area = 0;
        stack<int> s;
        s.push(0);
        for(int i=1;i<heights.size();){
            int face_num = heights[i];
            int face_id = i;

            if(!s.empty()&&heights[s.top()]>face_num){
                //计算面积
                int right = face_id;
                int left = -1;
                int height = heights[s.top()];s.pop();
                if(!s.empty())left = s.top();
                int area = height*(right-left-1);
                if(area>max_area)max_area=area;
                continue;
            }
            s.push(i++);
        }
        return max_area;
    }
};

简洁版：

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
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.push_back(0);           // 右侧哨兵
        stack<int> s;
        s.push(-1);                     // 左侧哨兵

        int max_area = 0;

        for (int i = 0; i < heights.size(); i++) {
            while (s.top() != -1 && heights[s.top()] > heights[i]) {
                int h = heights[s.top()];
                s.pop();
                int w = i - s.top() - 1;
                max_area = max(max_area, h * w);
            }
            s.push(i);
        }
        return max_area;
    }
};
//下面是我自己修改后的：
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int total_len = heights.size();
        heights.push_back(-1);
        int max_area = 0;
        stack<int> s;
        s.push(-1);
        for(int i=0;i<heights.size();){
            while(s.top()!=-1&&heights[s.top()]>heights[i]){
                int height = heights[s.top()];s.pop();
                int area=height*(i-s.top()-1);
                if(area>max_area)max_area=area;
            }
            s.push(i++);
        }
        return max_area;
    }
};
搜索
匹配结果数:
未搜索到匹配的文章。