Leetcode Daily Question
2.46K subscribers
517 files
2.16K links
Why are you asking me to do Leetcode for this CSS job?
Download Telegram
Leetcode-cn.com 2022-06-06
🔴 732.my-calendar-iii

🏷️ Tags
#design #segment_tree #ordered_set

Description
k 个日程安排有一些时间上的交叉时(例如 k 个日程安排都在同一时间内),就会产生 k 次预订。

给你一些日程安排 [start, end) ,请你在每个日程安排添加后,返回一个整数 k ,表示所有先前日程安排会产生的最大 k 次预订。

实现一个 MyCalendarThree 类来存放你的日程安排,你可以一直添加新的日程安排。


MyCalendarThree() 初始化对象。
int book(int start, int end) 返回一个整数 k ,表示日历中存在的 k 次预订的最大值。


 

Example
输入:
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
输出:
[null, 1, 1, 2, 3, 3, 3]

解释:
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // 返回 1 ,第一个日程安排可以预订并且不存在相交,所以最大 k 次预订是 1 次预订。
myCalendarThree.book(50, 60); // 返回 1 ,第二个日程安排可以预订并且不存在相交,所以最大 k 次预订是 1 次预订。
myCalendarThree.book(10, 40); // 返回 2 ,第三个日程安排 [10, 40) 与第一个日程安排相交,所以最大 k 次预订是 2 次预订。
myCalendarThree.book(5, 15); // 返回 3 ,剩下的日程安排的最大 k 次预订是 3 次预订。
myCalendarThree.book(5, 10); // 返回 3
myCalendarThree.book(25, 55); // 返回 3
Leetcode-cn.com 2022-06-07
🟡 875.koko-eating-bananas

🏷️ Tags
#array #binary_search

Description
珂珂喜欢吃香蕉。这里有 n 堆香蕉,第 i 堆中有 piles[i] 根香蕉。警卫已经离开了,将在 h 小时后回来。

珂珂可以决定她吃香蕉的速度 k (单位:根/小时)。每个小时,她将会选择一堆香蕉,从中吃掉 k 根。如果这堆香蕉少于 k 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 h 小时内吃掉所有香蕉的最小速度 kk 为整数)。

Example
输入:piles = [3,6,7,11], h = 8
输出:4
Leetcode-cn.com 2022-06-09
🟡 497.random-point-in-non-overlapping-rectangles

🏷️ Tags
#reservoir_sampling #math #binary_search #ordered_set #prefix_sum #randomized

Description
给定一个由非重叠的轴对齐矩形的数组 rects ,其中 rects[i] = [ai, bi, xi, yi] 表示 (ai, bi) 是第 i 个矩形的左下角点,(xi, yi) 是第 i 个矩形的右上角角点。设计一个算法来随机挑选一个被某一矩形覆盖的整数点。矩形周长上的点也算做是被矩形覆盖。所有满足要求的点必须等概率被返回。

在一个给定的矩形覆盖的空间内任何整数点都有可能被返回。

请注意 ,整数点是具有整数坐标的点。

实现 Solution 类:


Solution(int[][] rects) 用给定的矩形数组 rects 初始化对象。
int[] pick() 返回一个随机的整数点 [u, v] 在给定的矩形所覆盖的空间内。





Example
输入: 
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
输出:
[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]

解释:
Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
solution.pick(); // 返回 [1, -2]
solution.pick(); // 返回 [1, -1]
solution.pick(); // 返回 [-1, -2]
solution.pick(); // 返回 [-2, -2]
solution.pick(); // 返回 [0, 0]
Leetcode-cn.com 2022-06-10
🔴 730.count-different-palindromic-subsequences

🏷️ Tags
#string #dynamic_programming

Description
给定一个字符串 s,返回 s 中不同的非空「回文子序列」个数 。

通过从 s 中删除 0 个或多个字符来获得子序列。

如果一个字符序列与它反转后的字符序列一致,那么它是「回文字符序列」。

如果有某个 i , 满足 ai != bi ,则两个序列 a1, a2, ...b1, b2, ... 不同。

注意:


结果可能很大,你需要对 109 + 7 取模 。


Example
输入:s = 'bccb'
输出:6
解释:6 个不同的非空回文子字符序列分别为:'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
注意:'bcb' 虽然出现两次但仅计数一次。
Leetcode-cn.com 2022-06-11
🟡 926.flip-string-to-monotone-increasing

🏷️ Tags
#string #dynamic_programming

Description
如果一个二进制字符串,是以一些 0(可能没有 0)后面跟着一些 1(也可能没有 1)的形式组成的,那么该字符串是 单调递增 的。

给你一个二进制字符串 s,你可以将任何 0 翻转为 1 或者将 1 翻转为 0

