공부일기

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

난이도: easy

재귀로 풀이 

var mergeTwoLists = function(list1, list2) {
  if (!list1 || !list2) {
    return list1 || list2;
  }

  let node;

  if (list1.val < list2.val) {
    node = list1;
    node.next = mergeTwoLists(list1.next, list2);
  } else {
    node = list2;
    node.next = mergeTwoLists(list1, list2.next);
  }
  return node;
};

list1과 list2중 남아있는 것이 있다면 나머지를 전부 return하도록 하고, 

새롭게 생성할 node에는 list1과 list2의 현재 value를 비교하여 넣어주도록 

효율이 그렇게 좋진않은데, 아직 medium도 좀 어렵다... 어떻게 더 효율적으로 할 수 있을지 감이 잘 안잡힌다 

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant extra space.

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

Example 2:

Input: nums = [1,1,2]
Output: [1]

Example 3:

Input: nums = [1]
Output: []

난이도: medium

중복된 숫자를 구하는 문제인데, 이 문제는 풀이가 어렵다기 보다는 어떻게 효율적으로 코드를 짤 것인가 떄문에
난이도가 medium으로 측정된듯 싶다

일반적으로 중복되는 숫자를 찾는 문제는 map을 이용하여 풀이 했던 경험이 있어
원래 풀던대로 그대로 풀었는데, 효율이 그닥 좋지 못하다

var findDuplicates = function(nums) {
  const result = [];
  const map = new Map();

  for (let i = 0; i < nums.length; i ++) {
    const number = nums[i];
    const item = map.get(number);

    if (item) {
      result.push(number)
    }
    map.set(number, i + 1)
  }
  return result
};

절대값을 이용하는 풀이가 많이 보이는데 솔직히 이해가 안된다
왜 절대값을 이용하지?

A shop is selling candies at a discount.

For every two candies sold, the shop gives a third candy for free.

The customer can choose any candy to take away for free as long as the cost of the

chosen candy is less than or equal to the minimum cost of the two candies bought.

For example, if there are 4 candies with costs 1, 2, 3, and 4, and the customer buys candies with costs 2 and 3,

they can take the candy with cost 1 for free, but not the candy with cost 4.
Given a 0-indexed integer array cost, where cost[i]

denotes the cost of the ith candy, return the minimum cost of buying all the candies.

Example 1:

Input: cost = [1,2,3]
Output: 5
Explanation: We buy the candies with costs 2 and 3, and take the candy with cost 1 for free.
The total cost of buying all candies is 2 + 3 = 5. This is the only way we can buy the candies.
Note that we cannot buy candies with costs 1 and 3, and then take the candy with cost 2 for free.
The cost of the free candy has to be less than or equal to the minimum cost of the purchased candies.

Example 2:

Input: cost = [6,5,7,9,2,2]
Output: 23
Explanation: The way in which we can get the minimum cost is described below:
- Buy candies with costs 9 and 7
- Take the candy with cost 6 for free
- We buy candies with costs 5 and 2
- Take the last remaining candy with cost 2 for free
Hence, the minimum cost to buy all candies is 9 + 7 + 5 + 2 = 23.

Example 3:

Input: cost = [5,5]
Output: 10
Explanation: Since there are only 2 candies, we buy both of them. There is not a third candy we can take for free.
Hence, the minimum cost to buy all candies is 5 + 5 = 10.

난이도: easy

캔디가게에서 캔디를 2+1으로 판매한다.

서비스로 주는 캔디는 2개의 캔디중에 가격이 낮은 캔디의 가격보다 작거나 같아야한다

서비스로 주는 캔디의 가격이 높을수록 저렴하게 살 수 있겠구나 생각했고,
가장 비싼 캔디부터 구매하도록 풀이

/**
 * @param {number[]} cost
 * @return {number}
 */
var minimumCost = function(cost) {
  // 사탕은 2 + 1
  const sorted = cost.sort((a, b) => a - b);
  let count = 1;
  let result = 0;

  while (sorted.length !== 0) {
    const max = sorted.pop();
    if (count % 3 !== 0) {
      result += max
    } 
    count++
  }

  return result
};

You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

Example 1:

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

Example 2:

Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation: The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.

난이도: easy

단어들의 모음인 words와 chars가 주어졌을 때,
word가 chars에 모두 포함되면 포함된 글자들의 길이를 모두 더한값을 구해라

이해가 안되서 몇번 다시 읽었다

단순하게 word의 글자들이 모두 포함되는지를 찾는 것이다

const pass = (word, chars) => {
  let count = 0;

  for (let i = 0; i < word.length; i++) {
    const char = word[i]
    if (chars.includes(char)) {
      chars = chars.replace(char, '')
      count++
    }
  }

  if (count === word.length) return true
  return false 
}

var countCharacters = function(words, chars) {
  let result = '';
  let length = 0;

  for (let i = 0; i < words.length; i++) {
    // 단어 체크 
    const word = words[i]
    if (pass(word, chars)) {
      length = length + word.length
    }
  }  
  return length  
};

처음에는 단순히 포함된 되면 되는줄 알고,
chars = chars.replace(char, '')이 코드 없이 포함되는지만 찾았고,
중복되는 경우도 생각해야 해서 추가한뒤 통과했다

