当前位置: 首页 > news >正文

山东华邦建设网站首页会计培训班一般多少钱

山东华邦建设网站首页,会计培训班一般多少钱,网络维护基础知识,汕头网站建设推广厂家将X减到0的最小操作数 给你一个整数数组 nums 和一个整数 x 。每一次操作时,你应当移除数组 nums 最左边或最右边的元素,然后从 x 中减去该元素的值。请注意,需要 修改 数组以供接下来的操作使用。 如果可以将 x 恰好 减到 0 ,返…

将X减到0的最小操作数

在这里插入图片描述

给你一个整数数组 nums 和一个整数 x 。每一次操作时,你应当移除数组 nums 最左边或最右边的元素,然后从 x 中减去该元素的值。请注意,需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ,返回 最小操作数 ;否则,返回 -1

示例 1:

输入:nums = [1,1,4,2,3], x = 5
输出:2
解释:最佳解决方案是移除后两个元素,将 x 减到 0 。

示例 2:

输入:nums = [5,6,7,8,9], x = 4
输出:-1

示例 3:

输入:nums = [3,2,20,1,1,3], x = 10
输出:5
解释:最佳解决方案是移除后三个元素和前两个元素(总共 5 次操作),将 x 减到 0 。

提示:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104
  • `1 <= x <= 109
    在这里插入图片描述
    在这里插入图片描述
    这里我们可能会觉得正着做去求,会有些困难,可以尝试着反着来做,效果会不一样

算法思路:

题⽬要求的是数组「左端+右端」两段连续的、和为 x 的最短数组,信息量稍微多⼀些,不易理清 思路;我们可以转化成求数组内⼀段连续的、和为 sum(nums) - x 的最⻓数组。此时,就是熟 悉的「滑动窗⼝」问题了。

算法流程:

a. 转化问题:求 target = sum(nums) - x 。如果 target < 0 ,问题⽆解;

b. 初始化左右指针 left = 0 , right = 0 (滑动窗⼝区间表⽰为 [left, right) ,左右区间是否开闭很重 要,必须设定与代码⼀致),记录当前滑动窗⼝内数组和的变量 tmp= 0 ,记录当前满⾜条 件数组的最⼤区间⻓度ret = -1 ;

c. 当 right ⼩于等于数组⻓度时,⼀直循环:

i. 如果 sum < target ,右移右指针,直⾄变量和⼤于等于 target ,或右指针已经移到 头;

ii. 如果 sum > target ,右移左指针,直⾄变量和⼩于等于 target ,或左指针已经移到 头;

iii. 如果经过前两步的左右移动使得 sum == target ,维护满⾜条件数组的最⼤⻓度,并 让下个元素进⼊窗⼝;

d. 循环结束后,如果 ret 的值有意义,则计算结果返回;否则,返回 -1 。

代码如下:

class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum=0;for(int a:nums) sum+=a;int target=sum-x;if(target<0) return -1;int ret=-1;for(int left=0,right=0,tmp=0;right<nums.size();right++){tmp+=nums[right];while(tmp>target)tmp-=nums[left++];if(tmp==target)ret=max(ret,right-left+1);}if(ret==-1)return ret;else return nums.size()-ret;}
};

水果成篮

你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果 种类

你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:

  • 你只有 两个 篮子,并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
  • 你可以选择任意一棵树开始采摘,你必须从 每棵 树(包括开始采摘的树)上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次,你将会向右移动到下一棵树,并继续采摘。
  • 一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘。

给你一个整数数组 fruits ,返回你可以收集的水果的 最大 数目。

示例 1:

输入:fruits = [1,2,1]
输出:3
解释:可以采摘全部 3 棵树。

示例 2:

输入:fruits = [0,1,2,2]
输出:3
解释:可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘,则只能采摘 [0,1] 这两棵树。

示例 3:

输入:fruits = [1,2,3,2,2]
输出:4
解释:可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘,则只能采摘 [1,2] 这两棵树。

示例 4:

输入:fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出:5
解释:可以采摘 [1,2,1,1,2] 这五棵树。

提示:

  • 1 <= fruits.length <= 105
  • 0 <= fruits[i] < fruits.length

题目解析

转化成找出一个最长的子数组的长度,子数组中不能超过两种水果的类型

在这里插入图片描述
算法思路:**

研究的对象是⼀段连续的区间,可以使⽤「滑动窗⼝」思想来解决问题。

让滑动窗⼝满⾜:窗⼝内⽔果的种类只有两种。

做法:右端⽔果进⼊窗⼝的时候,⽤哈希表统计这个⽔果的频次。这个⽔果进来后,判断哈希表的 ⼤⼩:

▪ 如果⼤⼩超过 2:说明窗⼝内⽔果种类超过了两种。那么就从左侧开始依次将⽔果划出窗 ⼝,直到哈希表的⼤⼩⼩于等于 2,然后更新结果;

▪ 如果没有超过 2,说明当前窗⼝内⽔果的种类不超过两种,直接更新结果 ret。

算法流程:

a. 初始化哈希表 hash 来统计窗⼝内⽔果的种类和数量;

b. 初始化变量:左右指针 left = 0,right = 0,记录结果的变量 ret = 0;

c. 当 right ⼩于数组⼤⼩的时候,⼀直执⾏下列循环:

i. 将当前⽔果放⼊哈希表中;

ii. 判断当前⽔果进来后,哈希表的⼤⼩:

• 如果超过 2:

◦ 将左侧元素滑出窗⼝,并且在哈希表中将该元素的频次减⼀;

◦ 如果这个元素的频次减⼀之后变成了 0,就把该元素从哈希表中删除;

◦ 重复上述两个过程,直到哈希表中的⼤⼩不超过 2;

iii. 更新结果 ret;

iv. right++,让下⼀个元素进⼊窗⼝;

d. 循环结束后,ret 存的就是最终结果。

C++ 算法代码(使⽤容器):

class Solution
{
public:int totalFruit(vector<int>& f) {unordered_map<int, int> hash; // 统计窗⼝内出现了多少种⽔果int ret = 0;for(int left = 0, right = 0; right < f.size(); right++){hash[f[right]]++; // 进窗⼝while(hash.size() > 2) // 判断{// 出窗⼝
hash[f[left]]--;if(hash[f[left]] == 0)hash.erase(f[left]);left++;}ret = max(ret, right - left + 1);}return ret;}
};

但是一直插入和删除的时间复杂度会提高,所以根据题目提示是有范围的,可以考虑用数组来模拟哈希表

代码如下(⽤数组模拟哈希表):

class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100001]={0};int ret=0;for(int left=0,right=0,kinds=0;right<fruits.size();right++){if(hash[fruits[right]]==0)  kinds++;hash[fruits[right]]++;while(kinds>2){hash[fruits[left]]--;if(hash[fruits[left]]==0) kinds--;left++;}ret=max(ret,right-left+1);}return ret;}
};
http://www.hrbkazy.com/news/20709.html

相关文章:

  • 网站开发有没有前途怎样在百度上做广告推广
  • 徐州高端网站建设友链交易平台
  • 有什么网站做头像离我最近的电脑培训中心
  • 高校校园网站建设培训班谷歌seo排名优化
  • 深圳西乡地铁站体验营销理论
  • 大学交作业wordpress天津谷歌优化
  • 哪个网站名片做的号seo站长工具查询系统
  • 做婚恋网站seo网站推广方式
  • 秦皇岛旅游攻略南阳网站seo
  • 怎么做视频在线播放网站seo网页优化服务
  • 云南省城乡住房与建设厅网站武汉网站seo
  • 做网站价钱广告软文
  • html5炫酷网站企业邮箱格式
  • 海口网站制作设计百度客服系统
  • 学中文网站南宁企业官网seo
  • 用flash做的网站展示it培训班出来工作有人要么
  • 网站飘窗怎样做抖音seo查询工具
  • 上海做网站 公司排名推广普通话心得体会
  • 当今做啥网站致富关键词小说
  • 网站优化工具升上去百度建站平台官网
  • wordpress503原因seo的优点有哪些
  • 做网站的术语做广告推广哪个平台好
  • 大陆用户禁止访问app郑州网站seo外包
  • 镇江网站seo外包百度公司招聘2022年最新招聘
  • 流量网站制作最新小组排名
  • 北京做网站开发公司电话培训课程设计
  • 专门代做毕设的网站深圳网站建设找哪家公司好
  • 做外贸相关的网站西安关键词排名首页
  • 做vip兼职设计师的网站有哪些万能搜索网站
  • 企业所得税税率5% 10% 25%郑州seo管理