asm, c, c++ are my all
-- Core In Computer
posts - 139,  comments - 123,  trackbacks - 0

C++面试题集4

一. 华为一道面试题-1-n排序

有N个大小不等的自然数(1--N),请将它们由小到大排序。
要求程序算法:时间复杂度为O(n),空间复杂度为O(1)。

网上转的,一开始也没有注意到最开始的半句。

算法:N个不等的自然数1~N,排序完成后必然为1~N。所以可以一次遍历,遇到a[i]!=i的就把a[i]和a[a[i]]交换。

void sort(int a[], int n)
{
 int i;
 int t; /*临时变量:空间复杂度O(1)*/

 for (i=1; i<n+1; i++) /*时间复杂度O(n)*/
 {
 while(a[i]!=i)
  {
 t = a[a[i]];
 a[a[i]] = a[i];//排好一个元素
 a[i] = t;
  }
 }
}

二. 一次遍历 找 链表倒数第n个节点

 一道面试题目,阿明和晨晨看到并且告诉我答案的。要求通过一次遍历找到链表中倒数第n个节点,链表可能相当大,可使用辅助空间,但是辅助空间的数目必须固定,不能和n有关。
算法思想:两根指针,第一根先出发,相距n步后第二根出发。然后同时步进,直到第一根指针达到末尾。

struct iNode {
int value;
iNode * next;
};
iNode * getresult(iNode * head,int n)
{

iNode *pfirst;
iNode *psecond;

pfirst=head;
int counter;

for(counter=0;counter<n;counter++) {
 pfirst=pfirst->next;
}

psecond=head;

while(pfirst!=NULL) {
 pfirst=pfirst->next;
 psecond=psecond->next;
}

return psecond;

}

三. VC++学习笔记

1.       日期转成字符串:

   COleDateTime    ww;
ww=COleDateTime::GetCurrentTime();
AfxMessageBox(ww.Format("%Y-%m-%d %H:%M:%S"));

2.       字符串转成日期:

COleDateTime dt;

       dt.ParseDateTime(“2006-08-08 08:08:08”);

3.       资源文件

资源文件名:xxx.rc,其中要包含的主要文件:resource.h和afxres.h

4.       vc开发环境没有自动提示时:

   删除 目录下的ncb文件 ,再打开一般就ok了

5.       利用_variant_t 取数据库数据的方法:

   _variant_t ibb;

       ibb=(_variant_t)rs->GetCollect("inta");

       if(ibb.vt!=VT_NULL)

       {

              m_b=ibb.lVal;

       }

6.       平时取记录集字段值的方法:

   (LPCTSTR)(_bstr_t)rs->GetCollect("datea")

7.       DoModal()可以返回两个结果 IDOK,IDCANCEL,他们都是int型,分别是:1,2。通过EndDialog(IDOK)的方式返回。

8.       一般将数据库连接方面的信息放到app中。则AfxGetApp()非常重要,如;

   CAdo2App* mapp=(CAdo2App*)AfxGetApp();

   Map->conn->Execute(sql,NULL,adCmdText);

9.       DECLARE_DYNCREATE(类名),IMPLEMENT_DYNCREATE(类名,基类名)  使得由CObject继承来的类在程序运行的时候能够动态的创建。

10.   DECLARE_DYNAMIC(类名),IMPLEMENT_DYNAMIC(类名,基类名)  可以在运行时获得该类的信息

11.   DECLARE_SERIAL(类名),IMPLEMENT_SERIAL(类名,基类名,0)为一个可以串行化的CObject派生类产生必要的C++标题代码

12.   获得文档的方法: CMainFrame * pFrame=(CMainFrame *) AfxGetMainWnd();

CPClientDoc * pDoc =(CPClientDoc *) pFrame->GetActiveDocument();
 

13.   获得视图的方法:CMainFrame * pFrame=(CMainFrame *) AfxGetMainWnd();

myView =(CPClientView*) pFrame->GetActiveView();

14.   如果要引用全局变量或者全局方法,须在当前类中引入:extern 名字;

posted on 2006-10-19 21:11 Jerry Cat 阅读(3876) 评论(10)  编辑 收藏 引用

FeedBack:
# re: C++面试题集4
2006-10-19 21:12 | Jerry Cat
不知here有没有南京的网友, 我以前南京的一个同学赵小姐要我帮忙发个租房消息, 某虽不懂但老同学的事也不好推, 将就如下:

现有位于南京市江宁区"武夷花园"小区的三室一厅住房一套, 水,电,气齐全, 室内有热水器, 电视机及床, 衣柜等简单家具. 整租, 与人合租均可. 联系人: 赵小姐 电话:025-83909202  回复  更多评论
  
# re: C++面试题集4
2006-10-21 00:39 | 冬天¤不回来
面试题考快速思维,但不难,毕竟他要出的题目是要在15分钟内可以完成得了的.  回复  更多评论
  
# re: C++面试题集4
2006-10-23 23:08 | Jerry Cat
然也  回复  更多评论
  
# re: C++面试题集4
2006-12-10 23:31 | hzl
我怎么觉得你们把问题还是看复杂了呢?我看错了?
一. 华为一道面试题-1-n排序

有N个大小不等的自然数(1--N),请将它们由小到大排序。
要求程序算法:时间复杂度为O(n),空间复杂度为O(1)。
结果就是1-n还排什么啊?直接构建一个数组啊;
for(i=1;i<=n;i++)
array[i]=i;
  回复  更多评论
  
# re: C++面试题集4
2006-12-20 11:37 | crazytrain@163.com
第一题:空间复杂度为O(1) 我对这个概念基本上不记得啦,,感觉他的用意是用尽可能少的空间来实现
假如是这样的话,你那个t 变量也是多余的,,交换两个值的话不用中间变量也可以实现的 ,用异或来做  回复  更多评论
  
# re: C++面试题集4
2006-12-20 11:47 | crazytrain@163.com
hzl,我好佩服你,这样的答案也被你想得出来,严格来说是正确的,但是我想华为要的不是这样的答案 ^_^  回复  更多评论
  
# re: C++面试题集4
2006-12-24 22:41 | xiaoxiami
laji  回复  更多评论
  
# re: C++面试题集4
2007-06-07 23:17 | 星梦情缘
嘿嘿  回复  更多评论
  
# re: C++面试题集4
2007-07-19 16:58 | Ken
@crazytrain@163.com


对于一般的排序,好像没有时间复杂度为O(n),空间复杂度为O(1)的排序算法吧,至少据我所知是没有。  回复  更多评论
  
# re: C++面试题集4
2007-10-18 12:38 | Jeffrey Hua
空间复杂度为O(n),时间复杂度为O(1)
这个问题可以参照<<programming pearls>>书中的讨论.
  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2007年6月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(7)

随笔档案

最新随笔

搜索

  •  

最新评论

阅读排行榜

评论排行榜