【LeetCode】141. Linked List Cycle（Easy）
【最初に】
LeetCode 5個目に挑戦です
【問題】
与えられたLinkedListが循環しているかどうか判定せよ
Example 1:
Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.
【1.とりあえず】
ぱっと思いついたのは、LinkedListをループさせて可変長配列に詰めていく。過去のノードと同じノードが出てきたら循環参照していると判定する。
できた！
【2.違うパターン】
問題文の最後に
Can you solve it using O(1) (i.e. constant) memory?
とあるので、空間計算量がO(1)になるように考えてみる（今はLinkedListを全件ループして配列に格納しているのでO(n)になっている）
時間計算量はO(n)→O(n^2) になっちゃうけど、とにかく保存せずにループ回しまくってみる。
ひどいコードだけど一応できた！
【3.解答を見てみる】
2つの異なるスピードのポインターを持てばいいのでは？とあるが、個人的にはなかなか馴染みのない考え方。要は足の速い選手と遅い選手がいて、遅い選手が1進むたびに速い選手が2進むとすると、循環参照していた場合、足の速い選手が1ずつ周回遅れの遅い選手との距離を縮めて行っていつか追いつくというもの。やってみた。
できた！
これだと2のパターンよりループ回数も少なくて済むし、1のパターンよりメモリ使用量も少なくても済む。
【最後に】
最初に考えた人、頭いいなあ
【LeetCode】13. Roman to Integer（Easy）
【最初に】
LeetCode 4個目に挑戦です
【問題】
https://leetcode.com/problems/roman-to-integer/
ローマ数字を整数に変換せよ
Example 1:
Input: "III" Output: 3
Example 2:
Input: "IV" Output: 4
Example 3:
Input: "IX" Output: 9
Example 4:
Input: "LVIII" Output: 58 Explanation: L = 50, V= 5, III = 3.
Example 5:
Input: "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
【とりあえず】
文字から数字に置き換えて足していく。前の文字より数字が小さければ前の文字から引いた数字を足していく。
できた！
【解答をチラ見..】
しようと思ったら、この問題には解答がない！そんな問題あるんですね。簡単だからいらないでしょ？ってこと？？
【LeetCode】9. Palindrome Number (Easy)
【最初に】
LeetCode 3個目に挑戦です
【問題】
https://leetcode.com/problems/palindrome-number/
回文の整数（前から読んでも後ろから読んでも同じ数値になっている）かどうかを判定せよ。
Example 1:
Input: 121 Output: true
Example 2:
Input: -121 Output: false Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
Example 3:
Input: 10 Output: false Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
【とりあえず】
数値を文字列にして前からと後ろからで比較してみる
できた！
【違うパターン】
Coud you solve it without converting the integer to a string?
問題の最後に、integerをstringに変換せずに解いてみない？とある。
うーん、これって前回やった数値を逆にするのを使えばいけるんじゃない？
ということで、やってみた。
マイナスの場合は判定するまでもなくfalse、オーバーフローの場合もfalseにしつつ、数値を逆に並び替える。最後に入力された数字と並び替えた数字を比較して同じかどうかを返す。
できた！
【解答をチラ見する】
解答は数値を半分だけ逆順にすれば、回文であれば残りの数字と同じになるよねという考え方のよう。例えば、1221であれば1桁目と2桁目の21を逆順にした12は、残りの3桁目と４桁目と同じになる。
最後の判定で10で割った値と比較しているのは、数字が奇数だった場合、例えば入力値が12321の場合、x=12、result=123になるのでこのままだとfalseになってしまうから。真ん中の値は何でもいいので、resultを10で割って12に無理やりしている。
また、最初に10で割り切れる数を除外しているのは、例えば入力値が10の場合、最終的にx <= resultにならないとwhileループを抜けないので、ループを抜ける頃には x=0、result=1 になっている。このままだと回文でないにも関わらず、奇数計算用の x == result / 10 で true になってしまうので事前に除外する必要がある。
全部並べ換えるよりループは半分で済むけど、なんかわかりにくいように思うのは私だけ...？
【最後に】
以前やった問題とほぼ同じ問題かと思ったけど、そんなの出ないよね。
【LeetCode】7. Reverse Integer (Easy)
【最初に】
LeetCode 2個目に挑戦です
【問題】
https://leetcode.com/problems/reverse-integer/
32bit signed integer（−231 〜 231 − 1） の桁を逆順にせよ。 逆順の数値がオーバーフローした場合は0を返すものとする
Example 1:
Input: 123 Output: 321
Example 2:
Input: -123 Output: -321
Example 3:
Input: 120 Output: 21
【とりあえず】
パッと思いつくのは、文字列にして1つずつ逆順にして最後に数値に変換。頑張って書いてみたけど、これだと-123の時に-321ではなく321になっちゃうんですよね
もうめちゃくちゃだけど、マイナスかどうか最初に判定してやれば一応単純ケースでは動く。
あぁ、ひどいコード。オーバーフローにも対応できていないし、入力が0の場合にも答えが違う。
【解答を見る】
ここで文字列に置き換えずに数値として扱わないとオーバーフロー判定が面倒で、全然筋が違いそうな気がしてくる。ヒントを見ようと思ったけど、みんなスラスラ解けるからなのかこの問題にヒントはない。仕方ないので解答をチラ見する。そうか、10で割っていって余りをとれば1桁ずつ取れるじゃないの
めっちゃ簡単でした。10で割り続けるとintだといつか0になるのでwhile文を抜ける。
オーバーフローチェックを入れるとこんな感じかな。やっとできた。
時間計算量は O(log(x))だそう。計算量の求め方はこちらがわかりやすかったです
Oの中身はこういうルールで表記するらしい。
- 最高次数の項以外は落とす:
- 係数を無視する3n^2 -> n^2
例えば、上記のコードのループ回数は、
n=1のとき1回
n=10のとき2回
n=100のとき3回
つまり
n=10^kのときk+1回、つまり 回となり、
底数と減算は無視できるので、計算量はO(log(x))となるんじゃないかと思う。
【最後に】
新卒の頃とかにもっと基礎を勉強しとけば良かったなあ
【LeetCode】1. Two Sum (Easy)
【最初に】
LeetCodeのアルゴリズムの最初の問題を解いてみます
https://leetcode.com/problems/two-sum/
【問題】
与えられたint配列に対して足すと指定の数値になる配列内の2つの数値のインデックスを返せ。入力には必ず解が1だけある前提。配列の同じ要素は使わないこと。
Example:
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
【とりあえず】
単純に思いつくのは、とりあえずfor文をぶん回して足していって答えに辿り着いたら終了するパターン。
でもこれはたぶんダメダメなやつ
解答を見ると、上の例だと最後の1個まで解が見つからない場合、ループをn回実行して、各要素ごとにn回ずつ回すので、時間計算量はO(n^2)になるとのこと。
【違うパターン】
ヒントを見るとhashmapを使ったらとあるので、違うパターンを試してみる
最初に数字をkeyに、配列のインデックスをvalueにした連想配列を作る。次にもう一度配列を回して、補数がマップにあるかどうか検索。存在する場合は結果を返して終了する。
速くなった！（メモリは増えたけど）
時間計算量はO(n^2)からO(n)に減少（O(2n)と書かない理由はこちらを参照：https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0）ただし、空間計算量は配列の分だけmapとしてメモリに格納するのでO(1)からO(n)に増える
【さらに違うパターン】
↑だと配列のループを2回回しているけど、解答見るとループを1回で済ませる方法もある
ループを回していって、マップに補数がなければ格納。順にループを回していって過去に追加したマップの値と比較して発見すればインデックスを返して終了する。
【最後に】
気分転換に最初の1個目をやってみましたが面白いですね。アルゴリズムはこれまであまりきちんと勉強して来なかった（正確には大学でやってるはずだけど真面目に授業受けてなかった）ので、もうちょっと続けてみようかと思います。ちなみにC++も大学でやってるはずだけど...（以下同文）C++の作法とかよくわかってないので、その辺りはご容赦を。
【Unity】LWRPプロジェクトの作成とサンプルシーン
Unity2018.1 から LWRP (Lightweight Render Pipeline: 軽量レンダーパイプライン) が導入されました。LWRPはSRP（Scriptable Render Pipeline）の1つで、HDRP (High Definition Render Pipeline: 高画質レンダーパイプライン）に比べ軽量でモバイル向きだそうです。
SRPとはUnity がフレームをどのように描画するかをデベロッパーが C# で制御できるようにするものです。
まずは新規にLWRP用のプロジェクトを作成します。 なお、既存のプロジェクトをLWRPに適用させるのはテラシュールさんの記事がわかりやすかったです。
実行環境
Unity: 2018.3.4f1
LWRP: 4.1.0-preview
LWRPプロジェクトの作成
プロジェクトの新規作成で、Template に Lightweight RP (Preview) が増えているので選択します。ちなみに、LWRPはまだPreview版のようで、2019.1から本格的に使えるようになるようです。
プロジェクトを作成するとこんなサンプルシーンが開きます。
サンプルプロジェクトにはLWRP設定が3種類用意されています。Edit > Project Settings > Graphics の一番上の設定を切り替えれば変更できます。
| LWRP-LowQuality | LWRP-MediumQuality | LWRP-HighQuality |
|
|
|
 |
設定の違いは以下のようになっています。
| LWRP-LowQuality | LWRP-MediumQuality | LWRP-HighQuality | |
| HDR | OFF | ON | ON |
| MSAA(Anti Aliasing) | Disabled | 2x | 4x |
|
Main Light - Shadow Resolution |
512 | 1024 | 1024 |
|
Additional Lights |
Disabled |
Per Pixel |
Per Pixel |
|
Additional Lights - Cast Shadows |
- |
OFF |
ON (1024) |
|
Shadows - Cascades |
No Cascades | Two Cascades | Four Cascades |
|
Shadows - Soft Shadows |
OFF | ON | ON |
左の絵はHDRがオフなのでスポットライトとブルームが反映されていないのと、真ん中の絵はAdditional LightsのCast Shadowsがオフなので右側にスポットライトの影が出てないのが大きな違いでしょうか。
なお、LWRPと通常のUnityビルドインパイプラインの違いは下記に記載があります。
注意点は、CEDEC2018の発表資料にある通り、
① CameraのCallbackが呼ばれない
Camera.OnRenderImageなどのCamera系のコールバックが呼ばれなくなります。
② Surface Shaderが使えない
vertex shader / fragment shader もしくは、2018.1からの新機能ShaderGraphでのShader記述に置き換える必要があります。
それ以外にも、
③ 現状のLWRPでは複数のカメラに対応していない。Unity2019.1で対応するかもしれないとのこと。
https://forum.unity.com/threads/glitching-with-multiple-cameras-lwrp.592477/
- Remove multi-camera support. LWRP and HDRP will not support multi-camera layered rendering.
つまり、UI用にMainCameraとは別のカメラを追加する、みたいなことは現状ではうまく動作しないと思われます。
④ LWRPは、通常のビルドインのUnityレンダリングやHDRPとは互換性がない。既存のプロジェクトにLWRPを適用するための一括変換コマンドもあるが、すべて正確に変換できるとは限らずアセットによっては手動で修正しなければいけないかもしれません。
Editor > Render Piepeline > Update Project Materials To Lightweight Materials
などがありそうです。そもそもLWRPはまだPreview版で仕様が変更される可能もあります。本格的な使用はUnity2019での正式版まで待った方がいいかもしれません。
【Unity】async/awaitのフレーム消費
C# 6.0から async/await が使えるようになり、コルーチンでは解決できなかった「何もしてないのにフレーム消費されてしまう」問題が解決できそうです。
まずは今までのコルーチン処理です。IEnumeratorを返すメソッドでは下記のように非同期処理を上から順に実行される形で書くことができました。下記の処理では、coroutine1が終わるのを待ってからcoroutine2が実行されます。コールバック処理を書くよりも見通しの良いコードを書くことができました。
yield return coroutine1;
yield return coroutine2;
もちろん、下記のようにMoveNextを使って書くこともできますが、 上記のほうが1行で書けるためスッキリ書けました。
while (coroutine1.MoveNext())
{
yield return null;
}
while (coroutine2.MoveNext())
{
yield return null;
}
ただし、yield return coroutine; の書き方は問題もありました。メソッド内部で仮に何も処理していなくても、必ず1フレーム消費されてしまうことです。
public class AsyncFrameTest1 : MonoBehaviour
{
private int mFrameNum;
private bool mIsPlaying;
private IEnumerator Start()
{
// 念のため1フレーム待って計測
yield return null;
mIsPlaying = true;
mFrameNum = 0;
var previousFrame = mFrameNum;
yield return TestCoroutine1();
Debug.LogFormat("TestCoroutine1: (+{0}フレーム)", mFrameNum - previousFrame);
previousFrame = mFrameNum;
yield return TestCoroutine2();
Debug.LogFormat("TestCoroutine2: (+{0}フレーム)", mFrameNum - previousFrame);
}
public IEnumerator TestCoroutine1()
{
yield break;
}
public IEnumerator TestCoroutine2()
{
yield return null;
}
private void Update()
{
if (mIsPlaying)
{
mFrameNum++;
}
}
}
実行結果はご覧の通りです。TestCoroutine1は内部でyield breakしているだけですが、yield return nullしているTestCoroutine2と同様に処理が終わるまで1フレームかかっています。これが結構厄介で、例えばコルーチンメソッド内でキャッシュがある場合はロードせずにyield breakするような処理を書いても最低1フレームはかかってしまうということになります。
もちろんMoveNextで書いておけば余計なフレームは消費せずに済みます。
previousFrame = mFrameNum;
var testCoroutine1 = TestCoroutine1();
while (testCoroutine1.MoveNext())
{
yield return null;
}
Debug.LogFormat("MoveNext(TestCoroutine1): (+{0}フレーム)", mFrameNum - previousFrame);
var testCoroutine2 = TestCoroutine2();
while (testCoroutine2.MoveNext())
{
yield return null;
}
Debug.LogFormat("MoveNext(TestCoroutine2): (+{0}フレーム)", mFrameNum - previousFrame);
1行でスッキリ書けて、かつ余計なフレームを消費しない書き方があればいいのになあとずっと思っていましたが、async/awaitで実現できるようです。
public class AsyncFrameTest2 : MonoBehaviour
{
private int mFrameNum;
private bool mIsPlaying;
private async void Start()
{
mIsPlaying = true;
mFrameNum = 0;
var previousFrame = mFrameNum;
await TestAsync1();
Debug.LogFormat("TestAsync1: (+{0}フレーム)", mFrameNum - previousFrame);
previousFrame = mFrameNum;
await TestAsync2();
Debug.LogFormat("TestAsync2: (+{0}フレーム)", mFrameNum - previousFrame);
mIsPlaying = false;
}
public async UniTask TestAsync1()
{
// 何もしない
}
public async UniTask TestAsync2()
{
await UniTask.DelayFrame(1); // 1フレーム待つ
}
private void Update()
{
if (mIsPlaying)
{
mFrameNum++;
}
}
}
実行結果です
便利ですね！
