LeetCode Questions - Medium

const DICTIONARY: string = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

const URL_PREFIX: string = "http://tiny.url/";

const CODE_0: number = "0".charCodeAt(0);
const CODE_9: number = "9".charCodeAt(0);
const CODE_LOWER_A: number = "a".charCodeAt(0);
const CODE_LOWER_Z: number = "z".charCodeAt(0);
const CODE_UPPER_A: number = "A".charCodeAt(0);
const CODE_UPPER_Z: number = "Z".charCodeAt(0);

class URLService {
    private _stol: Map<number, string>;
    private _counter: number;

    constructor() {
        this._stol = new Map<number, string>();
        this._counter = 1;
    }

    public longToShort(url: string): string {
        let shorturl = URLService.base10ToBase62(this._counter);
        this._stol.set(this._counter, url);
        this._counter++;
        return URL_PREFIX + shorturl;
    }

    public shortToLong(url: string): string {
        let urlParam: string = url.substring(URL_PREFIX.length);
        let n: number = URLService.base62ToBase10(urlParam);
        return this._stol.get(n);
    }

    public static convert(charCode: number): number {
        if (charCode >= CODE_0 && charCode <= CODE_9) {
            return charCode - CODE_0;
        } else if (charCode >= CODE_LOWER_A && charCode <= CODE_LOWER_Z) {
            return charCode - CODE_LOWER_A + 10;
        } else if (charCode >= CODE_UPPER_A && charCode <= CODE_UPPER_Z) {
            return charCode - CODE_UPPER_A + 36;
        } else {
            return -1;
        }
    }

    public static base62ToBase10(s: string): number {
        let n: number = 0;
        for (let i: number = 0; i < s.length; i++) {
            n = n * 62 + URLService.convert(s.charCodeAt(i));
        }
        return n;
    }

    public static base10ToBase62(n: number): string {
        let s: string = "";
        while (n !== 0) {
            let r: number = n % 62;
            n = (n - r) / 62;
            s = DICTIONARY[r] + s;
        }
        while (s.length < 6) {
            s = "0" + s;
        }
        return s;
    }
}

function exec() {
    const service: URLService = new URLService();
    let result: string = service.shortToLong(service.longToShort("http://trsong.github.io/"));

    let div: HTMLElement = document.createElement("div");
    div.innerText = result;
    document.body.appendChild(div);
}

exec();

const INT_MAX: number = 2147483647;
const INT_MIN: number = -2147483648;

function atoi(str: string): number {
    let index: number = 0, sign: number = 1, total: number = 0;
    
    // 1. Empty string
    if (!str || str.length === 0) return 0;
    
    // 2. Remove whitespace
    while(index < str.length && str[index] === ' ') index++;
    
    // 3. Handle signs
    while (index < str.length && (str[index] === '+' || str[index] === '-')) {
        sign = str[index] === '+' ? sign : -sign;
        index++;
    }
    
    // 4. Convert number and avoid overflow
    while (index < str.length) {
        let digit: number = str.charCodeAt(index) - "0".charCodeAt(0);
        if (digit < 0 || digit > 9) {
            total = 0;
            break;
        } 
        total = 10 * total + digit;
        index++;
        
        if (total > INT_MAX && sign > 0) return INT_MAX;
        else if (total > -INT_MIN && sign < 0) return INT_MIN;
    }
    return total * sign;
}

function exec() {
    let result: number = atoi("   -+-++-42");

    let div: HTMLElement = document.createElement("div");
    div.innerText = result.toString();
    document.body.appendChild(div);
}

exec();

const CODE_WHITE_SPACE: number = " ".charCodeAt(0);

class Solution {
    public static reverseWords(s: string): string {
        if (!s) return undefined;
        let a: number[] = Array.from({length: s.length}, (_, index: number) => s.charCodeAt(index));
        
        // 1. Reverse the whole string
        Solution.reverse(a, 0, a.length - 1);
        
        // 2. Reverse each word in place
        Solution.reverseEachWordInPlace(a);
        
        // 3. Clean up spaces and return
        return Solution.cleanSpaces(a);
    }
    
