131 篇博文 含有标签「数组」

1、题干​

这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。

你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。

返回你最多可以修读的课程数目。

示例 1：

输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
输出：3
解释：
这里一共有 4 门课程，但是你最多可以修 3 门：
首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。
第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。
第三，修第 2 门课，耗时 200 天，在第 1300 天完成。
第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。

示例 2：

输入：courses = [[1,2]]
输出：1

示例 3：

输入：courses = [[3,2],[4,3]]
输出：0

提示:

• 1 <= courses.length <= 104
• 1 <= durationi, lastDayi <= 104

2、提交结果​

逻辑和代码比优先队列更简洁，执行效率更高。

3、解题思路​

破题思路还是看官解。这个题解主要说明如何在保证效率的前提下用更少代码替代优先队列。

每次答优先队列的题都巨难受，因为JS没有优先队列这种数据结构。由于数据范围特征明显1 <= duration[i] <= 1e4，可以用计数排序解这道题，代码比优先队列更简洁。凑巧的是测试用例也比较给力，执行效率比优先队列还好看些。接下来说下如何用计数排序替代优先队列。

设计思路​

优先队列解决的关键问题是快速插入、删除和查找最值。因此我们设计一个名为FPQ的数据结构解决这几个问题，FPQ主要包括的函数和变量是：list、max、constructor()、add()、del()

• list：元素容器，下标代表待排序的数据，元素值代表下标数字的数量
• max：所有元素中的最大值；可直接读取，时间复杂度为$O(1)$
• constructor()：构造函数，入参为整数n；时间复杂度为$O(n)$；函数逻辑如下：
  • 创建一个大小为n+1的数组list，初始化max为0
• add()：往list中添加元素，入参为整数n；时间复杂度为$O(1)$；函数逻辑如下：
  • list[n]自加1
  • 如果 n > max，则将max赋值为n
• del()：删除list中的元素，入参为整数 n；最坏时间复杂度为$O(n)$；函数逻辑如下：
  • list[n]自减1
  • 如果 n === max 且 list[n]===0，则需要重新计算最大值
  • 计算最大值：从下标 n 开始倒序遍历 list，如果list[n]>0，则将max赋值为list[n]并退出遍历

FPQ的插入方法比优先队列更高效，但删除方法不稳定，其效率可能比优先队列更好也可能更差。另外由于使用计数排序，因此使用场景也很有限。

4、代码​

var scheduleCourse = function (courses) {
  courses.sort((a, b) => a[1] - b[1]);

  const max = courses.reduce((acc, cur) => (cur[0] > acc ? cur[0] : acc), courses[0][0]);
  const pq = new FPQ(max);

  let res = 0;
  let time = 0;
  for (let i = 0; i < courses.length; i++) {
    if (time + courses[i][0] <= courses[i][1]) {
      res++;
      time += courses[i][0];
      pq.add(courses[i][0]);
    } else if (courses[i][0] < pq.max && time + courses[i][0] - pq.max < courses[i][1]) {
      time += courses[i][0] - pq.max;
      pq.add(courses[i][0]);
      pq.del(pq.max);
    }
  }

  return res;
};

class FPQ {
  constructor(n) {
    this.list = new Array(n + 1).fill(0);
    this.max = 0;
  }

  add(n) {
    this.list[n] += 1;
    if (n > this.max) this.max = n;
  }

  del(n) {
    this.list[n] -= 1;
    if (n !== this.max || this.list[n]) return;
    while (n > -1) {
      if (this.list[n] || !n) return (this.max = n);
      n--;
    }
  }
}

1、题干​

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 的值为 '0' 或 '1'

解题思路​

• 遍历矩阵grid，以grid[i][j]为起点往上下左右4个方向进行深度遍历
• 深度遍历过程中需要注意2点
  • 遍历过的节点修改为0，即grid[i][j] = '0'，以免重复遍历
  • grid[i][j]必须在矩阵中且grid[i][j] === '1'才累加岛屿数量

代码​

var numIslands = function (grid) {
    const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    function dfs(i, j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] === '0') return false;
        grid[i][j] = '0';
        for (const [di, dj] of dirs) dfs(i + di, j + dj);
        return true;
    }

    let count = 0;
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (dfs(i, j)) count++;
        }
    }

    return count;
};

1、题干​

给你一座由 n x n 个街区组成的城市，每个街区都包含一座立方体建筑。给你一个下标从 0 开始的 n x n 整数矩阵 grid ，其中 grid[r][c] 表示坐落于 r 行 c 列的建筑物的 高度 。

