且听疯吟

kickstart 2021 round H

2022-11-20

kickstart 2021 round H

kickstart的题目一向质量高,并且难度非常大，感觉基本上是校招面试题中难度最大的题目了，感觉力扣的难度弱爆了. 前三题感觉基本上只需要基本的数学技巧和数据结构的基本知识就可以做出来，最后一题真心是达到ACM的入门难度，还是挺难的题目。第四题花了好长时间才能弄懂题解.

Transform the String

Problem

You are given a string S which denotes a padlock consisting of lower case English letters. You are also given a string F consisting of set of favorite lower case English letters. You are allowed to perform several operations on the padlock. In each operation, you can change one letter of the string to the one following it or preceding it in the alphabetical order. For example: for the letter c, you are allowed to change it to either b or d in an operation. The letters can be considered in a cyclic order, i.e., the preceding letter for letter a would be letter z. Similarly, the following letter for letter z would be letter a.

Your aim is to find the minimum number of operations that are required such that each letter in string S after applying the operations, is present in string F.

Input

The first line of the input gives the number of test cases, T. T test cases follow.

Each test case consists of two lines.
The first line of each test case contains the string S.
The second line of each test case contains the string F.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum number of operations that are required such that each letter in string S after applying the operations, is one of the characters in string F.

地址

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000435914/00000000008da461#problem

题意

遍历

思路

  1. 第一题就是灌水题，非常简单.　要求找到将字符串中的字符全部变为给定的字符集中字符，求最小的变换次数，字符 a 转换到字符 b 有两种转换方法, 要么递增,要么递减翻转. $minstep = \min(|a-b|,26 - |a-b|)$,我们首先统计字符串 $s$ 中每种字符的个数, 然后对 $s$ 中的每种字符在字符集中找到最小的变换步数的目标字符 $c$ 即可.
  2. 复杂度分析:
  • 时间复杂度: $O(CN)$,其中 $M$ 为字符集中字符的个数。
  • 空间复杂度: $O(C)$,其中 $C = 26$。

代码

#include<iostream>
#include<vector>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<string>
#include<stack>
#include<algorithm>
#include<limits.h>

using namespace std;

void slove(int t){
    string src;
    string target;  
    long long ans = 0;
    cin>>src;
    cin>>target;  
    vector<int> cnt(26);
    for(auto c : src) cnt[c - 'a']++;
    for(int i = 0; i < 26; ++i) {
        if(cnt[i] == 0) continue;
        int curr = INT_MAX;
        for(auto c : target) {
            curr = min(curr, abs('a' + i - c));
            curr = min(curr, 26 - abs('a' + i - c));
        }
        ans += (long long)curr * cnt[i];
    }
    
    std::cout<<"Case #"<<t<<": ";
    cout<<ans<<endl;
}

int main(){
    int t;
    cin>>t;
    for(int i = 0; i < t; ++i){
        slove(i+1);
    }
    return 0;
}

Painter

题目

地址

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000435914/00000000008d9a88

题意

贪心算法或者dfs

思路

  1. 这个题目非常有趣,感觉跟某个力扣的某个题非常像,题意是说每种颜色可能有红黄蓝三种基本颜色组合, 每次涂画时可以选择一个区间　$[L,R]$ 涂上一种基本色, 给定的区间颜色分布,找到最少的涂画次数.
  2. 贪心算法, 我们设 $dp[i]$ 表示涂画前 $i$ 个颜色时所需要的涂画的最小步数, 我们在画 第 $i+1$ 个颜色时我们应该如何选择呢:
  • 按照贪心算法进行选择颜色, 假设第 $i$ 个颜色的基色包括 $i+1$ 个颜色使用的所有基色, 那么我们可以知道在画第 $i$ 个颜色时的基色时 我们肯定可以将 $i+1$ 个颜色的基色也包含进去,因此 $dp[i+1] = dp[i]$, 我们举例如下:
    • 我们假设第 $i$ 个颜色为 $G$, 第 $i+1$ 个颜色为 $P$, 则此时我们假设 $i$ 中的三种基色最后涂画时的区间分布分别为 $[L_r,i],[L_g,i],[L_b,i]$, 我们可以知道按照贪心原则我们可以将以上 $red$, $blue$ 的区间向由扩展一个位置,则此时三种基色的区间分别为 $[L_r,i+1],[L_g,i],[L_b,i+1]$, 此时即可同时满足第 $i$ 个颜色与 第 $i+1$ 个颜色.
  • 假设第 $i$ 个颜色的基色不能包含第 $i+1$ 个颜色使用的所有基色时,则此时我们只需要找到第 $i+1$ 个颜色使用了与第 $i$ 个颜色有哪些不同的基色.此时递推公式为 $dp[i+1] = dp[i] + diff(i,i+1)$
    实际处理中我们对每种颜色进行二进制编码, 我们用 $mask[i]$ 表示第 $i$ 个颜色的二进制编码, $mask[i+1]$ 表示第 $i+1$ 个颜色的二进制编码,则此时我们可以知道递推公式为 $dp[i+1] = dp[i] + count((mask[i]|mask[i]) \oplus maks[i])$
  1. 复杂度分析:
  • 时间复杂度分析: 时间复杂度为 $O(N)$,其中 $N$ 为字符串的长度.
  • 空间复杂度分析: 空间复杂度为 $O(N)$,其中 $N$ 为字符串的长度.

