皆さんご存知のバイナリサーチ。基本的には「探す対象の要素数を半分に分割しながら目的の値を探す」といった単純なものですが、パターンを分類しながらこれを深堀りしていく。

大きく分類して 3 つのパターンに分けられる。

  • パターン 1 : 各ステップで 1 つの要素を見て条件分岐する
  • パターン 2 : 各ステップで要素数が 2 つ以上あることを保証する
  • パターン 3 : 各ステップで要素数が 3 つ以上あることを保証する

パターン 1

最も単純で、最もベーシックなもの。
(配列がソートされている前提で) 要素数を半分に割ったときの値がターゲットより大きければ、前半の半分に絞って再度分割していく。
半分に割ったときの値がターゲットより小さければ、後半の半分に絞って再度分割していく。

  • 検索条件となるものは、mid で指定され …

お題

LeetCode の問題 210. Course Schedule II をお題にする。
input は numCourses int および prerequisites [][]int の 2 つ。

授業の履修計画のイメージ。numCourses の数だけコースがあり、prerequisites にて、あるコースを取るために事前に取らなくてはいけないコースの情報が与えられる。

output はコースを取る順番に並べた int 配列。(複数あれば任意のもの 1 つを返せばよい)

トポロジカルソート

これは、トポロジカルソートをそのまま題材にした問題なので、トポロジカルソートを実装すればよい。

とあるノード(またはジョブ)に到達するために事前に到達すべきノードがあり、それらを満たすような順序を考えるものである。
まあ、上の問 …


slack bot 作成にあたり、いい感じの記事がなかったので自分で書くことにした。
やりたいこと、API の話、簡単な導入をまとめる。

やりたいこと

slack チャンネルに bot を入れておき、特定の文字列を検知したら反応する、という bot を作りたかった。
このとき、bot をメンションしたり、スラッシュでコマンドを認識することなく、正規表現かなんかでマッチしたものを勝手に拾って処理したいという目的があった。
そもそもできるのか?という部分もあったが、結論から述べると実現可能な話だった。

API について

一番単純な Incoming Webhook では、Webhook URL というエンドポイントに json 形式のデータを投げれば bot から何かを投稿することができる。
ただ、今回はチャンネル内の発言を何らかの …


例題

1192. Critical Connections in a Network
https://leetcode.com/problems/critical-connections-in-a-network/

0 から n-1 まで番号の振られた n 台のサーバがある。この台数は n として与えられる。
また、それぞれの接続は 2 次元配列 connections で与えられる。
このときの critical connections (切断するといずれかのノードへの path が無くなるもの) を return する問題。

※ この問題では Bridge を critical connections と表現している

Basic concept

Bridges

以下のようなグラフがあったときに、赤く ❌ を付けたところが Bridge となる …


はじめに

iPad で開発ができないかと模索していたところ、とてもいい記事 を見つけたので実際に試してみた記録。
code-server と呼ばれるソフトウェアにより、ブラウザアクセスにより操作可能な VS Code をリモートサーバ上で動かせる。
セキュアな通信だったり認証周りだったりを考えるのが面倒だったので、AWS Client VPN を使ってそのへんをサクッと解消することにした。
(言うまでもなく、以下の話は AWS を前提としている)

※ここでは VPC を 172.31.0.0/16 としているが、接続元が特定のネットワークでない場合は 100.64.0.0/10 を利用すべきという指摘をいただきました。 link: RFC 6598

必要な作業は主に以下の 3 つであり、これに沿って作業 …

Kohei Yoshida

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store