ITeye博客

vergilwang的博客

vergilwang · 共 341 篇文章

2n个整数分为两组,使两组和差的绝对值最小

http://blog.sina.com.cn/s/blog_6f194ed3010114vt.html 最近建模看到作业这个题,一开始想了很久。在网上发现竟然没有完备的算法。不过最后想到一个可以Lingo实现的线性规划模型。 严格说,这不是一个算法,Lingo是如何实现0-1规划的我并不清楚。有可能也是枚举法,不过对于具体问题至少可以解决。因为是TeX编译的,重新打一遍太麻烦,所以正文用截图。最后提一个不成熟的算法。 问题重述:有2n个整数,试将其平均分为两组(每组n个),使两组元素和的差值最小。 (这里有一点打错了。“从另一个角度看”后的等式要加绝对值号。另外这里要注意需要限定S1较大,…

2013-04-27 15:22 · Algorithm · 评论(0)

在数组中找出3个数使得它们和为0

题目: 给定一个集合S,试找出3个数a,b,c,使得a+b+c=0。也即从集合中找出所有的和为0的3个数。 例如:集合S={-1,0,1,2,-1,4},则满足条件的3个数有2对: (-1, 0, 1)和(-1, 2, -1) 。注意(-1,1,0)与(-1,0,1)算同一个解,所以不用重复考虑。当然该例子集合的解也可以写成: (0, 1, -1)和(2, -1, -1) 。 解法: 这个问题也被称作3数和问题,3数和问题是下面这个问题的扩展。 问题:给定一个n个元素的集合S,找出S中满足条件的整数对 A,B**, 使得 A+B = K 。** 假定集合S已经排好序的话,则上面这个问题可以在…

2013-04-27 11:56 · Algorithm · 评论(0)

最长重复子串

问题描述 给定一个字符串,求出其最长重复子串 例如:abcdabcd 最长重复子串是 abcd,最长重复子串可以重叠 例如:abcdabcda,这时最长重复子串是 abcda,中间的 a 是被重叠的。 直观的解法是,首先检测长度为 n - 1 的字符串情况,如果不存在重复则检测 n - 2, 一直递减下去,直到 1 。 这种方法的时间复杂度是 O(N * N * N),其中包括三部分,长度纬度、根据长度检测的字符串数目、字符串检测。 改进的方法是利用后缀数组 后缀数组是一种数据结构,对一个字符串生成相应的后缀数组后,然后再排序,排完序依次检测相邻的两个字符串的开头公共部分。 这样的时间复杂度…

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

[笔试题] Google笔试题整理(超全!)附部分答案

