作者:TeddyZhang,公众号:算法工程师之路
字符串问题:
LeetCode # 397 398 401 404 405 406
1
编程题
【LeetCode #397】整数替换
给定一个正整数 n,你可以做如下操作:
示例 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