- 博客(172)
- 收藏
- 关注
RSS订阅原创 LeetCode-46.全排列
题目给定一个没有重复数字的序列，返回其所有可能的全排列。示例:输入: [1,2,3]输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]解题思路—回溯法：全排列问题是回溯法的经典应用，核心思想就是先固定一段序列的第一个数字，再将后续的数字依次交换。这一过程可以使用递归使用，要注意的是，每次将数字...
2019-06-03 10:41:47
435
原创 LeetCode-146.LRU缓存机制
题目运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。获取数据 get(key) — 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。写入数据 put(key, value) — 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使...
2019-06-01 20:33:11
424
原创 IDEA中无法@Override
在编写程序时，IDEA中的 @Override 一直标红，报错，错误例如：Annotations are not allowed here‘@Override’ not applicable to field在网上查了很多帖子，都是说JDK版本号问题，但是现在普遍都是使用的1.8，所以修改了没有用。其实，只需要恢复IDEA的默认设置即可！！！ 亲测有效。恢复之后，重新配置一次就行。...
2019-05-31 14:50:35
6070
3
原创 LeetCode-43.字符串相乘
题目给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。示例 1:输入: num1 = “2”, num2 = “3”输出: “6”示例 2:输入: num1 = “123”, num2 = “456”输出: “56088”说明：num1 和 num2 的长度小于110。num1 和 num2...
2019-05-30 14:54:17
966
5
原创 LeetCode-23.合并K个排序链表
题目合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。示例:输入: [ 1->4->5, 1->3->4, 2->6 ]输出: 1->1->2->3->4->4->5->6解题思路—最小堆：算法的时间复杂度为O(Nlogk)，其中k 是链表的数目，n 是链表的总节点数；空间复杂度为...
2019-05-30 00:32:49
878
原创 LeetCode-8.字符串转换整数(atoi)
题目请你来实现一个 atoi 函数，使其能将字符串转换成整数。首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可...
2019-05-28 16:50:16
285
原创 LeetCode-41.缺失的第一个正数
题目给定一个未排序的整数数组，找出其中没有出现的最小的正整数。示例 1:输入: [1,2,0]输出: 3示例 2:输入: [3,4,-1,1]输出: 2示例 3:输入: [7,8,9,11,12]输出: 1说明:你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。解题思路—正负翻转：此题有严格的时间复杂度与空间复杂度的要求，想要符合这个要求并不容易，...
2019-05-27 17:36:51
203
原创 LeetCode-40.组合总和II
题目给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。说明：所有数字（包括目标数）都是正整数。解集不能包含重复的组合。示例 1:输入: candidates = [10,1,2,7,6,1,5], target = 8所求解集为: [...
2019-05-27 14:36:14
322
原创 LeetCode-39.组合总和
题目给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。说明：所有数字（包括 target）都是正整数。解集不能包含重复的组合。示例 1:输入: candidates = [2,3,6,7], target = 7所求解集为: [ ...
2019-05-27 10:48:55
163
原创 LeetCode-34.在排序数组中查找元素的第一个和最后一个位置
题目给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。如果数组中不存在目标值，返回 [-1, -1]。示例 1:输入: nums = [5,7,7,8,8,10], target = 8输出: [3,4]示例 2:输入: nums = [5,7,7,8,8,10]...
2019-05-24 15:23:40
301
原创 LeetCode-33.搜索旋转排序数组
题目假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [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], ...
2019-05-23 18:35:04
159
原创 大数据处理相关知识点汇总
大数据处理相关知识点汇总简单统计Map-Reduce概念介绍用Map-Reduce方法统计一篇文章中每个单词出现的个数。海量数据处理解题关键请对10亿个IPV4的ip地址进行排序，每个ip只会出现一次请对10亿人的年龄进行排序。有一个包含20亿个全是32位整数的大文件，在其中找到出现次数最多的数，但是内存限制只有2G。32位无符号整数的范围是0-4294967295。现在有一个正好包含40亿个无符...
2019-05-22 21:26:30
858
原创 概率题目汇总
概率题目汇总球队两强相遇蚂蚁碰头男女比例随机函数等概率产生0和1出现概率变为k次方等概率打印概率动态变化-蓄水池抽样算法球队两强相遇8只球队，有3个强队，其余都是弱队，随机把它们分成4组比赛，每组两个队，问两强相遇的概率是多大？解题思路：首先求出8只球队分成4组的方法数：第一队有7种，第二队有5种，第三队有3种，第四队就剩下1种，所以总数为 7 × 5 × 3 × 1 = 105 种。...
2019-05-22 20:11:26
5868
原创 组合排序题目汇总(排列组合、卡特兰数和递归思想)
概率组合题目汇总排列组合矩阵走法A必须在B左边站队互不相邻站队分糖果球放入桶吃糖卡特兰数括号匹配进出栈顺序/售票顺序二叉树不同的结构数高矮排列递归思想信封装信排列组合矩阵走法在6×9的方格中，以左上角为起点，右下角为终点，每次只能向下走或者向右走，请问一共有多少种不同的走法。解题思路：一共走13步，必然向下要走五步，向右要走8步。所以在13步中选择5步或者8步进行组合即可，公式如下：...
2019-05-22 15:27:26
2332
原创 布隆过滤器概念及其公式推导
布隆过滤器概念及其公式推导布隆过滤器概念数据如何存入布隆过滤器误判情况实际应用面试题公式推导误判概率即失误率的证明和计算其他使用场景公式推导内容转自博客 https://blog.csdn.net/houzuoxin/article/details/20907911布隆过滤器概念数据如何存入布隆过滤器布隆过滤器是由一个很长的二进制矢量和一系列哈希函数组成的。二进制矢量本质是一个位数组：数...
2019-05-21 18:48:34
7644
7
原创 找到二叉树中的最大搜索二叉子树-Java版
题目给定一棵二叉树的头节点head，已知其中所有节点的值都不一样，找到含有节点最多的搜索二叉子树，并返回这棵子树的头节点。例如，下图中，右树就是左树的最大搜索子树。解题思路—后序遍历：后序遍历二叉树，若当前结点的左右子树都符合搜索二叉树，就返回当前结点；若有左子树（右子树）不符合，则返回右子树根节点（左子树根节点）。需要设置全局变量来保存当前子树的最大值、最小值以及节点数。代码不是特别好理...
2019-05-21 14:04:44
1288
转载 将CSDN博客内容保存为PDF
文章转自：https://blog.csdn.net/u010954948/article/details/82843105， 为了方便自己使用，所以在这里保存一下！使用Google Chrome浏览器，在右上角点开设置一栏，找到更多工具—开发者工具，会弹出下图中界面：接下来在Console中黏贴下面一段代码，然后按回车键即可，当前页面的pdf会自动加载出来。(function(){$(...
2019-05-20 18:55:33
7941
4
原创 二叉树知识点总结
二叉树知识点总结二叉树的基本术语定义二叉树的计算公式完全二叉树叶节点计算完全二叉树的节点数计算解题思路—二分思路Java解题—二分思路二叉树的基本术语定义节点的度：指该节点所含子树的个数。叶子节点（终端节点）：度为0的节点。兄弟节点：有共同父节点的节点。非终端节点：叶子以外的节点均为非终端节点，即度不为0的节点。阶层（级）：树的层级，树的根节点的层级为1，其余节点的阶层为该节点父节点...
2019-05-20 17:13:51
1540
原创 LeetCode-31.下一个排列
题目实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。以下是一些例子，输入位于左侧列，其相应输出位于右侧列。1,2,3 → 1,3,23,2,1 → 1,2,31,1,5 → 1,5,1解题思路—反向遍历：这题其实是典型的找规律题，怎么...
2019-05-17 10:44:16
181
原创 LeetCode-18.四数之和
题目给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。注意：答案中不可以包含重复的四元组。示例：给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。满足要求的四元组集合为： ...
2019-05-16 19:47:17
140
原创 LeetCode-16.最接近的三数之和
题目给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).解题思路—双指针：这题与LeetCo...
2019-05-16 18:24:29
150
原创 LeetCode-15.三数之和
题目给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：[ [-1, 0, 1], [-1, -1, 2] ]解题思...
2019-05-16 10:33:09
118
原创 LeetCode-11.盛最多水的容器
题目给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。说明：你不能倾斜容器，且 n 的值至少为 2。解题思路—双指针：两条线与x轴形成的长方形面积，长即为两条线在x轴间的距离，宽即为两条线中最...
2019-05-15 18:54:44
242
原创 LeetCode-5.最长回文子串
题目给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1：输入: “babad”输出: “bab”注意: “aba” 也是一个有效答案。示例 2：输入: “cbbd”输出: “bb”解题思路—中心扩展：遍历字符串，以每一个字符串都作为中间位，判断是否可以向左右扩展。这里要注意的是，i 可以作为偶数位回文中心，也可能作为奇数位回文...
2019-05-15 15:10:05
145
原创 Manacher算法解决最长回文子串问题-Java版
Manacher算法解决最长回文子串问题最长回文子串问题，就是给定一个字符串，求出字符串中最长回文子串的长度。回文串就是从头到尾遍历和从尾到头遍历是一模一样的。暴力求解，把字符串所有子串都找出来，再挨个判断是否为回文子串，再记录最长的长度，这个方法当然是可以的，但是复杂度太高！不推荐！所以设计了Manacher算法(马拉车算法)用来解决最长回文子串问题！字符串初始化处理奇数长和偶数长的回...
2019-05-15 00:21:04
496
原创 KMP算法基础版和进阶版简单解释-Java版
KMP算法基础版和进阶版简单解释KMP算法KMP算法基础版如何理解getNext中的k = next[k]KMP算法基础版代码KMP算法改进版KMP算法改进版代码KMP算法比较口语化的写了为什么k = next[k]和改进版中next[j] = next[k]，以及代码理解中的注意点。KMP算法是一种字符串匹配算法，其关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的...
2019-05-14 16:06:58
592
原创 十大排序算法汇总-Java版（由小到大排序）
十大排序算法汇总-Java版（由小到大排序）1.冒泡排序 — O(N^2)2.选择排序 — O(N^2)3.插入排序 — O(N^2)4.归并排序 — O(NlogN)5.快速排序 — O(NlogN)6.堆排序 — O(NlogN)7.希尔排序 — O(NlogN)8.计数排序 — O(N+K)9.桶排序 — O(N+K)10.基数排序 — O(N×K)1.冒泡排序 — O(N^2)publ...
2019-05-13 19:59:18
1205
1
原创 动态规划示例汇总-Java版(组合硬币、跳台阶、最小路径和、最长递增子序列、最长公共子序列、01背包问题、最小编辑代价)
动态规划算法示例汇总-Java版组合硬币Java解题—暴力搜索Java解题—记忆搜索Java解题—动态规划（两种写法）跳台阶Java解题—暴力递归Java解题—动态规划矩阵最小路径和Java解题—动态规划最长递增子序列Java解题—动态规划字符串最长公共子序列Java解题—动态规划0-1背包问题Java解题—动态规划最小编辑代价Java解题—动态规划组合硬币给定数组arr，arr中所有的值都为...
2019-05-12 23:31:40
924
原创 LeetCode-4.寻找两个有序数组的中位数
题目给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。示例 1:nums1 = [1, 3]nums2 = [2]则中位数是 2.0示例 2:nums1 = [1, 2]nums2 = [3, 4]则中位数是 (...
2019-05-07 20:25:26
210
原创 LeetCode-3.无重复字符的最长子串
题目给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。示例 1:输入: “abcabcbb”输出: 3解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。示例 2:输入: “bbbbb”输出: 1解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。示例 3:输入: “pwwkew”输出: 3解释: 因为无重复字符的最长子串是...
2019-05-07 10:22:56
115
原创 LeetCode-2.两数相加
题目给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。示例：输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -&...
2019-05-06 20:51:30
345
原创 剑指Offer-机器人的运动范围
题目描述地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？解题思路—递归：这题可以抽象成找出以(0,0...
2019-05-06 17:47:50
892
原创 剑指Offer-矩阵中的路径
题目描述请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符...
2019-05-06 13:49:40
368
原创 剑指Offer-滑动窗口的最大值
题目描述给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5...
2019-05-06 00:03:30
174
原创 剑指Offer-数据流中的中位数
题目描述如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。解题思路—直接插入：使用ArrayList，每次输入数据时，使用直接插入的思想，将数据按顺序插入list中...
2019-05-05 16:14:27
165
原创 剑指Offer-二叉搜索树的第k个结点
题目描述给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。何为二叉搜索树？树中每一个结点的值都大于左子结点且小于右子结点。所以若中序遍历二叉搜索树，得到的结果就是由小到大排序的有序数列。解题思路—中序遍历-递归版：通过递归进行中序遍历，当遍历到第k个数值的时候，输出结果。✨解题思路—中序遍历-递归简化版：这段代...
2019-05-05 11:24:08
191
原创 剑指Offer-序列化二叉树
题目描述请实现两个函数，分别用来序列化和反序列化二叉树。示例二叉树序列化{8,4,#,3,#,2}反序列化序列化指的是遍历二叉树为字符串；反序列化指的是依据字符串重新构造成二叉树。下面两种方法，使用ArrayList层次遍历是完全符合二叉树层次序列化示例，即示例输入。而递归的方法不是，这题的输入输出要求并不明确，可能序列化与反序列化函数的结果能互相匹配就能AC。解题思路—使用...
2019-04-30 11:18:42
444
原创 剑指Offer-把二叉树打印成多行
题目描述从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。解题思路—使用ArrayList层次遍历：这题就是剑指Offer—按之字形顺序打印二叉树的简化版。比较基础的就是用ArrayList、Stack或者Queue进行层次遍历。使用size记录每一层的结点个数，依次分层输出。✨解题思路—递归：使用了DFS，深度遍历思想，深度+1，则结果中就多一行ArrayList，然后递归每...
2019-04-29 16:53:40
171
原创 剑指Offer—按之字形顺序打印二叉树
题目描述请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。解题思路—只使用ArrayList模拟堆栈和队列：这题的关键依旧是层次遍历树，但是偶数行正序遍历，奇数行倒序遍历。里面有先进先出以及先进后出的思想，但是都可以用一个ArrayList来模拟。只需要每次都反向遍历，存储时注意left和right的...
2019-04-29 15:41:00
182
原创 剑指Offer-对称的二叉树
题目描述请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。解题思路—中序遍历：使用中序遍历同时搜索左右两棵子树，在遍历的过程中比对左右两棵子树的val，若不相同或有单独的空树，返回false；反之，继续遍历。★解题思路—递归：上一种方法虽然也使用了递归，但是递归结构写的不好，代码冗余，直接将左右结点对比的结果return，代码会更加...
2019-04-28 21:14:42
1415
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人