On the shoulders of giants.

weekly-contest-170

解码字母到整数映射

给你一个字符串 s,它由数字('0''9')和 '#' 组成。我们希望按下述规则将 s 映射为一些小写英文字符:

  • 字符('a''i')分别用('1' – '9')表示。
  • 字符('j''z')分别用('10#' – '26#')表示。 

返回映射之后形成的新字符串。

题目数据保证映射始终唯一。

示例 1:

输入:s = "10#11#12"
输出:"jkab"
解释:"j" -> "10#" , "k" -> "11#" , "a" -> "1" , "b" -> "2".

示例 2:

输入:s = "1326#"
输出:"acz"

示例 3:

输入:s = "25#"
输出:"y"

示例 4:

输入:s = "12345678910#11#12#13#14#15#16#17#18#19#20#21#22#23#24#25#26#"
输出:"abcdefghijklmnopqrstuvwxyz"

提示:

  • 1 <= s.length <= 1000
  • s[i] 只包含数字('0''9')和 '#' 字符。
  • s 是映射始终存在的有效字符串。
题解

直接遍历处理即可。

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

class Solution {
public:
    string freqAlphabets(string s) {
        int n = s.length();
        string result = "";

        for(int i = n - 1; 0 <= i; i--) {
            if(s[i] != '#') result += (s[i] - '1' + 'a');
            else {
                int num = s[i - 2] - '0';
                num = num * 10 + s[i - 1] - '0';
                result += num - 1 + 'a';
                i -= 2;
            }
        }
        reverse(result.begin(), result.end());

        return result;
    }
};

子数组异或查询

有一个正整数数组 arr,现给你一个对应的查询数组 queries,其中 queries[i] = [Li, Ri]

对于每个查询 i,请你计算从 Li 到 Ri 的 XOR 值(即 arr[Li] xor arr[Li+1] xor ... xor arr[Ri])作为本次查询的结果。

并返回一个包含给定查询 queries 所有结果的数组。

示例 1:

输入:arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
输出:[2,7,14,8] 
解释:
数组中元素的二进制表示形式是:
1 = 0001 
3 = 0011 
4 = 0100 
8 = 1000 
查询的 XOR 值为:
[0,1] = 1 xor 3 = 2 
[1,2] = 3 xor 4 = 7 
[0,3] = 1 xor 3 xor 4 xor 8 = 14 
[3,3] = 8

示例 2:

输入:arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
输出:[8,0,4,4]

提示:

  • 1 <= arr.length <= 3 * 10^4
  • 1 <= arr[i] <= 10^9
  • 1 <= queries.length <= 3 * 10^4
  • queries[i].length == 2
  • 0 <= queries[i][0] <= queries[i][1] < arr.length
题解

前缀和:设 \(sum_x\) 为 arr[1~x] 异或的结果,所以有:

\(arr_{x,y}=sum_y \bigoplus sum_{x-1}\)

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

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        int n = arr.size();
        vector<int> orSum(n, 0);
        for(int i = 0; i < n; i++) {
            if(!i) orSum[i] = arr[i];
            else orSum[i] = orSum[i - 1] ^ arr[i];
        }
        int m = queries.size();
        vector<int> result(m);
        for(int i = 0; i < m; i++) {
            int a = (queries[i][0] ? orSum[queries[i][0] - 1] : 0);
            int b = orSum[queries[i][1]];
            result[i] = b ^ a;
        }
        return result;
    }
};
获取你好友已观看的视频

有 n 个人,每个人都有一个  0 到 n-1 的唯一 id 。

给你数组 watchedVideos  和 friends ,其中 watchedVideos[i]  和 friends[i] 分别表示 id = i 的人观看过的视频列表和他的好友列表。

Level 1 的视频包含所有你好友观看过的视频,level 2 的视频包含所有你好友的好友观看过的视频,以此类推。一般的,Level 为 k 的视频包含所有从你出发,最短距离为 k 的好友观看过的视频。

给定你的 id  和一个 level 值,请你找出所有指定 level 的视频,并将它们按观看频率升序返回。如果有频率相同的视频,请将它们按名字字典序从小到大排列。

示例 1:

输入:watchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 1
输出:["B","C"] 
解释:
你的 id 为 0 ,你的朋友包括:
id 为 1 -> watchedVideos = ["C"] 
id 为 2 -> watchedVideos = ["B","C"] 
你朋友观看过视频的频率为:
B -> 1 
C -> 2

示例 2:

输入:watchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 2
输出:["D"]
解释:
你的 id 为 0 ,你朋友的朋友只有一个人,他的 id 为 3 。

提示:

  • n == watchedVideos.length == friends.length
  • 2 <= n <= 100
  • 1 <= watchedVideos[i].length <= 100
  • 1 <= watchedVideos[i][j].length <= 8
  • 0 <= friends[i].length < n
  • 0 <= friends[i][j] < n
  • 0 <= id < n
  • 1 <= level < n
  • 如果 friends[i] 包含 j ,那么 friends[j] 包含 i
题解

首先 BFS 求深度,然后在 level 深度出现的节点,进程维护更新。

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

class Solution {
public:
    map<string, int> total; 
    vector<pair<int, string>> tmp;
    vector<string> result;
    vector<int> dep;
    vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {
        int n = friends.size();
        queue<int> q;
        dep.resize(n);
        q.push(id);
        dep[id] = 1;
        while(!q.empty()) {
            int x = q.front(); q.pop();
            for(auto y : friends[x]) {
                if(dep[y]) continue;
                dep[y] = dep[x] + 1;
                q.push(y);
            }
        }
        for(int i = 0; i < n; i++) {
            if(dep[i] - 1 != level) continue;
            for(auto name : watchedVideos[i]) {
                total[name] += 1;
            }
        }
        for(auto art : total) {
            tmp.push_back(make_pair(art.second, art.first));
        }
        sort(tmp.begin(), tmp.end());
        for(auto x : tmp) result.push_back(x.second);
        return result;
    }
};

让字符串成为回文串的最少插入次数

给你一个字符串 s ,每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

「回文串」是正读和反读都相同的字符串。

示例 1:

输入:s = "zzazz"
输出:0
解释:字符串 "zzazz" 已经是回文串了,所以不需要做任何插入操作。

示例 2:

输入:s = "mbadm"
输出:2
解释:字符串可变为 "mbdadbm" 或者 "mdbabdm" 。

示例 3:

输入:s = "leetcode"
输出:5
解释:插入 5 个字符后字符串变为 "leetcodocteel" 。

示例 4:

输入:s = "g"
输出:0

示例 5:

输入:s = "no"
输出:1

提示:

  • 1 <= s.length <= 500
  • s 中所有字符都是小写字母。
题解

动态规划:设 \(dp_{x,y}\) 为区间 \([x,y]\) 的子串变为回文串的最小代价。

状态转移:

\(dp_{x,y}=\min (dp_{x+1,y}+1,dp_{x,y-1}+1)\) ,当 \(s_x \not= s_y\) 时;

\(dp_{x,y}=\min (dp_{x+1,y}+1,dp_{x,y-1}+1,dp_{x+1,y-1})\) ,当 \(s_x = s_y\) 时。

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

class Solution {
public:
    int minInsertions(string s) {
        int n = s.length();
        vector<vector<int>> dp(n, vector<int> (n));
        for(int l = 2; l <= n; l++) {
            for(int i = 0; i + l - 1 < n; i++) {
                int j = i + l - 1;
                dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j - 1] + 1);
                if(s[i] == s[j]) {
                    dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
                } 
            }
        }
        return dp[0][n - 1];
    }
};
Share

You may also like...

发表评论

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