Neunomizuの日記

俺だけが俺だけじゃない

# LeetCode Medium 173. Binary Search Tree Iterator

tags: leetcode

問題

イデア

二分木のイテレータを作れという問題です.

next()hasNext()というメソッドが時間,空間計算量を平均でそれぞれ$O(1)$,$O(h)$となるようにするという制約があります

解法1

木を配列に変換して,そこからノードを取るという風にします

配列にはinorder,つまり小さい順にノードを入れます.

計算量

ノードの数を$N$として,木の高さを$h$をします

  • 時間計算量
    • 木を配列に変換するのに$O(N)$
    • next()hasNext()に$O(1)$`
  • 空間計算量
    • 再帰の深さから$O(h)$
    • next()hasNext()に$O(1)$
    • ノードを格納する配列に$O(N)$

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
  vector<int> sortedNodes;    
  int index;
  
public:
  BSTIterator(TreeNode* root) {
    index = -1;
    _inorder(root);
  }

  /** @return the next smallest number */
  int next() {
    return sortedNodes.at(++index);
  }

  /** @return whether we have a next smallest number */
  bool hasNext() {
    return index + 1 < sortedNodes.size();
  }
  
private:
  void _inorder(TreeNode* root) {
    if (!root)
      return;
    
    _inorder(root->left);
    sortedNodes.push_back(root->val);
    _inorder(root->right);
  }
};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

解法2

上の解法では二分木のノードの数だけ空間が必要なのでこれをより効率的にするためにスタックを使います.

最初にスタックにinorderでノードを入れます.つまり,値の小さいノードからスタックに積んでいきます.

  • next()
    • スタックの先頭のノードを最小値として返す
    • その際に先頭のノードはポップする
    • そして,先頭の右の子にの左部分木をスタックに積む
  • hasNext
    • 現在のノードの数が0より大きければまだノードが取り出せるので`true

計算量

  • 時間計算量
    • 最初にノードをスタックに積むのに$O(h)$
    • next()hasNext()は共に$O(1)$
  • 空間計算量
    • スタックに積むノードは木の高さに依存するので$O(h)$
    • next()は$O(h)$が必要

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
  stack<TreeNode*> nodeStack;
public:
  BSTIterator(TreeNode* root) {
    _leftMostInorder(root);
  }

  /** @return the next smallest number */
  int next() {
    auto topNode = nodeStack.top();
    nodeStack.pop();
    if (topNode->right)
      _leftMostInorder(topNode->right);
    return topNode->val;
  }

  /** @return whether we have a next smallest number */
  bool hasNext() {
    return nodeStack.size() > 0;
    }
private:
  void _leftMostInorder(TreeNode* root) {
    while (root) {
      nodeStack.push(root);
      root = root->left;
    }
  }
};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

# 留年しても分かるPythonのshallow copyとdeep copy

tags: 情報

shallow copydeep copyの違いとか曖昧だけど必要になったら毎回ググればえーやろ^^

という精神で生きていたらググれない状況でそれを聞かれて破滅しました.こんなのも分からず生きていてごめんなさい...と思いましたが,他人がこれを知らなくても許せる優しい人間になりたい.

人にやさしく自分に厳しい人間になるのが夢です

...俺を反面教師にして「ググったらえーだけやろ」という考えは捨てろ!今すぐだ!

そもそもPythonの代入文は

Pythonの代入文ではmutableなものはアドレスをコピーしているだけなので

# coding: utf-8

b = a = 123
b += 456
print("a = {}, b = {}".format(a, b))

d = c = [1, 2, 3]
d.append(4)
print("c = {}, d = {}".format(c, d))

f = e = "ariga10"
f += "10"
print("e = {}, f = {}".format(e, f))

と書くと出力は

a = 123, b = 579
c = [1, 2, 3, 4], d = [1, 2, 3, 4]
e = ariga10, f = ariga1010

となります.リストはmutableなのでアドレスのコピーが変数に代入されて,それ以外はimmutableなオブジェクトなので値が代入されるというわけです.

mutableなものとしてはlist, set, dictが挙げられます.

Copy

copyというモジュールにあるcopy()というメソッドを使うことで新しいオブジェクトを作り,この問題を解消できるのです.

