package com.baidu.ecom;

public class BinarySearchMax {
	
	public static int bisearch(int[] arr , int b, int e, int num){
		int minIndex = b , maxIndex = e, midIndex=-1;
		while(minIndex <= maxIndex){
			midIndex = minIndex+(maxIndex-minIndex)/2;
			if(arr[midIndex] == num)
				break;
			else if(arr[midIndex] < num)
				minIndex = midIndex + 1;
			else
				maxIndex = midIndex - 1;
		}
		return midIndex;
	}
	
	public static int bisearchMax(int[] arr , int b, int e, int num){
		int minIndex = b , maxIndex = e, midIndex;
		while(minIndex <= maxIndex){
			midIndex = minIndex+(maxIndex-minIndex)/2;
			if(arr[midIndex] <= num)
				minIndex = midIndex + 1;
			else
				maxIndex = midIndex - 1;
		}
		if(arr[maxIndex]==num)
			return maxIndex;
		else if(arr[minIndex]==num)
			return minIndex;
		else
			return -1;
	}
	
	public static void main(String[] args) {
		int[] arr1={1,2,3,4,5,6,7,8,9};
		System.out.println(bisearch(arr1 , 0, 8, 7));
		int[] arr2={1,1,2,3,4,5,6,7,8};
		int[] arr3={1,2,3,4,5,6,7,8,8};
		int[] arr4={1,2,3,4,5,5,6,7,8};
		int[] arr5={1,2,3,4,5,6,6,7,8};
		int[] arr6={1,1,1,1,1,1,1,1,1};
		System.out.println(bisearchMax(arr1 , 0, 8, 7));
		System.out.println(bisearchMax(arr2 , 0, 8, 1));
		System.out.println(bisearchMax(arr3 , 0, 8, 8));
		System.out.println(bisearchMax(arr4 , 0, 8, 5));
		System.out.println(bisearchMax(arr5 , 0, 8, 6));
		System.out.println(bisearchMax(arr6 , 0, 8, 1));
	}

}

public class MinDigest{
	static String[] word;
	static String[] query;
	static void getMinDigest(String[] src, int N, String[] des, int m){
		word = src;
		query = des;
		int nTargetLen = N+1;
		int pBegin = 0;
		int pEnd = 0;
		int nLen = N;
		int nAbstractBegin = 0;
		int nAbstractEnd = 0;
		/*for(int k=0;k<query.length;k++)
		{
			System.out.println(query[k]);
		}
		for(int k=0;k<word.length;k++)
		{
			System.out.println(word[k]);
		}*/
		while(true)
		{
			while( pEnd< nLen&& (!isAllExisted(pBegin,pEnd)))
				pEnd++;
			//System.out.println(pBegin);
			//System.out.println(pEnd);
			while(isAllExisted(pBegin,pEnd))
			{
				if(pEnd-pBegin < nTargetLen)
				{
					nTargetLen = pEnd - pBegin;
					nAbstractBegin = pBegin;
					nAbstractEnd = pEnd;
				}
				pBegin++;
			}
			//System.out.println(pBegin);
			//System.out.println(pEnd);
			if(pEnd >=nLen)
				break;
		
		}
		System.out.println("nAbstractBegin:"+nAbstractBegin+",nAbstractEnd:"+nAbstractEnd);
		for(int k = nAbstractBegin;k <= nAbstractEnd;k++)
		{
			System.out.print(word[k]+" ");
		}
	
	}
	
	static boolean isAllExisted(int start, int end){
		if(end >= word.length)
			return false;
		int count = 0;
		for(int i=0;i<query.length;i++)
		{
			for(int j = start; j<=end; j++)
				if(query[i] == word[j])
						count++;
		}
		return count==query.length;
	}
	
	public static void main(String[] args){
		String[] str1 = {"宋轶山","何伟文","于峰","王冬锦","童俊杰","林单生","何伟文","童俊杰","何伟文","王冬锦","童俊杰"};
		String[] str2 = {"何伟文","童俊杰"};
		getMinDigest(str1,8,str2,2);

	}
}

/*人过大佛寺*我=寺佛大过人
* 每个字代表一个是数字，且每个字代表的数字不同
* 结果 21978*4 = 87912
*/
import java.util.*;
public class Huiwen {

	public static void main(String[] args){
		System.out.println("start");
		boolean flag; //数字是否有重复的标志
		boolean[] IsUsed={false,false,false,false,false,false,false,false,false,false};//数字是否使用过的boolean数组
		int number, revert_number,t,v;
		ArrayList<Num> list = new ArrayList<Num>();
		for(number =10000;number<100000;number++)
		{
			//每次循环开始，把该boolean数字清flase
			for(int i=0;i<IsUsed.length;i++)
				IsUsed[i] = false;
			flag = true;//初始没有数字重复
			t = number;
			revert_number = 0;
			
			for(int i=0;i<5;i++)
			{
				v = t%10;
				revert_number = revert_number*10+v;
				t /=10;
				if(IsUsed[v]){ //看是否数字出现过
					flag = false;//出现过直接置flag为false
                                              break;
				}else
					IsUsed[v]=true;;//未出现过直接置IsUsed数组相应位为true，表示这个数字出现过了

			
			}
			System.out.println("number:"+number+",revert_number:"+revert_number);
			if(flag&&(revert_number%number==0))//flag为true表示数字没有重复，且可以整除即v存在
			{
				v = revert_number/number;
				if(v<10&&!IsUsed[v]){//保证v小于10，且没有在number中出现过
					Num n = new Num(number,v,revert_number);
					list.add(n);
					System.out.println("人过大佛寺"+number+"*我"+v+"="+"寺佛大过人"+revert_number);
				}
			}
		}
		
		for(int i=0;i<list.size();i++){
			System.out.println("人过大佛寺"+list.get(i).num1+"*我"+list.get(i).num2+"="+"寺佛大过人"+list.get(i).num3);
			
		}
		
		System.out.println("over");
	}

		static class Num{
			int num1;
			int num2;
			int num3;
			Num(int n1,int n2,int n3){
				num1 = n1;
				num2 = n2;
				num3 = n3;
			}
		}


}

/** 
 
@author   
*         编写时间：2011-10-4 <br /> 
*         优化：2011-10-4 
*         类的名称为：RMB.java <br /> 
*         比较完善的解决方案。 测试通过。 <br /> 
 *       最准确的使用就是小数点之前最多13位，小数点之后不限,当然写多了也没有用，哈哈。<br /> 
 */  
  
import java.text.DecimalFormat;  
import java.text.NumberFormat; 
  
//总体思路：   
//对数字进行分级处理，级长为4   
//对分级后的每级分别处理，处理后得到字符串相连   
//如：123456=12|3456   
//第二级：12=壹拾贰 + “万”   
//第一级：3456 =叁千肆百伍拾陆 + “”   
  
  
public final class RMB {  
  
    private double amount = 0.0D;
    private static final String NUM = "零壹贰叁肆伍陆柒捌玖";  
    private static final String UNIT = "仟佰拾个";  
    private static final String GRADEUNIT = "仟万亿兆";  
    private static final String DOTUNIT = "角分厘";  
    private static final int GRADE = 4;  
    private static final String SIGN = "￥";  
    private static final NumberFormat nf = new DecimalFormat("#0.###"); //这个模式意味着在小数点前有两个数字，第一位如果没有就空着，第二位如果没有就补零；小数点后有三位数字，如果没有就空着
	//"####.000"的符号。这个模式意味着在小数点前有四个数字，如果不够就空着，小数点后有三位数字，不足用0补齐
    
    /** 
    * 带参数的构造方法 
    *  
    * @param amount 
    */  
 
    private RMB(double amount) {  
        this.amount = amount;  
    }  
  
