Weekly Contest 170

Posted on | In , | |
Words count in article: 850 | Reading time ≈ 5

1309. Decrypt String from Alphabet to Integer Mapping

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string freqAlphabets(string s) {
        string ret = "";
        int n = s.size();
        for(int i=0; i<n; ){
            int curint = 0;
            if(i+2<n && s[i+2] == '#'){
                curint = (s[i]-'0')*10+s[i+1]-'0';
                i+=3;
            }else{
                curint = s[i]-'0';
                i++;
            }
            ret += 'a'+curint-1;
        }
        return ret;
    }
};

1310. XOR Queries of a Subarray

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        vector<int> rem(arr.size());
        for(int i=0;i<arr.size(); i++){
            if(i-1>=0) rem[i] = rem[i-1]^arr[i];
            else rem[i] = arr[i];
        }
        vector<int> ret(queries.size());
        for(int i=0; i<queries.size(); i++){
            if(queries[i][0] == queries[i][1]) ret[i] = arr[queries[i][0]];
            else if(queries[i][0] == 0) ret[i] = rem[queries[i][1]];
            else ret[i] = rem[queries[i][1]] ^ rem[queries[i][0]-1];
        }
        return ret;
    }
};

1311. Get Watched Videos by Your Friends

dfs莫名不过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    map<string, int> mp;
    vector<int> visited;
    void dfs(vector<vector<string>> &watchedVideos, vector<vector<int>> &friends, int id, int level){
        if(visited[id] == 1) return;
        if(level < 0) return;
        if(level == 0){
            for(int i=0; i<watchedVideos[id].size(); i++)
                mp[watchedVideos[id][i]]++;
        }
        visited[id] = 1;
        for(int i=0; i<friends[id].size(); i++){
            dfs(watchedVideos, friends, friends[id][i], level-1);
        }
    }
    vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {
        visited.resize(friends.size());
        visited[id] = 1;
        for(int i=0; i<friends[id].size(); i++){
            dfs(watchedVideos, friends, friends[id][i], level-1);
        }
        vector<pair<string, int>> ret1;
        for(auto it = mp.begin(); it != mp.end(); it++){
            ret1.push_back(*it);
        }
        sort(ret1.begin(), ret1.end(), cmp);
        vector<string> ret;
        for(auto it=ret1.begin(); it != ret1.end(); it++)
            ret.push_back(it->first);
        return ret;
    }
    static bool cmp(const pair<string, int>& a, const pair<string, int>& b)
	{
		if (a.second == b.second)
			return a.first < b.first;
		else
			return a.second < b.second;
	}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public:
	vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {
		unordered_map<string, int> videosMap;
		queue<pair<int, int>> bfsQueue;
		vector<bool> visited(watchedVideos.size(), false);
		bfsQueue.push(make_pair(id, 0));
		visited[id] = true;
		while (!bfsQueue.empty())
		{
			const pair<int, int>& frontPair = bfsQueue.front();
			int frontId = frontPair.first;
			int frontLevel = frontPair.second;
			if (frontLevel == level - 1)
			{
				for (size_t i = 0; i < friends[frontId].size(); ++i)
				{
					int friendId = friends[frontId][i];
					if (!visited[friendId])
					{
						visited[friendId] = true;
						for (size_t j = 0; j < watchedVideos[friendId].size(); ++j)
						{
							string video = watchedVideos[friendId][j];
							if (videosMap.find(video) == videosMap.end())
								videosMap[video] = 1;
							else
								++videosMap[video];
						}
					}
				}
			}
			else
			{
				for (size_t i = 0; i < friends[frontId].size(); ++i)
				{
					int friendId = friends[frontId][i];
					if (!visited[friendId])
					{
						bfsQueue.push(make_pair(friendId, frontLevel + 1));
						visited[friendId] = true;
					}
				}
			}
			bfsQueue.pop();
		}
		vector<pair<string, int>> videosVec;
		for (auto it = videosMap.begin(); it != videosMap.end(); ++it)
			videosVec.push_back(make_pair(it->first, it->second));
		sort(videosVec.begin(), videosVec.end(), cmp);
		vector<string> videos;
		for (auto it = videosVec.begin(); it != videosVec.end(); ++it)
			videos.push_back(it->first);
		return videos;
	}

	static bool cmp(const pair<string, int>& a, const pair<string, int>& b)
	{
		if (a.second == b.second)
			return a.first < b.first;
		else
			return a.second < b.second;
	}
};

1312. Minimum Insertion Steps to Make a String Palindrome

动态规划 用字符串长度减去最长回文子序列的长度就是最少插入次数了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minInsertions(string s) {
        int n=s.size();
        int dp[n][n];
        memset(dp,0,sizeof(dp));
        for(int i=n-1;i>=0;--i){
            dp[i][i]=1;
            for(int j=i+1;j<n;++j){
                if(s[i]==s[j]){
                    dp[i][j]=dp[i+1][j-1]+2;
                }
                else{
                    dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return n-dp[0][n-1];
    }
};

Donate? comment?