城市的 天际线 是从远处观察城市时，所有建筑物形成的外部轮廓。从东、南、西、北四个主要方向观测到的 天际线 可能不同。

我们被允许为 任意数量的建筑物 的高度增加 任意增量（不同建筑物的增量可能不同） 。 高度为 0 的建筑物的高度也可以增加。然而，增加的建筑物高度 不能影响 从任何主要方向观察城市得到的 天际线 。

在 不改变 从任何主要方向观测到的城市 天际线 的前提下，返回建筑物可以增加的 最大高度增量总和 。

示例 1：

输入：grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
输出：35
解释：建筑物的高度如上图中心所示。
用红色绘制从不同方向观看得到的天际线。
在不影响天际线的情况下，增加建筑物的高度：
gridNew = [ [8, 4, 8, 7],
            [7, 4, 7, 7],
            [9, 4, 8, 7],
            [3, 3, 3, 3] ]

示例 2：

输入：grid = [[0,0,0],[0,0,0],[0,0,0]]
输出：0
解释：增加任何建筑物的高度都会导致天际线的变化。

提示：

• n == grid.length
• n == grid[r].length
• 2 <= n <= 50
• 0 <= grid[r][c] <= 100

解题思路​

题目比较简单，两次遍历先取行列最大值再累加最大差值即可。详细步骤如下：

• 先计算各行最大值maxInRows和各列最大值maxInCols
• 再遍历矩阵grid中每个元素，元素增大的上限是该行最大值maxInRows[i]和该列最大值maxInCols[j]中较小的那个
• 求局部最优解：计算出每个建筑物可以增加的最大高度(Math.min(maxInRows[i], maxInCols[j]) - grid[i][j])
• 累加可得全局最优解：建筑物高度可以增加的最大总和

时间复杂度：$O(n^2)$

代码​

var maxIncreaseKeepingSkyline = function (grid) {
    const maxInRows = new Array(grid.length).fill(0);
    const maxInCols = new Array(grid[0].length).fill(0);

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            maxInRows[i] = Math.max(maxInRows[i], grid[i][j]);
            maxInCols[j] = Math.max(maxInCols[j], grid[i][j]);
        }
    }

    let res = 0;
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            res += (Math.min(maxInRows[i], maxInCols[j]) - grid[i][j]);
        }
    }

    return res;
};

1、题干​

给你一个字符串数组 board 表示井字游戏的棋盘。当且仅当在井字游戏过程中，棋盘有可能达到 board 所显示的状态时，才返回 true 。

井字游戏的棋盘是一个 3 x 3 数组，由字符 ' '，'X' 和 'O' 组成。字符 ' ' 代表一个空位。

以下是井字游戏的规则：

• 玩家轮流将字符放入空位（' '）中。
• 玩家 1 总是放字符 'X' ，而玩家 2 总是放字符 'O' 。
• 'X' 和 'O' 只允许放置在空位中，不允许对已放有字符的位置进行填充。
• 当有 3 个相同（且非空）的字符填充任何行、列或对角线时，游戏结束。
• 当所有位置非空时，也算为游戏结束。
• 如果游戏结束，玩家不允许再放置字符。

示例 1：

输入：board = ["O  ","   ","   "]
输出：false
解释：玩家 1 总是放字符 "X" 。

示例 2：

输入：board = ["XOX"," X ","   "]
输出：false
解释：玩家应该轮流放字符。

示例 3:

输入：board = ["XOX","O O","XOX"]
输出：true

提示：

• board.length == 3
• board[i].length == 3
• board[i][j] 为 'X'、'O' 或 ' '

解题思路​

题目看似简单，实际答题还是出现了错漏(￣.￣)

• 题干中3个关键的限制条件

  • 第一个玩家总是放字符 “X”，且第二个玩家总是放字符 “O”
  • 当有 3 个相同（且非空）的字符填充任何行、列或对角线时，游戏结束
  • 如果游戏结束，玩家不允许再放置字符

• 分析得出的4种限制情况

  • 1、局内限制：X的数量与O相等或者比O多1，即：len(X) >= len(O) && len(X) - len(O) <= 1
  • 2、赢家限制：赢家是X时，X的数量比O多1，即：winners.has('XXX') && len(X) == len(O)+1
  • 3、赢家限制：赢家是O时，X的数量与O相等，即：winners.has('OOO') && len(X) == len(O)
  • 4、赢家限制：不能出现双赢局面，即winners.size<=1

