唯静美

唯有静下心来,才能发现美的存在!

前言

题目来自LeetCode:2367.算术三元组的数目

题目(难度:简单)(解法层层优化)

给你一个下标从 0 开始、严格递增 的整数数组 nums 和一个正整数 diff 。如果满足下述全部条件,则三元组 (i, j, k) 就是一个 算术三元组

  • i < j < k ,
  • nums[j] - nums[i] == diff 且
  • nums[k] - nums[j] == diff

返回不同 算术三元组 的数目。
示例 1:

输入:nums = [0,1,4,6,7,10], diff = 3
输出:2
解释
(1, 2, 4) 是算术三元组:7 - 4 == 3 且 4 - 1 == 3 。
(2, 4, 5) 是算术三元组:10 - 7 == 3 且 7 - 4 == 3 。

提示

  • 3 <= nums.length <= 200
  • 0 <= nums[i] <= 200
  • 1 <= diff <= 50
  • nums 严格 递增
    阅读全文 »

前言

题目来自LeetCode:1630.等差子数组

题目(难度:中等)

如果一个数列由至少两个元素组成,且每两个连续元素之间的差值都相同,那么这个序列就是 等差数列 。更正式地,数列 s 是等差数列,只需要满足:对于每个有效的 i , s[i+1] - s[i] == s[1] - s[0] 都成立。
例如,下面这些都是 等差数列

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

下面的数列 不是等差数列

1, 1, 2, 5, 7

给你一个由 n 个整数组成的数组 nums,和两个由 m 个整数组成的数组 l 和 r,后两个数组表示 m 组范围查询,其中第 i 个查询对应范围 [l[i], r[i]] 。所有数组的下标都是 从 0 开始 的。
返回 boolean 元素构成的答案列表 answer 。如果子数组 nums[l[i]], nums[l[i]+1], … , nums[r[i]] 可以 重新排列 形成 等差数列 ,answer[i] 的值就是 true;否则answer[i] 的值就是 false 。

示例 1

输入:nums = [4,6,5,9,3,7], l = [0,0,2], r = [2,3,5]
输出:[true,false,true]
解释
第 0 个查询,对应子数组 [4,6,5] 。可以重新排列为等差数列 [6,5,4] 。
第 1 个查询,对应子数组 [4,6,5,9] 。无法重新排列形成等差数列。
第 2 个查询,对应子数组 [5,9,3,7] 。可以重新排列为等差数列 [3,5,7,9] 。

阅读全文 »

前言

题目来自LeetCode:https://leetcode.cn/problems/numbers-with-repeated-digits/

题目(难度:困难)

给定正整数 n,返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。

示例1

输入:n = 20
输出:1
解释:具有至少 1 位重复数字的正数(<= 20)只有 11 。

示例 2

输入:n = 100
输出:10
解释:具有至少 1 位重复数字的正数(<= 100)有 11,22,33,44,55,66,77,88,99 和 100 。

提示

前言

题目来自LeetCode:https://leetcode.cn/problems/lexicographically-smallest-string-after-applying-operations/

题目(难度:中等)

给你一个字符串 s 以及两个整数 a 和 b 。其中,字符串 s 的长度为偶数,且仅由数字 0 到 9 组成。
你可以在 s 上按任意顺序多次执行下面两个操作之一:

  • 累加:将  a 加到 s 中所有下标为奇数的元素上 (下标从 0 开始)。数字一旦超过 9 就会变成 0,如此循环往复。例如,s = “3456” 且 a = 5,则执行此操作后 s 变成 “3951”。
  • 轮转:将 s 向右轮转 b 位。例如,s = “3456” 且 b = 1,则执行此操作后 s 变成 “6345”。

请你返回在 s 上执行上述操作任意次后可以得到的 字典序最小 的字符串。
如果两个字符串长度相同,那么字符串 a 字典序比字符串 b 小可以这样定义:在 a 和 b 出现不同的第一个位置上,字符串 a 中的字符出现在字母表中的时间早于 b 中的对应字符。例如,”0158” 字典序比 “0190” 小,因为不同的第一个位置是在第三个字符,显然 ‘5’ 出现在 ‘9’ 之前。
示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
输入:s = "5525", a = 9, b = 2
输出:"2050"
解释:执行操作如下:
初态:"5525"
轮转:"2555"
累加:"2454"
累加:"2353"
轮转:"5323"
累加:"5222"
累加:"5121"
轮转:"2151"
累加:"2050"​​​​​​​​​​​​
无法获得字典序小于 "2050" 的字符串。

