Chinaunix首页 | 论坛 | 博客
  • 博客访问: 999307
  • 博文数量: 128
  • 博客积分: 10012
  • 博客等级: 上将
  • 技术积分: 2050
  • 用 户 组: 普通用户
  • 注册时间: 2008-10-15 17:49
文章分类

全部博文(128)

文章存档

2011年(16)

2009年(57)

2008年(55)

分类: C/C++

2008-10-17 13:59:11

今天仔细看了一下这四个题目,貌似比较经典,目前只收集到相关的思路和个别题目的解法,不断更新中
(1)
一个整数数列,元素取值可能是0~65535中的任意一个数,相同数值不会重复出现。0是例外,可以反复出现。
请设计一个算法,当你从该数列中随意选取5个数值,判断这5个数值是否连续相邻。
注意:
- 5个数值允许是乱序的。比如: 8 7 5 0 6
- 0可以通配任意数值。比如:8 7 5 0 6 中的0可以通配成9或者4
- 0可以多次出现。
- 复杂度如果是O(n2)则不得分。

(2)
设计一个算法,找出二叉树上任意两个结点的最近共同父结点。
复杂度如果是O(n2)则不得分。

(3)
一棵排序二叉树,令 f=(最大值+最小值)/2,设计一个算法,找出距离f值最近、大于f值的结点。
复杂度如果是O(n2)则不得分。

(4)
一个整数数列,元素取值可能是1~N(N是一个较大的正整数)中的任意一个数,相同数值不会重复出现。设计一个算法,找出数列中符合条件的数对的个数,满足数对中两数的和等于N+1。
复杂度最好是O(n),如果是O(n2)则不得分。
 
思路分析
1.非0最大-非0最小+1 <=5 ==> 非0最大-非0最小 <=4

2.如果每个节点包含父亲指针,把两个节点到根的路径都记录下来,两条路径的最后面的元素肯定相同,
从两条路径的最后一个元素向前比较,直到第一次出现分叉为止,就可以找到最近节点。复杂度为O(n),
路径最长可能是n
如果不包含父亲节点,那就先前序遍历二叉树,遍历的时候可以像哈夫曼树那样左右01编号,
记录给定两节点的到达路径,最后比较两个0,1序列的前面位数,直到出现不相等为止,就找到最近父节点,
复杂度也是O(n)

3.找出最大值,最小值,复杂度都是O(h),然后搜索f,可以找到f应该插入的位置,复杂度也是O(h),
再找f的后继,复杂度也是O(h),h最大可能是n,所以总体最坏情况复杂度就是O(n)

4.先排序,复杂度O(nlgn),然后用两个指示器(front和back)分别指向第一个和最后一个元素,如果
A[front]+A[back]>N+1,则back--;
如果A[front]+A[back]=N+1,则计数器加1,back--,同时front++;
如果A[front]+A[back] 重复上述步骤,O(n)时间找到所有数对,总体复杂度为O(nlgn)
 
题目分析
第1题:首先扫描一遍求出非0平均值,然后再扫描一遍即可判断,复杂度:O(n)
第2题,是一个送分题,可以设计一个相当巧妙的数据结构,其复杂度为O(n)
第3题,也是送分题,扫描几次即可
第4题,送分题。牺牲空间即可完成。
 
 
具体算法
(1)
思路是 非0最大值-非0最小值 <=数组长度-1
我觉得这道题的前提非常重要
public boolean isContiguous(int[] array)
  {
  int min=-1;
  int max=-1;
  for(int i=0;i   {
  if(array[i]!=0)
  {
  if(min==-1||min>array[i])
  {
  min=array[i];
  }
  if(max==-1||max   {
  max=array[i];
  }
  }
  }
  return max-min <=array.length-1;
  }
 
 
(4)
关键点在于创建一个Hash表,典型的以空间换时间:-)   


    public static int getSumCount(int[] array,int N)
    {
    int count=0;
    //创建哈希表
        int[] hashTable=new int[N+1];
        for(int i=0;i         {
        hashTable[array[i]]=array[i];
        }
        for(int i=0;i         {
        //如果是数对中较小的整数(防止重复计数)
        //并且配对的整数存在
                //并且不等于与之配对的整数,因数列不存在重复整数
                if(array[i] <=(N+1)/2&&hashTable[N+1-array[i]]!=0&&array[i]*2!=N+1)
        {
            count++;
        }
        }
    return count;
    }
阅读(2240) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~