    // reverse a[] from a[i] to a[j]
    private static reverse(a: number[], i: number, j: number): void {
        while (i < j) {
            [a[i++], a[j--]] = [a[j], a[i]]
        }
    }
    
    // scan through and reverse each word in place
    private static reverseEachWordInPlace(a: number[]): void {
        let i: number = 0, j: number = 0;
        
        while (i < a.length) {
            while (i < j || i < a.length && a[i] === CODE_WHITE_SPACE) i++; // Skip spaces
            while (j < i || j < a.length && a[j] !== CODE_WHITE_SPACE) j++; // Skip non spaces
            Solution.reverse(a, i, j - 1); // reverse the word
        }
    }
    
    // trim leading, trailling and multiple spaces
    private static cleanSpaces(a: number[]): string {
        let i: number = 0, j: number = 0;
        
        while (j < a.length) {
            while (j < a.length && a[j] === CODE_WHITE_SPACE) j++; // skip spaces
            while (j < a.length && a[j] !== CODE_WHITE_SPACE) a[i++] = a[j++]; // keep non spaces 
            while (j < a.length && a[j] === CODE_WHITE_SPACE) j++; // skip spaces 
            if (j < a.length) a[i++] = CODE_WHITE_SPACE; // keep only one space between consecutive word
        }
        
        return a.slice(0, i).map((code: number) => String.fromCharCode(code)).join('');
    }
}

function exec() {
    let result: string = Solution.reverseWords("     Hello    World !");
    let div: HTMLElement = document.createElement("div");
    div.innerText = result;
    document.body.appendChild(div);
}

exec();

function divide(n: number, d: number): number {
    // Edge case optimization
    if (d == 1) return n;
    
    // Error/Overflow handling
    if (d == 0 || (n == Number.MIN_SAFE_INTEGER && d == -1)) return Number.MAX_SAFE_INTEGER;

    let result: number = 0;
    let n0: number = Math.abs(n);
    let d0: number = Math.abs(d);
    while (n0 >= d0) {
        let a: number = d0;
        let m: number = 1;
        while ((a << 1) < n0) {
            a <<= 1;
            m <<= 1;
        }
        result += m;
        n0 -= a;
    }
    
    if ((n > 0) !== (d > 0)) { // XOR
        result = -result;
    }
    return result;
}

function exec() {
    let result: number = divide(16, 3);

    let div: HTMLElement = document.createElement("div");
    div.innerText = result.toString();
    document.body.appendChild(div);
}

exec();

function fractionToDecimal(numerator: number, denominator: number): string {
    let result: string = "";
    let sign: string = (numerator < 0) !== (denominator < 0) ? "-" : "";
    let n: number = Math.abs(numerator);
    let d: number = Math.abs(denominator);
    
    result += sign;
    
    let remainder: number = n % d;
    if (remainder === 0) {
        result += n / d;
        return result;
    }
    
    result += (n - remainder) / d;
    result += ".";
    
    let remainderPosMap: Map<number, number> = new Map<number, number>();
    while (!remainderPosMap.has(remainder)) {
        remainderPosMap.set(remainder, result.length);
        let nextRemainder: number = remainder * 10 % d;
        result += (remainder * 10 - nextRemainder) / d;
        remainder = nextRemainder;
    } 
    let index: number = remainderPosMap.get(remainder);
    let prifixTerm: string = result.slice(0, index);
    let repeatedTerm: string = result.slice(index);
    
    if (repeatedTerm !== "0") {
        result = `${prifixTerm}(${repeatedTerm})`;
    } else {
        result = prifixTerm;
    }
    
    return result;
}

