LeetCode: Valid Parentheses

問題

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. 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)

グラフを見た感じも他の人も同じような戦略のようですね。 f:id:tsukakei1012:20181128114407p:plain

他の人の解答も見てみましょう。

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つです。

  1. Release Phaseでコンパイルしていた
  2. 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のプロジェクトをデプロイするときは必要な型定義ファイルやtscdependencies に入れましょう。

LeetCode: Reverse Integer

問題

Given a 32-bit signed integer, reverse digits of an integer.

解答

どうしようか迷ったのですが、入力値をStringにして反転して出力するのが一番楽そうだなと思ってそれで実装することにしました。 反転した値がオーバーフローする場合は0を返す仕様だったので、 x == Integer.MIN_VALUE の確認を入れたり、 Integer.parseIntNumberFormatExceptionが発生した時は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;
            }
        }
    }
}

しかし、それでもやはり遅かった。。。

f:id:tsukakei1012:20181127162826p:plain

他の人の解答はというと、

/**
 * 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)だから当たり前か。)。 f:id:tsukakei1012:20181127150713p:plain

それで他の人(の多くは)どう解答しているのか見てみることにします。 (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がんばります。