You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.

Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2
Output: false

난이도: easy

꽃이 심어져 있는 화단이 있다, 0은 안심어져있는 곳, 1은 이미 심어져 있는 곳
주변에 꽃이 심어져있지 않은 곳에만 꽃을 심을 수 있다

n이 주어졌을 때, n개의 숫자만큼 심을 수 있는지 판단해라

var canPlaceFlowers = function(flowerbed, n) {
  let flowerCount = 0;

  for (let i = 0; i < flowerbed.length; i++) {

    if (!flowerbed[i - 1] && !flowerbed[i] && !flowerbed[i + 1]) {
      flowerbed[i] = 1
      flowerCount++
    }
  }
  return flowerCount >= n
};

처음에는 화단의 끝부분일 경우와 중간에 심는 경우 두가지로 나누어서 생각했고,

통과를 하는데 너무 많은 조건이 붙기에, 자바스크립트에서 Array에 존재하지 않는 index를 불러올 경우
어떻게 되는지 확인 후, 다시 풀었다

풀고나니 되게 별거 아니어서 좀 허탈하네

easy난이도 100개정도는 풀어보고 medium으로 얼른 넘어가봐야겠다

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

난이도: easy

간단한 스택구현이다

push, pop, top, getMin 4가지 구현이고
top은 스택에서 가장 마지막에 들어온 숫자를 return 해주고, getMin은 스택내부에서 가장 작은 숫자를 return 해준다

MinStack.prototype.push = function(val) {
  this.stack.push(val)
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
  this.stack.pop()
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
  return this.stack[this.stack.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
  let min = Number.MAX_SAFE_INTEGER;

  for (let i = 0; i < this.stack.length; i++) {
    const value = this.stack[i];
    if (min > value) {
      min = value
    }
  }
  return min
};

정말 간단하게 stack구현이라 금방 풀었다

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation: 
All possible ways to reach at index 3 with value 0 are: 
index 5 -> index 4 -> index 1 -> index 3 
index 5 -> index 6 -> index 4 -> index 1 -> index 3 

Example 2:

Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true 
Explanation: 
One possible way to reach at index 3 with value 0 is: 
index 0 -> index 4 -> index 1 -> index 3

Example 3:

Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.

난이도: medium

자연수로 이루어진 Array에서 첫 시작점을 주고 점프를 하며 이동하는데, 0에 도달 가능한지 구해라

문제를 보고 DFS로 풀어야겠다 생각했는데

이런식으로 인덱스에서 이동가능한 경우의 수를 확인해보면 연결되는 모습이 보이는데

결과적으로는 그래프의 형태가 나오고 DFS겠구나 생각이 들었다

var canReach = function(arr, start) {
  const visited = new Set(); // visited = { index: arr[index] } index에 도달한적이 있는가?

  const dfs = (index) => {
    if (index < 0 || index > arr.length || visited.has(index)) {
      return false 
    }

    visited.add(index);
    const value = arr[index];
    if (value === 0) {
      return true
    }

    return dfs(index - value) || dfs(index + value)
  }

  return dfs(start);
};

메모리 효율이 좋지 못해서 풀이를 봤는데 대부분 Queue를 이용한 BFS로 풀이한 것으로 보인다

At a lemonade stand, each lemonade costs $5.
Customers are standing in a queue to buy from you and order one at a time (in the order specified by bills).
Each customer will only buy one lemonade and pay with either a $5, $10, or $20 bill.
You must provide the correct change to each customer so that the net transaction is that the customer pays $5.

Note that you do not have any change in hand at first.

Given an integer array bills where bills[i] is the bill the ith customer pays, return true if you can provide every customer with the correct change, or false otherwise.

Example 1:

Input: bills = [5,5,5,10,20]
Output: true
Explanation: 
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

Example 2:

Input: bills = [5,5,10,10,20]
Output: false
Explanation: 
From the first two customers in order, we collect two $5 bills.
For the next two customers in order, we collect a $10 bill and give back a $5 bill.
For the last customer, we can not give the change of $15 back because we only have two $10 bills.
Since not every customer received the correct change, the answer is false.

난이도: easy

bills = 손님들이 내는 돈의 순서
순서대로 레모네이드를 판매하는데 거스름돈을 지불하지 못하는 경우 false를 리턴
정상적으로 판매 가능하다면 true 리턴

거스름돈을 낼 수 있는 모든 경우의 수를 확인하면 되는 방식이고, 거스름돈이 큰 순서부터 내보내면 된다
Greedy 알고리즘이며, 경험상 거스름돈을 내는 문제는 대부분이 Greedy로 풀이 했었다

var lemonadeChange = function(bills) {
  let five = 0;
  let ten = 0;

  for (let i = 0; i < bills.length; i++) {
    const bill = bills[i];
    // 20일 경우
    if (bill === 20) {
      if (ten !== 0) {
        ten--;
        five--;
        if (five < 0) {
          return false
        }
      } else {
        five -= 3;
        if (five < 0) {
          return false
        }
      }
    }

    // 10일 경우 
    if (bill === 10) {
      ten++;
      five--;
      if (five < 0) {
        return false;
      }
    }

    // 5일 경우
    if (bill === 5) {
      five++
    }
  }
  return true
};