    public static String toBigAmt(double amount) {  
        nf.setMinimumFractionDigits(3);//小数点后不足的补零
        String amt = nf.format(amount);//将double类型的数格式化并转换成字符串,实际上进行了四舍五入   
        System.out.println(amt);  
        Double d = new Double(amount);  
        String dotPart = ""; //取小数位   
        String intPart = ""; //取整数位   
        int dotPos;  
  
        if ((dotPos = amt.indexOf('.')) != -1) {  
            intPart = amt.substring(0, dotPos);  
            dotPart = amt.substring(dotPos + 1);  
            if(dotPart.length()>4){ //超过4位直接截取   
                dotPart = dotPart.substring(0,4);  
            }  
        } else {  
            intPart = amt;  
        }  
 
        if (intPart.length() > 16)  
            throw new java.lang.InternalError("数额太大，无法转换。");  
        String intBig = intToBig(intPart);  
        String dotBig = dotToBig(dotPart);  
  
        //以下代码稍做修改，现在好多了。   
        if ((dotBig.length() == 0) && (intBig.length() != 0)) {  
            return intBig + "元整";  
        } else if ((dotBig.length() == 0) && (intBig.length() == 0)) {  
            return intBig + "零元";  
        } else if ((dotBig.length() != 0) && (intBig.length() != 0)) {  
            return intBig + "元" + dotBig;  
        } else {  
            return dotBig;  
        }  
    }  
  
   

   /** 
    * 用来处理多少元 ，这个要仔细考虑才行 
    * @param intPart 
    * @return 
    */  
    private static String intToBig(String intPart) {  
 
       //得到转换后的大写（整数部分）   
        int grade; //级长   
        String result = "";  
        String strTmp = "";  
  
       //得到当级长   
        grade = intPart.length() / GRADE;  
        //调整级次长度   
        if (intPart.length() % GRADE != 0)  
            grade += 1;  
    
        //对每级数字处理，先处理最高级，然后再处理低级的   
        for (int i = grade; i >= 1; i--) {  
            strTmp = getNowGradeVal(intPart, i);//取得当前级次数字   
            result += getSubUnit(strTmp);//转换大写   
            //System.out.println(strTmp+"|"+getSubUnit(strTmp));   
            result = dropZero(result);//除零 去掉连续的零   
            //System.out.println("result="+result);   
            //加级次单位   
            if (i > 1) //末位不加单位   
                //单位不能相连续   
                //注意：连续4个零的时候要特殊处理(wmj修改此bug)   
                if(getSubUnit(strTmp).equals("零零零零")){  
                    result = result+"零";  
                }else{  
                    result += GRADEUNIT.substring(i - 1, i);  
                }  
        }  
  
        return result;  
  
    }  

	
	
    /** 
    * 用来处理几角几分几厘 
    * @param dotPart 
    * @return 
    */  
    private static String dotToBig(String dotPart) {  
        //得到转换后的大写（小数部分）   
        String strRet = "";  
        for (int i = 0; i < dotPart.length() && i < 3; i++) {  
            int num;  
            if ((num = Integer.parseInt(dotPart.substring(i, i + 1))) != 0)  
                strRet += NUM.substring(num, num + 1)  
                       + DOTUNIT.substring(i, i + 1);  
        }  
        return strRet;  
    }  
	
	
	
  
    private static String getNowGradeVal(String strVal, int grade) {  
  
        //得到当前级次的串   
        String rst;  
        if (strVal.length() <= grade * GRADE)  
            rst = strVal.substring(0, strVal.length() - (grade - 1) * GRADE); 
        else  
            rst = strVal.substring(strVal.length() - grade * GRADE, strVal.length()- (grade - 1) * GRADE);  
        return rst;  
  
    }  
  
  
  
    private static String getSubUnit(String strVal) {  
 
        //数值转换   
        String rst = "";  
        for (int i = 0; i < strVal.length(); i++) {  
            String s = strVal.substring(i, i + 1);  
            int num = Integer.parseInt(s);  
            if (num == 0) { 
                //“零”作特殊处理   
                if (i != strVal.length()) //转换后数末位不能为零   
                    rst += "零";  
            } else {  
                //If IntKey = 1 And i = 2 Then   
                //“壹拾”作特殊处理   
                //“壹拾”合理   
                //Else   
                rst += NUM.substring(num, num + 1);  
                //End If   
                //追加单位   
                if (i != strVal.length() - 1)//个位不加单位   
                    rst += UNIT.substring(i + 4 - strVal.length(), i + 4 - strVal.length() + 1);  
            }
        }
        return rst;  
  
  }  
  
  
  
    /** 
     * 
     *@param strVal 
     * @return
     */  
  
    private static String dropZero(String strVal) {  
  
        //去除连继的“零”   
        String strRst;  
        String strBefore; //前一位置字符   
        String strNow; //现在位置字符   
        strBefore = strVal.substring(0, 1);  
        strRst = strBefore;  
  
        for (int i = 1; i < strVal.length(); i++) {  
            strNow = strVal.substring(i, i + 1);  
            if (strNow.equals("零") && strBefore.equals("零"))  
                ;//同时为零   
            else  
                strRst += strNow;  
            strBefore = strNow;  
        }  
  
        //末位去零   
        if (strRst.substring(strRst.length() - 1, strRst.length()).equals("零"))  
            strRst = strRst.substring(0, strRst.length() - 1);  
        return strRst;  
  
    }  

  
  
    public static void main(String[] args) {  
  
        System.out.println(RMB.toBigAmt(0.090D));  
        System.out.println(RMB.toBigAmt(10.090D));
        System.out.println(RMB.toBigAmt(9.090D)); 
        System.out.println(RMB.toBigAmt(9.290D));  
        System.out.println(RMB.toBigAmt(5.90D));  
//        System.out.println(RMB.toBigAmt(10052345.00D));   
//        System.out.println(RMB.toBigAmt(0.00D));   
//        System.out.println(RMB.toBigAmt(0.60D));   
//        System.out.println(RMB.toBigAmt(00.60D));   
//        System.out.println(RMB.toBigAmt(150.2101D));   
//        System.out.println(RMB.toBigAmt(15400089666.234D));   
//        System.out.println(RMB.toBigAmt(15400089666.2347D));   
//        System.out.println(RMB.toBigAmt(1111222233334444.2347D));   
        System.out.println(RMB.toBigAmt(111222233334444.2347D));  
        System.out.println(RMB.toBigAmt(11222233334444.2347D));  
        System.out.println(RMB.toBigAmt(1222233334444.2347D));  
        System.out.println(RMB.toBigAmt(222233334444.2347D));  
//        System.out.println(RMB.toBigAmt(33334444.2347D));   
//        java.math.BigDecimal bg = new java.math.BigDecimal(1111222233334444.2347D);   
//        System.out.println(bg.toString());   
//        //1111222233334444.25 BigDecimal也不是很准确   
        System.out.println(RMB.toBigAmt(22200004444.2347D));  
        //贰佰贰拾贰亿万肆仟肆佰肆拾肆元贰角叁分伍厘   
        System.out.println(RMB.toBigAmt(10004.2347D));  
        System.out.println(RMB.toBigAmt(22200000004.2347D));  
        System.out.println(RMB.toBigAmt(10400.0047D));  
        System.out.println(RMB.toBigAmt(1000000000000.23477777777777D));
        System.out.println(RMB.toBigAmt(100100100.090566D));  
        //壹亿零壹拾万零壹佰元玖分   
        //壹亿零壹拾万零壹佰元玖分   
        System.out.println(RMB.toBigAmt(00.60D)); 
		System.out.println(RMB.toBigAmt(06D)); 
    }
  
} 

package com.baidu.ecom;

import java.util.LinkedList;

public class LevelVisit {
	
