barbaraaa:D-CSDN博客

原创 [LeetCode 困难]1044. 最长重复子串

题目描述给出一个字符串 S，考虑其所有重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。返回任何具有最长可能长度的重复子串。（如果 S 不含重复子串，那么答案为 “”。）示例 1：输入："banana"输出："ana"示例 2：输入："abcd"输出："" 提示：2 <= S.length <= 10^5S 由小写英文字母组成。动态规划(超时)class Solution { public String longestDupSubstring

2021-02-25 21:20:24 418

原创 [LeetCode 困难]410. 分割数组的最大值

给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。示例 1：输入：nums = [7,2,5,10,8], m = 2输出：18解释：一共有四种方法将 nums 分割为 2 个子数组。其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。示例 2：输入：nums = [1,2,3,4,5], m = 2输出：9示例.

2021-02-25 18:22:09 309

原创 [LeetCode 困难二叉树]剑指 Offer 37. 序列化二叉树 297. 二叉树的序列化与反序列化

题目描述请实现两个函数，分别用来序列化和反序列化二叉树。示例: 你可以将以下二叉树： 1 / \ 2 3 / \ 4 5序列化为 "[1,2,3,null,null,4,5]"queue/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right;

2021-02-25 14:51:36 336 1

原创 [LeetCode 困难回溯]301. 删除无效的括号

题目描述删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。说明: 输入可能包含了除 ( 和 ) 以外的字符。示例 1:输入: "()())()"输出: ["()()()", "(())()"]示例 2:输入: "(a)())()"输出: ["(a)()()", "(a())()"]示例 3:输入: ")("输出: [""]回溯（计数）import java.util.*;public class Solution { private int len

2021-02-25 14:25:39 257

原创 [LeetCode 中等 BFS]286. 墙与门

题目描述你被给定一个 m × n 的二维网格 rooms ，网格中有以下三种可能的初始化值：-1 表示墙或是障碍物0 表示一扇门INF 无限表示一个空的房间。然后，我们用 231 - 1 = 2147483647 代表 INF。你可以认为通往门的距离总是小于 2147483647 的。你要给每个空房间位上填上该房间到最近门的距离，如果无法到达门，则填 INF 即可。示例 1：输入：rooms = [[2147483647,-1,0,2147483647],[2147483647,21474

2021-02-25 14:06:52 307 1

原创 [LeetCode 困难排序]493. 翻转对剑指 Offer 51. 数组中的逆序对

题目描述给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。你需要返回给定数组中的重要翻转对的数量。示例 1:输入: [1,3,2,3,1]输出: 2示例 2:输入: [2,4,3,5,1]输出: 3注意:给定数组的长度不会超过50000。输入数组中的所有数字都在32位整数的表示范围内。基于归并排序复杂度分析时间复杂度：O(NlogN)，其中 N 为数组的长度。空间复杂度：O(N)，其中

2021-02-25 13:40:34 258

原创 [LeetCode 中等排序]347. 前 K 个高频元素

题目描述给定一个非空的整数数组，返回其中出现频率前 k 高的元素。示例 1:输入: nums = [1,1,1,2,2,3], k = 2输出: [1,2]示例 2:输入: nums = [1], k = 1输出: [1] 提示：你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。你可以按任意顺序返回答案。

2021-02-25 12:03:47 158

原创 [LeetCode 中等前缀和]1352. 最后 K 个数的乘积

题目描述请你实现一个「数字乘积类」ProductOfNumbers，要求支持下述两种方法：add(int num)将数字 num 添加到当前数字列表的最后面。2. getProduct(int k)返回当前数字列表中，最后 k 个数字的乘积。你可以假设当前列表中始终至少包含 k 个数字。题目数据保证：任何时候，任一连续数字序列的乘积都在 32-bit 整数范围内，不会溢出。示例：输入：["ProductOfNumbers","add","add","add","add","ad

2021-02-24 23:57:16 159

原创 [LeetCode 中等动态规划]1191. K 次串联后最大子数组之和

题目描述给你一个整数数组 arr 和一个整数 k。首先，我们要对该数组进行修改，即把原数组 arr 重复 k 次。举个例子，如果 arr = [1, 2] 且 k = 3，那么修改后的数组就是 [1, 2, 1, 2, 1, 2]。然后，请你返回修改后的数组中的最大的子数组之和。注意，子数组长度可以是 0，在这种情况下它的总和也是 0。由于结果可能会很大，所以需要模（mod） 10^9 + 7 后再返回。示例 1：输入：arr = [1,2], k = 3输出：9示例 2：输入

2021-02-24 23:31:35 164

原创 [LeetCode 中等动态规划]516. 最长回文子序列

题目描述给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。示例 1:输入:"bbbab"输出:4一个可能的最长回文子序列为 "bbbb"。示例 2:输入:"cbbd"输出:2一个可能的最长回文子序列为 "bb"。提示：1 <= s.length <= 1000s 只包含小写英文字母动态规划class Solution { public int longestPalindrom

2021-02-24 23:02:31 128

原创 [LeetCode 中等链表]147. 对链表进行插入排序

题目描述对链表进行插入排序。插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。插入排序算法：插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。重复直到所有输入数据插入完为止。示例 1：输入: 4->2->1->3输出: 1-&gt

2021-02-24 19:31:32 172

原创 [LeetCode 中等 bfs]面试题 08.09. 括号

题目描述数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。示例 1：输入：n = 3输出：["((()))","(()())","(())()","()(())","()()()"]示例 2：输入：n = 1输出：["()"]提示：1 <= n <= 8递归BFSpublic class Solution { // 做减法 public List<String> generateParenthes

2021-02-24 19:14:45 118

原创 [LeetCode 困难单调栈]239. 滑动窗口最大值

题目描述给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。示例 1：输入：nums = [1,3,-1,-3,5,3,6,7], k = 3输出：[3,3,5,5,6,7]解释：滑动窗口的位置最大值--------------- -----[1 3 -1] -3 5 3 6 7

2021-02-24 18:57:01 202

原创 [LeetCode 中等]50. Pow(x, n)

题目描述实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。示例 1：输入：x = 2.00000, n = 10输出：1024.00000示例 2：输入：x = 2.10000, n = 3输出：9.26100示例 3：输入：x = 2.00000, n = -2输出：0.25000解释：2-2 = 1/22 = 1/4 = 0.25 提示：-100.0 < x < 100.0-231 <= n <= 231-1-104 &

2021-02-21 14:50:26 155

原创 [LeetCode 中等 DFS]417. 太平洋大西洋水流问题

题目描述给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。提示：输出坐标的顺序不重要m 和 n 都小于150示例：给定下面的 5x5 矩阵: 太平洋 ~ ~ ~ ~ ~ ~ 1 2 2 3 (5

2021-02-21 14:28:13 148

原创 [LeetCode 困难]295. 数据流的中位数

题目描述中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。例如，[2,3,4] 的中位数是 3[2,3] 的中位数是 (2 + 3) / 2 = 2.5设计一个支持以下两种操作的数据结构：void addNum(int num) - 从数据流中添加一个整数到数据结构中。double findMedian() - 返回目前所有元素的中位数。示例：addNum(1)addNum(2)findMedian() -> 1.5addNum(3)findMedi

2021-02-21 01:21:24 266

原创 [LeetCode 困难栈]726. 原子的数量

题目描述给定一个化学式formula（作为字符串），返回每种原子的数量。原子总是以一个大写字母开始，接着跟随0个或任意个小写字母，表示原子的名字。如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。例如，H2O 和 H2O2 是可行的，但 H1O2 这个表达是不可行的。两个化学式连在一起是新的化学式。例如 H2O2He3Mg4 也是化学式。一个括号中的化学式和数字（可选择性添加）也是化学式。例如 (H2O2) 和 (H2O2)3 是化学式。给定一个化学式，输出所有原

2021-02-21 00:15:56 157

原创 [LeetCode 中等]528. 按权重随机选择

题目描述给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。也就是说，选取下标 i 的概率为 w[i] / sum(w) 。示例 1：输入：["Solution","pic

2021-02-20 23:18:58 144

原创 [LeetCode 困难回溯]51. N 皇后

题目描述n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。示例 1：输入：n = 4输出：[[".Q…","…Q",“Q…”,"…Q."],["…Q.",“Q…”,"…Q",".Q…"]]解释：如上图所示，4 皇后问题存在两个不同的解法。示例 2：输入：n = 1输出：[[

2021-02-20 22:58:18 117

原创 [LeetCode 中等]76. 最小覆盖子串1249. 移除无效的括号

题目描述给你一个由 ‘(’、’)’ 和小写字母组成的字符串 s。你需要从字符串中删除最少数目的 ‘(’ 或者 ‘)’ （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。请返回任意一个合法字符串。有效「括号字符串」应当符合以下任意一条要求：空字符串或只包含小写字母的字符串可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」示例 1：输入：s = “lee(t©o)de)”输出：“le

2021-02-20 21:47:24 117

原创 [LeetCode 简单]剑指 Offer 09. 用两个栈实现队列

题目描述用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )示例 1：输入：[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”][[],[3],[],[]]输出：[null,null,3,-1]示例 2：输入：[“CQueue”,“deleteHead”,“appendTail

2021-02-20 20:19:11 117

原创 [LeetCode 简单]66. 加一

题目描述给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位，数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。示例 1：输入：digits = [1,2,3]输出：[1,2,4]解释：输入数组表示数字 123。示例 2：输入：digits = [4,3,2,1]输出：[4,3,2,2]解释：输入数组表示数字 4321。示例 3：输入：digits = [0]输出：[1]提示：1 <= d

2021-02-20 20:09:12 63

原创 [LeetCode 困难滑动窗口]76. 最小覆盖子串

题目描述给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。示例 1：输入：s = “ADOBECODEBANC”, t = “ABC”输出：“BANC”示例 2：输入：s = “a”, t = “a”输出：“a”提示：1 <= s.length, t.length <= 105s 和 t 由英文字母组成滑动窗口cl

2021-02-08 23:22:45 69

原创 [LeetCode 中等排序]215. 数组中的第K个最大元素

题目描述在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。示例 1:输入: [3,2,1,5,6,4] 和 k = 2输出: 5示例 2:输入: [3,2,3,1,2,4,5,5,6] 和 k = 4输出: 4说明:你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。利用快排的原理class Solution { public int findKthLargest(int[] nums, int

2021-02-08 19:45:24 61

原创 [LeetCode 中等链表]面试题 02.05. 链表求和

题目描述给定两个用链表表示的整数，每个节点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。示例：输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295输出：2 -> 1 -> 9，即912进阶：思考一下，假设这些数位是正向存放的，又该如何解决呢?示例：输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295

2021-02-05 00:52:41 126

原创 [LeetCode 中等动态规划]1143. 最长公共子序列

题目描述给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。若这两个字符串没有公共子序列，则返回 0。示例 1:输入：text1 = “abcde”, text2 =

2021-02-05 00:27:14 71

原创 [LeetCode 困难单调栈]84. 柱状图中最大的矩形

题目描述给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。示例:输入: [2,1,5,6,2,3]输出: 10暴力算法（超时）复杂度分析：时间复杂度：O(N^2) 这里 NN 是输入数组的长度。空间复杂度：O(1)。算每个正方形的横竖的最大面积

2021-02-03 02:10:47 172

原创 [leetcode 中等最大系列]85. 最大矩形 84. 柱状图中最大的矩形类似

题目描述给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。示例 1：输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]输出：6解释：最大矩形如上图所示。示例 2：输入：matrix = []输出：0示例 3：输入：matrix = [["0"]]输出：0示例

2021-02-03 00:49:23 239

原创 [leetcode 中等]6. Z 字形变换

题目描述将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：P A H NA P L S I I GY I R之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。请你实现这个将字符串进行指定行数变换的函数：string convert(string s, int numRows);示例 1：输入：s

2021-02-02 19:00:12 114

原创 [leetcode 中等字典序]179. 最大数

题目描述给定一组非负整数 nums，重新排列它们每个数字的顺序（每个数字不可拆分）使之组成一个最大的整数。注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。示例 1：输入：nums = [10,2]输出："210"示例 2：输入：nums = [3,30,34,5,9]输出："9534330"示例 3：输入：nums = [1]输出："1"示例 4：输入：nums = [10]输出："10" 提示：1 <= nums.length <=

2021-02-02 17:15:21 268

原创 [LeetCode 中等]134. 加油站

题目描述在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。说明: 如果题目有解，该答案即为唯一答案。输入数组均为非空数组，且长度相同。输入数组中的元素均为非负数。示例 1:输入: gas = [1,2,3,4,5]cost = [3,4,5,

2021-01-27 16:12:01 165

原创 [LeetCode 中等]8. 字符串转换整数 (atoi)

题目描述请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。函数 myAtoi(string s) 的算法如下：读入字符串并丢弃无用的前导空格检查第一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。确定最终结果是负数还是正数。如果两者都不存在，则假定结果为正。读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。将前面步骤读入的这些数字转换为整数（即，“1

2021-01-26 23:17:44 607

原创 [LeetCode 困难]135. 分发糖果

题目描述老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：每个孩子至少分配到 1 个糖果。评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。那么这样下来，老师至少需要准备多少颗糖果呢？示例 1：输入：[1,0,2]输出：5解释：你可以分别给这三个孩子分发 2、1、2 颗糖果。示例 2：输入：[1,2,2]输出：4解释：你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个

2021-01-26 22:52:53 161

原创 [LeetCode 中等二叉树的遍历]113. 路径总和 II

题目描述给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。说明: 叶子节点是指没有子节点的节点。示例:给定如下二叉树，以及目标和 sum = 22， 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1返回:[ [5,4,11,2], [

2021-01-26 18:48:06 72

原创 [LeetCode 简单双指针]26. 删除排序数组中的重复项

题目描述给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。示例 1:给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。你不需要考虑数组中超出新长度后面的元素。示例 2:给定 nums = [0,0,1,1,1,2,2,3,3,4],函数应该返回新的长度 5,

2021-01-26 16:53:37 63

原创 [LeetCode 困难子序列]128. 最长连续序列

题目描述给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。进阶：你可以设计并实现时间复杂度为 O(n) 的解决方案吗？示例 1：输入：nums = [100,4,200,1,3,2]输出：4解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。示例 2：输入：nums = [0,3,7,2,5,8,4,6,0,1]输出：9 提示：0 <= nums.length <= 104-109 <= num

2021-01-26 16:32:35 265

原创 [LeetCode 困难 DFS]329. 矩阵中的最长递增路径

题目描述给定一个整数矩阵，找出最长递增路径的长度。对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在对角线方向上移动或移动到边界外（即不允许环绕）。示例 1:输入: nums =[[9,9,4],[6,6,8],[2,1,1]]输出: 4解释: 最长递增路径为 [1, 2, 6, 9]。示例 2:输入: nums =[[3,4,5],[3,2,6],[2,2,1]]输出: 4解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

2021-01-26 15:58:54 83

原创 [LeetCode 困难贪心]45. 跳跃游戏 II

题目描述给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。示例:输入: [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。贪心class Solution { public int jump(int[] nums) { int length = num

2021-01-26 14:46:11 89

原创 [LeetCode 简单]剑指 Offer 29. 顺时针打印矩阵

题目描述输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。示例 1：输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[1,2,3,6,9,8,7,4,5]示例 2：输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]输出：[1,2,3,4,8,12,11,10,9,5,6,7]限制：0 <= matrix.length <= 1000 <= matrix[i].length <=

2021-01-20 21:30:38 54

原创 [LeetCode 中等链表]82. 删除排序链表中的重复元素 II

题目描述给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。示例 1:输入: 1->2->3->3->4->4->5输出: 1->2->5示例 2:输入: 1->1->1->2->3输出: 2->3三指针/** * Definition for singly-linked list. * public class ListNode { * int val;

2021-01-20 20:48:48 71

空空如也

空空如也