LeetCode 29 차 격주 전, 195 차 전 부분 해제

1493. 하나의 요 소 를 삭제 한 후에 모두 1 인 최 장자 배열 의 제목: 바 이 너 리 배열 nums 를 드 리 겠 습 니 다. 그 중에서 요 소 를 삭제 해 야 합 니 다.요 소 를 삭제 한 결과 배열 에서 가장 길 고 1 만 포 함 된 비 빈 배열 의 길 이 를 되 돌려 주 십시오.이러한 하위 배열 이 존재 하지 않 는 다 면 0 으로 돌아 가세 요.
교묘 한 해석.

class Solution {
public:
    int longestSubarray(vector<int>& a) {
        int ans = 0, n = a.size();
        vector<int> a1,a2;
        a1.resize(n);
        a1[0] = a[0]; 
        a2.resize(n);
        a2[n-1] = a[n-1];
        for(int i=1;i<n;i++){
            if(a[i]) a1[i] = a1[i-1]+1;
        }
        for(int i=n-2;i>=0;i--){
            if(a[i]) a2[i] = a2[i+1]+1;
        }
        for(int i=0;i<n;i++){
            int s1,s2;
            if(i==0) s1 = 0;
            else s1 = a1[i-1];
            if(i==n-1) s2 = 0;
            else s2 = a2[i+1];
            ans = max(ans,s1+s2);
        }
        return ans;
    }
};

4. 567917. 미끄럼 창: 최대 0 개 만 있 는 창 을 유지 합 니 다

class Solution {
public:
    int longestSubarray(vector<int>& a) {
        int l=0,r=0,n=a.size(),cnt=0,ans = 0;
        while(l<n){
            while(r<n && (a[r] || cnt==0)){
                if(a[r]==0) cnt++;
                r++;
            }
            ans = max(ans,r-l-1); //         
            if(a[l++]==0) cnt--;
        }
        return ans;
    }
};

1496. 경로 가 교차 하 는 지 여 부 를 제목 의 뜻 에 따라 모 의 하면 된다.

class Solution {
public:
    typedef pair<int,int> P;
    set<P> vis;
    bool isPathCrossing(string path) {
        vis.insert(make_pair(0,0));
        int x =0,y = 0;
        for(char c:path){
            if(c=='N'){
                y++;
            }else if(c=='E'){
                x++;
            }else if(c=='S'){
                y--;
            }else{
                x--;
            }
            P nP = make_pair(x,y);
            if(vis.count(nP)){
                return 1;
            }
            vis.insert(nP);
        }
        return 0;
    }
};

1497. 배열 이 k 에 의 해 제 거 될 수 있 는 지 확인 합 니 다. 정수 배열 arr 와 정수 k 를 드 리 겠 습 니 다. 그 중에서 배열 의 길 이 는 짝수 이 고 값 은 n 입 니 다.모든 숫자의 합 이 k 로 나 눌 수 있 도록 배열 을 n / 2 쌍 으로 나 누 어야 합 니 다.이러한 분 법 이 존재 한다 면 True 로 돌아 가세 요.그렇지 않 으 면 false 로 돌아 갑 니 다.
이산 수학 에서 의 모 n 잉여 류 집합, 즉 Z k = {[0], [1],..., [k - 1]} Z 고찰k = \ {[0], [1],..., [k - 1] \ \} Zk = {[0], [1],..., [k - 1]} 그 중 [x] k [x]k [x] k 는 x x x 모드 k k 와 같은 요소 의 집합 을 나타 낸다.이 사고방식 에 따라 각 잉여 류 의 개 수 를 통계 하면 되 고 그 다음 에 일일이 맞 출 수 있다.

class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        vector<int> m(k,0);
        for(int x:arr){
            m[ (x%k+k)%k ]++;
        }
        if(m[0]&1){
            return false;
        }
        for(int i=1;i<=k/2;i++){
            if(m[i]!=m[k-i]){
                return false;
            }
        }
        return true;
    }
};

