今天晚上没什么事，继续刷刷题吧，一周一篇，我这都欠了补补了欠的忘记具体怎么样了，只能有空就刷刷题度日了。
大礼包
题目：在LeetCode商店中， 有许多在售的物品。然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。现给定每个物品的价格，每个大礼包包含物品的清单，以及待购物品清单。请输出确切完成待购清单的最低花费。每个大礼包的由一个数组中的一组数据描述，最后一个数字代表大礼包的价格，其他数字分别表示内含的其他种类物品的数量。任意大礼包可无限次购买。
示例 1:
输入: [2,5], [[3,0,5],[1,2,10]], [3,2]
输出: 14
解释:
有A和B两种物品，价格分别为¥2和¥5。
大礼包1，你可以以¥5的价格购买3A和0B。
大礼包2， 你可以以¥10的价格购买1A和2B。
你需要购买3个A和2个B， 所以你付了¥10购买了1A和2B（大礼包2），以及¥4购买2A。
示例 2:
输入: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
输出: 11
解释:
A，B，C的价格分别为¥2，¥3，¥4.
你可以用¥4购买1A和1B，也可以用¥9购买2A，2B和1C。
你需要买1A，2B和1C，所以你付了¥4买了1A和1B（大礼包1），以及¥3购买1B， ¥4购买1C。
你不可以购买超出待购清单的物品，尽管购买大礼包2更加便宜。
说明:
最多6种物品， 100种大礼包。
每种物品，你最多只需要购买6个。
你不可以购买超出待购清单的物品，即使更便宜。
思路：怎么怎么说呢，可以理解为最优解。而一说到最优解不得不说的就是dp。所以这里暂时把这个题往dp的思路上想。毕竟单纯的回溯的话，也不是不行。但是最多100中礼包。。。这回溯的代价。。好像也不是不行，我先去试试。
我大概已经是个废物了，这里附上代码:
public class Solution {
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
//单个价格也当个礼包。一个单个的总价就是单价
return dfs(price,special, needs);
}
public int dfs(List<Integer> price,List<List<Integer>> special, List<Integer> needs) {
int min = cost(price, needs);
for(List<Integer> list : special) {
List<Integer> needs1 = new ArrayList<Integer>();
int i;
for(i = 0;i<needs.size();i++) {
needs1.add(needs.get(i)-list.get(i));
//这个商品多了，直接pass
if(needs1.get(i)<0) break;
}
//到这说明这个礼包可以用
if(i == needs.size()) min = Math.min(min, dfs(price, special, needs1)+list.get(needs.size()));
}
return min;
}
//当前商品都单买花多少钱
public int cost(List<Integer> price,List<Integer> needs) {
int res = 0;
for(int i = 0;i<price.size();i++) res += price.get(i)* needs.get(i);
return res;
}
}
别说第一版了，上面的不怎么地的代码差不多是最终版了，第一版本思路差不多，超时了，然後一点一点优化，最终才勉强ac。我又看了下我第一版本的代码，也不知道脑子进了多少水才会想出这么个注意。。。我把每一个单价都放在大礼包里面了。。。反正一言难尽。性能没想象中的差，但是也不怎么好，我去看看性能排行第一的代码：
class Solution {
private int sum_price;
/**
* 当前给定价格和对应的需求，直接购买需要的钱数
* @param price：单价价格
* @param needs：需求量
* @return 直接购买的钱数
*/
public int directBuy(List<Integer> price, List<Integer> needs){
int total = 0;
for (int i = 0; i < needs.size(); i++) {
total += price.get(i) * needs.get(i);
}
return total;
}
public boolean canUse(List<Integer> offers, List<Integer> needs){
boolean temp = true;
for (int i = 0; i < needs.size(); i++) {
if (offers.get(i) > needs.get(i)) {
temp = false;
break;
}
}
return temp;
}
/**
*
* @param price:商品单价数组
* @param needs：商品需求数组
* @param specials：大礼包集合数组
* @param index：大礼包当前使用到的下标
* @param cur_used：当前的花销
*/
public void helper(List<Integer> price, List<Integer> needs, List<List<Integer>> specials, int index, int cur_used){
if (cur_used > this.sum_price) return;
if (index == specials.size()) {
cur_used += directBuy(price, needs);
if (cur_used < this.sum_price) this.sum_price = cur_used;
return;
}
List<Integer> offer = specials.get(index); // 大礼包当中的优惠策略可以使用
if (this.canUse(offer, needs)) {
List<Integer> newNeeds = new ArrayList<>();
for (int i = 0; i < needs.size(); i++) {
// needs.set(i, needs.get(i) - offer.get(i)) ;
newNeeds.add(needs.get(i) - offer.get(i));
}
helper(price, newNeeds, specials, index, cur_used + offer.get(offer.size()-1));
}
helper(price, needs, specials, index+1, cur_used); // 大礼包当中的优惠策略不可以使用
}
/**
*
* @param price:单品价格
* @param special：大礼包
* @param needs：需求数组
* @return 返回需要用到的钱数
*/
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
this.sum_price = directBuy(price, needs);
helper(price, needs, special, 0, 0);
return this.sum_price;
}
}
Dota2参议院
题目：Dota2 的世界里有两个阵营：Radiant(天辉)和 Dire(夜魇)Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的一项：
禁止一名参议员的权利：
参议员可以让另一位参议员在这一轮和随后的几轮中丧失所有的权利。
宣布胜利：如果参议员发现有权利投票的参议员都是同一个阵营的，他可以宣布胜利并决定在游戏中的有关变化。给定一个字符串代表每个参议员的阵营。字母 “R” 和 “D” 分别代表了 Radian（天辉）和 Dire（夜魇）。然后，如果有 n 个参议员，给定字符串的大小将是 n。以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是 Radiant 或 Dire。
示例 1：
输入："RD"
输出："Radiant"
解释：第一个参议员来自 Radiant 阵营并且他可以使用第一项权利让第二个参议员失去权力，因此第二个参议员将被跳过因为他没有任何权利。然后在第二轮的时候，第一个参议员可以宣布胜利，因为他是唯一一个有投票权的人
示例 2：
输入："RDD"
输出："Dire"
解释：
第一轮中,第一个来自 Radiant 阵营的参议员可以使用第一项权利禁止第二个参议员的权利
第二个来自 Dire 阵营的参议员会被跳过因为他的权利被禁止
第三个来自 Dire 阵营的参议员可以使用他的第一项权利禁止第一个参议员的权利
因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利
提示：
给定字符串的长度在 [1, 10,000] 之间.
思路：这个题让我想起一句话：先手开团。。哈哈，反正意思就是这样，除了在阵容都是一样的情况下，肯定是要先ban人，ban人的规则应该是紧挨着自己的那个，让对面没机会出手是王道。所以思路很简单，每个人都ban离自己最近的那个异族。直到只剩下一个阵营。思路太清晰了，我去试试代码
第一版本代码出炉了，虽然性能不行但是启发了我有了别的思路，先贴出来：
class Solution {
public String predictPartyVictory(String senate) {
char[] c = senate.toCharArray();
while(true) {
for(int i = 0;i<c.length;i++) {
if(c[i]=='n') continue;
if(!ban(c, i)) {
if(c[i] == 'R') {
return "Radiant";
}else {
return "Dire";
}
}
}
}
}
public boolean ban(char[] c,int idx) {
for(int i = idx+1;i<c.length;i++) {
if(c[i]!=c[idx] && c[i] != 'n') {
c[i] = 'n';
return true;
}
}
for(int i = 0;i<idx;i++) {
if(c[i] != c[idx] && c[i] != 'n') {
c[i] = 'n';
return true;
}
}
return false;
}
}
这个代码就是无脑暴力了，判断有没有可ban的，没有就胜利，有就ban人。。。然后性能也就这么无脑的不好了。。。感觉启发我的思路就是可不可以用一种更优雅的方式来实现。。。一方面记录ban的人，当一个阵营的人都被ban了就输了。另一方面记录被ban人的下标，下次到他就直接略过？反正这么处理感觉都挺麻烦。。我再想想怎么实现。
改了一下，完美ac，超过百分之九十七的人，开森。。哈哈，我贴代码：
class Solution {
public String predictPartyVictory(String senate) {
return ban(senate, 0, 0);
}
public String ban(String senate,int d,int r) {
StringBuffer sb = new StringBuffer();
for(char c:senate.toCharArray()) {
if(c=='D') {//当前元素是d
if(d>0) {
d--;//可以ban
}else {//当前元素不用ban。
sb.append(c);
r++;//可以ban一个R
}
}else {
if(r>0) {
r--;
}else {
sb.append(c);
d++;
}
}
}
if(sb.indexOf("D") == -1) return "Radiant";
if(sb.indexOf("R") == -1) return "Dire";
return ban(sb.toString(), d, r);
}
}
怎么说呢，我这里用dp的方式。记录应该ban 的人数，然后到了每一个元素判断当前用不用ban，这样的操作感觉比第一版用n表示已ban性能好的多。果然做题最主要的是静下心来，心慌慌的真的影响思路。哈哈，下一题了。
石子游戏6
题目：Alice 和 Bob 轮流玩一个游戏，Alice 先手。一堆石子里总共有 n 个石子，轮到某个玩家时，他可以 移出 一个石子并得到这个石子的价值。Alice 和 Bob 对石子价值有 不一样的的评判标准 。给你两个长度为 n 的整数数组 aliceValues 和 bobValues 。aliceValues[i] 和 bobValues[i] 分别表示 Alice 和 Bob 认为第 i 个石子的价值。所有石子都被取完后，得分较高的人为胜者。如果两个玩家得分相同，那么为平局。两位玩家都会采用 最优策略 进行游戏。
请你推断游戏的结果，用如下的方式表示：
如果 Alice 赢，返回 1 。
如果 Bob 赢，返回 -1 。
如果游戏平局，返回 0 。
示例 1：
输入：aliceValues = [1,3], bobValues = [2,1]
输出：1
解释：
如果 Alice 拿石子 1 （下标从 0开始），那么 Alice 可以得到 3 分。
Bob 只能选择石子 0 ，得到 2 分。
Alice 获胜。
示例 2：
输入：aliceValues = [1,2], bobValues = [3,1]
输出：0
解释：
Alice 拿石子 0 ， Bob 拿石子 1 ，他们得分都为 1 分。
打平。
示例 3：
输入：aliceValues = [2,4,3], bobValues = [1,6,7]
输出：-1
解释：
不管 Alice 怎么操作，Bob 都可以得到比 Alice 更高的得分。
比方说，Alice 拿石子 1 ，Bob 拿石子 2 ， Alice 拿石子 0 ，Alice 会得到 6 分而 Bob 得分为 7 分。
Bob 会获胜。
提示：
n == aliceValues.length == bobValues.length
1 <= n <= 105
1 <= aliceValues[i], bobValues[i] <= 100
思路：这个题是今晚双周赛中的一个题目。很可惜在规定时间内超时了所以没ac，不过还好的是有了思路。我觉得这个题还是挺有意思的，所以也就在这里简单的记录一下。首先一开始我的思路是看自己拿最多的和看对面拿最多的哪个合适，陷入了一个误区。就是我要找出自己最多的我要拿的值和对面拿的值，另一方面是对面拿最多的自己拿的值和对面拿的值。看差值哪边大。说的可能比较绕。简单来说就是如果我这边最值钱的是4，对面是1.对面最值钱的是7，我这边2。这样的话我拿我这边最值钱的是4，对面最之前的是2.如果我拿对面的我损失了2。如果只有两个数的时候，对面拿不到7只能拿1，所以对面损失了6.这种情况最优解就是拿2。反过来类似。
其实到现在我也不想说我思路错了，只不过是绕了。各种算来算去，其实一句话可以解释的通：我这边拿了X获取其对应的价值，对面就损失了X对应的价值。所以每一个石子的价值可以看成是 在我这的价值和在对面的价值的和。只不过到手里的价值就变成在自己这边的价值了。由此这个一开始我想的很复杂的题目就简单了。
因为还剩五六分钟才把思路理明白，所以第一版本果断超时了，下面这个是能ac的版本：
class Solution {
public int stoneGameVI(int[] aliceValues, int[] bobValues) {
int suma = 0;
int sumb = 0;
//第一个是和，第二个是下标。
int[][] d = new int[aliceValues.length][2];
for(int i = 0;i<aliceValues.length;i++) {
d[i][0] = aliceValues[i]+bobValues[i];
d[i][1] = i;
}
Arrays.sort(d, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if(o1[0]==o2[0]) return 0;
return o1[0]>o2[0]?-1:1;
}
});
int n = 0;
while(n<aliceValues.length) {
if(n%2 == 0) {
suma += aliceValues[d[n][1]];
}else {
sumb += bobValues[d[n][1]];
}
n++;
}
if(suma==sumb) return 0;
return suma>sumb?1:-1;
}
}
这个题是我的意难平啊，就差九分钟，太可惜了，都是泪。然后我现在大半夜的在这一遍写一遍懊悔，哎。就这样吧。明天周赛看看有没有值得记录的题吧。
设置循环双端队列
题目：设计实现双端队列。你的实现需要支持以下操作：
MyCircularDeque(k)：构造函数,双端队列的大小为k。
insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true。
insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。
deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回 true。
deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。
getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。
getRear()：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1。
isEmpty()：检查双端队列是否为空。
isFull()：检查双端队列是否满了。
示例：
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1); // 返回 true
circularDeque.insertLast(2); // 返回 true
circularDeque.insertFront(3); // 返回 true
circularDeque.insertFront(4); // 已经满了，返回 false
circularDeque.getRear(); // 返回 2
circularDeque.isFull(); // 返回 true
circularDeque.deleteLast(); // 返回 true
circularDeque.insertFront(4); // 返回 true
circularDeque.getFront(); // 返回 4
提示：
所有值的范围为 [1, 1000]
操作次数的范围为 [1, 1000]
请不要使用内置的双端队列库。
思路：简单来说这种开放式题目，实现的方式有多种。我记得前不久刷了一个题是循环队列的。就是用两个指针指向当前的push/pop地址。这个是双端的话，感觉大同小异。还是一样的思路就是多了一个从头部取元素的方法，我去实现了。
好了，这个题和预计的差不多，我直接附上代码：
class MyCircularDeque {
int[] arr;
int first;
int end;
int k;
/** Initialize your data structure here. Set the size of the deque to be k. */
public MyCircularDeque(int k) {
this.k = k;
this.arr = new int[k];
this.first = 0;
this.end = 0;
}
/** Adds an item at the front of Deque. Return true if the operation is successful. */
public boolean insertFront(int value) {
//元素满了肯定插不进去
if(end-first == k+1) return false;
if(end == first) end++;
int start = first--;
if(start<0) start = k+start;
arr[start%k] = value;
return true;
}
/** Adds an item at the rear of Deque. Return true if the operation is successful. */
public boolean insertLast(int value) {
//元素满了肯定插不进去
if(end-first == k+1) return false;
if(first == end) first--;
int last = end++;
if(last<0) last = k+last;
arr[last%k] = value;
return true;
}
/** Deletes an item from the front of Deque. Return true if the operation is successful. */
public boolean deleteFront() {
//没元素肯定是false
if(first+1 == end) return false;
first++;
return true;
}
/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
public boolean deleteLast() {
//没元素肯定是false
if(first+1 == end) return false;
end--;
return true;
}
/** Get the front item from the deque. */
public int getFront() {
if(first+1 == end) return -1;
int start = first+1;
if(start<0) start = k+start;
return arr[start%k];
}
/** Get the last item from the deque. */
public int getRear() {
if(first+1 == end) return -1;
int last = end-1;
if(last<0) last = k+last;
return arr[last%k];
}
/** Checks whether the circular deque is empty or not. */
public boolean isEmpty() {
return first+1 == end;
}
/** Checks whether the circular deque is full or not. */
public boolean isFull() {
return first+k+1 == end;
}
}
/**
* Your MyCircularDeque object will be instantiated and called as such:
* MyCircularDeque obj = new MyCircularDeque(k);
* boolean param_1 = obj.insertFront(value);
* boolean param_2 = obj.insertLast(value);
* boolean param_3 = obj.deleteFront();
* boolean param_4 = obj.deleteLast();
* int param_5 = obj.getFront();
* int param_6 = obj.getRear();
* boolean param_7 = obj.isEmpty();
* boolean param_8 = obj.isFull();
*/
因为头尾都能删除都能插入，所以初始化的时候开始指针和结束指针一样，但是当有元素插入以后要分开的。反正代码都不复杂，我是面向测试案例不断改才ac了，主要是这个first+1=end这块一开始没想到，所以一个方法改一次，麻烦的狠。
这个性能超过百分之九十九了，所以我也不看别人的代码了，直接下一题。
最长数对链
题目：给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例：
输入：[[1,2], [2,3], [3,4]]
输出：2
解释：最长的数对链是 [1,2] -> [3,4]
提示：
给出数对的个数在 [1, 1000] 范围内。
思路：感觉这是一道乱入的题目吧。第一反应就是贪心。大概思路就是给定数组排序，按照第一个数的大小排序。然后第一个数一样按照第二个数大小。最终的结果是从头遍历，取尾数最小的。我去写代码试一下。
一次ac，而且思路顺畅的很，代码也比较简单。
class Solution {
public int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if(o1[0]<o2[0]) return -1;
if(o1[0]>o2[0]) return 1;
return o1[1]<o2[1]?-1:1;
}
});
int last = pairs[0][1];
int res = 1;
for(int[] i : pairs) {
if(i[0]>last) {//可以续
res++;
last = i[1];
}else {//续不上改成较小的那个作为数对链结尾
last = Math.min(last, i[1]);
}
}
return res;
}
}
其实思路也很简单，排序后小的开始在前面，所以后面的一定可以代替前面的数对。当不能续上以后，选择结尾小的有助于下次续上。经典贪心应该是。
这个题就这样了。
这篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！
