菜菜的大数据开发之路-CSDN博客

原创 4.＜tag-排序和TopK问题的三种典型解法＞补充: 面试题 17.14. 最小K个数 + lt.215-数组中的第K个最大元素 dbc

TopK问题很普遍, 解题套路也很简单, 无非就是排序, 运用最基础的排序(如Array.sort(nums))复杂度为nlogn, 或者使用堆, 复杂度为nlogk,或者在快排的基础上进行减治详细参见此文:对原数组从小到大排序后取出前K个数即可;我们,首先将前k个数插入到大根堆中, 随后从第k+1个数开始遍历,如果当前遍历到的数比大根堆的堆顶的数要小, 就把堆顶的数弹出, 再插入到当前遍历到的数,最后将大根堆的数存入到数组返回即可.注意, 之所以使用是因为, 每次都是,

2022-10-09 16:25:02 508 1

原创 tag排序-刷题预备知识-2. TopK 解法总结, Java实现 dbc

摘自看过的一篇深度好文, 强推!

2022-10-09 16:23:24 305

原创 23.＜tag-二叉树和树的链化问题＞补充: 剑指 Offer 36. 二叉搜索树与双向链表(同lt.426. 将二叉搜索树转化为双向链表) dbc

23.＜tag-二叉树和树的链化问题＞补充: 剑指 Offer 36. 二叉搜索树与双向链表(同lt.426. 将二叉搜索树转化为双向链表) dbc

2022-10-07 14:27:55 303

原创 22.＜tag-二叉树和树的链化,构建问题＞补充: lt.114. 二叉树展开为链表 + lt.108. 将有序数组转换为二叉搜索树 dbc

题目中，要求说是 in-place，之前一直以为这个意思就是要求空间复杂度是 O(1)O(1)。偶然看见评论区大神的解释， in-place 的意思可能更多说的是直接在原来的节点上改变指向，空间复杂度并没有要求。所以这道题也可以用递归解一下。

2022-10-05 13:11:00 349

原创 21.＜tag-二叉树和树的构建问题＞补充: lt.297. 二叉树的序列化与反序列化 dbc

【代码】21.＜tag-二叉树和树的构建问题＞补充: lt.297. 二叉树的序列化与反序列化 dbc。

2022-09-24 22:25:46 128

原创 20.＜tag-二叉树和递归遍历问题＞补充: lt.543. 二叉树的直径 + lt.124. 二叉树中的最大路径和

本道题等同于求一个节点左右子树的最大高度之和, 注意他跟104.二叉树的最大深度的区别在于, 他的路径可以不经过根节点.

2022-09-24 21:48:22 152

原创 8.＜tag-字符串和综合问题补充:lt.71. 简化路径 + lt.6. Z 字形变换 + lt.12. 整数转罗马数字 + lt.680. 验证回文串 II dbc

【代码】8.＜tag-字符串和综合问题补充:lt.71. 简化路径 + lt.6. Z 字形变换 + lt.12. 整数转罗马数字 + lt.680. 验证回文串 II dbc。

2022-09-22 17:58:58 201

原创 7.＜ tag-哈希表和数据结构设计＞补充: lt.705. 设计哈希集合 + lt.706. 设计哈希映射 + lt.380. O(1) 时间插入、删除和获取随机元素 dbc

1.由于题目给出了 0

2022-09-22 14:09:23 230

原创 6.＜ tag-哈希表和前缀和累加计数＞补充: lt.554. 砖墙

【代码】6.＜ tag-哈希表和前缀和累加计数＞补充: lt.554. 砖墙。

2022-09-22 11:50:01 109

原创 6. ＜tag-队列和单调队列问题＞补充: lt.239. 滑动窗口最大值 dbc

剑指 Offer 59 - II. 队列的最大值，

2022-09-21 21:37:40 677

原创 5.＜ tag-哈希表和TopK问题＞补充: lt.347. 前 K 个高频元素 + lt.692. 前K个高频单词 0.1 dbc

遍历Map, 将k个数传入优先队列, 超过k个就比较队列头元素和遍历到的key 的频次大小.先遍历一次, 用HashMap记录 ⇒ ;定义一个优先队列, 传入自定义比较器, 按照词频从大到小的顺序排列;遍历优先队列, 将他们放入到数组中返回即可;

2022-09-13 17:44:20 208

