On the shoulders of giants.

weekly-contest-172

6 和 9 组成的最大数字

给你一个仅由数字 6 和 9 组成的正整数 num

你最多只能翻转一位数字,将 6 变成 9,或者把 9 变成 6 。

请返回你可以得到的最大数字。

示例 1:

输入:num = 9669
输出:9969
解释:
改变第一位数字可以得到 6669 。
改变第二位数字可以得到 9969 。
改变第三位数字可以得到 9699 。
改变第四位数字可以得到 9666 。
其中最大的数字是 9969 。

示例 2:

输入:num = 9996
输出:9999
解释:将最后一位从 6 变到 9,其结果 9999 是最大的数。

示例 3:

输入:num = 9999
输出:9999
解释:无需改变就已经是最大的数字了。

提示:

  • 1 <= num <= 10^4
  • num 每一位上的数字都是 6 或者 9 。
题解

直接把最高位的 6 换成 9

时间复杂度:\(O(\log n)\)

class Solution {
public:
    int maximum69Number (int num) {
        int a[10], l = 0, result = 0;
        while(num) {
            a[l++] = num % 10;
            num /= 10;
        }
        for(int i = l - 1, flag = 0; 0 <= i; i--) {
            if(!flag && a[i] == 6) a[i] = 9, flag = 1;
            result = result * 10 + a[i];
        }
        return result;
    }
};

竖直打印单词

给你一个字符串 s。请你按照单词在 s 中的出现顺序将它们全部竖直返回。
单词应该以字符串列表的形式返回,必要时用空格补位,但输出尾部的空格需要删除(不允许尾随空格)。
每个单词只能放在一列上,每一列中也只能有一个单词。

示例 1:

输入:s = "HOW ARE YOU"
输出:["HAY","ORO","WEU"]
解释:每个单词都应该竖直打印。 
 "HAY"
 "ORO"
 "WEU"

示例 2:

输入:s = "TO BE OR NOT TO BE"
输出:["TBONTB","OEROOE","   T"]
解释:题目允许使用空格补位,但不允许输出末尾出现空格。
"TBONTB"
"OEROOE"
"   T"

示例 3:

输入:s = "CONTEST IS COMING"
输出:["CIC","OSO","N M","T I","E N","S G","T"]

提示:

  • 1 <= s.length <= 200
  • s 仅含大写英文字母。
  • 题目数据保证两个单词之间只有一个空格。
题解

模拟题,模拟竖性排列,然后保存结果,最后清除末尾空格。

时间复杂度:\(O(nm)\) ,n 为单词个数,m 为平均单词长度。

class Solution {
public:
    vector<string> printVertically(string s) {
        vector<string> words;
        int l, lim = -1;
        s += " ";
        for(int i = 0; i < s.length(); i++) {
            int j = i;
            while(i < s.length() && s[i] != ' ') i++;
            string word = s.substr(j, i - j);
            words.push_back(word);
            lim = max(lim, (int)word.length());
        }
        for(int i = 0; i < words.size(); i++) {
            while(words[i].length() != lim) words[i] += " ";
        }
        vector<string> result(lim);
        for(int i = 0; i < words.size(); i++) {
            for(l = 0; l < lim; l++) {
                result[l] += words[i][l];
            }
        }
        for(auto& word : result) {
            while(word.length() && word[word.length() - 1] == ' ') 
                word.pop_back();
        }
        return result;
    }
};

删除给定值的叶子节点

给你一棵以 root 为根的二叉树和一个整数 target ,请你删除所有值为 target 的 叶子节点

注意,一旦删除值为 target 的叶子节点,它的父节点就可能变成叶子节点;如果新叶子节点的值恰好也是 target ,那么这个节点也应该被删除。

也就是说,你需要重复此过程直到不能继续删除。

示例 1:

