Fixed win size sliding window

2024-01-06 16:20
文章标签 window win size fixed sliding

本文主要是介绍Fixed win size sliding window,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这篇记录灵神题单中的定长滑窗环节,不跟之前的Sliding Window一起了。

1. LC 1423 可获得的最大点数

这题其实有点思维的。实现上简单。

每次从首或者尾部拿,总共拿k次。相当于有n-k张牌不拿。因为不可能从中间截断着拿,因此必然这n-k张牌是连续的,所以就变成定长n-k滑窗。更新维护最小值,最终拿总和减掉最小值就是能拿的最大值。

import java.util.HashMap;class Solution {public int maxScore(int[] cardPoints, int k) {int sum = 0;for (int cardPoint : cardPoints) {sum+=cardPoint;}int rest = 0;int n = cardPoints.length;for (int i = 0; i < (n - k); i++) {rest += cardPoints[i];}int min = rest;for(int i=1;i<=k;i++){rest = rest - cardPoints[i-1]+cardPoints[i+n-k-1];min = Math.min(min,rest);}return (sum-min);}
}

2. LC 2134 最少交换次数来组合所有的1Ⅱ

这题是任意位置交换,不是相邻位置。有时间想想相邻交换要怎么做。

统计所有1的个数,统计当前区间(区间长度就是这个个数,因为把所有1聚集起来)的1的个数,差就是交换次数,维护最小值即可。统计区间的1很显然是个滑窗,环形数组取余即可。

import java.util.Arrays;class Solution {public int minSwaps(int[] nums) {int oT = 0;for (int num : nums) {oT += num==1?1:0;}int ans = oT+1;int t = 0;for(int i=0;i<oT;i++){t += nums[i]==1?1:0;}ans = Math.min(ans,oT-t);for(int i=1;i<nums.length;i++){t += (nums[i-1]==1?-1:0) + (nums[(i+oT-1)%nums.length]==1?1:0);ans = Math.min(ans,oT-t);}return ans;}
}

3. LC 2653 滑动子数组的美丽值

这题我写的很丑。

大致思路就是模拟,每个窗口更新维护一个有序哈希表,里面只存放负数的数量,然后从小到大累加各个负数的数量,直到找到第k小。

这种题用数组自己模拟比官方库快多了

import java.util.*;class Solution {public int[] getSubarrayBeauty(int[] nums, int k, int x) {int n = nums.length;int[] ans = new int[n - k + 1];Arrays.fill(ans,0);TreeMap<Integer, Integer> tm = new TreeMap<>();for (int i = 0; i < k; i++) {if(nums[i]<0){mAdd(tm,nums[i]);}}iter(ans,x,tm,0);for(int i=1;i<=n-k;i++){if(nums[i-1]<0){mRemove(tm,nums[i-1]);}if(nums[i+k-1]<0){mAdd(tm,nums[i+k-1]);}iter(ans,x,tm,i);}return ans;}private void iter(int[] ans,int x,Map<Integer,Integer> m,int index){int t = 0;for (Map.Entry<Integer, Integer> next : m.entrySet()) {t += next.getValue();if (t >= x) {ans[index] = next.getKey();return;}}}private void mAdd(Map<Integer,Integer> m,int num){m.put(num,m.getOrDefault(num,0)+1);}private void mRemove(Map<Integer,Integer> m,int num){Integer t = m.get(num);if(null==t){return;}if(1==t){m.remove(num);return;}m.put(num,t-1);}
}

这篇关于Fixed win size sliding window的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/576901

相关文章

Window Server创建2台服务器的故障转移群集的图文教程

《WindowServer创建2台服务器的故障转移群集的图文教程》本文主要介绍了在WindowsServer系统上创建一个包含两台成员服务器的故障转移群集,文中通过图文示例介绍的非常详细,对大家的... 目录一、 准备条件二、在ServerB安装故障转移群集三、在ServerC安装故障转移群集,操作与Ser

Window Server2016加入AD域的方法步骤

《WindowServer2016加入AD域的方法步骤》:本文主要介绍WindowServer2016加入AD域的方法步骤,包括配置DNS、检测ping通、更改计算机域、输入账号密码、重启服务... 目录一、 准备条件二、配置ServerB加入ServerA的AD域(test.ly)三、查看加入AD域后的变

Window Server2016 AD域的创建的方法步骤

《WindowServer2016AD域的创建的方法步骤》本文主要介绍了WindowServer2016AD域的创建的方法步骤,文中通过图文介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录一、准备条件二、在ServerA服务器中常见AD域管理器:三、创建AD域,域地址为“test.ly”

python中os.stat().st_size、os.path.getsize()获取文件大小

《python中os.stat().st_size、os.path.getsize()获取文件大小》本文介绍了使用os.stat()和os.path.getsize()函数获取文件大小,文中通过示例代... 目录一、os.stat().st_size二、os.path.getsize()三、函数封装一、os

windows端python版本管理工具pyenv-win安装使用

《windows端python版本管理工具pyenv-win安装使用》:本文主要介绍如何通过git方式下载和配置pyenv-win,包括下载、克隆仓库、配置环境变量等步骤,同时还详细介绍了如何使用... 目录pyenv-win 下载配置环境变量使用 pyenv-win 管理 python 版本一、安装 和

js window.addEventListener 是什么?

window.addEventListener 是 JavaScript 中的一个方法,用于向指定对象(在这个情况下是 window 对象,代表浏览器窗口)添加事件监听器,以便在该对象上发生特定事件时执行相应的函数(称为事件处理函数或事件监听器)。 这个方法接受三个参数: 事件类型(type):一个字符串,表示要监听的事件类型。例如,"click" 表示鼠标点击事件,"load" 表示页面加

Debugging Lua Project created in Cocos Code IDE creates “Waiting for debugger to connect” in Win-7

转自 I Installed Cocos Code IDE and created a new Lua Project. When Debugging the Project(F11) the game window pops up and gives me the message waiting for debugger to connect and then freezes. Also a

Qt中window frame的影响

window frame 在创建图形化界面的时候,会创建窗口主体,上面会多出一条,周围多次一圈细边,这就叫window frame窗口框架,这是操作系统自带的。 这个对geometry的一些属性有一定影响,主要体现在Qt坐标系体系: 窗口当中包含一个按钮,这个按钮的坐标系是以父元素为参考,那么这个参考是widget本体作为参考,还是window frame作为参考,这两种参考体系都存在

Caused by: android.view.WindowManager$BadTokenException: Unable to add window -- token android.os.B

一个bug日志 FATAL EXCEPTION: main03-25 14:24:07.724: E/AndroidRuntime(4135): java.lang.RuntimeException: Unable to start activity ComponentInfo{com.syyx.jingubang.ky/com.anguotech.android.activity.Init

最初的window

不知你是否也是一个常年在MFC下编程的程序员,有的时候是否忘记了在MFC之前是如何写画窗口的了呢,或者你从来都只是机械的在MFC下面写代码,已经麻木了。其实有一个很简单的方法,或许能够帮你更清楚的了解WINDOW是怎么产生的。 随便用什么版本的VS,在创建win32工程的时候,直接创建WINDOW类型的就OK了。然后,来研究下产生的源代码吧。 // Global Variables:H