ccyy's coding zone
往前走,不要留恋路边的风景.
posts - 25,comments - 9,trackbacks - 0
     摘要:     这段时间扫了C++Primer,自己觉得比较有用的tips,仅作为自己参考...  1.如果要在多个变量中使用一个const变量,可以在一个头文件中定义,然后再其他文件中include<>  或者可以在c++的源文件中定义,然后才其他源文件中extern 2.标准头文件用#inclue<> &nb...  阅读全文
posted @ 2011-07-31 19:00 ccyy 阅读(186) | 评论 (0)编辑 收藏
   

题目:有一个链表L,其每个节点有2个指针,一个指针next指向链表的下个节点,另一个random随机指向链表中的任一个节点,可能是自己或者为空,写一个程序,要求复制这个链表的结构并分析其复杂性

 

解决方法一:

O(n)的复杂度,扫面两边即可。

                                                                 图【1】
图【1】是需要复制的链表


                                                              图【2】

如图【2】所示,ABCD是原来的链表,A’B’C’D’是复制的链表,第一遍扫描顺序复制next指针,把ABCDnext分别指向A’B’C’D’,将A’next指针指向BB’next指针指向C,依次类推

复制random指针: A’->random=A->random->next

恢复:A->next=A’->next;A’->next=A’->next->next;

 

 

解决方法二:

也是O(n)的时间复杂度。。。


                                                                    图【3】

 

如图【3】,第一次遍历将要复制的链表A’ B’ C’ D’插入员链表中,然后再一次遍历复制random指针:A->next->random=A->random->next;

恢复很简单:A->next=A->next->next;A’-next=A’->next->next;


转载请注明出处。

posted @ 2011-04-02 23:01 ccyy 阅读(4043) | 评论 (2)编辑 收藏
 

 又去微软面试了,面试的技术支持

 没算好时间,结果早到了一个多小时…2点左右HR把我领到二楼的一个房间里,等了一会儿,面试官来了。第一个面试官主要问的是项目和C语言的理解程度,问的很细,而且一个接一个,速度很快,以致与我现在基本忘记问的什么了,只记得问了调用一个函数的时候参数是怎么传的,函数调用时参数压入堆栈的顺序(回去看了<C专家编程>,里面有讲到,真是书到用时方恨少,平时真的看的书太少了),还有一些位图的结构是什么,我说是文件头然后是一堆像素,然后又问文件头由哪几个部分组成,这个真的不知道了。总之好像是想到什么问什么,还问了些汇编的东西,都是很基础的,大概面了30分钟吧结束了,然后继续在房间里等。已经在那里工作的学长汪愈舟还过来给我加了下油。

然后又进来一个面试官,先聊了下,然后让我写100!,结果我写了标准的高精度,写了三页纸,面试官很惊讶:要写那么长么,回来的时候天哥说他10行搞定,说是高精乘低精悲催,然后也问了很多的问题,主要是关于windows的,usermodekernermode的区别,函数a调用函数b在堆栈上的实现,这些基本回答了。两个同样性能的计算机,为什么一台机器打开word较快一台较慢,windows的基本输入输出方式..这两个问题杯具了。最后问了下汇编的东西,问我8086的汇编EAXEBX,很基础的。由于课堂上讲的都是AX,BX结果比较杯具,面试官提醒说EAXEBX32位机的寄存器,AX,BX16位机的寄存器。。。面试官面完大概4点多。

等了会,又进来一个面试官,这个面试官感觉比较和善,没有很多技术性的问题,先让我写了个快排,以为之前有看过,很快就解决了。然后聊了下比赛啊,项目什么的,然后问我有什么要问的.想了一会,就问了下是否需要实习什么的,基本上结束了。

希望不要又杯具的被默拒啊..没想到微软这么快就叫我去面试..

God close a door He sometimes opens another…I hope it is true.

                                             2011.3.10
