Patrick Ragi (pipo1991)

LeetCode - 31 - Next Permutation

2023-08-06T02:38:00.004-07:00

/**

 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(nums) {
  var i = nums.length - 2;
  while (i > -1) {
    if (nums[i] < nums[i+1]) {
      break;
    }
    i--;
  }

  if (i > -1) {
    var nextMin = {
      index : i,
      value: 101
    };

    for (var j = nums.length - 1; j > i ; j--) {
      if (nums[j] > nums[i] && ((nums[j] - nums[i]) < nextMin.value)) {
        nextMin.value = nums[j] - nums[i];
        nextMin.index = j;
      }
    }

    swapInArr(nums, i, nextMin.index);
  }

  reverseSubArray(nums, i + 1, nums.length - 1);
};

function swapInArr(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

function reverseSubArray(arr, start , end) {
  while(start < end) {
    swapInArr(arr, start, end);
    start++;
    end--;
  }
}

LeetCode - 30 - Substring with Concatenation of All Words

2023-08-06T01:23:00.001-07:00

/**

 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
    var hash = {};
    var wordLength = words[0].length;
    var wordsTotal = wordLength * words.length;
    for (const word of words) {
        if (hash[word]) {
            hash[word]++;
        } else {
            hash[word] = 1;
        }
    }

    var slidingWindow = [];
    var sol = [];
    for(var i = 0; i < s.length ; i++) {
        if (slidingWindow.length < wordsTotal - 1) {
            slidingWindow.push(s[i]);
        } else {
            slidingWindow.push(s[i]);
            if (isPermutationOfWords(slidingWindow.join(''), Object.assign({}, hash), wordLength)) {
                sol.push(i - wordsTotal + 1);
            }
            slidingWindow.shift();
        }
    }
    return sol;
};

function isPermutationOfWords(s, words, wordLength) {
    var str = "";
    for(var i = 0; i < s.length; i++) {
        str += s[i];
        if (str.length == wordLength) {
            if (words[str]) {
                words[str]--;
                str = "";
            } else {
                return false;
            }
        }
    }
    return true;
}

LeetCode - 29 - Divide Two Integers

2023-08-03T12:47:00.002-07:00

class Solution {

    public int divide(int dividend, int divisor) {
        boolean isNeg = (dividend < 0) != (divisor < 0);
        long absDividend = Math.abs(new Long(dividend));
        long absDivisor = Math.abs(new Long(divisor));
        long sum = 0;
        while (absDivisor <= absDividend) {
            int counter = 0;
            long temp = absDivisor;
            while ((temp << 1) < absDividend) {
                temp = temp << 1;
                counter++;
            }
            sum += 1 << counter;
            absDividend -= temp;
        }
        
        if (isNeg) {
            if (-sum < Integer.MIN_VALUE) {
                return Integer.MIN_VALUE;
            }
            return (int) -sum ;
        }
        if (sum > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
        return (int)sum;
    }
}

LeetCode - 28 - Find the Index of the First Occurrence in a String

2023-08-03T11:11:00.000-07:00

/**

 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    var start = "";
    for (var i = 0; i < needle.length - 1 ; i++) {
        start += haystack[i];
    }
    for (var i = needle.length - 1 ; i < haystack.length ; i++) {
        start += haystack[i];
        if (start == needle) {
            return i - needle.length + 1;
        }
        start = start.slice(1);
    }
    return -1;
};

LeetCode - 27 - Remove Element

2023-08-02T13:27:00.002-07:00

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    var index = 0;
    for (const num of nums) {
        if (num != val) {
            nums[index] = num;
            index++;
        }
    }
    return index;
};

LeetCode - 26 - Remove Duplicates from Sorted Array

2023-08-02T13:25:00.001-07:00

/**

 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    var index = 0;
    var last = 200;
    for(const num of nums) {
        if (num != last) {
            nums[index] = num;
            index++;
        }
        last = num;
    }
    return index;
};

LeetCode - 25 - Reverse Nodes in k-Group

2023-08-02T13:10:00.003-07:00

/**

 * 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} k
 * @return {ListNode}
 */