代码

#include<iostream>
#include<vector>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<string>
#include<stack>
#include<algorithm>
#include<limits.h>

using namespace std;

/*
Red + Yellow = Orange 110
Red + Blue = Purple   101
Yellow + Blue = Green 011
Red + Yellow + Blue = Gray 111
U = Uncolored 000
R = Red       100
Y = Yellow    010
B = Blue      001
O = Orange    110
P = Purple    101
G = Green     011
A = Gray      111
*/
/*ROAOR 3
  12331 
*/

int count(int x) {
    int res = 0;
    while (x != 0) {
        x = x&(x-1);
        res++;
    }
    return res;
}

void slove(int t){
    long long ans = 0;
    int n;
    string s;
    cin>>n;
    cin>>s;
    vector<char> dict = {'U','R','Y','B','O','P','G','A'};
    vector<int> arr = {0, 4, 2, 1, 6, 5, 3, 7};
    unordered_map<char,int> cnt;
    vector<long long> dp(n, 0);
    for(int i = 0; i < arr.size(); ++i) {
        cnt[dict[i]] = arr[i];
    }

    dp[0] = count(cnt[s[0]]);
    for(int i = 1; i < n; ++i){
        int curr = cnt[s[i]];
        int prev = cnt[s[i - 1]];
        dp[i] = dp[i-1] + count(curr|prev) - count(prev);
    }

    std::cout<<"Case #"<<t<<": ";
    cout<<dp[n-1]<<endl;
}

int main(){
    int t;
    cin>>t;
    for(int i = 0; i < t; ++i){
        slove(i+1);
    }
    return 0;
}

Silly Substitutions

题目

You are given a string S of length N which consists of digits 0-9. You do the following operations on the string in the order given.

Find all the substrings 01 and replace each of them with 2.
Find all the substrings 12 and replace each of them with 3.
Find all the substrings 23 and replace each of them with 4.
Find all the substrings 34 and replace each of them with 5.
.
.
.

Find all the substrings 89 and replace each of them with 0.
Find all the substrings 90 and replace each of them with 1.
You repeat this process in the same given order until none of the above operations change the string. For example, if S is 12 then we do not stop at operation 1 since it does not affect the string but perform operation 2 and change the string to 3. We can see that the string does not change further no matter how many times we repeat the above process.

Your task is to find how the final string will look like for the given S.

地址

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000435914/00000000008d94f5

题意

双链表

思路

  1. 题目还是非常不错的，我们首先将字符串用双链表来表示出来．我们首先将双链表中所有可能合并的字符串的头节点全部存储在10个集合中,比如我们知道目前双链表如下:
    0->1->2->3>4
    此时我们知道可能合并的字符串分别为:
    0->1
    1->2
    2->3
    3->4
    我们会存储$0,1,2,3$ 所在的头节点.
  2. 我们依次遍历所有可能合并的组合 $01,12,23,34,45,56,…,90$等等.我们每次取出可以合并的数字组合时,每次合并时可能会产生新的组合,我们将新的可以合并的组合再加入到集合中,比如以下举例:
    ...a->0->1->b...
    我们将 $01$ 进行合并后生成 $a2b$, 此时我们首先对双链表进行节点的删除与插入,同时对新生成的数字组合判断是否可以构成待消除的组合,如果含有可以消除的组合,则我们将其插入到集合中.
  3. 复杂度分析:
  • 时间复杂度为 $O(CN)$,其中 $N$ 为字符串的长度, 我们每次 $10$ 次循环依次判断从 $01 \cdots 90$的消除组合，每次消除时都能消除一个字符，最多需要 $O(10N)$ 的时间复杂度．
  • 空间复杂度为 $O(N)$,其中 $N$ 为字符串的长度.

