LeetCode: 1. Two Sum (Easy) by PHP
はじめに
LeetCodeの「1. Two Sum」の個人的な考察です。
解いてから模範解答を見て書いています。
言語はPHPです。
問題
解法
1. Blute Force (総当たり)
<?php class Solution { /** * @param Integer[] $nums * @param Integer $target * @return Integer[] */ function twoSum($nums, $target) { $count = count($nums); for ($i = 0; $i < $count; $i++) { for ($j = $i + 1; $j < $count; $j++) { if ($nums[$i] + $nums[$j] === $target) { return [$i, $j]; } } } return []; } }
普通に考えたらこうでした。
配列内の2つの要素を足し合わせたらtargetの数字になると。
ただしTime complexity (時間計算量)がO(n2)でよくありません。
見るからにループが入れ子になっていますしね…。
$j = $i + 1
しているのは、一度チェックした数字を見ないようにするための工夫ですが、焼け石に水です。
2. Two-pass Hash Table
[2, 5, 6, 7]
でtargetは9
みたいなケースだと、2
に対するペアである7
を探せば答えが出ます。
しかし配列の要素であるため、すぐに探せない。そこで…。
<?php class Solution { /** * @param Integer[] $nums * @param Integer $target * @return Integer[] */ function twoSum($nums, $target) { $inums = array_flip($nums); $count = count($nums); for ($i = 0; $i < $count; $i++) { $searchNum = $target - $nums[$i]; if (isset($inums[$searchNum]) && $inums[$searchNum] !== $i) { return [$i, $inums[$searchNum]]; } } return []; } }
PHPにはarray_flip
関数があるので、キーと値をひっくり返すことが簡単にできます。
上記の例でいうと、2
のペアである7
を探しに行くのですが、例えば[2, 3, 5, 3]
みたいなケースでは[1, 1]
が成り立ってしまうので、それは避けるべくif文に$inums[$searchNum] !== $i
を追加しています。
3. One-pass Hash Table
結果はかなり良くなりますが、とはいえまだarray_flip
で内部的にはループしていることになります。
なのでチェックするループ内に後置的に値をセットしていくのが今回のやり方です。
ただし後置的に反転した配列を作成していくので、returnするタイミングは一歩遅くなることになります。
しかし後置的にすることで[2, 3, 5, 3]
の場合に1
のときに自分を拾う必要がなくなります。
また1, 2番目と比べて結果の配列の1つ目と2つ目が逆になります。
PHPの配列は連想配列(ハッシュ、マップ)なので、[1, 3]
と[3, 1]
が一緒と言われてもピンと来ないかもしれませんが…。
その場合は、returnの配列の順番を書き換えても問題ないでしょう。
(下記は公式の解答に準拠してます)
<?php class Solution { /** * @param Integer[] $nums * @param Integer $target * @return Integer[] */ function twoSum($nums, $target) { $count = count($nums); for ($i = 0; $i < $count; $i++) { $searchNum = $target - $nums[$i]; if (isset($inums[$searchNum])) { return [$i, $inums[$searchNum]]; } $inums[$nums[$i]] = $i; } return []; } }
終わりに
自分なりの学習メモを残していこうと思って書いた記事です。
しばらく試行錯誤が続きそう…。
2つ目はまだしも、3つ目は思いつかなさそう。PHP的にはarray_flip
が先に頭に浮かびそうで、自前で作っていく発想にいたらなさそうだなと思った次第です。
2つ目も、forの入れ子を脱するやり方を思いつけるか…。
ブランチの派生元を変更したいとき
はじめに
ブランチの派生元を変更したいときにコマンドで対応するお話です。
現ブランチでの修正が少なければ、
git diff
でパッチファイルを作成してブランチ切り替え後にgit apply
git cherry-pick
で特定のコミットを移動する- 新しいブランチに手で修正を入れ直す
で切り抜けられるかと思いますが、ある程度ブランチが進んだときにはツライものです。
これをコマンド一発で解決する方法についての記事になります。
※パッチファイルについては、過去に記事にしました。
一次情報
正直ここに書いてある内容だけで足りる…。
モデルケース
main cA -- cB -- cC \ develop -- c1 -- c2 -- c3 \ target -- cX -- cY -- cZ
develop
ブランチから派生したtarget
で開発していたんですが、この度その開発内容をリリースすることになりました。
develop
ブランチには他の修正が入っており、「develop→main」のマージができません。
そこでtarget
ブランチの派生元をmain
にし、main
ブランチにマージすることにします。
main target cA -- cB -- cC -- cX' -- cY' -- cZ' \ develop -- c1 -- c2 -- c3
やり方
git rebase --onto main develop target git rebase --onto 変更先ブランチ 現在の派生元ブランチ 移動対象ブランチ(省略可)
省略した場合は今自分がいるブランチが対象になります。
rebaseコマンドを使っていることからわかるように、targetブランチで積み上げた修正コミットをmainブランチのお尻に持ってくるような動きになります。
注意点
target
ブランチの過去が大きく変わることになるので、このブランチをpushしていた場合には間違いなくコンフリクトすることになります…。
なのでブランチ名を変更して逃げるか、リモートブランチを消せるものなら消すか、個人ならpush -f
するか、選んで対応する必要があると思っております。
最後に
最初に書いた通り、rebase以外の手段も残されています。
状況に応じて楽な手段を選んでいただければと思います。
以上でした!
.gitignore以外でローカルファイルをGit管理外にする
はじめに
.gitignore
はチームで管理されている場合が多いと思います。
それとは別に個人で作成したファイルをGit管理から外したい場合があると思います。
その対処方法です。
ソース
やりかた
Git管理されているディレクトリに移動して、下記のファイルを開きます。
.git/info/exclude
最初はこうなっていますが、
# git ls-files --others --exclude-from=.git/info/exclude # Lines that start with '#' are comments. # For a project mostly in C, the following would be a good set of # exclude patterns (uncomment them if you want to use them): # *.[oa] # *~
こちらにファイルパスを追加するだけでOKです。
書き方は.gitignore
と変わらず書けると思います。
(ワイルドカードやコメントも一緒。)
# 例: path/to/file_name.sh nbproject/*
おわりに
私は自分用の便利シェルスクリプトをGit管理下に置くことが多く、ただ毎回git status
をすると出てきてしまうのは煩わしく…。
方法を探してみた結果、こんなやり方が出てきました、というお話でした。
以上でした!
Ergo M575のボタンにExcelのシート切り替えを割り当てる
はじめに
Logicoolのトラックボールマウス、「Ergo M575」の「進む」「戻る」ボタンにExcelのシート切り替えを割り当てます。
M570だと特に設定いらずでできた記憶があるのですが…
やってみたら設定抜きにはできなかったので、今回の記事となりました。
製品ページ
設定はLogicool Options+を使います。
やり方
Logicool Options+ の画面右上の「+」をクリックすると、アプリケーションの選択が可能です。
アプリケーション毎の設定ができるわけです。
ここでMicrosoft Excelを選択します。
(画面ではすでに選んでる状態なので、Excelが「+」ボタンの横に出ておりますけども)
そしてExcelアイコンをクリックして、選択状態にしておきます。
(青緑のラインが表示されます)
デフォルトでは「進む」になっておりますが、こちらを「キーボードショートカット」に合わせます。
画面の通り、「Ctrl + PageUp」にします。
通常のExcelでもこのショートカットで選択するシートを変更するやつですね。
「戻る」でも同様に設定したらおしまいです。
試しにExcelを起動して、マウスボタンをポチポチしてみてください。
終わりに
Google Spreadsheetだと、マウススクロールでシート表示のバーがスクロールできるんですがね…
逆輸入してほしいものです。
以上でした!
WSL2上でopenコマンドを実行できるようにする
はじめに
WSL2上で、いわゆるopen
コマンドを実行できるようにします。
ディレクトリを指定すればディレクトリをエクスプローラーで開く、ファイルを指定すればファイルを開く、そんな動きをします。
openコマンド実装まで
1. cmd.exe へのパスを通す
vi ~/.profile
# path to Windows export PATH=$PATH:/mnt/c/Windows/System32
デフォルトではcmd.exe
は実行できない(パスが通っていない)と思うの で、.profile
に書き込むことでパスを通します。
追記したら、再読み込みを忘れずに。
source ~/.profile
2. .bashrcにてopen関数を作成
自前の関数を定義します。ソースコードは下記の通り。
シェルの起動時に定義した関数を使えるように、.bashrc
に記載します。
コードの解説は後ほど。
vi ~/.bashrc
function open() { path_name=$1 if [ $# -eq 0 ]; then path_name="." elif [ $# -gt 1 ]; then echo "open: $* : Set only one directory or file path" 1>&2 return 1 fi if [ -e "${path_name}" ]; then cmd.exe /c start $(wslpath -w ${path_name}) 2> /dev/null else echo "open: ${path_name} : No such file or directoty" 1>&2 return 1 fi return 0 }
こちらも、再読み込みを忘れずに。
source ~/.bashrc
3. 使ってみる
# 現在のディレクトリをエクスプローラーで開く open . # 現在のディレクトリをエクスプローラーで開く # (引数なしでもいけるようにしています。エラーにしてもいいんですが) open # 指定のディレクトリをエクスプローラーで開く # (変換をかけるので、WSL2上のパスで構いません) open ~/work/ # 指定のファイルを規定のプログラムで開く # (.bashrcなどを指定すると、Windows側でどのプログラムで開くか聞かれるかも) open ~/work/memo.txt # Windows側のexeファイルを実行することも可能です # (下記の例はメモ帳を立ち上げています) open /mnt/c/Windows/System32/notepad.exe
コードの解説
bashのマニュアルも見るとよいと思います。
function open() { # 第一引数($1)を変数に格納しておきます path_name=$1 # $#: 引数の数を表します。 if [ $# -eq 0 ]; then # 引数の数が0なら、パスを現在のディレクトリに指定します。 # エラーにしてもよいと思ってますが今回は救済してみました。 path_name="." elif [ $# -gt 1 ]; then # 引数の数 > 1 の場合にはエラーにすることにしました。 # $*: 引数すべてを列挙します。 echo "open: $* : Set only one directory or file path" 1>&2 # 終了ステータスを返す(0以外は失敗なので今回は1を返す) return 1 fi # パスの存在チェックを行っています if [ -e "${path_name}" ]; then # コマンドプロンプトでファイルを開きます。 cmd.exe /c start $(wslpath -w ${path_name}) 2> /dev/null else # 有効なパスでなければ、エラーを吐きます。 # 標準エラー出力に出るように調整しています。 echo "open: ${path_name} : No such file or directoty" 1>&2 # 終了ステータスを返す(0以外は失敗なので今回は1を返す) return 1 fi # 終了ステータスを返す(0が成功) return 0 }
詳細: コマンドプロンプトの操作について
cmd.exe /c start $(wslpath -w ${path_name}) 2> /dev/null
について、詳しく説明します。
wslpath について
恐らく最初から用意されているコマンドです。使い方はこんな感じです(Usageを表示してみました)。
$ wslpath wslpath: Invalid argument Usage: -a force result to absolute path format -u translate from a Windows path to a WSL path (default) -w translate from a WSL path to a Windows path -m translate from a WSL path to a Windows path, with '/' instead of '\' EX: wslpath 'c:\users'
wslpath -w ${path_name}
を実行することで、Linux的なパスをWindowsのパスに変換して、cmd.exe
に渡してあげています。
cmd.exe 部分について
あまり見慣れないかもしれませんが、コマンドプロンプトで実行できるコマンドをexeファイルを通して実行していることになります。
start
についてはこちらをご参照ください。
start は、指定された実行可能ファイルを検索し、見つかった場合は、現在の作業ディレクトリに関係なく実行可能ファイルを起動します。 実行可能ファイルを検索して、どの拡張子にも一致するものがないと、start は名前がディレクトリ名と一致するかどうかを調べます。 そのような場合は、 開始 そのパスに Explorer.exe を開きます。
上記引用部分が今回の使い方になります。
終わりに
WSL2とのやり取りをしたい場合はそこそこ発生するので、一度open
を実装してしまえば便利なツールとして使えると思います。
またご自分で使いやすいようにいじってもらえるとよいと思います。
以上でした!