记录

1119 10 Permutation Sequence

/**
* @param {number} n
* @param {number} k
* @return {string}
*/
var getPermutation = function(n, k) {
    // build the counts dict for each number of nums
    // start from n - 1, for each, k - 1, get how many does it have,
    // index = result + 1, get that num into our res and continue to next cycle
    const counts = Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        counts[i] = counts[i - 1] * i;
    }
    const nums = Array(n).fill().map((v, i) => i + 1);
    let res = '';
    k = k - 1; // once enough
    for (let i = n - 1; i >= 1; i--) {
        // i: how many numbers we are considering
        const index = Math.floor(k / counts[i]); // !!! no need to + 1 cuz array is 0 based, k + 1th element we are looking for its index is k
        const num = nums[index];
        res += `${num}`;
        nums.splice(index, 1);
        // !!!! you didn't f***ing update k !!!!!
        k = k % counts[i];
    }
    res += `${nums[0]}`;
    return res;
};

1119 11. Self Dividing Numbers

/**
* @param {number} left
* @param {number} right
* @return {number[]}
*/
var selfDividingNumbers = function(left, right) {
    const res = [];
    for (let i = left; i <= right; i++) {
        let x = i;
        let good = true;
        // 1. 这一部分要反复练习，怎么样从一个数字中拿出各个位的数
        // 2. 如果允许，我们直接转换成string，取后再转换回来
        while (x > 0) {
            const digit = x % 10;
            x = Math.floor(x / 10);
            if (i % digit !== 0) {
                good = false;
                break;
            }
        }
        if (good) {
            res.push(i);
        }
    }
    return res;
};

1119 12. Find Pivot Index

/**
* @param {number[]} nums
* @return {number}
*/
var pivotIndex = function(nums) {
    if (nums == null || nums.length === 0) {
        return -1;
    }
    const len = nums.length;
    const left = Array(len).fill(0);
    const right = Array(len).fill(0);
    for (let i = 1; i < nums.length; i++) {
        left[i] = left[i - 1] + nums[i - 1];
    }
    for (let i = nums.length - 2; i >= 0; i--) {
        right[i] = right[i + 1] + nums[i + 1];
    }
    for (let i = 0; i < nums.length; i++) {
        if (left[i] === right[i]) {
            return i;
        }
    }
    return -1;
};

1119 13. Maximum Length of Repeated Subarray

/**
* @param {number[]} A
* @param {number[]} B
* @return {number}
*/
var findLength = function(A, B) {
    if (A == null || A.length == 0 || B == null || B.length === 0) {
        return 0;
    }
    const lenA = A.length;
    const lenB = B.length;
    const dp = Array(lenA).fill().map(() => Array(lenB).fill(0));
    let max = 0;
    for (let i = lenA - 1; i >= 0; i--) {
        for (let j = lenB - 1; j >= 0; j--) {
            if (i === lenA - 1 || j === lenB - 1) {
                dp[i][j] = A[i] === B[j] ? 1 : 0;
            } else { // !!!! need the else, otherwise you need to explicitly return
                dp[i][j] = A[i] === B[j] ? dp[i + 1][j + 1] + 1 : 0;
                max = Math.max(dp[i][j], max);
            }

        }
    }
    return max;
};

1119 14. Next Greater Element III

/**
* @param {number} n
* @return {number}
*/
var nextGreaterElement = function(n) {
    // first, convert it into a list
    let x = n;
    const list = [];
    while (x !== 0) {
        const digit = x % 10;
        list.unshift(digit);
        x = Math.floor(x / 10);
    }
    let max = list[list.length - 1];
    let i;
    for (i = list.length - 1; i >= 0; i--) {
        max = Math.max(max, list[i]);
        if (max !== list[i]) {
            break;
        }
    }
    if (i === -1) {
        return -1;
    }
    const curr = list[i];
    const firstHalf = list.slice(0, i);
    const secondHalf = list.slice(i);
    let min = secondHalf[1];
    let index = 1;
    for (let j = 1; j < secondHalf.length; j++) {
        if (secondHalf[j] > curr && secondHalf[j] < min) {
            min = secondHalf[j];
            index = j;
        }
    }
    secondHalf.splice(index, 1);
    secondHalf.sort((a, b) => a - b);
    const str = [...firstHalf, min, ...secondHalf].join('');
    return Number.parseInt(str, 10) > 0x7FFFFFFF ? -1 : Number.parseInt(str, 10);
    // find the smallest that is bigger than curr in the second arr
    // rm that el and put it in the mid, then, sort the second one
    // first, mid, second
    // into str and into num
};

