Algorithm - LeetCode Problems 19

Problem 942. DI String Match

• A permutation perm of n + 1 integers of all the integers in the range [0, n] can be represented as a string s of length n where:
  • s[i] == 'I' if perm[i] < perm[i + 1], and
  • s[i] == 'D' if perm[i] > perm[i + 1].
• Given a string s, reconstruct the permutation perm and return it. If there are multiple valid permutations perm, return any of them.

Examples

• Example 1:

  • Input: s = "IDID"
  • Output: [0,4,1,3,2]

• Example 2:

  • Input: s = "III"
  • Output: [0,1,2,3]

• Example 3:

  • Input: s = "DDI"
  • Output: [3,2,0,1]

Constraints

• 1 <= s.length <= 10^5
• s[i] is either 'I' or 'D'.

Solution

/**
 * @param {string} s
 * @return {number[]}
 */
var diStringMatch = function(s) {
    const answer = [];
    let countI = 0;
    let countD = s.length;

    for (const letter of s) {
        if (letter === 'I') {
            answer.push(countI);
            countI++;
        } else {
            answer.push(countD);
            countD--;
        }
    }

    answer.push(countD);

    return answer;
};

Problem 1758. Minimum Changes To Make Alternating Binary String

• You are given a string s consisting only of the characters '0' and '1'. In one operation, you can change any '0' to '1' or vice versa.

• The string is called alternating if no two adjacent characters are equal. For example, the string "010" is alternating, while the string "0100" is not.

• Return the minimum number of operations needed to make s alternating.

Examples

• Example 1:

• Input: s = "0100"

• Output: 1

• Explanation: If you change the last character to '1', s will be "0101", which is alternating.

• Example 2:

• Input: s = "10"

• Output: 0

• Explanation: s is already alternating.

• Example 3:

• Input: s = "1111"

• Output: 2

• Explanation: You need two operations to reach "0101" or "1010".

Constraints:

• 1 <= s.length <= 10^4
• s[i] is either '0' or '1'.

Solution

/**
 * @param {string} s
 * @return {number}
 */
var minOperations = function(s) {
    const operationStartWith0 = getOperationCount(s, '0');
    const operationStartWith1 = getOperationCount(s, '1');
    return Math.min(operationStartWith0, operationStartWith1);
};

var getOperationCount = (str, flipStr) => {
    let operationCount = 0;

    for (const letter of str) {
        if (letter !== flipStr) {
            operationCount++;
        }
        flipStr = flipStr === '0' ? '1' : '0';
    }

    return operationCount;
}

Problem 94. Binary Tree Inorder Traversal

• Given the root of a binary tree, return the inorder traversal of its nodes' values.

Examples

• Example 1:
  • Input: root = [1,null,2,3]
  • Output: [1,3,2]

• Example 2:

  • Input: root = []
  • Output: []

• Example 3:

  • Input: root = [1]
  • Output: [1]

Constraints

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    const answer = [];
    
    const traverse = (node) => {
        if (!node) {
            return answer;
        }
        
        if (node.left) traverse(node.left);
        answer.push(node.val);
        if (node.right) traverse(node.right);
    };
    
    traverse(root);
    return answer;
};