1、来自《编程之美》的概率题：一个桶里面有白球、黑球各100个，现在按下述规则取球：的
i 、每次从通里面拿出来两个球；
ii、如果取出的是两个同色的求，就再放入一个黑球；
ii、如果取出的是两个异色的求，就再放入一个白球。
问：最后桶里面只剩下一个黑球的概率是多少？
package A1;发现黑球概率是百分之百，具体原因，大家想想吧。
import java.util.Random;
public class A1 {
public int getBall(int blackBall, int whiteBall) {
if (blackBall == 1 && whiteBall == 0) {
return 1;
}
if (blackBall == 0 && whiteBall == 1) {
return 0;
}
int black = 0;
int white = 0;
Random ram = new Random();
int ballNum = blackBall + whiteBall;
int ball1 = (int) ram.nextDouble() * ballNum + 1;
int ball2 = (int) ram.nextDouble() * ballNum + 1;
if (ball1 < blackBall) {
black++;
} else {
white++;
}
if (ball2 < blackBall) {
black++;
} else {
white++;
}
if (black == 2 || white == 2) {
return getBall(blackBall - black + 1, whiteBall - white);
} else {
return getBall(blackBall - black, whiteBall - white + 1);
}
}
public static void main(String[] args) {
int white = 0;
int black = 0;
int iterator = 1000;
A1 A = new A1();
for (int i = 0; i < iterator; ++i) {
if (A.getBall(100, 100) == 1) {
black++;
}
if (A.getBall(100, 100) == 0) {
white++;
}
}
System.out.println(black);
System.out.println((float)black / (float)iterator);
}
}
2、算法题：给你一个自然数N，求[6,N]之内的所有素数中，两两之和为偶数的那些偶数。
package A1;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
public class A2 {
public boolean isPrime(int n){
if(n<2){
return false;
}
for(int i=2;i<Math.sqrt(n);++i){
if(n%i==0){
return false;
}
}
return true;
}
public Set<Integer> find(int n){
if(n<6){
return null;
}
Set<Integer> even=new HashSet<Integer>();
List<Integer> prime=new ArrayList<Integer>();
for(int i=7;i<n;i+=2){
if(isPrime(i)){
prime.add(i);
}
}
for(int i=0;i<prime.size()-1;++i){
for(int j=i+1;j<prime.size();++j){
int sum=(prime.get(i)+prime.get(j));
if(sum%2==0){
even.add(sum);
}
}
}
return even;
}
public static void main(String[] args){
A2 A=new A2();
Set<Integer> set=A.find(100);
Iterator<Integer> it=set.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
}
}
二、9月5日，华为2014校园招聘的机试题目
通过键盘输入一串小写字母(a~z)组成的字符串。请编写一个字符串压缩程序，将字符串中连续出席的重复字母进行压缩，并输出压缩后的字符串。
压缩规则：
1、仅压缩连续重复出现的字符。比如字符串"abcbc"由于无连续重复字符，压缩后的字符串还是"abcbc"。
2、压缩字段的格式为"字符重复的次数+字符"。例如：字符串"xxxyyyyyyz"压缩后就成为"3x6yz"。
要求实现函数：
void stringZip(const char *pInputStr, long lInputLen, char *pOutputStr);
输入pInputStr： 输入字符串lInputLen： 输入字符串长度
输出 pOutputStr： 输出字符串，空间已经开辟好，与输入字符串等长；
注意：只需要完成该函数功能算法，中间不需要有任何IO的输入输出
示例
输入：“cccddecc” 输出：“3c2de2c”
输入：“adef” 输出：“adef”
输入：“pppppppp” 输出：“8p”
package A2;三、9月9日，迅雷2014校招笔试编程题：
public class A1 {
public String compression(String str){
if(str==null){
return "";
}
StringBuffer newStr=new StringBuffer();
int num=1;
char pre = str.charAt(0);
char current;
for(int i=1;i<str.length();++i){
current=str.charAt(i);
if(current==pre){
num++;
}
if(current!=pre){
if(num>1){
newStr.append(num);
}
newStr.append(pre);
num=1;
}
pre=current;
}
if(num>1){
newStr.append(num);
}
newStr.append(pre);
return newStr.toString();
}
public static void main(String args[]){
A1 A=new A1();
System.out.println(A.compression("ASGGGDSGSS"));
}
}
已知集合A和B的元素分别用不含头结点的单链表存储，函数difference()用于求解集合A与B的差集，并将结果保存在集合A的单链表中。例如，若集合A={5,10,20,15,25,30}，集合B={5,15,35,25}，完成计算后A={10,20,30}。
链表结点的结构类型定义如下：
class Node{
int data;
Node next;
}
package A3;
import java.util.HashSet;
import java.util.Set;
class Node{
int data;
Node next;
}
public class A1 {
public Node difference(Node a,Node b){
Node pre=new Node();
Node head=pre;
pre.next=a;
Node curr=a;
Set<Integer> set=new HashSet<Integer>();
while (b != null) {
set.add(b.data);
b = b.next;
}
while (curr != null) {
if (set.contains(curr.data)) {
pre.next = curr.next;
curr = curr.next;
} else {
pre = pre.next;
curr = curr.next;
}
}
a = head.next;
return a;
}
public static void main(String[] args) {
Node a = new Node();
Node b = new Node();
int aa[] = {5,10,20,15,25,30};
int bb[] = {5,15,35,25};
Node pre = a;
a.data = aa[0];
for (int i = 1; i < aa.length; ++i) {
Node temp = new Node();
temp.data = aa[i];
pre.next = temp;
pre = temp;
}
pre = b;
b.data = bb[0];
for (int i = 1; i < bb.length; ++i) {
Node temp = new Node();
temp.data = bb[i];
pre.next = temp;
pre = temp;
}
A1 A = new A1();
a = A.difference(a, b);
Node n = a;
while (n != null) {
System.out.println(n.data);
n = n.next;
}
}
}
四、9月10日，美团网2014校招研发笔试哈尔滨站
1、链表翻转。给出一个链表和一个数k，比如链表1→2→3→4→5→6，k=2，则翻转后2→1→4→3→6→5，若k=3,翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→5→6，用程序实现
package A4;
import java.util.LinkedList;
class Node{
int data;
Node next;
}
public class A1 {
public void reverse2(Node head,Node tail,int k){
if(head==null)
return;
if(k<2)
return;
if(head.next==null)
return;
if(head.next.next==null)
return;
Node pre=head;
Node curr=head.next;
Node next=curr.next;
while(k--!=0){
if(pre==head){
curr.next=tail;
}
else{
curr.next=pre;
}
if(next==null)break;
if(k==0)break;
pre=curr;
curr=next;
next=next.next;
}
head.next=curr;
}
public void reverse(Node head,int k){
Node node=head.next;
Node pre=head.next;
A1 A=new A1();
for(int i=1;i<k;i++){
node=node.next;
}
Node next=node.next;
A.reverse2(head,node.next, k);
while(next!=null){
Node h=pre;
for(int i=0;i<k;i++){
if(next==null)break;
next=next.next;
}
pre=h.next;
A.reverse2(h,next, k);
}
}
public static void main(String[] args) {
Node a = new Node();
int aa[] = {5,10,20,15,25,30};
Node pre = a;
a.data = aa[0];
for (int i = 1; i < aa.length; ++i) {
Node temp = new Node();
temp.data = aa[i];
pre.next = temp;
pre = temp;
}
Node list=new Node();
list.next=a;
A1 A = new A1();
A.reverse(list, 2);
Node n = list.next;
while (n != null) {
System.out.println(n.data);
n = n.next;
}
}
}
2、一个m*n的矩阵，从左到右从上到下都是递增的，给一个数elem，求是否在矩阵中，给出思路和代码
package A4;
public class A2 {
public static boolean isInMatrix(int n, int[][] a) {
int j = 0;
for (int i = 0; i < a.length; ++i) {
while (j < a[i].length) {
if (a[i][j] == n) {
return true;
}
if (a[i][j] > n) {
j--;
break;
}
System.out.println(a[i][j]);
if (j == a[i].length - 1) {
break;
}
++j;
}
}
return false;
}
public static void main(String args[]) {
int a[][] = { {1,2,8,9}, {2,4,9,12}, {4,7,10,13}, {6,8,11,15}};
for (int i = 0; i < a.length; ++i) {
for (int j = 0; j < a[i].length; ++j) {
System.out.print(a[i][j]);
Integer num = a[i][j];
for (int k = 0; k < 5 - num.toString().length(); k++) {
System.out.print(" ");
}
}
System.out.println();
}
System.out.println(isInMatrix(15, a));
}
}
1、分治法，分为四个矩形，配以二分查找，如果要找的数是6介于对角线上相邻的两个数4、10，可以排除掉左上和右下的两个矩形，而递归在左下和右上的两个矩形继续找，如下图所示：
2、定位法，时间复杂度O（m+n）。首先直接定位到最右上角的元素，再配以二分查找，比要找的数（6）大就往左走，比要找数（6）的小就往下走，直到找到要找的数字（6）为止，如下图所示：
五、创新工场2014校招
1、求一个正整数N的开方，不能用sqrt函数，精确度在0.001；
用牛顿2分法；
求一个数n的开方就是求y=x^2-n的零点。
一般地，对于函数f(x),如果存在实数c,当x=c时，若f(c)=0,那么把x=c叫做函数f(x)的零点。
解方程即要求f(x)的所有零点。
假定f(x)在区间（x，y）上连续
先找到a、b属于区间（x，y），使f(a)，f(b)异号，说明在区间(a,b)内一定有零点，然后求f[(a+b)/2],
①如果f[(a+b)/2]=0，该点就是零点，
如果f[(a+b)/2]<0,则在区间（(a+b)/2，b)内有零点，(a+b)/2>a，从①开始继续使用
中点函数值判断。
如果f[(a+b)/2]>0，则在区间(a,(a+b)/2)内有零点，(a+b)/2<b，从①开始继续使用
中点函数值判断。
这样就可以不断接近零点。
通过每次把f(x)的零点所在小区间收缩一半的方法，使区间的两个端点逐步迫近函数的零点，以求得零点的近似值，这种方法叫做二分法
package A5;
public class A1 {
public static float sqrt(int n){
float high=n;
float low=0;
float half=n/2;
float precision=n;
while(precision>0.001){
float s=half*half;
float temp=half;
if(s>n){
high=half;
}
if(s<n){
low=half;
}
half=(high+low)/2;
precision=Math.abs(half-temp);
}
return half;
}
public static void main(String args[]){
int n=2;
System.out.print(sqrt(n));
}
}
2、A、B两个整数集，设计一个算法，求他们的交集，尽可能高效。
package A6;
import java.util.HashSet;
import java.util.Set;
public class A2 {
public static void jiaoji(int a[],int b[]){
Set<Integer> set=new HashSet<Integer>();
for(int e:a){
set.add(new Integer(e));
}
for(int e:b){
if(set.contains(e)){
System.out.print(e+" ");
}
}
}
public static void main(String args[]){
int a[]={1,2,4,6,8,9,3,5};
int b[]={23,2,42,5,43,6};
jiaoji(a,b);
}
}
七、人人网2015校招笔试题。
给定一个有序数组a，长度为len，和一个数X，半段A数组中是否存在两个数，他们的和为X，存在返回true，不存在返回false。
package A7;
public class A1 {
public static boolean judge(int a[], int x) {
int low = 0;
int high = a.length - 1;
while (low < high) {
if (a[low] + a[high] == x) {
return true;
}
if (a[low] + a[high] > x) {
high--;
}
if (a[low] + a[high] < x) {
low++;
}
}
return false;
}
public static void main(String args[]) {
int a[] = {1,3,4,5,6,9,10,13,15,16};
System.out.println(judge(a, 4));
System.out.println(judge(a, 15));
System.out.println(judge(a, 44));
System.out.println(judge(a, 2));
System.out.println(judge(a, 32));
}
}
2、给定有n个数的数组a，其中超过一半的数为一个定值，在不进行排序，不开设额外数组的情况下，以最高的效率找出这个数;
如果每次删除两个不同的数（不管是不是我们要查找的那个出现次数超过一半的数字），那么，在剩下的数中，我们要查找的数（出现次数超过一半）出现的次数仍然超过总数的一半。通过不断重复这个过程，不断排除掉其它的数，最终找到那个出现次数超过一半的数字。
因此我们可以考虑在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1。 如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为零，我们需要保存下一个数字，并把次数重新设为1。
下面，举二个例子：
- 第一个例子，5，5，5，5，1 ：
不同的相消，相同的累积。遍历到第四个数字时，candidate 是5, nTimes 是4; 遍历到第五个数字时，candidate 是5, nTimes 是3; nTimes不为0，那么candidate就是超过半数的。
- 第二个例子，0，1，2，1，1：
开始时，保存candidate是数字0，ntimes为1，遍历到数字1后，与数字0不同，则ntime减1变为零,；接下来，遍历到数字2，2与1不同，candidate保存数字2，且ntimes重新设为1；继续遍历到第4个数字1时，与2不同，ntimes减一为零，同时candidate保存为1；最终遍历到最后一个数字还是1，与我们之前candidate保存的数字1相同，ntime加一为1。最后返回的是之前保存的candidate为1。
package A7;
public class A2 {
public static int find (int a[]){
int time=1;
int candidate=a[0];
for(int i=1;i<a.length;++i){
if(time==0){
candidate=a[i];
}
if(a[i]==candidate){
time++;
}
if(a[i]!=candidate){
time--;
}
}
return candidate;
}
public static void main(String[] args) {
int a[]={0,1,1,3,4,6,2,1,1,5,1,4,1,1,1,1,56,1,1,3};
System.out.println(find(a));
}
}
八、9月22日，阿里巴巴北邮站
设计一个最优算法查找一个n个元素数组中的最大值和最小值。已知一种需要比较2n次的方法，给出一个更优的算法。请特别注意优化时间复杂度的常数。
package A8;
import java.util.AbstractMap;
import java.util.Map.Entry;
public class A1 {
public static Entry maxAndMin(int a[]){
int max=Integer.MIN_VALUE;
int min=Integer.MAX_VALUE;
for(int i=0;i<a.length;++i){
if(a[i]<min){
min=a[i];
}
if(a[i]>max){
max=a[i];
}
}
Entry<Integer,Integer> entry=new AbstractMap.SimpleEntry<Integer,Integer>(max,min);
return entry;
}
public static void main(String[] args) {
int a[]={3,5,2,2,76,72,4,3,62,3,46,23,5};
System.out.println(maxAndMin(a));
}
}
九、9月24日，去哪儿网2014校招西安站笔试题
给定一个200MB的文本文件，里面存的是IP地址到真实地址信息的映射信息，例如：211.200.101.100北京
然后给你6亿个IP地址，请设计算法快速的打印出所对应的真实地址信息。
package A9;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class A1 {
public static void main(String[] args) {
Map<String,String> ipAddress=new HashMap<String,String>();
try {
File file = new File("D://ip.txt");
if (file.isFile() && file.exists()) {
FileInputStream fs = new FileInputStream(file);
InputStreamReader is = new InputStreamReader(fs, "GBK");
BufferedReader reader=new BufferedReader(is);
String temp=reader.readLine();
String ip;
String address;
while(temp!=null){
ip=temp.split(" ")[0];
address=temp.split(" ")[1];
ipAddress.put(ip, address);
temp=reader.readLine();
}
reader.close();
}
} catch (Exception e) {
System.out.println("读取出错");
}
try{
File file=new File("D://a.txt");
if (file.isFile() && file.exists()) {
FileInputStream fs = new FileInputStream(file);
InputStreamReader is = new InputStreamReader(fs,"GBK");
BufferedReader reader=new BufferedReader(is);
String ip=reader.readLine();
String address;
while(ip!=null){
address=ipAddress.get(ip);
if(address!=null){
System.out.println(ip+" "+address);
}
else{
System.out.println(ip+" unknow");
}
ip=reader.readLine();
}
reader.close();
}
}
catch(Exception e){
System.out.println("错误");
}
}
}