各种错误，看看应该怎么解答

sicilianee 发表于 2017-11-20 14:16
1119 14. Next Greater Element III

/**

思路好像都是类似的。 http://www.cnblogs.com/grandyang/p/6716130.html
但是为啥我写了这么长。

1120 1. Valid Parenthesis String

/**
* @param {string} s
* @return {boolean}
*/
var checkValidString = function(s) {
    // check
    // keep low, high, for (
    // (, ++
    // ), --
    // *, low--, high++
    // low === 0
    if (s == null || s.length === 0) {
        return true;
    }
    let low = 0;
    let high = 0;
    for (let c of s) {
        if (c === '(') {
            low++;
            high++;
        } else if (c === ')') {
            if (low > 0) {
                low--;
            }
            high--;
            if (high < 0) {
                return false;
            }
        } else { // *
            high++;
            if (low > 0) {
                low--;
            }
        }
    }
    return low === 0;
};

1121 1. Majority Element II

/**
* @param {number[]} nums
* @return {number[]}
*/
var majorityElement = function(nums) {
    // check
    // keep count1, count2, num1, num2
    // loop each num, if is num1, count1++, is num2, count2++
    // not 1, 2, if c1 c2 not 0, both --
    // else if c1 is 0, num1 = num, c1 = 1
    // else do same for c2
    // then test if both num1 and num2 is
    if (nums == null || nums.length === 0) {
        return [];
    }
    let n1 = null;
    let n2 = null;
    let count1 = 0;
    let count2 = 0;
    for (let num of nums) {
        if (num === n1) {
            count1++;
        } else if (num === n2) {
            count2++;
        } else if (count1 !== 0 && count2 !== 0) {
            count1--;
            count2--;
        } else {
            if (count1 === 0) {
                n1 = num;
                count1++;
            } else {
                n2 = num;
                count2++;
            }
        }
    }
    count1 = 0;
    count2 = 0;
    for (let num of nums) {
        if (num === n1) {count1++;}
        if (num === n2) {count2++;}
    }
    const res = [];
    const len = nums.length;
    const compareCount = Math.floor(len / 3);
    if (count1 > compareCount) {res.push(n1)} // !!!! you push the number, not its count!!! stupid
    if (count2 > compareCount) {res.push(n2)}
    return res;
   
};

1121 2. 132 Pattern

/**
* @param {number[]} nums
* @return {boolean}
*/
var find132pattern = function(nums) {
    // check
    // we need this: min, max, mid
    // now we keep mid, backwards, keep stack, looking for bigger one
    // found, now we have current stack top as mid, keep updating mid for the biggest mid
    // then go further left to look for the min
    if (nums == null || nums.length < 3) {
        return false;
    }
    let mid = -Infinity;
    let stack = [];
    for (let i = nums.length - 1; i >= 0; i--) {
        if (nums[i] < mid) {
            return true;
        } else while (stack.length > 0 && nums[i] > stack[stack.length - 1]) {
            mid = stack.pop();
        }
        stack.push(nums[i]);
    }
    return false;
};

1121 3. Restore IP Addresses

/**
* @param {string} s
* @return {string[]}
*/
var restoreIpAddresses = function(s) {
    // check
    // recurse, take i, k. k from 4, down to 1, we just take what is remaining, stop there
    // if not stop, we take 1, 2, 3, note if start from 0, can only take one, or you check if is valid
    if (s == null || s.length === 0) {
        return [];
    }
    const list = [];
    const res = [];
    recurse(0, 4);
    return res;
   
    function recurse (i, k) {
        if (k === 1) {
            const remaining = s.slice(i);
            if (isValid(remaining)) {
                list.push(remaining);
                // !!! need to convert it to valid ip, not just push it to res !!!
                res.push(list.join('.'));
                // !!!!!! before you return will need to backtrack !!!! Especially if you return early !!!
                list.pop();
            }
            return;
        }
        for (let j = i + 1; j <= s.length && j <= i + 3; j++) {
            const str = s.slice(i, j);
            if (isValid(str)) {
                list.push(str);
                recurse(j, k - 1);
                list.pop();
            }
        }
    }
   
};

function isValid (str) {
    // !!!! if is a single 0, it is valid
    if (str[0] === '0') {
        return str.length === 1;
    }
    const num = Number.parseInt(str, 10);
    return num >= 0 && num <= 255;
}