TIkitianya_社区达人页

2023年02月

• 02.08 17:56:57
  发表了文章 2023-02-08 17:56:57

  【每日一题Day104】LC2319判断矩阵是否是一个 X 矩阵 | 模拟

  思路：如果对角线的元素等于0或者其他元素不等于0，那么返回false
• 02.08 17:54:30
  发表了文章 2023-02-08 17:54:30

  【每日一题Day103】LC1669合并两个链表 | 模拟

  思路：遍历链表找到list1中的第a−1个节点和第b+1个节点，然后将第a−1个节点指向list2链表的初始节点，list2链表的尾节点指向list1中的第b+1个节点

  
• 02.08 17:52:49
  发表了文章 2023-02-08 17:52:49

  【每日一题Day102】LC2315统计星号 | 模拟

  思路：记录每个'|'的编号，统计第偶数个'|'之后、第奇数个'|'之前的星号，以及末尾剩余字符串的星号个数
• 02.08 17:50:58
  发表了文章 2023-02-08 17:50:58

  【每日一题Day101】LC1664生成平衡数组的方案数 | 预处理+枚举

  给你一个整数数组 nums 。你需要选择 恰好 一个下标（下标从 0 开始）并删除对应的元素。请注意剩下元素的下标可能会因为删除操作而发生改变。
• 02.08 17:42:03
  发表了文章 2023-02-08 17:42:03

  【每日一题Day100】LC2309兼具大小写的最好英文字母 | 哈希表 位运算

  实现：使用两个int类型变量记录每个字母的大小写是否出现过
• 02.08 17:38:17
  发表了文章 2023-02-08 17:38:17

  【每日一题Day99】LC1663具有给定数值的最小字符串 | 贪心

  如果k−(n−i)∗26<=1，那么表示尾部全部插入z，没有分数剩余甚至还有同于，那么第i个字符可以插入的最小字符'a'，贡献的分数为1
• 02.08 17:33:21
  发表了文章 2023-02-08 17:33:21

  【每日一题Day98】LCLC1632矩阵转换后的秩 | TreeMap+并查集

  然后遍历TreeMap，使用并查集处理存在相同元素时的情况，将元素分为几个连通块，对于每个连通块，里面所有元素对应的秩为这些行或列的最大秩加 1。
• 02.08 17:30:07
  发表了文章 2023-02-08 17:30:07

  【每日一题Day97】LC1828统计一个圆中点的数目 | 模拟

  思路：双重循环计算每个点到圆点的距离，如果小于等于半径，则证明在圆内
• 02.08 17:28:01
  发表了文章 2023-02-08 17:28:01

  【每日一题Day96】LC2303计算应缴税款总额 | 模拟

  若income<=bracket[0]，那么表示income遇到上限值，该段金额产生的税率为(income−pre)∗bracket[1]/100
• 02.08 17:24:54
  发表了文章 2023-02-08 17:24:54

  【每日一题Day95】LC1815得到新鲜甜甜圈的最多组数 | 状态压缩dp 记忆化搜索

  子问题、哪些操作会影响数据：余下的甜甜圈数量left，以及剩余可以选的元素个数 cnt[x]【dfs函数的两个参数->使用状态压缩至一个int类型变量中】

  
• 02.08 17:16:49
  发表了文章 2023-02-08 17:16:49

  【每日一题Day94】LC1824最少侧跳次数 | 贪心

  由于本题只有单条道路，道路的编号是1、2和3，因此贪心转移跑道时，可以使用6-当前跑道-最近有障碍的不是当前的跑道编号就可以得到转移的跑道编号
• 02.08 17:09:33
  发表了文章 2023-02-08 17:09:33

  【每日一题Day93】LC1817查找用户活跃分钟数 | 哈希表

  思路：使用哈希表记录每个用户的活跃时间，那么用户活跃分钟数则为活跃时间的多少，因此哈希表的key值为用户id，value值为Set集合
• 02.08 17:06:29
  发表了文章 2023-02-08 17:06:29

  周赛328总结

  • 找出 左上角 为 (row1i, col1i) 且 右下角 为 (row2i, col2i) 的子矩阵，将子矩阵中的 每个元素 加 1 。也就是给所有满足 row1i <= x <= row2i 和 col1i <= y <= col2i 的 mat[x][y] 加 1 。
