帮我看一下用折半法在一个已经排好序的数组中,从键盘上输入某数x,查找x是否在数组中的下标#includevoid
main( ){int a[10]={1,2,3,4,6,7,9,10,11,15}; int low,high,mid,i,x; scanf("%d", &x ); for(low=0,high=10-1;;)
{mid=(low+high)/2;
if(a[mid]==x) {printf("the number's position is %d\n",mid+1); }
if(x!=a[i]) { printf("Not found\n");;}
if(a[mid]x)
high=mid-1;}}
#includevoid main( ){int a[10]={1,2,3,4,6,7,9,10,11,15};int low=1,high=10,mid,x;int i=0;printf("Input search number:");scanf("%d",&x );while(low
为您推荐：
其他类似问题
扫描下载二维码小站会根据您的关注，为您发现更多，
看到喜欢的小站就马上关注吧！
下一站，你会遇见谁的梦想？
【程序员十大谎言】1.我以后给代码加注释。2.这是临时办法发布时不会这样写。3.已经开发完只剩几个小问题。4.开发：需要10天。老板：5天能完吗？开发：可以！5.TODO。6.在我机器上是好的。7.这不需要测试肯定是好的！8.以前就有这问题。9.只需改一行代码不会影响其它程序。10.这是硬件问题跟软件无关。
找工作的注意了：关于三方，关于违约，关于赔偿金~~~（很详细）
　　一、了解三方协议
　　网友：三方都有哪三方呢？　　专家：你好，三方协议是用人单位、毕业生和学校签署的标准协议，在毕业前签署，是毕业派遣的依据。毕业派遣后，凭报到证与用人单位签订劳动合同。　　网友：小企业需要签订三方协议吗？　　专家：你好，不论什么单位，只要毕业过去报到，都需要签三方协议。　　网友：请问什么是干部身份？干部身份有什么用？谢谢！　　专家：你好，保留干部身份对于你将来考公务员或调档等可能会有帮助，可以找一家单位或者人才市场签三方协议，每年交一定托管费，一年以后办理转正定级即可。　　网友：三方协议下来之前与公司签的双方协议书有法律效果吗？或者说对公司和个人有没有一定约束力？　　专家：就业协议、聘用协议，是双方当事人自愿、真实意思的表示，双方都应按照协议履行。专家提醒：在签就业协议时，对待附加协议(如聘用协议等)更要认真谨慎，因为这样的协议法律效力几乎等同于劳动合同，毕业生一定要仔细斟酌后再签，切不可草率，更不能轻易违约。　　你好，尽管offer不是三方协议，但它是你和公司之间签署的一个的合同，所以，对你和公司都是有约束力的。如果在offer中约定了违约金，那么，当你不去时，就算违约，仍然要交违约金，这点一定要注意。　　网友：老师，请问，三方协议到底有没有法律效力？如果和用人单位签了三方协议，用人单位又不想用这个劳动者了，这种情况该怎么办？？　　专家：你好，三方协议是应届生与用人单位签署的标准录用协议，并经学校盖章存档，具备法律效力。如果用人单位在你入职前不用你了，算违约，若合同中约定了违约金，需要赔偿你，反之对你也一样。入职以后，需要拿着派遣证与单位签署正式的劳动合同。
　　二、三方协议的签订
　　网友：三方协议应该怎么签，其中实习生的相关部分有哪些具体注意事项，若想去北京工作，户口等问题如何办理？期待您的解答。　　专家：你好，你和单位签好三方协议后，拿到学校盖章存档，学校留一份，你和公司各存一份。北京户口有两类，一种是人事局指标，每年很有限，比较难申请，另一种是人事部指标，一般由央企、研究所和事业单位等向中央申请名额，相对松一些。另外，如果考取国家公务员，也是可以解决北京户口的。　　网友：是不是如果到北京工作，是不是一般都会把户口迁回原籍比较好些，在北京只需要公司缴纳相应的保险等就可以了？　　专家：你好，如果能解决北京户口，当然最好。如果不能，可以考虑在学校所在地落户，或者把户口迁回原籍，具体取决于留在哪对你更有利。　　网友：在学校签公司是不是校就业办会帮我们跟公司协商好合同的签订啊？？我还想问问社会上的招聘真的要比校园招聘的风险要高吗？？　　专家：你好，学校会发给你三方协议，由你拿着三方协议和单位自行签署，然后拿一份回学校盖章存档，你和单位各留一份。毕业以后，拿着派遣证到公司报到，签署正式劳动合同。现在各大公司都会到学校进行校园招聘，或者网上招聘。社会上的招聘，要注意参加正规的大型招聘会，避免上当。　　网友：毕业生三方协议签订有哪些注意事项？　　专家：你好，签三方需要注意以下事项：1)户口，2)待遇，3)岗位及级别，4)加班出差情况，5)培训，6)发展机会，7)签约年限，8)违约金，9)公司口碑。具体请关注近期我的微博文章。　　网友：实习期没有签合同，也没有签三方协议，只有口头协议，如果实习期间被辞退，是否会有什么补偿？　　专家：你好，实习是不签劳动合同的，因为你还没毕业，关系和档案还在学校。除少数公司会签实习协议外，大部分公司可能都不会签书面协议，所以实习期间被辞退是没有补偿的。但如果你已经毕业，是在试用期被辞退，除劳动法第39条的情形外，是可以获得补偿的。　　网友：在学校核对的生源地信息是否直接关系到工作单位报到证，与三方协议有何关系？　　专家：你好，三方协议是你毕业前与单位签的标准的意向性协议，毕业后，拿着报到证到单位报到，签定正式劳动合同后，三方协议自动终止。核对生源地信息一般适用于以下情况：毕业后将户口和档案派回生源地。　　三、关于违约
　　网友：国家对违约金有没有统一的标准？　　专家：你好，如果是签定的三方协议，国家没有规定违约金上限，一般是你和单位协商确定，通常情况下，三方协议如果约定违约金的话，一般是或5000。　　网友：毕业生的三方协议是否应该约定薪资福利待遇，是否可以约定违约金？劳动合同未约定薪资数字劳动合同是否部分失效或全部无效？在此方面如何维护员工个人利益。　　专家：你好，三方协议一般不会约定薪资福利待遇，但可以约定违约金，如果违约，须交纳违约金。过去合同中需要约定你享有哪些福利待遇，但一般不会约定具体数字，待遇需要在签合同前谈好或者打听清楚。至于入职以后，承诺的收入能否达到，要看单位的人品。　　网友：老师您好，我想问这样一些问题：1.offer有什么作用？2.如果签了offer以后，又不去这家单位了，算不算违约，需不需要交违约金？　　专家：你好，offer是你和公司签署的一个录用意向，但最终须签署三方协议才算数。offer本质上是你和公司之间签署的一个的合同，所以，如果在offer中约定了违约金，那么，当你不去时，就算违约，仍然要交违约金，这点请一定要注意。　　网友：你好，我是一名大四的学生，我想问一下，如果已经和公司签订了劳动合同，但又考上了公务员，那要和公司解约付赔偿金吗？三方协议怎么办？我们老师说协议只有一份，如果考公务员最好就不要签就业合同。是这样吗？　　专家：你好，准确的说，应该是已经和公司签订了三方协议。这时需要先跟这家公司违约(可能要交违约金)，取得退函后，到学校领一份新三方协议，再和新单位签三方协议。这种做法可以有效降低求职的风险，只是不太道德，另外有的学校不允许违约。建议先了解清楚。　　网友：如果想违约该怎样做？合同期内被辞退有什么补偿？　　专家：你好，如果是应届生违约，需要原单位同意，并开出退函，如果三方协议约定了违约金，还要交违约金，然后拿退函到学校重领一份三方协议，与新单位签三方协议。注意与原单位协商好，不要担误与新单位签约。　　如果是合同期间被辞退，经济补偿按劳动者在本单位工作的年限，每满一年支付一个月工资的标准向劳动者支付。六个月以上不满一年的，按一年计算；不满六个月的，向劳动者支付半个月工资的经济补偿。如果用人单位违法终止劳动合同，按补偿标准的2倍支付赔偿金。　　网友：您好，我是应届毕业生，和一家企业签了三方协议，但是只填了一些协议上的基本信息，没有约定违约金。如果我想在合同签订前违约，应该怎么办？法律规定必须交违约金吗？需要交多少？谢谢您！　　专家：你好，如果要违约，应该主动跟原单位提出来，拿到对方的退函，态度要诚恳，争取取得对方谅解。像你这种情况，没有约定违约金就是不用交，但也会比较麻烦，退函拿的快慢全取决于单位。请一定要与原单位协商好，不要因为时间拖的过长而耽误与新单位签三方协议。　　资料来源于&智联招聘-求职无小事&与《点灯》作者王刚&正规劳动合同该怎样签？？&活动。
static用法汇总，有没有觉得笔试的时候一直出现然后一直写不全呢！！！！
在C语言中，static的字面意思很容易把我们导入歧途，其实它的作用有三条。
（1）先来介绍它的第一条也是最重要的一条：隐藏。
当我们同时编译多个文件时，所有未加static前缀的全局变量和函数都具有全局可见性。为理解这句话，我举例来说明。我们要同时编译两个源文件，一个是a.c，另一个是main.c。
下面是a.c的内容
char&a&=&'A';&//&global&variable
void&msg()&{&&&&printf("Hello\n");&}
下面是main.c的内容
int&main(void){&&&&&&&&extern&char&a;&&&&//&extern&variable&must&be&declared&before&use
&&&&printf("%c&",&a);&&&&(void)msg();&&&&return&0;}
程序的运行结果是：
你可能会问：为什么在a.c中定义的全局变量a和函数msg能在main.c中使用？前面说过，所有未加static前缀的全局变量和函数都具有全局可见性，其它的源文件也能访问。此例中，a是全局变量，msg是函数，并且都没有加static前缀，因此对于另外的源文件main.c是可见的。
如果加了static，就会对其它源文件隐藏。例如在a和msg的定义前加上static，main.c就看不到它们了。利用这一特性可以在不同的文件中定义同名函数和同名变量，而不必担心命名冲突。Static可以用作函数和变量的前缀，对于函数来讲，static的作用仅限于隐藏，而对于变量，static还有下面两个作用。
（）的第二个作用是保持变量内容的持久。存储在静态数据区的变量会在程序刚开始运行时就完成初始化，也是唯一的一次初始化。共有两种变量存储在静态存储区：全局变量和变量，只不过和全局变量比起来，可以控制变量的可见范围，说到底还是用来隐藏的。虽然这种用法不常见，但我还是举一个例子。
#include&&stdio.h&
int&fun(void){&&&&static&int&count&=&10;&&&&//&事实上此赋值语句从来没有执行过
&&&&return&count--;}
int&count&=&1;
int&main(void){&&&&&&&&printf("global\t\tlocal&static\n");&&&&for(;&count&&=&10;&++count)&&&&&&&&printf("%d\t\t%d\n",&count,&fun());&&&&&&&&&&&&return&0;}
程序的运行结果是：global&&&&&&&&& local static1&&&&&&&&&&&&&& 102&&&&&&&&&&&&&& 93&&&&&&&&&&&&&& 84&&&&&&&&&&&&&& 75&&&&&&&&&&&&&& 66&&&&&&&&&&&&&& 57&&&&&&&&&&&&&& 48&&&&&&&&& &&&&&39&&&&&&&&&&&&&& 210&&&&&&&&&&&&& 1
（3）static的第三个作用是默认初始化为0。其实全局变量也具备这一属性，因为全局变量也存储在静态数据区。在静态数据区，内存中所有的字节默认值都是0x00，某些时候这一特点可以减少程序员的工作量。比如初始化一个稀疏矩阵，我们可以一个一个地把所有元素都置0，然后把不是0的几个元素赋值。如果定义成静态的，就省去了一开始置0的操作。再比如要把一个字符数组当字符串来用，但又觉得每次在字符数组末尾加&\0&太麻烦。如果把字符串定义成静态的，就省去了这个麻烦，因为那里本来就是&\0&。不妨做个小实验验证一下。
#include&&stdio.h&
int&main(void){&&&&int&i;&&&&static&char&str[10];
&&&&printf("integer:&%d;&&string:&(begin)%s(end)",&a,&str);
&&&&return&0;}
程序的运行结果如下integer: 0;&string: (begin)(end)
最后对static的三条作用做一句话总结。首先static的最主要功能是隐藏，其次因为static变量存放在静态存储区，所以它具备持久性和默认值0。
网络的一些笔试题目总结~~~
1、OSI（国际标准化组织）它们分别是：物理层、数据链路层、网络层、传输层、会话层、表示层、应用层。2、集线器hub工作在物理层；网卡工作在物理层、路由器router工作在网络层；交换机switch工作在数据链路层。3、ARP的中文意思是（地址解析协议）。1、首先，每台主机上都会在自己的ARP缓冲区（ARP Cache）中建立一个ARP列表，以表示IP地址和MAC地址的对应关系。2、当源主机需要将一个数据包要发生到目的主机时，会首先检查自己的ARP列表中是否存在该IP地址对应的MAC地址，如果有，就只见将数据包发送到这个MAC地址；如果没有，就像本地网段发起一个ARP请求的广播包，查询此目的主机对应的MAC地址。此ARP请求数据包里包括源主机的IP地址、硬件地址、以及目的主机的IP地址。3、网络中的所有主机收到这个ARP请求后，会检查数据包中的目的IP是否和自己的IP地址一致，如果不同就忽略；如果相同，该主机首先将发送端的MAC地址和IP地址添加到自己的ARP列表中，如果ARP列表中已经存在该IP的信息，则将其覆盖，然后给源主机发送一个ARP响应数据包，告诉对方自己是它需要查找的MAC地址。4、源主机收到这个ARP响应数据包后，将得到的目的主机的IP地址和MAC地址添加到自己的ARP列表中，并利用此信息开始数据的传输。如果源主机一直没有收到ARP响应数据包，表示ARP查询失败。4、DNS，域名系统（Domain Name System）当DNS客户机需要查询程序中使用的名称时，它会查询DNS服务器来解析该名称。客户机发送的每条查询信息都包括3条信息，以指定服务器应回答的问题。1、指定的DNS域名，表示完全合格的域名。2、指定的查询类型，它可根据类型指定资源记录，或作为查询操作的专门类型。3、NDS域名的指定类别。5、TCP和UDPTCP提供的是面向连接的、可靠的数据流传输，而UDP提供的是非面向连接的、不可靠的数据流传输；简单的说，TCP注重数据安全，而UDP数据传输快点，但安全性一般。6、网关的作用是：通过它可以访问外网。&&1、浏览器和www服务器之间传输信息时使用的是http协议2、在星型局域网结构中，连接文件服务器与工作站的设备是交换机3、网桥：用于一个局域网与另一个局域网的连接4、中继器（Repeater）工作于OSI的物理层，是上所有节点的中心，它的作用是放大信号，补偿信号衰减，支持远距离的通信。它设计的目的是给你的网络信号以推动，以使它们传输得更远。&
SNMP(Simple Network Management Protocol，简单网络管理协议）
一些华为的上机测试题目~~
&1、选秀节目打分，分为专家评委和大众评委，score[] 数组里面存储每个评委打的分数，judge_type[] 里存储与 score[] 数组对应的评委类别，judge_type == 1，表示专家评委，judge_type == 2，表示大众评委，n表示评委总数。打分规则如下：专家评委和大众评委的分数先分别取一个平均分（平均分取整），然后，总分 = 专家评委平均分 &* 0.6 + 大众评委 * 0.4，总分取整。如果没有大众评委，则 总分 = 专家评委平均分，总分取整。函数最终返回选手得分。& & & & & & 函数接口 & int cal_score(int score[], int judge_type[], int n)&& & & 2、给定一个数组input[] ，如果数组长度n为奇数，则将数组中最大的元素放到&output[] 数组最中间的位置，如果数组长度n为偶数，则将数组中最大的元素放到 output[] 数组中间两个位置偏右的那个位置上，然后再按从大到小的顺序，依次在第一个位置的两边，按照一左一右的顺序，依次存放剩下的数。& & & 例如：input[] = {3, 6, 1, 9, 7} & output[] = {3, 7, 9, 6, 1}; & & & & && &input[] = {3, 6, 1, 9, 7, 8} & &output[] = {1, 6, 8, 9, 7, 3}& & & & & & &函数接口 & void sort(int input[[, int n, int output[])& & & 3、操作系统任务调度问题。操作系统任务分为系统任务和用户任务两种。其中，系统任务的优先级 & 50，用户任务的优先级 &= 50且 &= 255。优先级大于255的为非法任务，应予以剔除。现有一任务队列task[]，长度为n，task中的元素值表示任务的优先级，数值越小，优先级越高。函数scheduler实现如下功能，将task[] 中的任务按照系统任务、用户任务依次存放到 system_task[] 数组和 user_task[] 数组中（数组中元素的值是任务在task[] 数组中的下标），并且优先级高的任务排在前面，数组元素为-1表示结束。& & & 例如：task[] = {0, 30, 155, 1, 80, 300, 170, 40, 99} & &system_task[] = {0, 3, 1, 7, -1} &&&user_task[] = {4, 8, 2, 6, -1}& & & & & & &函数接口 & &void scheduler(int task[], int n, int system_task[], int user_task[])&&
1.第一道就是说算分数的问题，去掉一个最高分一个最低分，求平均分&
2.第二道：对一个数组，将数组中偶数从大到小排序，奇数从小到大排序 &&
奇数和偶数交叉着放且输出数组第一位放奇数若奇数和偶数不等长，则把剩下的直接放到数组中. &
3.第三道，对于一个数组的第i个数，该数除十七取余，若对于第j（j&i）个任意输出数不相等的话，
责任是第i数的输出数 & 否则，把刚才的余数＋1再除十七取余，
在与第j个任意输出数，看是不是有相等的，若不等，则位第i个输出数 &
&否则，再把第二步的余数＋2，与第j个任意输出数比较，若不等，则为输出数， &&&&
1. 手机号码合法性判断（20分）
问题描述：
我国大陆运营商的手机号码标准格式为：国家码+手机号码，例如：8。特点如下：
1、 &长度13位；
2、 &以86的国家码打头；
3、 &手机号码的每一位都是数字。
请实现手机号码合法性判断的函数要求：
1） &如果手机号码合法，返回0；
2） &如果手机号码长度不合法，返回1
3） &如果手机号码中包含非数字的字符，返回2；
4） &如果手机号码不是以86打头的，返回3；
【注】除成功的情况外，以上其他合法性判断的优先级依次降低。也就是说，如果判断出长度不合法，直接返回1即可，不需要再做其他合法性判断。
要求实现函数：
int s int verifyMsisdn(char* inMsisdn)
【输入】 char* inMsisdn，表示输入的手机号码字符串。
【输出】 &无
【返回】 &判断的结果，类型为int。
输入： &inMsisdn = &&
输出： &无
输入： &inMsisdn = &89&
输出： &无
输入： &inMsisdn = &89&
输出： &无
2. 将一个字符串的元音字母复制到另一个字符串，并排序（30分）
问题描述：
有一字符串，里面可能包含英文字母（大写、小写）、数字、特殊字符，现在需要实现一函数，将此字符串中的元音字母挑选出来，存入另一个字符串中，并对字符串中的字母进行从小到大的排序（小写的元音字母在前，大写的元音字母在后，依次有序）。
1、 &元音字母是a,e,i,o,u,A,E,I,O,U。
2、 &筛选出来的元音字母，不需要剔重；
最终输出的字符串，小写元音字母排在前面，大写元音字母排在后面，依次有序。
要求实现函数：
void sortVowel (char* input, char* output);
【输入】 &char* input，表示输入的字符串
【输出】 &char* output，排好序之后的元音字符串。
【返回】 &无
输入：char *input = &Abort!May Be Some Errors In Out System. &
输出：char *output =&aeeeooAEIO &
&3. 身份证号码合法性判断
问题描述：
我国公民的身份证号码特点如下：
1、 & & 长度为18位；
2、 & & 第1～17位只能为数字；
3、 & & 第18位可以是数字或者小写英文字母x。
4、 & & 身份证号码的第7~14位表示持有人生日的年、月、日信息。
例如：011x。
请实现身份证号码合法性判断的函数。除满足以上要求外，需要对持有人生日的年、月、日信息进行校验。年份大于等于1900年，小于等于2100年。需要考虑闰年、大小月的情况。所谓闰年，能被4整除且不能被100整除 或 能被400整除的年份，闰年的2月份为29天，非闰年的2月份为28天。其他情况的合法性校验，考生不用考虑。
函数返回值：
1） &如果身份证号合法，返回0；
2） &如果身份证号长度不合法，返回1；
3） &如果身份证号第1~17位含有非数字的字符，返回2；
4） &如果身份证号第18位既不是数字也不是英文小写字母x，返回3；
5） &如果身份证号的年信息非法，返回4；
6） &如果身份证号的月信息非法，返回5；
7） &如果身份证号的日信息非法，返回6（请注意闰年的情况）；
【注】除成功的情况外，以上其他合法性判断的优先级依次降低。也就是说，如果判断出长度不合法，直接返回1即可，不需要再做其他合法性判断。
要求实现函数：
int verifyIDCard(char* input)
1） 输入：&&，函数返回值：1；
2） 输入：&511002abc&，函数返回值：2；
3） 输入：&08123a&，函数返回值：3；
4） 输入：&081234&，函数返回值：4；
5） 输入：&081234&，函数返回值：5；
6） 输入：&321234&，函数返回值：6；
7） 输入：&291234&，函数返回值：7；
8） 输入：&081234&，函数返回值：0；
& &第一题【20分】：鉴定回文数组。
第二题【30分】：求两个整型数组的异集，即A+B-(A与B的交集)。
第三题【50分】：判定德州扑克的牌型。给5张牌，返回它的牌型，4个的，3个+对子，顺子，3个+2个单张，2对，1对，其他。&&&
解说华为薪资待遇+股票分红+加班制度+离职原因+奋斗历程
& &完全胜任的系数是1，基本胜任的系数是0.9，暂不胜任的系数是0.8地区差异系数：一级城市1，二级城市0.9，三级城市0.8其它的0.7，15级3-4w多期权。今年每股分红1块多。还有若干奖金、股票分红。　　在，助理工程师的技术等级为13C-15B，普通工程师B的等级为15A&16A。普通工程师A的等级为17C-17A。高级工程师B的等级18B-19B。高工A或技术专家19B&20A（华为技术专家的技术等级和待遇等同于三级部门主管，若高级专家最高可达到一级部门正职的技术等级21A-22B），三级部门主管19B。A，二级部门主管20A，一级部门主管21B，A&22B最高等级22A。　　里所说的年收入也因人而异。如一个社招的18级的员工，他进入华为以后的前四年每年的收入最多35万。而一个土著18级，他的年收入最少百万。这个差距是股票和奖金造成的。　　拿18A来说，每个月要交5700左右的个人所得税，扣除个人所交保险什么的，算2000吧，=24800.一年的工资税后收入大概是30万。奖金和分红另计。如果工作八年以上，可以去应聘16A（大多给16B，但是工资会低于上述所贴，上述的工资是每个级别的最高工资等级。工资开价 之间），工作六年的可以去应聘15A，B（工资开价之间，如开价16级肯定不会给）。若自认为能力突出，项目经验丰富，有经理级职务，或技术专家，可以去应聘18级，当然应聘的时候会和你讨价还价，讨价还价之后给你的级别一般会低于你的开价一大级。　　如果工作十年或以前担任过部门经理的社招员工，由于级别给的较高（17a以上者）大多数会赶到海外。　　04年进入华为的本科生目前大多15A，B。华为社招工作六年的能力和技术水平一般，基本能胜任工作普通社招员工，大多15A，B。如果在原公司是骨干可以高两个小级。即16B，16A。如果社招工作8年的普通员工，大多给予16A或17B。如果原公司（在业界有所闻名的公司）担任过公司正式任命的部门经理，并有超过两年担任部门经理（部门主管）职务的经历，有管理团队工作的业绩，或是工作十年以上的技术骨干，则不走普通招聘流程。作为特招进入。级别一般给予18A& 17A。给予签字费，股票。很多人会注明年终奖不低于某个数值。若是，，阿朗，诺西，等公司正式任命的部门经理（部门主管）则会给予等同于华为三级部门主管的级别19B或19A。（这里所说的部门经理即公司正式发文任命的部门经理，负责管理一个部门，负责管理部门整个部门的工作，制订部门计划，监督管理员工，负责员工考核，召开例会分配任务等。负责领导本部门全体员工完成公司或上级下达的各项任务的部门领导者。）&应届本科生最低级别就是13C.13c以下是3千多名生产线上的操作工的级别。　　签字费就是你愿意来华为给你的补偿金，一般是作为补偿你跳槽损失的奖金。一般3-N万。此签字费特招员工或普通工程师B以上的员工才有。（华为挖骨干员工的手段）。　　特招一般三面，没有普通社招的技术考试和群K。特招为每个产品线的人力资源也就是干部部的主管，（干部部是普通的负责招聘的部门，不是什么招收干部的部门，华为的干部部就是公司人力资源下设在在每个产品线的二级部门，负责应届招聘，社招，考核员工等。），用人部门主管和技术骨干面，大领导。特招以面谈为主。主要考察你领导团队能力，项目能力。　孙亚芳是最高级22A。和任一样。华为好像只有此两人为22A（具体不详），华为一级部门主管或副总裁在22B，C&21C之间，二级部门总监20A- 20C，三级部门主管19A&19C。（刚开始定级时三级部门主管大多18A，B，现在过去若干年华为的级别也有水分了。大家的级别也有升高）　　新入职的应届本科13C，一般每一年2小级。此任职资格和你的技术等级挂钩（但是内部有时又不挂钩），技术等级共为7级，7级只有一个，其余的为 6A》6B》6c》5a》5b》5c》4a》4b》4c》&。.1c），形象的说，技术等级是职称，任职资格是享受的待遇等级。也许有的人15年也到不了18A。也许有的人很快就到18A。不一而同。因人而异。　　华为任职资格和技术等级是挂钩的，规定为技术等级+13=任职资格，如技术等级3A，任职资格为3A+13=16A。规定是这样，也有不匹配。　　七千人离职事件发生在07年。2000年前入职的应该在1.3万人左右。他们都是沉淀下来的员工。因为他们一直在华为工作。股票较多，年终奖也高，2000年以前进入华为的工作都超过十年了，所以他们的年收入不止50万。他们的收入是社招18A的三倍左右。大多在百万左右。海外的更多。　　如果社招进华为，年收入会低于华为同级别的员工，因为他们有股票，年终奖也高，社招员工要三年左右才能配到和级别相应的股票，年终奖三年才能和同级别的相同。刚进去年终奖很低，股票也配给的少。股票要达到饱和有三四年的过程。　　因为每个级别都有完全胜任和不完全胜任或是不胜任，所以每个级别的员工的工资也有一些差异，股票也会有差异。这里所贴的是基本工资，如果不完全胜任，乘 0.8系数。　　胜任的工资要乘以0.8的系数。至于PL在华为不算什么，是研发最极低的小组长。也许只是三五个人中临时负责者，也许是二十来号人的小组长。很多研发人员外出为了提高身价，自己说自己是PL。（基本上无法求证），三级部门主管才有公司发文。如果有四级部门，有的PM可能也会有发文。&华为研发体系层级如下：普通研发&PL&PM&-四级部门有的是PM为部门负责人（很多研发部门有四级部门，也有的没有）&开发代表（三级部门主管）&-总监（二级部门主管）。　　如果他工作六年多，任职资格15A。入职时以应届生为例，入职工资00，他工作六年了。要知道华为已经连续三年普调工资，即便是一次只加五百元，三次也有1500，初此之外的另外三年他还应该没有一次加薪。这样，工资为00，此外，他是15a，即便是 15A的工资不匹配，也应该匹配14A或15B的工资标准。所以他15A不到10000的工资是特例。很少见。以他工作六年多，15A为例，他的股票应该在8万股左右。年分红12万左右。此外工作六年的年终奖应该在8万以上。　　若他的收入证明上和这个收入差距比较大。就会有疑问了。　　至于华为的工资及分红奖金开支，可以参照华为的收入，华为主要开支就是工资分红奖金开支了。物料成本可以忽略。老任还是很大方的。
　　华为员工：估计50%员工达不到28万元年薪水平　　又到华为发年终奖之际，在论坛上晒工资、秀分红，也再次成为部分华为员工的娱乐项目。　　华为2010年年报，去年公司在雇员费用这块的支出是306亿元，以华为11万员工计算，其员工平均年薪近28万元。　　&估计华为50%的员工都达不到28万元年薪的水平，最近华为的内部论坛为这件事炒得沸沸扬扬。&华为一名内部员工昨日表示。　　从年报看，这306亿元并不包括股票分红。据本报记者计算，华为去年的分红应为118亿元。　　大规模员工持股被认为是华为取得成功的一种公司治理模式，事实上，除了员工激励，这也是华为的内部集资行为。不过，华为的员工持股究竟是什么性质，是否可以一直持续地向员工配股，这都是不少分析人士疑惑之处。&等级分明的薪酬体系　　&我们上半年的工资整体水平确已上调10%。&华为生产部门一位内部员工表示，每个员工调薪的幅度与过去一年的工作绩效直接挂钩。但如果员工去年绩效考核在倒数5%以内，此次就失去获得上调薪水的机会。　　近日，华为公开对媒体披露，今年上半年华为4万多中基层员工工资已上涨11.4%，占总员工数的36%，下半年还将继续对中高层员工薪酬进行调整，预计工资涨幅5%~10%。　　上述内部员工指出，华为每年都会根据公司业绩普调员工薪水，调整幅度一般也在10%，这次调薪也与国内CPI指数持续攀升有关。不过，今年员工配股还没有开始实施，所配股票数量在几千股至几万股之间，也与去年工作绩效直接挂钩。　&其实华为员工的薪水与自身在什么体系和什么级别直接挂钩，等级非常分明。&上述内部员工说。　　上述内部员工透露，华为员工按生产、研发、市场销售和客户服务划分四个体系，其中，研发和市场销售体系的薪金水平明显高过生产和客户服务体系。刚毕业的本科生进入华为的起薪标准为6000元/月左右，研究生为8000元/月左右，这种区别随着工作年限加长而越来越小，主要比拼的是工作业绩和能力。　　天涯论坛华为专区上广泛转载的&华为内部工资和待遇详解&的帖子显示，华为员工薪水级别从13级起到22级，共10级。　　上述内部员工表示，该帖子内容基本属实，一般在市场销售和研发部门工作5年后，每月薪水加上年终奖和股票分红，一般都会在20万元左右。但在华为工作相对更辛苦，员工经常为完成工作而自发加班，但没有加班费，所以每年都有4%的员工离职。　　一位华为手机研发人员也证实，一般工作5年的研发人员年薪在20万元左右。
虚拟股票是否算真持股？　　华为市场部一位中层表示，工作5年以上，20万元年薪在华为研发和市场部门算是中等水平，而华为员工的工资水平也比（000063.SZ，00763.HK）等竞争对手差不多多了20%。更为重要的是，华为有六成员工持有公司股票，可以享受公司业绩增长所带来的盈利。　　财报显示，华为现有11万员工，其中6.5万人持股。　　对于华为员工工资比中兴通讯高的说法，中兴通讯一位内部人员表示，中兴通讯在奖金方面比华为高，但该人士不愿意透露，中兴通讯员工的年薪水平和结构。　　第三方验证权威机构挪威船级社注册主任审核员吴迪昨日对本报记者表示，公司业绩的增长与员工薪水增长其实并不直接挂钩，只是代表了员工薪水会增长的趋势，而华为员工持股的方式，也将公司利益与员工利益直接挂钩，自然提高华为薪水竞争力。　　或许正基于此，中兴通讯也在加紧实施股权激励。6月14日，中兴通讯第一大股东深圳新通讯设备公司减持4849.5万股，套现12.55亿元。该举动被业界猜测，中兴通讯通过迂回的方式实现员工激励。中兴通讯方面并没有对减持作任何说明，也不愿意透露减持的原因。　　然而，作为上市公司，中兴通讯要实现持续的员工股权激励存在不小难题&&用于激励的股权来自增发还是大股东转让？一般而言，大股东减持作为激励股权池的做法更为普遍。　　那么华为几乎年年向职工配股，股票又从何而来？事实上，从2001年开始，华为实行名为&虚拟受限股&的期权改革。虚拟股票是指公司授予激励对象一种虚拟的股票，激励对象可以据此享受一定数量的分红权和股价升值权，但是没有所有权，没有表决权，不能转让和出售，在离开企业时自动失效。　　这就是说，假如华为向一名员工配&虚拟受限股&一万股，这或许并不表明华为需要增发一万股新股供认购。此外，&虚拟受限股&是否对应着华为相同数量的股份，这都是未知数。此前就有律师认为，华为的员工持股计划并不规范，而更像是内部奖励制度。
【转】我所积累的二十条编程经验
本文转自Jonathan Danylko的网站DCS Media。Danylko是一位资深开发顾问，DCS公司的创始人。从11岁时，我就一直在编程，并且一直都很喜欢技术和编程。这些年来，我积累了一些艰难又容易的经验。作为一名程序员，你或许还没这些经验，但我会把它们献给那些想从中学到更多的朋友。我会持续更新这些经验，我可能还会有更多的感想，但就我这20年来看，我想下面这个列表中基本不需要增添额外的东西了。下面就是我至今最难忘的经验。1. 估算解决问题所需要的时间。不要怕，承认吧！我曾见过一些程序员为了解决一个特殊问题而坐在显示器前面8小时。为自己定一个时间限制吧，1小时、30分钟或甚至15分钟。如果在这期间你不能解决问题，那就去寻求帮助，或到网上找答案，而不是尝试去做&超级堆码员&。2. 编程语言是一种语言，只是一种语言。随着时光推移，只要你理解了一种语言的原理，你会发现各种语言之间的相似之处 。你所选择的语言，你应该觉得&舒服&，并且能够写出有效（而且简洁）的代码。最重要的，让语言去适应项目，反之亦然。3. 不要过于注重程序的&设计模式&。 有时候，写一个简单的算法，要比引入某种模式更容易。在多数情况下，程序代码应是简单易懂，甚至清洁工也能看懂。4. 经常备份代码。在我年轻时，我就有过因硬盘故障而丢了大量代码的经历，这经历很恐怖的。只要你一次没有备份，就应当像有着严格的期限，客户明天就需要。此时就该源码/版本控制软件大显身手了。5. 承认自己并不是最顶尖的程序员 & 知不足。我常想，我对编程了解已足够多，但是总有其他人比你优秀。正所谓，&一山总比一山高&。所以，向他们看齐吧！6. 学习再学习。正如第5点所说，我经常会在手里拿一本计算机或编程相关的杂志或书（不信，可以问我的朋友）。诚然，总有很多你不知道的技术，你可以从中学习以保持不落后。如果你有一种灵巧的方式来获取你需要的新技术，那你每天都应该坚持学习。7. 永恒的变化。你对待技术/编程知识，就应像你对待股票一样：多样化。不要在某一特定技术上自我感觉良好。如果那种技术或语言已经没有足够支持，那你还不如现在就开始更新你的简历，并启动培训新计划。我能保持前行的主要原则是什么呢？至少了解两到三种语言，所以，如果某种语言过时了，你在学习新技术的时候还可以依靠另一种语言。8. 提携新人。协助并且培养初级/入门的开发人员学习优秀的编程方法和技巧。也许你还不知道，在帮助他们向更高一层前进时，你自己也在向更高一层提升，你会更加自信。9. 简化算法。代码如恶魔，在你完成编码后，应回头并且优化它。从长远来看，这里或那里一些的改进，会让后来的支持人员更加轻松。10. 编写文档。无论是Web服务的API，还是一个简单的类，你尽量编写相应文档。我曾经引以为豪的代码注释，因过度注释而有人指责。给三行代码加一行注释，只需要你几秒时间。如果那是一个比较难以理解的技术，千万别担心过多注释。如果你能很好做好自己的工作，大多数架构师、后备程序员、支持组都会感激你。11. 测试、测试再测试。我是一名黑盒测试粉丝。当你完成编码后，你&被认可&的时候就开始了。如果你们公司有QA部门，如果你的代码中有错误，那你得到的评论，会比项目经理还多。如果你不彻底测试自己的代码，那恐怕你开发的就不只是代码，可能还会声名狼藉。12. 庆祝每一次成功。我见过很多程序员在解决编程技术难题后，会和同伴握手、击掌或甚至手舞足蹈。每个人在生命中都会碰到&顿悟&。如果一个程序员高兴地跑来叫你去看他的非凡代码，也许你已经看过这样的代码100遍了，但你也应该为了这个家伙而庆祝第101次。13. 经常检查代码。 在公司，你的代码要经常检查（包括自查和其他同事检查）。不要把别人的检查，看成是对代码风格的苛求。应该把它们看作是有建设性的批评。对个人来说，经常检查你的代码并且自问，&我怎样才能写得更好呢？& 这会让你加速你的成长，让你成为一个更优秀的程序员。14. 回顾你的代码。在看到自己以前的代码时，通常会有两种方式：&难以至信，这代码是我写的&和&难以至信，这代码是我写的&。第一种往往是厌恶的语气，并在想如何改进它。你也许会惊叹，旧代码也能复活成为一种更好的程序，甚至是一个完整的产品。第二种通常带着惊奇和成就感。开发人员应该一到两个自己完成的项目成果，能让众人不禁而立并注目而观的项目。同样，基于你优越的编程能力，你可以把过去的程序或项目拿出来，把它们更新为更加优秀的产品或想法。15. 幽默是不可缺的。在我20年的开发生涯中，我还没有碰到哪位程序员是没有幽默感的。实际上，干我们这行，幽默是一项必备品。16. 谨防那些无所不知的程序员，不愿分享的程序员，还有经验不足的程序员。当你遇到这几种程序员时，你自己要谦虚。无所不知的程序员，更想当一个英雄而不是团队成员；保守的程序员则是在编写着他们独享的代码；而经验不足的程序员则会每十分钟就来问你一下，当代码完成后，代码已经是你的，而不是他们。17. 任何项目都不会那么简单。朋友、家人和同事曾请求我仓促做一些事情，仓促做一个程序或者网站。对于这样的事，应该从双方做计划，才能做出令两方都会满意的东西。如果某人起初只是需要一个使用Microsoft Access的、只有有3个页面的网站，但来就很可能变成一个有15个页面的网站，并使用SQL Server，有一个论坛，还有一个定制的CMS（内容管理系统）。18. 任何时候不要想当然。假如你承接一个简单的项目，你可能会认为某个部分可以轻松完成。千万别这样想！除非你有一个类、组件、或者一段已经写好的代码，并且在现有的项目已经测试通过。不要认为这将是很容易的。19. 没有已经完成的软件。曾经有一位程序员告诉我，没有软件是已经完成的，它只是&暂时完成了&。这是明智的忠告。如果客户还在使用你写的程序，并经受了时间的考验。如果有机会，你仍在更新它，这并不是什么坏事，这让你不断地前行。20. 耐心是一种美德。当客户、朋友或家庭成员用电脑的时候，他们也许会受挫，进而想砸电脑，或气冲冲地离开。我一直在告诉他们，&是你掌控电脑，不是电脑掌控你。&对于用作编程的电脑，你要有一定的耐心。一旦程序员知道问题所在后，他们就会站在电脑的角度看问题，并且说&哦，这就是为什么它是这样做。&
腾讯搜搜技术博客：/
淘宝核心系统团队博客：/blog/cs/
真正的程序员是这样的：有人告诉他外面下雨了，他的第一反应是打开Google搜一下，而不是向窗外看一下。
爱因斯坦教你如何编程~~~~~~~~~
女孩：“咱们分手吧” 男孩：“为什么？” 女孩：“写程序很简单，我学会了。” 男孩：“可你只会写HTML网页。” 女孩：“……” 男孩：“你不知道我还会JavaScript和CSS？” 女孩：“讨厌，不早说。”
常见算法笔试或面试题
Assume that wehave a head pointer to a link-list. Also assumethat we know the list is single-linked. Can you come up an algorithm to checkwhether this link list includes a loop by using O(n) time and O(1) space wheren is the length of the list? Furthermore, can you do so with O(n) time and onlyone register?
方法：使用两个指针，从头开始，一个一次前进一个节点，一个前进2个节点，则最多2N，后两个指针可以重合；如果无环，则正常停止。
同样的，可以找到链表的中间节点。同上。
Problem 2：设计一个复杂度为n的算法找到链表倒数第m个元素。最后一个元素假定是倒数第0个。
提示：双指针查找
Problem 3：用最简单的方法判断一个LONG整形的数A是2^n（2的n次方）
提示：x&(x-1)
Problem 4：两个烧杯，一个放糖一个放盐，用勺子舀一勺糖到盐，搅拌均匀，然后舀一勺混合物会放糖的烧杯，问你两个烧杯哪个杂质多？
提示：相同。假设杂质不等，那么将杂质放回原杯中，则杯中物体重量必变化，不合理。
Problem 5：给你a、b两个文件，各存放50亿条url，每条url各占用64字节，内存限制是4G，让你找出a、b文件共同的url。
法1：使用hash表。使用a中元素创建hash表，hash控制在适当规模。在hash中查找b的元素，找不到的url先存在新文件中，下次查找。如果找到，则将相应的hash表项删除，当hash表项少于某个阈值时，将a中新元素重新hash。再次循环。
法2：对于hash表项增加一项记录属于的文件a，b。只要不存在的表项即放入hash表中，一致的项则删除。注意：可能存在很多重复项，引起插入，删除频繁。&
Problem 6：给你一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么定义b是a的兄弟单词。现在给你一个字典，用户输入一个单词，让你根据字典找出这个单词有多少个兄弟单词。
提示：将每个的单词按照字母排序，则兄弟单词拥有一致的字母排序（作为单词签名）。使用单词签名来查找兄弟单词。
Problem 7：五桶球，一桶不正常，不知道球的重量和轻重关系，用天平称一次找出那桶不正常的球。
Problem 8：给两个烧杯，容积分别是m和n升（m!=n），还有用不完的水，用这两个烧杯能量出什么容积的水？
m, n, m+n, m-n以及线性叠加的组合
Problem 9：写出一个算法，对给定的n个数的序列，返回序列中的最大和最小的数。
Problem 10：你能设计出一个算法，只需要执行1.5n次比较就能找到序列中最大和最小的数吗？能否再少？
提示：先通过两两比较，区分大小放入&大&，&小&两个数组中。从而最大数在&大&数组中，最小数在&小&数组中。
Problem 11：给你一个由n-1个整数组成的未排序的序列，其元素都是1到n中的不同的整数。请写出一个寻找序列中缺失整数的线性-时间算法。
提示：累加求和
Problem 12：void strton(const char* src, const char*token) 假设src是一长串字符，token存有若干分隔符，只要src的字符是token中的任何一个，就进行分割，最终将src按照token分割成若干单词。找出一种O(n)算法？
提示：查表的方法，将所有的字符串存储在长度为128的数组中，并将作为分隔符的字符位置1，这样即可用常数时间判断字符是否为分隔符，通过n次扫描，将src分割成单词。
Problem 13：一个排好序的数组A，长度为n，现在将数组A从位置m(m&n，m未知)分开，并将两部分互换位置，假设新数组记为B，找到时间复杂度为O(lgn)的算法查找给定的数x是否存在数组B中？
提示：同样采用二分查找。核心思想就是确定所查找数所在的范围。通过比较3个数（头，尾，中间）和所查找数之间的关系，可以确定下次查找的范围。
Problem 14：一个排好序的数组A，长度为n，现在将数组A从位置m(m&n，m已知)分开，并将两部分互换位置，设计一个O(n)的算法实现这样的倒置，只允许使用一个额外空间。（循环移位的效率不高）
提示：(A&B&)& =BA
Problem 15：给出Vector的一个更好实现。（STL的vector内存的倍增的，但是每次倍增需要拷贝已存元素，平均每个元素需要拷贝一次，效率不高）
提示：可使用2^n的固定长度作为每次分配的最小单位，并有序的记录每个块的首地址。这中结构同样可以实现线性查找，并且拷贝代价很低（仅有指针）
Problem 16：给出已排序数组A，B，长度分别为n，m，请找出一个时间复杂度为（lgn）的算法，找到排在第k位置的数。
提示：二分查找。
Problem 17：给出任意数组A，B，长度分别为n，m，请找出一个时间复杂度为（lgn）的算法，找到排在第k位置的数。
提示：通过最小堆记录k个数，不断更新，扫描一次完毕。
这个提示有问题，求最优算法！
Problem 18：假设数组A有n个元素，元素取值范围是1~n，判定数组是否存在重复元素？要求复杂度为O(n)。
法1：使用n的数组，记录元素，存在记为1，两次出现1，即重复。
法2：使用m的数组，分别记录大小：n/m, 2n/m &..的元素个数。桶方法
法3：累加求和。可用于求仅有一个元素重复的方法。
Problem 19：给定排好序的数组A，大小为n，现给定数X，判断A中是否存在两数之和等于X。给出一个O(n)的算法。
提示：从中间向两边查找。利用有序的条件
Problem 20：给定排好序的数组A，大小为n，请给出一个O(n)的算法，删除重复元素，且不能使用额外空间。
提示，既然有重复，必有冗余空间。将元素放入数组的前面，并记录下次可放位置，不断向后扫描即可。
Problem 21：给定两个排好序的数组A，B，大小分别为n，m。给出一个高效算法查找A中的哪些元素存在B数组中。
注意：一般在大数组中执行二分查找，将小数组的元素作为需查找的对象。
更优算法（轩辕刃提供）：可以使用两个指针遍历AB，比较当前大小就可以了...时间复杂度o(n+m)
Problem 22：问：有1000桶酒，其中1桶有毒。而一旦吃了，毒性会在1周后发作。现在我们用小老鼠做实验，要在1周内找出那桶毒酒，问最少需要多少老鼠。
答案：10只。将酒编号为1~1000 将老鼠分别编号为1 2 4 8 16 32 64 128 256 512 喂酒时 让酒的编号等于老鼠编号的加和如：17号酒喂给1号和16号老鼠&&76号酒喂给4号、8号和64号老鼠 七天后将死掉的老鼠编号加起来 得到的编号就是有毒的那桶酒 因为2的10次方等于1024 所以10只老鼠最多可以测1024桶酒
证明如下：使用二进制表示：01, 10, 100, 1000, & , 1,000,000,000。对于任何一个小于1024的数，均可以采用前面的唯一一组二进制数来表示。故成立。
Problem 23：设计一组最少个数砝码，使得天平能够称量1~1000的重量。
如果砝码只能放单边，1，2 ，4 ，& 512最好。（只能单加）
如果允许砝码双边放，1, 3, 9, 27&.& 最好。（可加可减）已知1,3，如何计算下一个数。现可称重量1,2,3,4。设下个数为x,可称重量为, x-4, x-3, x-2, x-1, x, x+1, x+2, x+3, x+4。为使砝码最好，所称重量应该不重复（浪费）。故x=9。同理，可得后面。
图形算法题
Problem 24：如何判断一个点是否在一个多边形内？
提示：对多边形进行分割，成为一个个三角形，判断点是否在三角形内。
一个非常有用的解析几何结论：如果P2(x1,y1),P2(x2,y2), P3(x3,y3)是平面上的3个点，那么三角形P1P2P3的面积等于下面绝对值的二分之一：
| x1& y1& 1 |
| x2&y2& 1 | = x1y2 + x3y1 + x2y3 &x3y2 & x2y1 & x1y3
| x3&y3& 1 |
&&&&&& 当且仅当点P3位于直线P1P2(有向直线P1-&P2)的右侧时，该表达式的符号为正。这个公式可以在固定的时间内，检查一个点位于两点确定直线的哪侧，以及点到直线的距离(面积=底*高/2)。
&&&&&& 这个结论：可以用来判断点是否在点是否在三角形内。法1：判断点和三角形三边所行程的3个三角形的面积之和是否等于原来三角形的面积。（用了三次上面的公式）。
法2：判断是否都在三条边的同一边，相同则满足，否则不在三角形内。
Problem 25：给出两个n为向量与0点形成角的角平分线。
提示：对两条边进行归一化，得到长度为1的两点，取两个的中点即可。
面试的时候不会就是不会，建议面试官问其他的问题。
数据库中的关系范式
第一范式：每一个分量必须是不可分的数据项。第二范式：首先是满足第一范式，并且每一个非主属性完全函数依赖于码。第三范式：每一个非主属性既不部分依赖于码也不传递依赖于码。BCNF范式：若x-&y且y不包含于x时，x必含有码。
话说最近面试有让写快排的~~~
#include &iostream&void quicsort(int *a,int x,int y){int key=a[x];int low=x;int high=y;if(low&=high)while(low!=high){while(low&high&&a[high]&=key)high--;a[low]=a[high];while(low&high&&a[low]&=key)low++;a[high]=a[low];&}&a[low]=quicsort(a,x,low-1);quicsort(a,low+1,y);}int main(int argc, char *argv[]){int a[]={1,4,5,2,6};quicsort(a,0,4);for(int i=0;i&5;i++)cout&&a[i]&&" ";return 0;}
编程判断两个链表是否相交
编程判断两个链表是否相交
给出两个单向链表的头指针(如图 3-8 所示),比如 h1,h2,判断这两个链表是否 相交.这里为了简化问题,我们假设两个链表均不带环.
链表相交示意图
写书评,赢取《编程之美--微软技术面试心得》www./BCZM.asp 分析与解法
这样的一个问题,也许我们平时很少考虑.但在一个大的系统中,如果出现两个链表相 交的情况,而且释放了其中一个链表的所有节点,那样就会造成信息的丢失,并且另一个与 之相交的链表也会受到影响,这是我们不希望看到的.在特殊的情况下,的确需要出现相交 的两个链表,我们希望在释放一个链表之前知道是否有其他链表跟当前这个链表相交.
【解法一】直观的想法 看到这个问题,我们的第一个想法估计都是,"不管三七二十一",先判断第一个链表 的每个节点是否在第二个链表中.这种方法的时间复杂度为 O(Length(h1) * Length(h2)).可 见,这种方法很耗时间.
【解法二】利用计数的方法 很容易想到,如果两个链表相交,那么这两个链表就会有共同的节点.而节点地址又是 节点的唯一标识.所以,如果我们能够判断两个链表中是否存在地址一致的节点,就可以知 道这两个链表是否相交.一个简单的做法是对第一个链表的节点地址进行 hash 排序,建立 hash 表,然后针对第二个链表的每个节点的地址查询 hash 表,如果它在 hash 表中出现,那 么说明第二个链表和第一个链表有共同的节点.这个方法的时间复杂度为 O(max(Length(h1) + Length(h2))).但是它同时需要附加 O(Length(h1))的存储空间,以存储哈希表.虽然这样做 减少了时间复杂度,但是是以增加存储空间为代价的.是否还有更好的方法呢,既能够以线 性时间复杂度解决问题,又能减少存储空间
【解法三】 由于两个链表都没有环, 我们可以把第二个链表接在第一个链表后面, 如果得到的链表 有环,则说明这两个链表相交.否则,这两个链表不相交(如图 3-9 所示).这样我们就把 问题转化为判断一个链表是否有环.
链表有环的情况
判断一个链表是否有环, 也不是一个简单的问题, 但是需要注意的是, 在这里如果有环, 则第二个链表的表头一定在环上, 我们只需要从第二个链表开始遍历, 看是否会回到起始点 就可以判断出来.最后,当然可别忘了恢复原来的状态,去掉从第一个链表到第二个链表表 头的指向.
写书评,赢取《编程之美--微软技术面试心得》
这个方法总的时间复杂度也是线性的,但只需要常数的空间.
【解法四】 仔细观察题目中的图示, 如果两个没有环的链表相交于某一节点的话, 那么在这个节点 之后的所有节点都是两个链表所共有的. 那么我们能否利用这个特点简化我们的解法呢 困 难在于我们并不知道哪个节点必定是两个链表共有的节点(如果它们相交的话).进一步考 虑"如果两个没有环的链表相交于某一节点的话,那么在这个节点之后的所有节点都是两个 链表共有的"这个特点,我们可以知道,如果它们相交,则最后一个节点一定是共有的.而 我们很容易能得到链表的最后一个节点,所以这成了我们简化解法的一个主要突破口. 先遍历第一个链表,记住最后一个节点.然后遍历第二个链表,到最后一个节点时和第 一个链表的最后一个节点做比较,如果相同,则相交,否则,不相交.这样我们就得到了一 个时间复杂度,它为 O((Length(h1) + Length(h2)),而且只用了一个额外的指针来存储最后一 个节点.这个方法比解法三更胜一筹.
1. 如果链表可能有环呢 上面的方法需要怎么调整 2. 如果我们需要求出两个链表相交的第一个节点呢&
链表有没有环的问题
1. 从链表的出入度考虑带环链表的结构形状。2. 快慢指针判别是否有环(分别为指针low和fast）。
&&&假设该链表在环出现之前有L个结点，环中有C个结点。&&&再假设慢指针初始化时指向的位置为a、快指针初始化时指向的位置为b，&&&如果二者在t 次移动后相遇，也就是说：(a+t-L) mod C == (b+2*t-L) mod C,&&&所以无论a、b的起始位置如何，二者总是会相遇的。&&&推导：(a+t-L) mod C == (b+2*t-L) mod&&&&&&&&&a+t-L-m*C == b+2*t-L -n*C&&&&&&&&&t == (a-b) - (m-n)*C&&&a==b ==& t == (n-m)*C；在保证m和n为正整数的情况下上式t有正整数解。&&&若两个指针的步长分别为：x和y（即每走一步步长分别为：x*t和y*t）&&&(x-y)*t == (a-b) - （m-n)*C&&&要是程序不陷入死循环必须满足上面这个等式有正整数解。&&&比方说：假设链表是由4个结点首尾相接构成的一个圆圈（编号为0~3）&&&慢指针初始位置在0，每次前进1步；&&&快指针初始位置在3，每次前进3步；&&&有：（3-1）*t == (3-0) - （m-n）*4&&&此等式没有正整数解，所以虽然这两个指针也是一快一慢一前一后，但它们永远也不会相遇！3&&寻找环的入口。在x=1，y=2，a=b=0的情况下，让fast回到链表的头部，重新走，每次步长走1，&&&那么当low和fast再次相遇的时候，就是环路的入口了。&&&t = (n-m)*C&&&假设再走t1步：(t+t1-L) mod C == 0 ==& t1 == L&&&测试代码：#include &iostream&
typedef struct Node{&&&&&&&&Node*}SN
//带头节点void creatList(SNode** s, int len, int c){&&&&int pos = 0;&&&&int l =&&&&SNode *p, *q;&&&&*s = new SN&&&&(*s)-&num = -1;&&&&(*s)-&next = NULL;&&&&q = *s;&&&&while(l--)&&&&{&&&&&&&&p = new SN&&&&&&&&p-&num = pos++;&&&&&&&&p-&next = NULL;
&&&&&&&&q-&next =&&&&&&&&q = q-&&&&&}
&&&&if( c &= 0 && c & len )&&&&{&&&&&&&&q = *s;&&&&&&&&while( c &= 0 )&&&&&&&&{&&&&&&&&&&&&--c;&&&&&&&&&&&&q = q-&&&&&&&&&}&&&&&&&&p-&next =&&&&}}
//不带头节点void creatList1(SNode** s, int len, int c){&&&&int pos = 0;&&&&int l =&&&&SNode *p, *q;&&&&*s = new SN&&&&(*s)-&num = pos++;&&&&(*s)-&next = NULL;&&&&--l;&&&&q = *s;&&&&while(l--)&&&&{&&&&&&&&p = new SN&&&&&&&&p-&num = pos++;&&&&&&&&p-&next = NULL;
&&&&&&&&q-&next =&&&&&&&&q = q-&&&&&}&&&&if( c &= 0 || c & len )&&&&{&&&&&&&&q = *s;&&&&&&&&while( c-- )&&&&&&&&{&&&&&&&&&&&&q = q-&&&&&&&&&}&&&&&&&&p-&next =&&&&}}
void printList(SNode *s, int len){&&&&SNode *p =&&&&while(p && len--)&&&&{&&&&&&&&cout && p-&num && " ";&&&&&&&&p = p-&&&&&}&&&&cout &&}
SNode* checkList(SNode *s){&&&&bool flag =&&&&SNode *low, *&&&&low =&&&&fast =&&&&while( low != NULL && fast != NULL )&&&&{&&&&&&&&low = low-&&&&&&&&&fast = fast-&next-&&&&&&&&&if( low == fast )&&&&&&&&{&&&&&&&&&&&&flag =&&&&&&&&&&&&&&&&&&&&}&&&&}
&&&&if( flag )&&&&{&&&&&&&&fast =&&&&&&&&while( low != fast )&&&&&&&&{&&&&&&&&&&&&low = low-&&&&&&&&&&&&&fast = fast-&&&&&&&&&}&&&&&&&&&&&&}&&&&return NULL;}
int main(){&&&&SNode *s;&&&&SNode *p;&&&&creatList1(&s, 20, 13);&&&&printList(s, 25);&&&&p = checkList(s);&&&&cout && p-&num &&&&&&return 0;}
今日西电招聘安排
老校区　114阶梯教室14:30-18:30&&大学生活动中心116招聘室（南校区）19:00&21:00&&西安电子科技大学北校区阶梯教室11419：00&&
&倒计时：3&天(周一)
阶梯教室11016:30&&
北校区阶梯教室110室9：30-12：00&&
阶教1：30&&
倒计时：4&天(周二)
北校区阶梯教室:30&&北校区西大楼420教室10：00---12:00&&
&倒计时：5&天(周三)
老校区阶梯教11019:00 ~ 21:00&
电子工程学院报告厅14:00-16:00&&
新校区D楼:00&&
倒计时：16&天(周日)
南校区D-:30&
阶梯教室:30&&
&倒计时：17&天(周一)
阶梯教室:30&&西电多媒体阶梯教室J:00&&南校区大学生活动中心11618:30软件开发专场，现场笔试&阶梯教学楼110室14:00-16:00&&
阶教110教室10：00-12：00&&待定&&&
&倒计时：18&天(周二)
待定18:30-20:00&&南校区D楼2：30&&阶梯教室110 （老校区）14:00&&新校区D2：45&
南校区大学生活动中心116室16：00&&北校区西大楼420教室19:30-21:30&&
&倒计时：19&天(周三)
北校区阶教:00&&
新校区D楼211室18:00&&新区D楼:00&&
&倒计时：24&天(周一)
图书馆3楼报告厅（本部）19：00&
新校区D21219:00&&
新校区大学生活动中心:00&&&
南校区D楼21216:00现场笔试&
&倒计时：25&天(周二)
南校区D楼:00&&北校区阶梯教室:00&&
南校区D楼212教室18:30-20:30&&
倒计时：26&天(周三)
老校区阶梯教室110室19：00-21：00&&&
（南校区） A楼:00西安分公司&
北校区教室楼阶梯教室：00宣讲会后直接笔试，请携带简历入场&阶梯教室1：00&&
&倒计时：27&天(周四)
南校区大学生活动中心116室19：00现场收简历
南校区D:00&&
阶梯楼114室14:00-16:00&&南校区D楼:45&&北校区阶梯教室11016:30&&
阶梯教室11019:00&&
&倒计时：28&天(周五)
待定14：00-18：00&&郭杜校区大学生活动中心14:00-17:00&&图书馆三楼报告厅18:30-20:30&
链表的逆转，这个要注意的一点就是链表的指针位置。（工作笔试常见题）
/*链表的逆转，这个要注意的一点就是链表的指针位置。指针仅仅代表节点的位置。每次改变后如果需要从头开始遍历要保存其头节点的信息。另外new创建的节点需要通过delete进行释放。&*/&#include &iostream&class node{public:node *};typedef node *//创建链表&link createlist(){link head,p;head=NULL;ch=getchar();while(ch!='\n'){p=p-&data=p-&next=head=p;ch=getchar();}}//释放内存空间&void deletelist(link head){while(head){p=head=head-&}}&//链表的逆置&link invert(link x){link p,q,r;p=x;q=NULL;while(p!=NULL){r=q;q=p;p=p-&q-&next=r;}}int main(int argc, char *argv[]){link head=createlist();link h=while(head){cout&&head-&data&&" ";head=head-&}cout&&link i=invert(h);link i_2=i;while(i){cout&&i-&data&&" ";i=i-&}while(i_2){tmp=i_2;i_2=i_2-&}return 0;}
站长在关注