공부일기

You are given an array of unique integers salary where salary[i] is the salary of the ith employee.

Return the average salary of employees excluding the minimum and maximum salary. Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input: salary = [4000,3000,1000,2000]
Output: 2500.00000
Explanation: Minimum salary and maximum salary are 1000 and 4000 respectively.
Average salary excluding minimum and maximum salary is (2000+3000) / 2 = 2500

Example 2:

Input: salary = [1000,2000,3000]
Output: 2000.00000
Explanation: Minimum salary and maximum salary are 1000 and 3000 respectively.
Average salary excluding minimum and maximum salary is (2000) / 1 = 2000

난이도: easy

사원들 연봉의 평균을 구하는 문제이다

가장 높은 연봉을 받는 사원과 가장 낮은 연봉을 받는 사원을 제외한 나머지의 평균을 구해라 

var average = function(salary) {
    let result = 0;
    const sorted = salary.sort((a, b) => a - b);
    
    sorted.reduce((acc, cur) => {
        result += cur;
    })
    
    result = result - sorted[sorted.length - 1]
    
    return result / (salary.length - 2) 
};

1. 정렬

2. 연봉 합치기 (여기서 인덱스를 빈칸으로 두어 가장 낮은 연봉은 제외하고 더해준다) 

3. 가장 많은 연봉을 제외

4. 평균 구하기 

Given two non-negative integers low and high. Return the count of odd numbers between low and high (inclusive).

Example 1:

Input: low = 3, high = 7
Output: 3
Explanation: The odd numbers between 3 and 7 are [3,5,7].

Example 2:

Input: low = 8, high = 10
Output: 1
Explanation: The odd numbers between 8 and 10 are [9].

난이도: easy

이 문제는 홀수인 숫자를 찾는 것으로

무조건 O(1)로 풀어야 된다라고 생각이 든게 그냥 들었다 

반복문으로 풀면 나눠서 count++ 해주면 되는데 이러면 분명 효율이 맨끝으로 갔을 것 같다 

var countOdds = function(low, high) {
    let count = 0;
    
    if (low % 2 === 1 || high % 2 === 1) count++
    
    count = count + Math.floor((high - low) / 2);

    return count;
};

문제에서 생각해줘야 할 부분은 

1. low: 홀수, high: 홀수

2. low, high 둘 중 하나 홀수

3. low: 짝수, high: 짝수

이렇게만 생각해주면 된다

Math.floor를 해줘서 둘 중 하나가 홀수인 경우를 해결해준다고 생각하면 된다 

풀이할 때 공책에 하나씩 적어가면서 규칙이 어떤지 찾아봤다

암산으로는 도저히 안풀려서 ㅋㅋㅋ 

The Tribonacci sequence Tn is defined as follows:

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given n, return the value of Tn.

Example 1:

Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

Example 2:

Input: n = 25
Output: 1389537

이 문제는 피보나치를 이해하고 풀이를 했는가를 물어보기 위해 나온 문제인듯 하다 

원래 하던 피보나치 풀이에 숫자를 하나 더 더해주면 된다 

DP

var tribonacci = function(n) {
    const arr = new Array(n).fill(0);
    
    arr[0] = 0;
    arr[1] = 1;
    arr[2] = 1;
    arr[3] = 2;
    
    for (let i = 4; i < n + 1; i++) {
        arr[i] = arr[i -1] + arr[i -2] + arr[i - 3];
    }
    
    return arr[n];
};

recursive하게 풀이 하려면 이전글에 지금과 똑같이 해주면 된다 

Leetcode에 챌린지가 있길래 이번에 참여해봤다 

2개 참여해서 총 4문제 풀었는데 이제 슬슬 미디움에 도전할 때가 된 것 같다 

챌린지 참여하면서 미디움 도전해봐야지 

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

난이도: easy 

DP

var fib = function(n) {
    const arr = new Array(n).fill(0);
    arr[0] = 0;
    arr[1] = 1;
    arr[2] = 1;
    
    for (let i = 3; i < n + 1; i++) {
        arr[i] = arr[i - 1] + arr[i - 2];
    }
    
    return arr[n]
};

Recursive

var fib = function(n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
    
    return fib(n - 1) + fib(n - 2);
}

물론 효율은 DP로 풀이하는 것이 훨씬 좋다 

Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs (i, j) where 0 <= i < j < n, such that nums[i] == nums[j] and (i * j) is divisible by k.

Example 1:

Input: nums = [3,1,2,2,2,1,3], k = 2
Output: 4
Explanation:
There are 4 pairs that meet all the requirements:
- nums[0] == nums[6], and 0 * 6 == 0, which is divisible by 2.
- nums[2] == nums[3], and 2 * 3 == 6, which is divisible by 2.
- nums[2] == nums[4], and 2 * 4 == 8, which is divisible by 2.
- nums[3] == nums[4], and 3 * 4 == 12, which is divisible by 2.

Example 2:

Input: nums = [1,2,3,4], k = 1
Output: 0
Explanation: Since no value in nums is repeated, there are no pairs (i,j) that meet all the requirements.

난이도: easy

같은 숫자인 두개의 index를 곱해서 k로 나누어 지는 경우를 구해라 

var countPairs = function(nums, k) {
    // map 생성 { number => [index] }
    const map = new Map();
    let count = 0;
    // for 문 -> map.get(number) ? [index].push : push(index)
    for (let i = 0; i < nums.length; i++) {
        const number = nums[i];
        const getItem = map.get(number);
        
        if (getItem) {
            for (let j = 0; j < getItem.length; j++) {
                const index = getItem[j];
                if ((index * i) % k === 0) count++;
            }
            getItem.push(i);
        } else {
            map.set(number, [i]);
        }
    }
    return count;
};

map을 생성해서 같은 숫자인지 확인 -> 곱해서 k로 나누어 떨어지는 확인 

두가지로 생각해서 풀이를 했다 hashMap을 사용해서 풀이 

언제쯤 easy에서 벗어날 수 있을까 

이중 for문으로 푼 경우가 더 효율이 좋은 걸 보고 내가 생각이 짧았구나 싶었다 

이래서 아직 medium은 벽이 느껴지나 보다 

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