• 02.08 16:55:40
  发表了文章 2023-02-08 16:55:40

  二维前缀和数组&二维差分数组

  二维差分数组div中的每一个格子记录的是「以当前位置为区域的左上角（区域右下角恒定为原数组的右下角）的值的变化量」【应该不固定 可以倒转】

  
• 02.08 16:39:22
  发表了文章 2023-02-08 16:39:22

  【每日一题Day92】LC2299强密码检验器 II | 模拟 状态压缩

  思路：首先判断密码长度是否大于等于8，若是则判断该密码是否包含至少一个数字、小写字母、大写字母以及特殊字符，并相邻字符不相同，若满足条件则返回true。
• 02.08 16:37:30
  发表了文章 2023-02-08 16:37:30

  【每日一题Day91】LC1825求出 MK 平均值 | 有序集合+模拟

  思路：排序后的数组可以分为三个部分：较小的前k个元素、中间元素、前大的后k个元素，因此使用3个有序集合存储这三个部分。在加入元素时，判断元素的个数以及元素的大小移动元素，时间复杂度为O(logm)；在求平均值时，直接求取中间元素的平均值，时间复杂度为O ( 1 )
• 02.08 16:33:06
  发表了文章 2023-02-08 16:33:06

  【每日一题Day90】LC1814统计一个数组中好对子的数目 | 哈希表

  思路：如果两个数满足好对子，那么这两个数反转后的变化量相同。因此可以使用哈希表存放反转后的变化量及其次数count，该变化量存在的所有好对子个数为count∗(count−1)/2
• 02.08 16:29:44
  发表了文章 2023-02-08 16:29:44

  【每日一题Day89】LC1813句子相似性 III | 双指针

  思路：由于插入的句子一定插入在字符串的中间（字符串左边或者右边可能为空），因此可以先用空格分隔所有的单词，然后统计左边相等单词的数量，再统计右边相等单词的数量，若两个数量之和等于最小单词数量，那么代表可以向这个字符串中添加一句话使得两个字符串相等
• 02.08 16:26:19
  发表了文章 2023-02-08 16:26:19

  【每日一题Day88】LC2293极大极小游戏 | 模拟 递归

  思路：数组中的元素被使用过就不再被使用，因此可以将第i ii对计算得到的结果，存储至nums[i]
• 02.08 16:22:16
  发表了文章 2023-02-08 16:22:16

  【每日一题Day87】LC1819序列中不同最大公约数的数 | 数学

  由于数组中的最大公约数不可能超过子序列的最大值，因此可以枚举所有可能的最大公约数来判断当前的公约数是否有子序列构成。
• 02.08 16:18:47
  发表了文章 2023-02-08 16:18:47

  【每日一题Day86】LC2287 重排字符形成目标字符串 | 哈希表

  思路：使用两个哈希表记录两个字符串中字符出现的次数，假设某个字符的在s和target中出现次数分别为a和b ，那么该字母可被重排的次数为⌊ a/ b ⌋ ，target可以被重排的次数为所有字母可被重排的最小值。
• 02.08 16:16:23
  发表了文章 2023-02-08 16:16:23

  【每日一题Day85】LC1807 替换字符串中的括号内容 | 哈希表 双指针

  如果当前字符不是左括号，那么将其直接放入结果末尾；如果是左括号，那么搜索括号内的单词，然后进行替换。
• 02.08 16:13:54
  发表了文章 2023-02-08 16:13:54

  【每日一题Day84】LC2283判断一个数的数字计数是否等于数位的值 | 哈希表

  思路：使用哈希表统计每个数字出现的次数，再与字符串中的次数进行比较，如果所有数字次数均等于字符串中的次数，返回true；反之，返回false
• 02.08 16:10:53
  发表了文章 2023-02-08 16:10:53

  周赛327总结

  workL：新仓库正在放箱的工人【在当前时间之前的所有工人均以完成事件，因此根据时间从小到大排序】
• 02.08 16:01:08
  发表了文章 2023-02-08 16:01:08

  【每日一题Day83】LC753破解保险箱 | dfs 贪心

  题意要求输入一个字符串，能够打开保险柜，密码的长度为n，每位数字小于k，因此题意可以转化为找到一个最短字符串，其包含了n位k进制所有的排列组合
• 02.08 15:55:04
  发表了文章 2023-02-08 15:55:04

  【每日一题Day82】LC1806还原排列的最少操作步数 | 模拟

  思路：按照题意进行变换，直至数组变为原始数组，记录变换次数