原创 4.＜tag-哈希表, 字符串, 滑动窗口＞补充: lt.3. 无重复字符的最长子串(同剑指 Offer 48) 0.5 dbc

【代码】4.＜tag-哈希表, 字符串, 滑动窗口＞补充: lt.3. 无重复字符的最长子串(同剑指 Offer 48) dbc。

2022-09-13 17:11:44 171

原创 19.＜tag-二叉树和公共祖先问题＞补充: lt.lt.236. 二叉树的最近公共祖先 + lt.235. 二叉搜索树的最近公共祖先（同剑指Offer 61 I，II）

如果找到了节点p或者q，或者遇到空节点，就返回。3, 确定单层递归逻辑值得注意的是，本题函数有返回值，是因为回溯的过程需要递归函数的返回值做判断，但是本题我们依然要遍历树的所有结点。...

2022-08-31 12:18:28 211

原创 18.＜tag-二叉树和回溯(路径问题)＞补充: lt.617. 合并二叉树 0.1

【代码】16.＜tag-二叉树和回溯(路径问题)＞补充: lt.617. 合并二叉树。

2022-08-31 11:07:55 120

原创 17.＜tag-二叉树和回溯(路径问题)＞补充:lt.129. 求根节点到叶节点数字之和 0.5

【代码】16.＜tag-二叉树和回溯(路径问题)＞补充:非根节点,叶节点的路径问题- lt.437. 路径总和 III (同面试题 04.12. 求和路径) dbc。

2022-08-29 14:45:15 170

原创 16.＜tag-二叉树和对常规遍历的理解＞补充: lt. 538. 把二叉搜索树转换为累加树(同lt.1038. 从二叉搜索树到更大和树) 2

比较无聊的一道题, 但是还是提醒我们, 不要忘了二叉树前中后序, 无时无刻不在各种各种的题目中得到应用。

2022-08-29 10:09:30 138

原创 15.＜tag-二叉树和回溯(路径问题)＞补充:非根节点,叶节点出发的路径和问题- lt.437. 路径总和 III (同面试题 04.12. 求和路径) dbc

【代码】14.＜tag-二叉树和回溯(路径问题)＞补充:非根节点,叶节点的路径问题- lt.437. 路径总和 III (同面试题 04.12. 求和路径) dbc。

2022-08-28 17:35:15 676

原创 8.＜tag-数学问题＞补充: lt.7. 整数反转 dbc

【代码】8.＜tag-数学问题＞补充: lt.7. 整数反转 dbc。

2022-08-23 10:32:47 226

原创 3.＜tag-哈希表, 字符串＞补充: lt.49. 字母异位词分组 + lt.242. 有效的字母异位词 + 438. 找到字符串中所有字母异位词 0.5

代码】3.＜tag-哈希表, 字符串＞补充: lt.49. 字母异位词分组 + lt.242. 有效的字母异位词 dbc。

2022-08-17 14:14:18 210

原创 3.＜tag-排序和最大数, 较小数问题＞补充: 剑指 Offer 45. 把数组排成最小的数 + lt.179. 最大数 dbc

3.＜tag-排序和最大数, 较小数问题＞补充: 剑指 Offer 45. 把数组排成最小的数 + lt.179. 最大数

2022-08-16 00:00:18 144

原创 33.＜ tag-数组和旋转(同字符的旋转)＞补充: lt.189. 轮转数组(右旋数组) + 剑指 Offer 58 - II. 左旋转字符串(左旋字符串) 1

代码】32.＜ tag-数组和数学＞补充: lt.189. 轮转数组 dbc。

2022-08-11 00:44:37 107

原创 tag单调栈-单调栈预备知识-lt.739. 每日温度

通常是。那么单调栈的原理是什么呢？为什么时间复杂度是O(n)就可以找到每一个元素的右边第一个比它大的元素位置呢？单调栈的本质是。

2022-08-02 16:15:47 108

原创 13.＜ tag-动态规划和回文字串＞lt.647. 回文子串 + lt.516.最长回文子序列

代码】13.＜tag-动态规划和回文字串＞lt.647.回文子串+lt.516.最长回文子序列。

2022-08-02 11:34:17 133

原创 12.＜ tag-动态规划和子序列, 子数组＞lt.72. 编辑距离