代码

#include<iostream>
#include<vector>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<string>
#include<stack>
#include<algorithm>
#include<list>
#include<limits.h>

using namespace std;

template <class T>
struct ListNode{
	T val;
    ListNode * prev;
    ListNode * next;
    ListNode(T val){
        this->val = val;
        this->prev = nullptr;
        this->next = nullptr;
    }
};

template <typename T>
inline ListNode<T> * insert(ListNode<T> * curr, T val) {
    ListNode<T> * node = new ListNode<T>(val);
    if(curr->next){
        node->next = curr->next;
        curr->next->prev = node;
    }
    if(curr) {
        curr->next = node;
        node->prev = curr;
    }    
    return node;
};

void slove(int t){
   string s;
   string ans;
   int n;
   cin>>n;
   cin>>s;
   vector<int> nxt(12);
   for(int i = 0; i <= 9; ++i) nxt[i] = (i+1)%10;
   nxt[10] = 10;
   nxt[11] = 11;

   /* link list*/
   vector<unordered_set<ListNode<int> *>> arr(10);
   ListNode<int> * head = new ListNode<int>(10);
   insert(head,11);
   ListNode<int> * tail = head;
   for(auto c : s) {
       tail = insert(tail, c - '0');
   }
   for(ListNode<int> * node = head; node != nullptr; node = node->next) {
       if(node->next && nxt[node->val] == node->next->val){
           arr[node->val].insert(node);
       }
   }
   
   /* we remove each key and merge*/ 
   while(1){
       bool rflag = false;
       for(int i = 0; i <= 9; ++i) {
           if(arr[i].empty()) continue;
           rflag = true;
           for(auto t : arr[i]){
               ListNode<int> * curr = new ListNode<int>((nxt[t->val] + 1)%10);
               ListNode<int> * prev = t->prev;
               ListNode<int> * next = t->next->next;

               /*remove key node*/
               if(nxt[prev->val] == t->val){
                   arr[prev->val].erase(prev);
               }
               if(nxt[t->next->val] == next->val){
                   arr[t->next->val].erase(t->next);
               }

               /*merge new key*/
               prev->next = curr;
               curr->prev = prev;
               curr->next = next;
               next->prev = curr;
               if(nxt[prev->val] == curr->val){
                   arr[prev->val].insert(prev);
               }
               if(nxt[curr->val] == next->val){
                   arr[curr->val].insert(curr);
               }
               delete t->next;
               delete t;
               
           }
           arr[i].clear();
       }
       if(!rflag) break;
   }
   
   for(ListNode<int> * node = head; node != nullptr; node = node->next) {
       if(node->val >= 0 && node->val <= 9) {
           ans.push_back(node->val + '0');
       }
   }
   std::cout<<"Case #"<<t<<": ";
   cout<<ans<<endl;
}

int main(){
    int t;
    cin>>t;
    for(int i = 0; i < t; ++i){
        slove(i+1);
    }
    return 0;
}

Dependent Events

题目

There are N events, numbered 1 through N. The probability of occurrence of each event depends upon the occurrence of exactly one other event called the parent event, except event 1, which is an independent event. In other words, for each event from 2 to N, 3 values are given: Pi denoting the parent event of event i, Ai denoting the probability of occurrence of event i if its parent event occurs, and Bi denoting the probability of occurrence of event i if its parent event does not occur. For event 1, its probability of occurrence K is given. There are Q queries that we want to answer. Each query consists of 2 distinct events, uj and vj, and you need to find the probability that both events uj and vj have occurred.

地址

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000435914/00000000008d9970

题意

数学问题

解题思路

题目太难了，不会．

代码


欢迎关注和打赏，感谢支持！

Tags: kickstart
← 【MIT6.S081】lab10 mmap leetcode contest 建信金科 →

扫描二维码，分享此文章