# 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 copyとdeep 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 copyとdeep 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: 情報
もう電気回路なんてしないなんて言わないよ絶対(なんて言わないよ絶対)
電気回路←うわぁ
前回インターンしようと思った会社のCTOが電気系でうわぁ...と思ったら案の定落ちていました.
もう電気のことなんか考えたくもないのでC言語の話をします.
UnionとStruct
なんかこいつら(union
とstruct
)似てないか?と思う人もたくさんいると思います.
ちなみに去年の今頃は僕もそう思っていませんでした.というか自分が授業をやるならアルゴリズムとかよりもこういう似ている気がするけど実際は違うものの違いを聞くと思います.
まぁそんなことはさておき,こいつらの違いはアドレスを出力してしまえば簡単に分かります.
下のようなコードを書きます.
#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 = 15
bytesです.しかし,myStruct
の大きさは16 bytesです.
C言語では処理系(gcc
やclang
など)によってパッディング(アラインメント)2と言って構造体内の奇数の大きさの型の大きさを偶数にすることがあります.
ここではint8_t
が1 byteなのでパッディングされて2 bytesになっているのでしょう.
まとめ
union
は複数の型を選んで使えるようにメモリを共有しているstruct
は複数の型を同時に格納できるようにそれぞれにメモリを格納している- パッディング(アラインメント)によってメモリの和がそのまま
struct
のメモリの大きさになるわけではない - 電気回路を二度と勉強したくない
# Scalaジョブが欲しい
tags: 情報
関数型プログラミングがしたい
業務で関数型プログラミングがしたいです.理由は書いていて楽しいからです.
それだけの理由で仕事先を探しているのです1が,仕事を見つけるためにはスキルが必要です.
ということでScalaのスキルを身につけるべく,Scalaを勉強中.
Scalaのインストール
ドワンゴはScalaで有名なのでその資料2を使ってScalaでHello 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!")
で完了です.
仕事を見つけるまで死にません...
-
本当は親からの仕送りがもらえず銀行口座に75円しかないので金がほしいというのもあります.↩
# 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_sum
はred + 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; } };