Algorithm - LeetCode Problems 15

Problem 345. Reverse Vowels of a String

• Given a string s, reverse only all the vowels in the string and return it.

• The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.

Examples

• Example 1:

  • Input: s = "hello"
  • Output: "holle"

• Example 2:

  • Input: s = "leetcode"
  • Output: "leotcede"

Constraints

• 1 <= s.length <= 3 * 10^5
• s consist of printable ASCII characters.

Solution

/**
 * @param {string} s
 * @return {string}
 */
var reverseVowels = function(s) {
    let left = 0;
    let right = s.length - 1;
    let strArr = s.split('');
    let vowelArr = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'];

    while (left < right) {
        if (vowelArr.includes(strArr[left]) && vowelArr.includes(strArr[right])) {
            [strArr[left], strArr[right]] = [strArr[right], strArr[left]];
            left++;
            right--;
        }
        if (!vowelArr.includes(strArr[left])) {
            left++;
        }
        if (!vowelArr.includes(strArr[right])) {
            right--;
        }
    }

    return strArr.join('');
};

Problem 279. Perfect Squares

• Given an integer n, return the least number of perfect square numbers that sum to n.

• A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Examples

• Example 1:

  • Input: n = 12
  • Output: 3
  • Explanation: 12 = 4 + 4 + 4.

• Example 2:

  • Input: n = 13
  • Output: 2
  • Explanation: 13 = 4 + 9.

Constraints

• 1 <= n <= 10^4

Solution

• 다른 사람 풀이 참고(Python/JS/Java/C++ by DP // Coin change [+ Demo & Visualization])

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
    const dp = [0];

    for (let i = 1; i <= n; i++) {
        dp[i] = Infinity;
        for (let j = 1; j*j <= i; j++) {
            dp[i] = Math.min(dp[i], dp[i - j*j] + 1);
        }
    }

    return dp[n];
};

Problem 203. Remove Linked List Elements

• Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

Examples

• Example 1:
  • Input: head = [1,2,6,3,4,5,6], val = 6
  • Output: [1,2,3,4,5]

• Example 2:

  • Input: head = [], val = 1
  • Output: []

• Example 3:

  • Input: head = [7,7,7,7], val = 7
  • Output: []

• Constraints:
• The number of nodes in the list is in the range [0, 10^4].
• 1 <= Node.val <= 50
• 0 <= val <= 50

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    const node  = new ListNode(0);
    node.next = head;
    let curr = node;

    while (curr.next) {
        if (curr.next.val === val) {
            curr.next = curr.next.next;
        } else {
            curr = curr.next;
        }
    }

    return node.next;
};