wy的leetcode刷题记录_Day86

声明

本文章的所有题目信息都来源于leetcode
如有侵权请联系我删掉!
时间：2024-3-13

前言

@TOC

2864. 最大二进制奇数

今天的每日一题是：2864. 最大二进制奇数

题目介绍

给你一个 二进制 字符串 s ，其中至少包含一个 '1' 。

你必须按某种方式 重新排列 字符串中的位，使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。

以字符串形式，表示并返回可以由给定组合生成的最大二进制奇数。

注意 返回的结果字符串 可以 含前导零。

示例 1：

输入：s = "010"
输出："001"
解释：因为字符串 s 中仅有一个 '1' ，其必须出现在最后一位上。所以答案是 "001" 。

示例 2：

输入：s = "0101"
输出："1001"
解释：其中一个 '1' 必须出现在最后一位上。而由剩下的数字可以生产的最大数字是 "100"。所以答案是 "1001"

思路

统计长度为n字符串s中1的个数num1，0的个数就为n-num1，于是对于返回的字符串我们令高num1-1位位1接下来的n-num1位为0，最低位为1即可。

代码

class Solution {
public:
    string maximumOddBinaryNumber(string s) {
        int num1=0;
        int n=s.size();
        int min_odd=9;
        string ans="";
        for(int i=0;i<n;i++)
        {
            if((s[i]-'0')==1)
            {
                num1++;
            }

        }
        for(int i=0;i<num1-1;i++)
        {
            ans+="1";
        }
        for(int i=0;i<n-num1;i++)
        {
            ans+="0";
        }

        ans+="1";
        return ans;
    }
};

官方题解：简介代码

class Solution {
public:
    string maximumOddBinaryNumber(string s) {
        int cnt = count(s.begin(), s.end(), '1');
        return string(cnt - 1, '1') + string(s.length() - cnt, '0') + '1';
    }
};

收获

count统计字符串中字符的个数，以及巩固了string的构建函数。

3. 无重复字符的最长子串

3. 无重复字符的最长子串

题目介绍

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

思路

模拟滑动窗口，使用一个哈希表来记录当前窗口内的元素，如果滑动窗口向后扩张时下一个元素已存在于哈希表中，代表窗口内即将有冲突，这时候我们要将窗口前端的元素进行丢弃直到可以容纳下一个元素为止，在滑动窗口扩张的过程中我们维护最长长度即可得到答案。

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int front=0,rear=0;
        int n=s.size();
        if(n==0)
            return 0;
        unordered_map<char,int> hash;
        int ans=0;
        while(rear<n)
        {
            if(hash[s[rear]])
            {
                while(hash[s[rear]])
                {
                    hash[s[front]]--;
                    front++;
                }
            }
          ans=max(ans,rear-front+1);
          hash[s[rear]]++;
          rear++;
        }
        return ans;
    }
};

收获

复习滑动窗口。

438. 找到字符串中所有字母异位词

438. 找到字符串中所有字母异位词

题目介绍

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释: 起始索引等于 0 的子串是 "cba", 它是"abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab"的异位词。

思路

跟上一题相同本题也可以使用哈希表来保存滑动窗口内的不同元素对应的个数，但在上题中我们使用的是set类型的哈希表那是因为上一题明确无重复的字符，而本题有重复的字符只能使用map来映射，这里因为字母固定26位我才用vector(26)来进行保存。

代码

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int n=s.size();
        int m=p.size();
        if(n<m)
            return vector<int>();

        vector<int> s1(26),p1(26);
        vector<int> ans;
        for(int i=0;i<m;i++)
        {
            s1[s[i]-'a']++;
            p1[p[i]-'a']++;
        }

        if(p1==s1)
        {
            ans.emplace_back(0);
        }
        for(int i=0;i<n-m;i++)
        {
            s1[s[i]-'a']--;
            s1[s[i+m]-'a']++;
            if(s1==p1)
            {
                ans.emplace_back(i+1);
            }
        }
        return ans;

    

    }
};

收获

一般滑动窗口需要配合哈希表来统计窗口内部的数据。

560. 和为 K 的子数组

560. 和为 K 的子数组

题目介绍

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

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

示例 2：

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

思路

方法一：暴力解法：枚举所有的起点，在每个起点中再枚举重点计算和是否等于k
方法二：前缀和+哈希表：前缀和可以是我们计算子数组之和的时间复杂度降低，哈希表记录前缀和出现的次数，后面的思路看下题解（只可意会不可言传）...

代码

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int count = 0;
        for (int start = 0; start < nums.size(); ++start) {
            int sum = 0;
            for (int end = start; end >= 0; --end) {
                sum += nums[end];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
};

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        hash[0]=1;
        int count=0,pre=0;
        int n=nums.size();
        if(n==1)
            return nums[0]==k?1:0;
        for(auto x:nums)
        {
            pre+=x;
            if(hash.count(pre-k))
                count+=hash[pre-k];
            hash[pre]++;
        }
        return count;

    }
};

收获

emmm头晕了。

53. 最大子数组和

53. 最大子数组和

题目介绍

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组
是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

思路