	static void visit(TreeNode root){
		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(root);
		int cur = 0;
		int last =1;
		while(cur < queue.size()){
			last = queue.size();
			while(cur < last ){
				 if(queue.get(cur) != null){
					 System.out.print(queue.get(cur).data); // 访问节点
					 if(queue.get(cur).pLeft!=null)  queue.add(queue.get(cur).pLeft);
					 if(queue.get(cur).pRight!=null) queue.add(queue.get(cur).pRight);
				 }else 
					 System.out.print("    本层结束"); // 访问null
				 cur++;
			}
			queue.add(null);
			if(queue.get(queue.size()-2)==null && queue.get(queue.size()-1)==null){
				queue.pollLast();
				break;
			}
			
			System.out.println();
			System.out.println("---------我是换行界限-----------");
		}
		addNext(queue);
	}
	
	static void addNext(LinkedList<TreeNode> queue){
		System.out.println();
		for(TreeNode tn:queue){
			if( tn != null)
				System.out.println(tn.data);
			else
				System.out.println("null");
		}
	}
	
	
	public static void main(String[] args) {
		TreeNode root = new TreeNode("root");
		TreeNode n2 = new TreeNode("2");
		TreeNode n3 = new TreeNode("3");
		TreeNode n4 = new TreeNode("4");
		TreeNode n5 = new TreeNode("5");
		TreeNode n6 = new TreeNode("6");
		TreeNode n7 = new TreeNode("7");
		TreeNode n8 = new TreeNode("8");
		TreeNode n9 = new TreeNode("9");
		root.pLeft = n2;
		root.pRight = n3;
		n2.pLeft = n4;
		n2.pRight = n5;
		n3.pLeft = n6;		
		n3.pRight = n7;
		n4.pLeft = n8;
		n4.pRight = n9;
		visit(root);
		
	
	
	
	}

}

/**    百度面试题（一）：假设一整型数组存在若干正数和负数，现在通过某种算法使得该数组的所有负数在正数的左边，且保证负数和正数间元素相对位置不变。时空复杂度要求分别为：o(n)和o(1)。
       百度面试题（二），给定一个存放正数的数组，重新排列数组使得数组左边为奇数，右边为偶数，且保证奇数和偶数之间元素相对位置不变。时空复杂度要求分别为：o(n)和o(1)。
       这两个题目是一个类型的题目：用两个指针，一个pre指针，一个cur指针，pre指针指向当前最后一次交换时候的位置，cur指针进行搜索，遇到小于零的数将pre指针的数插入到pre指针的后一位。时间复杂度花在移位运算上。空间复杂度花在保存临时值上。O(n)是指线性时间。http://www.cnblogs.com/hlxs/archive/2011/09/01/2161940.html 讨论帖中很多人对此的理解是错误的。
      给出面试题（-）的算法描述伪代码：
*/     
pre = 0；
 
       cur =  1;
 
       while (cur < length(array))
 
{ 
 
     if (array[cur] < 0)
 
        {  
 
         swap(array[cur],array[pre]);   
 
         pre ++;
 
       }
 
      cur++;
 
}


/* 但是数据的相对位置发生了变化
*  故我觉得答案是不可能
*   保证线性复杂度就无法保证数据的相对位置不发生变化
*/

package com.baidu.ecom;

public class InsertSort2 {

	
	static void insertSort(int[] a){
		int firstNum =0;
		for(int i=0;i<a.length;i++){
			if(a[i]%2==0){
				int temp = a[i];
				for(int j=i-1;j>=firstNum;j--){
					a[j+1]=a[j];
				}
				a[firstNum] = temp;
				firstNum++;
			}
		}
	}
	
	static void printArray(int[] a){
		for(int i=0;i<a.length;i++)
			System.out.print(a[i]);
		System.out.println();
	}
	
	public static void main(String[] args) {
		int[] a = {1,2,3,4,5,6,7,8,9,10,-11,-12,13,-14};
		printArray(a);
		insertSort(a);
		printArray(a);
	}

}

package com.baidu.ecom;

public class InsertSort1 {

	
	static void insertSort(int[] a){
		int firstNum =0;
		for(int i=0;i<a.length;i++){
			if(a[i]<0){
				int temp = a[i];
				for(int j=i-1;j>=firstNum;j--){
					a[j+1]=a[j];
				}
				a[firstNum] = temp;
				firstNum++;
			}
		}
	}
	
	static void printArray(int[] a){
		for(int i=0;i<a.length;i++)
			System.out.print(a[i]);
		System.out.println();
	}
	
	public static void main(String[] args) {
		int[] a = {-3,1,2,-1,4,5,6,-9,7,-90,8};
		printArray(a);
		insertSort(a);
		printArray(a);
	}

}

存储过程（Stored Procedure）是一组为了完成特定功能的SQL语句集，是利用SQL Server所提供的Transact-SQL语言所编写的程序。功能是将常用或复杂的工作，预先用SQL语句写好并用一个指定名称存储起来， 以后需要数据库提供与已定义好的存储过程的功能相同的服务时，只需调用execute,即可自动完成命令。存储过程是由流控制和SQL语句书写的过程，这个过程经编译和优化后存储在数据库服务器中，可由应用程序通过一个调用来执行，而且允许用户声明变量 。同时，存储过程可以接收和输出参数、返回执行存储过程的状态值，也可以嵌套调用。
首先在mysql中练习下存储过程的小例子：    mysql> delimiter //
mysql> create procedure hello()
    -> begin
    -> select 'It is not a HelloWorld';
    -> end
    -> //
Query OK, 0 rows affected (0.01 sec)其中“delimiter //”的意思是定义结束符号为“//”，以此来替换mysql中的“；”
在mysql中查询上面的过程hello():
mysql> call hello()//
+------------------------+
| It is not a HelloWorld |
+------------------------+
| It is not a HelloWorld |
+------------------------+
1 row in set (0.00 sec)建立一个简单的测试用表：
mysql> DROP TABLE IF EXISTS `userinfo`.`mapping`;
    -> CREATE TABLE  `userinfo`.`mapping` (
    ->   `cFieldID` smallint(5) unsigned NOT NULL,
    ->   `cFieldName` varchar(30) NOT NULL,
    ->   PRIMARY KEY  (`cFieldID`)
    -> ) ENGINE=InnoDB DEFAULT CHARSET=utf8;
    -> //
Query OK, 0 rows affected (0.14 sec)向table mapping中插入一些初始化的数据：
mysql> load data infile 'd:\\userInfo\\field.txt' into table mapping
    -> fields terminated by ',' lines terminated by '\r\n' //
Query OK, 5 rows affected (0.02 sec)
Records: 5  Deleted: 0  Skipped: 0  Warnings: 0
mysql> select *from mapping//
+----------+-------------+
| cFieldID | cFieldName  |
+----------+-------------+
|        1 | MarketValue |
|        2 | P/L         |
|        3 | EName       |
|        4 | Nominal     |
|        5 | Chg         |
+----------+-------------+
5 rows in set (0.02 sec)现在简历一个向mapping中插入一条记录并返回记录的总和
mysql> drop procedure if exists mappingProc;
    ->  create procedure mappingProc(out cnt int)
    ->  begin
    ->  declare maxid int;
    ->  select max(cFieldID)+1 into maxid from mapping;
    ->  insert into mapping(cFieldID,cFieldName) values(maxid,'hello');
    ->  select count(cFieldID) into cnt from mapping;
    ->  end
    ->  //查找mappingProc():