function exec() {
    let result: string = fractionToDecimal(61, 30);

    let div: HTMLElement = document.createElement("div");
    div.innerText = result;
    document.body.appendChild(div);
}

exec();

function getBucketIndex(value: number, windowSize: number): number {
    return Math.floor(value < 0 ? value / windowSize - 1 : value / windowSize);
}

// Check if exists different indices i, j such that abs(nums[i] - num[j]) <= t and abs(i - j) <= k
function containsNearbyAlmostDuplicate(nums: number[], k: number, t: number): boolean {
    if (k < 1 || t < 0) return false;
    let bucket: Map<number, number> = new Map<number, number>();
    let w: number = t + 1;
    for (let i: number = 0; i < nums.length; i++) {
        let bucketIndex: number = getBucketIndex(nums[i], w);
        if (bucket.has(bucketIndex) ||
        (bucket.has(bucketIndex - 1) && Math.abs(bucket.get(bucketIndex - 1) - nums[i]) < w) ||
        (bucket.has(bucketIndex + 1) && Math.abs(bucket.get(bucketIndex + 1) - nums[i]) < w)) {
            return true;
        }
        
        bucket.set(bucketIndex, nums[i]);
        if (i >= k) bucket.delete(getBucketIndex(nums[i - k], w));
    }
    return false;
}

function exec() {
    let result: boolean = containsNearbyAlmostDuplicate([-1, -5, 7, 3, 9, -3], 2, 2);
    let result2: boolean = containsNearbyAlmostDuplicate([-1, -5, 7, 3, 9, -3], 1, 2);

    let div: HTMLElement = document.createElement("div");
    div.innerText = result.toString();
    div.innerText += " \n " + result2.toString();
    document.body.appendChild(div);
}

exec();

const CODE_LOWER_A: number = "a".charCodeAt(0);

function addNextWords(word: string, wordDict: Set<string>, toVisitQueue: string[]): void {
    wordDict.delete(word);
    let w: number[] = Array.from({ length: word.length }, (_, index: number) => word.charCodeAt(index));
    for (let p: number = 0; p < word.length; p++) {
        let letter: number = word.charCodeAt(p);
        for (let k: number = 0; k < 26; k++) {
            w[p] = CODE_LOWER_A + k;
            let searchString: string = w.map(c => String.fromCharCode(c)).join("");
            if (wordDict.has(searchString)) {
                toVisitQueue.push(searchString);
                wordDict.delete(searchString);
            }
        }
        w[p] = letter;
    }
}

function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
    let dist: number = 2;
    let toVisitQueue: string[] = [];
    let wordDict: Set<string> = new Set<string>(wordList);
    
    wordDict.add(endWord);
    addNextWords(beginWord, wordDict, toVisitQueue);
    
    while (toVisitQueue.length !== 0) {
        let num: number = toVisitQueue.length;
        for (let i: number = 0; i < num; i++) {
            let word: string = toVisitQueue.shift();
            if (word === endWord) return dist;
            addNextWords(word, wordDict, toVisitQueue);
        }
        dist++;
    }
}

function exec() {
    let result: number = ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log"]);

    let div: HTMLElement = document.createElement("div");
    div.innerText = result.toString();
    document.body.appendChild(div);
}

exec();

const CODE_LOWER_A: number = "a".charCodeAt(0);

