LeetCode 12. Integer to Roman

LeetCode Problem No.12.

No.11 is here.

modalsoul.hatenablog.com

12. Integer to Roman

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Example 1

Input: 3
Output: "III"

Example 2

Input: 4
Output: "IV"

Example 3

Input: 9
Output: "IX"

Example 4

Input: 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 5

Input: 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Code

object Solution {
  def intToRoman(num: Int): String = {
    def toRoman(i:String, v:String, x:String, n:Int) = {
      if(n == 4) i+v else if(n == 9) i+x else if(n < 4) i*n else v + (i * (n%5))
    }
    val i = toRoman("I", "V", "X", num%10)
    val x = toRoman("X", "L", "C", num%100/10)
    val c = toRoman("C", "D", "M", num%1000/100)
    val m = "M" * (num%10000/1000)
    m+c+x+i
  }
}

Methods

D: 1, 10, 100
I: D
V: 5*D
X: 10*D

• In case n < 4, I by n
• In case n = 4, V
• In case n > 4, V and I by n%5
• In case n = 9, IX

Results

Runtime: 480 ms, faster than 76.19% of Scala online submissions for Integer to Roman. Memory Usage: 49 MB, less than 100.00% of Scala online submissions for Integer to Roman.

LeetCode 11. Container With Most Water

LeetCode Problem No.11.

No.10 is here.

modalsoul.hatenablog.com

11. Container With Most Water

https://leetcode.com/problems/container-with-most-water/

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Example

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

Code1

object Solution {
  import scala.math.{max, min, abs}
  def maxArea(height: Array[Int]): Int = {
    var tmp = 0
    for {
      n1 <- 0 until height.length
      n2 <- 0 until height.length
    } {
      tmp = max(tmp, min(height(n1), height(n2)) * abs(n1 - n2))
    }
    tmp
  }
}

Methods

• Get all pairs of line and calculate the area of all pairs.

Results

Runtime: 1412 ms, faster than 7.89% of Scala online submissions for Container With Most Water. Memory Usage: 53.4 MB, less than 100.00% of Scala online submissions for Container With Most Water.

Code2

object Solution {
  import scala.math.{max, min, abs}
  def maxArea(height: Array[Int]): Int = {
    var tmp = 0
    var left = 0
    var right = height.length - 1
    while (right > left) {
      val rh = height(right)
      val lh = height(left)
      tmp = max(tmp, min(rh, lh) * (right - left))
      if(rh > lh) left = left + 1
      else right = right - 1
    }
    tmp
  }
}

Methods

• left starts with head of array.
• right starts with last of array.
• Calculate area with left and right.
• Shift left or right which is smaller.

Results

Runtime: 708 ms, faster than 30.26% of Scala online submissions for Container With Most Water. Memory Usage: 75.5 MB, less than 100.00% of Scala online submissions for Container With Most Water.

LeetCode 10. Regular Expression Matching

LeetCode Problem No.10.

No.9 is here.

modalsoul.hatenablog.com

10. Regular Expression Matching

https://leetcode.com/problems/regular-expression-matching/

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

'.' Matches any single character. '*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Example 1

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Code

object Solution {
    def charMatch(s:String, p:String) = !s.isEmpty && (p.head == s.head || p.head == '.')
    def isMatch(s: String, p: String): Boolean = {
        if(p.isEmpty) s.isEmpty
        else if(p.length >= 2 && p.tail.head == '*') isMatch(s, p.drop(2)) || charMatch(s, p) && isMatch(s.tail, p)
        else charMatch(s, p) && isMatch(s.tail, p.tail)
    }
}

Methods

• If next pattern char is '*', check these cases.
  • Matching zero of the preceding element.
  • Matching more of the preceding element.
    • Compare string head char and pattern head char and check rest matching.
• If next patter char is not '*', compare string head char and pattern head char and check rest matching.

Results

Runtime: 600 ms, faster than 34.61% of Scala online submissions for Regular Expression Matching. Memory Usage: 54.4 MB, less than 100.00% of Scala online submissions for Regular Expression Matching.

LeetCode 9. Palindrome Number

