공부일기

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
};

Given an unsorted array of integers nums,
return the length of the longest continuous increasing subsequence (i.e. subarray).
The subsequence must be strictly increasing.

A continuous increasing subsequence is defined by two indices l and r (l < r) such that
it is [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] and for each l <= i < r, nums[i] < nums[i + 1].

예제:

Example 1:
Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element 4.

Example 2:

Input: nums = [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2] with length 1. Note that it must be strictly
increasing.

난이도: easy

정렬되지 않은 리스트가 있다
오름차순으로 증가하는 리스트의 길이 중 가장 긴 길이를 구해라

처음엔 문제를 잘못이해 하여 일정한 간격으로 증가하는 리스트의 길이를 구하는 줄 알았다
일정하지 않더라도 증가만 하면 되는 조건으로 구해주면 된다

String, value

var findLengthOfLCIS = function(nums) {
    let maxLength = 0;
    let currentLength = 0;

    for (let i = 0; i < nums.length; i++) {
      if ((i === 0) || nums[i] > nums[i - 1]) {
        currentLength += 1
      } else {
        currentLength = 1
      }
      if (currentLength > maxLength) {
        maxLength = currentLength
      }
    }
    return maxLength;
};

1번의 예제를 보면

[1, 3, 5, 4, 7]

[1, 3, 5]과 [4, 7] 두가지로 나뉘어 진다 

각각 오름차순으로 증가를 하고 있지만, 둘의 길이를 비교했을 때 가장 긴 길이는 3이다