function ladderLength(beginWord: string, endWord: string, wordList: string[]): number { 
    let wordDict: Set<string> = new Set<string>(wordList);
    let beginSet: Set<string> = new Set<string>();
    let endSet: Set<string> = new Set<string>();
    let visited: Set<string> = new Set<string>();
    
    let len: number = 1;
    beginSet.add(beginWord);
    endSet.add(endWord);
    
    while(beginSet.size !== 0 && endSet.size !== 0) {
        if (beginSet.size > endSet.size) {
            let tmp: Set<string> = beginSet;
            beginSet = endSet;
            endSet = tmp;
        }
        
        let neighbours: Set<string> = new Set<string>();
        for (let word of Array.from(beginSet)) {
            let chs: number[] = Array.from({ length: word.length }, (_, i: number) => word.charCodeAt(i));
            for (let i: number = 0; i < chs.length; i++) {
                for (let c: number = 0; c < 26; c++) {
                    let oldChar: number = chs[i];
                    chs[i] = CODE_LOWER_A + c;
                    let target: string = chs.map((s: number) => String.fromCharCode(s)).join("");

                    if (endSet.has(target)) {
                        return len + 1;
                    }
                    
                    if (!visited.has(target) && wordDict.has(target)) {
                        neighbours.add(target);
                        visited.add(target);
                    }
                    
                    chs[i] = oldChar;
                }
            }
        }

        beginSet = neighbours;
        len++;
    }
    
    return 0;
}

function exec() {
    let result: number = ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log"]);

    let div: HTMLElement = document.createElement("div");
    div.innerText = result.toString();
    document.body.appendChild(div);
}

exec();

function numDecodings(s: string): number {
    if (!s || s.length === 0) return 0;
    
    let dp: number[] = new Array(10).fill(0);    
    dp[0] = 1;
    dp[1] = s[0] !== "0" ? 1 : 0;
    
    for (let i: number = 2; i <= s.length; i++) {
        let one: number = +s.substring(i - 1, i);
        let two: number = +s.substring(i - 2, i);
        if (one >= 1 && one <= 9) {
            dp[i] = dp[i - 1];
        }
        
        if (two >= 10 && two <= 26) {
            dp[i] += dp[i - 2];
        }
    }
    
    return dp[s.length];
}

function exec() {
    let result: number = numDecodings("126");

    let div: HTMLElement = document.createElement("div");
    div.innerText = result.toString();
    document.body.appendChild(div);
}

exec();

function compareTo(s1: number, s2: number): number {
    if (s1 < s2) return -1;
    else if (s1 > s2) return 1;
    else return 0;
}

function compareVersion(version1: string, version2: string): number {
    let levels1: string[] = version1.split('.');
    let levels2: string[] = version2.split('.');
    
    let length: number = Math.max(levels1.length, levels2.length);
    
    for (let i: number = 0; i < length; i++) {
        let v1: number = i < levels1.length ? +levels1[i] : 0;
        let v2: number = i < levels2.length ? +levels2[i] : 0;
        
        let compareResult: number = compareTo(v1, v2);
        if (compareResult !== 0) {
            return compareResult;
        }
    }
    
    return 0;
}

function exec() {
    let result: number = compareVersion("1.10", "1.2");

    let div: HTMLElement = document.createElement("div");
    div.innerText = result.toString();
    document.body.appendChild(div);
}

exec();

function circularArrayLoop(nums: number[]): boolean {
    let n: number = nums.length;
    let arr: number[] = nums.slice();  // Make a copy
    const move = (i: number): number => {
        return i + nums[i] >= 0 ? (i + nums[i]) % n : (i + nums[i]) % n + n; 
    }
        
    for (let i: number = 0; i < n; i++) {
        if (arr[i] === 0) continue; 
        
        // slow / faster pointer
        let slow: number = i, fast: number = i;
        
        // Safe to move the slow pointer once and move the fast pointer twice
        while (arr[slow] * arr[i] > 0 && arr[fast] * arr[i] > 0 && arr[move(fast)] * arr[i] > 0) {
            // Make the move
            slow = move(slow);
            fast = move(move(fast));
            
            if (slow === fast) {  // Encounter each other!
                if (slow === move(slow)) break;  // 1 element loop is not a valid loop
                return true;
            }
        }
        
        // Optimization: Mark element along the path to be 0
        let direction: number = arr[i]; // arr[i] will be set to 0 in first iteration in loop
        slow = i;
        while (direction * arr[slow] > 0) {
            let nextPos: number = move(slow);
            arr[slow] = 0;
            slow = nextPos;
        }
    }
    return false;
}