posted @ 2011-03-15 17:27 ccyy 阅读(232) | 评论 (0)编辑 收藏
 

人生的第二次面试..上海旭刚市场研究有限公司..just for practice

上海市南京西路中欣大厦进去hr先给了一个张笔试题
1.
数字1,2,3,4,5,6,7,8,9,10,12,13,14,……10000遗漏了一个数字,用简便快速的方法找出这个数字,例子中是11

我写了二分查找算法,假设了这些数是存在连续的数组里面的..

void Find_lost_number()

{

         int left=1,right=10000;

         int mid;

         int lost_number;

         while(left<right)

         {

                   mid=(left+right)/2;

                   if(arr[mid]!=arr[mid-1]+1)

                   {

                            lost_number=arr[mid-1]+1;

                            break;

                   }

                   else if(arr[mid]!=arr[mid+1]-1)

                   {

                            lost_number=arr[mid+1]-1;

                            break;

                   }

                   if(arr[mid]<mid)

                            right=mid;

                   else

                            left=mid;

         }

}

后来回来请教某牛,某牛居然说小学数学题,把所有数加起来比较就行了,想想真是……原来这么简单啊,汗……….

2.给一个数组找出最小值的下标

水啊,好像线性扫描就可以了..

3.你有9个西服牌子,有两百个人,20-29的男性50人,20-29的女性50人,30-39的男性50人,30-39的女性人数50人,每个人随机选4个牌子,问如何随机分配,使不同年龄段不同性别的人得到的西服牌子尽量相同。

 

这是什么神马题目,完全没思路啊,随便写写交了..

 

等了一会儿,去面试了没想到那么轻松,感觉就是随便聊了一会,有没在实习什么的,要不要留上海之类的,工作有什么打算,还问了下薪资期望,这个不是应该最后要录取的时候问吗随便说了个六七千,…..然后还留了个任务,说完成了再聊,好像是转换数据,要我用excelSPSS都做一遍然后写个报告…..

 That’s all for today 2011.3.4

