LeetCode: Valid Parentheses
問題
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
解答
問題文を読んでExampleを見た瞬間にStackだなと思ったので、それで実装しました。 スタック - Wikipedia
import java.util.LinkedList; class Solution { public boolean isValid(String s) { LinkedList<Character> parenthesesStack = new LinkedList<>(); for (char ch : s.toCharArray()) { if (ch == '(' || ch == '{' || ch == '[') { parenthesesStack.push(ch); } else if (!parenthesesStack.isEmpty()) { char openParentheses = parenthesesStack.pop(); if (!(openParentheses == '(' && ch == ')') && !(openParentheses == '{' && ch == '}') && !(openParentheses == '[' && ch == ']')) { return false; } } else { return false; } } return parenthesesStack.isEmpty(); } }
時間計算量:O(n)、メモリ計算量:O(n)
他の人の解答はこんな感じです。
class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); for(char c : s.toCharArray()){ if(c=='(' || c=='[' || c=='{') stack.push(c); else if(!stack.isEmpty() && isMatch(stack.peek(),c)) { stack.pop(); } else{ return false; } } return stack.isEmpty()? true : false; } public boolean isMatch(char a, char b ){ return (a=='('&& b==')'|| a=='{' && b =='}' || a=='[' && b==']') ? true : false; } }
時間計算量:O(n)、メモリ計算量:O(n)
やっていることは全く同じなのですが、三項演算子を使って foo ? true : false
はちょっと拒絶反応が出ますね。。。
LeetCode: Longest Common Prefix
問題
Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "".
解答
大して上手いやり方が思い当たらず、力任せに解くことにしました。
class Solution { public String longestCommonPrefix(String[] strs) { if (strs.length == 0) return ""; StringBuilder sb = new StringBuilder(""); char currentChar = 0; for (int i = 0; ; i++) { for (int j = 0; j < strs.length; j++) { String str = strs[j]; if (str.length() <= i) { return sb.toString(); } char ch = str.charAt(i); if (j == 0) { currentChar = ch; } if (ch != currentChar) { return sb.toString(); } } sb.append(currentChar); } } }
入力される配列のサイズをm、文字列の平均長をnとすると、
時間計算量:O(m x n)、メモリ計算量:O(n)
グラフを見た感じも他の人も同じような戦略のようですね。
他の人の解答も見てみましょう。
class Solution { public String longestCommonPrefix(String[] strs) { if(strs.length == 0 || strs == null) { return ""; } String longCommonPre = strs[0]; for(int i = 1;i<strs.length;i++) { int k = 0; String currentItem = strs[i]; while(k < longCommonPre.length() && k < currentItem.length() && longCommonPre.charAt(k) == currentItem.charAt(k)) { k++; } if( k == 0) { return ""; } longCommonPre = longCommonPre.substring(0,k); } return longCommonPre; } }
時間計算量:O(m x n)、メモリ計算量:O(n)
やっていることは同じですが、僕のコードの方がわかりやすくないですか?
HerokuにTypeScriptのアプリをデプロイしたら見事にハマった話
Heroku Advent Calendar 2018 5日目の記事です。
今日は題名の通り、HerokuにTypeScriptのアプリをデプロイしたら見事にハマった話をします。
ただ外部サービスやアドオン、DBなどの話は 出てきません 。
普通に設定をミスして*.ts
がコンパイルされなかった話をします。
ハマったポイントは次の2つです。
- Release Phaseでコンパイルしていた
- Procfileの実行コマンドで
yarn install
していた
Release Phaseでコンパイルしていた
みなさん、Release Phase使ってますか? 僕は名前的にReleaseに伴う作業を記述した通りにやってくれるものだと信じていました。
でも実はRelease Phaseはone-off dyno上で動きます。 なのでRelease Phaseでコンパイルしたところでweb dynoにはJSファイルは1つもありません。(=> したがってweb dynoには実行ファイルが1つもない。) ということで、web dyno上でコンパイルするためにRelease PhaseではなくProcfileを使うことにしました。(そこでもまたどハマりしたのですが。。。) (web dynoとかone-off dynoについてはこの記事を参照してください。)
Procfileの実行コマンドで yarn install
していた
Procfileは各dynoにやって欲しい作業を記述するファイルです。
よくわからないけど、 web: bundle exec rails server -p $PORT
って書いておくファイルです。
今回はProcfile内に web : yarn install --production=false && tsc && foobar...
と記述しました。
(わざわざ yarn install --production=false
としたのは、tsc
や型定義ファイルを devDependencies
に入れておきたかったからです。
だって本番環境の動作には不要な感じがしませんか?)
Herokuはデプロイ後、60秒でwebプロセスが$PORTにバインディングされないとエラーでコケます。
今回はyarn install
し直しているので、当然のように60秒で作業が完了するわけもなくエラーでコケました。
したがって、大人しくtsc
や型定義ファイルをdependencies
に入れて、HerokuのBuild時にコンパイルに必要なファイルが全てインストールされるようにしました。
これでようやく無事にHerokuにデプロイされるようになりました〜!(ここまで約1時間)
結論
HerokuにTypeScriptのプロジェクトをデプロイするときは必要な型定義ファイルやtsc
はdependencies
に入れましょう。
LeetCode: Reverse Integer
問題
Given a 32-bit signed integer, reverse digits of an integer.
解答
どうしようか迷ったのですが、入力値をStringにして反転して出力するのが一番楽そうだなと思ってそれで実装することにしました。
反転した値がオーバーフローする場合は0を返す仕様だったので、 x == Integer.MIN_VALUE
の確認を入れたり、
Integer.parseInt
でNumberFormatException
が発生した時は0を返すようにしました。(後者だけで良かったかも?)
class Solution { public int reverse(int x) { try { if (x == Integer.MIN_VALUE) { return 0; } StringBuffer sb = new StringBuffer(String.valueOf(Math.abs(x))); int ans = Integer.parseInt(sb.reverse().toString()); if (x < 0) { return -ans; } else { return ans; } } catch (NumberFormatException e) { return 0; } } }
時間計算量:O(log n)、メモリ計算量:O(1)
(時間計算量について:SutringBufferのreverse()が文字列の長さnに対してO(n)なので、今回の問題の入力値nに対してはO(log10 n)のはず。)
他の人の解答も見てみましょう。 多くの人の解答はこんな感じのようです。
class Solution { public static int reverse(int x) { int counter = digitsCount(x); int sign = x >= 0 ? 1 : -1; long value = 0; x = Math.abs(x); while (x > 0 && value <= Integer.MAX_VALUE) { value += x % 10 * Math.pow(10, counter - 1); counter--; x /= 10; } if (value <= Integer.MAX_VALUE) { return (int) (value * sign); } else { return 0; } } private static int digitsCount(int x) { x = Math.abs(x); int counter = 0; while (x > 0) { x /= 10; counter++; } return counter; } }
時間計算量:O(log n) 、メモリ計算量:O(1)
普通に1桁ずつ逆にしているという感じですね。
LeetCode: Add Two Numbers
問題
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself.
解答
人に見せるつもりのなかったクソコードで恥ずかしいのですが、、、 1番小さい桁から計算して順次ListNodeにしていくという方針です。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode ans = null; ListNode current = null; boolean moveUp = false; while (true) { int val = 0; if (l1 != null) { val += l1.val; } if (l2 != null) { val += l2.val; } if (moveUp) { val += 1; moveUp = false; } if (val >= 10) { val -= 10; moveUp = true; } ListNode tmp = new ListNode(val); if (ans == null) { ans = tmp; current = tmp; } else { current.next = tmp; current = tmp; } if (l1 != null && l1.next != null) { l1 = l1.next; } else { l1 = null; } if (l2 != null && l2.next != null) { l2 = l2.next; } else { l2 = null; } if (l1 == null && l2 == null && !moveUp) { return ans; } } } }
しかし、それでもやはり遅かった。。。
他の人の解答はというと、
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode first = null; ListNode last = null; int carry = 0; while (l1 != null || l2 != null || carry != 0) { int sum = 0; if (l1 != null) { sum += l1.val; l1 = l1.next; } if (l2 != null) { sum += l2.val; l2 = l2.next; } sum += carry; ListNode newNode = new ListNode(sum % 10); if (last != null) { last.next = newNode; last = newNode; } last = newNode; if (first == null) { first = newNode; } carry = sum / 10; } return first; } }
やっていることはほとんど同じだけど、if文がスッキリしていますね。 実行時間がそれぞれ35msと27msというように差が出たのですが、これはif比較の差なのかな? これからも精進いたします。
LeetCode: Two Sum
はじめに
LeetCodeを始めてみた。 その1問目がこれ。
問題
Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.
僕の解答
class Solution { public int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] == target) { return new int[] { i, j }; } } } return new int[] { 0, 0 }; } }
とりあえず何も考えずに解いてみるかという感じで何も考えずにO(n2)で回しました。
でもこの解答、周りの人のに比べるとすごい遅いんですよね(O(n2)だから当たり前か。)。
それで他の人(の多くは)どう解答しているのか見てみることにします。 (LeetCodeは他の人の解答が見られるのがいいですね。)
class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> ht = new HashMap<Integer, Integer>(); int[] twoSum = new int[2]; if (nums == null || nums.length < 2) return twoSum; for (int i=0; i<nums.length; i++) { if (ht.containsKey(nums[i])) { twoSum[0] = ht.get(nums[i]); twoSum[1] = i; return twoSum; } else { ht.put(target-nums[i], i); } } return twoSum; } }
なるほど、Mapを使ってO(n)にしてるんですね。これは結構簡単だけど使えそうなテクニックですね。
おわりに
LeetCodeがんばります。