function exec() {
    let result: boolean = circularArrayLoop([2, -1, 1, 2, 2]);

    let div: HTMLElement = document.createElement("div");
    div.innerText = result.toString();
    document.body.appendChild(div);
}

exec();

class IPAddressProcessor {
	public static validIPAddress(ip: string): string {
		if (IPAddressProcessor.isValidIPv4(ip)) return "IPv4";
		else if (IPAddressProcessor.isValidIPv6(ip)) return "IPv6";
		else return "Neither";
	}
	
	public static isValidIPv4(ip: string): boolean {
		if (ip.length < 7) return false; // edge case: 0.0.0.0
		if (ip[0] === "." || ip[ip.length - 1] === ".") return false; // edge case: .0.10.0.
		let tokens: string[] = ip.split('.');
		if (tokens.length !== 4) return false;
		return tokens.every(IPAddressProcessor.isValidIPv4Token);
	}
	
	public static isValidIPv6(ip: string): boolean {
		if (ip.length < 15) return false; // edge case: 0:0:0:0:0:0:0:0
		if (ip[0] === ":" || ip[ip.length - 1] === ":") return false;
		let tokens: string[] = ip.split(":");
		if (tokens.length !== 8) return false;
		return tokens.every(IPAddressProcessor.isValidIPv6Token);
	}
	
	private static isValidIPv4Token(token: string): boolean {
		if (token.length === 0) return false;
		if (token[0] === "0" && token.length > 1) return false;
		
		try {
			let tokenValue: number = +token;
			if (tokenValue < 0 || tokenValue > 255) return false;
			if (tokenValue === 0 && token[0] !== "0") return false;
		} catch(e) {
			return false;
		}
		return true;
	}
	
	private static isValidIPv6Token(token: string): boolean {
		if (token.length > 4 || token.length === 0) return false;
		const isBase16 = (c: string) => {
			return (c >= "0" && c <= "9") // is digit
				|| (c >= "a" && c <= "f")  // is lower a to f
				|| (c >= "A" && c <= "F");  // is uppper a to f
		};
		
		return Array.from(token).every(isBase16);
	}
}

function exec() {
    let result: string = IPAddressProcessor.validIPAddress("2001:db8:85a3:0:0:8A2E:370:7334");

    let div: HTMLElement = document.createElement("div");
    div.innerText = result;
    document.body.appendChild(div);
}

exec();

class ThreeSumSolution {
    public static threeSum(nums: number[]): [number, number, number][] {
        let sorted: number[] = nums.sort();
        let result: [number, number, number][] = [];
        for (let i: number = 0; i < sorted.length - 2; i++) {
            if (i === 0 || i > 0 && sorted[i] !== sorted[i-1]) { // skip the term that has same value
                ThreeSumSolution.twoSum(sorted, i, result);
            }
        }
        return result;
    }
    
    private static twoSum(sorted: number[], i: number, output: [number, number, number][]): void {
        let lo: number = i + 1, hi: number = sorted.length - 1, sum: number = 0 - sorted[i];
        while (lo < hi) {
            if (sorted[lo] + sorted[hi] === sum) {
                output.push([sorted[i], sorted[lo], sorted[hi]]);
                while (lo < hi && sorted[lo] === sorted[lo + 1]) lo++;
                while (lo < hi && sorted[hi] === sorted[hi - 1]) hi--;
                lo++; hi--;
            } else if (sorted[lo] + sorted[hi] < sum) lo++;
            else hi--;
        }
    }
}

function exec() {
    let result: [number, number, number][] = ThreeSumSolution.threeSum([-1, 0, 1, 2, -1, -4]);

    let div: HTMLElement = document.createElement("div");
    div.innerText = result.toString();
    document.body.appendChild(div);
}

exec();