记录

1015 3. Reverse Vowels of a String

/**
* @param {string} s
* @return {string}
*/
var reverseVowels = function(s) {
    if (s == null || s.length < 2) {return s;}
    const set = new Set(['a', 'e', 'i', 'o', 'u']);
    const isVowel = c => set.has(c.toLowerCase());
    let i = 0;
    let j = s.length - 1;
    s = s.split(''); // !!!!! string is immutable. Though the operator looks the same, simply swapping string chars won't work!!! We need to convert it to array!!!!
    while (i < j) {
        if (isVowel(s[i]) && isVowel(s[j])) {
            ;[s[i], s[j]] = [s[j], s[i]];
            
            i++;
            j--;
        } else {
            if (!isVowel(s[i])) {
                i++
            }
            if (!isVowel(s[j])) {
                j--;
            }
        }
    }
    return s.join('');
};

1015 4. Longest Increasing Subsequence

/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function(nums) {
    // [10, 9, 2, 5, 3, 7, 101, 18]
    if (nums == null || nums.length === 0) {return 0;}
    const dp = Array(nums.length).fill(1);
    for (let i = 1; i < nums.length; i++) {
        const num = nums[i];
        for (let j = 0; j < i; j++) {
            if (nums[j] < num) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    // !!!! you need to rethink the meaning of dp[i]
    // it means the length of lis that ends with the ith num, not the length of lis till the ith num
    // so you still need to iterate all again
    return Math.max(...dp);
};

sicilianee 发表于 2017-10-16 12:36
1015 4. Longest Increasing Subsequence

/**

An even better solution: insert into an increasing sequence. We've seen this pattern before but forgot which problem.
It is a tricky solution, need to spend more time to understand it.
We only need the max length, and we don't care about the actual sequence. That is a good thing we can make use of it. Insert/replace current element to the existing increasing sequence, and this will not change the max length.

1016 1. Swap Nodes in Pairs
/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var swapPairs = function(head) {
    // 1 2 3 4
    if (head == null) {return head;}
    const dummy = new ListNode(0);
    dummy.next = head; // !!!!! need to set up the connection between dummy and head !!!!
    let prev = dummy;
    while (prev.next != null && prev.next.next != null) {
        const curr = prev.next;
        const next = curr.next;
        const nextNext = next.next;
        curr.next = nextNext;
        prev.next = next;
        next.next = curr;
        prev = prev.next.next;
    }
    return dummy.next;
};

1016 2. Valid Perfect Square

/**
* @param {number} num
* @return {boolean}
*/
var isPerfectSquare = function(num) {
    let left = 1;
    let right = num;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const sq = mid * mid;
        if (sq === num) {
            return true;
        } else if (sq < num) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
};

sicilianee 发表于 2017-10-16 12:58
1016 2. Valid Perfect Square

/**

Check other solutions: http://www.cnblogs.com/grandyang/p/5619296.html

1016 3. Sort Colors

/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var sortColors = function(nums) {
    if (nums == null || nums.length < 2) {return;}  // !!!! you returned here !!!
    let left = 0;
    let i = 0;
    let right = nums.length - 1;
    console.log(nums)
    while (i <= right) {
        if (nums[i] === 0) { // !!!! nums[i], not i !!!1
            swap(nums, i, left);
            left++;
            while (i < left) {i++;}
        } else if (nums[i] === 2) {
            swap(nums, i, right);
            right--;
        } else {
            i++;
        }
    }
    console.log(nums);
};

function swap (nums, i, j) {
    ;[nums[i], nums[j]] = [nums[j], nums[i]];
}

1016 4.  24 Game

/**
* @param {number[]} nums
* @return {boolean}
*/
var judgePoint24 = function(nums) {
    // 1 2 3 4
    // get first two
    // combine first two to form another
    // another and rest two, recurse
    if (nums.length === 1) {return Math.abs(nums[0] - 24) < 1e-6} // !!!! Using EPSILON gives the wrong answer, too small.
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < nums.length; j++) {
            if (i !== j) {
                const rest = nums.filter((num, index) => index !== i && index !== j);
                for (let k = 0; k < 4; k++) {
                    if (j < i && (k === 0 || k === 2)) {continue;}
                    if (nums[j] === 0 && k === 3) {continue;}
                    const newNum = calc(k, nums, nums[j]);
                    rest.push(newNum);
                    if (judgePoint24(rest)) {return true;}
                    rest.pop();
                }
            }
        }
    }
    return false;
};

function calc (operCode, a, b) {
    switch (operCode) {
        case 0:
            return a + b;
        case 1:
            return a - b;
        case 2:
            return a * b;
        case 3:
            return a / b;
        default:
            throw new Error('Invalid input');
    }
}
How to better handle floating point arithmetic? Precision loss?

1017 1.  Maximum Swap

/**
* @param {number} num
* @return {number}
*/
var maximumSwap = function(num) {
    const list = [];
    const original = num; // !!! num changed!!! and you want to return it !!! Better not change it
    while (num !== 0) {
        const digit = num % 10;
        list.unshift(digit);
        num = Math.floor(num / 10); // !!!!! it is javascript !!!! When you do division!!!
    }
    console.log(list);
    const map = new Map();
    list.forEach((num, index) => {
        map.set(num, index);
    });
    for (let i = 0; i < list.length; i++) {
        const curr = list[i];
        for (let j = 9; j > curr; j--) {
            if (map.has(j) && map.get(j) > i) {
                ;[list[i], list[map.get(j)]] = [list[map.get(j)], list[i]];
                return list.reduce((a, b) => a * 10 + b);
            }
        }
    }
    return original;
};

1017 2. Repeated Substring Pattern

/**
* @param {string} s
* @return {boolean}
*/
var repeatedSubstringPattern = function(s) {
    if (s == null || s.length < 2) {
        return false;
    }
    for (let i = 1; i <= s.length / 2; i++) {
        if (s.length % i !== 0) {continue;}
        const piece = s.slice(0, i);
        const count = Math.floor(s.length / i);
        const fake = piece.repeat(count);
        if (fake === s) {
            return true;
        }
    }
    return false;
};

TODO: understand KMP