mysql> call mappingProc(@a)//
mysql> select @a//
+------+
| @a   |
+------+
| 6    |
+------+
mysql> select * from mapping//
+----------+-------------+
| cFieldID | cFieldName  |
+----------+-------------+
|        1 | MarketValue |
|        2 | P/L                 |
|        3 | EName          |
|        4 | Nominal     |
|        5 | Chg         |
|        6 | hello       |
+----------+-------------+下面是java代码用来调用MySQL的存储过程：
package kissJava.sql;
import java.sql.CallableStatement;
import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.SQLException;
import java.sql.Types;
public class SQLUtils {
    String url = "jdbc:mysql://127.0.0.1:3306/userInfo"; 
    String userName = "root";
    String password = "zhui007";
    public Connection getConnection() {
        Connection con=null;
        try{
            DriverManager.registerDriver(new com.mysql.jdbc.Driver());
            con = DriverManager.getConnection(url, this.userName, this.password);
        }catch(SQLException sw){ 
         }
        return con;
    }
    public void testProc(){
        Connection conn = getConnection();
        CallableStatement stmt = null;
        try{
            stmt = conn.prepareCall("{call mappingProc(?)}");    
            stmt.registerOutParameter(1, Types.INTEGER);
            stmt.execute();
            int i= stmt.getInt(1);
            System.out.println("count = " + i);
        }catch(Exception e){
            System.out.println("hahad = "+e.toString());
        }finally{
            try {
                stmt.close();
                conn.close();
            }catch (Exception ex) {
                System.out.println("ex : "+ ex.getMessage());
            }
        }
    }
    public static void main(String[] args) {
        new SQLUtils().testProc();
    }
}

//* * * * * * * * * * * * * * * * * * * * * * * *
//*PROGRAM          :表达式求值                 *
//*CONTENT          :堆栈的应用                 *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <stdio.h>
#include <stdlib.h>
#include <dos.h>
#include <conio.h>
#define MAX 10       //定义堆栈最大容量
void push_opnd(char);//操作数堆栈入栈操作
float pop_opnd();    //操作数堆栈出栈操作
void push_optr(char);//操作符堆栈入栈操作
char pop_optr();     //操作符堆栈出栈操作
char relation(char,char);//比较两个操作符的优先级
float operate(float,char,float);//运算
float opnd[MAX];      //操作数堆栈
char optr[MAX];       //操作符堆栈
int topd=0;           //栈顶指针初始化
int top=0;
char symb[30];        //表达式字符串
void main()
{int i=0;
 char sy;
 float a,b;
 textbackground(3);   //设定屏幕颜色
 textcolor(15);
 clrscr();
 //---------------------程序解说-----------------------
 printf("本程序实现表达式求值的操作。可以进行加减乘除运算。\n");
 printf("这是堆栈应用的一个例子\n");
 //----------------------------------------------------
 printf("请输入表达式(以#结束):\n例如: 3*(3+2)/5#\n");
 push_optr('#');
 gets(symb);         //输入表达式，以#为结束符
 while((symb[i]!='#')||(optr[top]!='#'))
 {if((symb[i]!='+')&&(symb[i]!='-')&&(symb[i]!='*')&&(symb[i]!='/')
	 &&(symb[i]!='(')&&(symb[i]!=')')&&(symb[i]!='#')&&(symb[i]!=' '))
     {push_opnd(symb[i]);i++;}           //如果当前字符不是操作符，则入操作数栈，字符串指针加一
  else  switch(relation(optr[top],symb[i]))  //若是操作符，比较其和操作符栈的栈顶元素的优先级
	   {case '<':push_optr(symb[i]);i++;break;  //若栈顶元素优先级低，则当前字符入栈，指针加一
	    case '=':sy=pop_optr();i++; break;      //若优先级相等，必为两个配对的括号，退栈，指针加一
	    case '>':sy=pop_optr();b=pop_opnd();    //若优先级高，则栈顶元素退栈，进行运算
		     a=pop_opnd();
		     topd=topd+1;
		     opnd[topd]=operate(a,sy,b);     //把运算结果入栈
		     break;
	    case ' ':printf("语法错误!\n");exit(0);
	   }
  }
  printf("运算结果=%1.2f\n",opnd[topd]);
  printf("程序结束，按任意键退出!\n");
  getch();
}
void push_opnd(char ch)
{int ch_i;
 ch_i=ch-'0';   //把字符换算成数字，并入操作数栈
 topd++;
 opnd[topd]=ch_i;
}
float pop_opnd() 
{//操作数栈出栈
topd=topd-1;
 return opnd[topd+1];
}
void push_optr(char ch)
{//操作符入栈
 top++;
 optr[top]=ch;
}
char pop_optr()  
{//操作数出栈
 top--;
 return optr[top+1];
}
char relation(char sym1,char sym2)  
{//比较两个操作符的优先级
 int i;
 char chl[2];
 int ind[2];
 char re[7][7]={'>','>','<','<','<','>','>',
		'>','>','<','<','<','>','>',
		'>','>','>','>','<','>','>',
		'>','>','>','>','<','>','>',
		'<','<','<','<','<','=',' ',
		'>','>','>','>',' ','>','>',
		'<','<','<','<','<',' ','='};
 chl[0]=sym1;
 chl[1]=sym2;
 for(i=0;i<=1;i++)
    {switch(chl[i])
      {case '+':ind[i]=0;break;
       case '-':ind[i]=1;break;
       case '*':ind[i]=2;break;
       case '/':ind[i]=3;break;
       case '(':ind[i]=4;break;
       case ')':ind[i]=5;break;
       case '#':ind[i]=6;break;
       default:printf("Error!\n");return('0');
      }
    }
 return(re[ind[0]][ind[1]]);
}
float operate(float a,char sym,float b)  
{//进行运算
 float re;
 switch(sym)
    {case '+':re=a+b;break;
     case '-':re=a-b;break;
     case '*':re=a*b;break;
     case '/':re=a/b;break;
     default:printf("Error!\n");return(0);
    }
 return re;
}

package com.baidu.ecom;

public  class  Test  { 


	public  static  void  encode(byte[]  in,  byte[]  out,  int  password) 
	{ 
	int  len  =  in.length; 

	int  seed  =  password  ^  0xd5da34ab; 
	for  (int  i  =  0  ;  i  <  len;  ++i)  { 
			byte  a  =  (byte)(  (  in[i]  ^  seed  )  >>>  2  ); 
			byte  b  =  (byte)(  (  (  ((int)in[i])  <<  15  )  ^  seed  )  >>>  (15-6)  ); 
			a  &=  0x3f; 
			b  &=  0xc0; 
			out[i]  =  (byte)(a  |  b); 
			seed  =  (seed  *  84723701  +  out[i]); 
	}

	} 


	public static void decode(byte[] in, byte[] out, int password) {
		int len = in.length;
		int seed = password ^ 0xd5da34ab;
		for (int i = 0; i < len; ++i) {
		byte high6 = (byte) ((in[i]<< 2)^seed);
		byte low2 = (byte)((((int)in[i]<<(15-6))^seed)>>>(15));
		high6 &= 0xfc;
		low2 &= 0x03;
		out[i] = (byte) (high6 | low2);
		seed = (seed * 84723701 + in[i]);
		}
	}


	public  static  void  main(String  []  args)  throws  Exception 
	{ 
		int  password  =  0xc5f8061f; 
		byte[]  buf1  =  {-33,  124,  80,  76,  -26,  119,  -41,  -8,  -84,  30,  13,  -82,  24,  119,  95,  120,  -34,  73,  -23,  76,  -76,  -112,  106,  -27,  -116,  68,  42,  10,  83,  72,  26,  -2,  78,  90,  17,  83,  -18,  81,  51,  115,  70,  -68}; 
		byte[]  buf2  =  new  byte[buf1.length]; 
		decode(buf1,  buf2,  password); 
		System.out.println(new  String(buf2,  "GBK")); 
	} 


}

/**
* 非法输入：
*         1. 空指针或空串（考虑）
*         2. 不是数字的非法字符（考虑）
*         3. 字符串过长引起整数越界，溢出（考虑）
*
*/
public class String2IntUpdate {

	static int getString2IntSolution1(String str){
		if (str == null||str.equals("")) 
		{
            throw new NumberFormatException("null");
        }
		int result = Integer.valueOf(str, 10);
		
		return result;
	}
	
