记录

1027 1.  Set Matrix Zeroes

/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function(matrix) {
    if (matrix == null || matrix.length === 0) {
        return;
    }
    const firstRow = matrix[0].some(el => el === 0);
    let firstCol = false;
    for (let i = 0; i < matrix.length; i++) {
        if (matrix[i][0] === 0) {firstCol = true;}
    }
    const rowLen = matrix.length;
    const colLen = matrix[0].length;
    for (let i = 0; i < rowLen; i++) {
        for (let j = 0; j < colLen; j++) {
            if (matrix[i][j] === 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }
    // loop first row
    for (let i = 1; i < rowLen; i++) {
        if (matrix[i][0] === 0) {
            for (let j = 1; j < colLen; j++) {
                matrix[i][j] = 0;
            }
        }
    }
    // loop frist col
    for (let j = 1; j < colLen; j++) {
        if (matrix[0][j] === 0) {
            for (let i = 1; i < rowLen; i++) {
                matrix[i][j] = 0;
            }
        }
    }
    if (firstRow) {
        for (let j = 0; j < colLen; j++) {
            matrix[0][j] = 0;
        }
    }
    if (firstCol) {
        for (let i = 0; i < rowLen; i++) {
            matrix[i][0] = 0;
        }
    }
};

1027 2. Group Anagrams

/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function(strs) {
    if (strs == null || strs.length === 0) {
        return [];
    }
    const dict = {};
    for (let str of strs) {
        const key = getKey(str);
        dict[key] = dict[key] || [];
        dict[key].push(str);
    }
    const res = [];
    return Object.values(dict);
};

function getKey (str) {
    const chars = [...str].sort();
    return chars.join('');
}

Their node environment has Object.entries, Object.values.

1027 3. Guess Number Higher or Lower

/* The guess API is defined in the parent class GuessGame.
   @param num, your guess
   @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
      int guess(int num); */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int low = 1;
        int high = n;
        while (low < high) {
            int mid = low + (high - low) / 2;
            int res = guess(mid);
            if (res < 0) {
                high = mid - 1;  // !!!! shit, pay attention to this !!!
            } else if (res > 0) {
                low = mid + 1;  // !!! even you don't include ==, you cannot just use mid, dead loop
            } else {
                return mid;
            }
        }
        return low;
    }
}

这题要多做几遍

1028 1. Wiggle Subsequence


/**
* @param {number[]} nums
* @return {number}
*/
var wiggleMaxLength = function(nums) {
    // !!!! even less than 3, it doesn't directly become wiggle: it could equal!!!
    // !!!! no wonder they say less than 2
    if (nums == null || nums.length < 2) {
        return nums ? nums.length : 0;
    }
    let count = 1;
    let increase = null; // !!!! 1. you cannot just test for i === 1, for [3, 3, 3, 2, 5], the 2 acts like i === 1.
    // !!! so we need a trilean to indicate the first round
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === nums[i - 1]) {
            continue;
        }
        const currIncrease = nums[i] > nums[i - 1];
        if (increase !== currIncrease) {
            count++;
        }
        increase = currIncrease;
    }
    return count;
};

1028 2. Longest Substring with At Least K Repeating Characters

/**
* @param {string} s
* @param {number} k
* @return {number}
*/
var longestSubstring = function(s, k) {
    if (s == null || s.length < k) {
        return 0;
    }
    const dict = {};
    for (let c of s) {
        dict[c] = dict[c] || 0;
        dict[c]++;
    }
    const chars = [];
    Object.entries(dict).forEach(([c, count]) => {
        if (count < k) {
            chars.push(c);
        }
    });
    if (chars.length === 0) {
        return s.length;
    } else {
        const separator = chars.join('|'); // since all letters, assume no special ones
        const parts = s.split(new RegExp(separator)).filter(part => part); // need to filter out
        let max = 0;
        for (let part of parts) {
            const len = longestSubstring(part, k);
            max = Math.max(max, len);
        }
        return max;
    }
};

1028 3. Guess Number Higher or Lower II