返回使 s 单调递增的最小翻转次数。

Example
输入:s = "00110"
输出:1
解释:翻转最后一位得到 00111.
Leetcode-cn.com 2022-06-12
🟡 890.find-and-replace-pattern

🏷️ Tags
#array #hash_table #string

Description
你有一个单词列表 words 和一个模式 pattern,你想知道 words 中的哪些单词与模式匹配。

如果存在字母的排列 p ,使得将模式中的每个字母 x 替换为 p(x) 之后,我们就得到了所需的单词,那么单词与模式是匹配的。

(回想一下,字母的排列是从字母到字母的双射:每个字母映射到另一个字母,没有两个字母映射到同一个字母。)

返回 words 中与给定模式匹配的单词列表。

你可以按任何顺序返回答案。

Example
输入:words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
输出:["mee","aqq"]
解释:
"mee" 与模式匹配,因为存在排列 {a -> m, b -> e, ...}。
"ccc" 与模式不匹配,因为 {a -> c, b -> c, ...} 不是排列。
因为 a 和 b 映射到同一个字母。
Leetcode-cn.com 2022-06-13
🟢 1051.height-checker

🏷️ Tags
#array #counting_sort #sorting

Description
学校打算为全体学生拍一张年度纪念照。根据要求,学生需要按照 非递减 的高度顺序排成一行。

排序后的高度情况用整数数组 expected 表示,其中 expected[i] 是预计排在这一行中第 i 位的学生的高度(下标从 0 开始)。

给你一个整数数组 heights ,表示 当前学生站位 的高度情况。heights[i] 是这一行中第 i 位学生的高度(下标从 0 开始)。

返回满足 heights[i] != expected[i] 的 下标数量 。

Example
输入:heights = [1,1,4,2,1,3]
输出:3
解释:
高度:[1,1,4,2,1,3]
预期:[1,1,1,2,3,4]
下标 2 、4 、5 处的学生高度不匹配。
Leetcode-cn.com 2022-06-14
🟡 498.diagonal-traverse

🏷️ Tags
#array #matrix #simulation

Description
给你一个大小为 m x n 的矩阵 mat ,请以对角线遍历的顺序,用一个数组返回这个矩阵中的所有元素。

Example
输入:mat = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,4,7,5,3,6,8,9]
Leetcode-cn.com 2022-06-15
🔴 719.find-k-th-smallest-pair-distance

🏷️ Tags
#array #two_pointers #binary_search #sorting

Description
数对 (a,b) 由整数 ab 组成,其数对距离定义为 ab 的绝对差值。

给你一个整数数组 nums 和一个整数 k ,数对由 nums[i]nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。

Example
输入:nums = [1,3,1], k = 1
输出:0
解释:数对和对应的距离如下:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
距离第 1 小的数对是 (1,1) ,距离为 0 。
Leetcode-cn.com 2022-06-16
🟡 532.k-diff-pairs-in-an-array

🏷️ Tags
#array #hash_table #two_pointers #binary_search #sorting

Description
给定一个整数数组和一个整数 k,你需要在数组里找到 不同的 k-diff 数对,并返回不同的 k-diff 数对 的数目。

这里将 k-diff 数对定义为一个整数对 (nums[i], nums[j]),并满足下述全部条件:


0 <= i < j < nums.length
|nums[i] - nums[j]| == k


注意,|val| 表示 val 的绝对值。

Example
输入:nums = [3, 1, 4, 1, 5], k = 2
输出:2
解释:数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。
尽管数组中有两个1,但我们只应返回不同的数对的数量。
Leetcode-cn.com 2022-06-17
🟢 1089.duplicate-zeros

🏷️ Tags
#array #two_pointers

Description
给你一个长度固定的整数数组 arr,请你将该数组中出现的每个零都复写一遍,并将其余的元素向右平移。

注意:请不要在超过该数组长度的位置写入元素。

要求:请对输入的数组 就地 进行上述修改,不要从函数返回任何东西。

Example
输入:[1,0,2,3,0,4,5,0]
输出:null
解释:调用函数后,输入的数组将被修改为:[1,0,0,2,3,0,0,4]
Leetcode-cn.com 2022-06-18
🟡 剑指 Offer II 029.4ueAj6

🏷️ Tags
#linked_list

Description
给定循环单调非递减列表中的一个点,写一个函数向这个列表中插入一个新元素 insertVal ,使这个列表仍然是循环升序的。

给定的可以是这个列表中任意一个顶点的指针,并不一定是这个列表中最小元素的指针。

如果有多个满足条件的插入位置,可以选择任意一个位置插入新的值,插入后整个列表仍然保持有序。

如果列表为空(给定的节点是 null),需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。

