ITeye博客

vergilwang的博客

vergilwang · 共 341 篇文章

在 N 条水平线与 M 条竖直线构成的网格中,放 K 枚石子

【题目描述】 在 N 条水平线与 M 条竖直线构成的网格中,放 K 枚石子,每个石子都只能放在网格的交叉点上。问在最优的摆放方式下,最多能找到多少四边平行于坐标轴的长方形,它的四个角上都恰好放着一枚石子。 【输入】 输入文件包含多组测试数据。 第一行,给出一个整数T,为数据组数。接下来依次给出每组测试数据。 每组数据为三个用空格隔开的整数 N,M,K。 3 3 3 8 4 5 13 7 14 86 【输出】 对于每组测试数据,输出一行"Case #X: Y",其中X表示测试数据编号,Y表示最多能找到的符合条件的长方形数量。所有数据按读入顺序从1开始编号。 Case #1: 5 Case #2…

2013-04-08 00:11 · Algorithm · 评论(0)

HashMap用法

map是STL的一个关联容器,它提供一对一(其中第一个可以称为关键字,每个关键字只能在map中出现一次,第二个可能称为该关键字的值)的数据处理能力,由于这个特性,它完成有可能在我们处理一对一数据的时候,在编程上提供快速通道。这里说下map内部数据的组织,map内部自建一颗红黑树(一种非严格意义上的平衡二叉树),这颗树具有对数据自动排序的功能,所以在map内部所有的数据都是有序的,后边我们会见识到有序的好处。 下面举例说明什么是一对一的数据映射。比如一个班级中,每个学生的学号跟他的姓名就存在着一一映射的关系,这个模型用map可能轻易描述,很明显学号用int描述,姓名用字符串描述(本篇文章中不用…

2013-04-07 16:14 · Data structure · C++ · 评论(0)

C运算符优先级

优先级 运算符 名称或含义 使用形式 结合方向 说明 1 [] 数组下标 数组名[常量表达式] 左到右 () 圆括号 (表达式)/函数名(形参表) . 成员选择(对象) 对象.成员名 -> 成员选择(指针) 对象指针->成员名 2 - 负号运算符 -表达式 右到左 单目运算符 (类型) 强制类型转换 (数据类型)表达式 ++ 自增运算符 ++变量名/变量名++ 单目运算符 -- 自减运算符 --变量名/变量名-- 单目运算符 * 取值运算符 *指针变量 单目运算符 & 取地址运算符 &变量名 单目运算符 ! 逻辑非运算符 !表达式 单目运算符 ~ 按位取反运算符 ~表达式 单目运算符 siz…

2013-04-05 20:01 · C++ · 评论(0)

2012 Microsoft Intern Hiring Written Test

2012 Microsoft Intern Hiring Written Test 1. Suppose that a Selection Sort of 80 items has completed 32 iterations of the main loop. How many items are now guaranteed to be in their final spot (never to be moved again)? (A) 16 (B) 31 (C) 32 (D) 39 (E) 40 2. Which Synchronization mechanism(s) is/are…

2013-04-05 17:28 · Algorithm · 评论(0)

九大排序算法再总结

如果要转载,需要注明出处: http://blog.csdn.net/xiazdong 本文是http://blog.csdn.net/xiazdong/article/details/7304239的补充,当年看了《大话数据结构》总结的,但是现在看了《算法导论》,发现以前对排序的理解还不深入,所以打算对各个排序的思想再整理一遍。 本文首先介绍了基于比较模型的排序算法,即最坏复杂度都在Ω(nlgn)的排序算法,接着介绍了一些线性时间排序算法,这些排序算法虽然都在线性时间,但是都是在对输入数组有一定的约束的前提下才行。 这篇文章参看了《算法导论》第2、3、4、6、7、8章而总结。 算法的由来:…

2013-04-05 16:05 · Algorithm · 评论(0)

const 指针与指向const的指针

const 指针与指向const的指针 当使用带有const的指针时其实有两种意思。一种指的是你不能修改指针本身的内容,另一种指的是你不能修改指针指向的内容。听起来有点混淆一会放个例子上来就明白了。 先说指向const的指针,它的意思是指针指向的内容是不能被修改的。它有两种写法。 constint* p; (推荐) intconst* p; 第一种可以理解为,p是一个指针,它指向的内容是constint类型。p本身不用初始化它可以指向任何标示符,但它指向的内容是不能被改变的。 第二种很容易被理解成是p是一个指向int的const指针(指针本身不能被修改),但这样理解是错误的,它也是表示的是指…

2013-04-04 16:59 · C++ · 评论(0)

Introduction to Algorithm 6.3-3[Second Version]

证明: (1)对于h=0, 即叶子结点的个数,由6.1-7习题可知,叶子结点的个数最多为ceiling(n/2)=ceiling(n/2^(h+1)),即初始化成立。 (2)假设h=x成立,即高度为x的结点最多有ceiling(n/2^(x+1)), 那么对于高度为h=x+1的结点应该为高度为x的父结点,所以高度为x+1的结点个数最多为ceiling(n/2^(x+1))/2=ceiling(n/2^(x+2))=ceiling(n/2^(h+1)). 命题得证。

2013-04-04 10:43 · Algorithm · 评论(0)

斐波那契数列取模(大数)分治算法

斐波那契数列取模(大数)分治算法 这是算法课程上完分之策略后老师留的一道题目: 菲波那契数列如下:1,1,2,3,5,8,13,21,34......其中a[1] = 1, a[2] = 1, a[n]=a[n-1]+a[n-2](n>=3)。对给定的下标n,求解a[n]%1997的值. 其中测试数据n是整数范围内。 这个题目,主要是用到很关键的一个数学知识,斐波那契数列的求法,可以转换为矩阵的连乘,矩阵的n此方算法又可以用分治的算法。 而且又有理论依据:(n*m)%c=[ (n%c)*(m%c) ]%c ; (n+m)%c=[ (n%c)+(m%c) ]%c ,所以过程中的结果可以随时取模…

2013-04-01 17:03 · Algorithm · 评论(0)

Fast implementation/approximation of pow() function in C/C++

老外的帖子 Sure - it's easy if you have exponential and natural log functions. Since y = x^n , you can take the natural log of both sides: ln(y)= n*ln(x) Then taking the exponential of both sides gives you what you want: y = exp(n*ln(x)) If you want something better, the best place I know to look is Abr…

2013-03-29 16:42 · Algorithm · C++ · 评论(0)

C++ static

类中的静态成员真是个让人爱恨交加的特性。我决定好好总结一下静态类成员的知识点,以便自己在以后面试中,在此类问题上不在被动。 静态类成员包括静态数据成员和静态函数成员两部分。 一 静态数据成员: 类体中的数据成员的声明前加上static关键字,该数据成员就成为了该类的静态数据成员。和其他数据成员一样,静态数据成员也遵守public/protected/private访问规则。同时,静态数据成员还具有以下特点: 1.静态数据成员的定义。 静态数据成员实际上是类域中的全局变量。所以,静态数据成员的定义(初始化)不应该被放在头文件中。 其定义方式与全局变量相同。举例如下: xxx.h文件 class…

2013-03-27 22:29 · C++ · 评论(0)

C++共享变量机制

在程序设计中如何实现不同的函数模块之间的数据共享,是程序设计中的关键技术问题。 本文以C++为例,详细阐述了面向对象程序设计中各种方式数据共享的实现机制。 C++是目前应用广泛的一种面向对象程序设计语言,它比较适合于编写大型复杂程序。它所提供的数据共享机制具有广泛的代表性,能够很好的解决程序设计中数据的共享。 1、使用局部变量和全局变量共享 数据使用局部变量能够在调用和被调用函数之问通过参数传递实现不同函数块之问的数据共享【局部变量具有局部作用域,能很好地实现函数之间的数据隐蔽。但在传递过程中需要很大的系统开销,故一般只用于传递少量的数据。 全局变量具有文件作用域。全局变量所存储的数据在程序…

2013-03-27 22:23 · C++ · 评论(0)

C++ Public, Protected, Private

当private,public,protected单纯的作为一个类中的成员权限设置时: private: 只能由该类中的函数、其友元函数访问,不能被任何其他访问,该类的对象也不能访问. protected: 可以被该类中的函数、子类的函数、以及其友元函数访问,但不能被该类的对象访问 public: 可以被该类中的函数、子类的函数、其友元函数访问,也可以由该类的对象访问 注:友元函数包括两种:设为友元的全局函数,设为友元类中的成员函数<wbr style="line-height:25px"><div style="line-height:25px"><span style=""><span …

2013-03-27 22:02 · C++ · 评论(0)

C++class默认生成4个函数

【C/C++和指针】类默认生成的四个函数 序:对于一个空类,编译器默认生成四个成员函数:默认构造函数、析构函数、拷贝构造函数、赋值函数 一,默认构造函数 默认构造函数(default constructor)就是在没有显式提供初始化式时调用的构造函数。它由不带参数的构造函数,或者为所有的形参提供默认实参的构造函数定义。如果定义某个类的变量时没有提供初始化式就会使用默认构造函数。 如果用户定义的类中没有显式的定义任何构造函数,编译器就会自动为该类型生成默认构造函数,称为合成的构造函数(synthesized default constructor)。 C++语言为类提供的构造函数可自动完成对象…

2013-03-27 21:55 · C++ · 评论(0)

Dead Lock

产生死锁的必要条件 虽然进程在运行过程中,可能发生死锁,但死锁的发生也必须具备一定的条件,死锁的发生必须具备以下四个 必要条件 。 **1)互斥条件:**指进程对所分配到的资源进行排它性使用,即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源,则请求者只能等待,直至占有资源的进程用毕释放。 **2)请求和保持条件:**指进程已经保持至少一个资源,但又提出了新的资源请求,而该资源已被其它进程占有,此时请求进程阻塞,但又对自己已获得的其它资源保持不放。 **3)不剥夺条件:**指进程已获得的资源,在未使用完之前,不能被剥夺,只能在使用完时由自己释放。 **4)环路等待条件:**指…

2013-03-27 19:51 · Linux · 评论(0)

进程与线程

进程和线程的区别 收藏 简而言之,一个程序至少有一个进程,一个进程至少有一个线程. 线程的划分尺度小于进程,使得多线程程序的并发性高。 另外,进程在执行过程中拥有独立的内存单元,而多个线程共享内存,从而极大地提高了程序的运行效率。 线程在执行过程中与进程还是有区别的。每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。但是线程不能够独立执行,必须依存在应用程序中,由应用程序提供多个线程执行控制。 从逻辑角度来看,多线程的意义在于一个应用程序中,有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用,来实现进程的调度和管理以及资源分配。这就是进程和线程的重要区别。 …

2013-03-27 19:39 · Linux · 评论(0)