しかし,ここにも問題があります.copyにはshallow copydeep copyという違いがあることです.

ふざけるなよ...?なんで2つあるんだよ^^;

ちなみに,組み込みメソッドのcopy()shallow copy?だからPythonは嫌いなんだよ^^;

まあ落ち着けよ俺^^;

挙動

下のようなコードを書きます.

# coding: utf-8
import copy

a = [1, 2, [3, 4]]
b = copy.copy(a)
b[0] = 29
b[2][0] = 4649
print("a = {}, b = {}".format(a, b))

c = [5, 6, [7, 8]]
d = copy.deepcopy(c)
d[0] = 810
d[2][0] = 114514
print("c = {}, d = {}".format(c, d))

これを実行すると以下のような結果を得ます.

a = [1, 2, [4649, 4]], b = [29, 2, [4649, 4]]
c = [5, 6, [7, 8]], d = [810, 6, [114514, 8]]

copy.copy()shallow copy,つまり,mutableなオブジェクトの中のmutableなオブジェクトに関してはアドレスしか返さないです.

一方,copy.deepcopy()deep copy,つまりmutableなオブジェクトの中のmutableなオブジェクトに関しても同じオブジェクトを作成して返します.

このコードでは変数a内のリストを参照した値がbのリストに入っているので,bのリストの要素が変更されるとaにまで影響が及びます.

図示すると下のようになります.

まとめ

  • Pythonではmutableな値とimmutableな値のcopyには細心の注意を払おう
  • ググればええやんは面接では通じないし,ググらなくてもいいようにした方がいいよ(N=1)
  • 留年しそうになると頭がやられます

# 電気回路が分からなくても分かるC言語のUnionとStructの違い

tags: 情報

もう電気回路なんてしないなんて言わないよ絶対(なんて言わないよ絶対)

1

電気回路←うわぁ

前回インターンしようと思った会社のCTOが電気系でうわぁ...と思ったら案の定落ちていました.

もう電気のことなんか考えたくもないのでC言語の話をします.

UnionとStruct

なんかこいつら(unionstruct)似てないか?と思う人もたくさんいると思います.

ちなみに去年の今頃は僕もそう思っていませんでした.というか自分が授業をやるならアルゴリズムとかよりもこういう似ている気がするけど実際は違うものの違いを聞くと思います.

まぁそんなことはさておき,こいつらの違いはアドレスを出力してしまえば簡単に分かります.

下のようなコードを書きます.

#include <stdio.h>
#include <stdint.h>

typedef union union_t {
  int8_t i8;
  int16_t i16;
  int32_t i32;
  int64_t i64;
} myUnion;

typedef struct struct_t {
  int8_t i8;
  int16_t i16;
  int32_t i32;
  int64_t i64;
} myStruct;

int main (void) {
  myUnion u;
  myStruct s;

  printf("Address\n");
  printf("\n");
  printf("Union's i8 = %p, i16 = %p, i32 = %p, i64 = %p\n", &(u.i8), &(u.i16), &(u.i32), &(u.i64));
  printf("Struct's i8 = %p, i16 = %p, i32 = %p, i64 = %p\n", &(s.i8), &(s.i16), &(s.i32), &(s.i64));
  printf("-------------\n");
  printf("Union & Struct's Size\n");
  printf("\n");
  printf("myUnion's size = %zu\n", sizeof(myUnion));
  printf("myStruct's size = %zu\n", sizeof(myStruct));
  printf("-------------\n");
  printf("Sizes of types\n");
  printf("\n");
  printf("i8 = %zu, i16 = %zu, i32 = %zu, i64 = %zu\n", sizeof(int8_t), sizeof(int16_t),sizeof(int32_t), sizeof(int64_t));
  return 0;  
}

こいつをgccコンパイルして実行してやると以下のような出力を得ます.

Address

Union's i8 = 0x7fffbb250d48, i16 = 0x7fffbb250d48, i32 = 0x7fffbb250d48, i64 = 0x7fffbb250d48
Struct's i8 = 0x7fffbb250d50, i16 = 0x7fffbb250d52, i32 = 0x7fffbb250d54, i64 = 0x7fffbb250d58
-------------
Union & Struct's Size

