记录

sicilianee 发表于 2017-10-31 12:17
1030 3. Find K Closest Elements

/**

http://www.cnblogs.com/grandyang/p/7519466.html
Totally no need for the Binary Search. Just turn this one into another problem.

1030 4. Flatten Binary Tree to Linked List

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {void} Do not return anything, modify root in-place instead.
*/
var flatten = function(root) {
    if (root == null) {return}
    let prev = new TreeNode(0); // !!! dummy!
    recurse(root);
   
    function recurse (node) {
        if (node == null) {return;}
        const left = node.left; // !!! also need to process left
        const right = node.right;
        node.left = null;
        prev.right = node;
        prev = node;
        recurse(left);
        recurse(right);
    }
};

1030 5. Palindrome Number

/**
* @param {number} x
* @return {boolean}
*/
var isPalindrome = function(x) {
    if (x < 0) {return false}
    if (x === 0) {return true}
    let copyX = x;
    let count = 0;
    while (copyX > 0) {
        count++;
        copyX = Math.floor(copyX / 10);
    }
    let small = 1;
    let big = count;
    console.log(big)
    while (big > small) {
        if (getDigit(big) !== getDigit(small)) {
            return false;
        }
        big--;
        small++;
    }
    return true;
   
    function getDigit (i) {
        let val = 1;
        for (let j = 1; j < i; j++) {
            val = val * 10;
        }
        const clean = Math.floor(x / val);
        return clean % 10;  // !!!! not val here
    }
};

sicilianee 发表于 2017-10-31 12:56
1030 5. Palindrome Number

/**

重做。不要额外定义函数。消耗额外的时间。

1030 6. Count and Say

/**
* @param {number} n
* @return {string}
*/
var countAndSay = function(n) {
    // 1211
    let curr = '1';
    for (let i = 1; i < n; i++) { // !!! the first one is already there!
        curr = generateNext(curr);
    }
    return curr;
   
    function generateNext (str) {
        let res = ''
        let count = 1;
        for (let i = 1; i <= str.length; i++) {
            if (i === str.length || str[i] !== str[i - 1]) {
                res += `${count}${str[i - 1]}`;
                count = 1;
            }  else {
                count++;
            }
        }
        return res;
    }
};

1030 7. Peeking Iterator

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
class PeekingIterator implements Iterator<Integer> {
    Iterator<Integer> iterator;
    Integer nextOne;
   
        public PeekingIterator(Iterator<Integer> iterator) {
            // initialize any member here.
            this.iterator = iterator;
        this.nextOne = null;
        }

    // Returns the next element in the iteration without advancing the iterator.
        public Integer peek() {
        if (this.nextOne != null) { // !!!! this check!!!
            return this.nextOne;
        } else {
            if (this.iterator.hasNext()) {
                this.nextOne = this.iterator.next();
                return nextOne;
            } else {
                return null;
            }
        }
        }

        // hasNext() and next() should behave the same as in the Iterator interface.
        // Override them if needed.
        @Override
        public Integer next() {
        if (!this.hasNext()) {
            return null;
        }
            if (this.nextOne != null) {
            Integer nextOne = this.nextOne;
            this.nextOne = null;
            return nextOne;
        } else {
            return this.iterator.next();
        }
        }

        @Override
        public boolean hasNext() {
            if (this.nextOne != null) {
            return true;
        } else {
            return this.iterator.hasNext();
        }
        }
}

1030 8. Matchsticks to Square

/**
* @param {number[]} nums
* @return {boolean}
*/
var makesquare = function(nums) {
    if (nums == null || nums.length < 4) {
        return false;
    }
    const sum = nums.reduce((a, b) => a + b);
    if (sum % 4 !== 0) {
        return false;
    }
    const target = sum / 4;
    const visited = [];
    return recurse(0, 0, 4);
   
    function recurse (start, sum, k) {
        if (k === 1) {return true;}
        if (sum === target) {
            return recurse(0, 0, k - 1);
        }
        for (let i = start; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            if (recurse(i + 1, sum + nums[i], k)) { // !!! here it is still k
                return true;
            }
            visited[i] = false;
        }
        return false;
    }
};

Though I don't like it, still the same idea. Might need to find a better solution. And here the nums are all integers.

1030 9. Find Duplicate Subtrees

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode[]}
*/
var findDuplicateSubtrees = function(root) {
    if (root == null) {
        return [];
    }
    const res = [];
    const dict = {};
    recurse(root);
    return res;
   
    function recurse (node) {
        if (node == null) {return '#'}
        let str = `${node.val}`;
        const left = recurse(node.left);
        const right = recurse(node.right);
        str = str + left + right;
        dict[str] = dict[str] || 0;
        if (dict[str] === 1) {
            res.push(node);
        }
        dict[str]++;
        return str;
    }
};

Very smart.

1030 10. Remove Invalid Parentheses

/**
* @param {string} s
* @return {string[]}
*/
var removeInvalidParentheses = function(s) {
    if (s == null) { // !!! empty str is considered valid
        return [];
    }
    const q = [s];
    const res = []; // !!! will have duplicates, use set !!!!!
    const set = new Set(q);
    let found = false;
    while (q.length > 0) {
        const size = q.length;
        const level = [];
        for (let i = 0; i < size; i++) {
            const str = q.shift();
            if (isValid(str)) {
                found = true;
                res.push(str);
            }
            if (!found) {
                for (let i = 0; i < str.length; i++) {
                    if (str[i] === '(' || str[i] === ')') {
                        const newStr = str.slice(0, i) + str.slice(i + 1);
                        if (!set.has(newStr)) {
                            level.push(newStr);
                            set.add(newStr); // !!!! also need to add to the set. If you don't optimize here, will tle
                        }
                    }
                }
            }
        }
        console.log('if here')
        if (!found) {
            q.push(...level);
        }
    }
    console.log('not here')
    return res;
};

function isValid (str) {
    let leftCount = 0;
    for (let c of str) {
        if (c === '(') {
            leftCount++;
        } else if (c === ')') {
            leftCount--;
            if (leftCount < 0) {return false;}
        }
    }
    return leftCount === 0 // !!! Must be 0 to be valid
}

1031 1.  Linked List Cycle


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

/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
    if (head == null) {return false}
    let slow = fast = head;
    while (slow.next != null && fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            return true;
        }
    }
    return false;
};