Enhanfe

输入: x = 3, y = 5, z = 4
输出: True

输入: x = 2, y = 6, z = 5
输出: False

/**
 * @param {number} x
 * @param {number} y
 * @param {number} z
 * @return {boolean}
 */
var canMeasureWater = function(x, y, z) {
  if (x + y < z) {
    return false;
  }
  if (x === 0 || y === 0) {
    return z === 0 || x + y === z;
  }
  return z % calcGcd(x, y) === 0;
};
function calcGcd(a, b) {
  if (b === 0) {
    return a;
  }
  return calcGcd(b, a % b);
}

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function(head) {
  let linkSize = 0;
  let current = head;
  while (current) {
    ++linkSize;
    current = current.next;
  }
  let currentIndex = 0;
  const middleIndex = Math.floor(linkSize / 2);
  current = head;
  while (currentIndex < middleIndex) {
    ++currentIndex;
    current = current.next;
  }
  return current;
};

var middleNode = function(head) {
  slow = fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
};

输入：[[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
输出：3
解释：
在本例中，车能够捕获所有的卒。

输入：[[".",".",".",".",".",".",".","."],[".","p","p","p","p","p",".","."],[".","p","p","B","p","p",".","."],[".","p","B","R","B","p",".","."],[".","p","p","B","p","p",".","."],[".","p","p","p","p","p",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
输出：0
解释：
象阻止了车捕获任何卒。

输入：[[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","p",".",".",".","."],["p","p",".","R",".","p","B","."],[".",".",".",".",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."]]
输出：3
解释：
车可以捕获位置 b5，d6 和 f5 的卒。

/**
 * @param {character[][]} board
 * @return {number}
 */
var numRookCaptures = function(board) {
  let y,
    xlist = [],
    ylist = [],
    boardXLen = 8;

  for (let i = 0; i < boardXLen; i++) {
    if (board[i].indexOf('R') > -1) {
      y = board[i].indexOf('R');
      xlist = board[i].filter(e => e !== '.');
    }
  }
  for (let i = 0; i < boardXLen; i++) {
    board[i][y] !== '.' && ylist.push(board[i][y]);
  }

  let rx = xlist.indexOf('R'),
    ry = ylist.indexOf('R'),
    num = 0;

  if (xlist[rx + 1] && xlist[rx + 1] === 'p') ++num;
  if (xlist[rx - 1] && xlist[rx - 1] === 'p') ++num;
  if (ylist[ry + 1] && ylist[ry + 1] === 'p') ++num;
  if (ylist[ry - 1] && ylist[ry - 1] === 'p') ++num;

  return num;
};

输入：[1,2,3,4,4,3,2,1]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]

输入：[1,1,1,2,2,2,3,3]
输出：false
解释：没有满足要求的分组。

输入：[1]
输出：false
解释：没有满足要求的分组。

输入：[1,1]
输出：true
解释：可行的分组是 [1,1]

输入：[1,1,2,2,2,2]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[2,2]

/**
 * @param {number[]} deck
 * @return {boolean}
 */
var hasGroupsSizeX = function(deck) {
  let m = new Map();
  for (let n of deck) {
    m.set(n, m.has(n) ? m.get(n) + 1 : 1);
  }
  const vals = [...m.values()];
  let res = vals[0];
  return vals.every(val => (res = calcGcd(res, val)) > 1);
};

function calcGcd(a, b) {
  return b === 0 ? a : calcGcd(b, a % b);
}

/**
 * 初始化树.
 */
var Trie = function() {
  this.root = {};
};

/**
 * 将元素添加到树汇总
 */
Trie.prototype.insert = function(word) {
  let cur = this.root;
  for (i = 0; i < word.length; i++) {
    const char = word.charAt(i);
    if (!cur[char]) {
      cur[char] = {};
    }
    cur = cur[char];
  }
  cur.isWord = true;
};

/**
 * 搜索树中是否含有某给定字符串
 */
Trie.prototype.search = function(word) {
  let cur = this.root;
  for (i = 0; i < word.length; i++) {
    const char = word.charAt(i);
    if (!cur[char]) {
      return false;
    }
    cur = cur[char];
  }
  return cur.isWord || false;
};

/**
 * 搜索树中是否含有以给定字符串为前缀
 */
Trie.prototype.startsWith = function(prefix) {
  let cur = this.root;
  for (i = 0; i < prefix.length; i++) {
    const char = prefix.charAt(i);
    if (!cur[char]) {
      return false;
    }
    cur = cur[char];
  }
  return true;
};

/**
 * @param {string[]} words
 * @return {number}
 */
var minimumLengthEncoding = function(words) {
  const wordSet = new Set(words);
  for (let word of words) {
    for (let i = 1; i < word.length; i++) {
      wordSet.delete(word.substring(i));
    }
  }
  return [...wordSet].join('#').length + 1;
};

/**
 * @param {string[]} words
 * @return {number}
 */
var minimumLengthEncoding = function(words) {
  const trie = new Trie();
  let len = 0;
  const cwords = words.sort((a, b) => b.length - a.length);
  for (let word of cwords) {
    len += trie.insert(word);
  }
  return len;
};

var Trie = function() {
  this.root = {};
};

Trie.prototype.insert = function(word) {
  let cur = this.root;
  let isNew = false;
  for (i = word.length - 1; i >= 0; i--) {
    const char = word.charAt(i);
    if (!cur[char]) {
      isNew = true;
      cur[char] = {};
    }
    cur = cur[char];
  }
  return isNew ? word.length + 1 : 0;
};

输入：[[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释：
海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大，最大距离为 2。

输入：[[1,0,0],[0,0,0],[0,0,0]]
输出：4
解释：
海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大，最大距离为 4。

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxDistance = function(grid) {
  if (grid.length < 2) return -1;
  let n = grid.length;
  // 创建 dp 状态矩阵
  let dp = new Array(n);
  for (let i = 0; i < n; i++) {
    dp[i] = new Array(n);
  }

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      dp[i][j] = grid[i][j] ? 0 : Infinity;
    }
  }
  // 从左上向右下遍历
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j]) continue;
      if (i - 1 >= 0) dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
      if (j - 1 >= 0) dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
    }
  }
  // 从右下向左上遍历
  for (let i = n - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      if (grid[i][j]) continue;
      if (i + 1 < n) dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
      if (j + 1 < n) dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1);
    }
  }
  let ans = -1;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (!grid[i][j]) ans = Math.max(ans, dp[i][j]);
    }
  }
  if (ans === Infinity) {
    return -1;
  } else {
    return ans;
  }
};

