jvmakine
BAN USERScala
object NumberStringCombinations extends App {
val conversion = Map(
'1' -> List('a', 'b', 'c'),
'2' -> List('c', 'd', 'e'),
'3' -> List('f', 'g', 'h'))
def combinations(in: String, agg: String = ""): List[String] = in match {
case "" => List(agg)
case str => conversion(str.head).flatMap(c => combinations(str.tail, agg + c))
}
println(combinations("12"))
}
Scala
object MaxPathSum extends App {
case class Node(weight: Int, left: Option[Node] = None, right: Option[Node] = None) {
// Return the max path within this tree and the current max path for the path containing this node
def maxPath: (Int, Int) = {
val (leftMax, leftPath) = left.map(_.maxPath).getOrElse((0,0))
val (rightMax, rightPath) = right.map(_.maxPath).getOrElse((0,0))
val path = List(leftPath + weight, rightPath + weight, weight).max
val max = List(leftMax, rightMax, path).max
(max, path)
}
}
val tree =
Node(-1, Some(Node(2,
Some(Node(-5)),
Some(Node(3,
None,
Some(Node(6)))))),
Some(Node(-5,
Some(Node(1)),
Some(Node(8))))
)
println(tree.maxPath._1)
}
Modification of QuickSelect to partition by the kth largest element and sum the larger elements left from it. Runtime same as with QuickSelect, O(N)
In scala:
object MaxSubsetSum extends App {
val list = Array(8, -5, 3, 7, 9 ,0)
println(largestSubsetSum(3, 0, list.length - 1))
def swap(from: Int, to: Int): Unit = {
val temp = list(to)
list(to) = list(from)
list(from) = temp
}
def partition(left: Int, right: Int, pivot: Int): Int = {
var index = left
var i = left
swap(pivot, right)
while (i < right) {
if (list(i) > list(right)) {
swap(i, index)
index += 1
}
i += 1
}
swap(right, index)
index
}
def largestSubsetSum(k: Int, left: Int, right: Int): Int = {
val v = partition(left, right, (right - left) / 2)
if (v == k) list.take(k).sum
else if (v < k) largestSubsetSum(k, v + 1, right)
else largestSubsetSum(k, left, v - 1)
}
}
Scala
object PatternMatch extends App {
println(pmatch("*an*", List("crane", "drain", "refrain")))
def pmatch(p: String, strings: List[String]): List[String] = {
strings.filter { str =>
var si = 0
var pi = 0
var hit = false // set to true if we hit a last * in the pattern
while (si < str.length && pi < p.length && !hit) {
if (p(pi) == '*') {
if (pi < p.length - 1 && p(pi + 1) == str(si)) {
pi += 1
} else if (pi == p.length - 1) {
pi += 1
hit = true
} else {
si += 1
}
} else if (p(pi) == str(si)) {
pi += 1
si += 1
} else {
pi = 0
si += 1
}
}
// the full pattern was matched
pi == p.length ||
// allows * to match empty character as the final character in the pattern
(pi == p.length - 1 && p.last == '*')
}
}
}
Scala
object Palindrome extends App {
println(isPalindrome("L*&EVe)))l"))
def isPalindrome(str: String): Boolean = {
var (left, right) = (0, str.length - 1)
while (left < right) {
val (lc, rc) = (str(left), str(right))
if (!lc.isLetterOrDigit) {
left += 1
} else if (!rc.isLetterOrDigit) {
right -= 1
} else {
if (rc.toLower != lc.toLower) return false
left += 1
right -= 1
}
}
true
}
}
Scala
object Patterns extends App {
val transforms = List(
("1", "ABC"),
("2", "DE"),
("3", "PQ"),
("12", "X"))
println(patterns("123"))
def conversions(str: String, agg: List[String] = List.empty): List[List[String]] = {
if (str.length == 0) return List(agg)
transforms.flatMap { case (from, to) =>
if (str.startsWith(from)) {
conversions(str.substring(from.length), agg :+ to)
} else {
List.empty
}
}
}
def combinations(lst: List[String], agg: String = ""): List[String] = lst match {
case "" :: rest => combinations(rest, agg)
case str :: rest => str.flatMap(c => combinations(rest, agg + c)).toList
case _ => List(agg)
}
def patterns(input: String) = conversions(input).flatMap(combinations(_))
}
import scala.collection.immutable.Stack
object BalanceParenthesis extends App {
println(balance("((a((aa(((()d(())("))
def balance(input: String): String = {
var stack = Stack.empty[Int]
var remove = Set.empty[Int]
val withIndices = input.toCharArray.zipWithIndex
withIndices.foreach { case (c, i) =>
c match {
case '(' => stack = stack.push(i)
case ')' => if (stack.isEmpty) remove = remove + i else stack = stack.pop
case _ =>
}
}
remove = remove ++ stack.toSet
withIndices.filterNot(v => remove.contains(v._2)).map(_._1).mkString
}
}
Find the position for the last 1 with min number of flips required by counting the 0s from the left and 1s from the right. Return the smallest sum of the two
- jvmakine April 09, 2018