dp[i][0]以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0],显然为i,即删除i次。又因为,我们由递推公式得知,需要初始化dp[0][0],dp[i][0],dp[0][j]三种元素.那么dp[i][0]就应该是i，对word1里的元素全部做删除操作，即dp[i][0]=i;我们在回顾一下dp[i][j]的定义;同理,同理dp[0][j]=j;此时就需要编辑了，如何编辑呢？那么他们代表什么呢?...

2022-07-28 12:08:02 86

原创 7.＜tag-字符串和API的取舍＞补充: 剑指 Offer 05. 替换空格 0.1

使用StringBuilder,不断遍历原有的字符串,在sb.append过程中遇到空格时,替换为%20即可;或者创建字符数组,然后遍历String中的每一个char字符,注意这个字符数组长度->因为是一个空格要变成了三个字符(%20),所以总长度(当然了如果除了空格之外还有其他元素,所以不太可能用完)...

2022-07-27 21:25:36 94

原创 11.＜ tag-动态规划和子序列, 子数组＞lt.115. 不同的子序列 + lt. 583. 两个字符串的删除操作 dbc

代码】11.＜tag-动态规划和子序列,子数组＞lt.115.不同的子序列+lt.583.两个字符串的删除操作

2022-07-27 14:47:05 108

原创 10.＜ tag-动态规划和子序列, 子数组＞lt.53. 最大子数组和 + lt.392. 判断子序列 dbc

10.＜ tag-动态规划和子序列, 子数组＞lt.53. 最大子数组和 + lt.392. 判断子序列

2022-07-25 16:13:25 103

原创 9.＜ tag-动态规划和子序列, 子数组＞lt.718. 最长重复子数组 + lt.1143. 最长公共子序列

9.＜ tag-动态规划和子序列, 子数组＞lt.718. 最长重复子数组 + lt.1143. 最长公共子序列

2022-07-24 20:49:00 110

原创 8.＜ tag-动态规划和LCS问题＞lt.300. 最长递增子序列 + lt.674. 最长连续递增序列

有题dp[i]是可以用dp[j](j

2022-07-22 15:51:26 104

原创 32.＜ tag-数组和位运算＞补充: lt.剑指 Offer 56 - I. 数组中数字出现的次数

代码】32.＜tag-数组和位运算＞补充lt.剑指Offer56-I.数组中数字出现的次数。

2022-07-22 15:42:05 68

原创 7.＜ tag-动态规划和买卖股票合集＞lt.121. 买卖股票的最佳时机 + lt.122.买卖股票的最佳时机 II+ lt.123. 买卖股票的最佳时机 III dbc

因为股票就买卖一次，那么贪心的想法很自然就是取最左最小值，取最右最大值，那么得到的差值就是最大利润。表示第i天持有股票所得最多现金,这里可能有同学疑惑，本题中只能买卖一次，持有股票之后哪还有现金呢？其实一开始现金是0，那么加入第i天买入股票现金就是-prices[i]，这是一个负数。表示第i天不持有股票所得最多的现金。注意这里说的是“持有”，“持有”不代表就是当天“买入”！也有可能是昨天就买入了，今天保持持有的状态.很多同学把“持有”和“买入”没分区分清楚。持有b.如果第i天不持有。......

2022-07-21 11:20:47 103

原创 6.＜ tag-动态规划和打家劫舍合集(树形DP)＞lt.198.打家劫舍 + lt.213. 打家劫舍 II + lt.337. 打家劫舍 III dbc

dp[i]考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]决定dp[i]的因素是第i房间偷还是不偷,如果偷第i房间,那么dp[i]=dp[i-2]+nums[i],因为dp总是由之前的状态得到现在的状态嘛,如果要偷i,那么前一次只能偷i-2下标的房屋,用dp[i-2]+nums[i]才能得到偷dp[i]获得的金额如果不偷第i房间,那么dp[i]=dp[i-1],即包括i-1房间能够偷到的最大价值。...

2022-07-20 12:04:06 133

原创 Hive 自定义函数编写(UDF,UDAF,UDTF)

虽然hive中为我们提供了很多的内置函数，但是在实际工作中，有些情况下hive提供的内置函数无法满足我们的需求，就需要我们自己来手动编写，所以就有了自定义函数UDF。UDF分为三种，分别如下一进一出（输入一行，输出一行），输入一行数据,输出一行数据;比如upper()、lowser()等。，多进一出（输入多行，输出一行），输入多行数据,聚合成一行数据,比如avg()、sum()等。，一进多出（输入一行，输出多行），比如官方文档https。............

2022-07-17 16:43:10 944