posted @ 2011-03-04 23:49 ccyy 阅读(226) | 评论 (1)编辑 收藏

     电脑中的图像类型分为两大类,一类称为点阵图(位图),一类称为矢量图。 
  点阵图顾名思义就是由点构成的,如同用马赛克去拼贴图案一样,每个马赛克就是一个点,若干个点以矩阵排列成图案。 
  数码相机拍摄的照片、扫描仪扫描的稿件以及绝大多数的图片都属于点阵图,如一个典型的点阵图: 
  把这幅图片调入Photoshop,使用菜单【图像>图像大小】就可以看到图像信息:
  注意上部像素大小中的宽度和高度,分别是400像素和225像素。 
  像素是什么?像素就是组成点阵图像中的那些点,是点阵图最小的单位。如同拼成图案的那许多马赛克一样。 
  在Photoshop状态栏左端的缩放倍数往右一些的区域,按住ALT键单击也会出现像素数量信息,如果没有状态栏可用菜单【窗口>状态栏】打开。  如果我们放大图像〖快捷键 CTRL +〗,就会看到点也同时被放大了,这时就会出现所谓的马赛克现象(也称锯齿现象)。  
    我们可以看到有许多不同颜色的小正方形,那就是被放大的像素。每个像素只能有一个颜色。 
  宽400像素,高225像素,意味这幅图像由横方向400个点、竖方向225个点组成,400x225=90000,图像的总像素数量就是9万。 
  数码相机有一个很重要的指标就是300万像素、500万像素这样的称呼,就是指拍摄出来图像中的像素总量。 

  放大缩小图像的快捷键是〖CTRL +〗〖CTRL -〗,这种放大会沿着图像的中心点放大。 
  还有一种定点放大方式是按住空格和CTRL键,用鼠标单击图像的一个部分,这样会以单击的地方作为中心放大。缩小是按住空格和ALT键单击。 
  如果缩放程度不够可重复以上操作。图像窗口的标题栏、以及Photoshop下方状态栏的左端,都会显示缩放倍数。 
  严格来说应该是先按CTRL再按空格。但是在中文Windows下这正好是默认的中文输入法切换方式。因此建议先按空格再按CTRL。 
  如果图像超过了图像窗口的大小,将在右方和下方出现滚动条,此时拉动滚动条即可移动观看区域(不是移动图像)。 
  也可按住空格键在图像中按下鼠标拖动。当鼠标开始拖动以后,空格键可以松开。 
  以上的几个快捷键是最常用的。要把它们记住,这将让你的操作变得迅速。 
    像素是不是越多越好呢?从大部分情况来说是的,图像的像素越多,记录的信息也越详细,图像的局部就越细致 



     矢量格式图象 

  假设我们写了一首新的乐曲,要把它交给唱片公司,可以通过两种方式: 
  把这首乐曲弹奏出来并录制在磁带上。 
  把这首乐曲的乐谱写下来。 
  这两种方式的最大区别在于记录的形式。 
  前者是记述性的。包含乐曲的音频信息。其中的所有信息都是固定的,如演奏速度、乐器音色等。如果你想把笛子换成排箫,那就要重新录制一遍。 
  后者是描述性的,不包含音频信息,只包含对乐曲音律的描述。如果要改变演奏速度或乐器音色,只要在乐谱中修改一下就好。 
  点阵图像就属于记述性,以点为记录的对象。而矢量图像属于描述性,以线段和计算公式作为记录的对象。 

  比如直线: 
  如果以点阵方式来记录,就是从左上角第一个点开始,到右下角最后一个点结束,记录所有像素的颜色。 
  记录这幅图像(200 x 50像素)就需要1万个信息。即使这条直线本身并没有那么多像素,但点阵方式也是完整的把整幅图的像素记录下来。 
  因此不管是一条直线还是两条三条,对于点阵图像来说都是一样的。都是去逐个记录图像中的所有像素。 

  如果用矢量来记录这条直线,只需要三个信息:直线起点坐标、直线终点坐标、直线的颜色。 
  在还原的时候就利用这三个信息去生成图像,就如同乐队把乐谱演奏出来一样。

  由于矢量的这种特点,使得它非常便于修改。 
  比如要把上图的直线旋转一下,点阵方式就需要重新记录所有改动过的像素信息。而矢量图只需要改动起点和终点的坐标就好了。 
  当放大图像的时候,点阵图像会产生模糊和锯齿。就如同录音带播放时候加速产生的变调。对图像质量是有损失的。 
  而矢量图像是根据放大后的坐标重新生成图像,不会产生模糊和锯齿。就如同乐队根据新乐谱重新演奏。对图像质量是没有损失的。 
  为什么在第一次缩小之后没有看出区别呢? 
  这是因为缩小点阵图像是不会产生模糊的,在丢弃原先的一些像素后,剩下的像素是足够描述图像的,并没有产生像素空缺。而放大后才产生了像素空缺。 

  为什么矢量图像“饱经风霜”却依旧“面不改色”呢?这就是因为前面说过的矢量图像的特点:通过记忆线段的坐标来记录图像。 
  图像放大缩小的同时坐标也放大缩小,而各个坐标之间的相对位置并没有改变。然后根据改动后的坐标重新生成图像。因此无论放大多少都不会失真。

posted @ 2011-02-15 11:05 ccyy 阅读(870) | 评论 (0)编辑 收藏
I believe someone  who is writing blog is nothing more than show himself off ,I won't be one of them any more.
posted @ 2010-10-19 20:03 ccyy 阅读(80) | 评论 (0)编辑 收藏
筛素数,在天哥的威逼利诱下改了筛素数的模板...以后PE都python了...
#Firename:pe37.py
import math
N=1000000
prime = [0 for row in range(N)]
res = []
top=0
def Prime():
    for i in range (2,N):
        prime[i]=1
    prime[0],prime[1]=0,0
    for m in range(2,N): 
        if prime[m]==1:
            prime[m]=1
            res.append(m)
            for k in range(2*m,N,m):
                prime[k]=0
