字符串问题-LeetCode 397、398、401、404、405、406（蓄水池抽样）
字符串问题-LeetCode 397、398、401、404、405、406（蓄水池抽样）
作者：TeddyZhang，公众号：算法工程师之路
字符串问题：
LeetCode # 397 398 401 404 405 406
1
编程题
【LeetCode #397】整数替换
给定一个正整数 n，你可以做如下操作：
- 1. 如果 n 是偶数，则用 n / 2替换 n。
- 2. 如果 n 是奇数，则可以用 n + 1或n - 1替换 n。 n 变为 1 所需的最小替换次数是多少？
示例 1: 输入: 8 输出: 3 解释: 8 -> 4 -> 2 -> 1
class Solution {
public:
int integerReplacement(int n) {
return static_cast<int>(dfs(static_cast<long>(n)));
}
private:
long dfs(long n) {
if (n == ) return ;
if (n & ) {
return + min(dfs(n+), dfs(n-1));
} else {
return + dfs(n / );
}
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/integer-replacement
【LeetCode #398】随机数索引
给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。您可以假设给定的数字一定存在于数组中。
注意： 数组大小可能非常大。使用太多额外空间的解决方案将不会通过测试。
解题思路：
使用大数据中常用的蓄水池抽样算法，即：从N个元素中随机等概率的抽取k个元素，其中N无法确定，在本题中，我们需要从与target相同的位置进行随机抽取。 伪代码：
init : a reservoir with the size：k for i= k+1 to N M=random(1, i); if( M < k) SWAP the Mth value and ith value end for
class Solution {
public:
Solution(vector<int>& nums) : nums_(nums), dre(time()) {}
int pick(int target) {
int cnt = ;
int idx = ;
for(int i = ; i < nums_.size(); i++) {
if (nums_[i] == target){
++cnt;
std::uniform_int_distribution<int> uid(, cnt);
if (uid(dre) == cnt)
idx = i;
}
}
return idx;
}
private:
std::default_random_engine dre;
vector<int> nums_;
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/random-pick-index
【LeetCode #401】二进制手表
二进制手表顶部有 4 个 LED 代表小时（0-11），底部的 6 个 LED 代表分钟（0-59）。 每个 LED 代表一个 0 或 1，最低位在右侧。 例如，上面的二进制手表读取 “3:25”。
给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。
案例: 输入: n = 1 返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]
解题思路： 暴力枚举，然后计算对应数字中二进制1的个数，从而得到结果。
class Solution {
public:
int count1(int n) {
int res = ;
while(n) {
if (n & ) res++;
n = n >> ;
}
return res;
}
vector<string> readBinaryWatch(int num) {
vector<string> res;
for(int i = ; i < ; i++) {
for(int j = ; j < ; j++) {
if (count1(i) + count1(j) == num){
string tmp = to_string(j);
if (j < ) tmp = "0" + to_string(j);
res.push_back(to_string(i) + ":" + tmp);
}
}
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-watch
【LeetCode #404】左叶子之和
计算给定二叉树的所有左叶子之和。
示例：
3 / \ 9 20 / \ 15 7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == nullptr) return ;
if (root->left && root->left->left == nullptr && root->left->right == nullptr) // 左节点存在
return root->left->val + sumOfLeftLeaves(root->right);
else
return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sum-of-left-leaves
【LeetCode #405】数字转换为十六进制数
给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。 示例 1： 输入: 26 输出: "1a"
解题思路：
当num为负整数时，可以对其补码进行十六进制转换。 使用ans = hex[…] + ans，可以进行拼接，由于第一次ans取出的是后四位，因此需要拼接在后面。
class Solution {
public:
string toHex(int num) {
if (num == ) return "0";
string hex = "0123456789abcdef", ans = "";
while(num && ans.size() < ){
ans = hex[num & 0xf] + ans;
num >>= ;
}
return ans;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/convert-a-number-to-hexadecimal/
【LeetCode #406】根据身高重建队列
假设有打乱顺序的一群人站成一个队列。每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。编写一个算法来重建这个队列。
注意： 总人数少于1100人。
示例 输入: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] 输出: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
解题思路：
首先我们对people 进行排序，按照身高从高到低，并且在身高相同时，按照k从小到大排序。接着，按照k值对res进行插入元素，得到最后的结果。
class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
vector<vector<int>> res;
auto cmp = [](vector<int>& a, vector<int>& b) {
if (a[] != b[]) return a[] > b[];
else return a[] < b[];
};
sort(people.begin(), people.end(), cmp);
for(auto p: people) {
res.insert(res.begin()+p[], p);
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/queue-reconstruction-by-height