LeetCode:第57场双周赛记录
1941.检查是否所有字符出现次数相同
题目描述
给你一个字符串
s
,如果s
是一个好字符串,请你返回true
,否则请返回false
。
如果s
中出现过的所有字符的出现次数相同,那么我们称字符串s
是好字符串。
提示:
1 <= s.length <= 1000
s
只包含小写英文字母。
解法
用一个Tab
数组记录每个字符出现的次数,随后遍历数组,判断是否出现次数相同即可。
力扣第一题一般都是送分题。。。
class Solution {
public boolean areOccurrencesEqual(String s) {
int[] Tab = new int[26];
for(int i=0;i<s.length();i++) {
Tab[s.charAt(i)-'a']++;
}
int cont = 0;
for(int i=0;i<26;i++) {
if(cont!=0) {
if(Tab[i]!=0&&cont!=Tab[i])
return false;
}else {
if(Tab[i]!=0)
cont=Tab[i];
}
}
return true;
}
}
1942. 最小未被占据椅子的编号
题目描述
有
n
个朋友在举办一个派对,这些朋友从0
到n - 1
编号。派对里有无数
张椅子,编号为0
到infinity
。当一个朋友到达派对时,他会占据编号最小
且未被占据的椅子。
- 比方说,当一个朋友到达时,如果椅子 0 ,1 和 5 被占据了,那么他会占据 2 号椅子。
当一个朋友离开派对时,他的椅子会立刻变成未占据状态。如果同一时刻有另一个朋友到达,可以立即占据这张椅子。
给你一个下标从 0 开始的二维整数数组
times
,其中times[i] = [arrival_i, leaving_i]
表示第i
个朋友到达和离开的时刻,同时给你一个整数targetFriend
。所有到达时间互不相同
。
请你返回编号为targetFriend
的朋友占据的 椅子编号 。
提示
n == times.length
2 <= n <= 10^4
times[i].length == 2
1 <= arrival_i < leaving_i <=10^5
0 <= targetFriend <= n - 1
每个 a r r i v a l i arrival_i arrivali时刻互不相同
解法
竞赛时做这题卡了很久,最后我的思路和别人的也不太一样。
我是用3个哈希表:
hashA
:保存到达时间和朋友编号< a r r i v e i , i arrive_i,i arrivei,i>
hashE
:保存离去时间和朋友编号< l e a v i n g i , i leaving_i,i leavingi,i>
hashChair
:保存朋友编号和椅子编号< i i i,椅子编号>
一个优先队列:
chair
:保存剩下的椅子
然后根据时间遍历for(int i=0;i<10^5)
模拟占椅子的情况,当目标编号占椅子时返回编号。
class Solution {
public int smallestChair(int[][] times, int targetFriend) {
HashMap<Integer,Integer> hashA = new HashMap<Integer, Integer>();
HashMap<Integer,List<Integer>> hashE = new HashMap<>();
HashMap<Integer,Integer> hashChair = new HashMap<Integer, Integer>();
PriorityQueue<Integer> chair = new PriorityQueue<Integer>();
for(int i=times.length-1;i>=0;i--) {
chair.add(i);
}
for(int i=0;i<times.length;i++) {
hashA.put(times[i][0], i);
if(hashE.containsKey(times[i][1])) {
List<Integer> temp = hashE.get(times[i][1]);
temp.add(i);
hashE.put(times[i][1], temp);
}else {
List<Integer> temp = new LinkedList<>();
temp.add(i);
hashE.put(times[i][1], temp);
}
}
for(int i=1;i<=100000;i++) {
//i时刻走,放椅子
if(hashE.containsKey(i)) {
List<Integer> temp = hashE.get(i);
for(int j=0;j<temp.size();j++) {
int cha = hashChair.get(temp.get(j));
hashChair.remove(temp.get(j));
// if(cha==1) {
// System.out.println(cha+"让座"+times[temp.get(j)][1]);
// }
chair.add(cha);
}
}
//i时刻到达,占椅子
if(hashA.containsKey(i)) {
// if(chair.peek()==1) {
// System.out.println(chair.peek()+"占座"+times[hashA.get(i)][0]);
// }
if(hashA.get(i)==targetFriend)
return chair.poll();
hashChair.put(hashA.get(i), chair.poll());
}
}
return -1;
}
}
1943. 描述绘画结果
题目描述
给你一个细长的画,用数轴表示。这幅画由若干有重叠的线段表示,每个线段有独一无二的颜色。给你二维整数数组
segments
,其中segments[i] = [start_i, end_i, color_i]
表示线段为半开区间 [ s t a r t i , e n d i ) [start_i, end_i) [starti,endi) 且颜色为color_i
。
线段间重叠部分的颜色会被混合。如果有两种或者更多颜色混合时,它们会形成一种新的颜色,用一个集合表示这个混合颜色。
- 比方说,如果颜色
2
,4
和6
被混合,那么结果颜色为{2,4,6}
。为了简化题目,你不需要输出整个集合,只需要用集合中所有元素的和来表示颜色集合。
你想要用最少数目不重叠半开区间来表示这幅混合颜色的画。这些线段可以用二维数组
painting
表示,其中painting[j] = [leftj, rightj, mixj]
表示一个半开区间[left_j, right_j)
的颜色和为mix_j
。
- 比方说,这幅画由
segments = [[1,4,5],[1,7,7]]
组成,那么它可以表示为painting = [[1,4,12],[4,7,7]]
,因为:
[1,4)
由颜色{5,7}
组成(和为12
),分别来自第一个线段和第二个线段。[4,7)
由颜色{7}
组成,来自第二个线段。
请你返回二维数组painting
,它表示最终绘画的结果(没有 被涂色的部分不出现在结果中)。你可以按任意顺序返回最终数组的结果。半开区间
[a, b)
是数轴上点a
和点b
之间的部分,包含a且不包含b 。
解法
看到这题的时候狂喜,这题岂不是比第二题还简单?
该题我用2个哈希表:
hashA
:保存segments_i的开始点和片段编号< l e f t i , i left_i,i lefti,i>
注意: 由于left_i会存在重复,因此保存的value实际上是一个链表。
hashE
:保存segments_i的开始点和片段编号< r i g h t i , i right_i,i righti,i>
注意: 由于right_i会存在重复,因此保存的value实际上是一个链表。
然后根据区间的大小遍历for(int i=0;i<10^5)
模拟涂色的情况,当有segement进入或退出时更新一次区间。
class Solution {
public List<List<Long>> splitPainting(int[][] segments) {
HashMap<Integer,List<Integer>> hashA = new HashMap<>();
HashMap<Integer,List<Integer>> hashE = new HashMap<>();
for(int i=0;i<segments.length;i++) {
if(hashA.containsKey(segments[i][0])) {
List<Integer> temp = hashA.get(segments[i][0]);
temp.add(segments[i][2]);
hashA.put(segments[i][0], temp);
}else {
List<Integer> temp = new LinkedList<>();
temp.add(segments[i][2]);
hashA.put(segments[i][0], temp);
}
if(hashE.containsKey(segments[i][1])) {
List<Integer> temp = hashE.get(segments[i][1]);
temp.add(segments[i][2]);
hashE.put(segments[i][1], temp);
}else {
List<Integer> temp = new LinkedList<>();
temp.add(segments[i][2]);
hashE.put(segments[i][1], temp);
}
}
long sum = 0;
int l = 1;
List<List<Long>> ans = new LinkedList<>();
for(int i=1;i<=100000;i++) {
List<Long> ans2 = new LinkedList<>();
//位置i有片段
if(hashA.containsKey(i)) {
if(l!=i) {
ans2.add((long) l);
ans2.add((long) i);
ans2.add(sum);
if(sum!=0)
ans.add(ans2);
l=i;
ans2 = new LinkedList<>();
}
List<Integer> temp = hashA.get(i);
for(int j=0;j<temp.size();j++) {
sum+=temp.get(j);
}
}
//位置i离开
if(hashE.containsKey(i)) {
if(l!=i) {
ans2.add((long) l);
ans2.add((long) i);
ans2.add(sum);
if(sum!=0)
ans.add(ans2);
ans2 = new LinkedList<>();
l=i;
}
List<Integer> temp = hashE.get(i);
for(int j=0;j<temp.size();j++) {
sum-=temp.get(j);
}
}
}
return ans;
}
}
1944. 队列中可以看到的人数
题目描述
有
n
个人排成一个队列,从左到右编号为0
到n - 1
。给你以一个整数数组heights
,每个整数互不相同,heights[i]
表示第i
个人的高度。一个人能看到他右边另一个人的条件是这两人之间的所有人都比他们两人矮。更正式的,第
i
个人能看到第j
个人的条件是i < j
且min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1])
。请你返回一个长度为
n
的数组answer
,其中answer[i]
是第i
个人在他右侧队列中能看到的人数。
提示:
n == heights.length
1 <= n <= 10^5
1 <= heights[i] <= 10^5
heights
中所有数互不相同。
解题思路
竞赛的时候感觉这题应该挺简单的,但是没做出来。
后来看了答案说是单调栈,贴一下后来补的代码
从右到左维护一个单调减栈。
class Solution {
public int[] canSeePersonsCount(int[] heights) {
Stack<Integer> s = new Stack<Integer>();
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=heights.length-1;i>=0;i--) {
int j=i+1;
while(j<heights.length&&heights[i]>heights[j]) {
j=map.get(j);
}
map.put(i, j);
}
for(int i=heights.length-1;i>=0;i--) {
int j=i+1;
int count=0;
while(j<heights.length&&heights[i]>heights[j]) {
j=map.get(j);
count++;
}
if(j!=heights.length)
count++;
s.add(count);
}
int[] ans = new int[s.size()];
for(int i=0;i<ans.length;i++) {
ans[i]=s.pop();
}
return ans;
}
}
总的来说排名还行,第二题虽然卡了但第三题过的很快。。。
贴一下排名和令人发指的bug次数。。。