Algorithm - LeetCode Problems 1

Problem 1436. Destination City

• You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBi. Return the destination city, that is, the city without any path outgoing to another city.

• It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.

Examples

• Example 1:

  • Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
  • Output: "Sao Paulo"
  • Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

• Example 2:

  • Input: paths = [["B","C"],["D","B"],["C","A"]]
  • Output: "A"
  • Explanation: All possible trips are:
    "D" -> "B" -> "C" -> "A".
    "B" -> "C" -> "A".
    "C" -> "A".
    "A". Clearly the destination city is "A".

Solution

• graph의 adjacencyList와 전체 도시의 Set을 사용한 풀이

/**
 * @param {string[][]} paths
 * @return {string}
 */
var destCity = function(paths) {
    const graph = [];
    const citySet = new Set();
    paths.forEach(([start, end]) => {
        citySet.add(start);
        citySet.add(end);
        if (graph[start]) {
            graph[start].push(end);
        } else {
            graph[start] = [end];
        }
    });
    const startCityArr = [...Object.keys(graph)];
    for (const city of citySet.values()) {
        if (!startCityArr.includes(city)) {
            return city;
        }
    }
};

• 출발지 도시 Set와 도착지 도시 Set를 사용한 풀이

/**
 * @param {string[][]} paths
 * @return {string}
 */
var destCity = function(paths) {
    const startCities = new Set();
    const endCities = new Set();
    paths.forEach(([start, end]) => {
        startCities.add(start);
        endCities.add(end);
    });

    endCities.forEach((endCity) => {
        if (startCities.has(endCity)) {
            endCities.delete(endCity);
        }
    });
    return endCities.values().next().value;
};

Problem 1475. Final Prices With a Special Discount in a Shop

• You are given an integer array prices where prices[i] is the price of the ith item in a shop.

• There is a special discount for items in the shop. If you buy the ith item, then you will receive a discount equivalent to prices[j] where j is the minimum index such that j > i and prices[j] <= prices[i]. Otherwise, you will not receive any discount at all.

• Return an integer array answer where answer[i] is the final price you will pay for the ith item of the shop, considering the special discount.

Examples

• Example 1:

  • Input: prices = [8,4,6,2,3]
  • Output: [4,2,4,2,3]
  • Explanation:
    • For item 0 with price[0]=8 you will receive a discount equivalent to prices[1]=4, therefore, the final price you will pay is 8 - 4 = 4.
    • For item 1 with price[1]=4 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 4 - 2 = 2.
    • For item 2 with price[2]=6 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 6 - 2 = 4.
    • For items 3 and 4 you will not receive any discount at all.

• Example 2:

  • Input: prices = [1,2,3,4,5]
  • Output: [1,2,3,4,5]
  • Explanation:
    • In this case, for all items, you will not receive any discount at all.

Constraints

• 1 <= prices.length <= 500
• 1 <= prices[i] <= 1000

Solution

/**
 * @param {number[]} prices
 * @return {number[]}
 */
var finalPrices = function(prices) {
    return prices.map((price, index) => {
        let discountedPrice = 0;
        for (let i = index + 1; i < prices.length; i++) {
            const nextPrice = prices[i];
            if (price >= nextPrice) {
                discountedPrice = nextPrice;
                break;
            }
        }
        return discountedPrice ? price - discountedPrice : price;
    });
};

2024. Maximize the Confusion of an Exam

• A teacher is writing a test with ntrue/false questions, with 'T' denoting true and 'F' denoting false. He wants to confuse the students by maximizing the number of consecutive questions with the same answer (multiple trues or multiple falses in a row).

• You are given a string answerKey, where answerKey[i] is the original answer to the ith question. In addition, you are given an integer k, the maximum number of times you may perform the following operation:

  • Change the answer key for any question to 'T' or 'F' (i.e., set answerKey[i] to 'T' or 'F').

• Return the maximum number of consecutive 'T's or 'F's in the answer key after performing the operation at most k times.

Examples

• Example 1:

  • Input: answerKey = "TTFF", k = 2
  • Output: 4
  • Explanation:
    • We can replace both the 'F's with 'T's to make answerKey = "TTTT".
    • There are four consecutive 'T's.

• Example 2:

  • Input: answerKey = "TFFT", k = 1
  • Output: 3
  • Explanation:
    • We can replace the first 'T' with an 'F' to make answerKey = "FFFT".
    • Alternatively, we can replace the second 'T' with an 'F' to make answerKey = "TFFF".
    • In both cases, there are three consecutive 'F's.

Constaints

• n == answerKey.length
• 1 <= n <= 5 * 10^4
• answerKey[i] is either 'T' or 'F'
• 1 <= k <= n

Solution

• window sliding 다른 사람 풀이 참고

/**
 * @param {string} answerKey
 * @param {number} k
 * @return {number}
 */
var maxConsecutiveAnswers = function(answerKey, k) {
    let maxLength = 0;
    let left = 0;
    let right = answerKey.length;
    let TCount = 0;
    let FCount = 0;
    let start = 0;

    while (left < right) {
        if (answerKey[left] === 'T') {
            TCount++;
        } else {
            FCount++;
        }

        if (TCount <= k || FCount <= k) {
            maxLength = Math.max(maxLength, TCount + FCount);
        }

        while (TCount > k && FCount > k) {
            if (answerKey[start] === 'T') {
                TCount--;
            } else {
                FCount--;
            }
            start++;
        }
        left++;
    }
    return maxLength;
};

Problem 1347. Minimum Number of Steps to Make Two Strings Anagram

• You are given two strings of the same length s and t. In one step you can choose any character of t and replace it with another character.

• Return the minimum number of steps to make t an anagram of s.

• An Anagram of a string is a string that contains the same characters with a different (or the same) ordering.

Examples

• Example 1:

  • Input: s = "bab", t = "aba"
  • Output: 1
  • Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s.

• Example 2:

  • Input: s = "leetcode", t = "practice"
  • Output: 5
  • Explanation: Replace 'p', 'r', 'a', 'i' and 'c' from t with proper characters to make t anagram of s.

Constraints

• 1 <= s.length <= 5 * 10^4
• s.length == t.length
• s and t consist of lowercase English letters only.

Solution

/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var minSteps = function(s, t) {
    const strSMap = new Map();
    let answer = 0;

    for (let i = 0; i < s.length; i++) {
        const str = s[i];
        strSMap.set(str, (strSMap.get(str) || 0) + 1);
    }
    
    for (let j = 0; j < t.length; j++) {
        const str = t[j];
        const strCount = strSMap.get(str);
        if (strCount) {
            strSMap.set(str, strCount - 1);
        }
    }

    strSMap.forEach((value) => answer += value);
    return answer;
};