给你一个数组A[1..n],请你在O(n)的时间里构造一个新的数组B[1..n],使得B[i]=A[1]*A[2]*...*A[n]/A[i]。不能使用除法运算。
问题的关键在于不能使用除法运算。。。
只能用乘法。。
B[i]=A[1]*A[2]*...*A[n]/A[i]=A[1]*A[2]*...*A[i-1]*A[i+1]*...*A[n]
分解开来,也就是分别计算
A[1]*A[2]*...*A[i-1]
A[i+1]*...*A[n]
然后再乘了。
设置两个缓存数组M和N,一个保存前n项乘积,一个保存后n项乘积
M:A[1],A[1]*A[2],A[1]*A[2]*A[3],......,A[1]*..*A[n]
N:A[1]*...*A[n],.....,A[n-1],A[n]
计算M时间复杂度为O(n),计算N时间复杂度为O(n),计算B时间复杂度为O(n)
三个加起来O(3n)
符合要求么?
在一个重男轻女的国家里,每个家庭都想生男孩,如果他们生的孩子是女孩,就再生一个,直到生下的是男孩为止。这样的国家,男女比例会是多少?
倘若生男生女概率均等,则为1
若不等,假设生女概率为a, 则最后男女比例概率为:(1-a)/a
假设n个家庭
男孩数量为: n
女孩数量为: n*a+n*a*a+n*a*a*a+........=n*a/(1-a)
提取单链表倒数(注意是倒数)第m个元素,只允许遍历链表一次。
想了许久都是要用到两次遍历。。。看答案才晓得的。。。用两个指针。。。。间隔为m即可
如果你看到钟的时间是3:15,那一刻时针和分针的夹角是多少?(肯定不是0度!)
(360/12)/(60/15)=7.5
怎么才能识别出电脑的内存堆栈是向上溢出还是向下溢出?
定义两个局部变量,比较其地址大小。。。
对现在的Stack(栈)数据结构进行改进,加一个min()功能,使之能在常数,即O(1),时间内给出栈中的最小值。可对push()和pop()函数进行修改,但要求其时间复杂度都只能是O(1)。
这个好麻烦啊。
如果设置一个辅助元素min,每次push的时候只需要与min比较,重新设置就可以了
但是只能一次正确
当pop一次以后就不行了
如果要做到min和pop时间复杂度都为1,必须要有栈内元素的按大小排序后的次序信息
但又要求push时间复杂度为1,也不能在插入的时候进行排序
晕死
猜测方向应该是:建立辅助空间,在插入的时候以巧妙的方式直接确定插入元素在整个栈内的次序
但是,还是不晓得 咋 的 做
故事:5个海盗抢到了100颗宝石,每一颗都一样的大小和价值连城。他们决定这么分:
1. 抽签决定自己的号码(1,2,3,4,5)
2. 首先,由1号提出分配方案,然后大家5人进行表决,当且仅当超过半数的人同意时,按照他的提案进行分配,否则将被扔入大海喂鲨鱼。
3. 如果1号死后,再由2号提出分配方案,然后大家4人进行表决,当且仅当超过半数的人同意时,按照他的提案进行分配,否则将被扔入大海喂鲨鱼。
4. 以次类推
条件: 每个海盗都是很聪明的人,都能很理智的判断得失,从而做出选择。
问题:第一个海盗提出怎样的分配方案才能够使自己的收益最大化?
这个,曾经做过。没做出来。看答案才发现出题的人真tm有才!
给你一个长度为N的链表。N很大,但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个,且它们是完全随机的(出现概率均等)。
建立长度为k的指针数组;将遍历途中的前k个元素的地址放入这个缓冲区;然后在后面的遍历中,依次以一定的概率来替换缓冲区里面的数据;如果按这个思路,后面的问题就是:怎么确定替换元素的位置?以怎样的概率替换?(目的就是如何确保等概率)
当遍历到第 M 个元素时,以 K/M 的概率 用第M个元素指针 替换缓冲区的一个数据(1/K概率从中选择一个)
可行否?
推导了一下,从 K 到 K+1 可行
但从K+1到K+2就不行了
第K+1个元素的被选中的概率为:(K-1)/(K+1), 而不是K/(K+2),晕死
再想想先
分享到:
相关推荐
视图是一个虚拟的表,它从一个或多个表中检索数据。视图可以简化复杂的查询,并提供了一种方便的方式来组织和管理数据。 什么是备份? 备份是指将数据库的数据和结构复制到另一个位置或存储设备中,以防止数据丢失...
这是本人自己用c语言写的好几个字符串处理的面试题目源代码。觉得应该会很有用的,因为本人正在准备复习笔试题目~~。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。...
几个T-Sql 的面试题几个T-Sql 的面试题几个T-Sql 的面试题几个T-Sql 的面试题几个T-Sql 的面试题几个T-Sql 的面试题几个T-Sql 的面试题几个T-Sql 的面试题几个T-Sql 的面试题几个T-Sql 的面试题几个T-Sql 的面试题几...
以后会慢慢把Java相关的面试题、计算机网络等都加进来,其实这不仅仅是一份面试题,更是一份面试参考,让你熟悉面试题各种提问情况,当然,项目部分,就只能看自己了,毕竟每个人简历、实习、项目等都不一样。面试题...
几个常见的C语言面试题分析 几个常见的C语言面试题分析
几个SQL面试题及答案.sql
几个公司的Java面试试题:几个公司的Java面试试题:
│ Java面试题04.java中int占几个字节.mp4 │ Java面试题05.java面向对象的特征.mp4 │ Java面试题06.装箱和拆箱.mp4 │ Java面试题07.==和equals的区别.mp4 │ Java面试题08.String.mp4 │ Java面试题09.讲一下java...
Java EJB 经典面试题 面试时被问过几个
java面试题集,看你能回答出几个 java面试题集,看你能回答出几个
2018最新最全java高级工程师面试题,2018最新最全java高级工程师面试题2018最新最全java高级工程师面试题,2018最新最全java高级工程师面试题 十几个文档
java工程师面试题大全-100%公司笔试题你都能碰到几个
软件测试面试题 1.软件测试分哪两种方法?分别适合什么情况?
java(软件)工程师面试题大全-100%公司笔试题你都能碰到几个 达内笔试题集答案集.pdf 面试题集(全).pdf 达内笔试题集答案集001.pdf 华_为Java笔试题.txt 某公司java笔试题.(超难).txt Sql.txt java面试题集 .doc 等等...
我们毕业生如何在面试前对以上几个方面多加了解和练习,一定会在面试中取得良好的效果,在求职中获得成功 ************************** end 1、面向对象的特征有哪些方面 1.抽象:抽象就是忽略一个主题中与...
ava工程师面试题大全-100%公司笔试题你都能碰到几个.docx Java开发工程师上机笔试题.docx Java开发求职面试题.docx Java开发笔试题.docx Java数据结构类面试题.docx Java数据结构题.docx Java笔试面试宝典.docx Java...
ssh三大框架的经典面试题,一般逃不过这几个问题
几个常见的Java基础面试题总结。有答案。
LINUX内核经典面试题 ,20) 如何加载、卸载一个模块? 21) 模块和应用程序分别运行在什么空间? 22) Linux中的浮点运算由应用程序实现还是内核实现? 23) 模块程序能否使用可链接的库函数? 24) TLB中缓存的是什么...
│ (7)如果你觉得你够牛就回答这几个问题.txt │ (8)以上文档中的明显错误.txt │ c,c++笔试.txt │ CC++笔试题系列.txt │ IT职场中外企面试最爱提的问题TOP10 .txt │ memset.memmove.strcmp.txt │ TC使用.txt │...