代码​

var validTicTacToe = function (board) {
  const winners = new Set();
  const checkWinner = (s) => /XXX|OOO/.test(s) && winners.add(s);
  checkWinner(board[0][0] + board[1][1] + board[2][2]);
  checkWinner(board[0][2] + board[1][1] + board[2][0]);

  let [xc, oc] = [0, 0];
  for (let i = 0; i < board.length; i++) {
    checkWinner(board[i]);
    for (let j = 0; j < board[i].length; j++) {
      if (board[i][j] !== ' ') board[i][j] === 'X' ? xc++ : oc++;
      checkWinner(board[0][j] + board[1][j] + board[2][j]);
    }
  }

  //1、局内限制：len(X) >= len(O) && len(X) - len(O) <= 1
  if (xc < oc || xc - oc > 1) return false;
  //2、赢家限制：赢家是X时，len(X) == len(O)+1
  if (winners.has('XXX') && xc === oc) return false;
  //3、赢家限制：赢家是O时，len(X) == len(O)
  if (winners.has('OOO') && xc > oc) return false;
  //4、赢家限制：不能出现双赢局面
  return winners.size <= 1;
};

1、题干​

给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 素数  组成，且其中所有整数互不相同。

对于每对满足 0 <= i < j < arr.length 的 i 和 j ，可以得到分数 arr[i] / arr[j] 。

那么第 k 个最小的分数是多少呢?  以长度为 2 的整数数组返回你的答案, 这里 answer[0] == arr[i] 且 answer[1] == arr[j] 。

示例 1：

输入：arr = [1,2,3,5], k = 3
输出：[2,5]
解释：已构造好的分数,排序后如下所示: 
1/5, 1/3, 2/5, 1/2, 3/5, 2/3
很明显第三个最小的分数是 2/5

示例 2：

输入：arr = [1,7], k = 1
输出：[1,7]

提示：

• 2 <= arr.length <= 1000
• 1 <= arr[i] <= 3 * 104
• arr[0] == 1
• arr[i] 是一个 素数 ，i > 0
• arr 中的所有数字 互不相同 ，且按 严格递增 排序
• 1 <= k <= arr.length * (arr.length - 1) / 2

进阶：你可以设计并实现时间复杂度小于 O(n2) 的算法解决此问题吗？

2、解法1-暴力解法​

创建数组matrix，两层循环遍历素数数组，把所有素数对存入matrix中，然后对matrix进行排序。最先尝试了暴力解法，居然过了。。。

3、代码​

var kthSmallestPrimeFraction = function (arr, k) {
    const p = [];
    for (let i = 1; i < arr.length; i++) {
        for (let j = 0; j < i; j++) {
            p.push([arr[j], arr[i]]);
        }
    }

    p.sort((a, b) => a[0] / a[1] - b[0] / b[1]);

    return p[k - 1];
};

• 时间复杂度: $O(n^2*log(n^2))$
• 执行用时: 1908 ms，内存消耗: 94 MB

4、解法2-暴力解法的二分优化​

之后尝试使用二分法优化这段代码，这里二分的目标是matrix而不是原始数组arr，因为时间复杂度最高的地方在matrix的排序。优化后时间复杂度量级没有改变，但是matrix长度减半，执行速度会有所提升

思路是：

• 创建两个数组m1和m2，两层循环遍历素数数组
• 把所有商小于0.5的素数对存入m1中，其余存入m2中
• 如果k <= m1.length就对m1排序并返回m1[k-1]
• 如果k > m1.length就对m2排序并返回m2[k - m1.length - 1]

5、代码​

var kthSmallestPrimeFraction = function (arr, k) {
    const p1 = [];
    const p2 = [];
    for (let i = 1; i < arr.length; i++) {
        for (let j = 0; j < i; j++) {
            if (arr[j] / arr[i] < 0.5) {
                p1.push([arr[j], arr[i]]);
            } else {
                p2.push([arr[j], arr[i]]);
            }
        }
    }

    if (k <= p1.length) {
        p1.sort((a, b) => a[0] / a[1] - b[0] / b[1]);
        return p1[k - 1];
    } else {
        p2.sort((a, b) => a[0] / a[1] - b[0] / b[1]);
        return p2[k - p1.length - 1];
    }
};

• 时间复杂度: $O(n^2*log(n^2))$
• 执行用时: 1276 ms 内存消耗: 104.1 MB

6、解法3-桶排序​

