class Solution {
/**
* 双指针
*/
public void sortColors(int[] nums) {
int l = -1; // 设定[0...l]区间为0, [l + 1...i)前闭后开的区间为1, i表示遍历中要考察的元素
int r = nums.length; // [r...nums.length)前闭后开的区间值为2
int i = 0;
while(i < r){
if(nums[i] == 0){
l++;
nums[l] = 0;
if(l != i){
nums[i] = 1;
}
i++;
} else if(nums[i] == 1){
i++;
} else {
r--;
nums[i] = nums[r];
nums[r] = 2;
}
}
}
}
class ExamRoom {
public:
int N;//所有座位的个数
int haveSeated;//已经座了人的座位数
vector<int> mySeats;//存储各个座位的状态
ExamRoom(int N) {
this->N = N;//执行初始化操作
haveSeated = 0;
mySeats = vector<int>(N, 0);
}
int seat() {
//maxDis 是当前找到的离附近的人最远的间隔数,maxInsert 是对应的下标(坐的位置)
int maxDis = 0, maxInsert = 0, index = 0;
//检测第0个位置是否有人坐(也就是最前端是否有空位置段)
while (index < N && mySeats[index] == 0){
++index;
}
maxDis = index;//前端出现空位置段初始化为坐在第0个位置,否则index = 0,也可以初始化为第0个位置
maxInsert = 0;
while (index < N){
//跳过坐了人的位置
while (index < N && mySeats[index] == 1){
++index;
}
//确定连续空位置区间
int beforeIndex = index - 1;//beforeIndex记录空位置段的前一个坐了人的下标
while (index < N && mySeats[index] == 0){
++index;
}
//更新最大结果
if (index == N){
//连续的空位置出现尾端,坐在尾端
if (maxDis < index - beforeIndex - 1){
maxInsert = N - 1;
maxDis = index - beforeIndex - 1;
}
}
else if (maxDis < (index - beforeIndex) / 2){//坐在空位置段的中间
maxDis = (index - beforeIndex) / 2;
maxInsert = beforeIndex + (index - beforeIndex) / 2;
}
}
haveSeated += 1;
mySeats[maxInsert] = 1;
return maxInsert;
}
void leave(int p) {
mySeats[p] = 0;
haveSeated -= 1;
}
};
class Solution {
public int longestConsecutive(int[] nums) {
int max = 0;
HashMap<Integer,Integer> map = new HashMap<>();
for (int i:nums){
if(map.getOrDefault(i,0)==0){
int left = map.getOrDefault(i-1,0);
int right = map.getOrDefault(i+1,0);
map.put(i,left+right+1);
if(left!=0){
map.put(i-left,left+right+1);
}
if(right!=0){
map.put(i+right,right+left+1);
}
max = max>(left+right+1)?max:(left+right+1);
}
}
return max;
}
};
网友评论