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

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

image.png

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

展开讨论
共 9 个讨论

好像是为了大家过好年,今天的题极其简单。

7

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

第三题,示例5输出不对

3

6 和 9 组成的最大数字

用字符串做抢了把时间, 判断有没有6,和第一个6的位置

class Solution:
    def maximum69Number (self, num: int) -> int:
        if '6' not in str(num):
            return num
        for i, v in enumerate(str(num)):
            if v=='6':
                return int(str(num)[:i]+'9'+str(num)[i+1:])

竖直打印单词

用空格切分字符串,去最长字符串长度,在暴力遍历,越界追加空格

class Solution:
    def printVertically(self, s: str) -> List[str]:
        lis = s.split(' ')
        res = []
        tag = 0
        ma = 0
        for i in lis:
            ma = max(ma, len(i))

        for i in range(ma):
            tmp = ""
            for i in range(len(lis)):
                if tag>len(lis[i])-1:
                    tmp+=" "
                else:
                    tmp+=lis[i][tag]
            res.append(tmp.rstrip(' '))
            tag+=1
        return res

删除给定值的叶子节点

后序遍历,判断左右子节点是不是空,自己本身是不是等于目标值,符合的话=空
测试用例错了一个,以为眼瞎看错题,硬是瞪了3分钟才提交

class Solution:
    def removeLeafNodes(self, root: TreeNode, target: int) -> TreeNode:


        def dfs(node, parent, tag):
            if not node: return

            dfs(node.left, node, 'L')
            dfs(node.right, node, 'R')

            if node.val==target and not node.right and not node.left:
                if tag=='L':
                    parent.left = None
                elif tag=='R':
                    parent.right = None
                elif tag=='':
                    root = None

        dfs(root, None, '')

        if not root.left and not root.right and root.val==target:
            root = None

        return root

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

预处理一下每个点覆盖范围,左界和右届,按左界升序排序
贪心一下,如果最左端覆盖不到0,直接返回-1
如果中间有覆盖不到区域也返回-1
其他情况就按照右端,来删除前面 比如[0, 4], [2, 5], [3, 6] 遇到3,6就删除2,5
根据左端覆盖情况来判断

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        ran = []
        for i, v in enumerate(ranges):
            ran.append([i-v, i+v])

        ran.sort()
        res = [ran[0]]

        print(ran)

        low, height = ran[0][0], ran[0][1]

        for i in range(1, len(ran)):
            ll, hh = ran[i]
            if ll>height:
                return -1

            elif low<=0 and ll<=0 and ll>=low and hh>=height:
                res.pop()
                res.append(ran[i])
                low = ll
                height = hh
            elif hh<=height:
                continue
            elif hh>height:
                while len(res)>1 and ll<=res[-2][1]:
                    res.pop()
                height = hh
                res.append(ran[i])

            if hh>=n: break

        return len(res) if height>=n else -1
2

最后一题用动态规划写怎么写怎么超时

1

前3题,半小时不到就写完了...
第4题,开始想水龙头有开关两种状态,用位压缩看看....瞄了一眼数据...不可能了...
贪心,从覆盖最广的开始?还是动态规划,每个都检查一下?
后来把每个水龙头的覆盖范围都求出来[[L, R].....],排了个序...答案就出来了.
0-n1, 0是必须要有的,就从0开始往右推,
第一次 0-n1, n1要取最大,因为已经排序,遍历所有L<=n1的水龙头,如果[L,R]的L>n1, 就计数一次,把之前的水龙头的[L, R]中的R赋给n1,
然后求下一次的n1,
找R的过程中, 如果n1已经全部覆盖了,就返回当前的计数.
如[[0, 1], [0, 3], [1, 3], [2, 6], [4, 6], [6, 7]]
第一次 0,3 n1 = 3 L <= 0 的有 [0, 1], [0, 3] 取最大的[0, 3] n1 = 3
第二次 0,6 n1 = 6 L <= 3 的有 [1, 3], [2, 6], 取最大的[2, 6] n1 = 6
第三次 0,7 n1 = 7 L <= 6 的有 [4, 6], [6, 7] 取最大的[6, 7] n1 = 7 已经覆盖范围,返回计数 3.

1

我想问一下第三题的这个测试数据

[3,3,6,3,1,null,3,8,6,null,null,6,3,3,5,3,3,3,6,null,8,null,3,null,null,8,null,2,6,6,3,3,3,null,9,2,8,3,5,null,null,null,7,null,3,null,null,3,5,null,3,null,null,null,3,null,3,null,null,5,3,7,7,1,3,6,null,null,3,null,8,null,null,4,null,null,null,null,null,null,3,null,null,3,null,3,4,null,8,null,null,null,null,null,null,null,null,2,3,null,3,3,null,3,null,null,2,null,3,null,null,null,null,null,null,8,null,3,null,null,null,2,9,3]
3

最后的结果是
[3,3,6,3,1,null,3,8,6,null,null,6,3,3,5,3,3,3,6,null,8,null,3,null,null,8,null,2,6,6,null,3,3,null,9,2,8,null,5,null,null,null,7,null,3,3,5,null,3,null,null,null,null,null,3,5,null,7,7,1,3,6,null,null,null,null,8,4,null,null,null,null,null,null,null,3,null,null,4,null,8,null,null,null,null,2,3,null,null,null,null,null,2,null,3,8,null,3,null,null,null,2,9]

可是上面倒数第五个数3,怎么看都是值为3的叶子节点啊

第 172 场周赛 - 答案和思路解释
https://leetcode-cn.com/circle/article/6Su4LC/

第3题,为什么不能把删除的结点 delete 掉?只赋值 NULL 不会内存泄露吗?