博文中会简要介绍Leetcode P0273题目分析及解题思路。
“Integer to English Words”是一道稍难的题目。这道题的主要思路是利用分而治之的想法。
Convert a non-negative integer num to its English words representation.
Example 1:
Input: num = 123 Output: "One Hundred Twenty Three"Example 2:
Input: num = 12345 Output: "Twelve Thousand Three Hundred Forty Five"Example 3:
Input: num = 1234567 Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
这道题的分治思想的核心在于切分给定的数，每三位为一个划分，例如，12345678应当被划分为12,345,678。这样划分的目的是在英语的表达中，每三位会使用一个量词，譬如“千”、“百万”等等。进行每三位位一个划分后，不同划分内的表达是一致的，自然地就可以使用分治的思想，每个划分的处理方法是一致。
以下是Java的题解代码实现。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
this.maxHeap = new PriorityQueue<>((x, y) -> {
return Double.compare(y.getKey(), x.getKey());
});
this.dfs(root, target, k);
List<Integer> ret = new ArrayList<>();
while (!this.maxHeap.isEmpty()) {
ret.add(this.maxHeap.poll().getValue());
}
return ret;
}
private PriorityQueue<Pair<Double, Integer>> maxHeap = null;
private void dfs(TreeNode cur, double target, int k) {
if (cur == null)
return;
double diff = Math.abs(target-cur.val);
if (this.maxHeap.size() >= k) {
if (diff < this.maxHeap.peek().getKey()) {
this.maxHeap.poll();
this.maxHeap.offer(new Pair(diff, cur.val));
}
}
else {
this.maxHeap.offer(new Pair(diff, cur.val));
}
this.dfs(cur.left, target, k);
this.dfs(cur.right, target, k);
return;
}
}
以下是C++的题解代码实现。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
template<class K, class V>
struct PairComparator {
bool operator() (pair<K, V> x, pair<K, V> y) const {
return x.first < y.first;
}
};
class Solution {
public:
vector<int> closestKValues(TreeNode* root, double target, int k) {
_Dfs(root, target, k);
vector<int> ret;
while (!_max_heap.empty()) {
ret.push_back(_max_heap.top().second);
_max_heap.pop();
}
return ret;
}
private:
priority_queue<pair<double, int>, vector<pair<double, int>>, PairComparator<double, int>> _max_heap;
void _Dfs(TreeNode *cur, double target, int k) {
if (!cur)
return;
double diff = abs(target-cur->val);
if (_max_heap.size() >= k) {
if (diff < _max_heap.top().first) {
_max_heap.pop();
_max_heap.emplace(diff, cur->val);
}
}
else {
_max_heap.emplace(diff, cur->val);
}
_Dfs(cur->left, target, k);
_Dfs(cur->right, target, k);
return;
}
};