记录

1102 3. Valid Parentheses

/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
    // !!!!! you will use stack, not just a counter, to process multiple ones
    if (s == null || s.length === 0) {
        return true;
    }
    const stack = [];
    for (let c of s) {
        if (['(', '{', '['].includes(c)) {
            stack.push(c);
        } else {
            if (stack.length === 0) {return false;} // !!! have to guard it !!!
            const ac = stack.pop();
            // !!!!! there is an || you mistake to && , careful about long exps !!!1
            if ((c === '}') && (ac === '{') || (c === ']') && (ac === '[') || c === ')' && ac === '(') {
                // nothing
            } else {
                return false;
            }
        }
    }
    return stack.length === 0;
};

1102 4. Remove Nth Node From End of List

/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function(head, n) {
    if (head == null) {
        return head;
    }
    const dummy = new ListNode(0); // !!!! why? you might be asked to remove the first node from the list
    dummy.next = head;
    let slow = dummy;
    let fast = dummy;
    for (let i = 0; i < n; i++) {
        fast = fast.next;
    }
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
};

Still need the f***ing dummy node !!1

1105 1. Count of Smaller Numbers After Self

/**
* @param {number[]} nums
* @return {number[]}
*/
var countSmaller = function(nums) {
    // check
    // sort and de-duplicate
    // map values to their indice + 1
    // create the dict
    // loop the nums reversely, get mapping value and add it to the tree, and get sum for each one added
    if (nums == null || nums.length === 0) {
        return []; // !!! not empty
    }
    const dict = {};
    const allNums = ([...new Set(nums)]).sort((a, b) => a - b);
    ;allNums.map((value, index) => {
        dict[value] = index + 1;
    });
    const tree = new FenwickTree(allNums.length); // we do + 1 in the tree
    const res = [];
    console.log('to start with');
    console.log(tree.c);
    for (let i = nums.length - 1; i >= 0; i--) {
        const newValue = dict[nums[i]];
        res[i] = tree.sum(newValue - 1); // !!! on the right, not including itself !!!! If value - 1 is 0, it will return 0;
        tree.add(newValue, 1); // !!!! when you add, you also need to specify index !!! The index is the value, and the value is the count 1
    }
    return res;
   
};

// class, no ()
class FenwickTree  {
    constructor (n) {
        this.n = n;
        this.c = Array(n + 1).fill(0); // !!! will need to init  it
    }
    add (x, val) {
        while (x <= this.n) {
            this.c[x] += val;
            x += FenwickTree.lowBit(x);
        }
    }
    sum (x) {
        let res = 0;
        while (x >= 1) { // !!!! Could be 1
            res += this.c[x];
            x -= FenwickTree.lowBit(x);
        }
        return res;
    }
    static lowBit (x) {
        return x & (-x);
    }
}

Need to do it again in one shoot.

1105 2. Minimum Depth of Binary Tree

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var minDepth = function(root) {
    // !!! the problem is that null node doesn't count
    if (root == null) {
        return 0;
    }
    if (root.left == null && root.right == null) {  // note: seems like you don't need this one
        return 1;
    }
    // !!! the key thing is that we cannot enter with a null value
    if (root.left == null) {return minDepth(root.right) + 1}
    if (root.right == null) {return minDepth(root.left) + 1};
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
};

1105 3. Implement Stack using Queues

/**
* Initialize your data structure here.
*/
var MyStack = function() {
    this.mainQ = [];
    this.tmpQ = [];
};

/**
* Push element x onto stack.
* @param {number} x
* @return {void}
*/
MyStack.prototype.push = function(x) {
    while (this.mainQ.length > 0) {  // !!! keep forgetting `this`
        this.tmpQ.push(this.mainQ.shift());
    }
    this.mainQ.push(x);
    while (this.tmpQ.length > 0) {
        this.mainQ.push(this.tmpQ.shift());
    }
};

/**
* Removes the element on top of the stack and returns that element.
* @return {number}
*/
MyStack.prototype.pop = function() {
    return this.mainQ.shift();
};

/**
* Get the top element.
* @return {number}
*/
MyStack.prototype.top = function() {
    return this.mainQ[0];
};

/**
* Returns whether the stack is empty.
* @return {boolean}
*/
MyStack.prototype.empty = function() {
    return this.mainQ.length <= 0   // !!!! test if is empty, not if is not empty, you did too much invalid checking
};

/**
* Your MyStack object will be instantiated and called as such:
* var obj = Object.create(MyStack).createNew()
* obj.push(x)
* var param_2 = obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.empty()
*/

sicilianee 发表于 2017-11-6 02:48
1105 3. Implement Stack using Queues

/**

also check other solutions:

https://leetcode.com/articles/implement-stack-using-queues/

1105 4. Permutations II

/**
* @param {number[]} nums
* @return {number[][]}
*/
var permuteUnique = function(nums) {
    if (nums == null || nums.length === 0) {
        return [];
    }
    const res = [];
    recurse(0);
    return res;
   
    function recurse (start) {
        if (start === nums.length) {   
            res.push([...nums]);
            return;
        }
        for (let i = start; i < nums.length; i++) { // !!! no equal to length, why you do that
            // !!!! could be start itself, becuase we need to give chance to itself !!!
            if (i !== start && noSwap(nums, start, i)) { // !!! but here you need to exclude start since we need it
                continue;
            }
            swap(nums, start, i);
            recurse(start + 1);
            swap(nums, start, i);
        }
    }
};

function noSwap (nums, start, i) {
    for (let k = start; k < i; k++) { // !!!! it is k++> always the same issue. first it is j, then here it is k++ not i++
        if (nums[k] === nums[i]) {
            return true;
        }
    }
    return false; // !!! true and false reversed
}
               

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

1105 5. Rotate Function

/**
* @param {number[]} A
* @return {number}
*/
var maxRotateFunction = function(A) {
    if (A == null || A.length === 0) {
        return 0;
    }
    let value = 0; // !!!!! should init it !!!!!
    const len = A.length;
    for (let i = 0; i < len; i++) {
        value = value + i * A[i];
    }
    console.log(value);
    let max = value;
    const sum = A.reduce((a, b) => a + b);
    for (let i = 1; i < len; i++) {
        value = value + sum - len * A[len - i];
        max = Math.max(value, max);
    }
    return max;
};

1105 6.  Insertion Sort List

/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var insertionSortList = function(head) {
    if (head == null) {
        return head;
    }
    const dummy = new ListNode(0);
    let node = head;
    while (node != null) {
        const next = node.next;
        let prev = dummy;
        while (prev.next != null && prev.next.val <= node.val) {
            prev = prev.next;
        }
        // !!!! these are not inside the inner loop !!!
        const prevNext = prev.next;
        prev.next = node;
        node.next = prevNext;
        node = next;
    }
    return dummy.next;
};

1105 7. H-Index

/**
* @param {number[]} citations
* @return {number}
*/
var hIndex = function(citations) {
    if (citations == null || citations.length === 0) {
        return 0;
    }
    citations.sort((a, b) => b - a); // !!! reverse
    // !!!!
    for (let i = 0; i < citations.length; i++) {
        if (i >= citations[i]) { // !!! has equal? This is important and tricky !!!
            return i;
        }
    }
    return citations.length;
};