力扣刷题记录10.19

Last updated on October 19, 2024 pm

2024/10/19

（1）数组操作

1、使二进制数组全部等于 1 的最少操作次数 I

给你一个二进制数组 nums 。

你可以对数组执行以下操作 任意 次（也可以 0 次）：

  • 选择数组中 任意连续 3 个元素，并将它们 全部反转 。

反转 一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。

请你返回将 nums 中所有元素变为 1 的 最少 操作次数。如果无法全部变成 1 ，返回 -1 。

思路：遇见0就翻转，从左至右模拟，一直到倒数第三个元素，这样得到的结果就是最小的。如果模拟到最后，剩下两个元素不为1，就说明没办法。

二进制运算符号：

  • &：按位与

  • |：按位或

  • ^：按位异或（利用这个符号，异或1可以对每一位取反）

  • ~：按位取反

  • <<：左移（相当于*2，右边补零）

  • >>：右移（相当于/2，向下取整）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int minOperations(vector<int>& nums) {
        int cnt=0;
        int n=nums.size();
        for(int i=0;i<n-2;i++){
            if(nums[i]==0){
                nums[i+1]^=1;
                nums[i+2]^=1;
                cnt++;
            }
        }
        return nums[n-2]&&nums[n-1]?cnt:-1;
    }
};
2、使二进制数组全部等于 1 的最少操作次数 II

选择数组中 任意 一个下标 i ，并将从下标 i 开始一直到数组末尾 所有 元素 反转 。

有了上一题的启发，这一题很好模拟。从前往后和从后往前都一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int minOperations(vector<int>& nums) {
        int cnt=0;
        int n=nums.size();
        for(int i=n-1;i>=1;i--){
            if(nums[i]^nums[i-1]){
                cnt++;
            }
        }
        return nums[0]?cnt:cnt+1;
    }
};

（2）栈模拟

1、字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。（注意可以嵌套[]）

由于有嵌套，直接模拟很不好模拟，单栈法感觉没有双栈法清晰，所以这里只记录双栈法，比较容易理解。

num：存储遇到左括号前的数字（数字与’[‘一一对应）

currentS：存储遇到左括号前的字符串（也就是括号里的字符串要加到的地方）

怎么模拟呢？

  • 当遇到数字的时候，计算数字的大小（注意数字可能有好几位），k是截至上一位数字得到的值，然后到这一位需要十进制相加运算。
  • 当遇到'['的时候，意味着需要存储前面的数字和字符串了，方便后面弹栈出[]内的字符串时与之相加。存储后k和currentString需要归0。
  • 当遇到']'的时候，意味着可以将’[]’内的字符串与栈顶的字符串做相加了，按照数字的个数做相应相加，得到的结果继续使用currentString存储。
  • 当遇到的是小写字母，就直接用它加到currentString上即可。
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:
    string decodeString(string s) {
        stack<int> num;
        stack<string> currentS;
        string currentString;
        int k=0;
        for(char c:s){
            if(isdigit(c)){
                k=10*k+c-'0';
            }
            else if(c=='['){
                num.push(k);
                currentS.push(currentString);
                k=0;
                currentString="";
            }
            else if(c==']'){
                int times=num.top();
                num.pop();
                string cur=currentS.top();
                currentS.pop();
                while(times){
                    cur+=currentString;
                    times--;
                }
                currentString=cur;
            }
            else{
                currentString+=c;
            }
        }
        return currentString;
    }
};
2、每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

（我写的跟官解尊的一模一样，除了我的代码更冗余，难道说四个月前的记忆还留在我脑海里？？）

单调栈：（存储的是下标）

如果栈非空且当前元素大于栈顶元素作为下标的温度，就一直弹栈。并且开始记录栈顶的下标的天数差。最后再push进入当前下标。

  • 由于有!tem.empty()的条件，所以不需要在一开始push进0下标；
  • 由于vector会每个值初始化为0，所以不需要特地取出还留在栈里的元素把它们的值赋为0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& t) {
        int n=t.size();
        vector<int> up(n);
        stack<int> tem;
        for(int i=0;i<n;i++){
            while(!tem.empty()&&t[i]>t[tem.top()]){
                up[tem.top()]=i-tem.top();
                tem.pop();
            }
            tem.push(i);
        }
        return up;
    }
};
3、柱状图中最大的矩形

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

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

思路：

  • 遍历每个下标，分别记录其左边离他最近的小于它高度的下标和右边离他最近的小于它高度的下标。（这一步需要用到单调栈）（分别使用left[i]和right[i]记录）

  • 再次遍历，对于每个下标，以它作为高度能计算的最大面积就是：

    • height[i]*(right[i]-left[i]-1)

那么如何计算两个下标数组呢？

我们可以这样模拟：

  • 遍历，如果栈不为空且当前元素小于栈顶元素，就记录它的下标为栈顶下标的右边最近小元素。right[mono_stack.top()] = i;并且弹栈继续比较。
  • 如果栈为空，就说明当前下标的左边没有比它更小的元素，于是记录left[i]=-1；不然就说明栈顶元素是第一个小于它高度的下标。
  • 最后把当前的下标压入栈中。

注意将right数组的所有值均初始化为n，因为在遍历中一定可以记录left数组，却不一定能记录到right数组。有可能右边没有比当前元素小的值，初始化为n就免去了麻烦。

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

（2）二分法

1、在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

我的办法是先用二分法找到目标元素，然后再依次向左向右找到边界。但是评论区有人说这种办法在最坏的情况下复杂度是O(n)，遂看官方的办法：两次二分法。第一次找到第一个>=target的元素，第二次找到第一个大于target的元素。

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
class Solution { 
public:
    int binarySearch(vector<int>& nums, int target, bool lower) {
        int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();
        while (left <= right) {
           int mid = (left + right) / 2;
           if (nums[mid] > target || (lower && nums[mid] >= target)){
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {
            return vector<int>{leftIdx, rightIdx};
        } 
        return vector<int>{-1, -1};
    }
};
2、搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

思路：每次进行二分，mid左右两边的序列一定有一个是有序的。于是可以看target在不在有序的部分。如果在就在有序的部分查找，否则就在无序的部分查找。

如何判断有序？如果左边有序那么既然left<=mid就一定有nums[left]<=nums[mid]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n=nums.size();
        int l=0,r=n-1;
        while(l<=r){
            int mid=(l+r)>>1;
            if(nums[mid]==target) return mid;
            if(nums[l]<=nums[mid]){
                (nums[l]<=target&&target<nums[mid])?r=mid-1:l=mid+1;
            }
            else{
                (nums[mid]<target&&target<=nums[r])?l=mid+1:r=mid-1;
            }
        }
        return -1;
    }
};
c++
#c++
力扣刷题记录10.19
http://example.com/2024/10/19/力扣刷题记录10.19/
Author
Yaodeer
Posted on
October 19, 2024
Licensed under