Yubochang-CSDN博客

原创 LeetCode：最长回文子串

题目给定一个字符串 s，找到 s 中最长的回文子串。你可以假设s 的最大长度为 1000。示例 1：输入: "babad"输出: "bab"注意: "aba" 也是一个有效答案。来源：力扣（LeetCode）解回文子串有4种情况，一个是字符本身，一个是相同字符构成的字符串，一个是仅两两对称字符串，一个是带中心的两两对称字符串。第一种思路，依靠对称关系进行匹配，每个字符自身或与其相邻的字符作为中心点外扩，直接最长匹配，时间上O(n^2)就能完成，不需要辅助空间，这里不讨论.

2020-11-20 20:29:44 203

原创 LeetCode：加油站

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

2020-11-19 00:15:30 209

原创 LeetCode：根据身高重建队列

题目假设有打乱顺序的一群人站成一个队列。每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。编写一个算法来重建这个队列。注意：总人数少于1100人。示例输入:[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]输出:[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]来源：力扣（LeetCode）解首先我们大概猜出，应该是要把k=0的放前面，然后k!

2020-11-16 20:04:12 138

原创 LeetCode：数组的相对排序

题目给你两个数组，arr1 和arr2，arr2中的元素各不相同arr2 中的每个元素都出现在arr1中对 arr1中的元素进行排序，使 arr1 中项的相对顺序和arr2中的相对顺序相同。未在arr2中出现过的元素需要按照升序放在arr1的末尾。示例：输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]输出：[2,2,2,1,4,3,3,9,6,7,19]提示：arr1.length, ...

2020-11-14 20:48:54 204 1

原创 LeetCode：验证二叉树的前序序列化

题目序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。 _9_ / \ 3 2 / \ / \4 1 # 6/ \ / \ / \# # # # # #例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前...

2020-11-13 20:44:58 121

原创 leetCode：奇偶数组2.0版

题目给定一个非负整数数组A， A 中一半整数是奇数，一半整数是偶数。对数组进行排序，以便当A[i] 为奇数时，i也是奇数；当A[i]为偶数时， i 也是偶数。你可以返回任何满足上述条件的数组作为答案。示例：输入：[4,2,5,7]输出：[4,5,2,7]解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。来源：力扣（LeetCode）解简单的，也是有效的，用两个 Array.length/2 长的辅助数组来存储奇偶数，然后根据...

2020-11-12 20:53:23 139

原创 leetCode：奇偶链表

题目给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。示例 1:输入: 1->2->3->4->5->NULL输出: 1->3->5->2->4->NULL来源：力扣（LeetCode）解显然的，一次取一个，分别连

2020-11-07 20:02:48 125

原创 LeetCode：被围绕的区域

题目给定一个二维的矩阵，包含'X'和'O'（字母 O）。找到所有被 'X' 围绕的区域，并将这些区域里所有的'O' 用 'X' 填充。示例:X X X XX O O XX X O XX O X X运行你的函数后，矩阵变为：X X X XX X X XX X X XX O X X解释:被围绕的区间不会存在于边界上，换句话说，任何边界上的'O'都不会被填充为'X'。任何不在边界上，或不与边界上的'O'相连的'O'最终都会被填充为'X'。如果两...

2020-11-05 18:48:04 275

原创 LeetCode：Z字形变换

题目将一个给定字符串根据给定的行数，以从上往下、从左到右进行Z 字形排列。比如输入字符串为 "LEETCODEISHIRING"行数为 3 时，排列如下：L C I RE T O E S I I GE D H N之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。来源：力扣（LeetCode）解这道题可以想到有两种...

2020-11-04 11:31:55 168

原创 LeetCode：有效的山脉数组

题目给定一个整数数组A，如果它是有效的山脉数组就返回true，否则返回 false。让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：A.length >= 3在0 < i< A.length - 1条件下，存在i使得：A[0] < A[1] < ... A[i-1] < A[i]A[i] > A[i+1] > ... > A[A.length - 1]来源：力扣（LeetCode）解这道题除了...

2020-11-03 23:34:37 113

原创中：链表的插入排序