动态规划：我先放上原文（讲的巨好）。我自己的理解就是dp[i]表示前i个元素的最大和，而前i+1个元素的最大和与dp[i]和nums[i+1]有关。

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans=-10000;
        int n=nums.size();

        for(int start=0;start<n;start++)
        {
            int sum=0;
            for(int end=start;end<n;end++)
            {
                sum+=nums[end];
                ans=max(ans,sum);
            }
        }
        return ans;
    }
};

优化空间：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n=nums.size();
        int pre=0;
        int ans=nums[0];

        for(int i=0;i<n;i++)
        {
            pre=max(pre+nums[i],nums[i]);
            ans=max(ans,pre);
        }

        return ans;
    }
};

收获

动态规划全忘完咯！

56. 合并区间

56. 合并区间

题目介绍

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

思路

emm说实话我一开始没思路，看了一眼评论区才有思路。先用排序（根据起点开始排序），然后将第i个区间的右边界与排序后的第i+1个区间的左边界进行比较，如果大于则相交，否则不相交。相交将较小的左边界与较大的有边界装入新的ans中，再与下一个区间进行比较。

代码

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n=intervals.size();
        if(n==0)
            return intervals;
        
        sort(intervals.begin(),intervals.end());
        vector<vector<int>> ans;
        for(int i=0;i<n;i++)
        {
            if(!ans.size()||ans.back()[1]<intervals[i][0])//不相交
            {
                ans.push_back({intervals[i][0],intervals[i][1]});
            }
            else
            {
                ans.back()[1]=max(ans.back()[1],intervals[i][1]);
            }

        }
        return ans;
    }
};

收获

无。

189. 轮转数组

189. 轮转数组

题目介绍

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4]

示例2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]

思路

方法一：反转数组，样例1：1234567.。我们先整体反转7654321，再将前k个和剩余n-k个反转得5671234，即可实现。
方法二：使用额外数组来保存原数组反转后的位置，原数组的每个元素计算其在新数组中的位置然后赋值即可。

代码

class Solution {
public:

    void reverse(vector<int>& nums,int start,int end)
    {
        while(start<end)
        {
            swap(nums[start],nums[end]);
            start++;
            end--;
        }
    }
    void rotate(vector<int>& nums, int k) {
        k=k%nums.size();
        reverse(nums,0,nums.size()-1);
        reverse(nums,0,k-1);
        reverse(nums,k,nums.size()-1);

    }
};

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n=nums.size();
        k%=n;
        vector<int> a(n);
        for(int i=0;i<n;i++)
        {
            a[(i+k)%n]=nums[i];
        }
        nums.assign(a.begin(),a.end());
    }
};

收获

巩固了反转数组和数组的一些赋值操作,vector.assigin(iterator,iterator)。

238. 除自身以外数组的乘积

238. 除自身以外数组的乘积

题目介绍

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

思路

可恶啊，本来记录所有元素的乘积然后除以对应元素就可以得到答案，可恶的出题人不让用除法。这里我使用两个数组left和right分别记录i左边的乘积和和i右边的乘积和，left[i]*right[i]即为所求。

代码

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> left(n,0),right(n,0);
        left[0]=1;
        right[n-1]=1;
        for(int i=1;i<n;i++)
        {
            left[i]=nums[i-1]*left[i-1];
        }
        for(int i=n-2;i>=0;i--)
        {
            right[i]=nums[i+1]*right[i+1];
        }
        for(int i=0;i<n;i++)
        {
            nums[i]=left[i]*right[i];
        }
        return nums;
    }
};

收获

无

73. 矩阵置零

73. 矩阵置零

题目介绍

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

思路

直观的想法，分别用两个HashSet来保存需要清0的行和列，对整个矩阵进行遍历后得到hashset对hashset选中的行列进行清0即可。
题解中给出了另外两种空间上优化解法，这里我只说第一种优化的，剩下那个没看....，我们一开始使用了两个HashSet来记录需要清0的空间，这里我们不需要额外的空间使用二维矩阵的第0行和第0列来表示是否需要对该行或者该列进行清空，这是我们丢失了原本第0行和第0列的信息，所以我们需要两个O（1）的变量来记录是否需要对第0行和第0列进行清空即可。

代码

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        unordered_set<int> row,col;
        int n=matrix.size();
        int m=matrix[0].size();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(matrix[i][j]==0)
                {
                    row.insert(i);
                    col.insert(j);
                }
            }
        }
        for(auto i:col)
        {
            for(int j=0;j<n;j++)
            {
                matrix[j][i]=0;
            }
        }

        for(auto i:row)
        {
            for(int j=0;j<m;j++)
            {
                matrix[i][j]=0;
            }
        }
    }
};

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int flag_col0 = false, flag_row0 = false;
        for (int i = 0; i < m; i++) {
            if (!matrix[i][0]) {
                flag_col0 = true;
            }
        }
        for (int j = 0; j < n; j++) {
            if (!matrix[0][j]) {
                flag_row0 = true;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (!matrix[i][j]) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (!matrix[i][0] || !matrix[0][j]) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (flag_col0) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        if (flag_row0) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
    }
};

收获

无