kkokey/leetcode

Solve leetcode problem

leetcode's Issues

Problem_02 문제 코딩

/*
주어진 숫자 배열 "nums" 중에 2개의 숫자를 더하여
결과값 R과 동일한 숫자의 index번호를 구하시오.
index 번호는 총 2개 입니다.
- 전제 조건 -
1. 배열 "nums"는 정렬된 값 입니다.
2. 합산한 값이 결과 값 R이 되는 숫자 2개는 반드시 포함한다.
3. 배열은 기본적으로 정렬되어 있다.
4. 시간 복잡도가 O(n)보다 적어야 한다.
5. 배열 nums의 크기 L은 다음과 같다.
4 < L < 100
* 시간 복잡도가 O(n) 이거나 O(n) 보다 크다면 오답 입니다.
예)
배열 nums : {1,2,7,11,15}
결과 R. : 3
요청index : [0,1]
이번 문제부터는 올려주신 답안들을
제가 보고 답인지 아닌지 확인 할 예정입니다.
제가 잘못 판단할 수 있으니 이의가 있으시면
말씀해주세요!
*/

public static void problem(int[] nums, int target){

    int compareIdx = 0;
    int startIdx = 0;
    int endIdx = nums.length-1;
    int n;
    int[] rsNums= new int[2];
    int oCount = 1;
    if( target == (nums[startIdx] + nums[endIdx])){
        rsNums[0] = startIdx;
        rsNums[1] = endIdx;
    }
    compareIdx = getMidIdx(startIdx, endIdx); // 배열의 중간 값 구하기.
    while(target != (nums[startIdx] + nums[endIdx])) {
        oCount++;                                       // Big O check.

        if(target == (nums[startIdx] + nums[endIdx])){
            rsNums[0] = startIdx;
            rsNums[1] = endIdx;
            break;
        }

        n = nums[compareIdx];
        System.out.println("idx::["+startIdx+","+endIdx+"]");
        if(target-n > n) {
            startIdx = compareIdx;
            compareIdx = getMidIdx(startIdx, endIdx); // 배열의 중간 값 구하기.
            rsNums[0] = startIdx;
        }else{
            endIdx = compareIdx;
            compareIdx = getMidIdx(startIdx, endIdx); // 배열의 중간 값 구하기.
            rsNums[1] = endIdx;
        }
    }
    System.out.println("Big O:["+oCount+"], index :["+rsNums[0]+","+rsNums[1]+"]");
}

public static int getMidIdx(int startIdx, int length){
    System.out.println(startIdx+"|"+length);
    return ((length-startIdx) >>> 1) + startIdx;
}

public static void main(String[] args) {
    int[] nums  = {2,3,4};             // 주어지는 배열.
    int target = 6;                    // 배열중 2개의 숫자를 더했을 때 나와야 하는 결과 값.
    problem(nums, target);
}

problem_02_solution

• 삭제 - 푼 코드는 일요일 아침부터 올려주세요~ (from nameboy)

problem 03

problem_02 solution (scala)

def solve(nums: IndexedSeq[Int], r: Int): (Int, Int) = {
  require(nums.size > 2, s"the size of nums should be larger than 2: ${nums.size}")
  val upperLimitValue = r - nums(0)
  //println(s"===> upperLimitValue: $upperLimitValue")
  
  @annotation.tailrec
  def findUpperLimit(from: Int, until: Int): Int = {
    val m = (from + until)/2
    //println(s"===> findUpperLimit($from, $until): ${nums(m)} at $m")
    if (m == from) until
    else (upperLimitValue - nums(m)).signum match {
      case 0 => m
      case 1 => findUpperLimit(m, until)
      case -1 => findUpperLimit(from, m)
    }
  }
  
  @annotation.tailrec
  def loop(from: Int, to: Int): (Int, Int) = {
    require(from < to, s"No solution found: ($from, $to)")
    val sum = nums(from) + nums(to)
    //println(s"===> loop($from, $to): $sum")
    (r - sum).signum match {
      case 0 => (from, to)
      case 1 => loop(from + 1, to)
      case -1 => loop(from, to - 1)
    }
  }
  
  loop(0, findUpperLimit(1, nums.size))
}

println(solve(IndexedSeq(1, 2, 7, 11, 15), 3) == (0, 1))
println(solve(IndexedSeq(1, 2, 7, 11, 15), 13) == (1, 3))

