?
1915. 最美子字符串的数目
难度中等71
如果某个字符串中?至多一个?字母出现?奇数?次，则称其为?最美?字符串。
- 例如，
"ccjjc"?和?"abab"?都是最美字符串，但?"ab"?不是。给你一个字符串?
word?，该字符串由前十个小写英文字母组成（'a'?到?'j'）。请你返回?word?中?最美非空子字符串?的数目。如果同样的子字符串在?word?中出现多次，那么应当对?每次出现?分别计数。子字符串?是字符串中的一个连续字符序列。
示例 1：
输入：word = "aba" 输出：4 解释：4 个最美子字符串如下所示： - "aba" -> "a" - "aba" -> "b" - "aba" -> "a" - "aba" -> "aba"示例 2：
输入：word = "aabb" 输出：9 解释：9 个最美子字符串如下所示： - "aabb" -> "a" - "aabb" -> "aa" - "aabb" -> "aab" - "aabb" -> "aabb" - "aabb" -> "a" - "aabb" -> "abb" - "aabb" -> "b" - "aabb" -> "bb" - "aabb" -> "b"示例 3：
输入：word = "he" 输出：2 解释：2 个最美子字符串如下所示： - "he" -> "h" - "he" -> "e"提示：
1 <= word.length <= 105word?由从?'a'?到?'j'?的小写英文字母组成来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-wonderful-substrings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
做题结果：
失败，关键点10个字母已抓到，看到提示位运算还是想不到，水平不够。
题目关键点：
1. 只有10种字母
2. 是不是美丽串只与奇偶性有关，与其他规则无关
3. 奇数-奇数=偶数，偶数-偶数=偶数，也就是说减去奇偶性相同的可得到所有元素是偶数的种类数，允许有一个奇数，也就是可以有一个奇偶性不同，所以只与之前每个字母状态有关，奇偶性可使用位运算状态标识
class Solution {
public long wonderfulSubstrings(String word) {
long ans = 0;
//代表此奇偶性状态共出现几次
long[] state = new long[1<<10];
//出现0次也是偶数，需要计数
state[0] = 1;
//掩码，对应二进制位1代表奇数次，0代表偶数次
int mask = 0;
int n = word.length();
for(int i = 0; i < n; i++){
int index = word.charAt(i)-'a';
mask = mask ^(1<<index);//获得当前长度的奇偶性
ans += state[mask];//获得当前奇偶性相同数目
for(int j = 0; j < 10; j++){
ans += state[mask ^ (1<<j)];//获得某一种字母不同的奇偶性数目
}
state[mask]++;
}
return ans;
}
}1942. 最小未被占据椅子的编号
难度中等23
有?
n?个朋友在举办一个派对，这些朋友从?0?到?n - 1?编号。派对里有?无数?张椅子，编号为?0?到?infinity?。当一个朋友到达派对时，他会占据?编号最小?且未被占据的椅子。
- 比方说，当一个朋友到达时，如果椅子?
0?，1?和?5?被占据了，那么他会占据?2?号椅子。当一个朋友离开派对时，他的椅子会立刻变成未占据状态。如果同一时刻有另一个朋友到达，可以立即占据这张椅子。
给你一个下标从?0?开始的二维整数数组?
times?，其中?times[i] = [arrivali, leavingi]?表示第?i?个朋友到达和离开的时刻，同时给你一个整数?targetFriend?。所有到达时间?互不相同?。请你返回编号为?
targetFriend?的朋友占据的?椅子编号?。示例 1：
输入：times = [[1,4],[2,3],[4,6]], targetFriend = 1 输出：1 解释： - 朋友 0 时刻 1 到达，占据椅子 0 。 - 朋友 1 时刻 2 到达，占据椅子 1 。 - 朋友 1 时刻 3 离开，椅子 1 变成未占据。 - 朋友 0 时刻 4 离开，椅子 0 变成未占据。 - 朋友 2 时刻 4 到达，占据椅子 0 。 朋友 1 占据椅子 1 ，所以返回 1 。示例 2：
输入：times = [[3,10],[1,5],[2,6]], targetFriend = 0 输出：2 解释： - 朋友 1 时刻 1 到达，占据椅子 0 。 - 朋友 2 时刻 2 到达，占据椅子 1 。 - 朋友 0 时刻 3 到达，占据椅子 2 。 - 朋友 1 时刻 5 离开，椅子 0 变成未占据。 - 朋友 2 时刻 6 离开，椅子 1 变成未占据。 - 朋友 0 时刻 10 离开，椅子 2 变成未占据。 朋友 0 占据椅子 2 ，所以返回 2 。提示：
n == times.length2 <= n <= 104times[i].length == 21 <= arrivali?< leavingi?<= 1050 <= targetFriend <= n - 1- 每个?
arrivali?时刻?互不相同?。来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/the-number-of-the-smallest-unoccupied-chair
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
做题结果：
成功，和昨天那题很像，比昨天那题简单
做题思路：
首先是用堆，需要考虑各种因素动态排序
1. 使用新的数组保存开始时间、结束时间，另外保存朋友编号，用于避免排序后朋友编号丢失
2. 按开始时间排序
3. 记录占用椅子和未占用椅子，注意占用椅子排序需要考虑编号顺序
4. 按朋友顺序依次查找可用的椅子，找到指定朋友，结束判断
class Solution {
public int smallestChair(int[][] times, int targetFriend) {
int m = times.length;
int[][] friends = new int[m][3];
for(int i = 0; i < m; i++){
friends[i][0] = times[i][0];
friends[i][1] = times[i][1];
friends[i][2] = i;
}
//按开始时间先排序
Arrays.sort(friends,Comparator.comparingInt(o->o[0]));
//可用椅子，m把够了
PriorityQueue<Integer> wait = new PriorityQueue<>();
for(int i = 0; i < m; i++){
wait.offer(i);
}
//占用椅子
PriorityQueue<int[]> use = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if(o1[1]!=o2[1]) return o1[1]-o2[1];
return o1[0]-o2[0];
}
});
for(int i = 0; i < m; i++){
//释放到时间的椅子
while (!use.isEmpty() && use.peek()[1]<=friends[i][0]){
wait.offer(use.poll()[0]);
}
//待选中拿变化小的椅子
int chair = wait.poll();
use.offer(new int[]{chair,friends[i][1]});
if(friends[i][2]==targetFriend){
//返回期望结果
return chair;
}
}
return -1;
}
}1953. 你可以工作的最大周数
难度中等33
给你?
n?个项目，编号从?0?到?n - 1?。同时给你一个整数数组?milestones?，其中每个?milestones[i]?表示第?i?个项目中的阶段任务数量。你可以按下面两个规则参与项目中的工作：
- 每周，你将会完成?某一个?项目中的?恰好一个?阶段任务。你每周都?必须?工作。
- 在?连续的?两周中，你?不能?参与并完成同一个项目中的两个阶段任务。
一旦所有项目中的全部阶段任务都完成，或者仅剩余一个阶段任务都会导致你违反上面的规则，那么你将?停止工作?。注意，由于这些条件的限制，你可能无法完成所有阶段任务。
返回在不违反上面规则的情况下你?最多?能工作多少周。
示例 1：
输入：milestones = [1,2,3] 输出：6 解释：一种可能的情形是： ????- 第 1 周，你参与并完成项目 0 中的一个阶段任务。 - 第 2 周，你参与并完成项目 2 中的一个阶段任务。 - 第 3 周，你参与并完成项目 1 中的一个阶段任务。 - 第 4 周，你参与并完成项目 2 中的一个阶段任务。 - 第 5 周，你参与并完成项目 1 中的一个阶段任务。 - 第 6 周，你参与并完成项目 2 中的一个阶段任务。 总周数是 6 。示例 2：
输入：milestones = [5,2,1] 输出：7 解释：一种可能的情形是： - 第 1 周，你参与并完成项目 0 中的一个阶段任务。 - 第 2 周，你参与并完成项目 1 中的一个阶段任务。 - 第 3 周，你参与并完成项目 0 中的一个阶段任务。 - 第 4 周，你参与并完成项目 1 中的一个阶段任务。 - 第 5 周，你参与并完成项目 0 中的一个阶段任务。 - 第 6 周，你参与并完成项目 2 中的一个阶段任务。 - 第 7 周，你参与并完成项目 0 中的一个阶段任务。 总周数是 7 。 注意，你不能在第 8 周参与完成项目 0 中的最后一个阶段任务，因为这会违反规则。 因此，项目 0 中会有一个阶段任务维持未完成状态。提示：
n == milestones.length1 <= n <= 1051 <= milestones[i] <= 109
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-number-of-weeks-for-which-you-can-work
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
做题结果：
成功，贪就完事
做题思路：
1. 当最大任务是其他任务和加1的时候，可以通过完成一个最大任务，再完成一个其他任务的方式，完成所有任务
2. 当最大任务大于其他任务和一加的时候，则最多能完成其他任务和*2+1个任务，原因是最大任务，最多能完成 （其他和+1），其他任务都能完成，最终结果为 其他和+1+其他和=其他和*2+1
class Solution {
public long numberOfWeeks(int[] milestones) {
long sum = 0L;
int n = milestones.length;
int index = 0;
for(int i = 0; i < n; i++){
if(milestones[i]>milestones[index]){
index = i;
}
sum += milestones[i];
}
if(milestones[index]<=sum-milestones[index]+1){
return sum;
}
return (sum-milestones[index])*2+1;
}
}评论🌹点赞👍收藏?关注👀，是送给作者最好的礼物，愿我们共同学习，一起进步
如果对作者发布的内容感兴趣，可点击下方关注公众号?钰娘娘知识汇总?查看更多作者文章哦！
