Z**********4
发帖数: 528 | 1 session 1一个class {int a, bool c, int b} 里面每个variable所占的空间都不同
，比如a,b是int 所以分别占4byte. bool的c只占1byte。还有其他变量，可能占8bytes
或者16bytes。都是2的次方就是。
问题是写一个程序让他们可以很好的被放到8byte为单位的block里面去然后空间不会浪
费。
比如如果是 就按照a, c, b的话它一共要占12个byte。因为当把a和c放到一个block的
时候就会浪费一些空间。
所以最好摆成a，b，c这样的话更合理。占9个byte。剩下的空间还可以放一些小的
object。
其实这个就是用排序，然后从大的变量依次放进block。
有个followup的问题就是：因为我不想过多移动这些变量，所以怎么才能设计一个算法
所需要移动的object最少。
比如如果变量的size一次是4, 4, 1, 1, 8, 8, 1, 1最好的排法是4, 4, 8, 8, 1, 1,
1, 1.而不是8 8 4 4 1 1 1 1因为前一种所需要移动的cost最小。这个没想出来了。。
应该用divide and conquer？
session 2： 1. 设计算法找出平面上点的convex hull 不用写code（不熟。讨论下想
出，但是应该悲剧）
2. code 插入元素到max heap。
session 3： 1. 一个bit的stream， 每次读取6个bit。转化成char。
2. 很多URL，找到所有distinct的URL。（分布式计算）
session 4: 写出长度小于N的所有旋转对称数。
例子 689 顺时针旋转180度还是689
递归。也可以dp。
session 5: 设计数据结构，满足insert,delete,getRandom都是O(1)
就是这样了。结果估计不咋地。
anyway move on。
希望后面的面试结果不错。 |
y***n
发帖数: 1594 | |
Z**********4
发帖数: 528 | 3 不能同意更多。
lc也刷了几遍了。
但是写那个bit流的时候，输入是一个char array
然后我在那里想办法算offset做位操作，最后code竟然没有finish。
然后我就释然了。你懂的。
【在 y***n 的大作中提到】
: 感觉看着简单，写好不容易。
|
G******n
发帖数: 572 | 4 mark。
session5 应该是什么数据结构？谢谢 |
y***n
发帖数: 1594 | 5 我也版上看了一段时间了，G的面试题最有质量，靠刷题还是比较难的，要基础好。
【在 Z**********4 的大作中提到】
: 不能同意更多。
: lc也刷了几遍了。
: 但是写那个bit流的时候，输入是一个char array
: 然后我在那里想办法算offset做位操作，最后code竟然没有finish。
: 然后我就释然了。你懂的。
|
v***o
发帖数: 287 | 6 1. 变量的值在{1，4，8，16} 中间，直接group就可，不需排序，找出相同值连续最多
的同一值group,把其他零碎的移过来即可。
8bytes
【在 Z**********4 的大作中提到】
: session 1一个class {int a, bool c, int b} 里面每个variable所占的空间都不同
: ，比如a,b是int 所以分别占4byte. bool的c只占1byte。还有其他变量，可能占8bytes
: 或者16bytes。都是2的次方就是。
: 问题是写一个程序让他们可以很好的被放到8byte为单位的block里面去然后空间不会浪
: 费。
: 比如如果是 就按照a, c, b的话它一共要占12个byte。因为当把a和c放到一个block的
: 时候就会浪费一些空间。
: 所以最好摆成a，b，c这样的话更合理。占9个byte。剩下的空间还可以放一些小的
: object。
: 其实这个就是用排序，然后从大的变量依次放进block。
|
U***A
发帖数: 849 | 7 第一题是一定要从大到小排序？是不是只要分两端就可以，4byte及以上的排在前面，
2byte及1byte的排在后半段（后半段还是按大小排序。）
有点像quick sort。 |
r*******e
发帖数: 971 | |
U***A
发帖数: 849 | |
r*******e
发帖数: 971 | 10 session 3 的第二题怎么用分布式计算 解决呢？
【在 y***n 的大作中提到】
: 我也版上看了一段时间了，G的面试题最有质量，靠刷题还是比较难的，要基础好。
|
|
|
G******n
发帖数: 572 | |
j**********3
发帖数: 3211 | |
t*******i
发帖数: 4960 | 13 直接吐血倒地。
楼主什么背景啊，这些题一出我直接投降。
8bytes
【在 Z**********4 的大作中提到】
: session 1一个class {int a, bool c, int b} 里面每个variable所占的空间都不同
: ，比如a,b是int 所以分别占4byte. bool的c只占1byte。还有其他变量，可能占8bytes
: 或者16bytes。都是2的次方就是。
: 问题是写一个程序让他们可以很好的被放到8byte为单位的block里面去然后空间不会浪
: 费。
: 比如如果是 就按照a, c, b的话它一共要占12个byte。因为当把a和c放到一个block的
: 时候就会浪费一些空间。
: 所以最好摆成a，b，c这样的话更合理。占9个byte。剩下的空间还可以放一些小的
: object。
: 其实这个就是用排序，然后从大的变量依次放进block。
|
Z**********4
发帖数: 528 | 14 工作了一段时间。
我也投降啊。。
【在 t*******i 的大作中提到】
: 直接吐血倒地。
: 楼主什么背景啊，这些题一出我直接投降。
:
: 8bytes
|
h*******e
发帖数: 1377 | 15 convex hull 旋转卡壳之类的不用模板根本不可能保证没bug~~
【在 Z**********4 的大作中提到】
: 不能同意更多。
: lc也刷了几遍了。
: 但是写那个bit流的时候，输入是一个char array
: 然后我在那里想办法算offset做位操作，最后code竟然没有finish。
: 然后我就释然了。你懂的。
|
h*******e
发帖数: 1377 | 16 插入到max heap是要求不用stl 那种手工实现么。。昨天还和一google 的同学讨论呢
， 他说topk min heap不用自己手工写， 看来没有什么是绝对的。 |
Z**********4
发帖数: 528 | 17 你这个是可以的。
，
【在 U***A 的大作中提到】
: 第一题是一定要从大到小排序？是不是只要分两端就可以，4byte及以上的排在前面，
: 2byte及1byte的排在后半段（后半段还是按大小排序。）
: 有点像quick sort。
|
Z**********4
发帖数: 528 | 18 只用实现插入。
用一个数组表示heap。
几行代码就可以搞定。
【在 h*******e 的大作中提到】
: 插入到max heap是要求不用stl 那种手工实现么。。昨天还和一google 的同学讨论呢
: ， 他说topk min heap不用自己手工写， 看来没有什么是绝对的。
|
Z**********4
发帖数: 528 | 19 我觉得大概思路就是先把相同的url想办法放到同一个server上面。利用类似
consistent hashing的办法。
然后每个server计算distinct的url。再汇总。
【在 r*******e 的大作中提到】
: session 3 的第二题怎么用分布式计算 解决呢？
|
Z**********4
发帖数: 528 | 20 哈哈。累啊。
【在 j**********3 的大作中提到】
: 你最近面很多阿
|
|
|
h*******e
发帖数: 1377 | 21 很多东西有类库实现了， 用和想的时候，思维就把这个抽象掉了， 渐渐就忘掉了～～～
等晚上有大块时间的，我再仔细看看你的面经里面的题。多谢面经，很详细的。
【在 Z**********4 的大作中提到】
: 只用实现插入。
: 用一个数组表示heap。
: 几行代码就可以搞定。
|
t*******i
发帖数: 4960 | 22 MapReduce?
【在 Z**********4 的大作中提到】
: 我觉得大概思路就是先把相同的url想办法放到同一个server上面。利用类似
: consistent hashing的办法。
: 然后每个server计算distinct的url。再汇总。
|
l*****a
发帖数: 14598 | 23 好银，先顶后看
8bytes
【在 Z**********4 的大作中提到】
: session 1一个class {int a, bool c, int b} 里面每个variable所占的空间都不同
: ，比如a,b是int 所以分别占4byte. bool的c只占1byte。还有其他变量，可能占8bytes
: 或者16bytes。都是2的次方就是。
: 问题是写一个程序让他们可以很好的被放到8byte为单位的block里面去然后空间不会浪
: 费。
: 比如如果是 就按照a, c, b的话它一共要占12个byte。因为当把a和c放到一个block的
: 时候就会浪费一些空间。
: 所以最好摆成a，b，c这样的话更合理。占9个byte。剩下的空间还可以放一些小的
: object。
: 其实这个就是用排序，然后从大的变量依次放进block。
|
l*****8
发帖数: 1083 | |
w******e
发帖数: 1621 | 25 先谢lz好人，第一题的follow up 没有看懂啊 lz能不能举个栗子
8bytes
【在 Z**********4 的大作中提到】
: session 1一个class {int a, bool c, int b} 里面每个variable所占的空间都不同
: ，比如a,b是int 所以分别占4byte. bool的c只占1byte。还有其他变量，可能占8bytes
: 或者16bytes。都是2的次方就是。
: 问题是写一个程序让他们可以很好的被放到8byte为单位的block里面去然后空间不会浪
: 费。
: 比如如果是 就按照a, c, b的话它一共要占12个byte。因为当把a和c放到一个block的
: 时候就会浪费一些空间。
: 所以最好摆成a，b，c这样的话更合理。占9个byte。剩下的空间还可以放一些小的
: object。
: 其实这个就是用排序，然后从大的变量依次放进block。
|
l*****a
发帖数: 14598 | 26 得写两个吧
heap未满时shiftup
满时shiftdown
【在 Z**********4 的大作中提到】
: 只用实现插入。
: 用一个数组表示heap。
: 几行代码就可以搞定。
|
v***n
发帖数: 562 | |
m*****k
发帖数: 731 | 28 比如如果变量的size一次是4, 4, 1, 1, 8, 8, 1, 1最好的排法是4, 4, 8, 8, 1, 1,
1, 1.而不是8 8 4 4 1 1 1 1因为前一种所需要移动的cost最小。
>=8的直接输出，<8的插入一个当前block（if null, then create 1）,overflow则内
部按降序,
insertion sort，满8输出，多的插入新block中，update 当前block=新block,
循环完时输出当前block if !null,
8bytes
【在 Z**********4 的大作中提到】
: session 1一个class {int a, bool c, int b} 里面每个variable所占的空间都不同
: ，比如a,b是int 所以分别占4byte. bool的c只占1byte。还有其他变量，可能占8bytes
: 或者16bytes。都是2的次方就是。
: 问题是写一个程序让他们可以很好的被放到8byte为单位的block里面去然后空间不会浪
: 费。
: 比如如果是 就按照a, c, b的话它一共要占12个byte。因为当把a和c放到一个block的
: 时候就会浪费一些空间。
: 所以最好摆成a，b，c这样的话更合理。占9个byte。剩下的空间还可以放一些小的
: object。
: 其实这个就是用排序，然后从大的变量依次放进block。
|
o***e
发帖数: 28 | 29 感觉是个好解法 只是如果 blocks 比较少的时候 因为是插入排序 有可能没有快排之
类的快 不知道会不会是个问题
【在 m*****k 的大作中提到】
: 比如如果变量的size一次是4, 4, 1, 1, 8, 8, 1, 1最好的排法是4, 4, 8, 8, 1, 1,
: 1, 1.而不是8 8 4 4 1 1 1 1因为前一种所需要移动的cost最小。
: >=8的直接输出，<8的插入一个当前block（if null, then create 1）,overflow则内
: 部按降序,
: insertion sort，满8输出，多的插入新block中，update 当前block=新block,
: 循环完时输出当前block if !null,
:
: 8bytes
|
r*******k
发帖数: 1423 | 30 还是不一定是最优啊
4 2 2 这样的，就完全不用移动
或者8个1连续的
，
【在 U***A 的大作中提到】
: 第一题是一定要从大到小排序？是不是只要分两端就可以，4byte及以上的排在前面，
: 2byte及1byte的排在后半段（后半段还是按大小排序。）
: 有点像quick sort。
|
|
|
r*******k
发帖数: 1423 | 31 堆一定要有长度限制么？
看了眼java里的实现
内部数组，如果长度超了
就新开数组进行arraycopy
【在 l*****a 的大作中提到】
: 得写两个吧
: heap未满时shiftup
: 满时shiftdown
|
t*******e
发帖数: 274 | 32 有具体的实现么？
【在 m*****k 的大作中提到】
: 比如如果变量的size一次是4, 4, 1, 1, 8, 8, 1, 1最好的排法是4, 4, 8, 8, 1, 1,
: 1, 1.而不是8 8 4 4 1 1 1 1因为前一种所需要移动的cost最小。
: >=8的直接输出，<8的插入一个当前block（if null, then create 1）,overflow则内
: 部按降序,
: insertion sort，满8输出，多的插入新block中，update 当前block=新block,
: 循环完时输出当前block if !null,
:
: 8bytes
|
Z**********4
发帖数: 528 | 33 这个取决于面试官。
你可以问他。 我当时没有问了。
【在 r*******k 的大作中提到】
: 堆一定要有长度限制么？
: 看了眼java里的实现
: 内部数组，如果长度超了
: 就新开数组进行arraycopy
|
x**i
发帖数: 2627 | 34 不错，赞一个！！
8bytes
【在 Z**********4 的大作中提到】
: session 1一个class {int a, bool c, int b} 里面每个variable所占的空间都不同
: ，比如a,b是int 所以分别占4byte. bool的c只占1byte。还有其他变量，可能占8bytes
: 或者16bytes。都是2的次方就是。
: 问题是写一个程序让他们可以很好的被放到8byte为单位的block里面去然后空间不会浪
: 费。
: 比如如果是 就按照a, c, b的话它一共要占12个byte。因为当把a和c放到一个block的
: 时候就会浪费一些空间。
: 所以最好摆成a，b，c这样的话更合理。占9个byte。剩下的空间还可以放一些小的
: object。
: 其实这个就是用排序，然后从大的变量依次放进block。
|
h*******0
发帖数: 270 | 35 用hadoop来做可以吗？ 一个reducer就搞定了。 还是说google不想让咱们借用外部工
具？
【在 Z**********4 的大作中提到】
: 我觉得大概思路就是先把相同的url想办法放到同一个server上面。利用类似
: consistent hashing的办法。
: 然后每个server计算distinct的url。再汇总。
|
f******n
发帖数: 279 | |
s******i
发帖数: 236 | |
j**********3
发帖数: 3211 | 38 我可以站内你问经验么？
先谢谢lz。。。
【在 Z**********4 的大作中提到】
: 哈哈。累啊。
|
Z**********4
发帖数: 528 | 39 可以啊
【在 j**********3 的大作中提到】
: 我可以站内你问经验么？
: 先谢谢lz。。。
|
y***n
发帖数: 1594 | 40 这给ｂｉｔ 题什么意思？
【在 Z**********4 的大作中提到】
: 不能同意更多。
: lc也刷了几遍了。
: 但是写那个bit流的时候，输入是一个char array
: 然后我在那里想办法算offset做位操作，最后code竟然没有finish。
: 然后我就释然了。你懂的。
|
|
|
m*****k
发帖数: 731 | 41 code起来感觉是比较tedious，
但本质上就是新来的size如果会使当前没填满的block溢出的话就去找block中刚好
sumup等于溢出量的size们（从后往前倒着找保证最小move， 而且可以证明一定可以找
到sumup等于溢出量的size们，这源于size都是2的次方），把他们放入新block，新
来的size加入到当前没填满的block使之填满，输出。
example:
[1 1 1 4 ], incoming 4, overflow 3, find the 3 1's that sumup to 3,
change to
[4 4 ] [1 1 1], 输出 4, 4, 当前没填满的block reset 为 ［ 1 1 1］
【在 t*******e 的大作中提到】
: 有具体的实现么？
|
m********6
发帖数: 58 | 42 SESSION1 的体，我觉得不用SORT。 只要在无法完成8bytes的时候swap即可。
public static void optimize(int[] fields)
{
int blockStart = 0;
int blockSize = 0;
for (int i = 0; i < fields.length; i++)
{
blockSize += fields[i];
if (blockSize % 8 == 0)
{
blockStart = i + 1;
blockSize = 0;
}
else if (blockSize > 8)
{
blockStart = rearrange(fields, blockStart, i);
blockSize = blockSize % 8;
}
}
}
private static int rearrange(int[] fields, int blockStart, int blockEnd)
{
int maxSize, maxPos, blockSize;
blockSize = 0;
while (blockSize < 8)
{
maxSize = fields[blockStart];
maxPos = blockStart;
for (int i = blockStart + 1; i <= blockEnd; i++)
{
if (fields[i] > maxSize)
{
maxSize = fields[i];
maxPos = i;
}
}
fields[maxPos] = fields[blockStart];
fields[blockStart] = maxSize;
blockStart++;
blockSize += maxSize;
}
return blockStart;
}
rearrange虽然是有一个loop， 但是虽多执行7次， 所以是O(1)。 optimize是O(N)。
严格的说， optimize是O(N*M*M)。 N是field size, M是block size。
8bytes
【在 Z**********4 的大作中提到】
: session 1一个class {int a, bool c, int b} 里面每个variable所占的空间都不同
: ，比如a,b是int 所以分别占4byte. bool的c只占1byte。还有其他变量，可能占8bytes
: 或者16bytes。都是2的次方就是。
: 问题是写一个程序让他们可以很好的被放到8byte为单位的block里面去然后空间不会浪
: 费。
: 比如如果是 就按照a, c, b的话它一共要占12个byte。因为当把a和c放到一个block的
: 时候就会浪费一些空间。
: 所以最好摆成a，b，c这样的话更合理。占9个byte。剩下的空间还可以放一些小的
: object。
: 其实这个就是用排序，然后从大的变量依次放进block。
|
m********6
发帖数: 58 | 43 Session 4:
A valid number may not contain 2,3,4,5,7. Flip those numbers 180 degrees and
it's not a valid number. Single digit numbers is a special case. It
contains 0, 1, 8. For 2N digit numbers, the first digit can be 1,6,8,9 and
the next N-1 digits can be 0,1,6,8,9. For 2N+1 digit numbers, you can insert
0,1,8 in the middle of any valid 2N digit numbers and it's still a valid
number.
1 digit: 3
2N digit: 4 * 5 ^ (N-1)
2N+1 digit: 3 * 4 * 5 ^ (N-1)
For example, there are 20 valid 4 digit numbers:
10 => 1001, 11 => 1111, 16 => 1691, 18 => 1881, 19 => 1961
60 => 6009, 61 => 6119, 66 => 6699, 68 => 6889, 69 => 6969
80 => 8008, 81 => 8118, 86 => 8698, 88 => 8888, 89 => 8968
90 => 9006, 91 => 9116, 96 => 9696, 98 => 9886, 99 => 9966
there are 60 valid 5 digit numbers
1001 => 10001, 10101, 10801 etc
public static int getNumMirrors(String limit)
{
byte[] n = limit.getBytes();
int digits = n.length;
for (int i = 0; i < digits; i++)
{
n[i] -= '0';
}
if (digits == 1)
{
return getNumMirrorsSingleDigit(n[0]);
}
else
{
return getNumMirrorsLessThanKDigits(digits) +
getNumKDigitMirrorsLessThanN(n, digits);
}
}
private static int getNumMirrorsSingleDigit(int n)
{
if (n >=8) return 3;
if (n >=1) return 2;
return 1;
}
private static int getNumMirrorsLessThanKDigits(int digits)
{
int sum = 3; // 0, 1, 8
int base = 4; // 1, 8, 6, 9
for (int i = 1; i < digits/2; i++)
{
sum += 4 * base;
base *= 5;
}
if (digits % 2 == 1)
{
sum += base;
}
return sum;
}
private static int getNumKDigitMirrorsLessThanN(byte[] n, int digits)
{
int sum;
int base = 1;
boolean isNMirror;
for (int i = 1; i < digits/2; i++)
{
base *= 5;
}
if (digits % 2 == 1)
{
base *= 3;
}
switch (n[0]) // 1, 6, 8, 9
{
// n=987654321, add all mirrors between 0 and 900000000
case 9: sum = 3 * base; isNMirror = n[digits-1] == 6; break;
case 8: sum = 2 * base; isNMirror = n[digits-1] == 8;break;
case 7: return 2 * base;
case 6: sum = base; isNMirror = n[digits-1] == 9;break;
case 1: sum = 0; isNMirror = n[digits-1] == 1;break;
default: return base;
}
for (int i = 1; i < digits/2; i++)
{
base /= 5;
switch (n[i]) // 0, 1, 6, 8, 9
{
// n=987654321, i=1, add all mirrors between 900000000 and
980000000
case 9: sum += 4 * base; isNMirror &= n[digits-i-1] == 6;
break;
case 8: sum += 3 * base; isNMirror &= n[digits-i-1] == 8;
break;
case 7: return 3 * base;
case 6: sum += 2 * base; isNMirror &= n[digits-i-1] == 9;
break;
case 1: sum += base; isNMirror &= n[digits-i-1] == 1; break;
case 0: isNMirror &= n[digits-i-1] == 0; break;
default: return sum + 2 * base;
}
}
if (digits % 2 == 1)
{
switch (n[digits/2]) // 0, 1, 8
{
case 9: return sum + 3;
case 8: sum += 2; break;
case 1: sum += 1; break;
case 0: break;
default: return sum + 2;
}
}
return isNMirror ? sum + 1 : sum;
}
8bytes
【在 Z**********4 的大作中提到】
: session 1一个class {int a, bool c, int b} 里面每个variable所占的空间都不同
: ，比如a,b是int 所以分别占4byte. bool的c只占1byte。还有其他变量，可能占8bytes
: 或者16bytes。都是2的次方就是。
: 问题是写一个程序让他们可以很好的被放到8byte为单位的block里面去然后空间不会浪
: 费。
: 比如如果是 就按照a, c, b的话它一共要占12个byte。因为当把a和c放到一个block的
: 时候就会浪费一些空间。
: 所以最好摆成a，b，c这样的话更合理。占9个byte。剩下的空间还可以放一些小的
: object。
: 其实这个就是用排序，然后从大的变量依次放进block。
|
m*****k
发帖数: 731 | 44 跑了一下你的程序，
int[] input = new int[] { 1, 1, 1, 2, 4 };
optimize(input);
input 变成 { 4, 2, 1, 1, 1 }
答案应该是｛1,1,2,4,1｝吧
【在 m********6 的大作中提到】
: SESSION1 的体，我觉得不用SORT。 只要在无法完成8bytes的时候swap即可。
: public static void optimize(int[] fields)
: {
: int blockStart = 0;
: int blockSize = 0;
: for (int i = 0; i < fields.length; i++)
: {
: blockSize += fields[i];
: if (blockSize % 8 == 0)
: {
|
g***s
发帖数: 3811 | 45 你这个也不是最优。
就如你给的例子： {1 1 1 4 4}
只需要2 blocks，0 swaps。
【在 m*****k 的大作中提到】
: code起来感觉是比较tedious，
: 但本质上就是新来的size如果会使当前没填满的block溢出的话就去找block中刚好
: sumup等于溢出量的size们（从后往前倒着找保证最小move， 而且可以证明一定可以找
: 到sumup等于溢出量的size们，这源于size都是2的次方），把他们放入新block，新
: 来的size加入到当前没填满的block使之填满，输出。
: example:
: [1 1 1 4 ], incoming 4, overflow 3, find the 3 1's that sumup to 3,
: change to
: [4 4 ] [1 1 1], 输出 4, 4, 当前没填满的block reset 为 ［ 1 1 1］
|
m*****k
发帖数: 731 | 46 输入{1 1 1 4 4}
变成
｛4 4 1 1 1｝ why 0 swaps?
难道你的答案是{1 1 1 4 4}？
block1 ［1 1 1 ］with 5 empty ， followed by block2［4 4］
显然不是答案，原题首先要求空间不浪费，其次要求最小move
【在 g***s 的大作中提到】
: 你这个也不是最优。
: 就如你给的例子： {1 1 1 4 4}
: 只需要2 blocks，0 swaps。
|
g***s
发帖数: 3811 | 47 看你如何定义不浪费
1 1 1 4 4 无论如何都要2 blocks，所以我认为的不浪费是1 1 1 4 4占用的空间是等
于4 4 1 1 1的。只是多余的空间到底是第一个block还是第二个。
另外，即使按你的理解，你用你的算法试试下面这个例子
1 1 1 4 4 1 1 1 8 8 1 1
最优解应该是4 blocks 2 swaps
【在 m*****k 的大作中提到】
: 输入{1 1 1 4 4}
: 变成
: ｛4 4 1 1 1｝ why 0 swaps?
: 难道你的答案是{1 1 1 4 4}？
: block1 ［1 1 1 ］with 5 empty ， followed by block2［4 4］
: 显然不是答案，原题首先要求空间不浪费，其次要求最小move
|
j***m
发帖数: 6 | 48 session 3： 1. 一个bit的stream， 每次读取6个bit。转化成char。
这题有什么特别吗？不就是把每6个bit取出来变成char吗？还是我想简单了。。。。
8bytes
【在 Z**********4 的大作中提到】
: session 1一个class {int a, bool c, int b} 里面每个variable所占的空间都不同
: ，比如a,b是int 所以分别占4byte. bool的c只占1byte。还有其他变量，可能占8bytes
: 或者16bytes。都是2的次方就是。
: 问题是写一个程序让他们可以很好的被放到8byte为单位的block里面去然后空间不会浪
: 费。
: 比如如果是 就按照a, c, b的话它一共要占12个byte。因为当把a和c放到一个block的
: 时候就会浪费一些空间。
: 所以最好摆成a，b，c这样的话更合理。占9个byte。剩下的空间还可以放一些小的
: object。
: 其实这个就是用排序，然后从大的变量依次放进block。
|
m*****k
发帖数: 731 | 49 1 1 1 4 4 1 1 1 8 8 1 1
我的方法会返回
4 4 ，8， 8， 1 1 1 1 1 1 1 1
【在 g***s 的大作中提到】
: 看你如何定义不浪费
: 1 1 1 4 4 无论如何都要2 blocks，所以我认为的不浪费是1 1 1 4 4占用的空间是等
: 于4 4 1 1 1的。只是多余的空间到底是第一个block还是第二个。
: 另外，即使按你的理解，你用你的算法试试下面这个例子
: 1 1 1 4 4 1 1 1 8 8 1 1
: 最优解应该是4 blocks 2 swaps
|
y***n
发帖数: 1594 | 50 再看了一遍题，我觉得你是对的。
【在 m*****k 的大作中提到】
: 1 1 1 4 4 1 1 1 8 8 1 1
: 我的方法会返回
: 4 4 ，8， 8， 1 1 1 1 1 1 1 1
|
|
|
g***s
发帖数: 3811 | 51 但最优解应该是（swaps=2）
1 1 1 1 1 1 1 1 8 8 4 4
【在 m*****k 的大作中提到】
: 1 1 1 4 4 1 1 1 8 8 1 1
: 我的方法会返回
: 4 4 ，8， 8， 1 1 1 1 1 1 1 1
|
m*****k
发帖数: 731 | 52 我那个办法一次扫描，只处理一个当前block，的确不能得到1 1 1 1 1 1 1 1 8 8 4 4。
不过最优解应该是
1 1 1 1 1 1 1 1 4 4 8 8 吧
要得到这种解，得再改改，就是在未满的当前block后如果有满的block，别急着输出，
满的
block先存到一个fullfilled block list 中，然后incoming 的size能填到前边未满
block的，则填之，不能则开新的block，最后merge输出fullfilled block list 和当
前block（可满可不满）。
code麻烦不少，
需要类似如下的class
block{
int index;
List sizes;
}
【在 g***s 的大作中提到】
: 但最优解应该是（swaps=2）
: 1 1 1 1 1 1 1 1 8 8 4 4
|
g***s
发帖数: 3811 | 53 1 1 1 1 1 1 1 1 4 4 8 8需要交换的次数更多，1...8 8 4 4 只要两次交换。
你这改良也无法保证最少交换次数。
4。
★ 发自iPhone App: ChineseWeb 8.6
【在 m*****k 的大作中提到】
: 我那个办法一次扫描，只处理一个当前block，的确不能得到1 1 1 1 1 1 1 1 8 8 4 4。
: 不过最优解应该是
: 1 1 1 1 1 1 1 1 4 4 8 8 吧
: 要得到这种解，得再改改，就是在未满的当前block后如果有满的block，别急着输出，
: 满的
: block先存到一个fullfilled block list 中，然后incoming 的size能填到前边未满
: block的，则填之，不能则开新的block，最后merge输出fullfilled block list 和当
: 前block（可满可不满）。
: code麻烦不少，
: 需要类似如下的class
|
y***n
发帖数: 1594 | 54 大牛不要调我们口味了，上一个Code吧 ：-）
【在 g***s 的大作中提到】
: 1 1 1 1 1 1 1 1 4 4 8 8需要交换的次数更多，1...8 8 4 4 只要两次交换。
: 你这改良也无法保证最少交换次数。
:
: 4。
: ★ 发自iPhone App: ChineseWeb 8.6
|
g***s
发帖数: 3811 | 55 这题我不会
【在 y***n 的大作中提到】
: 大牛不要调我们口味了，上一个Code吧 ：-）
|
y***n
发帖数: 1594 | 56 好了，我不纠结了 ：-）
【在 g***s 的大作中提到】
: 这题我不会
|
m*****k
发帖数: 731 | 57 1 1 1 1 1 1 1 1 4 4 8 8需要交换的次数更多，1...8 8 4 4 只要两次交换。？？？？
1 1 1 1 1 1 1 1 4 4 8 8只需要把5个1插入第一block而已，
你这个还把4 4 都移动了，完全没必要。
又看了一下原帖，移动cost最小，我不认为swap次数最少＝移动cost最小
【在 g***s 的大作中提到】
: 1 1 1 1 1 1 1 1 4 4 8 8需要交换的次数更多，1...8 8 4 4 只要两次交换。
: 你这改良也无法保证最少交换次数。
:
: 4。
: ★ 发自iPhone App: ChineseWeb 8.6
|
g***s
发帖数: 3811 | 58 1 1 1 4 4 1 1 1 8 8 1 1
1 1 1 1 1 1 1 1 4 4 8 8 (at least 6 items are changed)
1 1 1 1 1 1 1 1 8 8 4 4 (only 4 items are changed, swap(4,11) swap(5,12))
no matter what's your understanding for the cost/swap, 1 1 1 1 1 1 1 1 8 8 4
4 should be better.
？？
【在 m*****k 的大作中提到】
: 1 1 1 1 1 1 1 1 4 4 8 8需要交换的次数更多，1...8 8 4 4 只要两次交换。？？？？
: 1 1 1 1 1 1 1 1 4 4 8 8只需要把5个1插入第一block而已，
: 你这个还把4 4 都移动了，完全没必要。
: 又看了一下原帖，移动cost最小，我不认为swap次数最少＝移动cost最小
|
m*****k
发帖数: 731 | 59 感觉你还是算swap，
其实从array idx 变化，
移动步数而言，这两个加起来一样多。
但就本题block分配而言，4 4所在的block没必要调到最后。
1 1 1 1 1 1 1 1 4 4 8 8 表示
［1 1 1 1 1 1 1 1］ ［ 4 4］ ［8 8］
1 1 1 1 1 1 1 1 8 8 4 4 表示
［1 1 1 1 1 1 1 1］ ［8 8］ ［4 4］
1 1 1 4 4 1 1 1 8 8 1 1
只需要把1都往第一个block填就行了，4 4 8 8不用动，
你觉得1 1 1 1 1 1 1 1］ ［8 8］ ［4 4］
比 ［1 1 1 1 1 1 1 1］ ［ 4 4］ ［8 8］ 更优么？
4
【在 g***s 的大作中提到】
: 1 1 1 4 4 1 1 1 8 8 1 1
: 1 1 1 1 1 1 1 1 4 4 8 8 (at least 6 items are changed)
: 1 1 1 1 1 1 1 1 8 8 4 4 (only 4 items are changed, swap(4,11) swap(5,12))
: no matter what's your understanding for the cost/swap, 1 1 1 1 1 1 1 1 8 8 4
: 4 should be better.
:
: ？？
|
g***s
发帖数: 3811 | 60 按照你的理解，
a1 a2 .... a11 12
1 1 1 4 4 1 1 1 8 8 1 1
先把a11 a12移到a3后面，再把a4 a5移到最后（或者移到a6后面），只需要4步。
按你说的需要5步("把5个1插入第一block而已“)。
再给你个例子
1 1 1 4 4 1
按照你的算法 [4 4] 构成一个full block， 你会输出 4 4 1 1 1 1 (2 moves at
least)
而正确的应该是 1 1 1 4 1 4 (1 move)
【在 m*****k 的大作中提到】
: 感觉你还是算swap，
: 其实从array idx 变化，
: 移动步数而言，这两个加起来一样多。
: 但就本题block分配而言，4 4所在的block没必要调到最后。
: 1 1 1 1 1 1 1 1 4 4 8 8 表示
: ［1 1 1 1 1 1 1 1］ ［ 4 4］ ［8 8］
: 1 1 1 1 1 1 1 1 8 8 4 4 表示
: ［1 1 1 1 1 1 1 1］ ［8 8］ ［4 4］
: 1 1 1 4 4 1 1 1 8 8 1 1
: 只需要把1都往第一个block填就行了，4 4 8 8不用动，
|
|
|
m*****k
发帖数: 731 | 61 你说的是移动几次，我说的是移动的距离总和，不纠结这个问题了。
>>1 1 1 4 4 1
我的算法的确只能返回4 4 1 1 1 1
1 1 1 4 1 4 这种解得要求全局优化，重组，我是想不出简洁的通用算法求出来了，求
各位大神不吝指教，呵呵。 |
a**a
发帖数: 316 | 62 我觉得的你的理解是正确的。题目所说的应该是bit 交换，而不是整数交换。
【在 m*****k 的大作中提到】
: 你说的是移动几次，我说的是移动的距离总和，不纠结这个问题了。
: >>1 1 1 4 4 1
: 我的算法的确只能返回4 4 1 1 1 1
: 1 1 1 4 1 4 这种解得要求全局优化，重组，我是想不出简洁的通用算法求出来了，求
: 各位大神不吝指教，呵呵。
|
