- 浏览: 130593 次
文章分类
- 全部博客 (189)
- Tree (14)
- Dynamic Programming (34)
- Array (20)
- Search (1)
- Hash (12)
- Backtracking (22)
- Divide and Conque (8)
- Greedy (6)
- Stack (12)
- software (0)
- List (7)
- Math (22)
- Two pointers (16)
- String (20)
- Linux (1)
- Sliding Window (4)
- Finite State Machine (1)
- Breadth-first Search (7)
- Graph (4)
- DFS (6)
- BFS (3)
- Sort (9)
- 基础概念 (2)
- 沟通表达 (0)
- Heap (2)
- Binary Search (15)
- 小结 (1)
- Bit Manipulation (8)
- Union Find (4)
- Topological Sort (1)
- PriorityQueue (1)
- Design Pattern (1)
- Design (1)
- Iterator (1)
- Queue (1)
最新评论
-
likesky3:
看了数据结构书得知并不是迭代和递归的区别,yb君的写法的效果是 ...
Leetcode - Graph Valid Tree -
likesky3:
迭代和递归的区别吧~
Leetcode - Graph Valid Tree -
qb_2008:
还有一种find写法:int find(int p) { i ...
Leetcode - Graph Valid Tree -
qb_2008:
要看懂这些技巧的代码确实比较困难。我是这么看懂的:1. 明白这 ...
Leetcode - Single Num II -
qb_2008:
public int singleNumber2(int[] ...
Leetcode - Single Num II
Leetcode - Closest Binary Search Tree Value II
- 博客分类:
- Tree
- Stack
- PriorityQueue
[分析]
思路1:遍历所有节点找到和 target最接近的 k 个元素,能否有个数据结构在遍历过程中维护已遍历元素离target最近的呢?PriorityQueue具备这种能力。我们需要个最小堆,堆元素需要保存两个信息,一个是树节点元素值,一个是这个元素和target的差的绝对值。但PriorityQueue是没有“堆底”概念的,当堆的size 增长到 k 后,如何删除堆中最大元素呢? 为实现删除最小堆中最大值的操作,可以再维护一个最大堆,两个堆同步更新,需要从堆中删除元素时一定时删除最大堆的堆顶元素。
实现注意点:
1)想清楚堆节点元素保存什么信息
2)新定义的Pair类要么实现了Comparable接口,要么在创建堆时传入比较器,否则运行时抛异常(PriorityQueue在JAVA文档中是这么声明的:A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).)。
3)minHeap 靠maxHeap来删除元素,因此往两个堆中添加元素时必须时同一个对象。
思路2:参考https://leetcode.com/discuss/55240/ac-clean-java-solution-using-two-stacks。 作者非常巧妙的利用了inorder遍历的特性,inorder遍历可得到某个元素的sorted predecessors, 逆inorder则可得到sorted successors.强悍!
思路1:遍历所有节点找到和 target最接近的 k 个元素,能否有个数据结构在遍历过程中维护已遍历元素离target最近的呢?PriorityQueue具备这种能力。我们需要个最小堆,堆元素需要保存两个信息,一个是树节点元素值,一个是这个元素和target的差的绝对值。但PriorityQueue是没有“堆底”概念的,当堆的size 增长到 k 后,如何删除堆中最大元素呢? 为实现删除最小堆中最大值的操作,可以再维护一个最大堆,两个堆同步更新,需要从堆中删除元素时一定时删除最大堆的堆顶元素。
实现注意点:
1)想清楚堆节点元素保存什么信息
2)新定义的Pair类要么实现了Comparable接口,要么在创建堆时传入比较器,否则运行时抛异常(PriorityQueue在JAVA文档中是这么声明的:A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).)。
3)minHeap 靠maxHeap来删除元素,因此往两个堆中添加元素时必须时同一个对象。
思路2:参考https://leetcode.com/discuss/55240/ac-clean-java-solution-using-two-stacks。 作者非常巧妙的利用了inorder遍历的特性,inorder遍历可得到某个元素的sorted predecessors, 逆inorder则可得到sorted successors.强悍!
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { Comparator<Pair> ascendComparator = new Comparator<Pair>() { public int compare(Pair a, Pair b) { return (int)(a.diff - b.diff); } }; Comparator<Pair> descendComparator = new Comparator<Pair>() { public int compare(Pair a, Pair b) { return (int)(b.diff - a.diff); } }; public List<Integer> closestKValues(TreeNode root, double target, int k) { List<Integer> result = new ArrayList<Integer>(); if (root == null) return result; PriorityQueue<Pair> minHeap = new PriorityQueue<Pair>(k, ascendComparator); PriorityQueue<Pair> maxHeap = new PriorityQueue<Pair>(k, descendComparator); helper(root, target, k, minHeap, maxHeap); Iterator<Pair> iter = minHeap.iterator(); while (iter.hasNext()) { result.add(iter.next().value); } return result; } public void helper(TreeNode root, double target, int k, PriorityQueue<Pair> minHeap, PriorityQueue<Pair> maxHeap) { if (root != null) { double currDiff = Math.abs(root.val - target); if (minHeap.size() < k || currDiff < maxHeap.peek().diff) { if (minHeap.size() == k) { minHeap.remove(maxHeap.poll()); } Pair pair = new Pair(currDiff, root.val); minHeap.offer(pair); maxHeap.offer(pair); } helper(root.left, target, k, minHeap, maxHeap); helper(root.right, target, k, minHeap, maxHeap); } } class Pair{ double diff; int value; public Pair(double diff, int value) { this.diff = diff; this.value = value; } } }
发表评论
-
Inorder Successor in BST
2015-09-26 17:49 688[分析] 参考https://leetcode.com/dis ... -
Lowest Common Ancestor of A Binary Tree
2015-09-26 11:39 534[分析] 最近公共祖先(LCA)是一个经典问题,以前没有好好 ... -
Leetcode - Graph Valid Tree
2015-09-02 08:50 2236Given n nodes labeled from 0 to ... -
Leetcode - Closest Binary Search Tree Value II
2015-09-01 09:50 3140Given a non-empty binary search ... -
Leetcode - Binary Tree Postorder
2015-08-29 21:07 507[分析] 迭代实现后序遍历比迭代实现先序和中序都要稍微复杂,对 ... -
Leetcode - Binary Tree Upside Down
2015-08-29 18:50 383Given a binary tree where all t ... -
Leetcode - Verify Preorder Sequence in Binary Search Tree
2015-08-29 16:46 2999[分析] 思路1:暴力法,遍历当前待检查数组,找到第一个大于数 ... -
Leetcode - Min Stack
2015-08-29 11:20 514[分析] 这题属于简单题 ... -
Leetcode - Basic Calculator II
2015-08-27 09:16 865mplement a basic calculator to ... -
Leetcode - Converted Sorted List to BST
2015-08-23 20:07 324Given a singly linked list wher ... -
Leetcode - Kth Smallest Element in BST
2015-08-11 10:26 619[分析] 思路1: 递归中序遍历,返回中序遍历中的第k个数。 ... -
Leetcode - Recover Binary Search Tree
2015-07-02 09:27 493Two elements of a binary search ... -
Leetcode - Validate Binary Search Tree
2015-07-01 08:31 563Given a binary tree, determine ... -
Leetcode - Simplify Path
2015-06-17 21:58 397Given an absolute path for a fi ... -
Leetcode - Calculator
2015-06-10 09:31 507[分析] 思路1:逆序遍历字符串,数字和右括号保存在一个堆栈s ... -
Leetcode - Count Complete Tree Nodes
2015-06-07 20:51 740Definition of a complete binary ... -
Leetcode - Contains Duplicate III
2015-06-07 20:08 472Given an array of integers, fi ... -
Leetcode - Maximal Square
2015-06-04 08:25 588Given a 2D binary matrix fille ... -
Leetcode - Maximum Rectangle
2015-05-20 08:58 463Given a 2D binary matrix fill ... -
Leetcode - Largest Rectangle in Histogram
2015-05-20 07:53 460Given n non-negative integers ...
相关推荐
leetcode-tag-Tree
《leetcode-solutions》,刷算法题,需要有一定的英文阅读能力。。。
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
IDEA 插件,lettcode刷题,leetcode-editor7.4版本下载进行本地导入(直接将压缩包拖进IDEA即可)
Algorithm-leetcode-spider.zip,leetcode公司,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
在IDE中解决LeetCode问题,支持leetcode.com与leetcode-cn.com,满足基本的做题需求。 理论上支持: IntelliJ IDEA PhpStorm WebStorm PyCharm RubyMine AppCode CLion GoLand DataGrip Rider MPS Android Studio。
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
leetcode 答案解析 golang解答
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/bin/leetcode 修改模板 open ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/...
leetcode-helper-1.7.1
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...
leetcode-tag-dynamic programming
LeetCode-BinarySearch
leetcode卡LeetCode---二分搜索 该存储库包括二进制搜索探索卡中所有问题的解决方案。
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode-tag-Stack
然后进入到LeetCode-Spider目录中修改config.json,其中outputDir需要填写该工程的/docs/views文件夹路径 { "username": "aaa", "password": "bbb", "outputDir": "/Users/liuyao/Downloads/LeetCode-Blog-Test/docs...