讨论/题目交流/🏆 第 172 场力扣周赛/
🏆 第 172 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛】

image.png

3 分 - 6 和 9 组成的最大数字
4 分 - 竖直打印单词
5 分 - 删除给定值的叶子节点
6 分 - 灌溉花园的最少水龙头数目

展开讨论
力扣 (LeetCode)发起于 2020-01-19

6 和 9 组成的最大数字

思路
  1. 转换成字符串
  2. 把第一个 6 改成 9
答题
int maximum69Number (int num) {
    string n = to_string(num);
    for (size_t i = 0; i < n.size(); i++)
    {
        if (n[i] == '9') continue;
        n[i] = '9';
        break;
    }
    return stoi(n);
}

竖直打印单词

思路
  1. 先按照空格分开单词,保存到vector中
  2. 同步所有单词的字母索引,按顺序填入string temp
  3. 如果哪个单词不够长,就补空格
  4. 把temp去掉尾部空格,填入返回的结果中
答题
void trimR(string& input)
{
	input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
		return !isspace(ch);
		}).base(), input.end());
}

vector<string> printVertically(string s)
{
	stringstream ss(s);
	vector<string> aa;
	string temp;
	while (ss >> temp) aa.push_back(temp);

	vector<string> ans;
	bool flag = true;
	size_t i = 0;
	while (flag)
	{
		flag = false;
		temp = "";
		for (auto& a : aa)
		{
			if (i >= a.size())
			{
				temp += " ";
			}
			else
			{
				flag = true;
				temp += a[i];
			}
		}
		trimR(temp);
		ans.push_back(temp);
		i++;
	}
	ans.pop_back();
	return ans;
}

删除给定值的叶子节点

思路
  1. 只能删叶子节点
  2. 如果叶子节点都删完了,其父节点会变成新的叶子节点
  3. 根据特点,使用后序遍历
  4. 找到叶子节点,判断是否删除
    41. C++ 注意删除时,不能 delete 传入的参数,指针置空就好
  5. 递归
答题
TreeNode* removeLeafNodes(TreeNode* root, int target) 
{
	if (root == nullptr) return nullptr;

	root->left = removeLeafNodes(root->left, target);
	root->right = removeLeafNodes(root->right, target);

	return (root->left == nullptr && root->right == nullptr && root->val == target) ? nullptr : root;
}

灌溉花园的最少水龙头数目

思路
  1. n 代表土地数量(0 - 1 之间是一块地,1 - 2 之间是一块地)
  2. n + 1 代表水龙头数量,水龙头插在数字上
  3. ranges 代表当前位置的水龙头,向左向右可以覆盖多少块地
  4. 定义一个 land 数据

代表“在能够覆盖这块土地的所有水龙头中,找到往右边能够覆盖到最远位置的水龙头,记录它最右覆盖的土地”
索引 0 代表覆盖了 0 - 1 之间这块地的所有水龙头,能够覆盖到最右的土地
比如值是 5 ,代表覆盖到了 4 - 5 这块地
索引是水龙头右边的那块地,而值是水龙头左边的那块地
因此下面代码中 cur = land[cur]; 表示无缝的覆盖过去

  1. 将 ranges 转换为 land 数据
  2. 从土地 0 开始,一直到土地 n ,记录数目
答题
int minTaps(int n, vector<int>& ranges) 
{
	vector<int> land(n);
	for (int i = 0; i < ranges.size(); i++)
	{
		int l = max(i - ranges[i], 0);
		int r = min(i + ranges[i], n);
		if (l == r) continue;
		for (int j = l; j < r; j++)
		{
			land[j] = max(land[j], r);
		}
	}

	int cnt = 0;
	int cur = 0;
	while (cur < n)
	{
		if (land[cur] == 0) return -1;
		cur = land[cur];
		cnt++;
	}
	return cnt;
}
致谢

虽然题很简单,但是
第一次完赛也要撒花!

感谢观看

5
展开全部 9 讨论