记录

sicilianee 发表于 2017-12-10 08:35
1209 3. Wiggle Sort II

/**

不符合题目要求

1209 4.  Encode and Decode Strings

/**
* Encodes a list of strings to a single string.
*
* @param {string[]} strs
* @return {string}
*/
var encode = function(strs) {
    if (strs == null || strs.length === 0) {
        return '';
    }
    return strs.map(str => `${str.length}:${str}`).join('');
};

/**
* Decodes a single string to a list of strings.
*
* @param {string} s
* @return {string[]}
*/
var decode = function(s) {
    if (s == null || s.length === 0) {
        return [];
    }
    const ans = [];
    for (let i = 0; i < s.length; i++) {
        if (s[i] >= '0' && s[i] <= '9') {
            let j = i;
            while (s[j] >= '0' && s[j] <= '9') {
                j++;
            }
            const str = s.slice(i, j);
            const num = Number.parseInt(str, 10);
            const curr = s.slice(j + 1, j + 1 + num);
            ans.push(curr);
            i = j + 1 + num - 1; // !!!! a for loop, you need to -1
        } else {
            throw new Error('invalid format');
        }
    }
    return ans;
};

/**
* Your functions will be called as such:
* decode(encode(strs));
*/

1209 5. Reorder List

/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {void} Do not return anything, modify head in-place instead.
*/
var reorderList = function(head) {
    if (head == null) {return} // !!! don't return
    let slow = head;
    let fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    let first = head;
    let second = slow.next;
    slow.next = null;
    // !!!! need to reverse the second half
    let prev = null;
    let curr = second;
    while (curr != null) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    second = prev;
    const dummy = new ListNode(0);
    prev =dummy; // !!! prev already defined
    let moveFirst = true;
    while (first != null || second != null) {
        if (moveFirst) {
            prev.next = first;
            prev = first;
            first = first.next;
            moveFirst = false;
        } else {
            prev.next = second;
            prev = second;
            second = second.next;
            moveFirst = true;
        }
    }
};

1209 6. Remove K Digits

/**
* @param {string} num
* @param {number} k
* @return {string}
*/
var removeKdigits = function(num, k) {
    if (num == null || num.length === 0) {return '0'}
    let stack = [];
    const keep = num.length - k; // !!!! get keep before you change k
    for (let c of num) {
        while (k > 0 && stack.length > 0 && stack[stack.length - 1] > c) {
            stack.pop();
            k--;
        }
        stack.push(c);
    }
    stack = stack.slice(0, keep); // !!!! if we have more to use, just keep the smallest few
    console.log(k, stack)
    let i;
    for (i = 0; i < stack.length && stack[i] === '0'; i++);
    if (i === stack.length) {
        return '0';
    } else {
        return stack.slice(i).join('');
    }
};

1209 7. Copy List with Random Pointer

/**
* Definition for singly-linked list with a random pointer.
* function RandomListNode(label) {
*     this.label = label;
*     this.next = this.random = null;
* }
*/

/**
* @param {RandomListNode} head
* @return {RandomListNode}
*/
var copyRandomList = function(head) {
    if (head == null) {
        return head;
    }
    const map = new Map();
    let node = head;
    const dummy = new RandomListNode(0);
    let copyPrev = dummy;
    while (node != null) {
        const copyNode = new RandomListNode(node.label);
        map.set(node, copyNode);
        copyPrev.next = copyNode;
        node = node.next; // !!!!! forget to move the node !!!!
        copyPrev = copyNode;
    }
    node = head;
    while (node != null) {
        const copyNode = map.get(node);
        const randomNode = map.get(node.random) || null; // !!! node.random could be null, and you should do null also
        copyNode.random = randomNode;
        node = node.next; // !!! Same here !!!!
    }
    return dummy.next;
};

有比较smart的方法

1209 8. Pow(x, n)

/**
* @param {number} x
* @param {number} n
* @return {number}
*/
var myPow = function(x, n) {
    if (n === 0) {return 1}
    const half = myPow(x, Math.trunc(n / 2));
    if (n % 2 === 0) {
        return half * half;
    } else if (n > 0) {
        return half * half * x;
    } else {
        return half * half / x;
    }
};

1209 9.  Simplify Path

/**
* @param {string} path
* @return {string}
*/
var simplifyPath = function(path) {
    if (path == null || path.length === 0) {
        return path
    }
    const list = path.split('/').filter(str => str);
    const stack = [];
    for (let part of list) {
        if (part === '.') {
            continue;
        } else if (part === '..') {
            // !!!! could be empty: /../
            if (stack.length > 0) {
                stack.pop();
            }
        } else {
            stack.push(part);
        }
    }
    return '/' + stack.join('/');
};

1209 10. Design Twitter

/**
* Initialize your data structure here.
*/
var Twitter = function() {
    this.users = new Map();
};

let counter = 0;

class User {
    constructor (id) {
        this.id = id;
        this.followees = new Set([id]);
        this.tweets = [];
    }
}

class Tweet {
    constructor (id) {
        this.id = id;
        this.time = counter++; // !!! could be within the same second !!!
    }
}