输入: n = 5, m = 3
输出: 3

输入: n = 10, m = 17
输出: 2

/**
 * @param {number} n
 * @param {number} m
 * @return {number}
 */
var lastRemaining = function(n, m) {
  let res = 0;
  for (let i = 2; i != n + 1; ++i) res = (m + res) % i;
  return res;
};

输入：seq = "(()())"
输出：[0,1,1,1,1,0]

输入：seq = "()(())()"
输出：[0,0,0,1,1,0,1,1]
解释：本示例答案不唯一。
按此输出 A = "()()", B = "()()", max(depth(A), depth(B)) = 1，它们的深度最小。
像 [1,1,1,0,0,1,1,1]，也是正确结果，其中 A = "()()()", B = "()", max(depth(A), depth(B)) = 1 。

仅由 "(" 和 ")" 构成的字符串，对于每个左括号，都能找到与之对应的右括号，反之亦然。
下述几种情况同样属于有效括号字符串：

  1. 空字符串
  2. 连接，可以记作 AB（A 与 B 连接），其中 A 和 B 都是有效括号字符串
  3. 嵌套，可以记作 (A)，其中 A 是有效括号字符串

类似地，我们可以定义任意有效括号字符串 s 的 嵌套深度 depth(S)：

  1. s 为空时，depth("") = 0
  2. s 为 A 与 B 连接时，depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是有效括号字符串
  3. s 为嵌套情况，depth("(" + A + ")") = 1 + depth(A)，其中 A 是有效括号字符串

例如：""，"()()"，和 "()(()())" 都是有效括号字符串，嵌套深度分别为 0，1，2，而 ")(" 和 "(()" 都不是有效括号字符串。

/**
 * @param {string} seq
 * @return {number[]}
 */
let maxDepthAfterSplit = (seq, dep = 0) => {
  return seq.split('').map(e => (e === '(' ? dep++ % 2 : --dep % 2));
};

输入：
[
  [0,1,0],
  [0,0,1],
  [1,1,1],
  [0,0,0]
]
输出：
[
  [0,0,0],
  [1,0,1],
  [0,1,1],
  [0,1,0]
]

var gameOfLife = function(board) {
  let row = board.length;
  let col = board[0].length;
  let helper = function(ro, co, copy) {
    let count = 0;
    if (ro > 0) {
      count += copy[ro - 1][co];
      if (co > 0) {
        count += copy[ro - 1][co - 1];
      }
      if (co < col - 1) {
        count += copy[ro - 1][co + 1];
      }
    }
    if (ro < row - 1) {
      count += copy[ro + 1][co];
      if (co > 0) {
        count += copy[ro + 1][co - 1];
      }
      if (co < col - 1) {
        count += copy[ro + 1][co + 1];
      }
    }
    if (co > 0) {
      count += copy[ro][co - 1];
    }
    if (co < col - 1) {
      count += copy[ro][co + 1];
    }
    //根据状态进行归类，true为状态变化的，即死变活，活变死
    if (copy[ro][co] == 1) {
      if (count < 2) {
        return true;
      } else if (count > 3) {
        return true;
      }
    }
    if (copy[ro][co] == 0 && count == 3) return true;
    return false;
  };
  let copy = JSON.parse(JSON.stringify(board));
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (helper(i, j, copy)) {
        //直接通过异或运算变更状态
        board[i][j] ^= 1;
      }
    }
  }
};

