- 博客(47)
- 收藏
- 关注
RSS订阅原创 [题记] 距离顺序排列矩阵单元格——Leetcode
给出 R 行 C 列的矩阵，其中的单元格的整数坐标为 (r, c)，满足 0 <= r < R 且 0 <= c < C。另外，我们在该矩阵中给出了一个坐标为 (r0, c0) 的单元格。返回矩阵中的所有单元格的坐标，并按到 (r0, c0) 的距离从最小到最大的顺序排，其中，两单元格(r1, c1) 和 (r2, c2) 之间的距离是曼哈顿距离，|r1 - r2| + |c1 - c2|。（你可以按任何满足此条件的顺序返回答案。）示例 1：输入：R = 1, C = 2.
2020-11-19 11:00:27
104
原创 [题记]二叉搜索树的范围和——LeetCode
给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。二叉搜索树保证具有唯一的值。示例 1：输入：root = [10,5,15,3,7,null,18], L = 7, R = 15输出：32示例 2：输入：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10输出：23思路：深度搜索对二叉搜索树进行深度搜索，如果当前节点的值小于L，遍历它的右子树。如果当前节点的值大于R，遍历它的左子树。如果当前.
2020-08-09 23:23:24
116
原创 [题记]字符串相加——LeetCode
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。提示：num1 和num2 的长度都小于 5100num1 和num2 都只包含数字 0-9num1 和num2 都不包含任何前导零你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式思路：从两个数的个位数开始相加，将每一位相加的和的个位数加入到str，十位数记录后加到下一位的和中。以此类推，直到相加完成。注意：此时str字符串是有个位到高位的顺序，而不是高位到个位的顺序，所以.
2020-08-03 23:38:19
161
原创 [题记]最小高度树——LeetCode
给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。示例:给定有序数组: [-10,-3,0,5,9],一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树： 0 / \ -3 9 / / -10 5 思路：二分搜索使用二分搜索递归构建左右子树即可。class Solution { //二分法递归构.
2020-08-02 21:40:44
99
原创 [题记]二叉树中第二小的节点——LeetCode
给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。示例 1:输入: 2 / \ 2 5 / \ 5 7输出: 5说明: 最小的值是 2 ，第二小的值是 5 。示例 2:输入: 2 / \ 2 2输出: -1说明.
2020-08-01 10:54:06
184
1
原创 [题解-dp]不同路径II——LeetCode
一个机器人位于一个 m x n 网格的左上角 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。说明：m 和 n 的值均不超过 100。输入:[ [0,0,0], [0,1,0], [0,0,0]]输出: 2解释:3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径：1. 向右 -> 向右 -> 向下 .
2020-07-06 23:08:10
169
原创 [题记-DP]最长的重复子数组——LeetCode
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。输入：A: [1,2,3,2,1]B: [3,2,1,4,7]输出：3解释：长度最长的公共子数组是 [3, 2, 1] 。提示：1 <= len(A), len(B) <= 10000 <= A[i], B[i] < 100思路：动态规划设dp[i][j] 为以i为结尾的A数组和以j为结尾的B数组的最大重复子数组的长度。有两种情况：A[i] == B[j]，那么dp[.
2020-07-01 23:04:37
101
原创 [题记-单调栈]每日温度——LeetCode
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。思路：单调栈根据题意，我们要找到索.
2020-06-11 17:41:21
96
原创 [题记]最长连续序列——LeetCode
给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。示例:输入: [100, 4, 200, 1, 3, 2]输出: 4解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。思路：并查集初始化的时候可以将每个数的值初始化为他的下一个数，查询的时候只需要查询它可以达到的最大数字便可。class Solution {public: map<int, int> m; int find( int x ) { .
2020-06-06 22:52:52
53
原创 [题记]除自身以外数组的乘积——LeetCode
给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。示例:输入: [1,2,3,4]输出: [24,12,8,6] 提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。思路：前缀乘积 * 后缀乘积数组中除了第 i 数其它数的乘积等于它的 前缀.
2020-06-04 21:47:46
70
原创 [题记-动态规划]打家劫舍——LeetCode
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。示例 1:输入: [1,2,3,1]输出: 4解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。示例 2:输.
2020-05-29 22:20:54
110
原创 [题记]从前序与中序遍历序列构造二叉树——LeetCode
根据一棵树的前序遍历与中序遍历构造二叉树。注意:你可以假设树中没有重复的元素。例如，给出前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树： 3 / \ 9 20 / \ 15 7思路：分治前序遍历序列结构：[ 根 ] [ 左子树 ] [ 右子树 ]中序遍历序列结构：[ 左子树 ] [ 根 ] [ 右子树 ]如上，我们可以根据前序遍历序列和中序遍历序列中根的.
2020-05-23 00:02:17
87
原创 [题记]最长回文串——LeetCode
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1：输入: "babad"输出: "bab"注意: "aba" 也是一个有效答案。示例 2：输入: "cbbd"输出: "bb"思路：中心拓展遍历字符串，每个字符都可能是回文字符的中心，由这个字符向两端拓展，记录最长回文串的长度即可。class Solution {public: int check(string s, int left, int right) { .
2020-05-21 22:07:07
107
原创 [题记]验证回文字符串 Ⅱ——LeetCode
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。注意:字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。示例 1:输入: "aba"输出: True示例 2:输入: "abca"输出: True解释: 你可以删除c字符。思路：判断原始字符串是不是回文串，如果不是，将不相等的位置左边和右边分别删除判断。class Solution {public: bool judge( string &s, int &left.
2020-05-19 14:06:28
72
原创 [题记-位运算]只出现一次的数字——LeetCode
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。★要求不使用额外空间。示例 1:输入: [2,2,1]输出: 1示例 2:输入: [4,1,2,1,2]输出: 4思路：位运算^（异或）运算：数位相同为0，相异为1.对整个数组进行异或运算，出现两次的数将抵消掉，最后剩下的便是出现一次的数字。class Solution {public: int singleNumber(vector<int>&am.
2020-05-14 14:02:46
106
原创 [题记-二分查找]x的平方根——LeetCode
实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。☆：由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。示例 1:输入: 4输出: 2示例 2:输入: 8输出: 2说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。思路：二分查找比较mid的平方与x的关系从而找出答案ans。class Solution {public: int mySqrt(int x) {.
2020-05-09 10:57:25
99
原创 [题记-动态规划]最大正方形——LeetCode
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。示例:输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4思路：动态规划设dp[i]为最大正方形的右下角。、那么我们该如何去更新dp[i]的值，因为dp[i]表示正方形的右下角，很显然dp[i]的值与它的左边，左上角，上边的三个值有关系。我们取...
2020-05-08 14:47:05
108
原创 [题记]另一个树的子树——LeetCode
给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。示例 1:给定的树 s: 3 / \ 4 5 / \ 1 2给定的树 t： 4 / \ 1 2返回 true，因为 t 与 s 的一个子树拥有相同的结构和节...
2020-05-07 18:41:47
74
原创 [题记]验证二叉搜索树——LeetCode
给定一个二叉树，判断其是否是一个有效的二叉搜索树。|假设一个二叉搜索树具有如下特征：1.节点的左子树只包含小于当前节点的数。2.节点的右子树只包含大于当前节点的数。3.所有左子树和右子树自身必须也是二叉搜索树。示例 1:输入: 2 / \ 1 3输出: true示例 2:输入: 5 / \ 1 4 / \ 3 ...
2020-05-05 18:13:26
103
原创 [题解]跳跃游戏——LeetCode
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。示例:输入: [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。说明:假设你总是可以到达数组的最后一...
2020-05-04 10:27:10
132
原创 [题记]最大自序和——LeetCode
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:输入: [-2,1,-3,4,-1,2,1,-5,4],输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。思路：动态规划赋值一个与nums相同的数组v，v[i]表示以 i 为开头的最大子序和。每一段序列的子序和都与下一段的子序和有关，由此得出递推公...
2020-05-03 11:53:10
96
原创 [题记]无重复字符的最长子串——LeetCode
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。示例 1:输入: "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:输入: "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:输入: "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "w...
2020-05-02 20:23:40
79
原创 [题记]快乐数——LeetCode
编写一个算法来判断一个数 n 是不是快乐数。「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。 如果 n 是快乐数就返回 True ；不是，则返回 False 。输入：19输出：true解释：12 + 92 = 8282 + 22 = ...
2020-04-30 10:56:28
89
原创 [题记-二分查找]山脉数组中查找目标值——LeetCode
给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。 如果不存在这样的下标 index，就请返回 -1。 何为山脉数组？如果数组 A 是一个山脉数组的话，那它满足如下条件：首先，A.length >= 3其次，在 0 < i < A.length - 1 条件下，存在 ...
2020-04-29 15:59:33
112
原创 [题记-位运算]数组中数字出现的次数——LeetCode
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。示例 1：输入：nums = [4,1,4,6]输出：[1,6] 或 [6,1]示例 2：输入：nums = [1,2,10,4,1,4,3,3]输出：[2,10] 或 [10,2]限制：2 <= nums <= ...
2020-04-28 20:04:26
87
原创 [笔记]Linux磁盘分区及临时挂载
版本：CentOS7.1本人是初学linux，具体对错欢迎指点~一：虚拟机要先有一块未分区的磁盘，这里我加了一个1GB大小的磁盘。二：可以利用系统自带的磁盘查看工具查看这块未分配的磁盘位置。三：用fdisk命令进行分区。查看这块磁盘的信息：# fdisk -l /dev/sdb开始分区：输入命令：# fdisk dev/sdb输入m可以获取帮助。输入n为...
2020-04-28 12:58:55
736
原创 [题记]搜索螺旋排序数组——LeetCode
假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。你可以假设数组中不存在重复的元素。☆：你的算法时间复杂度必须是 O(log n) 级别。示例 1:输入: nums = [4,5,6,7,0,1,2], ...
2020-04-27 10:50:04
226
原创 [题记]全排列——LeetCode
给定一个没有重复数字的序列，返回其所有可能的全排列。一：回溯法每次寻找没有被记录的数字，然后将其加入临时数组，全部加入后，代表这一次排序完成，进行回溯寻找下一个排序方式。class Solution {public: vector<vector<int>> ans;//答案数组 vector<int> tmp;//临时数组 ...
2020-04-25 12:06:20
94
原创 [题记]数组中的逆序对——LeetCode
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。示例 1:输入: [7,5,6,4]输出: 5 限制：0 <= 数组长度 <= 50000一：直接 暴力，当然超时了～～class Solution {public: int reversePairs(vector<in...
2020-04-24 11:38:50
143
原创 [题记]层数最深叶子节点的和——LeetCode
给你一棵二叉树，请你返回层数最深的叶子节点的和。输入：root = [1,2,3,4,5,null,6,7,null,null,null,null,8]输出：15dfs记录每层的和即可。class Solution {public: int deepestLeavesSum(TreeNode* root) { if( root == NULL ) re...
2020-04-23 21:21:16
123
原创 [笔记]二分查找——总结
二分查找，通过每次折半搜索范围来确定搜索对象。时间复杂度：logN准备：const int len1 = 10;//数组1的长度const int len2 = 20;//数组2的长度int array1[10] = {1,2,3,4,5,6,7,8,9,10};int array2[20] = {1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5};...
2020-04-23 15:46:52
114
原创 [题记]二叉搜索树的插入——LeetCode
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。给定二叉搜索树: 4 / \ 2 7 / \ 1 3和 插入的值: 5你可以返回...
2020-04-22 23:39:58
58
原创 [题记]二叉树的右视图——LeetCode
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。输入: [1,2,3,null,5,null,4]输出: [1, 3, 4]解释: 1 <--- / \2 3 <--- \ \ 5 4 <---一：深搜每次先遍历右子树，将每一...
2020-04-22 20:56:10
97
原创 [题记]D/BFS岛屿数量——LeetCode
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。示例 1:输入:11110110101100000000输出: 1示例 2:输入:11000110000010000011输出: 3解释: 每座岛屿只...
2020-04-20 21:44:05
87
原创 [题记]序列计数——蓝桥杯
小明想知道，满足以下条件的正整数序列的数量：第一项为 n；第二项不超过 n；从第三项开始，每一项小于前两项的差的绝对值。请计算，对于给定的 n，有多少种满足条件的序列。【输入格式】输入一行包含一个整数 n。【输出格式】输出一个整数，表示答案。答案可能很大，请输出答案除以10000的余数。【样例输入】4【样例输出】7【样例说明】以下是满足条件的序列：4 14...
2020-04-18 16:02:07
201
原创 [题记-数学]约瑟夫环-LeetCode
0,1,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。示例 1：输入: n = 5, m = 3输出: 3示例 2：输入: n = 10, m = 17输出: 2限...
2020-04-18 15:56:57
136
原创 [题记-动态规划] 编辑距离 —— LeetCode
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：插入一个字符删除一个字符替换一个字符示例 1：输入：word1 = "horse", word2 = "ros"输出：3解释：horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删...
2020-04-18 15:52:03
75
原创 [题记-并查集] 合根植物 ——蓝桥杯
w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？输入格式： 第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1<m,n<1000）...
2020-04-18 15:48:27
98
原创 [题记-双指针]盛水最多的容器——LeetCode
给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。—说明：你不能倾斜容器，且 n 的值至少为 2。||图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水...
2020-04-18 15:42:28
102
原创 [题记]合并区间——LeetCode
给出一个区间的集合，请合并所有重叠的区间。示例 1:输入: [[1,3],[2,6],[8,10],[15,18]]输出: [[1,6],[8,10],[15,18]]解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].示例 2:输入: [[1,4],[4,5]]输出: [[1,5]]解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。...
2020-04-17 00:12:50
59
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人