Lt819.最常见的单词、Lt118.杨辉三角、Lt119.杨辉三角 II

819.最常见的单词

Category	Difficulty	Likes	Dislikes
algorithms	Easy (40.82%)	72	-

Tags
dynamic-programming
Companies
Unknown
给定一个段落 (paragraph) 和一个禁用单词列表 (banned)。返回出现次数最多，同时不在禁用列表中的单词。
题目保证至少有一个词不在禁用列表中，而且答案唯一。
禁用列表中的单词用小写字母表示，不含标点符号。段落中的单词不区分大小写。答案都是小写字母。

示例：

输入:
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
输出: "ball"
解释:
"hit" 出现了3次，但它是一个禁用的单词。
"ball" 出现了2次 (同时没有其他单词出现2次)，所以它是段落里出现次数最多的，且不在禁用列表中的单词。
注意，所有这些单词在段落里不区分大小写，标点符号需要忽略（即使是紧挨着单词也忽略， 比如 "ball,"），
"hit"不是最终的答案，虽然它出现次数更多，但它在禁用单词列表中。

提示：

• 1 <= 段落长度 <= 1000
• 0 <= 禁用单词个数 <= 100
• 1 <= 禁用单词长度 <= 10
• 答案是唯一的, 且都是小写字母  (即使在 paragraph 里是大写的，即使是一些特定的名词，答案都是小写的。)
• paragraph 只包含字母、空格和下列标点符号!?',;.
• 不存在没有连字符或者带有连字符的单词。
• 单词里只包含字母，不会出现省略号或者其他标点符号。

---

Discussion | Solution

思路

题目 tag 是动态规划，这里使用对象，字符串，正则，数组的方法来强解。字符串转为小写，正则去除标点，split 分为数组，数组遍历生成类哈希表，再根据 banned 表筛选和降序，返回第一个元素

解答

/*
 * @lc app=leetcode.cn id=819 lang=javascript
 *
 * [819] 最常见的单词
 */

// @lc code=start
/**
 * @param {string} paragraph
 * @param {string[]} banned
 * @return {string}
 */
var mostCommonWord = function (paragraph, banned) {
  paragraph = paragraph
    .toLowerCase()
    .replace(/([^A-Za-z])/g, " ")
    .split(" ")
    .filter((e) => e);
  const obj = {};
  for (const arr of paragraph) {
    if (obj[arr]) {
      obj[arr] += 1;
    } else {
      obj[arr] = 1;
    }
  }
  const res = Object.entries(obj)
    .filter((e) => {
      if (banned.length) {
        return !banned.includes(e[0]);
      } else {
        return true;
      }
    })
    .sort((a, b) => Number(b[1]) - Number(a[1]));
  if (res.length) {
    return res[0][0];
  } else {
    return null;
  }
};
// @lc code=end

Accepted
47/47 cases passed (104 ms)
Your runtime beats 22.56 % of javascript submissions
Your memory usage beats 24.69 % of javascript submissions (40.4 MB)

118.杨辉三角

Category	Difficulty	Likes	Dislikes
algorithms	Easy (67.28%)	343	-

Tags
array
Companies
apple | twitter
给定一个非负整数 numRows，生成杨辉三角的前 numRows *行。

在杨辉三角中，每个数是它左上方和右上方的数的和。
*示例:**

输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

---

Discussion | Solution

思路

没有特别思路，双重循环即可。每行的第一个和最后一个添加 1。使用错行相加，例如当前行的第二个为上一行的第一个加第二个，使用 k 记录上一行的下标值，不断加一。

解答

/*
 * @lc app=leetcode.cn id=118 lang=javascript
 *
 * [118] 杨辉三角
 */

// @lc code=start
/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
  const res = [];
  let temp;
  for (let i = 0; i < numRows; i++) {
    temp = [];
    for (let j = 0, k = 0; j < i + 1; j++) {
      if (j === 0 || j === i) temp.push(1);
      else {
        temp.push(res[i - 1][k] + res[i - 1][++k]);
      }
    }
    res.push(temp);
  }
  return res;
};
// @lc code=end

Accepted
15/15 cases passed (80 ms)
Your runtime beats 53.67 % of javascript submissions
Your memory usage beats 5.06 % of javascript submissions (38.1 MB)

119.杨辉三角 II

Category	Difficulty	Likes	Dislikes
algorithms	Easy (61.84%)	176	-

Tags
array
Companies
amazon
给定一个非负索引 k_，其中 _k ≤ 33，返回杨辉三角的第 k *行。

在杨辉三角中，每个数是它左上方和右上方的数的和。
*示例:**

输入: 3
输出: [1,3,3,1]

进阶：
你可以优化你的算法到 O(k) 空间复杂度吗？

---

Discussion | Solution

思路

可以根据规律推出，每一行每一个数即为排列公式的 Cnk 求解方案，例如第四行第一个为 C40=1 第二个为 C41 = 4，公式如下

解答

/*
 * @lc app=leetcode.cn id=119 lang=javascript
 *
 * [119] 杨辉三角 II
 */

// @lc code=start
/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function (rowIndex) {
  const res = [];
  const getCombineNumber = (n, k) => {
    return getFact(n) / (getFact(k) * getFact(n - k));
  };
  const getFact = (num) => {
    if (num === 0) return 1;
    let res = num;
    while (num > 1) {
      num--;
      res *= num;
    }
    return res;
  };
  for (let i = 0; i < rowIndex + 1; i++) {
    res.push(getCombineNumber(rowIndex, i));
  }
  return res;
};
// @lc code=end

Accepted
34/34 cases passed (92 ms)
Your runtime beats 20.96 % of javascript submissions
Your memory usage beats 10.38 % of javascript submissions (38.1 MB)