- 博客(267)
- 收藏
- 关注
RSS订阅原创 92. 反转链表 II（java链表）
题目反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明:1 ≤ m ≤ n ≤ 链表长度。示例:输入: 1->2->3->4->5->NULL, m = 2, n = 4输出: 1->4->3->2->5->NULL代码/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode n
2020-10-15 15:40:48
556
原创 91. 解码方法（字符串）
题目一条包含字母 A-Z 的消息通过以下方式进行了编码：'A' -> 1'B' -> 2...'Z' -> 26给定一个只包含数字的 非空 字符串，请计算解码方法的总数。题目数据保证答案肯定是一个 32 位的整数。示例 1：输入："12"输出：2解释：它可以解码为 "AB"（1 2）或者 "L"（12）。示例 2：输入："226"输出：3解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。示例 3
2020-10-15 15:12:13
724
原创 90. 子集 II（技巧）
题目给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明： 解集不能包含重复的子集。示例:输入: [1,2,2]输出:[ [2], [1], [1,2,2], [2,2], [1,2], []]思路首先应该想到的是 dfsdfsdfs，每一步递归得到的路径都是一种子集，这样一来，去重就变得简单了；在这一思路的基础上，重复的子集是这样产生的，递归的同一层如果存在相同的元素，那么以这些相同元素为双亲节点的子树一定是相同的，所以我们的去
2020-10-15 14:26:49
377
原创 88. 合并两个有序数组（技巧）
题目给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中_，_使 nums1 成为一个有序数组。说明：初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。示例：输入：nums1 = [1,2,3,0,0,0], m = 3nums2 = [2,5,6], n = 3输出：[1,2,2,3,5,6]提示：-10^
2020-10-14 15:05:54
274
原创 87. 扰乱字符串（动态规划）
题目给定一个字符串 s1，我们可以把它递归地分割成两个非空子字符串，从而将其表示为二叉树。下图是字符串 s1 = "great" 的一种可能的表示形式。 great / \ gr eat / \ / \g r e at / \ a t在扰乱这个字符串的过程中，我们可以挑选任何一个非叶节点，然后交换它的两个子节点。例如，如果我们挑选非叶节点 "gr" ，交换它的两个子节点，将会产生扰乱字符串 "rgeat"
2020-10-13 14:58:01
237
原创 86. 分隔链表（java链表）
题目给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。示例:输入: head = 1->4->3->2->5->2, _x_ = 3输出: 1->2->2->4->3->5代码/** * Definition for singly-linked list. * public class ListNode { * int va
2020-10-07 20:53:05
142
原创 85. 最大矩形（单调栈）
题目给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。示例:输入:[ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"]]输出: 6思路这个题可以看成上一题 84. 柱状图中最大的矩形（单调栈） 的拓展，我们一行一行的来分析这个矩阵：第一行：[1, 0, 1, 0, 0]；第一至二行：[2, 0, 2,
2020-10-07 20:09:41
152
原创 84. 柱状图中最大的矩形（单调栈）
题目给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。示例:输入: [2,1,5,6,2,3]输出: 10思路一这里先介绍暴力解法，后续优化版将基于暴力解法为基础，先依次遍历每个木块，对于木块 i，我们分别向前向后查找高度小于木块 i，得到下标 lef
2020-10-07 16:29:52
267
原创 83. 删除排序链表中的重复元素（java链表）
题目给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。示例 1:输入: 1->1->2输出: 1->2示例 2:输入: 1->1->2->3->3输出: 1->2->3代码/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int
2020-10-07 14:06:40
150
原创 82. 删除排序链表中的重复元素 II（java链表）
目录给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。示例 1:输入: 1->2->3->3->4->4->5输出: 1->2->5示例 2:输入: 1->1->1->2->3输出: 2->3思路注意这题是去掉重复的节点（相同节点全部删除），而不是简单的去重，所以在遍历节点过程中，每一个节点都需要向前探测，直到节点值不等于后缀节点时结束，并对这一过程加入计数器，如果计数器大
2020-10-07 13:57:00
240
原创 81. 搜索旋转排序数组 II（技巧）
题目假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。示例 1:输入: nums = [2,5,6,0,0,1,2], target = 0输出: true示例 2:输入: nums = [2,5,6,0,0,1,2], target = 3输出: false进阶:这是 搜索旋转排序数组 的
2020-10-06 21:15:21
331
原创 80. 删除排序数组中的重复项 II（水题）
题目给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组并在使用 O(1)O(1)O(1) 额外空间的条件下完成。示例 1:给定 nums = [1,1,1,2,2,3],函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。你不需要考虑数组中超出新长度后面的元素。示例 2:给定 nums = [0,0,1,1,1,1,2,3,3],
2020-10-06 18:59:43
109
原创 79. 单词搜索（dfs+回溯）
题目给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。示例:board =[ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']]给定 word = "ABCCED", 返回 true给定 word = "SEE", 返回 true给定 word = "ABCB", 返回
2020-10-06 16:42:47
176
原创 LeetCode刷题算法总结（持续更新）
1. 指针法11. 盛最多水的容器（双指针法）15. 三数之和（指针法）16. 最接近的三数之和（指针法）18. 四数之和（双指针）2. 动态规划10. 正则表达式匹配（动态规划）5. 最长回文子串（动态规划）32. 最长有效括号（动态规划）44. 通配符匹配（动态规划）72. 编辑距离（动态规划）3. 贪心45. 跳跃游戏 II（贪心算法）53. 最大子序和（贪心）55. 跳跃游戏（贪心）4. KMP应用28. 实现 strStr()（KMP应用）5. 滑
2020-10-06 14:47:48
348
原创 77. 组合（递归求解）
题目给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。示例:输入: n = 4, k = 2输出:[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],]思路对于示例中 k=2k = 2k=2，很容易通过双重循环解题，但 k 很大时，我们无法动态构造 k 重循环，因此可以用递归代替 k 重循环，代码如下：代码class Solution { private List<List<Integ
2020-10-06 14:06:23
224
原创 76. 最小覆盖子串（滑动窗口）
题目给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n)O(n)O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。示例：输入：S = "ADOBECODEBANC", T = "ABC"输出："BANC"提示：如果 S 中不存这样的子串，则返回空字符串 ""。如果 S 中存在这样的子串，我们保证它是唯一的答案。思路这道题应采用滑动窗口的思想，定义两个指针 left, right，窗口的初始大小为 0，即 left = right =
2020-10-06 13:38:53
652
原创 75. 颜色分类（荷兰旗问题）
题目给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。注意:不能使用代码库中的排序函数来解决这道题。示例:输入: [2,0,2,1,1,0]输出: [0,0,1,1,2,2]进阶：一个直观的解决方案是使用计数排序的两趟扫描算法。首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。你能想出一个仅使用常数空间
2020-10-05 18:49:30
440
原创 74. 搜索二维矩阵（二分查找）
题目编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个整数。示例 1:输入:matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]]target = 3输出: true示例 2:输入:matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [2
2020-10-05 10:27:45
590
原创 73. 矩阵置零（技巧）
题目给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用**原地算法。示例 1:输入: [ [1,1,1], [1,0,1], [1,1,1]]输出: [ [1,0,1], [0,0,0], [1,0,1]]示例 2:输入: [ [0,1,2,0], [3,4,5,2], [1,3,1,5]]输出: [ [0,0,0,0], [0,4,5,0], [0,3,1,0]]思路一定义两个
2020-10-04 21:01:43
1300
1
原创 72. 编辑距离（动态规划）
题目给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：插入一个字符删除一个字符替换一个字符示例 1：输入：word1 = "horse", word2 = "ros"输出：3解释：horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')示例 2：输入：word1 = "inte
2020-10-04 15:32:38
398
1
原创 71. 简化路径（字符串处理）
题目以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。示例
2020-10-04 10:30:42
205
原创 70. 爬楼梯（递推）
题目假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意： 给定 n 是一个正整数。示例 1：输入： 2输出： 2解释： 有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶示例 2：输入： 3输出： 3解释： 有三种方法可以爬到楼顶。5. 1 阶 + 1 阶 + 1 阶6. 1 阶 + 2 阶7. 2 阶 + 1 阶思路采用递推的思想，我们可以这样想，对于当前的第 iii 级台阶，
2020-10-04 10:04:13
757
原创 69. x 的平方根（二分）
题目实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。示例 1:输入: 4输出: 2示例 2:输入: 8输出: 2说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。思路个人认为这题要做好，算是中等难度的题目了；最简单的思路一定是从 i=0 开始试探，每次令 i += 1 ，再判断 i*i 与 x 的大小关系，这样遍历一定是可以找到
2020-09-29 20:55:07
104
原创 68. 文本左右对齐（字符串处理）
题目给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。文本的最后一行应为左对齐，且单词之间不插入额外的空格。说明:单词是指由非空格字符组成的字符序列。每个单词
2020-09-29 16:39:57
682
原创 67. 二进制求和（水题）
题目给你两个二进制字符串，返回它们的和（用二进制表示）。输入为 非空 字符串且只包含数字 1 和 0。示例 1:输入: a = "11", b = "1"输出: "100"示例 2:输入: a = "1010", b = "1011"输出: "10101"思路代码public class Solution { public String addBinary(String a, String b) { StringBuilder sb = new Strin
2020-09-29 15:07:01
158
原创 66. 加一（水题）
题目给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。示例 1:输入: [1,2,3]输出: [1,2,4]解释: 输入数组表示数字 123。示例 2:输入: [4,3,2,1]输出: [4,3,2,2]解释: 输入数组表示数字 4321。思路代码import java.util.Arrays;public class Solution {
2020-09-29 14:53:44
227
原创 65. 有效数字（有限状态机）
题目验证给定的字符串是否可以解释为十进制数字。例如:"0" => true" 0.1 " => true"abc" => false"1 a" => false"2e10" => true" -90e3 " => true" 1e" => false"e3" => false" 6e-1" => true" 99e2.5 " => false"53.5e93" => true" --6 " => fals
2020-09-29 14:43:00
367
原创 64. 最小路径和（递推）
题目给定一个包含非负整数的 m×nm \times nm×n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明： 每次只能向下或者向右移动一步。示例:输入:[ [1,3,1], [1,5,1], [4,2,1]]输出: 7解释: 因为路径 1→3→1→1→1 的总和最小。思路同前两题 62. 不同路径、63. 不同路径 II 思路相同，都是用递推的思想；这道题求路径之和最小，那么可以反着递推，我们从终点出发，从右到左，从下到上，过程中的每个位置到终
2020-09-28 19:36:12
141
原创 63. 不同路径 II（递推）
题目一个机器人位于一个 m×nm \times nm×n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。说明：m 和 n 的值均不超过 100。示例 1:输入:[ [0,0,0], [0,1,0], [0,0,0]]输出: 2解释:3x3 网格的正
2020-09-28 18:46:32
110
原创 62. 不同路径（递推）
题目一个机器人位于一个 m×nm \times nm×n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？例如，上图是一个 7×37 \times 37×3 的网格。有多少可能的路径？示例 1:输入: m = 3, n = 2输出: 3解释:从左上角开始，总共有 3 条路径可以到达右下角。1. 向右 -> 向右 -> 向下2. 向右 ->
2020-09-28 15:06:03
203
原创 61. 旋转链表（技巧）
题目给定一个链表，旋转链表，将链表每个节点向右移动 kkk 个位置，其中 kkk 是非负数。示例 1:输入: 1->2->3->4->5->NULL, k = 2输出: 4->5->1->2->3->NULL解释:向右旋转 1 步: 5->1->2->3->4->NULL向右旋转 2 步: 4->5->1->2->3->NULL示例 2:输入: 0->1->
2020-09-27 20:36:46
139
原创 60. 第k个排列（技巧）
题目给出集合 [1,2,3,…,n][1,2,3,…,n][1,2,3,…,n]，其所有元素共有 n!n!n! 种排列。按大小顺序列出所有排列情况，并一一标记，当 n=3n = 3n=3 时, 所有排列如下："123""132""213""231""312""321"给定 nnn 和 kkk，返回第 kkk 个排列。说明：给定 n 的范围是 [1, 9]。给定 k 的范围是[1, n!]。示例 1:输入: n = 3, k = 3输出: "213"示例 2:输入
2020-09-27 19:56:27
825
原创 59. 螺旋矩阵 II（水题）
题目给定一个正整数 nnn，生成一个包含 1 到 n2n^2n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。示例:输入: 3输出:[ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ]]代码import java.util.Arrays;public class Solution { public int[][] generateMatrix(int n) { int[][] matrix = new int[n][n];
2020-09-21 09:03:43
106
原创 58. 最后一个单词的长度（水题）
题目给定一个仅包含大小写字母和空格 ' ' 的字符串 s，返回其最后一个单词的长度。如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。如果不存在最后一个单词，请返回 0 。说明： 一个单词是指仅由字母组成、不包含任何空格字符的 最大子字符串。示例:输入: "Hello World"输出: 5代码import java.util.*;public class Solution { public int lengthOfLastWord(String s) {
2020-09-19 15:49:57
165
2
原创 57. 插入区间（技巧）
题目给出一个_无重叠的 ，_按照区间起始端点排序的区间列表。在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。示例 1：输入：intervals = [[1,3],[6,9]], newInterval = [2,5]输出：[[1,5],[6,9]]示例 2：输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]输出：[[1,2],[3,10],[12,16
2020-09-19 15:31:07
377
原创 56. 合并区间（技巧）
题目给出一个区间的集合，请合并所有重叠的区间。示例 1:输入: intervals = [[1,3],[2,6],[8,10],[15,18]]输出: [[1,6],[8,10],[15,18]]解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].示例 2:输入: intervals = [[1,4],[4,5]]输出: [[1,5]]解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。思路一定义一个结构体，两个变量节点值和区分左右区间变量，将所有节
2020-09-18 20:13:34
3606
原创 55. 跳跃游戏（贪心）
题目给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。示例 1:输入: [2,3,1,1,4]输出: true解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。示例 2:输入: [3,2,1,0,4]输出: false解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。思路贪心思
2020-09-17 17:06:24
100
原创 54. 螺旋矩阵（技巧）
题目给定一个包含 m×nm \times nm×n 个元素的矩阵（mmm 行, nnn 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。示例 1:输入:[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ]]输出: [1,2,3,6,9,8,7,4,5]示例 2:输入:[ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12]]输出: [1,2,3,4,8,12,11,10,9,5,6,7]思路由外层到内存依
2020-09-17 15:45:45
217
原创 53. 最大子序和（贪心）
题目给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:输入: [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。进阶:如果你已经实现复杂度为 O(n)O(n)O(n) 的解法，尝试使用更为精妙的分治法求解。思路贪心，逐个遍历并累加，贪心策略如下：当我们遍历到 nums[i] 时t （累加变量）小于等于0，那么 i 前面的部分被舍弃，因为这部分会使和更小；t
2020-09-17 14:02:30
189
原创 52. N皇后 II（dfs+回溯）
题目nnn 皇后问题研究的是如何将 nnn 个皇后放置在 n×nn\times nn×n 的棋盘上，并且使皇后彼此之间不能相互攻击。上图为 8 皇后问题的一种解法。给定一个整数 nnn，返回 nnn 皇后不同的解决方案的数量。示例:输入: 4输出: 2解释: 4 皇后问题存在如下两个不同的解法。[ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."
2020-09-16 20:20:43
128
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人