/* * 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)。