人民搜索笔试题3

关于atoi()函数

/* 
    * name:xif 
    * coder:xifan@2010@yahoo.cn 
    * time:08.20.2012 
    * file_name:my_atoi.c 
    * function:int my_atoi(char* pstr) 
    */  
      
    int my_atoi(char* pstr)  
    {  
        int Ret_Integer = 0;  
        int Integer_sign = 1;  
          
        /* 
        * 判断指针是否为空 
        */  
        if(pstr == NULL)  
        {  
            printf("Pointer is NULL\n");  
            return 0;  
        }  
          
        /* 
        * 跳过前面的空格字符 
        */  
        while(isspace(*pstr) == 0)  
        {  
            pstr++;  
        }  
          
        /* 
        * 判断正负号 
        * 如果是正号，指针指向下一个字符 
        * 如果是符号，把符号标记为Integer_sign置-1，然后再把指针指向下一个字符 
        */  
        if(*pstr == '-')  
        {  
            Integer_sign = -1;  
        }  
        if(*pstr == '-' || *pstr == '+')  
        {  
            pstr++;  
        }  
          
        /* 
        * 把数字字符串逐个转换成整数，并把最后转换好的整数赋给Ret_Integer 
        */  
        while(*pstr >= '0' && *pstr <= '9')  
        {  
            Ret_Integer = Ret_Integer * 10 + *pstr - '0';  
            pstr++;  
        }  
        Ret_Integer = Integer_sign * Ret_Integer;  
          
        return Ret_Integer;  
    }

2、翻转一个句子，其中单词是正序的

算法：

1、将字符串str[0]和str[str.length-1]互换元素，str[1]和str[str.length-2]互换元素····直到将str翻转；时间复杂度：O(n/2)

2、再将单词翻转。时间复杂度：O(nlog2(n))

package peopleseach;


/**
 * 翻转一个句子，其中单词是正序的
 * 
 * @author he
 * 
 */
public class OverturnSentence {
    
    private static String overturn(String ss) {
        char[] sentence = ss.toCharArray();
        //将字符串str[0]和str[str.length-1]互换元素，str[1]和str[str.length-2]互换元素····直到将str翻转；时间复杂度：O(n/2)
        for(int i=0;i<sentence.length/2;i++){
            char temp = sentence[i];
            sentence[i] = sentence[sentence.length-1-i];
            sentence[sentence.length-1-i] = temp;
        }
        System.out.println(new String(sentence));
        int start = 0;
        for(int i=0;i<sentence.length;i++){
            if(!((sentence[i] >= 'a'&&sentence[i]<='z') ||(sentence[i] >= 'A'&&sentence[i]<='Z'))){
                //如果不是英文字符,说明一个字符完结，即str[start]-str[i-1]组成一个单词。接着就对该单词翻转
                for(int j=0;j<(i-start)/2;j++){
                    char temp = sentence[start+j];
                    sentence[start+j] = sentence[i-1-j];
                    sentence[i-1-j] = temp;
                }                
                start = i+1;
            }
        }
        return new String(sentence);
    }
    
    
    /**
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(overturn("I am a good boy!"));
    }

}

3、二叉树两个结点中的最小公共子结点==>求长度，长度之差，远的先走，再一起走

4、三角阵中从第一行到最后一行(给出搜索方向的限制)找一个连续的最大和。

package peopleseach;

/** 
 * @author he
 *         题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。 
 *         求所有子数组的和的最大值。要求时间复杂度为O(n)。 浙大数据结构课本上有 思路: 
 *         求连续数字之和,当和为负值,抛弃.当和为正值,比较其与最大值,如大于,则替换之 
 */  
public class ContinuationMax {
    
    /**
     * 连续的最大和
     * @param array 上三角矩阵的压缩存储数组
     */
    public static void findMax(int[] array) {
        int curMax = 0,max = 0;
        for(int i=0;i<array.length;i++){
            curMax += array[i];
            if(curMax < 0)
                curMax = 0;
            else if(curMax > max)
                max = curMax;
        }
        //if all data is negative
        if(max == 0){
            max = array[0];
            //find the max negative
            for(int i=1;i<array.length;i++)
                if(array[i]>max)
                    max = array[i];
        }
        System.out.println("The ContinuationMax is "+max);
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        int[][] tarray = new int[][]{
                {1, -2, 3, 10},{Integer.MAX_VALUE,-2, -3, 5},{Integer.MAX_VALUE,Integer.MAX_VALUE,6,-7},{Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,11}};
        int n=(1+tarray.length)*tarray.length/2;
        int[] array = new int[n];
        int m = 0;
        for(int i=0;i<tarray.length;i++)
            for(int j=i;j<tarray.length;j++){
                array[m++] = tarray[i][j];
                System.out.println(tarray[i][j]);
            }
        findMax(array);
    }

}

5、实现一个STL中的vector中的尽量多的方法。

6、字符串移动（字符串为*号和26个字母的任意组合，把*号都移动到最左侧，把字母移到最右侧并保持相对顺序不变），要求时间和空间复杂度最小。

/** 
    ** author :hackbuteer
    ** 时间复杂度 :O(n);空间复杂度：O(1)  
　　 ** 注意：从str数组末尾向前遍历要优于从前向后遍历
    **/  
    void Arrange(char *str , int n) 
    { 
        int i , k = n-1; 
        for(i = n - 1 ; i >= 0 ; --i) 
        { 
            if(str[i] != '*') 
            { 
                if(str[k] == '*') 
                { 
                    str[k] = str[i]; 
                    str[i] = '*'; 
                } 
                --k; 
            } 
        } 
    }

7、说说outer join、inner join、left join、right join的区别是什么？

SQL语句:sql内连接和外连接。（inner join）内连接就是表结果集的交集，外连接（outer join）是表结果集的并集。 外连接又分为左连接(left join)和右连接(right join)。