LeetCode problem No.9.

No.8 is here.

modalsoul.hatenablog.com

9. Palindrome Number

https://leetcode.com/problems/palindrome-number/

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1

Input: 121
Output: true

Example 2

Input: -121
Output: false

Example 3

Input: 10
Output: false

Code

object Solution {
    def isPalindrome(x: Int): Boolean = {
        val str = x.toString
        str == str.reverse
    }
}

Methods

• Convert integer to string.
• Make reversed string.
• Compare string and reversed string.

Result

Runtime: 512 ms, faster than 6.09% of Scala online submissions for Palindrome Number. Memory Usage: 55 MB, less than 100.00% of Scala online submissions for Palindrome Number.

Follow up

Coud you solve it without converting the integer to a string?

Code

object Solution {
    def isPalindrome(x: Int): Boolean = {
        if(x < 0 || (x%10 == 0 && x != 0)) false
        else {
          var num = x
          var reversed = 0
          while(num > reversed) {
            reversed = reversed*10 + num%10
            num = num/10
          }
          num == reversed || num == reversed/10
        }
    }
}

Methods

• Initial num is x.
• Initial reversed num is 0.
• Calculate reversed num while reversed num is smaller than num.
  • Multiply reversed num by 10 and add remainder of num.
  • Divide num by 10.
• If num is equal to reversed num, true.
• if num is equal to reversed num divided by 10, true.

Result

Runtime: 904 ms, faster than 6.09% of Scala online submissions for Palindrome Number. Memory Usage: 54.6 MB, less than 100.00% of Scala online submissions for Palindrome Number.

LeetCode 8. String to Integer (atoi)

LeetCode problem No.8.

No.7 is here.

modalsoul.hatenablog.com

8. String to Integer (atoi)

https://leetcode.com/problems/string-to-integer-atoi/

Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:

• Only the space character ' ' is considered as whitespace character.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (2³¹ − 1) or INT_MIN (−2³¹) is returned.

Example 1

Input: "42"
Output: 42

Example 2:

Input: "   -42"
Output: -42

Code

object Solution {
  val numChars = "0123456789"
  def myAtoi(str:String): Int = {
    val trimed = str.dropWhile(_ == ' ')
    if(trimed.isEmpty) return 0
    val (sign, in) = if(trimed.head == '+') (1, trimed.tail) else if(trimed.head == '-') (-1, trimed.tail) else (1, trimed)
    var result = 0L
    for {
      n <- in
    } {
      if(numChars.contains(n)) {
        result = result*10 + n.asDigit
        if(result*sign >= scala.Int.MaxValue) return scala.Int.MaxValue
        if(result*sign <= scala.Int.MinValue) return scala.Int.MinValue
      } else {
        return (result*sign).toInt
      }
    }
    (result*sign).toInt
  }
}

Methods

• Discards whitespaces.
• Determine sign from character at the head of the trimmed string.
  • If the trimmed string starts with optional sign character(+/-), sign is 1/-1. (Drop optional sign character).
  • Else, sign is 1.
• Read a character.
  • If a character is a number, increase result by one digit, and plus.
  • If a character is not a number, multiply result and sign, return it.
• After reading, multiply result and sign, return it.

Result

Runtime: 488 ms, faster than 17.39% of Scala online submissions for String to Integer (atoi). Memory Usage: 55.1 MB, less than 100.00% of Scala online submissions for String to Integer (atoi).

LeetCode 7. Reverse Integer

LeetCode problem No.7.

No.6 is here.

modalsoul.hatenablog.com

7. Reverse Integer

https://leetcode.com/problems/reverse-integer/

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

Example 1

Input: 123
Output: 321

Example 2

Input: -123
Output: -321

Example 3

Input: 120
Output: 21

Note Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Code 1

object Solution {
    def reverse(x: Int): Int = {
        var tmp = x
        var result = 0L
        while(tmp/10 != 0) {
          val digit = tmp%10
          result = result * 10 + digit
          tmp = tmp/10
        }
        result = result * 10 + tmp
        if(result < scala.Int.MinValue || result > scala.Int.MaxValue) 0 else result.toInt
    }
}