输入:root = [1,2,3,2,null,2,4], target = 2
输出:[1,null,3,null,4]
解释:
上面左边的图中,绿色节点为叶子节点,且它们的值与 target 相同(同为 2 ),它们会被删除,得到中间的图。
有一个新的节点变成了叶子节点且它的值与 target 相同,所以将再次进行删除,从而得到最右边的图。

示例 2:

输入:root = [1,3,3,3,2], target = 3
输出:[1,3,null,null,2]

示例 3:

输入:root = [1,2,null,2,null,2], target = 2
输出:[1]
解释:每一步都删除一个绿色的叶子节点(值为 2)。

示例 4:

输入:root = [1,1,1], target = 1
输出:[]

示例 5:

输入:root = [1,2,3], target = 1
输出:[1,2,3]

提示:

  • 1 <= target <= 1000
  • 每一棵树最多有 3000 个节点。
  • 每一个节点值的范围是 [1, 1000] 。
题解

遍历二叉树。可以增加一个根节点的父亲节点,从而减少代码复杂度。

时间复杂度:\(O(n)\)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void dfs(TreeNode* father, int x, TreeNode* root, int& target) {
        if(root == NULL) return;
        dfs(root, 0, root->left, target);
        dfs(root, 1, root->right, target);
        if(root->left == NULL && root->right == NULL) {
            if(root->val == target) {
                if(x == 0) {
                    father->left = NULL;
                } else {
                    father->right = NULL;
                }
            }
        }
    }
    TreeNode* removeLeafNodes(TreeNode* root, int target) {
        TreeNode* father = new TreeNode(-1);
        father->left = root;
        dfs(father, 0, root, target);
        return father->left;
    }
};

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

在 x 轴上有一个一维的花园。花园长度为 n,从点 0 开始,到点 n 结束。

花园里总共有 n + 1 个水龙头,分别位于 [0, 1, ..., n]

给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges ,其中 ranges[i] (下标从 0 开始)表示:如果打开点 i 处的水龙头,可以灌溉的区域为 [i -  ranges[i], i + ranges[i]] 。

请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方,请你返回 -1 。

示例 1:

输入:n = 5, ranges = [3,4,1,1,0,0]
输出:1
解释:
点 0 处的水龙头可以灌溉区间 [-3,3]
点 1 处的水龙头可以灌溉区间 [-3,5]
点 2 处的水龙头可以灌溉区间 [1,3]
点 3 处的水龙头可以灌溉区间 [2,4]
点 4 处的水龙头可以灌溉区间 [4,4]
点 5 处的水龙头可以灌溉区间 [5,5]
只需要打开点 1 处的水龙头即可灌溉整个花园 [0,5] 。

示例 2:

输入:n = 3, ranges = [0,0,0,0]
输出:-1
解释:即使打开所有水龙头,你也无法灌溉整个花园。

示例 3:

输入:n = 7, ranges = [1,2,1,0,2,1,0,1]
输出:3

示例 4:

输入:n = 8, ranges = [4,0,0,0,0,0,0,0,4]
输出:2

示例 5:

输入:n = 8, ranges = [4,0,0,0,4,0,0,0,4]
输出:1

提示:

  • 1 <= n <= 10^4
  • ranges.length == n + 1
  • 0 <= ranges[i] <= 100
题解

贪心,经典区间贪心问题。

求区间最小覆盖,区间左端点排序,选右端点尽量大的,一直贪心下去即可。

时间复杂度:\(O(n \log n)\)

class Solution {
public:
    int minTaps(int n, vector<int>& ranges) {
        vector<pair<int, int>> pos(n + 1);
        for(int i = 0; i <= n; i++) {
            pos[i] = make_pair(i - ranges[i], i + ranges[i]);
        }
        sort(pos.begin(), pos.end());
        int count = 0, p = 0;
        for(int i = 0; i <= n; i++) {
            int lim = p;
            if(p < pos[i].first) return -1;
            while(i <= n && pos[i].first <= p) {
                lim = max(lim, pos[i++].second);
            }
            p = lim;
            count++, i--;
            if(n <= p) break;
        }
        return (p < n ? -1 : count);
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注