怎么免费申请网站,怎么创建教育网站,seo手机端排名软件,wordpress博文字符串customers只包含’Y’和’N’两种字母, 表示 i 时刻商店是否有客人来。 如果商店在 i 时刻处于开门状态#xff0c;Y’的代价是0#xff0c;N’的代价是1.#xff08;开门了却没有客人就算损失#xff09;。 反之#xff0c;在 i 时刻处于关门状态#xff0c;N’的…
字符串customers只包含’Y’和’N’两种字母, 表示 i 时刻商店是否有客人来。 如果商店在 i 时刻处于开门状态Y’的代价是0N’的代价是1.开门了却没有客人就算损失。 反之在 i 时刻处于关门状态N’的代价是0Y’的代价是1.关门却有客人来也是损失。
如果商店在 j 时刻关门那么从 j 时刻到最后都是关门状态。 问在哪个时刻关门代价最小。
思路
方法一
先计算一直在关门状态0时刻关门的代价。 然后把关门的时间右移这时候只需要在上一步代价的基础上改变前一时刻的代价值。
举个例子看Example1. 先计算0时刻关门的代价为3.
然后关门时刻移动到时刻1这时时刻1后面还是关门状态代价上没有变化有变化的是0时刻的关门状态变成了开门状态。 这时候需要修改0时刻的代价0时刻是’Y’, 关门时代价是1开门代价是0关门到开门状态需要减去代价1. 这时在上一步代价3的基础上减去多出来的代价1. 所以时刻1的代价为3-12. 后面依次类推。 直到移动到字符串最右边边界外表示一直开门。
这个过程中记下最小代价和对应的时刻。 public int bestClosingTime(String customers) {char[] chs customers.toCharArray();int cntY 0;int cntN 0;int n chs.length;int[] penalty new int[n1];int minP 0;int minIdx 0;//从0时刻起不开门的代价for(int i n-1; i 0; i--) {if(chs[i] Y){cntY ;penalty[i] penalty[i1] 1;} else {cntN ;penalty[i] penalty[i1];}}if(cntY n) return n;if(cntN n) return 0;//i时刻关门minP penalty[0];for(int i 1; i n; i) {if(chs[i-1] Y) penalty[i] penalty[i-1]-1;else penalty[i] penalty[i-1]1;if(penalty[i] minP) {minP penalty[i];minIdx i;}}return minIdx;}方法二
其实不需要计算初始0时刻关门的代价。 因为它是多少并不影响结果。
还是Example1。我们把0最后时刻关门的代价排列一下
3, 2, 1, 2, 1
第2时刻代价最小选在第2时刻关门。
这时把初始时刻关门的代价由3改到0后面还是和方法1一样改变前一时刻的代价于是得到
0, -1, -2, -1, -2
结果还是第2时刻代价最小。所以初始0时刻关门代价是多少都无所谓只要后面能得到代价最小的时刻即可。
省去方法一中计算0时刻关门的代价默认0时刻关门代价是0. 然后右移关门时刻 i , 每移一步改变前一时刻的代价。比如移到1时改变0时刻的代价。 0时刻是’Y’, 关门代价是1开门代价是0现在开门了需要把代价-1反之如果是’N’就1.
右移的过程中记录下最小代价和对应的时刻。 public int bestClosingTime(String customers) {char[] a customers.toCharArray();int n a.length;int j -1, penalty 0, minP 0;for (int i 0; i a.length; i) {penalty a[i] Y? -1 : 1;if (penalty minP) {j i;minP penalty;}}return j 1;}