Best Time to Buy and Sell Stock 풀이

solve :: [Int] -> Int
solve = maximum . (zipWith subtract <*> scanr1 max)

2번 문제 코드

중간에 값 계산해서 좀더 빨리 줄일수도 있을거 같은데.. 테스트 만드는게.. ㅠㅠ

const prob2 = (input, need) => {
  let start = 0
  let end = input.length - 1

  while(input[start] + input[end] != need) {
    if(input[start] + input[end] > need)
      end--
    else
      start++
  }
  return [start, end]
}

Path Sum 풀이

문제 푼것에 의의를...

data Tree a = Leaf | Node (Tree a) a (Tree a) deriving (Eq, Show)
type Path a = Either [a] [(a, [a], Tree a)]

solve :: Int -> Tree Int -> Int
solve sum tree = length . solve' $ Right [(sum, [], tree)]

solve' :: Path Int -> [Int]
solve' (Left breadcrumb) = breadcrumb
solve' (Right []) = []
solve' (Right ps) = solve' . fmap concat . sequence . fmap step $ ps

step :: (Int, [Int], Tree Int) -> Path Int
step (0, breadcrumb, Leaf) = Left breadcrumb
step (sum, breadcrumb, tree)
  | sum <= 0 = Right []
  | tree == Leaf = Right []
  | otherwise = let
    Node left value right = tree
    sum' = sum - value
    breadcrumb' = value : breadcrumb
  in Right [(sum', breadcrumb', left), (sum', breadcrumb', right)]

Word Ladder 풀이

문제 푼것에 의의를...

import           Data.List  (delete, insert, nub, splitAt)
import           Data.Maybe (fromJust, isJust)
import           Prelude    hiding (Word)

type Mask = (String, [String])
type Word = (String, [String])
type Neighbor = [String]
type Link = (String, [String])
data SolveData = SolveData {
  count      :: Int,
  current    :: String,
  breadcrumb :: [String],
  remain     :: [Link]
}
type Solve = (Int, [String])

makeMask :: String -> Mask
makeMask a = (a, masks) where
  length1 = length a - 1
  masks = map (mask . split) [0..length1]
  split = flip splitAt a
  mask (h, t) = h ++ '_' : tail t

makeWord :: Mask -> [Word]
makeWord (w, ms) = foldr (\ m rs -> (m, [w]) : rs) [] ms

mergeMask :: Word -> [Word] -> [Word]
mergeMask mw as = insert mw' as' where
  (m, ws) = mw
  pws = lookup m as
  mw' = maybe mw (\ pws -> (m, nub (ws ++ pws))) pws
  as' = if isJust pws then delete (m, fromJust pws) as else as

hasNeighbor :: Mask -> Bool
hasNeighbor (_, ws) = length ws > 1

makeNeighbor :: [Mask] -> [Neighbor]
makeNeighbor = map (\ (_, ms) -> ms)

mergeNeighbor :: Neighbor -> [Link] -> [Link]
mergeNeighbor ws gs = foldr f gs ws where
  f m as = insert ws'' as' where
    ws' = delete m ws
    pws = lookup m as
    ws'' = maybe (m, ws') (\ pws -> (m, nub (ws' ++ pws))) pws
    as' = if isJust pws then delete (m, fromJust pws) as else as

makeLinks :: String -> [String] -> [Link]
makeLinks beginWord wordList = foldr mergeNeighbor [] .
  makeNeighbor .
  filter hasNeighbor .
  foldl (foldr mergeMask) [] .
  map makeWord .
  map makeMask $ beginWord : wordList

emptySolve :: Solve
emptySolve = (maxBound, [])

solve :: String -> String -> [String] -> Int
solve beginWord endWord wordList = fst s where
  links = makeLinks beginWord wordList
  s = solve' endWord (SolveData 0 beginWord [] links) emptySolve

solve' :: String -> SolveData -> Solve -> Solve
solve' target (SolveData count current breadcrumb remain) solve@(minCount, _) = value where
  next = lookup current remain
  next' = fromJust next
  count' = count + 1
  breadcrumb' = current : breadcrumb
  remain' = delete (current, next') remain
  nextSolve = foldr (\ current' -> solve' target (SolveData count' current' breadcrumb' remain')) solve
  value = if current == target
    then if minCount > count' then (count', breadcrumb') else solve
    else if minCount <= count' || current `elem` breadcrumb then solve else maybe solve nextSolve next