/**
* Compose a new tweet.
* @param {number} userId
* @param {number} tweetId
* @return {void}
*/
Twitter.prototype.postTweet = function(userId, tweetId) {
    const user = this.users.get(userId) || new User(userId);
    this.users.set(userId, user);
    user.tweets.unshift(new Tweet(tweetId)); // !!! because later we start from index 0 to retrieve the latest
};

/**
* Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
* @param {number} userId
* @return {number[]}
*/
Twitter.prototype.getNewsFeed = function(userId) {
    const user = this.users.get(userId);
    if (user) {
        const lists = [...user.followees].map(followeeId => this.users.get(followeeId).tweets);
        const feeds = [];
        const indices = Array(lists.length).fill(0);
        for (let i = 0; i < 10; i++) {
            // get maxTime
            let maxTime = 0;
            for (let j = 0; j < indices.length; j++) {
                const list = lists[j];
                const index = indices[j];
                const tweet = list[index];
                if (tweet && tweet.time > maxTime) {
                    maxTime = tweet.time;
                }
            }
            // update index of maxTime
            for (let j = 0; j < indices.length; j++) {
                const list = lists[j];
                const index = indices[j];
                const tweet = list[index];
                if (tweet && tweet.time === maxTime) {
                    feeds.push(tweet.id);
                    indices[j]++;
                }
            }
        }
        return feeds;
    } else {
        return [];
    }
};

/**
* Follower follows a followee. If the operation is invalid, it should be a no-op.
* @param {number} followerId
* @param {number} followeeId
* @return {void}
*/
Twitter.prototype.follow = function(followerId, followeeId) {
    const follower = this.users.get(followerId) || new User(followerId);
    this.users.set(followerId, follower);
    const followee = this.users.get(followeeId) || new User(followeeId);
    this.users.set(followeeId, followee);
    follower.followees.add(followeeId);
};

/**
* Follower unfollows a followee. If the operation is invalid, it should be a no-op.
* @param {number} followerId
* @param {number} followeeId
* @return {void}
*/
Twitter.prototype.unfollow = function(followerId, followeeId) {
    if (followerId != followeeId && this.users.has(followerId) && this.users.has(followeeId)) { // !!!! cannot unfollow himself
        const follower = this.users.get(followerId);
        follower.followees.delete(followeeId);
    }
};

/**
* Your Twitter object will be instantiated and called as such:
* var obj = Object.create(Twitter).createNew()
* obj.postTweet(userId,tweetId)
* var param_2 = obj.getNewsFeed(userId)
* obj.follow(followerId,followeeId)
* obj.unfollow(followerId,followeeId)
*/

const t = new Twitter();
t.postTweet(1, 5)
t.getNewsFeed(1)


有一个更好的办法，用linkedlist装tweets， 用heap 来找10个

1029 11. Can I Win

/**
* @param {number} maxChoosableInteger
* @param {number} desiredTotal
* @return {boolean}
*/
var canIWin = function(maxChoosableInteger, desiredTotal) {
    if (maxChoosableInteger > desiredTotal) {return true}
    let sum = 0;
    for (let i = 1; i <= maxChoosableInteger; i++) {
        sum += i;
    }
    if (sum < desiredTotal) {return false;}
    // valid input
    const used = Array(maxChoosableInteger + 1).fill(false);
    const map = new Map();
    return canWin(desiredTotal);
   
    function canWin (total) {
        if (total <= 0) {
            return false;
        }
        const key = getKey(used);
        if (map.has(key)) {
            return map.get(key);
        }
        // for remaining numbers, we try each of them to see if we can win
        for (let i = 1; i < used.length; i++) { // !!!! start from 1, not 0 !!!! Why adding 0 is wrong? You cannot take nothing at one step
            if (!used[i]) {
                used[i] = true;
                if (!canWin(total - i)) {
                    // other one can't win, I can win
                    map.set(key, true);
                    used[i] = false;
                    return true;
                }
                used[i] = false;
            }
        }
        map.set(key, false);
        return false;
    }
           
   
    function getKey (used) {
        return used.join('');
    }
};

1029 12. Longest Palindromic Substring

/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
    if (s == null || s.length < 2) {
        return s;
    }
    // const len = s.length;
    // const dp = Array(len).fill().map(() => Array(len).fill(false));
    // let max = '';
    // for (let range = 1; range <= len; range++) {
    //     for (let i = 0; i + range - 1 < len; i++) {
    //         const j = i + range - 1;
    //         if (range === 1) {
    //             dp[i][j] = true;
    //         } else if (range === 2) {
    //             dp[i][j] = s[i] === s[j];
    //         } else {
    //             dp[i][j] = s[i] === s[j] && dp[i + 1][j - 1];
    //         }
    //         if (dp[i][j]) {
    //             max = s.slice(i, j + 1);
    //         }
    //     }
    // }
    // return max;
    let max = '';
    const extend = (left ,right) => {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            if (right - left + 1 > max.length) {
                max = s.slice(left, right + 1);
            }
            left--;
            right++;
        }
    }
    for (let i = 0; i < s.length; i++) {
        extend(i, i);
        extend(i, i + 1);
    }
    return max;
    // 感觉时间复杂度和dp是一样的呀，为什么这样就可以过，dp就不能过呢？
};

为何dp不能过呢？