2019-11-10

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;
    }
};