输入: "42"
输出: 42

输入: "   -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
     我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。

输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。

输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
     因此无法执行有效的转换。

输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
     因此返回 INT_MIN (−2^31) 。

/**
 * @param {string} str
 * @return {number}
 */
var myAtoi = function(str) {
  str = str.trim();
  if (!/^[+|-]?\d+/.test(str)) return 0;
  let val = parseInt(str.match(/^[+|-]?\d+/));
  let base = Math.pow(2, 31);
  let min = -base,
    max = base - 1;
  return Math.max(Math.min(val, max), min);
};

LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回 1
cache.put(3, 3);    // 去除 key 2
cache.get(2);       // 返回 -1 (未找到key 2)
cache.get(3);       // 返回 3
cache.put(4, 4);    // 去除 key 1
cache.get(1);       // 返回 -1 (未找到 key 1)
cache.get(3);       // 返回 3
cache.get(4);       // 返回 4

/**
 * @param {number} capacity
 */
var LFUCache = function(capacity) {
  this.limit = capacity;
  this.cache = new Map();
  this.freqMap = new Map();
};

/**
 * @param {number} key
 * @return {number}
 */
LFUCache.prototype.get = function(key) {
  let cache = this.cache;
  let r = -1;
  if (typeof cache[key] != 'undefined') {
    let o = cache[key];
    r = o.value;
    //更新频率记录
    this.updateL(key, o);
  }
  return r;
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LFUCache.prototype.put = function(key, value) {
  let { cache, limit, freqMap: fmap } = this;
  if (limit <= 0) return;
  if (typeof key == 'undefined' || typeof value == 'undefined')
    throw new Error('key or value is undefined');
  // 存在则直接更新
  if (typeof cache[key] == 'undefined') {
    // 获取频率 key
    // 判断容量是否满
    if (Object.keys(cache).length == limit) {
      let fkeys = Object.keys(fmap);
      let freq = fkeys[0];
      // 获取key集合
      let keys = fmap[freq];
      // 淘汰首位
      delete cache[keys.shift()];
      // delete cache[keys[0]];
      // keys.splice(0, 1);
      // 清理
      if (fmap[freq].length == 0) delete fmap[freq];
    }
    // 频率记录是否存在
    if (!fmap[1]) fmap[1] = [];
    // 插入新值
    fmap[1].push(key);
    cache[key] = {
      value: value,
      freq: 1, // 默认的频率
    };
  } else {
    cache[key].value = value;
    //更新频率记录
    this.updateL(key, cache[key]);
  }
};

LFUCache.prototype.updateL = function(key, obj) {
  let { freq } = obj;
  let arr = this.freqMap[freq];
  // 删除原频率记录
  this.freqMap[freq].splice(arr.indexOf(key), 1);
  // 清理
  if (this.freqMap[freq].length == 0) delete this.freqMap[freq];
  // 更新频率
  freq = obj.freq = obj.freq + 1;
  if (!this.freqMap[freq]) this.freqMap[freq] = [];
  this.freqMap[freq].push(key);
};

给定 matrix =
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
],

原地旋转输入矩阵，使其变为:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
let rotate = matrix => {
  for (let i = 0; i < matrix.length; i++) {
    for (let j = i; j < matrix[i].length; j++) {
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
    }
  }
  matrix.forEach(row => row.reverse());
};

输入：m = 2, n = 3, k = 1
输出：3

输入：m = 3, n = 1, k = 0
输出：1

/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var movingCount = function(m, n, k) {
  let step = {};

  let num = 0;
  function dfs(i, j) {
    if (i < 0 || j < 0 || i >= m || j >= n) return;

    if (!step[`${i}|${j}`] && canMove(i, j, k)) {
      step[`${i}|${j}`] = true;
      num++;

      dfs(i - 1, j);
      dfs(i + 1, j);
      dfs(i, j - 1);
      dfs(i, j + 1);
    }
  }
  dfs(0, 0);
  return num;
};
function canMove(i, j, k) {
  let vali = i
    .toString()
    .split('')
    .reduce((a, b) => {
      return Number(a) + Number(b);
    });
  let valj = j
    .toString()
    .split('')
    .reduce((a, b) => {
      return Number(a) + Number(b);
    });
  if (Number(vali) + Number(valj) <= k) return true;
  return false;
}

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

