Contest 71 （）

 

Contest 72 （）

 

Contest 73 （2019年1月30日模拟）

链接：https://leetcode.com/contest/weekly-contest-73

结果：2/4，会做第一题和第三题，第二题和第四题不会做。

【788】Rotated Digits（第一题 4分）（谷歌tag）

给了一个 good number 的定义，X is a good number if after rotating each digit individually by 180 degrees, we get a valid number that is different from X. 

0， 1， 8旋转之后是本身，2，5旋转之后互为另一个数，6，9 同 2，5。

给定一个 N，问 1～N 里面有多少个 good number？（N < 10000）

题解：直接枚举。注意旋转是说 每个数字单独旋转，并不是把整个数旋转。

 1 class Solution {
 2 public:
 3     int rotatedDigits(int N) {
 4         unordered_map<int, int> mp;
 5         mp[0] = 0, mp[1] = 1, mp[8] = 8, mp[2]= 5, mp[5] = 2, mp[6] = 9, mp[9] = 6; 
 6         int ans = 0;
 7         for (int i = 1; i <= N; ++i) {
 8             string s = to_string(i);
 9             string rev = "";
10             bool valid = true;
11             for (auto c : s) {
12                 if (mp.find(c-'0') == mp.end()) {
13                     valid = false; 
14                     break;
15                 }
16                 rev += string(1, mp[c-'0'] + '0');
17             }
18             if (valid && s != rev && rev[0] != '0') {
19                 ans++;
20             }
21         }
22         return ans;
23     }
24 };

View Code

 

【789】Escape The Ghosts（第二题 5分）逃离鬼魂（谷歌tag，数学题）

假设你站在原点，有个去的目标 target 坐标，在二维平面上有一些鬼魂（鬼也有坐标）。每一步，你和鬼魂都能上下左右移动一格。问有没有可能在鬼怪抓到你之前，到达target。如果你和鬼怪同时到达target的话，那么鬼赢了。

题解：我比赛的时候想成了比较复杂的bfs，去模拟每个位置。幸好没有写。本题的本质是只要你和target 的曼哈顿距离小于任何一个鬼怪距离target的目标距离，你就有可能会赢。所以只要判断一下距离就行了。

 

 1 class Solution {
 2 public:
 3     bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
 4         const int dist = abs(target[0]) + abs(target[1]);
 5         for (auto& ele : ghosts) {
 6             int d = abs(target[0] - ele[0]) + abs(target[1] - ele[1]);
 7             if (d < dist) {
 8                 return false;
 9             }
10         }
11         return true;
12     }
13 };

View Code

 

 

【791】Custom Sort String（第三题 5分）

 给了两个字符串 S 和 T，S 定义了一种新的字母顺序，要求把 T 按照 S 定义的顺序排序。

题解：我是先用了一个 hashmap 记录了 T 的每个字母的频次，然后再遍历一遍 S， 构造ans字符串，最后遍历hashmap中剩下的字符，组成新的字符串。

 1 class Solution {
 2 public:
 3     string customSortString(string S, string T) {
 4         const int n = T.size();
 5         unordered_map<char, int> mp;
 6         for (int i = 0; i < n; ++i) {
 7             mp[T[i]]++;
 8         }
 9         string ret;
10         for (auto c : S) {
11             if (mp.find(c) == mp.end() || mp[c] == 0) {continue;}
12             ret += string(mp[c], c);
13             mp[c] = 0;
14         }
15         for (auto ele : mp) {
16             if (ele.second > 0) {
17                 ret += string(ele.second, ele.first);
18             }
19         }
20         return ret;
21     }
22 };

View Code

 

【790】Domino and Tromino Tiling（第四题 5分）

给了多米诺骨牌，有两种形状，

 

XX  <- domino

XX  <- "L" tromino
X

 

给定一个 N 问有多少种填充方案能填满 2 * N 个格子。答案要对 1e9+7 取模。

题解：dp做。

 

Contest 74 （2019年1月31日模拟）

链接：https://leetcode.com/contest/weekly-contest-74

 

Contest 75 （2019年1月31日模拟）

链接：https://leetcode.com/contest/weekly-contest-75