力扣提交未通过题目重写-3 1915/1942/1953

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 <= 105
• word 由从 '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< 
 
 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.length
2 <= n <= 104
times[i].length == 2
1 <= arrivali < leavingi <= 105
0 <= 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 wait = new PriorityQueue<>();
        for(int i = 0; i < m; i++){
            wait.offer(i);
        }

        //占用椅子
        PriorityQueue use = new PriorityQueue<>(new Comparator() {
            @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.length
1 <= n <= 105
1 <= 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;
    }
}
 
评论点赞收藏✨关注，是送给作者最好的礼物，愿我们共同学习，一起进步
 
如果对作者发布的内容感兴趣，可点击下方关注公众号 钰娘娘知识汇总 查看更多作者文章哦！