別府旅行

新卒同期兼、中高ずっと一緒だった友だちと別府にいってきた。ゆっくりするつもりだったけど、いろいろなところを回った。

最終日は天草に行くか行かないかでもめて喧嘩した。ゆっくり旅行は恋人と(できるのかお前に)行けば良いからエクストリームで良かったなと今となっては思う。(すまん)

Leetcode 124. Binary Tree Maximum Path Sum

問題

 

 

f:id:yuyaito:20190815090734p:image

 

huahuaさんの動画解説が見やすくて例を考えやすい。余談だけど、こういう例をきちんとかけると色々と考えやすくなるから必ず書いた方がいいね。

考えるケースは二つ。

 

1. ノードからまだ上に続く場合

2. ノードが根となる場合

 

1の場合は、左の子or右の子+対象ノード。2の場合は対象ノード+左の子+右の子。

 

考え方としてはこれだけなんだけど、実装が難しい。DFSでグローバルに最大値を更新していく。

 

 

Leetcode 98. Validate Binary Search Tree

問題

木系の問題の中で一番苦手。。。なTraverse問題。 leetcode.com

解法

大まかな方針はこの記事と一緒。

yuyaito.hatenablog.com

左を限界まで詰めて、戻る過程で右にいけたら1マスだけいくというステップで構築されるstackにおいて、stackに格納されている要素は単調減少するという性質を利用する。

[9,6,4,3,2,1] → BST [9,5,7,3,2,1] → Not BST

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        stack, tmp = [], -float('inf')
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            node = stack.pop()
            if node.val <= tmp:
                return False
            print(node.val,tmp)
            tmp = node.val
            
            root = node.right
        return True

左の子から親、親から右の子という二操作がともに単調増加であるということを見抜けるかが鍵の問題。discussionを覗いてみても、やはりこの方法が一番理解しやすいのだろうと思われる。再帰的に解く方法は、正直自分では思いつけないと思う。

地味に、値を外で保存しておくというのも難しかった。

Leetcode 230. Kth Smallest Element in a BST

問題

BSTの探索問題

leetcode.com

解法

左を掘っていって、終着点から右に行けたら一つ右に行き、また左を掘り進める作戦。AC.

木の高さをNとして、時間も空間も計算量はO(N)

def kthSmallest(self, root: TreeNode, k: int) -> int:
        parents, cnt = [], 0
        self.dig_left(root, parents)
        while parents:
            node = parents.pop()
            cnt += 1
            if cnt == k:
                return node.val
            self.dig_left(node.right, parents)
        return
        
def dig_left(self, root, l):
        if root == None:
            return
        l.append(root)
        self.dig_left(root.left, l)

左に進めるのはいわゆる再帰的で、スタックを使ってやってるのはIterativeなやり方。

dig_leftはwhile rootと書くことでiterativeにかける。

def kthSmallest(root, k):
    stack = []
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        k -= 1
        if k == 0:
            return root.val
        root = root.right

再帰的にだけやろうとすると、コールスタックをうまく使わなければならず自分には難しすぎた。。。(下のコードでいくとself.helper(node.left)が積まれていく。)

def kthSmallest(self, root, k):
    self.k = k
    self.res = None
    self.helper(root)
    return self.res

def helper(self, node):
    if not node:
        return
    self.helper(node.left)
    self.k -= 1
    if self.k == 0:
        self.res = node.val
        return
    self.helper(node.right)

Leetcode 235. Lowest Common Ancestor of a Binary Search Tree

免許更新の講習中に考えていた問題。

問題

leetcode.com

BSTのLCA(Lowest Common Ancestor)を求めよという問題。

解法

はじめはノードからノードをたどること(よくあるTraverseの問題か?)と思っていたが、どうにも違う。とくに根まで探索しなければならなそうだったので却下。

根からノードまでのパスを2つ用意して、その2つのパスで値が違ったら、値が違う前で最新のものをリターンする。AC.

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        p_l, q_l = [], []
        self.getPath(root,p.val,p_l)
        self.getPath(root,q.val,q_l)
        for i in range(min(len(p_l), len(q_l))):
            if p_l[i].val!=q_l[i].val:
                return p_l[i-1]
        return q_l[-1] if len(p_l)>len(q_l) else p_l[-1]
        
def getPath(self,root,v, l):
        l.append(root)
        print(len(l), root.val, v)
        if root.val == v:
            return
        if root.val > v:
            self.getPath(root.left, v, l)
        else:
            self.getPath(root.right, v,l)

時間計算量は根の深さをNとしてO(N), 空間計算量はパスを2つ保存するので同様にO(N).

模範解答は頭いいなあと思った。BSTにおけるLCAは必ず

p.val < root.val < q.val
q.val < root.val < p.val

を満たす根からたどった最初のノード。

再帰的 (コールスタックにサブルーチンを格納するので、O(N)の空間計算量がかかる)

def lowestCommonAncestor(self, root, p, q):
    if p.val < root.val > q.val:
        return self.lowestCommonAncestor(root.left, p, q)
    if p.val > root.val < q.val:
        return self.lowestCommonAncestor(root.right, p, q)
    return root

繰り返し(O(1)の空間計算量)

def lowestCommonAncestor(self, root, p, q):
    while root:
        if p.val < root.val > q.val:
            root = root.left
        elif p.val > root.val < q.val:
            root = root.right
        else:
            return root

評価されたい自分と、よく分からない自分

23にもなって何言ってんのって感じだけど、さいきん何がしたいのかよくわからなくなってきちゃった。

 

オーバーウォッチは楽しいし、プログラミングも楽しいんだけど、それ以上ではない。満足できていない。

 

もちろんその環境にいるときは本当に楽しいし、全力でやっているんだけど。

 

いま家にいる自分はほんとに虚無。

 

お金持ちになることも、憧れのGoogleに入ることも、なにを目標にしていた?

 

目指してる自分に満足しているだけ?

 

どこに向かってるんだろう。

 

口だけ。

 

お前はこんなもんかよ、命燃やしてるか。

 

神経質にならず、ゴーゴー人生!!!

LRU Cache @Python

問題

leetcode.com

解法

率直にキューと辞書使うんだなと思い浮かぶ。ただこれリアル世界で使う場合、辞書を消してくのってどうなの?って感じする。Pythonの場合、OrderedDictがあるのでそれを使うと実装が楽。(内部的にはLinkedHashMap)

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.dic = collections.OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.dic:
            return -1
        v= self.dic.pop(key)
        self.dic[key] = v
        return v
            

    def put(self, key: int, value: int) -> None:
        if key in self.dic:
            self.dic.pop(key)
        elif self.capacity > 0:
            self.capacity -= 1
        else:
            self.dic.popitem(last=False)
        self.dic[key] = value

順序付き辞書の popitem() メソッドは、(key, value) 対を返して消去します。この対は last が真なら LIFO で、偽なら FIFO で返されます。