提示:

  • 2 <= s.length <= 100
  • s.length 是偶数
  • s 仅由数字 0 到 9 组成
  • 1 <= a <= 9
  • 1 <= b <= s.length - 1
    阅读全文 »

前言

题目来自LeetCode:https://leetcode.cn/problems/split-two-strings-to-make-palindrome/

题目(难度:中等)

给你两个字符串 a 和 b ,它们长度相同。请你选择一个下标,将两个字符串都在 相同的下标 分割开。由 a 可以得到两个字符串: aprefix 和 asuffix ,满足 a = aprefix + asuffix ,同理,由 b 可以得到两个字符串 bprefix 和 bsuffix ,满足 b = bprefix + bsuffix 。请你判断 aprefix + bsuffix 或者 bprefix + asuffix 能否构成回文串。
当你将一个字符串 s 分割成 sprefix 和 ssuffix 时, ssuffix 或者 sprefix 可以为空。比方说, s = “abc” 那么 “” + “abc” , “a” + “bc” , “ab” + “c” 和 “abc” + “” 都是合法分割。
如果 能构成回文字符串 ,那么请返回 true,否则返回 false 。
注意, x + y 表示连接字符串 x 和 y 。
示例 1:

1
2
3
4
5
6
输入:a = "abdef", b = "fecab"
输出:true
解释:
aprefix = "abd", asuffix = "ef"
bprefix = "fec", bsuffix = "ab"
那么 bprefix + asuffix = "fec" + "ef" = "fecef" 是回文串。

提示:

  • 1 <= a.length, b.length <= 10^5
  • a.length == b.length
  • a 和 b 都只包含小写英文字母
    阅读全文 »

前言

题目来自LeetCode:https://leetcode.cn/problems/longest-subsequence-with-limited-sum/

题目(难度:简单)

给你一个长度为 n 的整数数组 nums ,和一个长度为 m 的整数数组 queries 。
返回一个长度为 m 的数组 answer ,其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列最大 长度  。
子序列 是由一个数组删除某些元素(也可以不删除)但不改变剩余元素顺序得到的一个数组。
示例1

1
2
3
4
5
6
输入:nums = [4,5,2,1], queries = [3,10,21]
输出:[2,3,4]
解释:queries 对应的 answer 如下:
- 子序列 [2,1] 的和小于或等于 3 。可以证明满足题目要求的子序列的最大长度是 2 ,所以 answer[0] = 2
- 子序列 [4,5,1] 的和小于或等于 10 。可以证明满足题目要求的子序列的最大长度是 3 ,所以 answer[1] = 3
- 子序列 [4,5,2,1] 的和小于或等于 21 。可以证明满足题目要求的子序列的最大长度是 4 ,所以 answer[2] = 4

提示:

  • n == nums.length
  • m == queries.length
  • 1 <= n, m <= 1000
  • 1 <= nums[i], queries[i] <= 10^6
    阅读全文 »

前言

题目来自LeetCode:https://leetcode.cn/problems/count-subarrays-with-median-k/

题目(难度:困难)

给你一个长度为 n 的数组 nums ,该数组由从 1 到 n 的 不同 整数组成。另给你一个正整数 k 。
统计并返回 nums 中的 中位数 等于 k 的非空子数组的数目。
注意:

  • 数组的中位数是按 递增 顺序排列后位于 中间 的那个元素,如果数组长度为偶数,则中位数是位于中间靠 的那个元素。
    • 例如,[2,3,1,4] 的中位数是 2 ,[8,4,3,5,1] 的中位数是 4 。
  • 子数组是数组中的一个连续部分。
    示例1:
    1
    2
    3
    输入:nums = [3,2,1,4,5], k = 4
    输出:3
    解释:中位数等于 4 的子数组有:[4]、[4,5] 和 [1,4,5] 。
    提示:
  • n == nums.length
  • 1 <= n <= 10^5
  • 1 <= nums[i], k <= n
  • nums 中的整数互不相同
    阅读全文 »

前言

题目来自LeetCode:https://leetcode.cn/problems/maximal-network-rank/

题目(难度:中等)

