1. 문제 및 예시

 

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

 


Example:
Input:  [1,2,3,4]
Output: [24,12,8,6]
Constraint: It's guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.

 

 

 

2. 풀이

 

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    let result = [];
    let lp = 1, rp = 1;
    for(let i = 0; i < nums.length; i ++){
        result.push(lp);
        lp *= nums[i];
    }
    for(let i = nums.length -1; i >= 0; i --){
        result[i] *= rp;
        rp *= nums[i];
    }
    return result;
}

** 정방향으로 한번, 역방향으로 한번.

 

 

 

3. 결과

 

18 / 18 test cases passed.
Status: Accepted
Runtime: 80 ms
Memory Usage: 42.2 MB

 

 

 

 

 

1. 문제 및 예시

 

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

 


Example 1:
Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.


Example 2:
Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

 


** The length of the given binary array will not exceed 50,000.

 

 

 

2. 풀이

 

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxLength = function(nums) {
    const map = {};
    map[0] = -1;
    let sum = 0, max = 0;
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i] == 1 ? 1 : -1;
        if (sum in map) { max = Math.max(max, i - map[sum]); }
        else { map[sum] = i; }
    }
    return max;
};

** 변수를 둬서 1을 만나면 1, 아니면 -1을 더함.

** 변수값과 동일한 값을 만나면 그 사이의 하위배열은 0과 1의 수를 가져야 합니다.

 

 

 

3. 결과

 

555 / 555 test cases passed.
Status: Accepted
Runtime: 140 ms
Memory Usage: 46.2 MB

 

 

 

 

 

 

1. 문제 및 예시

 

We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together.  Suppose the stones have weights x and y with x <= y.  The result of this smash is:

  • If x == y, both stones are totally destroyed;
  • If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left.  Return the weight of this stone (or 0 if there are no stones left.)

 

 

Example 1:
Input: [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.

 

 

** 1 <= stones.length <= 30
** 1 <= stones[i] <= 1000

 

 

 

2. 풀이

 

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function(stones) {
  while(stones.length > 1){
    let s1 = Math.max(...stones);
    stones.splice(stones.indexOf(s1), 1);
    let s2 = Math.max(...stones);
    stones.splice(stones.indexOf(s2), 1);
    if(s1 != s2) {
        stones.push(s1-s2);
    }
  }
  return (stones.length > 0) ? stones[0] : 0;
};

 

 

 

3. 결과

70 / 70 test cases passed.
Status: Accepted
Runtime: 96 ms
Memory Usage: 33.8 MB

 

 

 

 

1. 문제 및 예시

 

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

 

 

Example:
Given a binary tree


Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

 

** The length of path between two nodes is represented by the number of edges between them.

 

 

 

2. 풀이

 

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function(root) {
    if(!root) return 0;
    let result = -1;
    let getH = function (node, h) {
        if(!node) return 0;
        let lh = getH(node.left);
        let rh = getH(node.right);
        result= Math.max(result, 1 + lh + rh);
        return 1 + Math.max(lh, rh);
    }
    getH(root);
    return result -1;
};

** 좌측 노드의 최대 깊이와 우측 노드의 최대 깊이를 구해 더한다.

 

 

3. 결과

 


106 / 106 test cases passed.
Status: Accepted
Runtime: 84 ms
Memory Usage: 37.4 MB

 

 

 

 

1. 문제 및 예시

 

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

  • push(x) -- Push element x onto stack.
  • pop() -- Removes the element on top of the stack.
  • top() -- Get the top element.
  • getMin() -- Retrieve the minimum element in the stack.

 

 

Example:

 

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

 

 

 

2. 풀이

 

/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.st = [];
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.st.push(x);
};

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

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

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.st.reduce((a, b)=> a > b ? b : a);
};

/** 
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

 

 

 

3. 결과

 


18 / 18 test cases passed.
Status: Accepted
Runtime: 140 ms
Memory Usage: 44.3 MB

 

 

 

 

1. 문제 및 예시

 

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

 

 

Example 1:
Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

 

Example 2:
Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

 

Example 3:
Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

 

Example 4:
Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".



** 1 <= S.length <= 200
** 1 <= T.length <= 200
** S and T only contain lowercase letters and '#' characters.

 

 

 

2. 풀이

 

/**
 * @param {string} S
 * @param {string} T
 * @return {boolean}
 */
var backspaceCompare = function(S, T) {
    let newS = [], newT = [];
    for(let c of S){
        if(c === "#") {
            newS.pop();
        }
        else{
            newS.push(c);
        }
    }
    newS = newS.join('');
    for(let c of T){
        if(c === "#") {
            newT.pop();
        }
        else{
            newT.push(c);
        }
    }
    newT = newT.join('');
    return newS === newT;
};

 

 

 

