p*a
发帖数: 7676 | 1 问题的关键是，病毒不听党的话也不听总统的话。
一旦放出去，放的人自己就控制不了了。机器就不一样，不管什么机器，它只能按人设
定的程序执行，包括所谓AI也是。 |
|
c****e
发帖数: 9482 | 2 首页是水版原帖的置顶
有没有看到除了反证法之外的解法啊？
我看见有个人的回帖说： 我设变量，花10分钟把三角定律，正弦定律，余弦定律通通
输入到mathmatica解方程， 然后回车！ |
|
q****2
发帖数: 667 | 3 如果只是email事件，这可以算成，没想那么多，大意了。其实大多数人都用公司的
email，电话，虽然公司设一道一道防火墙。说是事，也是事，说不是事也不是事。
trump对穷人不nice，心眼不善，不喜欢。 |
|
发帖数: 1 | 4 这两日，天价片酬问题重回舆论焦点。
8月11日，爱奇艺、优酷、腾讯视频、正午阳光、华策影视、柠萌影业、慈文传媒、耀
客传媒、新丽传媒联手发布《关于抑制不合理片酬，抵制行业不正之风的联合声明》。
《声明》称，三家视频网站联合六大影视制作公司即日起严格执行有关部门每部电影、
电视剧、网络视听节目全部演员、嘉宾的总片酬不得超过制作总成本的40%，主要演员
片酬不得超过总片酬的70%的最高片酬限额制度；并对不合理的演员片酬进行控制，三
家视频网站和六大影视制作公司采购或制作的所有影视剧，单个演员的单集片酬（含税
）不得超过100万元人民币，其总片酬（含税）最高不得超过5000万元人民币。联合声
明还表示，共同抵制偷逃税，“阴阳合同”等违法行为，共同倡导廉洁之风、弘扬浩然
正气。
8月12日，以华谊兄弟为会长单位，汇集了博纳影视、横店影视、乐视花儿影视、唐德
影视等400余家影视企业的横店影视产业协会也发表了《关于“加强行业自律、规范行
业秩序、促进影视精品创作”的倡议》，倡议召全行业一同遏制天价片酬、“阴阳合同
”、偷逃税等问题，共同规范行业秩序，加强行业自律，促进影视行业创作精品化。
舆论对... 阅读全帖 |
|
l***y
发帖数: 1166 | 5 证明：假设素数是有限的，假设素数只有有限的n个，最大的一个素数是p，
设q为所有素数之积加上1，那么，q=（ 2×3×5×…×p ）+1不是素数，
那么，
1.q可以被2、3、…、p中的数整除，
而q被这2、3、…、p中任意一个整除都会余1，与之矛盾．
或者
2.q可以被非2、3、…、p中的其它素数x整除，同样与假设矛盾
所以，素数是无限的． |
|
W***J
发帖数: 18 | 6 我有PAY AMAZON的MERCHANT FEE。我说的不是设置自己SHIPPING POLICY.我说的是在设
置了自己的SHIPPING POLICY之后，另外对自己某几个PRODUCT设置特殊的SHIPPING
RATE. |
|
发帖数: 1 | 7 40 人赞同了该回答
属于极高收入人群，算富人群体了。
资产百亿RMB以上算巨富（超级富豪），资产十亿RMB以上算大富。
资产一亿对应稳定年收入百万以上，算富翁（富婆）了。
不要小看这个“稳定”二字，假如深圳一个50平铺面月租1万，意味着他至少持有8个铺
面，单价不低于12万/平；一个100平套房月租6000，意味着他至少持有16套商品房 ，
深圳均价五万+；如果他是纯利3%的工厂主，意味着他的年营收不低于3300万；假如他
是打工族，起码是BAT的高级总监或创收部门的总监，或者中小型互联网企业、上市公
司的头头脑脑。以上是达成题设的最低资产/职务条件。
so，达到这样条件的人，在你的身边有几个？即便在深圳，这样的人也不常见呢。 |
|
b********e
发帖数: 20 | 8 = = 我觉得这个男的跟那些结婚以后对方生大病面临选择的是不一样的。他结婚之前他
老婆可是什么都说明白了，他贪图美貌不顾一切娶了。这种行为我觉得就意味要对他老
婆的病情负责了。现在她老婆真的复发了，照顾时间长了，发现不能有孩子了，他开始
后悔开始jjww，最不可理喻的是竟然开始抱怨自己父母亲当初没提醒他，开始怀疑这是
老婆父母给他设的圈套。
当初他把一个漂亮的公主娶回家的时候怎么就不说婚姻草率了？现在来说，见过没担当
的，没见过没担当还这么ws的。 |
|
m********n
发帖数: 4570 | 9 我纯粹是进来怀疑你的题设的
随口胡驺无图无真相阿 |
|
m********n
发帖数: 4570 | 10 你阅读障碍怎么得我题设里面有狐臭吗？
你全家都狐臭 |
|
g*******y
发帖数: 1930 | 11 来自主题: JobHunting版 - 问一道老题 将原来7台机子上存的keys拿来rehashing一次，按照新的hash值移动到新的server。
考虑到data比较大，移动会有很大cost，可以在新server相应的储存该key的地方，设一个forward的标签，把fetch data的request forward到旧server上 |
|
H*M
发帖数: 1268 | 12 来自主题: JobHunting版 - 问一道老题 第一个方案肯定不行的，如果hash function没规律的话，移动data复杂度太大，最坏的
N太机器全要移动。
forward idea不错。不过可能会要forward好多层。每变一次hashfunction就要forward
。
设一个forward的标签，把fetch data的request forward到旧server上 |
|
n******r
发帖数: 1247 | 13 可以的
先对array求和，找出两个missing number的和,设为M
则必然一个小于M/2,一个大于M/2
对array里所有
对array里所有>M/2的数xor，再和{floor[M/2]+1,...,N}xor得到第二个数 |
|
b***e
发帖数: 1419 | 14 有重复也没关系. 两个hash, 一个存s2的inverted index, 一个存现在已经找到的. 设
两个指针i, j来traverse s1(j >= i), 多退(i++)少补(j++), 没找到就重新来过. 唯一
tricky的地方就是如果j++多扫进来一个字母, 假设是a, 那么i++要一直repeat直到把上一个a吐出
来. 沿路经过都要吐出去. |
|
n******r
发帖数: 1247 | 15 设X为10分钟的车和前一班5分钟的车之间的间隔，没有额外信息情况下，假定X～U[0,5]
E[等待时间|X]=(X/10)*(5-X)+((5-X)/10)*5+(1/2)*X
E[等待时间]=积分 (1/5)*E[平均等待时间|X],0<=X<=5
35/12
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
从这里开始就应该积分 |
|
k***e
发帖数: 556 | 16 提一点，为什么要设三个变量
define:
f(n): the # of abc array with length n and contains no ab
g(n): # of length n, begin with a and no ab
then f(n)=g(n）＋ 2f(n-1)
g(n)=g(n-1)+f(n-2)
第二个式子直接可以得到g(n)=sum(f(1)...f(n-2)) + 2
代入前面，用f(n) f(n-1)差一下就可以得到
f(n)=3f(n-1)-f(n-2) |
|
m*****f
发帖数: 1243 | 17 假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法
设最大的那个数最终位置为x, 显然b<=x<=a, 得
f(a,b) = f(a-1, b-1) (x=a的情况) + f(a-2, b-1)*(a-1) (x=a-1的情况, a位置可放
任一数) + f(a-3, b-1)*(a-1)*(a-2) (x=a-2, a, a-1位置可放任意数) ....
until...f(b-1, b-1) * (a-1) * (a-2) ...(a-b)
声明一个axb的数组, 显然
f(*,1) = 1
f(a, b) = 1 if a = b
f(a, b) = 0 if a < b
然后填满这个数组, 我刚才懒得写完, 现在就写完罢
当然, 求更好的方法... |
|
e***l
发帖数: 710 | 18 说说我的想法，设g(N,L,R)为最终所求，那么根据最高的block的位置i=(1...N)，有N
个情况。于是
g(N,L,R)=Σ C(N-1, i-1) * f(i-1,L-1) * f(N-i,R-1)
i=1,2...N
其中第一项C(n,r)是组合数记号，从n个里面选r个的选法，
第二项f(n,a)表示只考虑最高的左边那些block，用i-1个block摆出从左看，有L-1个
block可见的摆法。
第三项是从右看的情况，函数是同一个（因为对称）。
接下来再考虑f，同样根据最高的block的位置，f可以递归求得
f(N,L) = Σ f(i-1,L-1)
i=1,2...N
再有几个初始值就可以求出g，但是直接的解析式似乎很麻烦。。。
测试了几个例子基本正确，大家看看正确吗？
代码：
#include "stdafx.h"
//求x的阶乘
int factorial(int x){
if(x==0) return 1;
int r=1;
for(int i=1;i<=x;i++)
r=r*i;
return r;
}
//求组 |
|
B*****t
发帖数: 335 | 19 题目的特点：
1. 只要C出手，必有一人被干掉，而且C一定会对命中率高的人下手(先B后A，如果C一
直活着的话）
2. B没有其他选择的可能，他一定去打C，因为轮到C的时候，他必死。
3. A处于最有利的位置，3个原因：a)他有有限选择权；b)C一定要先把B干掉后才去打A
. c)B会先打C而不是A。
A有三种策略：先打B， 先打C， 开空枪。
这里只讨论A开空枪的情况，其他类似。
Pr(C存活的概率)=Pr(B cannot kill C)*Pr(A cannot kill C) = 0.35
如果C被B打死（概率0.5）AB之间死磕，轮到A出手，设A打死B的概率为x
x = 0.3 + 0.7*0.5*x ==> x=0.3/0.65
如果C没有被B打死（概率0.5），C打死B， 然手轮到A出手，他只有一次机会打死C，概
率为0.5*0.3
所以A活下来的概率为0.5*0.3/0.65+0.5*0.3=0.381
B活下来的概率为1-.35-.381 |
|
j**l
发帖数: 2911 | 20 老中的二倍珍珠解法，用百度搜索中文都可找到的，而且有图。
个人觉得还是老印的解法巧妙，下面具体用例子说说。
假如链表为A->B->C->D->E
A的random指向E, B的random指向D, C的random指向自身C, D和E的random都为NULL。
第一步，平凡复制原始链表，不考虑random指针（全部设为NULL)
这样得到A'->B'->C'->D'->E'，所有random都为NULL
第二步，建立连接
让A的random指向A', B的random指向B', ..., E的random指向E', 成为梯子的单向辐条。
让A'的next指向E, B'的next指向D, C'的next指向C, D'和E'的next都为NULL， 也就是
用复制链表的next保存原始链表的原始random
A->B->C->D->E
| | | | |
A' B' C' D' E'
第三步，给A', B', C', D', E'的空random指针赋值
这样A'的random指向E', B'的random指向D', C'的random指向自身C', D'和E'的random
都 |
|
r********e
发帖数: 27 | 21 弱问一下，xyz& operator+(int m) “const”， 最后那个const表示什么意思？是不
是说first
operand is const?
const xyz& operator+(const xyz &rhs) “const”， 需要这个设成const吗?
谢了 |
|
g****n
发帖数: 431 | 22 我想到一个办法：
假设从A数组中找一个数，使其能整除B数组中的一个数。先把B排序，从小到大。遍历A
，对于A中的每一
个数a，设n=B[0]/a, m=B[MAX]/a。这样如果B中有一个数能被a整除，除完以后的倍数
一定在[n,
m]之间。现在遍历i = n->m，在B中二分查找a*i即可。
时间复杂度是|A|*K*Log(|B|), K为B中最大元素除以A中最小元素得到的商。 |
|
f*********g
发帖数: 207 | 23 想到一个办法，类似randix sort。假设A中最大，最小数分别为Amax,Amin,将A hash
到size为Amax-Amin＋1的数组,设为H,H[i]=1 if Amin+i在A中，否则为零。然后对B中
每一个数，依次检验H[([Amin/Bi]，[Amin/Bi]+1,....[Amax/Bi])*Bi]是否为1。这样
假设A,B中的数组均值差不多，计算量为O(NA+NB) |
|
c********4
发帖数: 18 | 24 通俗的描述是：给你N种硬币，每种硬币的面额D[i]也给你。规定每种硬币可以取任意
个（可以是0个），问
最少用几枚硬币可以组成面额Y。这个题目可以用动态规划，设一个数组ans[i][j],表
示用0到i种硬
币，拼出j面额所需要的最小数量。然后递推式为：
ans[i][j] = Min {n + ans[i-1][j-n*D[i]]} (0 <= n <= j/D[i])
意思是：对于第i种硬币，遍历可以取的个数n，然后看剩下的面额j-n*D[i]最少可以用
多少枚0到(i-
1)种硬币拼出来。 |
|
h**6
发帖数: 4160 | 25 只求个数可以用DP，输出全部组合则还是需要递归。
在一个可重复集合中，有n个不同元素a1,a2,...,an，分别出现了x1,x2,...,xn次，
现要从该集合中取出k个元素的组合，问有多少种取法，并输出每一种取法。
设f(i, j)为前i个不同元素取出j个的取法，则f(n, m)为全部取法个数。
f(i, j) = sum(k = 0 to min(xi, j, m)){f(i-1, j-k)} |
|
m**q
发帖数: 189 | 26 这样行不行？
因为目的是想让自己多得分，对方少得分，既然每人取n/2个，
相当于想办法使得自己得分比对方得分多得越多越好。
设f(i,j)表示范围i...j中所得获得的最大分差(自己总分 - 对方总分）
f(i,j) = max { f(i+1,j-1) + Vi - Vj,
f(i+2,j) + Vi - Vi+1,
f(i+1,j-1) + Vj - Vi,
f(i,j-2) + Vj - Vj-1 }
我觉得这个的最优解应该和你的是一样的。
2))}+Vj } |
|
k*p
发帖数: 1526 | 27 想到一个heuristic的算法
设数组为a，定义一个vector b，一个计数器n记录当前找到的出现了的数字的个数
while(n<100) {
if(!b[a[i]]) {
b[a[i]]==true;
n++;
}
i++;
}
当n==100，说明除了那个没有的，其余都出现了，scan可以提前结束
10000个数只有101个可能，如果平均分布，很快就能找到 |
|
i**********e
发帖数: 1145 | 28 在字符都排好序的前提下，那么重复的字符都必定相连在一起。
给个例子：
aaabcc
进入递归，首先看到第一个的字符是 'a'。每一次标记位置用过，然后再进入下个
level 的递归。下一个 level 的时候，位置 0 的 'a' 已用过，所以我们跳到下一个
'a'，设位置 1 为用过，以此类推。
当递归回溯的时候，位置又被还原为没用过，照理应该跳到下一个位置的字符。但如果
下一个字符也是重复的字符，这样会产生重复的组合。例如，位置 0 的 'a'下一个字符
也是 'a'，这肯定是个重复的组合。
由于字符都排好序，只要跳到下一个不重复的字符就能跳过所有重复的组合。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
g***s
发帖数: 3811 | 29 这个好像是一道当年的acm/icpc试题，不过当时没去做。
给一个所有x,y没有相同值的基本思路：
把所有的矩形的左边和右边按x排序（），总共有2n条边。
初始话一个 hashmap A (float->int) 用来记录：对于记录当前x值下，对于点y，有多
少个重复。
同时，需要保存一个当前排好序的所有y值的队列R
从左向右扫描这2n条边。
对于左边，
× 检查R里面的点，被这条边覆盖。对于这些点，更改A里面的值 ++1
× 加入到边的两点的y值加入到A和R里面，A里面的值设为1
对于右边：
× 检查R里面的点，被这条边覆盖。对于这些点，更改A里面的值 --1
× 从A和R删除这两点。
在这个过程中，A里面出现的最大值就是最大overlapping最多的数目
最坏的可能性是O(n^2). |
|
m**q
发帖数: 189 | 30 假设每个任务开始结束为start[i], end[i],对应的权值为a[i],
先把数组按start[i]排序，设从i...n的工作中，总的最大权值为f[i],则：
f[i] = max { f[i+1], a[i] + f[k]: k是i之后和i不冲突的第一个元素 }
排序O(nlgn),遍历a[]数组O（n),对每个元素i用二分法找对应的k，O(lgn),
总复杂度为O(nlgn)。
这个方法对不？
O( |
|
h*********n
发帖数: 11319 | 31 能不能这样
首先找到范围内最小的heavy数，设为current
tencurrent = current
while tencurrent没有跨越尾数为00的边界，
tencurrent每次+9, 然后算tencurrent数到最近的个位为9的数之间的距离（包括俩端
点）
如果tenrtcurrent跨越了尾数为00边界，那么
hundredcurrent = current, 然后
while hundredcurrent没有跨越尾数为000的边界，
hundred每次+99，重复前一个循环
如果hundredtcurrent跨越了尾数为000边界，那么
thousandcurrent = current, 然后
while hundredcurrent没有跨越尾数为0000的边界，
hundred每次+999，重复前两个循环
。。。。。。
就这么一层层包下去直到边界的量级大于给出的范围
写起来好像挺复杂，真面试的时候我肯定得debug半天。。。 |
|
i**********e
发帖数: 1145 | 32 来自主题: JobHunting版 - 一道G家题 恩，不好意思
我仔细想了想，似乎 invariant 欠缺了一些重要的东西
用lz的例子:
1 2 3 5 6
后边贴一个 +infinity，让我们的 invariant 更简洁：
1 2 3 5 6 +INF
设 lo = 0, hi = n (5) (但实际上永远不会 access A[hi])
然后再折半查找：
invariant 的条件要改一改：
if (M-L >= A[M] - A[L])
L = M;
else
H = M;
终止条件比较 tricky，就是 H - L <= 1 的时候。 |
|
P**********c
发帖数: 3417 | 33 能解释下
p2 = (void**) (((size_t)(p1)+offset) & ~(alignment-1))
这句吗？前面的code基本上是说申请大小是
required_byes+offset大小的memory, p1指向这块memory.
我能理解这句把p2 转化成了alignment的倍数。保留了高位，把alignment之后的bit都设成0。但是这样p2指向的还是required_bytes大小的memory吗？
感觉p1+offset指向的才是required_bytes大小的memory啊。&之后还是吗？
还有p2[-1]，这种情况下是p2前面多少byte？ |
|
c****p
发帖数: 6474 | 34 &(p2[-1])=p2 - sizeof(void *);
都设成0。但是这样p2指向的还是required_bytes大小的memory吗？ |
|
M**A
发帖数: 78 | 35 总结各位评论，欢迎拍砖。
题目
align_malloc(1000, 128) will return a memory address that is a multiple of
128 and that points to memory of size 1000 bytes.
aligned_free() will free memory allocated by align_malloc.
解答
int offset = alignment-1+sizeof(void*);//分配空间给a memory address that is
a multiple of 128
这个offset的空间用来存放memory address，就是*p1 that points to memory of
size 1000 bytes
p1 = (void*)malloc(required_bytes+offset)) //分配空间给memory of size 1000
bytes+memory address that is a multiple of
128， required_byt... 阅读全帖 |
|
g*****k
发帖数: 623 | 36 anysize_reader有一个静态buffer和一个静态index指向buffer起始位置。
当buffer中数据完全处理完毕，就调用block_reader(buffer)并且设index=0
这样即便有数据残留在buffer中，下次调用anysize_reader也是先处理buffer中的 |
|
P**********c
发帖数: 3417 | 37 这个好像不太对，上来就把x[i]设成－1, 后面应该判断是不是回到原位置了吧。 |
|
r*******g
发帖数: 1335 | 38 贪心不一定最优吧，假设先weight排序好，我们只看height，假设如下的hight
1,2,3,6,5,5.5,5.8
这个用贪心怎么求？明显结果是可选6个，但是如果简单把5设为unfit然后重新开始就
有问题。 |
|
a**********2
发帖数: 340 | 39 来自主题: JobHunting版 - 问个算法题 画一颗后缀树，建立过程中存在的节点就将这个节点加一，不存在就创建并设为1，最
后找出最大计数路径。
其实很好理解，后缀树是字符串所有后缀的字串的集合而成的，计数就相当于统计字串
的出现频率
连续的话用就不知道怎么弄了 |
|
i**********e
发帖数: 1145 | 40 来自主题: JobHunting版 - 问个算法题 Recursion + caching，可以转换成 bottom-up DP.
0000. F(0) = 0
0001. F(1) = 1
0010. F(2) = 2
0011. F(3) = 4
0100. F(4) = 5
0101. F(5) = 7
0110. F(6) = 9
0111. F(7) = 12 = (7-3) + 2*F(3) = 4 + 2*4 = 12
1000. F(8) = 13
...
1111. F(15) = (15-7) + 2*F(7) = 8 + 2*12 = 32
假设要找的是 F(N)，那么首先设 k = ceil( log(N+1) )
建立表从 F(2^i - 1), i = 0 .. k , O(log N) 时间
然后计算 F(N) = N-(2^k - 1) + F(2^k - 1) |
|
l*y
发帖数: 21010 | 41 按三路归并的办法，把三个数组并成一个，在这个过程中就找到了所需triplet。
首先设minDistance为MAXINT。归并的过程中，每次选三个数组各自最小元素的最小的
拿出来放入归并好的序列。假设某时刻三个数组的最小元素分别为ai,bj,ck，且ai最小
，我们记录max(|ai-bj|,|ai-ck|)的值。这个值就是在最后归并好的序列中，以ai为最
小数的triplet的Distance（可用反证法证明，因为bj和ck分别是另外两个数组中比ai
大的最小的数，所以再取更大的数Distance一定更大），记为curDistance，然后更新
minDistance如果比它更小（并且记住该minDistance对应的triplet是ai,bj,ck）。
完成归并后，我们就得到了minDistance和所需的那个triplet。
distance |
|
m**a
发帖数: 139 | 42 假设有n个数组。 每个数组设一个pointer 指向开始。计算n个书中的最小距离（最大
值减最小值），如果比global的小，更新global。向后指向n个数中最小的那个的
pointer。重复知道所有pointer都指向数组末。 |
|
z********c
发帖数: 72 | 43 我的想法
F[i][j]为S的substring最后取得位置是i，T的sub sequence最后取得位置是j，匹配的
方案数
1. S[i]!=T[j]，则F[i][j]=0
2. S[i]==T[j]，则
a. i和j分别都是各自的第一个字符，方案数1
b. i和j不是第一个字符，那么方案数F[i - 1][k] k < j
so
F[i][j] = 1 + sum (F[i - 1][1] + F[i - 1][2] .. F[i][j - 1])
设
S[i][j] = F[i][1] + F[i][2] + ... F[i][j]
所以
F[i][j] = 1 + S[i - 1][j - 1]
S[i][j] = S[i][j - 1] + F[i][j]
answer = sigma (F[i][j]), i <= len (s), j <= len(t) |
|
m******6
发帖数: 82 | 44 1.找到最小的>0的数，然后设为pivot
2.然后做一次in-place partition
不知道对不对
1) |
|
w****o
发帖数: 2260 | 45 yishan,
我觉得你的方法不行。可能是我没有太理解。
举个简单的例子，
比如一个数组， 5 5 5
第一遍：
第一个5出现的时候，你把 bitflag[5] = 1
第二个5出现的时候，bitflag[5]仍是1, 同时数组变成了 5 -5 5
第三个5出现的时候，bitflag[5]仍是1, 同时数组变成了 5 -5 -5
到这里我的理解是对的吗？
可是你的第二遍，我就没有弄明白了。
第二遍：
遇到5，bitflag[5]是1，数组不做改动，仍是5 -5 -5
然后遇到-5, 怎么办？设bitflag[5]=0?,数组变成 5 5 -5？
然后遇到-5,怎么办？
你什么时候判断5是出现了几次？
谢谢！ |
|
w****o
发帖数: 2260 | 46 yishan,
我觉得你的方法不行。可能是我没有太理解。
举个简单的例子，
比如一个数组， 5 5 5
第一遍：
第一个5出现的时候，你把 bitflag[5] = 1
第二个5出现的时候，bitflag[5]仍是1, 同时数组变成了 5 -5 5
第三个5出现的时候，bitflag[5]仍是1, 同时数组变成了 5 -5 -5
到这里我的理解是对的吗？
可是你的第二遍，我就没有弄明白了。
第二遍：
遇到5，bitflag[5]是1，数组不做改动，仍是5 -5 -5
然后遇到-5, 怎么办？设bitflag[5]=0?,数组变成 5 5 -5？
然后遇到-5,怎么办？
你什么时候判断5是出现了几次？
谢谢！ |
|
t********e
发帖数: 344 | 47 我觉得明明有solution啊，就用quick sort的思想，大家看看对不对，还是我理解题目
有问题？
先扫一遍数组A[n]，知道有多少负数，假设有m个
把m视为pivot的位置，设两个指针，一个初始指向A[0], 另一个初始指向A[m]:
i=0, j=m
if A[i]>0 and A[j]<0, swap them
if A[i]<0,i++
if A[j]>0,j++
直到i=m-1 或j = n-1
这样就好了是O(n) time, O(1)space
对挖？ |
|
g***s
发帖数: 3811 | 48 任何一个字符串，只考虑它的第一个后最后一个字母。
设p(a,b) 为第一个字母是a，最后一个字母是b的字符串数目。
这样，扫描一遍就可以算出所有的p。p的空间是26×26.
后面怎么处理都不难了。 |
|
|
m*****k
发帖数: 731 | 50 离散数学书标准算法， ：－）
先每位排序，从最小开始，从左到右，
设当前处理位 ＝ 最后一位；
A：从当前处理位开始，向左扫描，找到数值比它小的一位i，交换，i 后边所有位排序
，从小到大，从左到右，重设当前处理位 ＝ 最后一位；若找不到数值比它小的，当前
处理位左移一位， go to A; 如果无法左移，done。
example：
123,
当前处理位 ＝ 最后一位， 指向3, 向左扫描，找到比它小的一位， 值是2，交换，得
132, 排序3后的所有位，
得132,
当前处理位重设为最后一位，
指向2,向左扫描，找到比它小的一位， 值是1,交换得231,排序2后的所有位,得213,
当前处理位重设为最后一位，
指向3,向左扫描，找到比它小的一位，值是1, 交换得231，排序3后的所有位,仍得231,
当前处理位重设为最后一位，
指向1, 向左扫描，无法找到比它小的一位，当前处理位 左移一位，指向3,
3,向左扫描，找到比它小的一位，值是2, 交换得321，排序3后的所有位，得312,
当前处理位重设为最后一位，
指向2，向左扫描，找到比它小的一位， 值是1,交换得321,排序2后的... 阅读全帖 |
|