	static int getString2IntSolution2(String str){
		if (str == null||str.equals("")) {
            throw new NumberFormatException("null");
        }
		boolean negative = false;
		negative = str.startsWith("-");
		int temp=0, radix=1;
		long current=0;
		int strLength=str.length();
		if(negative)
		{
			for(int i=strLength-1;i>=1;i--){
				temp = Character.digit(str.charAt(i),10);//JDK: char --> int
//				System.out.println("temp:"+temp);
				if(temp>=0&&temp<=9){
					current = temp*radix+current;
					if(current>Integer.MAX_VALUE)
					{
						current = 0;
						break;
					}
					radix *=10;
				}else
				{
					current = 0;
					break;
				}
				
			}
		}else
		{
			for(int i=strLength-1;i>=0;i--){
				temp = Character.digit(str.charAt(i),10);//JDK: char --> int
//				System.out.println("temp:"+temp);
				if(temp>=0&&temp<=9){
					current = temp*radix+current;
					if(current>Integer.MAX_VALUE)
					{
						current = 0;
						break;
					}
					radix *=10;
				}else
				{
					current = 0;
					break;
				}
			}
		}
		if(negative)
			return (int)-current;
		else
			return (int)current;
		
	}
	
	static int getString2IntSolution3(String str){
		if (str == null||str.equals("")) {
            throw new NumberFormatException("null");
        }
		boolean negative = false;
		negative = str.startsWith("-");
		int temp=0, radix=1;
		long current=0;
		int strLength=str.length();
		if(negative)
		{
			for(int i=strLength-1;i>=1;i--){
				temp = str.charAt(i)-'0';//My own: char --> int
//				System.out.println("temp:"+temp);
				if(temp>=0&&temp<=9){
					current = temp*radix+current;
					if(current>Integer.MAX_VALUE)
					{
						current = 0;
						break;
					}
					radix *=10;
				}else
				{
					current = 0;
					break;
				}
			}
		}else
		{
			for(int i=strLength-1;i>=0;i--){
				temp = str.charAt(i)-'0';//My own: char --> int
//				System.out.println("temp:"+temp);
				if(temp>=0&&temp<=9){
					current = temp*radix+current;
					if(current>Integer.MAX_VALUE)
					{
						current = 0;
						break;
					}
					radix *=10;
				}else
				{
					current = 0;
					break;
				}
			}
		}
		if(negative)
			return (int)-current;
		else
			return (int)current;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String str = "456";
//		String str = "456sd543";
//		String str = "4568888888888888888888888888888888888888888";
		String str2 = "-456de45";
//		String str2 = "-456yu785";
//		String str2 = "-45699999999999999999999999999999999999999";
		System.out.println(getString2IntSolution1(str));
		System.out.println(getString2IntSolution2(str));
		System.out.println(getString2IntSolution3(str));
		System.out.println(getString2IntSolution1(str2));
		System.out.println(getString2IntSolution2(str2));
		System.out.println(getString2IntSolution3(str2));
	}

}

package com.baidu.ecom;
/**
* 非法输入：
*         1. 空指针或空串（考虑）
*         2. 不是数字的非法字符（未考虑）
*         3. 字符串过长引起整数越界，溢出（未考虑）
*
*/
public class String2Int {

	static int getString2IntSolution1(String str){
		if (str == null||str.equals("")) 
		{
            throw new NumberFormatException("null");
        }
		int result = Integer.valueOf(str, 10);
		
		return result;
	}
	
	static int getString2IntSolution2(String str){
		if (str == null||str.equals("")) {
            throw new NumberFormatException("null");
        }
		boolean negative = false;
		negative = str.startsWith("-");
		int temp=0, current=0,radix=1;
		int strLength=str.length();
		if(negative)
		{
			for(int i=strLength-1;i>=1;i--){
				temp = Character.digit(str.charAt(i),10);//JDK: char --> int
//				System.out.println("temp:"+temp);
				current = temp*radix+current;
				radix *=10;
			}
		}else
		{
			for(int i=strLength-1;i>=0;i--){
				temp = Character.digit(str.charAt(i),10);//JDK: char --> int
//				System.out.println("temp:"+temp);
				current = temp*radix+current;
				radix *=10;
			}
		}
		if(negative)
			return -current;
		else
			return current;
		
	}
	
	static int getString2IntSolution3(String str){
		if (str == null||str.equals("")) {
            throw new NumberFormatException("null");
        }
		boolean negative = false;
		negative = str.startsWith("-");
		int temp=0, current=0,radix=1;
		int strLength=str.length();
		if(negative)
		{
			for(int i=strLength-1;i>=1;i--){
				temp = str.charAt(i)-'0';//My own: char --> int
//				System.out.println("temp:"+temp);
				current = temp*radix+current;
				radix *=10;
			}
		}else
		{
			for(int i=strLength-1;i>=0;i--){
				temp = str.charAt(i)-'0';//My own: char --> int
//				System.out.println("temp:"+temp);
				current = temp*radix+current;
				radix *=10;
			}
		}
		if(negative)
			return -current;
		else
			return current;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String str = "456";
		String str2 = "-456";
		System.out.println(getString2IntSolution1(str));
		System.out.println(getString2IntSolution2(str));
		System.out.println(getString2IntSolution3(str));
		System.out.println(getString2IntSolution1(str2));
		System.out.println(getString2IntSolution2(str2));
		System.out.println(getString2IntSolution3(str2));
	}

}

public class ReverseIteratively {

	static ListNode ReverseIteratively(ListNode pHead)
	{
		System.out.println("--------------开始反转---------------");
		ListNode pReverseHead = null;
		ListNode pNode = pHead;
		ListNode pPrev = null;
		while(pNode!=null){
			//存
			ListNode pNext = pNode.m_pNext;
			//判
			if(pNext == null)
				pReverseHead = pNode;
			//反
			pNode.m_pNext = pPrev;
			//换
			pPrev = pNode;
			//移
			pNode = pNext;
		}
		System.out.println("--------------反转结束---------------");
		return pReverseHead;
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		ListNode ln5= new ListNode(5,null);
		ListNode ln4= new ListNode(4,ln5);
		ListNode ln3= new ListNode(3,ln4);
		ListNode ln2= new ListNode(2,ln3);
		ListNode ln1= new ListNode(1,ln2);
		ListNode pNode = ln1;
		while(pNode!=null){
			System.out.println("value:"+pNode.m_nKey);
			pNode = pNode.m_pNext;
		}
		System.out.println("------------------------------------");
		ListNode pHead = ReverseIteratively(ln1);
		ListNode pNodeReverse = pHead;
		while(pNodeReverse!=null){
			System.out.println("value:"+pNodeReverse.m_nKey);
			pNodeReverse = pNodeReverse.m_pNext;
		}
		System.out.println("------------------------------------");
 	}

}

	class ListNode
	{
		int m_nKey;
		ListNode m_pNext;
		public ListNode(int mNkey, ListNode mPNext) {
			super();
			m_nKey = mNkey;
			m_pNext = mPNext;
		}
		public int getM_nkey() {
			return m_nKey;
		}
		public void setM_nkey(int mNkey) {
			m_nKey = mNkey;
		}
		public ListNode getM_pNext() {
			return m_pNext;
		}
		public void setM_pNext(ListNode mPNext) {
			m_pNext = mPNext;
		}
	}

public class LCSTest {

