Android 面試題之編程

1、排序

package cn.java.suanfa;


public class SuanFa {

	public static void main(String[] args) {

		int[] arr = {5,7,3,9,1,3,2};
//		selectSort(arr);
		System.out.println(" ------------------- ");
//		maopaoSort(arr);
		quickSort(arr,0,arr.length-1);
		
	}
	/**
	 * Java排序算法（六）：直接插入排序 
	 *  直接插入排序的基本操作就是將待排序的數據元素按其關鍵字值的大小插入到前面的有序序列中。  
	 *  直接插入的時間效率並不高，如果在最壞的情況下，所有元素的比較次數總和為（0+1+...+n-1）=O(n^2)
	 *  。其他情況下也要考慮移動元素的次數，故時間復雜度為O(n^2)  直接插入空間效率很好，
	 *  只需要1個緩存數據單元，也 就是說空間復雜度為O(1). 直接插入排序是穩定的。  直接插入排序在數
	 *  據已有一定順序的情況下，效率較好。但如果數據無規則，則需要移動大量的數據，其效率就與冒泡排序
	 *  法和選擇排序法一樣差了。
	 *  算法描述  
	 *     對一個有n個元素的數據序列，排序需要進行n-1趟插入操作：  
	 *     第1趟插入，將第2個元素插入前面的有序子序列--此時前面只有一個元素，當然是有序的。  
	 *     第2趟插入，將第3個元素插入前面的有序子序列，前面2個元素是有序的。 
	 *     第n-1趟插入，將第n個元素插入前面的有序子序列，前面n-1個元素是有序的。
	 * @param data
	 */
	public static void insertSort(int[] data) {
		for (int i = 1; i < data.length; i++) {
			// 緩存i處的元素值
			int tmp = data[i];
			if (data[i] < data[i - 1]) {
				int j = i - 1;
				// 整體後移一格
				while (j >= 0 && data[j] > tmp) {
					data[j + 1] = data[j];
					j--;
				}
				// 最後將tmp插入合適的位置
				data[j + 1] = tmp;
				print(data);
			}
		}
	}
	
	/**
	 * Java排序算法（五）：快速排序  
	 * 快速排序是一個速度非常快的交換排序算法，它的基本思路很簡單，從待排的數據序列中任取一個數據（如第一
	 * 個數據）作為分界值，所有比它小的數據元素放到左邊，所有比它大的數據元素放到它的右邊。經過這樣一趟下
	 * 來，該序列形成左右兩個子序列，左邊序列中的數據元素的值都比分界值小，右邊序列中數據元素的值都比分界
	 * 值大。  接下來對左右兩個子序列進行遞歸排序，對兩個子序列重新選擇中心元素並依此規則調整，直到每個元素
	 * 子表的元素只剩下一個元素，排序完成。 思路：  
	 * 1.定義一個i變量，i變量從左邊第一個索引開始，找大於分界值的元素的索引，並用i來記錄它。  
	 * 2.定義一個j變量，j變量從右邊第一個索引開始，找小於分界值的元素的索引，並用j來記錄它。  
	 * 3.如果i=j，可以判斷j左邊的數據元
	 * 素都小於分界值，j右邊的數據元素都大於分界值，最後將分界值和j索引處的元素交換即可。 時間復雜度 
		最好情況（每次總是選到中間值作樞軸）T(n)=O(nlogn) 
		最壞情況（每次總是選到最小或最大元素作樞軸） 做n-1趟，每趟比較n-i次，
		總的比較次數最大：[O(n²)] 
		平均時間復雜度為：：T(n)=O(nlogn) 
	 * @param data
	 * @param start
	 * @param end
	 */
	public static void quickSort(int[] data, int start, int end) {
		if (start >= end) {
			return;
		}
		int middleVal = data[start];
		int i = start + 1;
		int j = end;

		while (true) {
			while (i <= end && data[i] < middleVal) {
				i++;
			}
			while (j > start && data[j] > middleVal) {
				j--;
			}
			if (iarr[j]) {
					int temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
					print(arr);
				}
			}
		}
	}

	/**
	 * 選擇排序
	 * 直接選擇排序的基本操作就是每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的
	 * 數列的最後，直到全部待排序的數據元素排完，它需要經過n-1趟比較。算法不穩定，O(1)的額外的空間，比較
	 * 的時間復雜度為O(n^2)，交換的時間復雜度為O(n)，並不是自適應的。在大多數情況下都不推薦使用。只有在
	 * 希望減少交換次數的情況下可以用。
	 * @param arr
	 */
	public static void selectSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			int minIndex = i;
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[minIndex] > arr[j]) {
					minIndex = j;
				}
			}
			if (minIndex != i) {
				int temp = arr[i];
				arr[i] = arr[minIndex];
				arr[minIndex] = temp;
				print(arr);
			}
		}
	}

	
	public static void print(int[] data) {
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + "\t");
		}
		System.out.println();
	}
	
	private static void swap(int[] data, int i, int j){
		int temp = data[i];
		data[i] = data[j];
		data[j] = temp;
		print(data);
	}
}

/**
 * 創建二叉樹，對數組進行排序
 * @author libin
 *
 */
public class BinaryTree {
	
	public int value;
	public BinaryTree left;
	public BinaryTree right;
	
	public BinaryTree(int value){
		this.value = value;
	}
	
	public void addValue(int val){
		if(valvalue){
			if (right==null) {
				right = new BinaryTree(val);
			}else {
				right.addValue(val);
			}
		}
	}
	
	public boolean find(int val){
		if(this.value == val){
			return true;
		}
		if(val>this.value){
			if(right==null){
				return false;
			}else {
				return right.find(val);
			}
		}
		if(val

2、








public class CalByteNum {

	public static void main(String[] args) throws Exception {
		//對應字節 105  -25  -120  -79  121  111  117  50  
		String str = "i愛you2";
		int by = calByte(str.getBytes("GBK"),3);
		System.out.println(str.substring(0, by));
	}
	/**
	 * 截取字符串，當遇到半個漢字時將會捨棄。
	 * calByte(str.getBytes("GBK"),2) ---> 輸出：i
	 * calByte(str.getBytes("GBK"),3) ---> 輸出：i愛
	 * @param buf
	 * @param cut
	 * @return
	 */
	public static int calByte(byte[] buf,int cut){
		int resNum=0;
		int chineseFlag = 0;
		for (int i = 0; i < cut; i++) {
			if (buf[i]<0 ) {
				if(chineseFlag==1){
					chineseFlag=0;
					resNum++;
				}else{
					chineseFlag++;
				}
			}else {
				resNum++;
			}
		}
		return resNum;
	}
}