/**
* @param {number} n
* @return {number}
*/
var getMoneyAmount = function(n) {
    // !!!! binary search will use min times to find the target, but not necessarily min cost
    // dp, the best worst for sub problem i - j
    // 1 - n
    if (n < 2) {
        return 0;
    }
    const dp = Array(n + 1).fill().map(() => Array(n + 1).fill(0));
    for (let range = 2; range <= n; range++) {
        for (let i = 1; i + range - 1 <= n; i++) {
            const j = i + range - 1;
            dp[i][j] = Infinity;
            for (let k = i; k <= j; k++) {
                const left = k === i ? 0 : dp[i][k - 1];
                const right = k === j ? 0 : dp[k + 1][j];
                dp[i][j] = Math.min(dp[i][j], Math.max(left, right) + k);
            }
        }
    }
    return dp[1][n];
};

1028 4.  Dota2 Senate

!!! Very smart about how to use the q and index

/**
* @param {string} senate
* @return {string}
*/
var predictPartyVictory = function(senate) {
    if (senate == null || senate.length === 0) {
        return null;
    }
    const rq = [];
    const dq = [];
    for (let i = 0; i < senate.length; i++) {
        const c = senate[i];
        if (c === 'R') {
            rq.push(i);
        } else {
            dq.push(i);
        }
    }
    const len = senate.length;
    while (rq.length > 0 && dq.length > 0) {
        const ri = rq.shift();
        const di = dq.shift();
        if (ri < di) {
            rq.push(ri + len)
        } else {
            dq.push(di + len);
        }
    }
    return rq.length === 0 ? 'Dire' : 'Radiant';
};

1030 1. Split Array into Consecutive Subsequences


/**
* @param {number[]} nums
* @return {boolean}
*/
var isPossible = function(nums) {
    if (nums == null || nums.length < 3) {
        return false;
    }
    const freq = {};
    const need = {};
    nums.forEach(num => {
        freq[num] = freq[num] || 0;
        need[num] = need[num] || 0;
        freq[num]++;
    });
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        if (freq[num] === 0) {
            continue;
        } else if (need[num] > 0) {
            need[num]--;
            freq[num]--;
            need[num + 1]++;
        } else if (freq[num + 1] > 0 && freq[num + 2] > 0) {
            freq[num]--;
            freq[num + 1]--;
            freq[num + 2]--;
            need[num + 3] = need[num + 3] || 0;
            need[num + 3]++;
        } else {
            return false;
        }
    }
    return true;
};

1030 2. Partition to K Equal Sum Subsets

/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
var canPartitionKSubsets = function(nums, k) {
    if (nums == null || nums.length === 0) {
        return false;
    }
    const allSum = nums.reduce((a, b) => a + b);
    if (allSum % k !== 0) {
        return false;
    }
    const target = allSum / k;
    const visited = [];
    return recurse(0, 0, k);
   
    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)) {
                return true;
            }
            visited[i] = false;
        }
        return false;
    }
};

这个解法就是感觉特奇怪。而且感觉是有太多的重复计算了。需要找其他的解法。lc有答案可以研究一下。

1030 3. Find K Closest Elements

/**
* @param {number[]} arr
* @param {number} k
* @param {number} x
* @return {number[]}
*/
var findClosestElements = function(arr, k, x) {
    // first, binary search to find the position to start with
    // then, two pointers left and right starting from the mid
    // each time, compare left and right choose one and put into res (note ceiling)
    // until reached k
    if (arr == null || arr.length === 0) {
        return [];
    }
    let left = 0;
    let right = arr.length - 1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        const value = arr[mid];
        if (x === value) {
            left = mid + 1; // !!! 1. equals mid not x
            right = mid; // !!! 2. cannot make them equal because later we will move only one of them each time !!! 3. left and right will be switched, so we make them switch
            break;
        } else if (x < value) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    ;[left, right] = [right, left];
    const res = [];
    while (k > 0) {
        const leftDiff = left >= 0 ? Math.abs(arr[left] - x) : Infinity;
        const rightDiff = right < arr.length ? Math.abs(arr[right] - x) : Infinity;
        if (leftDiff <= rightDiff) {
            res.push(arr[left]);
            left--;
        } else {
            res.push(arr[right]);
            right++;
        }
        k--;
    }
    return res.sort((a, b) => a - b);
};

Took me so long to pass. Good one.