Neunomizuの日記

俺だけが俺だけじゃない

# LeetCode Easy 706. Design HashMap

tags: leetcode

問題

イデア

HashMapを実装せよという問題.この手の問題ってHash関数を決めるのが面倒だし,この手の問題はコードで実装するというより口頭で説明出来れば良い気がする.

だから,実装は適当です.

  • put(key, value): HashMapに(key, value)を挿入する.すでに,HashMapに存在していれば,valueを更新する.
  • get(key): keyによって指定された値を返す.もし,なければ-1を返す.
  • remove(key): もしあれば,keyによって指定される値を削除する.

解法

std::vectorの要素にstd::listを使い,std::pairを入れたり出したりします.

計算量

HashMapの大きさが$M$,挿入する要素の数が$N$がです.

  • 時間計算量
    • コンストラクタは$O(M)$
    • put(key, value)は$O(1)$, get(key)は平均$O(1)$で最悪$O(N)$でremove(key)も同様
  • 空間計算量
    • コンストラクタは$O(M)$
    • 他は全て$O(1)$

C++

class MyHashMap {
private:
  vector<list<pair<int, int>>> hashMap;
  size_t mapSize = 10000;
public:
    /** Initialize your data structure here. */
    MyHashMap() {
      hashMap.resize(mapSize);
    }
    
    /** value will always be non-negative. */
    void put(int key, int value) {
      auto &list = hashMap[key % mapSize];
      for (auto& pair : list) {
        if (pair.first == key) {
          pair.second = value;
          return;
        }
      }
      list.emplace_back(key, value);
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    int get(int key) {
      const auto &list = hashMap[key % mapSize];
      if (list.empty())
        return -1;
      
      for (const auto& pair : list) {
        if (pair.first == key) {
          return pair.second;
        }
      }
      return -1;
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
      auto &list = hashMap[key % mapSize];
      for (auto pair = list.begin(); pair != list.end(); ++pair) 
        if (pair->first == key) {
          list.erase(pair);
          return;
        }
    }
};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */

# LeetCode Easy 705. Design HashSet

tags: leetcode

学科の研究室の選抜(?)の第一段階に自分の名前がなくて萎えています.

研究室に顔を出しても入れなかったらどうしようか…と思い鬱.とりあえず実装をします.

問題

イデア

組み込みライブラリを使わずにHashSetを設計せよという問題.以下の関数を含む必要がある.

  • add(value): HaseSetに値を挿入する.
  • contains(value): HashSetに値が存在するかどうかを返す.
  • remove(value): HashSetから値を取り除く.もし,HashSetに値がなければ何もしない.

どの程度の実装にすれば良いのかよくわからず…

解法1(お手軽)

雑過ぎる解法として1次元のboolean配列で管理するという方法があります.

この問題の値の範囲が狭いことからこの解法でも可能です(おそらくもっと大きくした方が問題として良いです).

計算量

値の範囲が[0, N)とします.

  • 時間計算量
    • コンストラクタは$O(N)$で,他は$O(1)$
  • 空間計算量
    • コンストラクタは$O(N)$で,他は$O(1)$

値の範囲が広くなると空間計算量が非常に大きくなるので実際にこの方法で実装されることはないはず?

C++

class MyHashSet {
private:
  vector<bool> hashSet;
public:
    /** Initialize your data structure here. */
    MyHashSet(): hashSet(vector<bool>(1000001)) {}
    
    void add(int key) {
      hashSet[key] = true;
    }
    
    void remove(int key) {
      hashSet[key] = false;
    }
    
    /** Returns true if this set contains the specified element */
    bool contains(int key) {
      return hashSet[key];
    }
};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet* obj = new MyHashSet();
 * obj->add(key);
 * obj->remove(key);
 * bool param_3 = obj->contains(key);
 */

解法2(二次元配列)

実装がバグっているので後日上げるかも知れません(これ何回目だ).

# LeetCode Medium 622. Design Circular Queue

tags: leetcode

こういう実装系の問題をやっていきたいのでやっている系です.

次にHash系とTrieを実装したら,多分普通の問題を解きます.

問題

イデア

Circular Queueとは要するにFIFOで,最後の部分が先頭に繋がっているようなデータ構造です.

利点としては,普通のqueueでは空間が余ってしまいますが,このデータ構造では空間を有効的に活用できるという点です.

