【Leetcode周赛】从contest-71开始。(一般是10个contest写一篇文章)
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)
题解:直接枚举。注意旋转是说 每个数字单独旋转,并不是把整个数旋转。
class Solution {
public:
int rotatedDigits(int N) {
unordered_map<int, int> mp;
mp[] = , mp[] = , mp[] = , mp[]= , mp[] = , mp[] = , mp[] = ;
int ans = ;
for (int i = ; i <= N; ++i) {
string s = to_string(i);
string rev = "";
bool valid = true;
for (auto c : s) {
if (mp.find(c-'') == mp.end()) {
valid = false;
break;
}
rev += string(, mp[c-''] + '');
}
if (valid && s != rev && rev[] != '') {
ans++;
}
}
return ans;
}
};
【789】Escape The Ghosts(第二题 5分)逃离鬼魂(谷歌tag,数学题)
假设你站在原点,有个去的目标 target 坐标,在二维平面上有一些鬼魂(鬼也有坐标)。每一步,你和鬼魂都能上下左右移动一格。问有没有可能在鬼怪抓到你之前,到达target。如果你和鬼怪同时到达target的话,那么鬼赢了。
题解:我比赛的时候想成了比较复杂的bfs,去模拟每个位置。幸好没有写。本题的本质是只要你和target 的曼哈顿距离小于任何一个鬼怪距离target的目标距离,你就有可能会赢。所以只要判断一下距离就行了。
class Solution {
public:
bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
const int dist = abs(target[]) + abs(target[]);
for (auto& ele : ghosts) {
int d = abs(target[] - ele[]) + abs(target[] - ele[]);
if (d < dist) {
return false;
}
}
return true;
}
};
比赛的时候理解有问题,我一直以为某个时间人和鬼都必须要移动,不能站着不动。但是总监说不能站着不动的话,这题的难度也没有增加,因为如果有个鬼到target的距离和人到target距离如果差了一步的话,人就能到target,如果差了两步的话,鬼就能先离开,然后再回到target,所以这个时候鬼赢了。
然后还有一个变种,如果鬼不能到target,它最多在target周围四个格子,有点像猫和老鼠那题。
【791】Custom Sort String(第三题 5分)
给了两个字符串 S 和 T,S 定义了一种新的字母顺序,要求把 T 按照 S 定义的顺序排序。
题解:我是先用了一个 hashmap 记录了 T 的每个字母的频次,然后再遍历一遍 S, 构造ans字符串,最后遍历hashmap中剩下的字符,组成新的字符串。
class Solution {
public:
string customSortString(string S, string T) {
const int n = T.size();
unordered_map<char, int> mp;
for (int i = ; i < n; ++i) {
mp[T[i]]++;
}
string ret;
for (auto c : S) {
if (mp.find(c) == mp.end() || mp[c] == ) {continue;}
ret += string(mp[c], c);
mp[c] = ;
}
for (auto ele : mp) {
if (ele.second > ) {
ret += string(ele.second, ele.first);
}
}
return ret;
}
};
【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
Contest 77 (2019年2月3日模拟)
链接:https://leetcode.com/contest/weekly-contest-77
总结:做出来三道题。3/4
【806】Number of Lines To Write String(第一题 4分)
给了一个数组,数组中的元素作为 'a' ~ 'z' 的每个占位符的宽度。每行最多100个字符宽度,问给了一个字符串,返回两个数字,一个是这个字符串需要占多少行,第二个是这个字符串的最后一行有多少个字符。
Example :
Input:
widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "abcdefghijklmnopqrstuvwxyz"
Output: [3, 60]
Explanation:
All letters have the same length of 10. To write all 26 letters,
we need two full lines and one line with 60 units.
题解:用个 curSum 的变量记录当前行有多少个字符,当 curSum 大于 100 的时候就换行。
class Solution {
public:
vector<int> numberOfLines(vector<int>& widths, string S) {
const int n = S.size();
int curLen = ;
vector<int> ans(, );
for (int i = ; i < n; ++i) {
curLen += widths[S[i]-'a'];
if (curLen > ) {
ans[]++;
curLen = widths[S[i]-'a'];
}
}
ans[] += ;
ans[] = curLen;
return ans;
}
};
【804】Unique Morse Code Words(第二题 4分)
给了一个数组作为 'a' 到 'z' 的摩斯码编码,给了一个 word list, 不同的单词可能有相同的莫斯码编码,返回有多少不同的摩斯码编码的种类。
题解:遍历,用set去除重复。
class Solution {
public:
int uniqueMorseRepresentations(vector<string>& words) {
vector<string> morse = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
set<string> st;
for (auto& w : words) {
string str;
for (auto& c : w) {
str += morse[c - 'a'];
}
st.insert(str);
}
return (int)st.size();
}
};
【807】Max Increase to Keep City Skyline(第三题 5分)
给了一个 二维的grid, grid[i][j] 代表 (i, j) 坐标的楼的高度,我们能从前后和左右看到两个高度的轮廓,我们的目标是增加楼的高度,但是让轮廓线不变。
Example:
Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
Output: 35
Explanation:
The grid is:
[ [3, 0, 8, 4],
[2, 4, 5, 7],
[9, 2, 6, 3],
[0, 3, 1, 0] ] The skyline viewed from top or bottom is: [9, 4, 8, 7]
The skyline viewed from left or right is: [8, 7, 9, 3] The grid after increasing the height of buildings without affecting skylines is: gridNew = [ [8, 4, 8, 7],
[7, 4, 7, 7],
[9, 4, 8, 7],
[3, 3, 3, 3] ]
题解:我们先计算出 top 和 left 的轮廓线,grid[i][j] 能取到的最大的高度就是 min(top[j], left[i])
class Solution {
public:
int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
const int n = grid.size(), m = grid[].size();
vector<int> fromTop(m, ), fromLeft(n, );
for (int i = ; i < n; ++i) {
for (int j = ; j < m; ++j) {
fromTop[j] = max(fromTop[j], grid[i][j]);
fromLeft[i] = max(fromLeft[i], grid[i][j]);
}
}
int ret = ;
for (int i = ; i < n; ++i) {
for (int j = ; j < m; ++j) {
ret += min(fromTop[j], fromLeft[i]) - grid[i][j];
}
}
return ret;
}
};
【805】Split Array With Same Average(第四题 9分)
最新文章
- C#开发中常用方法2------json转DataTable
- plain framework 1(简约框架)一款主要用于网络(游戏)开发的C/C++框架 即将开源发布
- JS组件系列——Bootstrap Table 表格行拖拽(二:多行拖拽)
- IBatis和Hibernate区别
- java selenium (八) Selenium IDE 用法
- Bootstrap系列 -- 8. 代码显示
- Greenplum——升级的分布式PostgresSQL
- [Json] C#ConvertJson|List转成Json|对象|集合|DataSet|DataTable|DataReader转成Json (转载)
- linux定时器
- Problem B: Excuses, Excuses!
- Trie树:应用于统计和排序
- Ansible系列(五):playbook应用和roles自动化批量安装示例
- RSS简介
- ajax参数
- Should we ban guns 英语禁枪议论文
- .NET拾忆:反射的本质——元数据
- 猜生日 Java小游戏
- springboot工程pom的两种配置方式
- hdu1081 To The Max 2016-09-11 10:06 29人阅读 评论(0) 收藏
- 关于IIS权限问题(Selenium WebDriver调用出错记录)