var generateParenthesis = function(n) {
  let res = [];
  //  cur :当前字符  left：当前字符左括号 right:当前字符右括号
  const help = (cur, left, right) => {
    if (cur.length === 2 * n) {
      res.push(cur);
      return;
    }
    if (left < n) {
      help(cur + '(', left + 1, right);
    }
    if (right < left) {
      help(cur + ')', left, right + 1);
    }
  };
  help('', 0, 0);
  return res;
};

输入: "the sky is blue"
输出: "blue is sky the"

输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
  return s
    .split(' ')
    .filter(item => item)
    .reverse()
    .join(' ');
};

输入：K = 1, N = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
如果它没碎，那么我们肯定知道 F = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。

输入：K = 2, N = 6
输出：3

输入：K = 3, N = 14
输出：4

/**
 * @param {number} K
 * @param {number} N
 * @return {number}
 */
var superEggDrop = function(K, N) {
  let dp = Array(K + 1).fill(0);
  let cnt = 0;
  while (dp[K] < N) {
    cnt++;
    for (let i = K; i > 0; i--) {
      dp[i] = dp[i - 1] + dp[i] + 1;
    }
  }
  return cnt;
};

Twitter twitter = new Twitter();

// 用户1发送了一条新推文 (用户id = 1, 推文id = 5).
twitter.postTweet(1, 5);

// 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文.
twitter.getNewsFeed(1);

// 用户1关注了用户2.
twitter.follow(1, 2);

// 用户2发送了一个新推文 (推文id = 6).
twitter.postTweet(2, 6);

// 用户1的获取推文应当返回一个列表，其中包含两个推文，id分别为 -> [6, 5].
// 推文id6应当在推文id5之前，因为它是在5之后发送的.
twitter.getNewsFeed(1);

// 用户1取消关注了用户2.
twitter.unfollow(1, 2);

// 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文.
// 因为用户1已经不再关注用户2.
twitter.getNewsFeed(1);

/**
 * Initialize your data structure here.
 */
var Twitter = function() {
  this.time = 0;
  this.users = {}; // follows
};

/**
 * Compose a new tweet.
 * @param {number} userId
 * @param {number} tweetId
 * @return {void}
 */
Twitter.prototype.postTweet = function(userId, tweetId) {
  this.time += 1;
  let { users } = this;
  if (users[userId] === undefined) users[userId] = [];
  if (users[userId]['tweets'] === undefined) users[userId]['tweets'] = [];
  // 考虑重复推文
  let hasTweets = [];
  for (let tweet of users[userId]['tweets']) {
    hasTweets.push(tweet.tweetId);
  }
  if (hasTweets.includes(tweetId)) return;
  users[userId]['tweets'].push({ tweetId, time: this.time });
};

/**
 * 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) {
  let users = this.users,
    list = [],
    ids = [userId]; // 自己和自己关注的 userId
  if (users[userId] === undefined) return [];
  let follows = users[userId]['follows'];
  if (follows !== undefined) {
    ids.push(...follows);
  }

  for (let userid of ids) {
    if (users[userid] === undefined) continue;
    if (users[userid]['tweets'] === undefined) continue;
    list.push(...users[userid]['tweets']);
  }

  list.sort((a, b) => b.time - a.time);

  let res = new Set(); // 去重重复推文，防止自己关注自己的情况
  for (let i = 0; i < list.length; i++) {
    res.add(list[i]['tweetId']);
    if (res.size === 10) break;
  }
  return [...res];
};

/**
 * 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) {
  let users = this.users;
  if (users[followerId] === undefined) users[followerId] = [];
  if (users[followerId]['follows'] === undefined) {
    users[followerId]['follows'] = [];
  }
  if (users[followerId]['follows'].indexOf(followeeId) !== -1) return;
  users[followerId]['follows'].push(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) {
  let users = this.users;
  if (users[followerId] === undefined) return;
  if (users[followerId]['follows'] === undefined) return;
  let userFollows = users[followerId]['follows'];
  let index = userFollows.indexOf(followeeId);
  if (index === -1) return;
  userFollows.splice(index, 1);
};

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
  let stack1 = [];
  let stack2 = [];
  while (l1) {
    stack1.push(l1.val);
    l1 = l1.next;
  }
  while (l2) {
    stack2.push(l2.val);
    l2 = l2.next;
  }
  let mark = 0;
  let res = null;
  while (stack1.length > 0 || stack2.length > 0 || mark !== 0) {
    let val1 = stack1.length > 0 ? stack1.pop() : 0;
    let val2 = stack2.length > 0 ? stack2.pop() : 0;
    let val = val1 + val2 + mark;
    mark = (val / 10) | 0;
    curNode = new ListNode(val % 10);
    curNode.next = res;
    res = curNode;
  }
  return res;
};