• 02.08 15:52:49
  发表了文章 2023-02-08 15:52:49

  【每日一题Day81】LC2185统计包含给定前缀的字符串 | 模拟

  思路：判断每一个word是否以prefix开头，最后返回满足条件的单词数量。
• 02.08 15:51:08
  发表了文章 2023-02-08 15:51:08

  【每日一题Day80】LC1658将 x 减到 0 的最小操作数 | 滑动窗口

  假设左侧取到nums[i]，右侧取到nums[j]，由于和一定，因此随着i 的增大，j也会增大，因此可以先记录符合条件的i的最小位置，然后从大到小枚举j，并使i尽可能左移，当sum==x时，更新最小长度。
• 02.08 15:44:11
  发表了文章 2023-02-08 15:44:11

  【每日一题Day78】LC1803统计异或值在范围内的数对有多少 | 字典树+容斥原理

  不过如果在工程中，不考虑前缀匹配的话，基本上使用 hash 就能满足。如果考虑前缀匹配的话，工程也不会使用 Trie 。一方面是字符集大小不好确定，另外，对于个别的超长字符 Trie 会进一步变深。

  
• 02.08 15:32:06
  发表了文章 2023-02-08 15:32:06

  【每日一题Day77】LC1802有界数组中指定下标处的最大值 | 二分查找+贪心

  当数组和一定时，要使指定下标处的数值最大，应以该位置为中心，相邻位置以1为间隔梯度下降，直至数值等于1【贪心获得数组和】
• 02.08 15:28:01
  发表了文章 2023-02-08 15:28:01

  【每日一题Day76】LC2042检查句子中的数字是否递增 | 模拟

  • 思路：通过split函数获得以空格为分割符的子字符串，判断当前子字符串首字母是否为数字，若是数字，那么与之前出现的数字进行比较，如果不为递增顺序，返回false
• 02.08 15:22:08
  发表了文章 2023-02-08 15:22:08

  【每日一题Day75】LC1801积压订单中的订单总数 | 优先队列

  思路：使用两个优先队列存储类型为buy或者sell的积压订单，根据规则删除积压订单，并统计积压订单的数量，最后返回结果即可
• 02.08 15:19:21
  发表了文章 2023-02-08 15:19:21

  周赛326总结

  优化：不需要判断i是否是质因数，因为num已经用前面的i 分解了，所以从小到大用i 能够整除num时，i一定是num的质因数

  
• 02.08 15:11:02
  发表了文章 2023-02-08 15:11:02

  【每日一题Day74】LC2351第一个出现两次的字母 | 哈希表 位运算

  思路：使用哈希表统计出现的字母及其次数，当某个字母出现次数为2时立即返回
• 02.08 15:06:08
  发表了文章 2023-02-08 15:06:08

  【每日一题Day72】LC855考场就座 | 构造数据结构 动态数组+二分查找

  可以使用哈希表记录每个座位是否有人入座，但是当n很大时，每次在搜索距离的时候，不可避免的会搜索到未就座的座位，时间复杂度为O(n)；因此我使用动态数组isSeated记录已经就座的座位序号，并手动保证数组为升序排列（也可以使用TreeSet 做的时候没想到…），然后遍历数组，按照规律就座以及移除座位序号。

  
• 02.08 15:00:45
  发表了文章 2023-02-08 15:00:45

  【每日一题Day71】LC2032至少在两个数组中出现的值 | 哈希表 + 位运算

  思路：使用一个哈希表记录每个数字在三个数组中的出现情况，哈希表的key值为数值大小，value值为该数字在数组中的出现情况，从左到右第i位为1则表示该数字在第i个数组中出现过。最后根据value值将至少出现在两个数组中的num添加至结果集
• 02.08 14:58:30
  发表了文章 2023-02-08 14:58:30

  【每日一题Day70】LC1750删除字符串两端相同字符后的最短长度 | 双指针模拟+贪心

  思路：使用双指针定位左右两端的字符，当左右两端的字符相同时，删除所有能够删除的相同字符[有一点贪心]，将左指针右移，将右指针左移；当左右两端字符不相同时，不能够进行删除操作，最后返回左右指针中间的字符串长度即可
• 02.08 14:56:49
  发表了文章 2023-02-08 14:56:49

  【每日一题Day69】转换字符串的最少操作次数 |贪心

  实现：遍历整个字符串，如果当前字符为’X’，那么进行转换，指针后移三位；如果当前字符为’O’，那么指针后移一位
