wap网站制作怎么做,抖音测一测小程序怎么赚钱,首钢建设集团山东公司网站,电子商务网站dw建设实验报告目录 1.最大连续1的个数 III
1.题目解析
2.算法原理
2.1暴力枚举#xff08;不过多介绍#xff09;
2.2双指针优化
3.代码编写
2. 将 x 减到 0 的最小操作数
1.题目解析
2.算法原理
2.1滑动窗口
3.代码编写
3. 水果成篮
1.题目解析
2.算法思路
2.1滑动窗口哈希…目录 1.最大连续1的个数 III
1.题目解析
2.算法原理
2.1暴力枚举不过多介绍
2.2双指针优化
3.代码编写
2. 将 x 减到 0 的最小操作数
1.题目解析
2.算法原理
2.1滑动窗口
3.代码编写
3. 水果成篮
1.题目解析
2.算法思路
2.1滑动窗口哈希表 1.最大连续1的个数 III
1.题目解析
。 2.算法原理
2.1暴力枚举不过多介绍 int longestOnes(vectorint nums, int k) {int n nums.size();int ret 0;for(int i 0; in; i){int t k;int cnt 0;for(int j i; jn; j){if(nums[j] 1){cnt;}else if(nums[j] 0){t--;if(t 0){break; }cnt;}ret max(ret,j-i1);}}return ret;
} 2.2双指针优化
在暴力解法中发现两个指针是同向一起向后走考虑双指针优化。
将问题转化为维护一个区间区间内部的0的个数不能超过k。求最长的区间。
进窗口遍历数组如果nums[right] 0,计数器cnt--
判断区间内0的个数是否超过k
出窗口left直到区间内0的个数小于k
3.代码编写 int longestOnes(vectorint nums, int k) {int left 0,right 0;int ret 0, cnt 0;while(right nums.size()){if(nums[right] 0){cnt;}while(cnt k){ if(nums[left] 0){cnt--;}left; }ret max(ret,right - left 1);right;}return ret;} 2. 将 x 减到 0 的最小操作数
1.题目解析
这道乍一看左边减一次右边见一次很不好处理这个时候用逆向思维可以很好解决问题。
让操作次数最短就是让左右两边的和为x长度加起来最短转换一下让中间部分和为sum-x最长sum为整个数组的和。
求和为sum-x的最长子数组
2.算法原理
2.1滑动窗口
求数组整体的和sum
进窗口遍历数组cnt nums[right]
判断cnt的值是否大于target
出窗口cnt - nums[left]
3.代码编写 int minOperations(vectorint nums, int x) {int sum 0;for(int i : nums){sum i;}int target sum - x;int n nums.size();if(target 0)return -1;int cnt 0;int ret -1;for(int left 0,right 0; right nums.size(); right){cnt nums[right];while(cnt target){cnt - nums[left];left;}if(cnt target)ret max(ret,right-left1);}return ret -1 ? -1 : n -ret ;} 3.最大连续1的个数 III
1.题目解析 说了一大堆翻译成人话就是
求数字种类不超过2种的最长子数组。12就是不同的水果种类
2.算法思路
2.1滑动窗口哈希表
进窗口:进哈希表数字种类。
判断哈希表的大小是否大于2
出窗口将left指针指向的元素在哈希表中数字种类--减为0之后删除直到哈希表的大小小于2。
int totalFruit(vectorint fruits) {//找一个最长连续的子数组子数组内的类型不能超过2种unordered_mapint,int hash;int ret 0;int left 0, right 0;while(right fruits.size()){ hash[fruits[right]];//进窗口while(hash.size() 2)//判断{ hash[fruits[left]]--;//出窗口if(hash[fruits[left]] 0){hash.erase(fruits[left]);}left;}ret max(ret,right-left1);right;}return ret;}