tot=0
Prime()

for i in range(len(res)):
    temp=res[i]
    flag=0
    while temp>0:
        if prime[temp]!=1:
            flag=1
            break
        temp/=10
    temp=res[i]
    t=1
    while temp>0:
        temp/=10
        t*=10
    temp=res[i]
    while t>0:
        if prime[temp]!=1:
            flag=1
            break
        tmp=temp/t
        temp=temp-tmp*t
        t/=10
    if flag==0 and res[i]>10:
        top+=1
        tot+=res[i]
print tot
print top
后来发现python里面原来有直接可以求素数的函数  - -||
#prime_list(n) 返回一个list,存1 - n 内的素数
#prime_table(n) 返回一个list,用0 1 表示是不是素数        
            

posted @ 2010-08-29 21:54 ccyy 阅读(62) | 评论 (0)编辑 收藏
    继续研究C++builder,ms程序里有某个变量溢出了..但是百思不得其解..于是向万老师请教C++builder的调试方法..然后万老师教了我一个她自己调试方法..感觉很实用..类似于VC里面调试的printf();
(1)Form的方法ShowMessage(String);
这个函数可以把出你想知道的任意中间变量的值用消息框的形式显示出来。
Example:
int Varies;
Form1->ShowMessage(IntToStr(Varies));
(2)利用Form的Memo控件
可以同时查看很多变量;先在窗体中添加一个Memo控件,然后调用Memo->Lines->Add(String)把要观察的变量加进去;
Example:
float sum=0;
for(i=1;i<=100;i++)
 { 
      sum+=1.0/i;
     Form1->Memo->Lines->Add(FloatToStr(sum));
}
试过..不错~~
posted @ 2010-08-28 01:17 ccyy 阅读(309) | 评论 (0)编辑 收藏

8.24

今天去问了万老师….万老师是果然是C的牛人啊听她说她以前做的项目仰慕中听她说以前C语言和她读书的事情…..很好玩~~…

解决了一些问题:

1.      怎么使Plane和界面相符合

Plane->Align可以改

2.      Label的字体大小

Label->font

3.直接在头文件里面添加变量和通过newfield添加有区别吗

   没有

4.      Mousemove&&Mousedown&&Mouseup

Form的响应函数,研究ing

5.      Timer 的用法

MFCOnTimer类似..

6.      Scree.

7.      关于rand()

 

   感觉今天最大的收获就是学会了怎么用帮助文档以前都不知道.

   还顺便问了一下抽奖程序的问题..shmm他们说要做个抽奖程序….听万老师说的ms不是很难..原来滚动条显示名字都是假象真实的情况是产生一个随机数然后把响应的明字显示出来就可以了..

       C++builder 真的挺不错的..个人感觉比MFC简单实用

posted @ 2010-08-25 12:43 ccyy 阅读(91) | 评论 (0)编辑 收藏
研究python ing 什么都不懂的...
刷水题练python...
#Fiename:pe44.py
import math
arr = [0 for row in range(10000)]
def check(x):
    i=int(math.sqrt(x*0.2/3))-1
    while (i*(i*3-1))/2<x:
        i=i+1
    if i*(i*3-1)/2==x:
        return 1
    return 0
for i in range (1,3000):
    arr[i]=i*(i*3-1)/2
Max=0xfffffff
for i in range (1,3000):
    for j in range(i+1,3000):
        if check(arr[i]+arr[j])==1 and check(arr[j]-arr[i])==1 and arr[j]-arr[i]<Max:
            Max=arr[j]-arr[i]
print Max

posted @ 2010-08-21 22:24 ccyy 阅读(120) | 评论 (0)编辑 收藏
仅列出标题  下一页