• 02.08 14:55:07
  发表了文章 2023-02-08 14:55:07

  【每日一题Day68】LC1759 统计同构字符串的数目 | 数学

  思路：统计以每个字符为末尾的同构子字符串的最长长度j ，那么根据排列组合原理，以其为末尾的同构子字符串的数目为j个，累加可得最终结果
• 02.08 14:51:43
  发表了文章 2023-02-08 14:51:43

  【每日一题Day67】LC1739放置盒子 | 找规律+贪心 二分查找

  有一个立方体房间，其长度、宽度和高度都等于 n 个单位。请你在房间里放置 n 个盒子，每个盒子都是一个单位边长的立方体。

  
• 02.08 14:42:40
  发表了文章 2023-02-08 14:42:40

  【每日一题Day66】LC1754构造字典序最大的合并字符串 | 贪心 双指针模拟

  思路：双指针遍历两个字符串，贪心比较字符的字典顺序，并添加至结果集

  
• 02.08 14:39:22
  发表了文章 2023-02-08 14:39:22

  【每日一题Day65】LC2011执行操作后的变量值 | 模拟

  思路：遍历整个数组，模拟加一和减一的操作，最后返回结果。进行加一或者减一的操作取决于字符串的第二个字符：
• 02.08 14:37:29
  发表了文章 2023-02-08 14:37:29

  【每日一题Day64】LC1799N 次操作后的最大分数和 | 状态压缩dp 状态压缩+dfs+记忆化搜索

  每个数字有两种状态，删除或者未删除，因此可以使用状态压缩记录未删除的数字情况state，便于使用位运算进行状态的遍历及转移；使用状态压缩dp找到将所以数字删除的最大分数

  
• 02.08 14:29:16
  发表了文章 2023-02-08 14:29:16

  【每日一题Day63】LC1753移除石子的最大得分 | 贪心 + 数学

  当对a,b,c进行升序排序后，如果a+b≥c，应先优先让a 和b去匹配，匹配的次数为a+b−c，得分为count=⌈(a+b−c)/2⌉
• 02.08 14:26:12
  发表了文章 2023-02-08 14:26:12

  【每日一题Day62】LC1760袋子里最少数目的球 | 二分查找

  首先，将题意转化为，当操作次数一定时，求出单个袋子里球的数目的最大值的最小值y yy，那么可以通过二分查找的方法找到最终的y yy，二分查找的下限为1，上限为数组nums中的最大值

  
• 02.08 14:20:34
  发表了文章 2023-02-08 14:20:34

  【每日一题Day61】寻找图中是否存在路径 | BFS 并查集

  初始时将source设为已访问，并且将其加入队列。之后每次将队列中的节点出队，并将其能够到达的未访问过的节点入队。如果访问到destination，则直接返回true；如果队列为空，仍未访问到destination，则返回false
• 02.08 14:16:34
  发表了文章 2023-02-08 14:16:34

  【每日一题Day60】LC1703得到连续 K 个 1 的最少相邻交换次数 | 中位数贪心

  局部最优：x位于区间[p[0],p[k−1]]内部时【无论位于哪个位置】，到p[0]和p[k−1]的距离是定值p[k−1]−p[0]，因此应使x xx位于所有区间的内部即中位数，使x xx到所有区间的距离为定值，此时能够达到全局最优

  
• 02.08 13:03:27
  发表了文章 2023-02-08 13:03:27

  【每日一题Day59】LC1764通过连接另一个数组的子数组得到一个数组 | 双指针模拟

  如果不存在下标为 k 的元素 nums[k] 属于不止一个子数组，就称这些子数组是 不相交 的。子数组指的是原数组中连续元素组成的一个序列。
• 02.08 13:00:36
  发表了文章 2023-02-08 13:00:36

  【每日一题Day58】LC1785构成特定和添加的最少元素 | 贪心

  思路：首先统计数组nums的和sum，然后计算sum与goal的差target，我们需要向数组中添加最少的元素，使元素的和满足差值，元素的个数即为最终结果，因此每次添加的元素应尽可能最大。由于添加数值的绝对值大小受limit限制，因此添加元素的数值绝对值为limit的个数为Math.abs(target)/limit，如果Math.abs(target)不等于0，那么还需添加一个元素使和等于target