[笔试题] Google笔试题整理(超全!)附部分答案 写出这样一个函数 ,输入一个 n, 输出从1到这个数字之间的出现的1的个数,比如f(13)等于6; f(9)等于1; 网上有很多这道题的解法,大多采用穷举法。这把这个算法题变成了程序设计,这道题,我认为是总结一个递推公式,然后用递推法实现,比较好。后来在网上考证了一下,这道题本来也是让总结一个数学函数即可,无需编程。既然写了,就贴出来,发表一下自己的解法。这道题还有另一半,当f(n)=n是,最小的n是多少?本人还没有好的方法,所以就不贴了。 下面的程序是上半部java实现的。 /* 可以推出下列递推公式: * f(n)=(a>1?s:n…

2013-04-26 14:13 · Algorithm · 评论(0)

C++ STL Pair

Pair类型概述 pair是一种模板类型,其中包含两个数据值,两个数据的类型可以不同,基本的定义如下: pair<int, string> a; 表示a中有两个类型,第一个元素是int型的,第二个元素是string类型的,如果创建pair的时候没有对其进行初始化,则调用默认构造函数对其初始化。 pair<string, string> a("James", "Joy"); 也可以像上面一样在定义的时候直接对其初始化。 由于pair类型的使用比较繁琐,因为如果要定义多个形同的pair类型的时候,可以时候typedef简化声明: typedef pair<string, string> auth…

2013-04-26 11:22 · Data structure · C++ · 评论(0)

求一个字符串中连续出现次数最多的子串

http://blog.csdn.net/imcdragon/article/details/6838565 解答二 http://hi.baidu.com/icyday315/item/040aadab454c8a97151073da 合并思路(不能重复abcdabcd 就不行了,abcda是最长重复子串) /* Author:Mcdragon Date:15-07-1121:17 Description:求一个字符串中连续出现次数最多的子串. 基本算法描述: 给出一个字符串abababa 1.穷举出所有的后缀子串 substrs[0]=abababa; substrs[1]=bababa…

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

amazon题代码

First Phone Interview: 1.提出尽可能多的方法使一个method可以返回多个不同type的值 2.reverse string 比如 "I have a dream" -> "dream a have I" 3.判断一个binary tree是不是对称的 Second Phone Interview: 1.给a list of number,返回前top K个(内存足够怎么做,内存不够怎么做) 2.用OOD来电梯 3.找两个链表的交集 Onsite 6轮 1轮HR 1轮午餐 4轮技术 (亚马逊web services team) 1.设计个电话本, 可以用那些数据结构 …

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

字符串面试题

一般面试字符串的题目分四种:1, 基本运算(求长度,连接,比较)2. 格式转换(atoi, itoa) 3.字符串翻转 4. 模式匹配。 1. 基本运算 a. 赋值操作 函数原型:int StrAssign(const char *s, char *t) 函数说明:将s的内容付给t 函数定义: int StrAssign(const char *s, char *t){ <wbr><wbr>char *p = t;<br><wbr><wbr><wbr><wbr>while(*s !='\0'){<br><wbr><wbr><wbr><wbr>*p++ = *s++;<br><wbr><wbr…

2013-04-25 15:45 · Algorithm · 评论(0)

在继承中派生类成员的访问权限测试

派生类对自身基类的private成员没有访问权限,对基类对象的protected成员没有访问权限,对派生类对象的(基类之外)的private和protected成员具有访问权限。 由于C++基础不好,平时也不用它,导致今天才纠正一个非常关键的错误,类的访问权限,是对类而言的,而不是对类的对象而言的。一直都理解错了。这句话都没脸写出来,还是写下来了。 下面是一段简答的测试代码。对于调用成员函数的对象test,基类形参,派生类形参三者的访问权限做了测试如下: [cpp] view plain copy print ? #include<iostream> usingnamespacestd; c…

2013-04-24 19:44 · Linux · C++ · 评论(0)

C++中 public,protected, private 访问标号小结

C++中 public,protected, private 访问标号小结 第一:private, public, protected 访问标号的访问范围。 private:只能由1.该类中的函数、2.其友元函数访问。 不能被任何其他访问,该类的对象也不能访问。 protected:可以被1.该类中的函数、2.子类的函数、以及3.其友元函数访问。 但不能被该类的对象访问。 public:可以被1.该类中的函数、2.子类的函数、3.其友元函数访问,也可以由4.该类的对象访问。 注:友元函数包括3种:设为友元的普通的非成员函数;设为友元的其他类的成员函数;设为友元类中的所有成员函数。 第二:类的…

2013-04-24 14:58 · C++ · 评论(0)

amazon笔试题

1.判断一年是否为闰年的方法 2.非递归实现exists方法 template <class T> class BinaryTree{ protected: T* _data; BinaryTree<T> * _left; BinaryTree<T> * _right; }; template <class T> class BST:public BinaryTree<T>{ public: virtual bool exists(const T& item> const; }; 3.找到下面的bugs #include<stdio.h> #include<malloc.h> void fo…

2013-04-24 14:29 · Algorithm · 评论(0)

google玻璃球

有一栋100层高的大楼,给你两个完全相同的玻璃球。假设从某一层开始,丢下玻璃球会摔碎。那么怎么利用手中的两个球,用什么最优策略知道这个临界的层是第几层?? 解题思路: 假如只有一个球,那很显然,只有一个办法:从第一层开始投,如果没碎再试第二层、第三层..... 现在有两个球,我们应该利用第一个球缩小临界楼层所在的楼层范围,可能会想到第一个球先从50层开始投,如果碎了,再用最后一个球从第一层开始投,最多到49楼肯定可以找到临界楼层,如果没碎那就说明临界楼层在50-100中,此时继续尝试75楼.... 可惜,上面的方法并非是最好的。因为最坏情况的投掷次数分布不均匀。比如,如果50楼碎了,此时最坏…

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

腾讯猜字游戏

A、B两人玩猜字游戏,游戏规则如下: A选定一个 [1,100]之间的数字背对B写在纸上,然后让B开始猜; 如果B猜的偏小,A会提示B这次猜的偏小; 一旦B某次猜的偏大,A就不再提示,此次之后B猜的偏小A也不会再提示,只回答猜对与否。 请问:B至少要猜( )次才能保证猜对?在这种策略下,B第一次猜测的数字是( )。 <wbr></wbr> 首先阅读题目,一个很重要的信息点就是: 一旦B某次猜的偏大,A就不再提示,此次之后B猜的偏小A也不会再提示,只回答猜对与否 。如果没有这个条件,或者说改变这个条件,改为: 如果B猜的偏大,A会提示B这次猜的偏大 那么相信大家都会给出答案,那就是用二分法,只…

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

C++ STL博客

http://www.cnblogs.com/miao11621/archive/2012/08/31/2665565.html

2013-04-23 18:32 · C++ · 评论(0)

阿里Set

上次面阿里巴巴。面试官问了我这样一个问题,“C++ STL中的set是如何实现的”。当时只答了二叉树,回来查下书,原来一般是红黑树,后悔没好好记住啊。。。 接着,面试官又考了我一道这样的编程题:定义一个Student结构体,包括name和age等数据,要求编程实习在set中查找一个name == "张三",age == 13的操作。 本来set自己用得不多,当时一下懵了。回来查阅《C++标准程序库》这本书,自己试着实现了下。 #include<iostream> #include<set> usingnamespacestd; /*Student结构体*/ structStudent{ st…

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