n 座城市和一些连接这些城市的道路 roads 共同组成一个基础设施网络。每个 roads[i] = [ai, bi] 都表示在城市 ai 和 bi 之间有一条双向道路。
两座不同城市构成的 城市对网络秩 定义为:与这两座城市 直接 相连的道路总数。如果存在一条道路直接连接这两座城市,则这条道路只计算 一次
整个基础设施网络的 最大网络秩 是所有不同城市对中的 最大网络秩
给你整数 n 和数组 roads,返回整个基础设施网络的 最大网络秩
示例1
示例1

1
2
3
输入:n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
输出:4
解释:城市 01 的网络秩是 4,因为共有 4 条道路与城市 01 相连。位于 01 之间的道路只计算一次。

提示:

  • 2 <= n <= 100
  • 0 <= roads.length <= n * (n - 1) / 2
  • roads[i].length == 2
  • 0 <= ai, bi <= n-1
  • ai != bi
  • 每对城市之间 最多只有一条 道路相连
    阅读全文 »

前言

题目来自LeetCode:https://leetcode.cn/problems/find-valid-matrix-given-row-and-column-sums/

题目(难度:中等)

给你两个非负整数数组 rowSum 和 colSum ,其中 rowSum[i] 是二维矩阵中第 i 行元素的和, colSum[j] 是第 j 列元素的和。换言之你不知道矩阵里的每个元素,但是你知道每一行和每一列的和。
请找到大小为 rowSum.length x colSum.length 的任意 非负整数 矩阵,且该矩阵满足 rowSum 和 colSum 的要求。
请你返回任意一个满足题目要求的二维矩阵,题目保证存在 至少一个 可行矩阵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
示例 1:
输入:rowSum = [3,8], colSum = [4,7]
输出:[[3,0],
[1,7]]
解释:
第 0 行:3 + 0 = 3 == rowSum[0]
第 1 行:1 + 7 = 8 == rowSum[1]
第 0 列:3 + 1 = 4 == colSum[0]
第 1 列:0 + 7 = 7 == colSum[1]
行和列的和都满足题目要求,且所有矩阵元素都是非负的。
另一个可行的矩阵为:[[1,2],
[3,5]]
提示:
1 <= rowSum.length, colSum.length <= 500
0 <= rowSum[i], colSum[i] <= 10e8
sum(rowSum) == sum(colSum)
阅读全文 »

前言

题目来自LeetCode:https://leetcode.cn/problems/minimum-hours-of-training-to-win-a-competition/

题目(难度:简单)

你正在参加一场比赛,给你两个 正 整数 initialEnergy 和 initialExperience 分别表示你的初始精力和初始经验。
另给你两个下标从 0 开始的整数数组 energy 和 experience,长度均为 n 。
你将会 依次 对上 n 个对手。第 i 个对手的精力和经验分别用 energy[i] 和 experience[i] 表示。当你对上对手时,需要在经验和精力上都 严格 超过对手才能击败他们,然后在可能的情况下继续对上下一个对手。
击败第 i 个对手会使你的经验 增加 experience[i],但会将你的精力 减少  energy[i] 。
在开始比赛前,你可以训练几个小时。每训练一个小时,你可以选择将增加经验增加 1 或者 将精力增加 1 。
返回击败全部 n 个对手需要训练的 最少 小时数目。

实例1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入:initialEnergy = 5, initialExperience = 3, energy = [1,4,3,2], experience = [2,6,3,1]
输出:8
解释:在 6 小时训练后,你可以将精力提高到 11 ,并且再训练 2 个小时将经验提高到 5 。
按以下顺序与对手比赛:
- 你的精力与经验都超过第 0 个对手,所以获胜。
精力变为:11 - 1 = 10 ,经验变为:5 + 2 = 7 。
- 你的精力与经验都超过第 1 个对手,所以获胜。
精力变为:10 - 4 = 6 ,经验变为:7 + 6 = 13 。
- 你的精力与经验都超过第 2 个对手,所以获胜。
精力变为:6 - 3 = 3 ,经验变为:13 + 3 = 16 。
- 你的精力与经验都超过第 3 个对手,所以获胜。
精力变为:3 - 2 = 1 ,经验变为:16 + 1 = 17 。
在比赛前进行了 8 小时训练,所以返回 8 。
可以证明不存在更小的答案。
阅读全文 »
0%