var reverseKGroup = function(head, k) {
    if (head == null) {
        return head;
    }
    var pointer = head;
    var stack = [];
    while (pointer != null && stack.length < k ) {
        var temp = pointer;
        pointer = pointer.next;
        temp.next = null;
        stack.push(temp);
    }
    if (stack.length < k) {
        var stack2 = [];
        while (stack.length > 0) {
            stack2.push(stack.pop());
        }
        stack = stack2;
    }
    var nextElements = reverseKGroup(pointer, k);
    var newHead = stack.pop();
    var pointer2 = newHead;
    while (stack.length > 0) {
        pointer2.next = stack.pop();
        pointer2 = pointer2.next;
    }
    pointer2.next = nextElements;
    return newHead;
};

LeetCode - 24 - Swap Nodes in Pairs

2023-08-02T11:44:00.003-07:00

/**
 * 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 {ListNode}
 */
var swapPairs = function(head) {
    if (head == null) {
        return null;
    }
    if (head.next == null) {
        return head;
    }
    var newHead = head.next;
    var nextElements = swapPairs(newHead.next);
    head.next = nextElements;
    newHead.next = head;
    return newHead;
};

LeetCode - 23 - Merge k Sorted Lists

2023-08-02T11:10:00.004-07:00

/**

 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    var n = lists.length;
    if (n == 0) {
        return null;
    }
    if (n == 1) {
        return lists[0];
    }
    var newLists = [];
    for (var i = 0; i < n - 1 ; i += 2) {
        newLists.push(mergeTwoLists(lists[i], lists[i+1]));
    }
    if (lists.length % 2 == 1) {
        newLists.push(lists[n-1]);
    }
    return mergeKLists(newLists);
};

function mergeTwoLists(list1, list2) {
    var mergedList = new ListNode(null, null);
    var pointer1 = list1, pointer2 = list2, pointer3 = mergedList;
    while (pointer1 !== null && pointer2 !== null) {
        var value;
        if (pointer1.val < pointer2.val) {
            value = pointer1.val;
            pointer1 = pointer1.next;
        } else {
            value = pointer2.val;
            pointer2 = pointer2.next;
        }
        pointer3.next = new ListNode(value, null);
        pointer3 = pointer3.next;
    }
    while (pointer1 !== null) {
        pointer3.next = new ListNode(pointer1.val, null);
        pointer3 = pointer3.next;
        pointer1 = pointer1.next;
    }
    while (pointer2 !== null) {
        pointer3.next = new ListNode(pointer2.val, null);
        pointer3 = pointer3.next;
        pointer2 = pointer2.next;
    }
    return mergedList.next;
};

LeetCode - 22 - Generate Parentheses

2023-08-02T10:54:00.002-07:00

/**

 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    var output = [];
    getAllParenthis(n, n, "", output);
    return output;
};

function getAllParenthesis(opening, closing, comb, output) {
    if (opening == 0 && closing == 0) {
        output.push(comb);
        return
    }
    if (opening < closing) {
        getAllParenthesis(opening, closing -1, comb + ")", output);
    }
    if (opening > 0) {
        getAllParenthesis(opening - 1, closing, comb + "(", output);
    }
}

LeetCode - 21 - Merge Two Sorted Lists

2023-08-02T10:34:00.001-07:00

/**

 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(list1, list2) {
    var mergedList = new ListNode(null, null);
    var pointer1 = list1, pointer2 = list2, pointer3 = mergedList;
    while (pointer1 !== null && pointer2 !== null) {
        var value;
        if (pointer1.val < pointer2.val) {
            value = pointer1.val;
            pointer1 = pointer1.next;
        } else {
            value = pointer2.val;
            pointer2 = pointer2.next;
        }
        pointer3.next = new ListNode(value, null);
        pointer3 = pointer3.next;
    }
    while (pointer1 !== null) {
        pointer3.next = new ListNode(pointer1.val, null);
        pointer3 = pointer3.next;
        pointer1 = pointer1.next;
    }
    while (pointer2 !== null) {
        pointer3.next = new ListNode(pointer2.val, null);
        pointer3 = pointer3.next;
        pointer2 = pointer2.next;
    }
    return mergedList.next;
};

LeetCode - 20 - Valid Parentheses

2023-08-01T08:22:00.001-07:00

/**

 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    var stack = [];
    for (var c of s) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.length == 0) {
                return false;
            }
            var currentStack = stack.pop();
            if (currentStack == '(' && c != ')') {
                return false;
            } else if (currentStack == '[' && c != ']') {
                return false;
            } else if (currentStack == '{' && c != '}') {
                return false;
            }
        }
    }
    if (stack.length > 0) {
        return false;
    }
    return true;
};