3. 결과

 

104 / 104 test cases passed.
Status: Accepted
Runtime: 52 ms
Memory Usage: 35.8 MB

 

 

 

 

1. 문제 및 예시

 

Given a non-empty, singly linked list with head node head, return a middle node of linked list. 
If there are two middle nodes, return the second middle node. 
  

Example 1: 
Input: [1,2,3,4,5] 
Output: Node 3 from this list (Serialization: [3,4,5]) 
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]). 
Note that we returned a ListNode object ans, such that: 
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL. 

 

Example 2: 
Input: [1,2,3,4,5,6] 
Output: Node 4 from this list (Serialization: [4,5,6]) 
Since the list has two middle nodes with values 3 and 4, we return the second one. 

** The number of nodes in the given list will be between 1 and 100.

 

 

 

2. 풀이

 

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function(head) {
    let arr = []
    let trav = function(node){
        arr.push(node);
        if(node.next){
            trav(node.next)
        }
    }
    trav(head);
    return arr[(arr.length %2 === 0) ? arr.length /2 : (arr.length-1) /2]    
};

 

 

 

3. 결과

 

15 / 15 test cases passed.
Status: Accepted
Runtime: 48 ms
Memory Usage: 33.7 MB

 

 

 

 

 

1. 문제 및 예시

 

Given an integer array arr, count element x such that x + 1 is also in arr.

If there're duplicates in arr, count them seperately.

 

 

Example 1:
Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

 

Example 2:
Input: arr = [1,1,3,3,5,5,7,7]
Output: 0
Explanation: No numbers are counted, cause there's no 2, 4, 6, or 8 in arr.

 

Example 3:
Input: arr = [1,3,2,3,5,0]
Output: 3
Explanation: 0, 1 and 2 are counted cause 1, 2 and 3 are in arr.

 

Example 4:
Input: arr = [1,1,2,2]
Output: 2
Explanation: Two 1s are counted cause 2 is in arr.

 

 

** 1 <= arr.length <= 1000
** 0 <= arr[i] <= 1000

 

 

 

2. 풀이

 

/**
 * @param {number[]} arr
 * @return {number}
 */
var countElements = function(arr) {
    let set = [], result = 0;
    for(let elem of arr){
        if(set.indexOf(elem) === -1){
            set.push(elem);
        }
    }
    for(let elem of arr){
        if(set.indexOf(elem +1) !== -1){
            result ++;
        }
    }
    return result;
};

 

 

 

3. 결과

 

35 / 35 test cases passed.
Status: Accepted
Runtime: 52 ms
Memory Usage: 33.8 MB

 

 

 

 

 

 

1. 문제 및 예시

 

Given an array of strings, group anagrams together.

 


Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

 


** All inputs will be in lowercase.
** The order of your output does not matter.

 

 

 

2. 풀이

 

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const mapStrs = new Map();
    for (let i = 0; i < strs.length; i++) {
        let str = strs[i];
        let sortedStr = str.split('').sort().join('');
        if(mapStrs.size > 0 && mapStrs.has(sortedStr)){
            mapStrs.get(sortedStr).push(str);
        }else{
            mapStrs.set(sortedStr,[str])
        }
    }
    let result = [];
    for(let list of mapStrs){
        result.push(list[1]);
    }
    return result;
};

** 단어내 알파벳을 정렬시켜 맵에 담아두고 같은 알파벳을 가진 단어를 찾는다.

 

 

 

3. 결과

 

101 / 101 test cases passed.
Status: Accepted
Runtime: 240 ms
Memory Usage: 45.2 MB

 

 

 

 

 

 

1. 문제

 

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

** You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

 

 

 

2. 예시

 

Example 1:
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

 

Example 2:
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

 

Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

 

 

 

3. 풀이

 

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let result = 0, idx = 0;
    let high = prices[0], low = prices[0];
    while(idx < prices.length -1){
        while(idx < prices.length -1 && prices[idx] >= prices[idx +1]){
            idx ++;
        }
        low = prices[idx];
        while(idx < prices.length -1 && prices[idx] <= prices[idx +1]){
            idx ++;
        }
        high = prices[idx];
        result += (high - low);
    }
    return result;
};

** 하락점에서 구매, 상승점에서 판매를 반복한다.

 

 

 

4. 결과

 

201 / 201 test cases passed.
Status: Accepted
Runtime: 112 ms
Memory Usage: 35.3 MB

 

 

 

 

 

+ Recent posts