Methods

• Divide x by 10 and get remainder.
• Multiply current result by 10 and add remainder.
• When x becomes smaller than 10, exit while.
• If result is not in the the 32-bit signed integer range, result is 0.

Result

Runtime: 724 ms, faster than 5.95% of Scala online submissions for Reverse Integer. Memory Usage: 54.2 MB, less than 100.00% of Scala online submissions for Reverse Integer.

Very slowly...orz

Code 2

object Solution {
    def reverse(x: Int): Int = {
        var tmp = x
        var result = 0L
        Iterator.continually(tmp).takeWhile( n => n/10 != 0).foreach { n =>
          val digit = n%10
          result = result * 10 + digit
          tmp = tmp/10
        }
        result = result * 10 + tmp
        if(result < scala.Int.MinValue || result > scala.Int.MaxValue) 0 else result.toInt
    }
}

Methods

• Use Iterator.continually instead of while

Result

Runtime: 428 ms, faster than 5.95% of Scala online submissions for Reverse Integer. Memory Usage: 54.2 MB, less than 100.00% of Scala online submissions for Reverse Integer.

A little bit optimized, but not fast yet.

Code 3

object Solution {
    def reverse(x: Int): Int = {
        val result = if(x >= 0) x.toString.reverse.toLong else x.toString.reverse.init.toLong * -1
        if(result < scala.Int.MinValue || result > scala.Int.MaxValue) 0 else result.toInt
    }
}

Methods

• Convert Int to String
• Reverse String
• Convert String to Long
• If result is not in the the 32-bit signed integer range, result is 0.

Result

Runtime: 616 ms, faster than 5.95% of Scala online submissions for Reverse Integer. Memory Usage: 54.1 MB, less than 100.00% of Scala online submissions for Reverse Integer.

⛳!!

LeetCode 6. ZigZag Conversion

LeetCode problem No.6.

No.5 is here.

modalsoul.hatenablog.com

6. ZigZag Conversion

https://leetcode.com/problems/zigzag-conversion/

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows

Example1

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example2

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"

Code 1

object Solution {
  def convert(s: String, numRows: Int): String = {
    if(numRows == 1) return s
    val converted:Array[String] = (0 until numRows).map(_ => "").toArray
    for {
      i <- 0 until s.length
    } {
      if(i%(numRows*2-2) < numRows) {
        converted(i%(numRows*2-2)) = converted(i%(numRows*2-2)) + s(i)
      } else {
        val index = numRows - i%(numRows-1) - 1
        converted(index) = converted(index) + s(i)
      }
    }
    converted.fold("")((z,n) => z + n)
  }
}

Methods

• Prepare numRows strings.
• Read given string and append each character to prepared strings.
  • Characters located indexes i in given string,
    • If i % (numRows*2-2) < numRows, characters are vertically aligned.
      • Characters will locate i % (numRows*2-2) row.
    • Else, characters are the only character in each column.
      • Characters will locate numRows - i%(numRows-1) - 1 row.
• Concatenate all strings.

Result

Runtime: 624 ms, faster than 12.20% of Scala online submissions for ZigZag Conversion. Memory Usage: 57.8 MB, less than 100.00% of Scala online submissions for ZigZag Conversion.

Code 2

object Solution {
  def convert(s: String, numRows: Int): String = {
    if(numRows == 1) return s
    val converted:Array[String] = (0 until numRows).map(_ => "").toArray
    for {
      i <- 0 until s.length
    } {
      if(i%(numRows*2-2) < numRows) {
        converted(i%(numRows*2-2)) = converted(i%(numRows*2-2)) + s(i)
      } else {
        val index = numRows - i%(numRows-1) - 1
        converted(index) = converted(index) + s(i)
      }
    }
    converted.mkString
  }
}

Methods

• Use mkString instead of fold.

Result

Runtime: 588 ms, faster than 14.63% of Scala online submissions for ZigZag Conversion. Memory Usage: 57.6 MB, less than 100.00% of Scala online submissions for ZigZag Conversion.