myUnion's size = 8
myStruct's size = 16
-------------
Sizes of types

i8 = 1, i16 = 2, i32 = 4, i64 = 8

出力解説

Addressの出力から分かるようにunionはアドレスが全て同じで,structはアドレスが全て違います.

次にUnion & Struct's Sizeを見てみます.ここからは(当然?)使っているメモリの大きさが異なります.

最後に各型の大きさが違うことが分かります.

結論から言ってしまうと,unionはメンバーの型のうち最大のもののメモリ領域を確保して,メンバーのいずれかに値を格納します.

一方,structはメンバー変数のメモリ領域をそれぞれ確保して,それぞれに別々の値を格納します

図示すると下のようになります.

Padding

ただ,今回全てのtypeの大きさを足すと1 + 2 + 4 + 8 = 15bytesです.しかし,myStructの大きさは16 bytesです.

C言語では処理系(gccclangなど)によってパッディング(アラインメント)2と言って構造体内の奇数の大きさの型の大きさを偶数にすることがあります.

ここではint8_tが1 byteなのでパッディングされて2 bytesになっているのでしょう.

まとめ

  • unionは複数の型を選んで使えるようにメモリを共有している
  • structは複数の型を同時に格納できるようにそれぞれにメモリを格納している
  • パッディング(アラインメント)によってメモリの和がそのままstructのメモリの大きさになるわけではない
  • 電気回路を二度と勉強したくない

# Scalaジョブが欲しい

tags: 情報

関数型プログラミングがしたい

業務で関数型プログラミングがしたいです.理由は書いていて楽しいからです.

それだけの理由で仕事先を探しているのです1が,仕事を見つけるためにはスキルが必要です.

ということでScalaのスキルを身につけるべく,Scalaを勉強中.

Scalaのインストール

ドワンゴScalaで有名なのでその資料2を使ってScalaHello Worldをします.

現実のScalaアプリケーションでは、Scalaプログラムを手動でコンパイル1することは非常に稀で、標準的なビルドツールであるsbtというツールを用いることになります。

という文章に従って,とりあえずsbtをインストールします.

公式HPに従ってインストールをします.

echo "deb https://dl.bintray.com/sbt/debian /" | sudo tee -a /etc/apt/sources.list.d/sbt.list
curl -sL "https://keyserver.ubuntu.com/pks/lookup?op=get&search=0x2EE0EA64E40A89B84B2DF73499E82A75642AC823" | sudo apt-key add
sudo apt-get update
sudo apt-get install sbt

これでインストールは完了したっぽいです.

次にHello Worldをします.sbt consoleでREPLを開始し,

println("Hello, World!")

で完了です.

後はこれを見てEmacsをいい感じにしました.

仕事を見つけるまで死にません...


  1. 本当は親からの仕送りがもらえず銀行口座に75円しかないので金がほしいというのもあります.

  2. https://scala-text.github.io/scala_text/sbt-install.html

# LeetCode Easy 724. Find Pivot Index

tags: leetcode

志望度の高かったインターンに落ちて気持ちが萎えています.でも逆にやりたいことがはっきりしました.

問題

イデア

ある要素よりも左の要素の和と右の要素の和が等しい要素のindexを返せという問題です.

解法

最初に配列を全て足し合わせます(C++ならstd::accumulateが便利です).この和をsumとします.

次に,pivotとなる部分までを左から足した値をleft_sumとして2 * left_sum - nums[pivot] == sumとなるはずです.

下の図のようにpivotを境にした左(赤)と右(青)の和は等しいので,2 * left_sumred + blue + 2 * pivotと等しいです

計算量

配列の大きさを$N$とします.

  • 時間計算量
    • $O(N)$
  • 空間計算量
    • $O(1)$

C++

class Solution {
public:
  int pivotIndex(vector<int>& nums) {
    auto sum = accumulate(nums.begin(), nums.end(), 0);
    auto left_sum = 0;
    for (int pivot = 0; pivot < nums.size(); pivot++) {
      left_sum += nums[pivot];
      if (2 * left_sum - nums[pivot] == sum)
        return pivot;
    }
    return -1;
  }
};