Algorithm - LeetCode Problems 16

Problem 2130. Maximum Twin Sum of a Linked List

• In a linked list of size n, where n is even, the ith node (0-indexed) of the linked list is known as the twin of the (n-1-i)th node, if 0 <= i <= (n / 2) - 1.

  • For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.

• The twin sum is defined as the sum of a node and its twin.

• Given the head of a linked list with even length, return the maximum twin sum of the linked list.

Examples

• Example 1
  • Input: head = [5,4,2,1]
  • Output: 6
  • Explanation:
    • Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6.
    • There are no other nodes with twins in the linked list.
    • Thus, the maximum twin sum of the linked list is 6.

• Example 2
  • Input: head = [4,2,2,3]
  • Output: 7
  • Explanation:
    • The nodes with twins present in this linked list are:
    • Node 0 is the twin of node 3 having a twin sum of 4 + 3 = 7.
    • Node 1 is the twin of node 2 having a twin sum of 2 + 2 = 4.
    • Thus, the maximum twin sum of the linked list is max(7, 4) = 7.

Constraints

• The number of nodes in the list is an even integer in the range [2, 10^5].
• 1 <= Node.val <= 10^5

Solution

• array와 for문을 사용한 풀이

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

    while (node) {
        values.push(node.val);
        node = node.next;
    }

    let maxSum = 0;
    const totalValueCount = values.length;

    for (let i = 0; i < totalValueCount / 2; i++) {
        const sum = values[i] + values[totalValueCount - i - 1];
        maxSum = Math.max(maxSum, sum);
    }

    return maxSum;
};

• two pointer를 통해 구한 prev와 reverse linked list를 사용한 풀이 (다른 사람 풀이 참고)

var pairSum = function(head) {
    let node = head;
    let reverse = head;
    let prev = null;
    let temp;

    while (node && node.next) {
        node = node.next.next;
        temp = reverse.next;
        reverse.next = prev;
        prev = reverse;
        reverse = temp;
    }

    let maxSum = 0;

    while (prev) {
        maxSum = Math.max(maxSum, prev.val + reverse.val);
        prev = prev.next;
        reverse = reverse.next;
    }

    return maxSum;
};

Problem 714. Best Time to Buy and Sell Stock with Transaction Fee

• You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.

• Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

• Note:

  • You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
  • The transaction fee is only charged once for each stock purchase and sale.

Examples

• Example 1:

  • Input: prices = [1,3,2,8,4,9], fee = 2
  • Output: 8
  • Explanation: The maximum profit can be achieved by:
    • Buying at prices[0] = 1
    • Selling at prices[3] = 8
    • Buying at prices[4] = 4
    • Selling at prices[5] = 9
    • The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

• Example 2:

  • Input: prices = [1,3,7,5,10,3], fee = 3
  • Output: 6

Constraints

• 1 <= prices.length <= 5 * 10^4
• 1 <= prices[i] < 5 * 10^4
• 0 <= fee < 5 * 10^4

Solution

/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function(prices, fee) {
    let profitSum = 0;
    let buyPrice = prices[0];

    for (let i = 1; i < prices.length; i++) {
        if (prices[i] < buyPrice) {
            buyPrice = prices[i];
        } else if (prices[i] > buyPrice + fee) {
            profitSum += prices[i] - buyPrice - fee;
            buyPrice = prices[i] - fee;
        }
    }
    return profitSum;
};

Problem 1493. Longest Subarray of 1's After Deleting One Element

• Given a binary array nums, you should delete one element from it.

• Return the size of the longest non-empty subarray containing only 1's in the resulting array. Return 0 if there is no such subarray.

Examples

• Example 1:
• Input: nums = [1,1,0,1]
• Output: 3
• Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.

-Example 2:

• Input: nums = [0,1,1,1,0,1,1,0,1]

• Output: 5

• Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

• Example 3:

• Input: nums = [1,1,1]

• Output: 2

• Explanation: You must delete one element.

Constraints

• 1 <= nums.length <= 10^5
• nums[i] is either 0 or 1.

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestSubarray = function(nums) {
    let left = 0;
    let k = 1;
    let maxLength = 0;

    for (let right = 0; right < nums.length; right++) {
        if (nums[right] === 0) {
            k--;
        }

        while (k < 0) {
            if (nums[left] === 0) {
                k++;
            }
            left++;
        }

        maxLength = Math.max(maxLength, right - left);
    }

    return maxLength;
};

Problem 1876. Substrings of Size Three with Distinct Characters

• A string is good if there are no repeated characters.

• Given a string s, return the number of good substrings of length three in s.

• Note that if there are multiple occurrences of the same substring, every occurrence should be counted.

• A substring is a contiguous sequence of characters in a string.

Examples

• Example 1:

  • Input: s = "xyzzaz"
  • Output: 1
  • Explanation:
    • There are 4 substrings of size 3: "xyz", "yzz", "zza", and "zaz".
    • The only good substring of length 3 is "xyz".

• Example 2:

  • Input: s = "aababcabc"
  • Output: 4
  • Explanation:
    • There are 7 substrings of size 3: "aab", "aba", "bab", "abc", "bca", "cab", and "abc".
    • The good substrings are "abc", "bca", "cab", and "abc".

Constraints:

• 1 <= s.length <= 100
• s consists of lowercase English letters.

Solution

• 내가 푼 풀이 (객체, 이중 for 문 사용)

/**
 * @param {string} s
 * @return {number}
 */
var countGoodSubstrings = function(s) {
    let goodSubstrCount = 0;
    for (let i = 0; i < s.length - 2; i++) {
        const obj = {};
        let isGoodSubstr = true;

        for (let j = i; j < i + 3; j++) {
            const letter = s[j];
            if (obj[letter]) {
                isGoodSubstr = false;
                break;
            }
            obj[letter] = 1;
        }

        if (isGoodSubstr) {
            goodSubstrCount++;
        }
    }
    
    return goodSubstrCount;
};

• 다른 사람 풀이 (slice, Set 사용)

var countGoodSubstrings = function(s) {
    let goodSubstrCount = 0;
    for (let i = 0; i < s.length - 2; i++) {
        const substr = s.slice(i, i + 3);
        const set = new Set(substr);
        if (set.size === 3) {
            goodSubstrCount++;
        }
    }
    
    return goodSubstrCount;
};