LeetCode Weekly Contest 151 3問目 - Remove Zero Sum Consecutive Nodes from Linked List [1171]

Source

LeetCode Weekly Contest 151
問題文

問題概要

省略

解法

省略

cLay（version 20190829-1）のコード [C++に変換後]

#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
template<class S> void arrErase(int k, int &sz, S a[]){
  int i;
  sz--;
  for(i=(k);i<(sz);i++){
    a[i] = a[i+1];
  }
}
template<class S, class T> void arrErase(int k, int &sz, S a[], T b[]){
  int i;
  sz--;
  for(i=(k);i<(sz);i++){
    a[i] = a[i+1];
  }
  for(i=(k);i<(sz);i++){
    b[i] = b[i+1];
  }
}
template<class S, class T, class U> void arrErase(int k, int &sz, S a[], T b[], U c[]){
  int i;
  sz--;
  for(i=(k);i<(sz);i++){
    a[i] = a[i+1];
  }
  for(i=(k);i<(sz);i++){
    b[i] = b[i+1];
  }
  for(i=(k);i<(sz);i++){
    c[i] = c[i+1];
  }
}
template<class S> void arrInsert(const int k, int &sz, S a[], const S aval){
  int i;
  sz++;
  for(i=sz-1;i>k;i--){
    a[i] = a[i-1];
  }
  a[k] = aval;
}
template<class S, class T> void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval){
  int i;
  sz++;
  for(i=sz-1;i>k;i--){
    a[i] = a[i-1];
  }
  for(i=sz-1;i>k;i--){
    b[i] = b[i-1];
  }
  a[k] = aval;
  b[k] = bval;
}
template<class S, class T, class U> void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval){
  int i;
  sz++;
  for(i=sz-1;i>k;i--){
    a[i] = a[i-1];
  }
  for(i=sz-1;i>k;i--){
    b[i] = b[i-1];
  }
  for(i=sz-1;i>k;i--){
    c[i] = c[i-1];
  }
  a[k] = aval;
  b[k] = bval;
  c[k] = cval;
}
#define main dummy_main
int main(){
  return 0;
}
#undef main

class Solution{
  public:
  ListNode* removeZeroSumSublists(ListNode* head){
    ListNode *p[1000];
    int N, arr[1000], fg, i, j, k;
    map<int,int> mp;
    {
      ListNode *a=head;
      N = 0;
      while(a!=NULL){
        arrInsert(N, N, arr, a->val, p, a);
        a = a->next;
      }
    }
    for(;;){
      mp.clear();
      mp[0] = 0;
      k = 0;
      fg = 0;
      for(i=0;i<(N);i++){
        k += arr[i];
        if(mp.count(k)){
          j = mp[k];
          while(i >= j){
            arrErase(i, N, arr, p);
            i--;
          }
          fg++;
          break;
        }
        mp[k] = i+1;
      }
      if(!fg){
        break;
      }
    }
    if(N==0){
      return NULL;
    }
    for(i=0;i<(N-1);i++){
      p[i]->next = p[i+1];
    }
    p[N-1]->next = NULL;
    return p[0];
  }
}
;
// cLay varsion 20190829-1

// --- original code ---
// #define main dummy_main
// {}
// #undef main
// 
// struct ListNode {
//     int val;
//     ListNode *next;
// };
// 
// class Solution {
// public:
//   ListNode* removeZeroSumSublists(ListNode* head) {
//     int i, j, k, N, fg;
//     int arr[1000];
//     map<int,int> mp;
//     ListNode *p[1000];
// 
//     {
//       ListNode *a = head;
//       N = 0;
//       while(a!=NULL){
//         arrInsert(N, N, arr, a->val, p, a);
//         a = a->next;
//       }
//     }
// 
//     for(;;){
//       mp.clear();
//       mp[0] = 0;
//       k = 0;
//       fg = 0;
//       rep(i,N){
//         k += arr[i];
//         if(mp.count(k)){
//           j = mp[k];
//           while(i >= j) arrErase(i, N, arr, p), i--;
//           fg++;
//           break;
//         }
//         mp[k] = i+1;
//       }
//       if(!fg) break;
//     }
// 
//     if(N==0) return NULL;
//     rep(i,N-1) p[i]->next = p[i+1];
//     p[N-1]->next = NULL;
// 
//     return p[0];
//   }
// };

Current time: 2024年04月26日00時52分58秒
Last modified: 2019年08月30日08時00分21秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)