记录

1111 4. Sum of Square Numbers

/**
* @param {number} c
* @return {boolean}
*/
var judgeSquareSum = function(c) {
    if (c === 0) {
        return true;
    }
    const set = new Set(); // !!!! use a list is TLE.
    let i = 1;
    while (i * i <= c) {
        if (i * i === c) {
            return true;
        }
        set.add(i * i);
        i++;
    }
    for (let i of set) {
        if (set.has(c - i)) {
            return true;
        }
    }
    return false;
};

Use a list caused TLE. We changed to set.
TODO: checkout the leetcode articles they have better solutions.

1111 5. Repeated String Match

/**
* @param {string} A
* @param {string} B
* @return {number}
*/
var repeatedStringMatch = function(A, B) {
    if (A == null || B == null) {
        return false;
    }
    const aLen = A.length;
    const bLen = B.length;
    const len = aLen + bLen;
    let str = '';
    let count = 0;// !!!! they want the num of repeats, not boolean
    // !!! the first time you violate the condition is ok, but you don't continue the loop after that, how is that expressed?
    // you won't continue when you already exceeds that number, and you should have already visited it. Still seems like a do-while loop
    // update at the start of the loop
    do {
        str += A;
        count++;
        if (str.includes(B)) {
            return count;
        }
    } while (str.length <= aLen + bLen); // !!! <=, this is the condition to continue, wtf
    console.log(str)
    return -1;
};

sicilianee 发表于 2017-11-12 08:06
1111 5. Repeated String Match

/**

1. do while pattern is rarely used. This is a good chance to practice
   - first do it, then check, if condition not met, we don't continue, but the first time condition not met is executed -- this is where we use a do while
   - in a do while, we do loop vars update at the beginning.

2. checkout leetcode articles for the rolling hash solution.

1111 6. Valid Palindrome II

/**
* @param {string} s
* @return {boolean}
*/
var validPalindrome = function(s) {
    if (s == null || s.length === 0) {
        return true;
    }
    let left = 0;
    let right = s.length - 1;
    while (left <= right) {
        if (s[left] != s[right]) {
            return isPalindrome(s.slice(0, left) + s.slice(left + 1)) || isPalindrome(s.slice(0, right) + s.slice(right + 1));
        }
        left++;
        right--;
    }
    return true;
};

function isPalindrome (str) {
    if (str == null || str.length === 0) {
        return true;
    }
    let left = 0;
    let right = str.length - 1;
    while (left <= right) {
        if (str[left] != str[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

sicilianee 发表于 2017-11-12 08:34
1111 6. Valid Palindrome II

/**

理解过程是比较tricky的。可以分两种情况，多出的这一个char和对面的相等/不相等。

1111 7. Longest Common Prefix

/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
    if (strs == null || strs.length === 0) {
        return '';
    }
    const root = {};
    let minLen = Infinity; // !!!! cannot exceed the minLen. If we include this, there is no need to do special check for empty string
    for (let str of strs) {
        minLen = Math.min(str.length, minLen);
        insert(str);
    }
    let node = root;
    let str = '';
    let count = 0;
    while (Object.entries(node).length === 1 && count < minLen) { // !!! count < minLen, no ==. This is interesting. The current count has already been added.
        const entry = Object.entries(node)[0];
        str += entry[0];
        // !!!!! habit: check loop variable !!!!
        node = node[entry[0]];
        count++;
    }
    return str;
   
    function insert (str) {
        let node = root;
        for (let c of str) {
            node[c] = node[c] || {};
            node = node[c];
        }
    }
};


Took me a while to pass oj.

sicilianee 发表于 2017-11-12 08:58
1111 7. Longest Common Prefix

/**

Might start with brute force solution.

1111 8.  Length of Last Word

/**
* @param {string} s
* @return {number}
*/
var lengthOfLastWord = function(s) {
    if (s == null || s.length === 0) {
        return 0;
    }
    const list = s.split(' ').filter(str => str);
    if (list.length === 0) {return 0;}
    return list[list.length - 1].length;
};

1111 9. Intersection of Two Linked Lists

/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/

/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function(headA, headB) {
    const len1 = getLen(headA);
    const len2 = getLen(headB);
    let short;
    let long;
    if (len1 >= len2) {
        short = headB;
        long = headA;
    } else {
        short = headA;
        long = headB;
    }
    const diff = Math.abs(len1 - len2);
    for (let i = 0; i < diff; i++) {
        long = long.next;
    }
    while (short != null) {
        if (short === long) {
            return short;
        }
        short = short.next;
        long = long.next;
    }
    return null;
};

function getLen (node) {
    let count = 0;
    while (node != null) {
        count++;
        node = node.next;
    }
    return count;
}

sicilianee 发表于 2017-11-12 09:13
1111 9. Intersection of Two Linked Lists

/**

Note: short, long, int, native, char, byte, etc are reserved words now. Better avoid them.