题目：每次只选择一个元素，将其放到合适的位置，直到所有元素可以形成一个有序的输出列表。解：直接从头开始比较值，然后插入，也就是插入排序的变异版。主要得注意链表头插入，其余的没什么了。当然了，也可以直接先断链表，然后再排序，也省得要在不同情况下断链。class Solution { public ListNode insertionSortList(ListNode head) { if(head==null || head.next==null){

2020-11-01 20:00:44 86

原创小记：捋捋接口和抽象类

接口接口是一系列方法的声明，是一些方法特征的集合。抽象类抽象类是它的所有子类的公共属性的集合。so？关于变量接口，默认为public static final type property;（修饰符可略）抽象类，无限制，跟其它普通类的变量规定一样。关于方法接口，在JDK1.8以前，只能为public abstract type method();（修饰符可略）但是JDK1.8以后，方法也可以是带有方法体的default/static方...

2020-11-01 16:44:59 103

原创 LeetCode：链表随机节点

题目：给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。进阶:如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？示例:// 初始化一个单链表 [1,2,3].ListNode head = new ListNode(1);head.next = new ListNode(2);head.next.next = new ListNode(3);Solution solution = new Solution(head

2020-10-31 21:03:06 290

原创 LeetCode：岛屿周长

题目：给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地0 表示水域。网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。来源：力扣（LeetCode）解：简单点说，就是让我们计算这些‘1’格子连成的外围有多长。最方便的.

2020-10-30 17:12:30 291

原创 LeetCode：根节点到叶子节点的数和

题目：给定一个二叉树，它的每个结点都存放一个0-9的数字，每条从根到叶子节点的路径都代表一个数字。例如，从根到叶子节点路径 1->2->3 代表数字 123。计算从根到叶子节点生成的所有数字之和。说明:叶子节点是指没有子节点的节点。示例 1:输入: [1,2,3] 1 / \ 2 3输出: 25解释:从根到叶子节点路径 1->2 代表数字 12.从根到叶子节点路径 1->3 代表数字 13.因此，数字总和 = 12 + ...

2020-10-29 19:43:54 184

原创 LeetCode：独一无二的出现次数

题目：给你一个整数数组arr，请你帮忙统计数组中每个数的出现次数。如果每个数的出现次数都是独一无二的，就返回true；否则返回false。解：最近的每日一题难度好像都不高。这道题显然的，次数统计最高效就是“标记法”，O(n)时间。这道题两次统计其实都是一样的算法，只不过第一次统计次数，第二次统计重复。class Solution { public boolean uniqueOccurrences(int[] arr) { //一般检测例子数量较小，...

2020-10-28 11:34:26 120

原创 LeetCode：统计数组中小于当前数的数量

题目：给你一个数组nums，对于其中每个元素nums[i]，请你统计数组中比它小的所有数字的数目。换而言之，对于每个nums[i]你必须计算出有效的j的数量，其中 j 满足j != i 且 nums[j] < nums[i]。以数组形式返回答案。示例 1：输入：nums = [8,1,2,2,3]输出：[4,0,1,1,3]解释：对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。对于 nums[1]=1 不存在比它小的数字。对于...

2020-10-26 22:43:19 1607

原创 LeetCode：划分字母区间

题目：字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。示例 1：输入：S = "ababcbacadefegdehijhklij"输出：[9,7,8]解释：划分结果为 "ababcbaca", "defegde", "hijhklij"。每个字母最多出现在一个片段中。像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。提示：S的

2020-10-22 16:54:43 262

原创 LeetCode：长按键入重复检测

题目：你的朋友正在使用键盘输入他的名字name。偶尔，在键入字符c时，按键可能会被长按，而字符可能被输入 1 次或多次。你将会检查键盘输入的字符typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回True。示例 1：输入：name = "alex", typed = "aaleex"输出：true解释：'alex' 中的 'a' 和 'e' 被长按。来源：力扣（LeetCode）解：这道题双数组同时遍历即可，主要是注意边界判断。...

2020-10-21 10:21:06 125

原创二叉树的遍历（迭代）

一般我们二叉树遍历都是用递归，耗费内存但是快速且方便。节省空间上来讲，迭代是个比较好的选择，由于需要保存层次节点（否则难以返回），所以我们可以用栈来辅助。前序遍历，即先root再left再right，所以我们直接访问root，先压right，再压left完成本次操作。class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> rs=n

2020-10-20 17:02:46 107

原创 LeetCode：比较含退格的字符串

题目：给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。注意：如果对空文本输入退格字符，文本继续为空。输入：S = "ab#c", T = "ad#c"输出：true解释：S 和 T 都会变成 “ac”。来源：力扣（LeetCode）解：这道题第一种方法，重构字符串。双指针滑动检查字符，当遍历遇到非'#'时保存至新字符数组尾指针，否则尾指针退一个值（表示删除，注意溢出问题）。最后比较新字符数组是否相等。时间

2020-10-19 13:05:51 144

原创 LeetCode：有序数组的平方

题目：给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。示例 1：输入：[-4,-1,0,3,10]输出：[0,1,9,16,100]来源：力扣（LeetCode）解：这道题如果直接求解再排序，再快也要O(nlogn)，所以这里不采用。一个有序数组如果全负或全正，那么我们就可以获得平方后的有序数组。所以我们把数组看成两部分，前半部分为负数组，后半部分为正数组（含0），采用双指针方法从边界（正负端都是从大到小）遍历平方，然后比较大

2020-10-16 17:13:14 193

原创 Java：常用设计模式

1.单例模式（Singleton Pattern）概念上，即一个类只能有一个实例，而不允许创建多个类实例。应用于类的对应实体只能一个的情况下，比如学校校长，一个学校一般只有一个校长，所以不会在业务中new很多个校长实例，而是只创建一个校长实例进行操作。设计上，一个singleton类跟普通类区别在于构造方法私有化，不允许外部调用构造方法，内部持有唯一的一个实例，提供一个静态方法获取唯一实例。那么问题来了，不构造怎么实例化？于是我们的静态获取方法里还要提供 instance==null 的判断，如果

2020-10-15 16:50:21 183 1

原创 LeetCode：查找常用字符

题目：给定仅有小写字母组成的字符串数组 A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表。例如，如果一个字符在每个字符串中出现 3 次，但不是 4 次，则需要在最终答案中包含该字符 3 次。你可以按任意顺序返回答案。来源：力扣（LeetCode）解：这道题暴力破解的话，时间复杂度达到O(n^3)，不采取。用数组标记法，这里用java的map标记。每一次字符串遍历，存下当前字符重复情况，跟之前存下的重复字符情况比较，保存最小值，不重复的删除。时间复杂度o(n^2)

2020-10-14 23:27:29 118

原创 LeetCode：二叉搜索树的最小绝对差

题目：给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。示例：输入： 1 \ 3 / 2输出：1解释：最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。来源：力扣（LeetCode）解：这道题暴力破解就算了，时间空间都很大。我们知道，二叉搜索树是有序的，而绝对差是什么？两个值之间的距离，所以最小绝对差就是有序序列中某两个相邻值的绝对差。中序遍历二叉搜索树的结果就是一个有序...

2020-10-12 17:06:09 131

原创 LeetCode：分割等和子集

题目：给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。注意:每个数组中的元素不会超过 100数组的大小不会超过 200示例 1:输入: [1, 5, 11, 5]输出: true解释: 数组可以分割成 [1, 5, 5] 和 [11].来源：力扣（LeetCode）解：集合取部分元素构成新集合，典型的0-1背包问题。区别在于0-1背包不一定装满，但是这里要的是“装满”，我们选取元素进“背包”，（背包容量就是数组和的一半，因为

2020-10-11 23:00:58 159

原创 LeetCode：重排链表

题目：给定一个单链表L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。示例1:给定链表 1->2->3->4, 重新排列为 1->4->2->3.来源：力扣（LeetCode）解：这道题显然就是首尾不断重连接，1-n-2-(n-1)-3......-中点。这道题最简单的就是直接首尾重连接，但是每次获取尾部都要遍历一遍，..

2020-10-10 19:32:08 131

原创 LeetCode：前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 个高频元素的集合是唯一的。你可以按任意顺序返回答案...

2020-10-08 11:37:50 194

原创 LeetCode：颜色分类

题目：给定一个包含红色、白色和蓝色，一共n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。注意:不能使用代码库中的排序函数来解决这道题。来源：力扣（LeetCode）解：这道题禁止使用排序函数，那么也意味着可以有别的方法。因为颜色数字只有三个，已经确定，所以第一种方法，统计数字个数，直接重构数组，两趟O（n）完成。这里介绍一种复杂一点的双指针算法。我们可以想出..

2020-10-07 13:39:06 145

原创 LeetCode：节点与父节点最大差

题目：给定二叉树的根节点root，找出存在于不同节点A 和B之间的最大值 V，其中V = |A.val - B.val|，且A是B的祖先。（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）来源：力扣（LeetCode）解：这道题应该就是用DP，但是一开始思路错了，以为递归传递当前最大差值，但是传递最大差值处理起来比较麻烦，因为我们不仅需要知道当前集构成的最大差值，还需要知道是哪两个节点构成的，否则就会出错。题解中...

2020-10-07 00:22:01 247

原创 LeetCode：括号生成

题目：数字 n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。示例：输入：n = 3输出：[ "((()))", "(()())", "(())()", "()(())", "()()()" ]来源：力扣（LeetCode）解：这道题我自己是没看出什么规律，查看了官方题解也是没什么规律可循，因为不同括号的组合是任意的，所以一般用递归优化或者回溯剪枝。这里用递归求...

2020-10-05 15:37:34 103

原创 LeetCode：两数之和（链表）

题目：给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0开头。示例：输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -> 8原因：342 + 465 = 807来源：力扣（LeetCode）解：这道题之...

2020-10-04 16:05:20 279

原创 LeetCode：两数之和

题目：给定一个整数数组 nums和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。示例:给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]来源：力扣（LeetCode）解：注意，这道题返回的是下标，所以我们不会用排序后双指针去做，因为下标会乱。暴...

2020-10-03 18:56:23 103

原创 LeetCode：宝石与石头

题目：给定字符串J代表石头中宝石的类型，和字符串S代表你拥有的石头。S中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。J中的字母不重复，J和S中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。示例 1:输入: J = "aA", S = "aAAbbbb"输出: 3解：这道题算是简单类型的，用辅助标记法就可以做。先用一个数组（用HashSet、HashMap也可以）存下代表宝石的字符，然后扫描统计即可。cl...

2020-10-02 16:42:48 121

原创 LeetCode：下一个排列

题目：实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。以下是一些例子，输入位于左侧列，其相应输出位于右侧列。1,2,3 → 1,3,23,2,1 → 1,2,31,1,5 → 1,5,1来源：力扣（LeetCode）解：这道题描述的是，数值序列下一个大的，也就是重排后跟原值的差值最小的。我们知道，降序序列值最大不需要改动，要获得大

2020-10-01 22:41:09 164

原创 LeetCode：填充树的右侧节点

题目：给定一个二叉树struct Node { int val; Node *left; Node *right; Node *next;}填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有next 指针都被设置为 NULL。进阶：你只能使用常量级额外空间。使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。来源：力扣（LeetCode）解：...

2020-09-28 20:27:48 132

原创 LeetCode:三数之和

题目：给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，使得a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。来源：力扣（LeetCode）解：这道题最简单的做法就是暴力破解，即a,b,c一层一层循环，然后去重复即可。但是时间复杂度太高，O(n^3)，而且去重复麻烦，因为没什么规律，显然是个比较低效的算法。我们可以这样设计：先把数组排序，这样我们在遍历时快速去重复，可以减少遍历的次数，如...

2020-09-25 20:50:33 129

原创 LeetCode：盛最多水的容器

+盛水最多的容器给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点(i,ai) 。在坐标内画 n 条垂直线，垂直线 i的两个端点分别为(i,ai) 和 (i, 0)。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。说明：你不能倾斜容器，且n的值至少为 2。来源：力扣（LeetCode）解：这道题速度最快使用双指针法，即用head和tail指向数组头尾，然后获得当前面积值 Math.min(height[head],height[ta...

2020-09-24 00:12:50 65

原创字节跳动：将数字字符串转换成IP地址

题目描述现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。例如：给出的字符串为"25525511135",返回["255.255.11.135", "255.255.111.35"]. (顺序没有关系)解：这道题采用的是回溯，我们递归查找，获得结果后返回进行下一个分支查找。子结构：插入“.”，如果还未满足3个点。判断是否为IP地址：是否“.*.”的 * 满足<255（这里不需要考虑>0，因为字符串不带-），同时不能存在“ 0...

2020-09-20 23:33:42 858

原创字节跳动：寻找二叉树两节点的最近祖节点

题目描述给定一棵二叉树以及这棵树上的两个节点 o1和o2，请找到 o1和o2的最近公共祖先节点。解：这道题可以采用递归查找+标记法求解，先找到两个节点的位置并用栈保存路径，（因为没有父节点指向没办法回滚）。然后对路径进行重合检查即可。这道题有点特殊，返回值只能是int，也就是说不存在找不到的情况。所以边界检查可做可不做。import java.util.*;/* * public class TreeNode { * int val = 0; * TreeN...

2020-09-19 21:49:16 243

空空如也

空空如也