周赛 – 175

1. 检查整数及其两倍数是否存在

给你一个整数数组 arr,请你检查是否存在两个整数 N 和 M,满足 N 是 M 的两倍(即,N = 2 * M)。
更正式地,检查是否存在两个下标 i 和 j 满足:

  • i != j
  • 0 <= i, j < arr.length
  • arr[i] == 2 * arr[j]

样例

示例 1:

输入:arr = [10,2,5,3]
输出:true
解释:N = 10 是 M = 5 的两倍,即 10 = 2 * 5 。

示例 2:

输入:arr = [7,1,14,11]
输出:true
解释:N = 14 是 M = 7 的两倍,即 14 = 2 * 7 。

示例 3:

输入:arr = [3,1,7,11]
输出:false
解释:在该情况下不存在 N 和 M 满足 N = 2 * M 。

提示

  • 2 <= arr.length <= 500
  • -10^3 <= arr[i] <= 10^3

代码

viv丑陋版

我是猪这题居然还WA了一发因为我没有考虑自己是自己的两倍比如说0的情况……
$O(n^2)$遍历两遍数组,看存不存在两倍关系。

class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        int n = arr.size();
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(i == j) continue;
                if(arr[i] == arr[j] * 2 || arr[j] == arr[i] * 2) return true;
            }
        }
        return false;
    }
};

zz美丽版

看完zz美丽版发现我居然还多判断了一遍……早起毁一天……
if语句只需要判断arr[i]是否等于arr[j]*2就可以了,都会遍历到的,写两个是重复。

class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        int n = arr.size();
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(i == j) continue;
                if(arr[i] == arr[j] * 2) return true;
            }
        }
        return false;
    }
};

2. 制造字母异位词的最小步骤数

给你两个长度相等的字符串 s 和 t。每一个步骤中,你可以选择将 t 中的 任一字符 替换为 另一个字符
返回使 t 成为 s 的字母异位词的最小步骤数。
字母异位词 指字母相同,但排列不同的字符串。

样例

示例 1:

输出:s = “bab”, t = “aba”
输出:1
提示:用 ‘b’ 替换 t 中的第一个 ‘a’,t = “bba” 是 s 的一个字母异位词。

示例 2:

输出:s = “leetcode”, t = “practice”
输出:5
提示:用合适的字符替换 t 中的 ‘p’, ‘r’, ‘a’, ‘i’ 和 ‘c’,使 t 变成 s 的字母异位词。

示例 3:

输出:s = “anagram”, t = “mangaar”
输出:0
提示:”anagram” 和 “mangaar” 本身就是一组字母异位词。

示例 4:

输出:s = “xxyyzz”, t = “xxyyzz”
输出:0

示例 5:

输出:s = “friend”, t = “family”
输出:4

提示

  • 1 <= s.length <= 50000
  • s.length == t.length
  • s 和 t 只包含小写英文字母

代码

viv丑陋版

直觉告诉我是计算两个字符串对应的26个小写字母计数数组之间的曼哈顿距离的一半。
然后就过了……

class Solution {
public:
    int minSteps(string s, string t) {
        int cnt1[26]; memset(cnt1, 0, sizeof(cnt1));
        int cnt2[26]; memset(cnt2, 0, sizeof(cnt2));
        int n = s.size();
        for(int i=0; i<n; i++) {
            cnt1[s[i]-'a']++;
            cnt2[t[i]-'a']++;
        }
        int ans = 0;
        for(int i=0; i<26; i++) {
            ans += abs(cnt1[i] - cnt2[i]);
        }
        return ans / 2;
    }
};

zz美丽版

思路一致。但是。
啊啊啊!zz连写这题都能比我少开一个数组。还有我什么时候才能记住auto的用法TAT。

class Solution {
public:
    int minSteps(string s, string t) {
        int cnt[26] = {0};
        for(auto c: s) cnt[c - 'a']++;
        for(auto c: t) cnt[c - 'a']--;

        int ans = 0;
        for(int i=0; i<26; i++) {
            if(cnt[i] < 0) ans -= cnt[i];
            else ans += cnt[i];
        }
        return ans / 2;
    }
};

3. 推文计数

