Chapter 38 Google 2016 11
38.1 Design Candy Crush
2016(10-12月) 码农类 硕士 全职 Google - 内推 - Onsite |Otherfresh grad应届毕业生 MTV onsite.
1. 印度小哥,全程没有提示.这道题完全不知道怎么写,最后瞎写了一下… 题目:有一条公路,长度是m, 中间有k个加油站,由此我们可以得到一个加油站之间的最大距离,然后给你一个数t,这个数代表增加的加油站的数量(往里面插入),求使得加油站之间最大距离变得最小的值,返回这个最小的最大距离.
2. 印度小哥,上来先问了问一个数组全是0,1,应该怎么sort. (bucket sort/ counting sort). 然后问题: Candy Crush. 假设要设计一个这样的游戏,我们有4种Candy, 然后有一个board(n * n), 规定在任何一行和一列上不能出现连续的3个相同的Candy, 如何设计这个游戏版. 这个游戏版是用于游戏的初始化,所以每次要尽可能的使版面随机,并且满足限制条件.
中午是个国人大哥,带吃饭非常爽
3. 白人小哥, leetcode 425 Wrod Squares 稍微修改了一下, 有重复,并且每个字的长度不一定相同, follow up : test cases 应该怎么写 (DFS + Trie) 没写完
4. 中国小哥, 提示很多.有一个数组,类似于:{{‘Canada’, 3}, {‘USA’, 5}, {‘UK’, 2}, {‘Brasil’, 3}}, 数组的类型是Country, 有两个变量, Country.name, Country.weight. 每个国家都有一个权重,然后给一个output()函数,每次调用这个函数的时候就输出一个国家的名字,要使每个国家被输出的概率相等.我用的方法是平摊weight: {Canada, Canada, USA, USA, USA, USA, UK, UK, Brasil, Brasil, Brasil}, 然后用Random 函数输出.Follow up : 如果这个权重的值很大很大,比如billio级别,应该怎么办.我的方法是类似于线段树,然后再用sum * Random(), 看这个区间坐落在哪里.
还是水平太差,滚回去继续刷题!
补充内容 (2016-11-21 09:52): 第四题说错了,应该是输出的概率和权重匹配,就是canada应该是3/13, USA: 5/13 http://bit.ly/2etEAJr
38.3 Light Strength (Bomb Enemy Extended)
如果光有范围? 炸弹有爆炸范围?单纯tmp记录到目前为止能bomb的enemy就不够,它没有保存每个enemy的位置信息.
用一个queue保存目前能炸掉的enemy的位置信息,每次循环到一个新点的时候,检查queue的front元素是否在爆炸范围之内,不在的话就pop.
如果每点光照范围不同,可以用priority_queue
queue存的东西是这样的:
{range, location}
比较函数是:
location-range
38.4 68. Text Justification
38.4.1 Justify Text Line
今天看到这类题中最简单的一个.
Write an algorithm to count the number of optimal ways that we can justify a text line to both left and right margins by adding extra spaces between words as necessary.
The length of the desired justified line is given as an input argument.
For example, if the input line is: ‘justify this line’ and the length of the desired justified line is 20, there will be 4 ways to justify that line:
a: 'justify this line'
b: 'justify this line'
c: 'justify this line'
d: 'justify this line'out of which 2 are optimal (b and c) in the sense that they are the most visually appealing solutions, so the answer will be 2.
- Input Format
The first line specifies the length of the justified line. The second line specifies the number of input lines N. The next N lines specify the input lines
- Constraints
None
- Output Format
One number per input line which specifies the number of ways the corresponding input line can be justified to left and right marging
https://www.hackerrank.com/contests/algomars-02162017/challenges/line-alignment
int Justify_Text_Line(string s, int len) {
istringstream ss(s);
vector<string> tokens;
string e;
while (getline(ss, e, ' ')) //注意如果有多个空格要忽略空格
if(!e.empty()) tokens.push_back(e);
int L = tokens.size();
int t = 0;
for (int i = 0; i<L; ++i)t += tokens[i].size();
if (t>len) return -1;
int spaces = len - t;
int gap = L - 1;
if (gap <= 1) return 1;
int k = spaces%gap;
int r = 1;
while (k <= gap) r *= k++;
return r;
}edge case
当只有一个或者两个单词时候,直接返回1,因为the number of optimal ways一定等于1.
注意要手写string split函数. 还有最后的16,17行是在算\(C^{k}_{n}\).
38.4.2 Leetcode Greedy
Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ’ ’ when necessary so that each line has exactly L characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.
Return the formatted lines as:
[
"This is an",
"example of text",
"justification. "
]
https://leetcode.com/problems/text-justification/
http://zhuixin8.com/2016/10/02/leetcode-68/
本来这是一个经典的动态规划题目,但是本题指定用Greedy来解,难度立刻下降了.
https://discuss.leetcode.com/topic/4189/share-my-concise-c-solution-less-than-20-lines
struct Solution { // 0ms
vector<string> fullJustify(vector<string>& ws, int maxWidth) {// 0ms
vector<string> r;
int L = ws.size(), m = 0, sumlen = 0, i = 0;
while (i<L) { //sumlen:该行所有单词长度和,m:该行单词数目=gap+1
// 1. 找到填满一行需要的单词
m = 0, sumlen = 0;
//1个单词0个空格,2个单词至少1个空格,3个单词至少2个空格
while (i + m != L && m + sumlen + ws[i + m].size() <= maxWidth)
sumlen += ws[i + m].size(), m++;
// 2. 用找到的单词填满一行
string s(ws[i]); //spaces:需要填的空格的数目
int gap = m - 1, spaces = maxWidth - sumlen;
for (int j = 0; j < gap; j++) {
if (i + m == L) { //last line每个单词后只跟一个space
s += " ";
} else {
s.append(spaces / gap + (j<spaces%gap), ' '); //append
}
s += ws[i + j + 1];
}
// edge case: one word in one line or lastline,填满一行
if (m == 1 || i + m == L) s.append(maxWidth - s.size(), ' ');
// 3. 把这一行加入最终结果
r.push_back(s);
i += m;
}
return r;
}
};其中这一行str.append(spaces/gib+(j<spaces%gib), ' ');巧妙的求不均衡空格,就是利用位置与除余的关系来让左边分配多余空格．多余空格分配在前面.
append的一个比较少见的用法(http://www.cplusplus.com/reference/string/string/append/).
复杂度: \(O(NK)\) K是每行的string个数
struct Solution {
vector<string> fullJustify(vector<string>& words, int maxwidth) {
vector<string> r;
int N = words.size();
int h = 0;
while (h<N) {
int wordlen = 0, n = 0;
while (h + n<N && wordlen + words[h + n].size() + n <= maxwidth)
wordlen += words[h + n].size(), n++;
string oneline(words[h]);
int gap = n - 1, spaces = maxwidth - wordlen;
for (int i = 0; i<gap; ++i) {
if (h + n == N) {
oneline += " ";
} else {
int x = spaces / gap, y = spaces%gap;
oneline.append(x + (i<y), ' ');
}
oneline += words[h + i + 1];
}
if (n == 1 || h + n == N) oneline.append(maxwidth - oneline.size(), ' ');
r.push_back(oneline);
h += n;
}
return r;
}
};