  • MyCircularQueue(k): Constructor.queueの大きさをkに定める.
  • Front: queueの先頭を手に入れる.空なら-1を返す.
  • Rear: queueの末尾を手に入れる.空なら-1を返す.
  • enQueue(value): circular queueに要素を挿入する.操作が成功したかをbool値で返す.
  • deQueue(): circular queueから要素を削除する.操作が成功したかをbool値で返す.
  • isEmpty(): queueが空か返す.
  • isFull(): queueが満杯か返す.

解法

queueとしてstd::vectorを使います.

先頭と末尾を指す変数headtailを使います.

また,現在のqueueの要素数を表すsizeと最初に決めたqueueの容量maxSizeをコンストラクタで定義します.

このようにすると以下のように定義出来ます()

計算量

  • 時間計算量
    • コンストラクタを実行する時は$O(k)$
    • 他は全て$O(1)$
  • 空間計算量
    • コンストラクタを実行する時は$O(k)$
    • 他は全て$O(1)$

C++

class MyCircularQueue {
  
public:
    /** Initialize your data structure here. Set the size of the queue to be k. */
    MyCircularQueue(int k): queue(vector<int>(k)), head(0), tail(-1), size(0), maxSize(k) {}
    
    /** Insert an element into the circular queue. Return true if the operation is successful. */
    bool enQueue(int value) {
      if (isFull())
        return false;
      tail = (tail + 1) % maxSize;
      queue[tail] = value;
      ++size;
      return true;
    }
    
    /** Delete an element from the circular queue. Return true if the operation is successful. */
    bool deQueue() {
      if (isEmpty())
        return false;
      head = (head + 1) % maxSize;
      --size;
      return true;
    }
    
    /** Get the front item from the queue. */
    int Front() {
      if (isEmpty())
        return -1;
      else
        return queue.at(head);
    }
    
    /** Get the last item from the queue. */
    int Rear() {
      if (isEmpty())
        return -1;
      else
        return queue.at(tail);
    }
    
    /** Checks whether the circular queue is empty or not. */
    bool isEmpty() {
      return size == 0;
    }
    