Example
输入:head = [3,4,1], insertVal = 2
输出:[3,4,1,2]
解释:在上图中,有一个包含三个元素的循环有序列表,你获得值为 3 的节点的指针,我们需要向表中插入元素 2 。新插入的节点应该在 1 和 3 之间,插入之后,整个列表如上图所示,最后返回节点 3 。
Leetcode-cn.com 2022-06-19
🟡 508.most-frequent-subtree-sum

🏷️ Tags
#tree #depth_first_search #hash_table #binary_tree

Description
给你一个二叉树的根结点 root ,请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同,返回所有出现次数最多的子树元素和(不限顺序)。

一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和(包括结点本身)。

Example
输入: root = [5,2,-3]
输出: [2,-3,4]
Leetcode-cn.com 2022-06-20
🔴 715.range-module

🏷️ Tags
#design #segment_tree #ordered_set

Description
Range模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为 半开区间 的范围并查询它们。

半开区间 [left, right) 表示所有 left <= x < right 的实数 x

实现 RangeModule 类:


RangeModule() 初始化数据结构的对象。
void addRange(int left, int right) 添加 半开区间 [left, right),跟踪该区间中的每个实数。添加与当前跟踪的数字部分重叠的区间时,应当添加在区间 [left, right) 中尚未跟踪的任何数字到该区间中。
boolean queryRange(int left, int right) 只有在当前正在跟踪区间 [left, right) 中的每一个实数时,才返回 true ,否则返回 false
void removeRange(int left, int right) 停止跟踪 半开区间 [left, right) 中当前正在跟踪的每个实数。


Example
输入
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
输出
[null, null, null, true, false, true]

解释
RangeModule rangeModule = new RangeModule();
rangeModule.addRange(10, 20);
rangeModule.removeRange(14, 16);
rangeModule.queryRange(10, 14); 返回 true (区间 [10, 14) 中的每个数都正在被跟踪)
rangeModule.queryRange(13, 15); 返回 false(未跟踪区间 [13, 15) 中像 14, 14.03, 14.17 这样的数字)
rangeModule.queryRange(16, 17); 返回 true (尽管执行了删除操作,区间 [16, 17) 中的数字 16 仍然会被跟踪)
Leetcode-cn.com 2022-06-22
🟡 513.find-bottom-left-tree-value

🏷️ Tags
#tree #depth_first_search #breadth_first_search #binary_tree

Description
给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

 

Example
输入: root = [2,1,3]
输出: 1
Leetcode-cn.com 2022-06-23
🔴 30.substring-with-concatenation-of-all-words

🏷️ Tags
#hash_table #string #sliding_window

Description
给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配,中间不能有其他字符 ,但不需要考虑 words 中单词串联的顺序。

 

Example
输入:s = "barfoothefoobarman", words = ["foo","bar"]
输出:[0,9]
解释:
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
Leetcode-cn.com 2022-06-24
🟡 515.find-largest-value-in-each-tree-row

🏷️ Tags
#tree #depth_first_search #breadth_first_search #binary_tree

Description
给定一棵二叉树的根节点 root ,请找出该二叉树中每一层的最大值。

Example
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
Leetcode-cn.com 2022-06-25
🟡 剑指 Offer II 091.JEj789

🏷️ Tags
#array #dynamic_programming

Description
假如有一排房子,共 n 个,每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种,你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然,因为市场上不同颜色油漆的价格不同,所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。

例如,costs[0][0] 表示第 0 号房子粉刷成红色的成本花费;costs[1][2] 表示第 1 号房子粉刷成绿色的花费,以此类推。

请计算出粉刷完所有房子最少的花费成本。

Example
输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色,1 号房子粉刷成绿色,2 号房子粉刷成蓝色。
最少花费: 2 + 5 + 3 = 10。
Leetcode-cn.com 2022-06-26
🔴 710.random-pick-with-blacklist

🏷️ Tags
#hash_table #math #binary_search #sorting #randomized

Description
给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法,从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。

优化你的算法,使它最小化调用语言 内置 随机函数的次数。

实现 Solution 类:


Solution(int n, int[] blacklist) 初始化整数 n 和被加入黑名单 blacklist 的整数
int pick() 返回一个范围为 [0, n - 1] 且不在黑名单 blacklist 中的随机整数


Example
输入
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
输出
[null, 0, 4, 1, 6, 1, 0, 4]

解释
Solution solution = new Solution(7, [2, 3, 5]);
solution.pick(); // 返回0,任何[0,1,4,6]的整数都可以。注意,对于每一个pick的调用,
// 0、1、4和6的返回概率必须相等(即概率为1/4)。
solution.pick(); // 返回 4
solution.pick(); // 返回 1
solution.pick(); // 返回 6
solution.pick(); // 返回 1
solution.pick(); // 返回 0
solution.pick(); // 返回 4