【优选算法题练习】day4

摘星

发布于 2023-10-15 15:53:27

1070

发布于 2023-10-15 15:53:27

文章被收录于专栏：C/C++学习C/C++学习

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

1.题目简介

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

2.解题思路

3.代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        if(n == 0 || n == 1) return n;
        int begin = 0, end = 0;
        int ret = 1;
        int hash[128] = {0};
        while(end < n)
        {
            if(hash[s[end]] == 0)
            {
                hash[s[end++]]++;
                ret = max(ret, end - begin);
            }
            else
            {
                hash[s[begin++]]--;
            }
        }
        return ret;
    }
};

4.运行结果

二、1004. 最大连续1的个数 III

1.题目简介

1004. 最大连续1的个数 III 给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回数组中连续 1 的最大个数。

2.解题思路

3.代码

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        //可以将题目转化为求最多有k个0的最长连续区间的长度
        int ret = 0;
        int begin = 0, end = 0;
        int num = 0;//区间内0的个数
        while(end < nums.size())
        {
            if(nums[end++] == 0) num++;//入窗口
            while(num > k)//出窗口
            {
                if(nums[begin++] == 0) num--;
            }
            ret = max(ret, end - begin);
        }
        return ret;
    }
};

4.运行结果

三、1658. 将 x 减到 0 的最小操作数

1.题目简介

1658. 将 x 减到 0 的最小操作数给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要修改数组以供接下来的操作使用。如果可以将 x 恰好减到 0 ，返回最小操作数；否则，返回 -1 。

2.解题思路

3.代码

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
    //可以将题目转化为求nums数组中一段最长的和为sum(nums) - x的连续子数组的长度len(再用nums.size() - len就能得到结果)
        int sum = 0;
        for(auto& e : nums)
        {
            sum += e;
        }
        int target = sum - x;
        if(target < 0) return -1;
        int len = -1;
        sum = 0;
        int left = 0, right = 0;
        while(right < nums.size())
        {
            //入窗口
            sum += nums[right++];
            //出窗口
            while(sum > target)
            sum -= nums[left++];
            //更新结果
            if(sum == target)
            {
                len = max(len, right - left);
            }
        }
        if(len == -1)
        {
            return -1;
        }
        return nums.size() - len;
    }
};