当前位置:首页 > 开发 > IT生活 > 正文

笔试简单基础算法

发表于: 2012-11-08   作者:braveCS   来源:转载   浏览次数:
摘要: 最近太困太累,昨天宣讲会上打盹打得啊,最后笔试稀里糊涂地写了。回来后想起自己写的,太次了。冒泡排序也能写错,生产者和消费者也挂了。这里就补上冒泡,生生产者消费者另外一篇 http://bravecs.iteye.com/blog/1720415 。提醒自己做事不能随便,不能差不多,不能浮躁 import java.util.Scanner; class Sort { priv
最近太困太累,昨天宣讲会上打盹打得啊,最后笔试稀里糊涂地写了。回来后想起自己写的,太次了。冒泡排序也能写错,生产者和消费者也挂了。这里就补上冒泡,生生产者消费者另外一篇http://bravecs.iteye.com/blog/1720415 。提醒自己做事不能随便,不能差不多,不能浮躁
import java.util.Scanner;

class Sort
{
	private int[] a;
	private int len;
	private int count;
	//从console中输入
	public void input()
	{
		Scanner scanner=new Scanner(System.in);
		String str=scanner.nextLine();
		String[] temp=str.split(",");
		len=temp.length;
		a=new int[len];
		for(int i=0;i<len;i++)
			a[i]=Integer.parseInt(temp[i]);
	}
	//显示
	public void show()
	{
		for(int i=0;i<len;i++)
			System.out.print(a[i]+",");
		System.out.println("\n比较次数:"+count);
	}
	
	//冒泡排序
	public void sort()
	{
		boolean flag=false;
		count=0;
		int temp;
		for(int i=0;!flag&&i<len-1;i++)
		{
			flag=true;
			for(int j=0;j<len-i-1;j++)
			{
				if(a[j]<a[j+1])
				{
					temp=a[j];
					a[j]=a[j+1];
					a[j+1]=temp;
					flag=false;
					count++;
				}
			}
		}
	}
	
	/**
	 * 二分法dichotomy查找  非递归recursion
	 * 前提:已排好序
	 */
	public int dichotomy(int target)
	{
		int start=0,end=a.length-1,middle;
		while(start<end)
		{
			middle=(start+end)/2;
			if(a[middle]==target)
				return middle;
			else if(a[middle]<target)
				end=middle-1;
			else
				start=middle+1;	
		}
		return start==end&&a[start]==target?start:-1;
	}
	
	/**
	 * 二分法dichotomy查找 递归 recursion
	 * 前提:已排好序
	 */
	public int dichotomy(int target,int start,int end)
	{
		if(start>end)
			return -1;
		if(start==end)
			return a[start]==a[end]?start:-1;
		int middle=(start+end)/2;
		if(a[middle]==target)
			return middle;
		if(a[middle]<target)
			return dichotomy(target,start,middle-1);
		else
			return dichotomy(target,middle+1,end);		
	}	
}

public class Cs 
{
	public static void main(String[] args)
	{	
		Sort cs=new Sort();
		cs.input();
		cs.sort();
		cs.show();
	}	
}

笔试简单基础算法

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
一:插入排序 插入排序:对于少量的元素排序,它是个有效的算法。时间复杂度:N^2 插入排序好比一手
一、基本概念 问题:需要回答的一般性提问,通常含若干参数。 算法:有限条指令的集合,确定某个问
本篇文章为转载 前言:   找工作时(IT行业),除了常见的软件开发以外,机器学习岗位也可以当作
百度面试题(一):假设一整型数组存在若干正数和负数,现在通过某种算法使得该数组的所有负数在正
树的具体的定义不说了,说几个重要的树的性质 一棵树是N个节点和N-1条边的集合,因为除了根节点以外
在我的博客对冒泡排序,直接插入排序,直接选择排序,希尔排序,归并排序,快速排序和堆排序这七种
在网上搜索Java的基础算法题,差不多都是那50道,也有很多人贴了代码。参考着一份代码,我自己也大
这一节主要讲很多方面非常重要的hash table等问题. 由于平时很少用到这些,基本都忘了。。。 怎样快
邻接表(adjacency lists)是表示图的标准方法。 如果是稠密图,可以使用 邻接矩阵(adjacency matrix)
import java.util.Arrays; import java.util.regex.Matcher; import java.util.regex.Pattern; /**
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号