On the shoulders of giants.

weekly-contest-175

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

给你一个整数数组 arr,请你检查是否存在两个整数 NM,满足 N 是 M 的两倍(即,N = 2 * M)。

更正式地,检查是否存在两个下标 ij 满足:

  • 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
题解

直接枚举所有情况判断即可。

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

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

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

给你两个长度相等的字符串 st。每一个步骤中,你可以选择将 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
  • st 只包含小写英文字母
题解

在两字符串 s1、s2 相同时,字符串 s1 中从字符 a 改变到 字符 b ,那么

字符串 s1 对比字符串 s2 中字符 a 会减一,字符 b 会加一;

总的来说,字符串 s1 对比字符串 s2 减少的字符数和增加的字符数相同。

而其数值,就是让变化后的字符串变回原串的最小代价。

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

class Solution {
public:
    int minSteps(string s, string t) {
        int count[26][2] = {0, 0}, result = 0;
        for(int i = 0; i < s.length(); i++) {
            count[s[i] - 'a'][0]++;
            count[t[i] - 'a'][1]++;
        }
        for(int i = 0; i < 26; i++) {
            int sum = count[i][0] - count[i][1];
            if(sum > 0) result += sum; 
        }
        return result;
    }
};

推文计数

请你实现一个能够支持以下两种方法的推文计数类 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)>,其中 idelta(取决于 freq)都是非负整数。

示例:

输入: ["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 条推文。 

提示:

  • 同时考虑 recordTweet 和 getTweetCountsPerFrequency,最多有 10000 次操作。
  • 0 <= time, startTime, endTime <= 10^9
  • 0 <= endTime - startTime <= 10^4
题解

建立一颗平衡树,每个节点索引为 TweetName,其值为该用户的发布时间列表。

record:直接在树中索引下添加时间,时间复杂度:\(O(\log n)\)

getCount:枚举该用户下的所有时间,判断符合什么条件即可,时间复杂度:\(O(m)\)

class TweetCounts {
public:
    map<string, vector<int>> date;
    TweetCounts() {}
    
    void recordTweet(string tweetName, int time) {
        date[tweetName].push_back(time);
    }
    
    vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {
        int delta = (freq == "minute" ? 60 : (freq == "hour" ? 3600 : 24 * 3600));
        int n = (endTime - startTime) / delta + 1;
        vector<int> result(n, 0);
        for(auto time : date[tweetName]) {
            if(startTime <= time && time <= endTime) {
                result[(time - startTime) / delta]++;
            }
        }
        return result;
    }
};

/**
 * 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);
 */

参加考试的最大学生数

给你一个 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
题解

状态压缩动态规划:设 \(dp_{x,s}\) 为处理完 x 行后,x 行状态为 s 的最大方案数。

在合法的情况下,有状态转移方程:

\(dp_{i,now}=\max dp_{i-1,last}+count(now)\)

其中 \( 0 \leq now,last \leq 2^m-1\ \) ,\(count(num)\) 为 num 整数在二进制下有多少的 1

最后答案为:\(\max dp_{n,s}\)

时间复杂度:\(O(nm2^{2m})\)

class Solution {
public:
    bool check(int s) {
        for(int i = 0; i < 7; i++) {
            if(((s >> i) & 1) && ((s >> (i + 1)) & 1)) return true;
        }
        return false;
    }
    int maxStudents(vector<vector<char>>& seats) {
        int n = seats.size(), m = seats[0].size(), result = 0;
        vector<vector<int>> dp(n, vector<int> ((1 << m) - 1));
        vector<int> state(n);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                state[i] = (state[i] << 1) + (seats[i][j] == '#');
        for(int i = 0; i < n; i++) {
            for(int now = 0; now < (1 << m); now++) {
                if((now & state[i]) || check(now)) continue;
                if(i != 0) {
                    for(int last = 0; last < (1 << m); last++) {
                        if((last & state[i - 1]) || check(last)) continue;
                        bool flag = true;
                        for(int k = 0; k < 8 && flag; k++) {
                            if(((now >> k) & 1) == 0) continue;
                            if(k != 0 && ((last >> (k - 1)) & 1)) flag = false;
                            if(k != 7 && ((last >> (k + 1)) & 1)) flag = false; 
                        }
                        if(flag) dp[i][now] = max(dp[i][now], dp[i - 1][last]);
                    }
                }
                bitset<8> bit(now);
                dp[i][now] += bit.count();
                if(i == n - 1) result = max(result, dp[i][now]);
            }
        }
        return result;
    }
};
Share

You may also like...

发表评论

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