	/*
	 * 	directions of LCS generaction
	 */
	enum decreaseDir{
		kLeft,kUp,kLeftUp,kInit;
	}
	
	
	/*
	 * Get the length of two Strings' LCSs , and print one of the LCSs
	 * Input: 
	 * 		pStr1	--	the first String
	 * 		pStr2	--	the second String
	 * Output:
	 * 		the length of two Strings' LCSs
	 */
	static int[][] LCS(String pStr1, String pStr2){
		if(pStr1.equals("")||pStr1==null||pStr2.equals("")||pStr2==null)
			return new int[0][0];
		int length1 = pStr1.length();
		int length2 = pStr2.length();
		int i,j;
		//	initiate the length matrix
		int[][] LCS_length = new int[length1][length2];
		for(i=0;i < length1; i++)
			for(j=0;j < length2; j++)
				LCS_length[i][j]=0;
		System.out.println("----------LCS矩阵初始化结束----------------");
		//initiate the direction matrix
		decreaseDir[][] LCS_direction = new decreaseDir[length1][length2];
		for(i=0;i < length1; i++)
			for(j=0;j < length2; j++)
				LCS_direction[i][j]=decreaseDir.kInit;
		System.out.println("----------LCS方向矩阵初始化结束----------------");
		for(i=0;i < length1; i++)
		{
			for(j=0;j < length2; j++)
			{
				if(i==0||j==0){
					
					if(pStr1.charAt(i)==pStr2.charAt(j))
					{	LCS_length[i][j]=1;
						LCS_direction[i][j]=decreaseDir.kLeftUp;
					}else
						LCS_length[i][j]=0;
				}
				/*
				 * a char of LCS is found
				 * it comes from the left up entry in the direction matrix
				 */
				else if(pStr1.charAt(i)==pStr2.charAt(j))
				{
					LCS_length[i][j]=LCS_length[i-1][j-1]+1;
					LCS_direction[i][j]=decreaseDir.kLeftUp;
				}
				/*
				 * it comes from the up entry in the direction matrix
				 */
				else if(LCS_length[i-1][j]>LCS_length[i][j-1])
//				else if(LCS_length[i-1][j]>=LCS_length[i][j-1])
				{
					LCS_length[i][j]=LCS_length[i-1][j];
					LCS_direction[i][j]=decreaseDir.kUp;
				}
				/*
				 * it comes from the left entry in the direction matrix
				 */
				else
				{
					LCS_length[i][j]=LCS_length[i][j-1];
					LCS_direction[i][j]=decreaseDir.kLeft;
				}
			}
		}
		System.out.println("----------LCS矩阵和方向矩阵计算结束----------------");
		System.out.println("----------开始打印一个LCS----------------");
		LCS_Print(LCS_direction, pStr1, pStr2, length1-1, length2-1);
		System.out.print("\n");
		System.out.println("----------打印一个LCS结束----------------");
		return LCS_length;
	}
	
	
	/*
	 * Print a LCS for two 	Strings
	 * Input: LCS_direction -- a 2d matrix which records the direction of LCS generation
	 * 		pStr1	--	the first String
	 * 		pStr2	--	the second String
	 * 		row		--	the row index in the matrix LCS_direction
	 * 		col		--	the column index int matrix LCX_direction
	 */
	private static void LCS_Print(decreaseDir[][] LCS_direction, String pStr1,
			String pStr2, int row, int col) {
		if(pStr1.equals("")||pStr1==null||pStr2.equals("")||pStr2==null)
			return;
		
		int length1 = pStr1.length();
		int length2 = pStr2.length();
		if(length1==0||length2==0||!(row<length1&&col<length2))
			return;
		/*
		 *	kLeftUp implies a char in the LCS is found	
		 */
		if(LCS_direction[row][col]==decreaseDir.kLeftUp)
		{
			if(row>0&&col>0)
				LCS_Print(LCS_direction, pStr1, pStr2, row-1, col-1);
//			System.out.printf("%c", pStr1.charAt(row));
		/*
		 * print the char	
		 */
			System.out.printf("%c", pStr2.charAt(col));
		}else if(LCS_direction[row][col]==decreaseDir.kLeft)
		{
			/*
			 * move to the left entry in the direction matrix	
			 */
			if(col>0)
				LCS_Print(LCS_direction, pStr1, pStr2, row, col-1);
		}else if(LCS_direction[row][col]==decreaseDir.kUp)
		{
			/*
			 * move to the up entry in the direction matrix	
			 */
			if(row>0)
				LCS_Print(LCS_direction, pStr1, pStr2, row-1, col);
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String pSt1 = "ABCBDAB";
//		String pSt2 = "ABCBDAB";
		String pSt2 = "BDCABA";
		LCS(pSt1, pSt2);
	}

}

public class StringRotateNew {

	/**
	 * 采用String有多首先的地方
	 * 1. str： 需要旋转的字符串
	 * 2. n： 需要旋转的位数
	 */
	public static void LeftRotateString(String str, int n){
		int strLength = str.length();
		if(n>=0 && n<= strLength && strLength>0){
			ReverseString(str, 0, n-1);
			System.out.println("-------------------------");
			ReverseString(str, n, strLength-1);
			System.out.println("-------------------------");
			ReverseString(str, 0, strLength-1);
			System.out.println("-------------------------");
		}else{
			System.out.println("输入的参数illegal");
		}
		System.out.println("Rotate result:"+str);
		
	}
	
	public static void ReverseString(String str , int start, int end){
		//修改后的str无法传出这个方法体，StringBuffer就可以
		System.out.println("orignal str:"+str);
		if(start>=0 && end >=0 && end <= str.length()){
			char[] arr = str.toCharArray();
			while(start < end){
				char temp = str.charAt(start);
				arr[start] = str.charAt(end);
				arr[end] = temp;
				start++;
				end--;
			}
			str = new String(arr);
			System.out.println("Reverse String result:"+str);
		}else{
			System.out.println("输入的参数illegal");
		}
	}
	
	
	public static void main(String[] args) {
		String str = "12A3G4F5 678RT io9";
//		ReverseString(str,0,5);
		System.out.println("-------------------------");
		LeftRotateString(str,5);
		
/*		
                   -------------------------
		orignal str:12A3G4F5 678RT io9
		Reverse String result:G3A214F5 678RT io9
		-------------------------
		orignal str:12A3G4F5 678RT io9
		Reverse String result:12A3G9oi TR876 5F4
		-------------------------
		orignal str:12A3G4F5 678RT io9
		Reverse String result:9oi TR876 5F4G3A21
		-------------------------
		Rotate result:12A3G4F5 678RT io9
*/
	}

}

public class StringRotate {

	/**
	 * 采用String有多受限的地方
	 * 1. str： 需要旋转的字符串
	 * 2. n： 需要旋转的位数
	 */
	public static String LeftRotateString(String str, int n){
		String s1,s2,s3,result = str; 
		int strLength = str.length();
		if(n>=0 && n<= strLength && strLength>0){
			s1 = ReverseString(str, 0, n-1);
			System.out.println("-------------------------");
			s2 = ReverseString(str, n, strLength-1);
			System.out.println("-------------------------");
			s3 = s1.substring(0, n).concat(s2.substring(n, strLength));
			System.out.println("-------------------------"+s3);
			result = ReverseString(s3, 0, strLength-1);
			System.out.println("-------------------------");
		}
		System.out.println("Rotate result:"+result);
		return result;
		
	}
	
	public static String ReverseString(String str , int start, int end){
		System.out.println("str:"+str);
		if(start>=0 && end >=0 && end <= str.length()){
			char[] arr = str.toCharArray();
			while(start < end){
				char temp = str.charAt(start);
				arr[start] = str.charAt(end);
				arr[end] = temp;
				start++;
				end--;
			}
			String result = new String(arr);
			System.out.println("result:"+result);
			return new String(result);
		}else{
			System.out.println("输入的参数illegal");
			return new String(str);
		}
	}
	
	
	public static void main(String[] args) {
		String str = "12A3G4F5 678RT io9";
//		ReverseString(str,0,5);
		System.out.println("-------------------------");
		LeftRotateString(str,5);
		
/*		str:12A3G4F5 678RT io9
		result:G3A214F5 678RT io9
		-------------------------
		str:12A3G4F5 678RT io9
		result:12A3G9oi TR876 5F4
		-------------------------
		-------------------------G3A219oi TR876 5F4
		str:G3A219oi TR876 5F4
		result:4F5 678RT io912A3G
		-------------------------
		Rotate result:4F5 678RT io912A3G
*/
	}

}

public class StringBufferRotate {