请你实现一个能够支持以下两种方法的推文计数类 TweetCounts:

  1. recordTweet(string tweetName, int time)

    • 记录推文发布情况:用户 tweetName 在 time(以  为单位)时刻发布了一条推文。
  2. getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime)

    • 返回从开始时间 startTime(以 为单位)到结束时间 endTime(以 为单位)内,每 分 minute时 hour 或者 日 day (取决于 freq)内指定用户 tweetName 发布的推文总数。
    • freq 的值始终为 分 minute时 hour 或者 日 day 之一,表示获取指定用户 tweetName 发布推文次数的时间间隔。
    • 第一个时间间隔始终从 startTime 开始,因此时间间隔为 [startTime, startTime + delta*1>,  [startTime + delta*1, startTime + delta*2>, [startTime + delta*2, startTime + delta*3>, … , [startTime + delta*i, min(startTime + delta*(i+1), endTime + 1)>,其中 i 和 delta(取决于 freq)都是非负整数。

样例

示例 1:

输入:
[“TweetCounts”,”recordTweet”,”recordTweet”,”recordTweet”,”getTweetCountsPerFrequency”,”getTweetCountsPerFrequency”,”recordTweet”,”getTweetCountsPerFrequency”]
[[],[“tweet3”,0],[“tweet3”,60],[“tweet3”,10],[“minute”,”tweet3″,0,59],[“minute”,”tweet3″,0,60],[“tweet3”,120],[“hour”,”tweet3″,0,210]]
输出:
[null,null,null,null,[2],[2,1],null,[4]]
解释:
TweetCounts tweetCounts = new TweetCounts();
tweetCounts.recordTweet(“tweet3”, 0);
tweetCounts.recordTweet(“tweet3”, 60);
tweetCounts.recordTweet(“tweet3”, 10); // “tweet3” 发布推文的时间分别是 0, 10 和 60 。
tweetCounts.getTweetCountsPerFrequency(“minute”, “tweet3”, 0, 59); // 返回 [2]。统计频率是每分钟(60 秒),因此只有一个有效时间间隔 [0,60> – > 2 条推文。
tweetCounts.getTweetCountsPerFrequency(“minute”, “tweet3”, 0, 60); // 返回 [2,1]。统计频率是每分钟(60 秒),因此有两个有效时间间隔 1) [0,60> – > 2 条推文,和 2) [60,61> – > 1 条推文。
tweetCounts.recordTweet(“tweet3”, 120); // “tweet3” 发布推文的时间分别是 0, 10, 60 和 120 。
tweetCounts.getTweetCountsPerFrequency(“hour”, “tweet3”, 0, 210); // 返回 [4]。统计频率是每小时(3600 秒),因此只有一个有效时间间隔 [0,211> – > 4 条推文。

代码

viv丑陋版

第一次在Leetcode做这种题……仿佛回到了C++上机课……
定义了一个map<string, vector<int>>类型的变量,存放用户名对应的发送推特时间(以秒为单位)。
第一种操作是更新。就用昨晚双周赛学到的方法,将tweetName对应的vector中放入time。
第二种操作是查询。因为查询的结果是指定时间段内每个单位时间发送推特数组成的vector,所以我们首先在vector内占$(endTime-startTime)/div+1$个位置并初始化。然后遍历了该用户发送的所有推特的时间,在$[startTime, endTime]$之内的,就让vector在位置$(x-startTime)/div$的记录值+1。

class TweetCounts {
private:
    map<string, vector<int>> mp;
public:
    TweetCounts() {
        
    }
    
    void recordTweet(string tweetName, int time) {
        mp[tweetName].push_back(time);
    }
    
    vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {
        vector<int> ans;
        int div = 0;
        if(freq == "minute") div = 60;
        else if(freq == "hour") div = 60 * 60;
        else div = 24 * 60 * 60;

        for(int i=0; i<=(endTime - startTime) / div; i++) ans.push_back(0);

        int n = mp[tweetName].size();
        for(int i=0; i<n; i++) {
            int x = mp[tweetName][i];
            if(x > endTime || x < startTime) continue;
            ans[(x - startTime) / div]++;
        }
        return ans;
    }
};

/**
 * Your TweetCounts object will be instantiated and called as such:
 * TweetCounts* obj = new TweetCounts();
 * obj->recordTweet(tweetName,time);
 * vector<int> param_2 = obj->getTweetCountsPerFrequency(freq,tweetName,startTime,endTime);
 */

zz美丽版

我在比赛的时候就想过用set,但是我考虑到重复的问题放弃了,没想到还有multiset这种东西,我是STL废。
但是写完一遍感觉迭代器好难啊……哭唧唧,是我太菜了吗。不过用set代替vector会快很多是毋容置疑的。
两个迭代器,第一个it用lower_bound初始化为在查询区间$[startTime, endTime]$中的第一条推文,第二个end用来标记迭代器的末尾。

class TweetCounts {
public:
    map<string, multiset<int>> storage;
    TweetCounts() {
        storage.clear();
    }
    
    void recordTweet(string tweetName, int time) {
        storage[tweetName].insert(time);
    }
    
    vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {
        vector<int> ret; ++endTime;

        int delta = 0;
        if(freq == "minute") delta = 60;
        if(freq == "hour") delta = 60 * 60;
        if(freq == "day") delta = 60 * 60 * 24;

        multiset<int>::iterator it = storage[tweetName].lower_bound(startTime);
        multiset<int>::iterator ed = storage[tweetName].end();
        for(int i=0; startTime + delta * i < endTime; i++) {
            int s = startTime + delta * i, e = min(startTime + delta * i + delta, endTime);
            if(it == ed || (*it) >= e) ret.push_back(0);
            else {
                int cur = 0;
                while(it != ed && (*it) < e) {
                    ++cur;
                    ++it;
                }
                ret.push_back(cur);
            }
        }
        return ret;
    }
};

/**
 * Your TweetCounts object will be instantiated and called as such:
 * TweetCounts* obj = new TweetCounts();
 * obj->recordTweet(tweetName,time);
 * vector<int> param_2 = obj->getTweetCountsPerFrequency(freq,tweetName,startTime,endTime);
 */

4. 参加考试的最大学生数

给你一个 m * n 的矩阵 seats 表示教室中的座位分布。如果座位是坏的(不可用),就用 ‘#’ 表示;否则,用 ‘.’ 表示。
学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷,但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的一起参加考试且无法作弊的最大学生人数。
学生必须坐在状况良好的座位上。

样例

示例 1:

输入:seats =
[[“#”,”.”,”#”,”#”,”.”,”#”],
[“.”,”#”,”#”,”#”,”#”,”.”],
[“#”,”.”,”#”,”#”,”.”,”#”]]
输出:4
解释:教师可以让 4 个学生坐在可用的座位上,这样他们就无法在考试中作弊。

示例 2:

输入:seats =
[[“.”,”#”],
[“#”,”#”],
[“#”,”.”],
[“#”,”#”],
[“.”,”#”]]
输出:3
解释:让所有学生坐在可用的座位上。

示例 3:

输入:seats =
[[“#”,”.”,”.”,”.”,”#”],
[“.”,”#”,”.”,”#”,”.”],
[“.”,”.”,”#”,”.”,”.”],
[“.”,”#”,”.”,”#”,”.”],
[“#”,”.”,”.”,”.”,”#”]]
输出:10
解释:让学生坐在第 1、3 和 5 列的可用座位上。

提示

  • seats 只包含字符 ‘.’ 和’#’
  • m == seats.length
  • n == seats[i].length
  • 1 <= m <= 8
  • 1 <= n <= 8

代码

viv丑陋版

比赛的时候第一反应,八皇后问题。
然鹅……感觉这比它复杂的多,需要DP和组合数学的知识呀,搞不明白。

zz美丽版

原来是我的知识盲区状压DP
$dp[i][bits]$表示前$i$行中,第$i$行座位情况为$bits$的最大答案,其中$bits$为01串,1表示有人坐。
简单了解了一下,感觉状压DP主要就是状态表示和位运算,其实思想还是很暴力很朴素的。
$lowbit(x)$是$x$的二进制表达式中最低位的1所对应的值,状压DP和树状数组感觉都有用到。
利用lowbit即可写出bcount,用于计算一个数对应的二进制表示中1的位数。
DP过程非常暴力,从外到内依次枚举行数、当前行的状态和前一行的状态,判断当前状态的合法性来决定是否转移。
状态转移方程$dp[i][cur] = max(dp[i][cur], dp[i-1][pre] + bcount(cur))$。
最后通过枚举第$n$行的状态,即$dp[n][i]$来求得最终答案。

class Solution {
public:
    int lowbit(int x) {
        return x & -x;
    }
    int bcount(int x) {
        int ret = 0;
        while(x) {
            ret++;
            x -= lowbit(x);
        }
        return ret;
    }
    int maxStudents(vector<vector<char>>& seats) {
        int n = seats.size(), m = seats[0].size();
        int dp[10][1<<m]; memset(dp, -1, sizeof(dp));
        dp[0][0] = 0;

        int lim = (1 << m);
        for(int i=1; i<=n; i++) {
            for(int cur=0; cur<lim; cur++) {
                for(int pre=0; pre<lim; pre++) {
                    if(dp[i-1][pre] == -1) continue;
                    bool flag = true;
                    for(int j=0; j<m; j++) {
                        if(((cur >> j) & 1) == 0) continue;
                        if(seats[i-1][j] == '#') flag = false;
                        if(j-1>=0 && ((cur>>(j-1))&1)) flag = false;
                        if(j+1<m && ((cur>>(j+1)&1))) flag = false;
                        if(j-1>=0 && ((pre>>(j-1))&1)) flag = false;
                        if(j+1<m && ((pre>>(j+1)&1))) flag = false;
                    }
                    if(!flag) continue;
                    dp[i][cur] = max(dp[i][cur], dp[i-1][pre] + bcount(cur));
                }
            }
        }
        int ans = 0;
        for(int s=0; s<lim; s++) ans = max(ans, dp[n][s]);
        return ans;
    }
};
暂无评论

发送评论 编辑评论


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