    /** Checks whether the circular queue is full or not. */
    bool isFull() {
      return size == maxSize;
    }
private:
  vector<int> queue;
  int head;
  int tail;
  int size;
  const int maxSize;
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue* obj = new MyCircularQueue(k);
 * bool param_1 = obj->enQueue(value);
 * bool param_2 = obj->deQueue();
 * int param_3 = obj->Front();
 * int param_4 = obj->Rear();
 * bool param_5 = obj->isEmpty();
 * bool param_6 = obj->isFull();
 */
 ```

# LeetCode Medium 707. Design Linked List

tags: leetcode

インターンの応募ってこの時期多いのか中々返信が来ないですよね

待っている間に出来ることはたくさんあると思うんですが,私は待たされている状態にパフォーマンスが落ちるので出来ればあっちから連絡が欲しいですね(笑)←笑(笑)

問題

イデア

連結リストを設計せよという問題です.

単方向でも双方向でもいいらしいので,ここでは簡単単方向を設計します.

  • get(index):index目のノードを返す.なければ-1を返す.
  • addAtHead(val): 先頭にvalを持つノードを付け,それを先頭とする.
  • addAtTail(val): 末尾にvalを持つノードを付け,それを末尾とする.
  • addAtIndex(index, val): index目のノードにvalを持つノードを付ける.
  • deleteAtIndex(index): index目のノードを削除する

解法(doubly linked list)

実装するだけなのですが,その前に双方向なのでNodeのメンバー変数にはvalnextprevが必要です.

先頭を指すポインタheadだけでなく,末尾を指すポインタtailを使うことで計算量を落としています.

sizeによって処理を簡単にしています.

計算量

ノードの数を$N$とします.

  • get(index)
    • 平均$O(N)$
  • addAtHead(val)
    • $O(1)$
  • addAtTail(val)
    • $O(1)$
  • addAtIndex(index, val)
    • 平均$O(N)$
  • deleteAtIndex(index)
    • 平均$O(N)$

C++

struct Node {
  int val;
  Node* next;
  Node* prev;
  Node(int x) : val(x), next(NULL), prev(NULL) {}
};
class MyLinkedList {
private:
  Node *head, *tail;
  int size;
public:
    /** Initialize your data structure here. */
    MyLinkedList() {
        head = NULL;
        tail = NULL;
        size = 0;
    }
    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    int get(int index) {
      if (!head || index < 0 || size <= index)
        return -1;
      auto cur = head;
      for (int i = 0; i < index; ++i) {
        cur = cur->next;
      }
      return cur->val;
    }
    
    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    void addAtHead(int val) {
      auto newNode = new Node(val);
      newNode->next = head;
      if (head)
        head->prev = newNode;
      head = newNode;
      if (!tail)
        tail = head;
      ++size;
    }
    
    /** Append a node of value val to the last element of the linked list. */
    void addAtTail(int val) {
      auto newNode = new Node(val);
      if (tail) {
        tail->next = newNode;
        newNode->prev = tail;
        tail = newNode;
      } else {
        head = newNode;
        tail = newNode;
      }
      ++size;
    }
    
    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    void addAtIndex(int index, int val) {
      if (index <= size) {
        auto newNode = new Node(val);
        if (!head) {
          head = newNode;
          tail = newNode;
        } else {
          if (index == size) {
            auto cur = head;
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
          } else {
            auto cur = head;
            for (int i = 0; i < index; ++i)
              cur = cur->next;
            newNode->next = cur;
            newNode->prev = cur->prev;
            if (cur->prev)
              cur->prev->next = newNode;
            else
              head = newNode;
            cur->prev = newNode;
          }
        }
        ++size;
      }
    }
    
    /** Delete the index-th node in the linked list, if the index is valid. */
    void deleteAtIndex(int index) {
      if (head && 0 <= index && index < size) {
        auto cur = head;
        for (int i = 0; i < index; ++i)
          cur = cur->next;
        if (cur->prev) {
          if (cur->next) {
            cur->prev->next = cur->next;
            cur->next->prev = cur->prev;
          } else {
            cur->prev->next = NULL;
            tail = cur->prev;
          }
        } else {
          if (cur->next) {
            cur->next->prev = NULL;
            head = cur->next;
          } else {
            head = NULL;
            tail = NULL;
          }
        }
        --size;
      }
    }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

# 自分がやりたいことを整理する

tags: その他

動機

一般的に大学3年生にもなると就職とか研究が気になってきますよね.

僕の場合は

「東大だし情報系だし就活は別に何もしなくてなんとかなるでしょ(笑)」

と思って生きていたのですが,留年しそうになって考えが変わりました.

というのも留年すると1年位暇になるのでその間に自分がする,本当にやりたいことを探す必要が出てくるからです.

となると,自分が本当にしたいのは就職かそれとも研究かというもの考える必要が出てきます.そこでこの記事を書くことに.

過去編

ということで過去を振り返ります.

  • 小中高時代
    • 本を読む・洋楽を聞く・ゲーム・バイトしかしていない(大学生っぽい?)
    • 何も得られないまま死ぬのは怖いと思った
    • 何も残せないで死ぬ恐怖から世界に貢献して生きた証がほしいと思った(笑)
    • 同年代の優秀な中国人にあってこのままだとまずいと思った
    • 世界引っ張りてぇ~~~
  • 大学1・2年
    • 教育に興味があって大学入った
      • そもそも格差とか人の違いみたいなのに興味があった
      • どこで差が付くのかを考えてマクロで見ると教育に原因があると思った
      • 世界の教育がしっかりしていれば世界の人間が幸せに生きることができると思った(頭ハッピーセット)
    • 大学では教育学をやろうか法学を修めて官僚として教育に携わろうか迷って文系学部ならどこでも(進学選択で楽に)行ける文Iを選んだ
      • 国連に入って世界で教育のしっかりしていない地域で貢献したいと思っていたので将来的に大学院に入ることを考えると官僚は国内で実務も得られるし良いと思っていた
      • 教育学の本場は英語(?)と思い英語の勉強をしていた
    • 理論を学ぶのは大事だと思ったが,実際に自分の目で見ることが大事だと思いボランティアに参加した
    • 加えて個別指導の塾で働いた
    • 加えて加えて色んな人と関わった方がいいのかなと思い,人間と関わるためにバイトを色々した(なぜサークル活動に熱心じゃなかったのかというと同じような人が集まると思っていたから)
    • もう少し大規模にそういうことをしようと思ったけど失敗した
    • そんな感じで生きていたらなんか自分上手くやっているのではと満足してきた
    • ちょっと違う...俺が求めているのはもっとこう,なんというか,乾いた感情であって,こういう大したことをしていない現状に満足することじゃないんだと思った
    • 教育現場のボランティアを通して思ったのは教育は現場だけだと変えられない.というか親に&'ぷされた女の子とか,親が謎の宗教にハマっている子供とかどうやって教育で変えるねん
      • もちろん長い目で見れば変えられるかもしれない.ただ,教育というのは結構精神を持っていかれるので,長期間こういうエグい子供の話を聞くのは耐性がないと難しそう.僕は自分の精神が先にやられると思ったのでやめた.
      • 加えて,ボランティアとは体の良い奴隷で,学生をタダ働きさせるための方便でしかなかった.大学生は勉強して将来金を稼ぐなどして貢献した方が良いと思った.
      • かと言って,金が絡むとまたきな臭い方向に成るということから結局お金がない人間には公教育からアプローチする必要があると感じた.つまり,今の自分には何も出来ないのかと疑問に感じた.
    • そこで人工知能ブームがあってこれでなんとかするかぁとなった(笑)
      • 具体的には人工知能を使って自動で最適化した問題を提供し続けるソフトウェアがあれば,教師は見守っているだけで勉強に子供が集中でき,他の部分で手伝えると思った.
    • 根本的に人の考え方を変えるには教育じゃなくてテクノロジーだと考えた
    • そこで東大のサークルでそういうのをやっているのに入って勉強をした.機械学習エンジニアのインターンも少しした
    • 学科は計数かEEICかにしようと思って点数の関係上EEICになった
      • 根本的なところから変えたいと思ったので計数(応用数学っぽい)が1番良いと思った.多少文系からいわゆる理転するからそれに対して数学に負い目を感じていたのもあるかもしれない.
      • EEICはハードとソフトが学べると聞いたから行こうと思った.実際はあまり良い選択ではなかった気がするが,結局自分でやるしかないのでどうでもよいと思う.まぁ文系からの選択なのでしょうがない.
    • 結局EEICに入った.学科の授業は本当につまらなかった.正直電気回路とか半導体とかを勉強して何になるのか未だに分からない.コンピュータを抽象化をして扱えるようにしているのに,わざわざなぜこんなものを…だから劣化理情なんだよと思いながらも適当に単位を回収した.
      • なお必修である電気回路と電磁気の単位がまずいので留年しそうに
      • だが,これも良い機会なのかなと思っている.全ての出来事は今に繋がっているのだなと感じる(感情的だ)
    • ということで「本質」を学ぶべく所謂理論を中心に学んでいた
      • 俺が変えたいのは時代の潮流.それは大きな流れでそれを変えるものが「本質」
      • ただ,小さな流れにも興味がある
      • 両者ともに学びたいとは思っているが現在の優先度は前者の方が重要だと考えているので,先に学んでいた

そして,現在編へ.

現在編

本質は分からなくても,その奥深さは分かってきたので,それを活かしたいと思っています

インターンで働いて金を稼ぎながら実践する機会が欲しいと思っていますが,先日ある会社に落ちました…逆に落ちたことで応募する勇気が出てきたので結果オーライ(?)ですが.

色んな会社に応募をしました.合格するのはいつなのかな^^;

To be continued...

今考えているのは留年しなかった場合です.

留年したらインターンをしながら気ままに研究室に潜り込んで研究をするか起業を学科同期とすれば良いと思っています.自由に与えられた時間を自由に生きるだけです(親の金銭的援助を受けながら).こっちは研究室に正式に配属されない分楽に生きられます.

ただ,留年しないとなると自分が本当にしたのはなんなのかわからないで困っています.自由に時間が与えられたらやることは決まっているのに,逆に時間が奪われるとどうして良いか分からなくなってしまいます.俺は狂っているのか?本当にそれがやりたいことなのか?という葛藤に襲われます.

本当に迷っています.休学して留年した際と同じように生きたいと思うこともあれば,1年がもったいなく感じられて普通に研究して普通に(大多数と同様に?)1年で卒業したいと思うこともあります.大学院に行く前提も最近なくなりました.大学院に行く意味ももっと考えないといけない気がしています.学部で卒業するなら別に休学してもいいのかなとか思いつつも,学部で卒業して1回働いてから大学院行くというのもありに思えて,それなら大学で休学する必要はないんじゃないのかとか思いながらうんぬんかんぬんちんぷんかんぷん.

ということで未だに決心が付いていないので大学は早く留年するかどうかを教えてくれ!

結論

全く整理出来なかった!!!