	/**
	 * 采用StringBuffer的可以直接操作底层的数组，到达和指针同样地效果，而且具有联动性
	 * 1. strBuffer： 需要旋转的字符串
	 * 2. n： 需要旋转的位数
	 */
	public static StringBuffer LeftRotateString(StringBuffer strBuffer, int n){
		int strLength = strBuffer.length();
		if(n>=0 && n<= strLength && strLength>0){
			ReverseString(strBuffer, 0, n-1);
			System.out.println("-------------------------");
			ReverseString(strBuffer, n, strLength-1);
			System.out.println("-------------------------");
			ReverseString(strBuffer, 0, strLength-1);
			System.out.println("-------------------------");
		}else{
			System.out.println("输入的参数illegal");
		}
		System.out.println("Rotate result:"+strBuffer);
		return strBuffer;
	}
	
	public static void ReverseString(StringBuffer strBuffer , int start, int end){
		//修改后的strBuffer可以传出这个方法体，String就不可以
		System.out.println("orignal str:" + strBuffer);
		if(start>=0 && end >=0 && end <= strBuffer.length()){
			while(start < end){
				char temp = strBuffer.charAt(start);
				strBuffer.setCharAt(start, strBuffer.charAt(end));
				strBuffer.setCharAt(end, temp);
				start++;
				end--;
			}
			System.out.println("Reverse String result:" + strBuffer);
		}else{
			System.out.println("输入的参数illegal");
		}
	}
	
	public static void main(String[] args) {
		StringBuffer str = new StringBuffer("12A3G4F5 678RT io9");
//		ReverseString(str,0,5);
		System.out.println("-------------------------");
//		LeftRotateString(str,0);
//		LeftRotateString(str,50);
		LeftRotateString(str,5);
/*
 *
 * 
		orignal str:12A3G4F5 678RT io9
		Reverse String result:G3A214F5 678RT io9
		-------------------------
		orignal str:G3A214F5 678RT io9
		Reverse String result:G3A219oi TR876 5F4
		-------------------------
		orignal str:G3A219oi TR876 5F4
		Reverse String result:4F5 678RT io912A3G
		-------------------------
		Rotate result:4F5 678RT io912A3G
 * 
 */
	}

}

public class NumOf1 {

	/**
     * 计算一个 非负整数的二进制表示中1的个数
	 * @param int型的num
	 */
	public static int counter1(int num){
		int count = 0;
		while(num!=0){
			if((num&1)!=0)
				count++;
			num = num>>1;
		}
		return count;
	}
	/**
     * 计算一个整数的二进制表示中1的个数
	 * @param int型的num
	 */
	public static int counter2(int num){
		int count = 0;
		int flag = 1;
		while(flag!=0){
			if((num&flag)!=0)
				count++;
			flag = flag<<1;
//			System.out.println("count:"+count);
//			System.out.println("num:"+num);
//			System.out.println("flag:"+flag);
		}
		return count;
	}
	/**
     * 计算一个整数的二进制表示中1的个数
	 * @param int型的num
	 */
	public static int counter3(int num){
		int count = 0;
		while(num!=0){
			count++;
			num = num&(num-1);
		}
		return count;
	}
	
	public static void main(String[] args) {
		System.out.println(counter1(9));
//		System.out.println(counter1(-8)); //counter1不行哦，支持正整数
		System.out.println("-----------------");
		System.out.println(counter1(9));
		System.out.println(counter2(-8));
		System.out.println("-----------------");
		System.out.println(counter3(129));
		System.out.println(counter3(-8));
		System.out.println("-----------------");
	}

}

#include <stack>

/////////////////////////////////////////////////////////////////////////////
// Given a push order of a stack, determine whether an array is possible to 
// be its corresponding pop order
// Input: pPush   - an array of integers, the push order
//        pPop    - an array of integers, the pop order
//        nLength - the length of pPush and pPop
// Output: If pPop is possible to be the pop order of pPush, return true.
//         Otherwise return false
/////////////////////////////////////////////////////////////////////////////
bool IsPossiblePopOrder(const int* pPush, const int* pPop, int nLength)
{
	bool bPossible = false;

	if(pPush && pPop && nLength > 0)
	{
		const int *pNextPush = pPush;
		const int *pNextPop = pPop;

		// ancillary stack
		std::stack<int>stackData;

		// check every integers in pPop
		while(pNextPop - pPop < nLength)
		{
			// while the top of the ancillary stack is not the integer 
			// to be poped, try to push some integers into the stack
			while(stackData.empty() || stackData.top() != *pNextPop)
			{
				// pNextPush == NULL means all integers have been 
				// pushed into the stack, can't push any longer
				if(!pNextPush)
					break;

				stackData.push(*pNextPush);

				// if there are integers left in pPush, move 
				// pNextPush forward, otherwise set it to be NULL
				if(pNextPush - pPush < nLength - 1)
					pNextPush ++;
				else
					pNextPush = NULL;
			}

			// After pushing, the top of stack is still not same as 
			// pPextPop, pPextPop is not in a pop sequence
			// corresponding to pPush
			if(stackData.top() != *pNextPop)
				break;

			// Check the next integer in pPop
			stackData.pop();
			pNextPop ++;
		}

		// if all integers in pPop have been check successfully, 
		// pPop is a pop sequence corresponding to pPush 
		if(stackData.empty() && pNextPop - pPop == nLength)
			bPossible = true;
	}

	return bPossible;
}

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package javaapplication1;

import java.util.Stack;

/**
 *
 * @author lenovo
 */

public class StackSequence {

    public static boolean IsPossiblePopOrder(final int[] pPush, final int[] pPop, int nLength){
// Given a push order of a stack, determine whether an array is possible to 
// be its corresponding pop order
// Input: pPush   - an array of integers, the push order
//        pPop    - an array of integers, the pop order
//        nLength - the length of pPush and pPop
// Output: If pPop is possible to be the pop order of pPush, return true.
//         Otherwise return false

        boolean bPossible = false;
        if((nLength < 0)&&(pPush.length != pPop.length)&&(pPush.length ==0)&&( pPop.length==0)){
            return false;
        }else{
            int currentPushIndex = 0;
            int nextPushIndex = 0;
            int currentPopIndex = 0;
            int nextPopIndex = 0;
            int pNextPush = pPush[nextPushIndex];
            int pNextPop = pPop[nextPopIndex];
            Stack<Integer> stackData = new Stack<Integer>();
            // check every integers in pPop
            while((nextPopIndex - currentPopIndex < nLength) ){
                pNextPop = pPop[nextPopIndex];
                // while the top of the ancillary stack is not the integer 
                // to be poped, try to push some integers into the stack
                while(stackData.empty() || stackData.peek() != pNextPop){
                // pNextPush == -1 means all integers have been 
  		// pushed into the stack, can't push any longer
                   if(nextPushIndex == -1)   break;
                    pNextPush = pPush[nextPushIndex];
		    stackData.push(pNextPush);
        	// if there are integers left in pPush, move 
                // nextPushIndex forward, otherwise set it to be NULL( in java I use -1 instead)
                    if(nextPushIndex - currentPushIndex < nLength - 1)
                            nextPushIndex ++;
                    else
                            nextPushIndex = -1;
               }
                // Check the next integer in pPop
                if(stackData.peek() != pNextPop)   break;
		stackData.pop();
		nextPopIndex ++;
         }
         if(stackData.empty() && nextPopIndex == nLength)
			bPossible = true;
    }
        System.out.println(bPossible);
        return bPossible;
}
    public static void main(String[] args){
        int[] pPush = {1,2,3,4,5};
        int[] pPop ={4,5,3,2,1};
//        int[] pPop ={4,3,5,1,2};
        IsPossiblePopOrder(pPush,pPop,5);
    }
}

void FindContinuousSequence(int n)
{
	if(n < 3)
		return;

	int small = 1; 
	int big = 2;
	int middle = (1 + n) / 2;
	int sum = small + big;

	while(small < middle)
	{
		// we are lucky and find the sequence
		if(sum == n)
			PrintContinuousSequence(small, big);

		// if the current sum is greater than n, 
		// move small forward
		while(sum > n)
		{
			sum -= small;
			small ++;

			// we are lucky and find the sequence
			if(sum == n)
				PrintContinuousSequence(small, big);
		}

		// move big forward
		big ++;
		sum += big;
	}
}

// Print continuous sequence between small and big
void PrintContinuousSequence(int small, int big)
{
	for(int i = small; i <= big; ++ i)
		printf("%d ", i);

	printf("\n");
}

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package javaapplication1;

/**
 *
 * @author lenovo
 */
public class ContinousSum {
    
    
    
    
    
