周赛 – 172

1. 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 是最大的数。
先删除回文子序列 “a”,然后再删除 “bb”。

示例 3:

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

提示

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

代码

viv丑陋版

这题是在zz家写的。
然后自己在家再写还不如那天,可能是关傻了。
就很简单,将最高位的6换成9就可以了。
从个位往其余位判断,是9则更改记录值ans。

class Solution {
public:
    int maximum69Number (int num) {
        int tmp = num;
        int ans = 0, base = 1;
        while(tmp) {
            int x = tmp % 10;
            tmp /= 10;
            if(x == 6) ans = base;
            base *= 10;
        }
        return num + ans * 3;
    }
};

zz美丽版

思路一样,只不过我没有好好看数据范围。我的方法更通用,哼。
不过zz写代码真的是好简洁qwq。

class Solution {
public:
    int maximum69Number (int num) {
        for(int i=1000, cur=num; i>=1; i/=10) {
            int now = cur / i; cur = cur % i;
            if(now == 6) {
                num = num + 3 * i;
                break;
            }
        }
        return num;
    }
};

2. 竖直打印单词

给你一个字符串 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 仅含大写英文字母。
  • 题目数据保证两个单词之间只有一个空格。

代码

viv丑陋版

在zz家的时候,因为up主一直在旁边叭叭我静不下心来,so直接没有继续做下去。
一道模拟题,今晚写了好久,我的代码能力果然还是很令人捉急。
首先,我考虑到最后返回的vector大小应为最长单词的长度,直接暴力求解就可以。然后我还非常愚蠢的错了,”HOW IS IT GOING”让我意识到不要忘记最后一个单词的判断。
然后我的想法是直接遍历字符串,同一个单词的每个字母依次加在指定的string后面,用now变量来决定是哪个string,一个单词结束即遇到空格now清零。
接下来要处理空格,首先就是最终返回的字符串前导空格不能省。思路是在遇到空格即一个单词结束时,将当前单词没有涉及到的答案string后都加一个空格。这里同样会漏掉最后一个单词,但是因为题目中要求去掉字符串结尾的空格,所以可以直接忽略最后一个单词的空格问题。
然后就是去掉结尾空格。我并不会,所以百度了一个STL用法。

s.erase(0, s.find_first_not_of(" ")); // 去掉s的前导空格
s.erase(s.find_last_not_of(" ") + 1); // 去掉s的末位空格

还有一个问题就是我不太会将vector转化成数组赋值,所以我直接用数组处理了,在最后将数组转化成了vector。

class Solution {
public:
    vector<string> printVertically(string s) {
        int len = s.size();
        int mx = 0, cur = 0;
        for(int i=0; i<len; i++) {
            if(s[i] == ' ') {
                mx = max(mx, cur);
                cur = 0;
            }
            else cur++;
        }
        mx = max(mx, cur);

        string ans[mx];
        for(int i=0, now=0; i<len; i++) {
            if(s[i] != ' ') {
                string str = ans[now];
                str += s[i];
                ans[now++] = str;
            }
            else {
                while(now<mx) {
                    string str = ans[now];
                    str += ' ';
                    ans[now++] = str;
                }
                now = 0;
            }
        }
        
        vector<string> ret;
        for(int i=0; i<mx; i++) {
            string str = ans[i];
            str.erase(str.find_last_not_of(" ") + 1);
            ret.push_back(str);
        }
        return ret;
    }
};

在看完zz美丽版之后,我发现这种写法是没有问题的。我把ans数组直接改成这个第一行也能过。

vector<string> ans(mx);
ans[i] = str;

我猜刚才是因为越界,所以才报错。

zz美丽版

首先把字符串变成单词的vector,这个操作确实有必要,不然每次都得遍历。而且zz很直接很巧妙地处理了最后一个单词的问题,我和我的代码还是太蠢了。
然后,求出最大单词长度。这个我也会(瘫。
又到了我菜的地方,zz是从后往前处理的。对于一个位置,如果这个位置为空格且后面有东西,才应输出空格。从后往前做,就可以提前知道某个位置后面有没有空格。好的,这就避免了STL盲区。

class Solution {
public:
    vector<string> printVertically(string s) {
        int m = s.size();
        vector<string> words;
        string cur = "";
        for(int i=0; i<=m; i++) {
            if(i == m || s[i] == ' ') {
                words.push_back(cur);
                cur = "";
            }
            else cur += s[i];
        }
        
        int mx = 0;
        for(auto w: words) mx = max(mx, (int)w.size());

        vector<string> ans;
        for(int i=0; i<mx; i++) ans.push_back("");

        int n = words.size();
        for(int i=n-1; i>=0; i--) {
            int l = words[i].size();
            for(int j=0; j<l; j++) ans[j] = words[i][j] + ans[j];
            for(int j=l; j<mx; j++) {
                if(ans[j].size() > 0) ans[j] = " " + ans[j];
            }
        }
        return ans;
    }
};

3. 删除给定值的叶子节点

给你一棵以 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] 。

代码

viv丑陋版

不知道是不是被气坏了,好吧大概还是因为我两个月没写代码,我连dfs都不会了。
写了好久,然后去看了zz代码。

zz丑陋版

递归向下不删除,开始回溯的时候删除。很Easy。

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

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

在 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

代码

viv丑陋版

看到题第一反应是线段覆盖问题,主要是这个我大一在计算思维课上讲过(PPT还是在zz学长眼皮子底下做的)。
然后写了半天都写不利索,被自己气死了。
将ranges数组里的信息转换成线段信息,然后将线段按照左端点从小到达排序。
很简单的贪心思想,记录当前可以覆盖到的最大距离mx,每次选取左端点小于等于mx且右端点尽量大的线段。

const int MAXN = 1e4 + 5;
struct Range {
    int left, right;
} range[MAXN];
bool cmp(const Range& r1, const Range& r2) {
    return r1.left < r2.left;
}

class Solution {
public:
    int minTaps(int n, vector<int>& ranges) {
        for(int i=0; i<=n; i++) {
            int len = ranges[i];
            range[i].left = max(0, i-len);
            range[i].right = min(n, i+len);
        } 
        sort(range, range+n+1, cmp);

        int mx = 0, ans = 0;
        for(int i=0; i<=n; i++) {
            if(range[i].left <= mx) {
                int tmp = range[i].right;
                while(i<=n && range[i].left <= mx) {
                    tmp = max(tmp, range[i].right);
                    i++;
                }
                i--;
                mx = max(mx, tmp);
                ans++;
                if(mx >= n) break;
            }
        }
        if(mx < n) return -1;
        return ans;
    }
};

zz美丽版

zz是用DP做的,嗯我好菜……
dp[i]用来表示前i个花园被灌溉所用的最少水龙头数。
转移时,假设当前水龙头可以覆盖到的区间为[left, right]。
那么dp[right]可以由区间内任意一点转移过来。

const int MAXN = 1e4 + 5;
int dp[MAXN];
class Solution {
public:
    int minTaps(int n, vector<int>& ranges) {
        memset(dp, -1, sizeof(dp));
        dp[0] = 0;
        for(int i=0; i<=n; i++) {
            int left = max(0, i-ranges[i]);
            int right = min(n, i+ranges[i]);
            for(int j=left; j<=right; j++) {
                if(dp[j] == -1) continue;
                if(dp[right]==-1 || dp[right]>dp[j]+1) dp[right] = dp[j] + 1;
            }
        }
        return dp[n];
    }
};
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