1498. 조건 을 만족 시 키 는 하위 시퀀스 의 수량 문제: 정수 배열 nums 와 정수 target 을 드 립 니 다.nums 에서 최소 요소 와 최대 요소 의 합 이 target 보다 작 거나 같은 비 빈자리 시퀀스 의 수 를 통계 하고 되 돌려 주 십시오.
하나의 서열 에는 모두 2n 2 ^ n 2n 의 하위 서열 이 있다.그러나 모든 하위 서열 의 최대 치 와 최소 치 의 합 은 제한 이 있어 단조 로 운 것 이 분명 하 다.먼저 순서 (순서 가 질서 가 있다 고 하지만 제목 의 뜻 은 실제 적 으로 한 부분 집합 을 꺼 내 는 것) 를 배열 한 다음 에 두 바늘 (l, r, l, r, l, r) 의 사상 으로 l l l l 은 어 렸 을 때 부터 매 거 진 것 이다. 비 어 있 기 때문에 l l l 에 대응 하 는 요 소 를 선택 한 다음 에 문제 의 요 구 를 만족 시 키 는 가장 큰 r r r 를 조정 해 야 한다. 이 부분 집합 은 모두 요 구 를 만족 시 키 는 것 이다.개 수 는 2 r - l 2 ^ {r - l} 2r - l 이다.제기 할 만 한 것 은 단조 성 때문에 r r 는 필요 하지 않 아 도 매번 n - 1 n - 1 n - 1 에서 왼쪽으로 이동 할 수 없다. 그렇지 않 으 면 시간 복잡 도 는 선형 이 아니다.

class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
        int MO = 1e9+7,n = nums.size();
        vector<int> mi(n+1,0);
        mi[0] = 1;
        for(int i=1;i<=n;i++){
            mi[i] = (mi[i-1]<<1) % MO;
        }
        sort(nums.begin(),nums.end());
        int l,r = n-1,ans = 0;
        for(l=0;l<n;l++){
            while(l<=r  && nums[l]+nums[r]>target ) r--;
            if(l>r) break;
            ans = (ans+mi[r-l])%MO;
        }
        return ans;
    }
};

1499. 부등식 최대 치 슬라이딩 창 + set 유지보수 창 내 최대 치 를 만족 시 킵 니 다.좌표 x 의 단조 성 으로 인해 실제 적 으로 조건 을 만족 시 키 는 창 안의 최대 치 를 찾 는 것 입 니 다.

class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& a, int k) {
        int ans = -1e9,l = 0,r = 0,n = a.size();
        multiset<int> vis;
        while(l<n){
            while(r<n && a[r][0]-a[l][0]<=k){
                vis.insert(a[r][0]+a[r][1]);
                r++;
            }
            vis.erase(vis.find(a[l][0]+a[l][1]));
            if(vis.size()) ans = max(ans,*vis.rbegin()+a[l][1]-a[l][0]); 
            l++;
        }
        return ans;
    }
};

미끄럼 창 최대 값 은 단조 로 운 대기 열 로 해결 할 수 있 습 니 다. 시간 복잡 도 O (n) O (n) O (n).문제 의 유사 성 때문에 자 연 스 럽 게 단조 로 운 대열 로 해결 할 수 있다.

class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        deque<int> dq;
        int ans = -1e9,n = points.size(),l=0,r=0;
        while(l<n){
            while(r<n && points[r][0]-points[l][0]<=k){
                int val = points[r][0]+points[r][1];
                while(dq.size() && dq.back()<val) dq.pop_back();
                dq.push_back(val);
                r++;
            }
            if(dq.front() == points[l][1]+points[l][0]) dq.pop_front();
            if(dq.size()) ans = max(ans,points[l][1]-points[l][0]+dq.front());
            l++;
        }
        return ans;
    }
};