   public static void FindContinuousSequence(int n){
       if(n<=2){
           System.out.println("The num is too small!");
           return;
       }
       int small = 1;
       int big = 2;
       int middle = (n+1)/2;
       int sum = small+big;
       while(small<middle){
           if(sum == n){
               System.out.println("The continous sequence is：");
               PrintContinuousSequence(small, big);
               big ++;
               sum += big;
           }else if(sum > n){
               sum -= small;
               small++;
           }else if(sum < n){
               big++;
               sum += big;
           }
      }
   }
            
   public static void PrintContinuousSequence(int small, int big)
{
	for(int i = small; i <= big; ++ i)
		System.out.printf("%d ", i);
	System.out.printf("\n");
}
   public static void main(String[] args){
       FindContinuousSequence(18);
   }
}

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package javaapplication1;

/**
 *
 * @author lenovo
 */

public class Permutation {
    
//比如：abcd四个字符，
//首先，考虑放在第一个位置的字符，将第一个字符与第一，二，三，四个字符交换。
//1－1：abcd
//1－2：bacd
//1－3：cbad
//1－4：dbca
//其次，考虑第2到n个字符，用递归做。每次都要重新恢复字符串的位置。

    public static void getPermutation(char a[], int start, int end)
        {
            int i;
            char temp;
            if(start == end)//如果到了第N个字符，输出该串
            {
                for(i = 0; i <= end; i++)         
                    System.out.printf(" %c ",a[i]);
                    System.out.printf("\n");
            }
            else
            {
                for(i = start; i <= end; i++)
                {
                    temp=a[start]; a[start]=a[i]; a[i]=temp;
                    getPermutation(a, start+1, end);
                    temp=a[start]; a[start]=a[i]; a[i]=temp;//重新恢复字符串的位置
                }
            }
        }

    public static void main(String[] args){
            char[] A = "abcd".toCharArray();
            getPermutation(A,0,3);

    }
    
}

void PrintListReversely(ListNode* pListHead)
{
	if(pListHead != NULL)
	{
		// Print the next node first
		if (pListHead->m_pNext != NULL)
		{
			PrintListReversely(pListHead->m_pNext);
		}
 
		// Print this node
		printf("%d", pListHead->m_nKey);
	}
}

题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
分析：这是一道很新颖的关于位运算的面试题。
首先我们考虑这个问题的一个简单版本：一个数组里除了一个数字之外，其他的数字都出现了两次。请写程序找出这个只出现一次的数字。
这个题目的突破口在哪里？题目为什么要强调有一个数字出现一次，其他的出现两次？我们想到了异或运算的性质：任何一个数字异或它自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现依次的数字，因为那些出现两次的数字全部在异或中抵消掉了。
有了上面简单问题的解决方案之后，我们回到原始的问题。如果能够把原数组分为两个子数组。在每个子数组中，包含一个只出现一次的数字，而其他数字都出现两次。如果能够这样拆分原数组，按照前面的办法就是分别求出这两个只出现一次的数字了。
我们还是从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其他数字都出现了两次，在异或中全部抵消掉了。由于这两个数字肯定不一样，那么这个异或结果肯定不为0，也就是说在这个结果数字的二进制表示中至少就有一位为1。我们在结果数字中找到第一个为1的位的位置，记为第N位。现在我们以第N位是不是1为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第N位都为1，而第二个子数组的每个数字的第N位都为0。
现在我们已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。因此到此为止，所有的问题我们都已经解决。
基于上述思路，我们不难写出如下代码：
///////////////////////////////////////////////////////////////////////
// Find two numbers which only appear once in an array
// Input: data - an array contains two number appearing exactly once,
//               while others appearing exactly twice
//        length - the length of data
// Output: num1 - the first number appearing once in data
//         num2 - the second number appearing once in data
///////////////////////////////////////////////////////////////////////
void FindNumsAppearOnce(int data[], int length, int &num1, int &num2)
{
	if (length < 2)
		return;
 
	// get num1 ^ num2
	int resultExclusiveOR = 0;
	for (int i = 0; i < length; ++ i)
		resultExclusiveOR ^= data[i];
 
	// get index of the first bit, which is 1 in resultExclusiveOR
	unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR);	
 
	num1 = num2 = 0;
	for (int j = 0; j < length; ++ j)
	{
		// divide the numbers in data into two groups,
		// the indexOf1 bit of numbers in the first group is 1,
		// while in the second group is 0
		if(IsBit1(data[j], indexOf1))
			num1 ^= data[j];
		else
			num2 ^= data[j];
	}
}
 
///////////////////////////////////////////////////////////////////////
// Find the index of first bit which is 1 in num (assuming not 0)
///////////////////////////////////////////////////////////////////////
unsigned int FindFirstBitIs1(int num)
{
	int indexBit = 0;
	while (((num & 1) == 0) && (indexBit < 32))
	{
		num = num >> 1;
		++ indexBit;
	}
 
	return indexBit;
}
 
///////////////////////////////////////////////////////////////////////
// Is the indexBit bit of num 1?
///////////////////////////////////////////////////////////////////////
bool IsBit1(int num, unsigned int indexBit)
{
	num = num >> indexBit;
 
	return (num & 1);
}

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package javaapplication1;

/**
 *
 * @author lenovo
 */
public class JavaApplication1 {

    /**
     * @param args the command line arguments
     */
    public static int getSingle(int[] array){
       int temp = 0;
       for(int a:array){
           temp = a^temp;
       }
       System.out.println(temp);
        return temp;
    }
    
    public static String getSingleTwo(int[] array){
       int temp = 0;
       int num1 = 0;
       int num2 = 0;
       for(int a:array){
           temp = a^temp;
       }
       System.out.println("before division:"+temp);
       int middleResult = FindFirstBitIs1(temp);
       for(int a:array){
           if(IsBit1(a,middleResult)){
               num1 = a^num1;
           }else{
               num2 = a^num2;
           }
       System.out.println("After division , result is num1："+num1+" ,num2："+num2);
       }
       return num1+","+num2;
    }
    
    public static int FindFirstBitIs1(int num){
        int result = 0;
        for(int i=0;i<32;i++){
            int middleResult = (num >>i)^0;
            if(middleResult==1){
                result =i;
            }
        }
        System.out.println(result);
        return result;
    }
    
    public static boolean IsBit1(int num, int indexBit){
        System.out.println(((num>>indexBit)&1)!=0);
        return ((num>>indexBit)&1)!=0;
        
    }
    public static void main(String[] args) {
//        int i = 7;
//        int j = 0;
//        int result = i^j;
//        System.out.println(i+" 异或 "+j+"："+result);
        
//        int[] a = {1,2,3,4,9,1,2,3,4};
//        getSingle(a);
        
//        FindFirstBitIs1(32);
//        IsBit1(8,2);
        
          int[] a = {1,2,3,4,9,1,2,3,4,8};
          getSingleTwo(a);
    }
}