二分方案中，把matrix二分后两个子数组的元素个数的数量级几乎相当，其实推广到$N(2<N<=n*(n-1)/2,n=1000)$也适用。也就是说matrix分成N个子组后每个子组的长度几乎相等，这其实就是桶排序。

所以如果这样理解题意就简单很多：数组中最多包含约500000（$n*(n-1)/2,n=1000$）个无序排列的小数，这些小数从0到1均匀分布，返回其中第k小的小数。

桶排序的思路：

• 创建大小为N的二维数组matrix，matrix中的每个元素(数组)就是一个桶
• 根据分组规则把所有小数均匀放入桶中
• 累计每个桶内元素数量，找到第k个小数所在的桶matrix[k']，对该桶内小数进行排序
• 在matrix[k']这个桶中找到第k个小数即可

小数的分组规则：

• 分组的关键问题是分组规则，也就是任意小数a应该放入桶的序号i是多少（即a与i之间的映射关系）
• 实际上可以用桶的数量$N$乘以小数$a$再取整作为桶的序号，即$i=Math.trunc(a*N)$，这样就建立起小数a与桶序号i的映射，消耗的时间复杂度是$O(1)$

对于这个分组规则可以举个例子：假设$N$取$1000$，对于任意小数$0.0012$，把数据代入公式$i=Math.trunc(a*N)$中算得$i=1$，也就是说$0.0012$应该放入$matrix[1]$这个桶中。

还是在暴力解法的基础上优化，只需要把matrix分为N个子数组，然后只对包含第k个小数的子数组进行排序，最后返回对应的素数对即可。

如果N的取值合适的话，时间复杂度可以降到 $O(n^2)$。这里使用的取值计算公式是：N = 10 ** Math.trunc(Math.log10(arr[arr.length - 1]))。

7、代码​

var kthSmallestPrimeFraction = function (arr, k) {
    const BASE = 10 ** Math.trunc(Math.log10(arr[arr.length - 1]));
    const matrix = new Array(BASE);
    for (let i = 1; i < arr.length; i++) {
        for (let j = 0; j < i; j++) {
            const index = Math.trunc(arr[j] / arr[i] * BASE);
            if (!matrix[index]) matrix[index] = [];
            matrix[index].push([arr[j], arr[i]]);
        }
    }

    for (let arr of matrix) {
        arr = arr || [];
        if (k - arr.length <= 0) {
            arr.sort((a, b) => a[0] / a[1] - b[0] / b[1]);
            return arr[k - 1];
        }
        k = k - arr.length;
    }
};

• 时间复杂度: $O(n^2)$
• 执行用时: 876 ms 内存消耗: 97.8 MB

8、解法4-桶排序优化​

每个桶都使用Array.push放入数据，最终只使用了其中一个桶进行排序，这在时间和空间上都存在大量浪费。可以进一步优化为，只在包含第k个小数的桶中存入素数对，其他的桶只记录元素个数即可。

程序最终逻辑：

• 计算分组数量N
• 初始化matrix并写入N个0
• 双层遍历arr，计算每个桶包含小数的数量
• 按桶累计小数数量，找到第k个小数对应的桶序号index，将桶matrix[index]赋值为空数组
• 双层遍历arr，当小数对应的序号与index相等时，将素数对放入桶matrix[index]中
• 对桶matrix[index]进行排序，返回第k个素数对

9、代码​

var kthSmallestPrimeFraction = function(arr, k) {
  // 计算分组数量N
  const N = 10 ** Math.trunc(Math.log10(arr[arr.length - 1]));
  // 初始化matrix并写入N个0
  const matrix = new Array(N).fill(0);

  // 双层遍历arr，计算每个桶包含小数的数量
  for (let i = 1; i < arr.length; i++) {
    for (let j = 0; j < i; j++) {
      const m = Math.trunc((arr[j] / arr[i]) * N);
      matrix[m] += 1;
    }
  }

  // 按桶累计小数数量，找到第k个小数对应的桶序号index，将桶`matrix[index]`赋值为空数组
  let index = 0;
  for (let i = 0; i < matrix.length; i++) {
    if (k - matrix[i] <= 0) {
      index = i;
      matrix[index] = [];
      break;
    }
    k = k - matrix[i];
  }

  // 双层遍历arr，当小数对应的序号与index相等时，将素数对放入桶`matrix[index]`中
  for (let i = 1; i < arr.length; i++) {
    for (let j = 0; j < i; j++) {
      const m = Math.trunc((arr[j] / arr[i]) * N);
      if (index === m) matrix[m].push([arr[j], arr[i]]);
    }
  }

  // 对桶`matrix[index]`进行排序，返回第k个素数对
  matrix[index].sort((a, b) => a[0] / a[1] - b[0] / b[1]);
  return matrix[index][k - 1];
};

• 时间复杂度: $O(n^2)$
• 执行用时: 92 ms 内存消耗: 41.1 MB

1、题干​

给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。

示例 1：

输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出：16 
解释：这两个单词为 "abcw", "xtfn"。

示例 2：

输入：words = ["a","ab","abc","d","cd","bcd","abcd"]
输出：4 
解释：这两个单词为 "ab", "cd"。

示例 3：

输入：words = ["a","aa","aaa","aaaa"]
输出：0 
解释：不存在这样的两个单词。

提示：

• 2 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] 仅包含小写字母

思路​

• 暴力解法：

  • 暴力解法是做个嵌套循环遍历所有words，判断两个word是否有相同字母需要再遍历word中的字符
  • 按暴力解法估算时间复杂度大概是O(n^3)，n取1000的话，超时基本没跑了
  • 实际上2层嵌套循环基本无法避免，也就是说时间复杂度至少是O(n^2)，那就想办法再减少一层遍历

• 第1层优化-字典：

  • 题目中说到 每个单词只包含小写字母，通常会想到把单词转换成以字母为key的哈希表或者数组字典来做优化
  • 根据题意，使用数组表示单词时，只要将字母对应ASCII码顺序作为索引，值为bool类型即可
  • 举个例子，单词abc可以表示为[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1]，单词a可以表示为[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
  • 判断两个单词是否包含相同字母需要做一次遍历，由于数组长度恒定为26，因此时间复杂度为常数
  • 至此，时间复杂度已经可以达到O(n^2)

• 第2层优化-位运算：

  • 实际上，如果用二进制整数来表示单词会更简洁 abc可以表示为0b111，a可以表示为0b1
  • 而且判断两个单词是否有相同字母只需要做一次&运算而不需要遍历数组，&运算结果为0则表示没有相同字母
  • 这个优化不能减少时间复杂度，但是可以减少执行时间

• 解题步骤：

  • 1、遍历words，将words中的单词转换为长度为2的数组[bit,word.length]，数组两个元素分别表示单词的二进制和单词的长度
  • 2、再次遍历words，把当前单词与剩余单词做匹配，如果不存在相同单词，则计算长度乘积
  • 3、返回长度乘积的最大值，具体代码如下

• 进一步优化：

  • 题解中说到单词转成二进制之后可能会相等，因此可以用哈希表做进一步优化（答题的时候没想到，另外考虑到单词组合问题，26个字母组成1000个单词，最坏情况下转成二进制之后可能没有相等的情况，因此就不写了）
  • 答题的时候发现运算次数达到一定量级之后，位运算的速度比乘方运算更快些（属于自己挖坑了，这里耗时差距能达到10+倍，具体参考附录）

代码​

var maxProduct = function (words) {
    const CODEA = 'a'.charCodeAt(0);
    for (let i = 0; i < words.length; i++) {
        let bit = 0;
        for (let j = 0; j < words[i].length; j++) {
            const p = words[i].charCodeAt(j) - CODEA;
            bit = bit | (1 << p);
        }
        words[i] = [bit, words[i].length];
    }

    let res = 0;
    for (let i = 0; i < words.length; i++) {
        for (let j = i + 1; j < words.length; j++) {
            if ((words[i][0] & words[j][0]) === 0) {
                res = Math.max(res, words[i][1] * words[j][1]);
            }
        }
    }

    return res;
};

附录​

const K = 1e6;
const MOD = 10;

console.time('乘方');
let n = 0;
for (let i = 0; i < K; i++) {
  n = n | (2 ** (i % MOD));
}
console.timeEnd('乘方');

console.time('位运算');
n = 0;
for (let i = 0; i < K; i++) {
  n = n | (1 << (i % MOD));
}
console.timeEnd('位运算');
// 浏览器下执行结果
// 乘方: 78.853759765625 ms
// 位运算: 6.093994140625 ms

1、题干​

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

• 1 <= nums.length <= 105
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

解题思路​

• 创建哈希映射map，用于统计数字出现次数，key为数字，value为出现次数
• 创建数组arr，用于统计每个出现次数对应的数字集合，数组下标代表数字出现次数，值为出现次数与之相等的数字的集合
• 倒序遍历数组arr，提取前出现频率前 k 高的数字

代码​

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    const map = {};
    for (let i = 0; i < nums.length; i++) {
        map[nums[i]] = (map[nums[i]] || 0) + 1;
    }

    const matrix = Object.entries(map);
    const arr = [];
    for (let i = 0; i < matrix.length; i++) {
        const [n, c] = matrix[i];
        if (!arr[c]) arr[c] = [];
        arr[c].push(+n);
    }

    const res = [];
    for (let i = arr.length - 1; i > -1; i--) {
        if (arr[i] && res.length < k) {
            res.push(...arr[i].slice(0, k - res.length));
        }
    }

    return res;
};

1、题干​

给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。

子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

示例 1：

输入：arr = [1,2,3,4], difference = 1
输出：4
解释：最长的等差子序列是 [1,2,3,4]。

示例 2：

输入：arr = [1,3,5,7], difference = 1
输出：1
解释：最长的等差子序列是任意单个元素。

示例 3：

输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出：4
解释：最长的等差子序列是 [7,5,3,1]。

提示：

• 1 <= arr.length <= 105
• -104 <= arr[i], difference <= 104

头回见到用哈希表做dp table，记录下。

代码​

/**
 * @param {number[]} arr
 * @param {number} d
 * @return {number}
 */
var longestSubsequence = function (arr, d) {
    let max = 1;
    const dp = {};
    for (let n of arr) {
        dp[n] = (dp[n - d] || 0) + 1;
        max = Math.max(max,dp[n]);
    }

    return max;
};

1、题干​

给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。

你必须找到一个内存复杂度优于 O(n2) 的解决方案。

示例 1：

输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出：13
解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13

示例 2：

输入：matrix = [[-5]], k = 1
输出：-5

提示：

• n == matrix.length
• n == matrix[i].length
• 1 <= n <= 300
• -109 <= matrix[i][j] <= 109
• 题目数据 保证 matrix 中的所有行和列都按 非递减顺序 排列
• 1 <= k <= n2

进阶：

• 你能否用一个恒定的内存(即 O(1) 内存复杂度)来解决这个问题?
• 你能在 O(n) 的时间复杂度下解决这个问题吗?这个方法对于面试来说可能太超前了，但是你会发现阅读这篇文章（ this paper ）很有趣。

代码​

/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(matrix, k) {
    while (matrix.length > 1) {
        const nums = [];
        const nums1 = matrix.shift();
        const nums2 = matrix.shift();

        let [k1, k2] = [0, 0];
        while (k1 < nums1.length || k2 < nums2.length) {
            if (k2 >= nums2.length || (k1 < nums1.length && nums1[k1] <= nums2[k2])) {
                nums.push(nums1[k1]);
                k1++;
                continue;
            }

            if (k1 >= nums1.length || (k2 < nums2.length && nums1[k1] > nums2[k2])) {
                nums.push(nums2[k2]);
                k2++;
            }
        }

        matrix.push(nums);
    }

    return matrix[0][k - 1];
};

1、题干​

Alice 有 n 枚糖，其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长，所以前去拜访了一位医生。

医生建议 Alice 要少摄入糖分，只吃掉她所有糖的 n / 2 即可（n 是一个偶数）。Alice 非常喜欢这些糖，她想要在遵循医生建议的情况下，尽可能吃到最多不同种类的糖。

给你一个长度为 n 的整数数组 candyType ，返回： Alice 在仅吃掉 n / 2 枚糖的情况下，可以吃到糖的 最多 种类数。

示例 1：

输入：candyType = [1,1,2,2,3,3]
输出：3
解释：Alice 只能吃 6 / 2 = 3 枚糖，由于只有 3 种糖，她可以每种吃一枚。

示例 2：

输入：candyType = [1,1,2,3]
输出：2
解释：Alice 只能吃 4 / 2 = 2 枚糖，不管她选择吃的种类是 [1,2]、[1,3] 还是 [2,3]，她只能吃到两种不同类的糖。

示例 3：

输入：candyType = [6,6,6,6]
输出：1
解释：Alice 只能吃 4 / 2 = 2 枚糖，尽管她能吃 2 枚，但只能吃到 1 种糖。

提示：

• n == candyType.length
• 2 <= n <= 104
• n 是一个偶数
• -105 <= candyType[i] <= 105

代码​

/**
 * @param {number[]} candyType
 * @return {number}
 */
var distributeCandies = function (candyType) {
    return Math.min(new Set(candyType).size, candyType.length / 2);
};