某公司技术岗笔考题

某公司技术岗笔试题
1、用数组实现队列，可实现自动伸缩。当队列满时，容量增加一倍，当队列所占容量不足1/4,将容量减少为原来的一半。
2、将1、2、3、4、5、6……组成一个数，如1234567891011121314151617181920212223……，求第n位为多少
3、结点相连，结点连通具有自反性、传递性、还有一个什么性质忘了，说明结点所得到的是树还是图，还是什么都不是。比如（1,2），（1,3），（1，4），（2,6），（3，5）组成一个树。
[最优解释]
题目二
写了个非常复杂的实现，跪求优化。

public static int get(int x){

int start = 1;//1位数开始位
int end = 9;//1位数结束位
int r = 1;//当前位数
while(true){

if(x <= end){//是不是r位数

int buf = x - start;//离该位开头多少个数
int bit = buf%r;
buf = buf/r;
int b = 1;
int rank = r;

while(rank > 1){
b = b*10;
rank --;
}

buf = buf + b;//定位数

bit = r - bit -1;//取该数的第bit位
while( 0 < bit ){
buf = buf/10;
bit --;
}
buf = buf%10;
return (buf);
}

//更新r位数至r+1位~更新开始结束标识和位数
start = end + 1;
r ++;
int b = 1;
int rank = r;
while(rank > 1){
b = b*10;
rank --;
}
end = 9*b*r + start - 1;

}

}
[其他解释]

题目三
附加条件是不是自反性、传递性、对称性？构建一个临界矩阵表示图
做N-1（N是节点数）次矩阵相乘，矩阵是不是没有0值，没有就是全连通图，否则只能说明不是全连通
不能得到部分连通。
[其他解释]

引用:

题目二
写了个非常复杂的实现，跪求优化。

public static int get(int x){

int start = 1;//1位数开始位
int end = 9;//1位数结束位
int r = 1;//当前位数
while(true){

if(x <= end){//是不是r位数

int buf = x - start;//离……

算法不好..不知道有没问题..
加了写测试代码在里面，大概没问题吧


public static void main(String[] args) {
/*
 * 这一段是测试代码
 */
StringBuffer stringBuffer = new StringBuffer();
for(int i = 1; i &lt; 100000; i ++){
stringBuffer.append(i);
}
for(int i = 0; i &lt; 10000; i ++){
int random = (int) (Math.random() * stringBuffer.length());
if(stringBuffer.charAt(random) - '0' != getNValue(random)){
System.out.println("error");
}
}
}

private static int getNValue(int n){
byte bit = 0;
//计算出n对应的位数
while(getLengthByBit(bit) &lt;= n){
bit ++;
}
//减去前面bit-1位数字的总长度后的剩余长度
long leftLength = n - getLengthByBit(bit - 1);
//计算对应的值
int value = (int) (Math.pow(10, bit - 1) + leftLength / bit);
//取出数字
for(int i = 0; i &lt; bit - 1 - leftLength % bit; i ++)
value /= 10;
value %= 10;
return value; 
 
}

private static long getLengthByBit(int bit){
if(bit == 0)
return 0;
if(bit == 1)
return 9;
else
return (int) (getLengthByBit(bit - 1) + 9 * bit * Math.pow(10, bit - 1));
}

我觉得最重要的是观察长度吧
[1,9]有9位
[1,99]=[1,9]+[10,99]=[1,9]+ 9 * 10 * 2
[1,999]=[1,99] + [100,999]=[1,99] + 9 * 100 * 3
那大概能看出[1,10^n] = [1,10^(n - 1)] + 9 * n * 10^(n - 1)
[其他解释]


    public static int getIndex(int n) {
int length=String.valueOf(n).length();
if(length==1)
    return n;
int temp=(int) Math.pow(10, length-1);
return length*(n-temp+1)+getIndex(temp-1);
    }
    public static void main(String[] args){
System.out.println(getIndex(1234));
    }

[其他解释]
第三个显然不是个树
[其他解释]

有个笔误
“那大概能看出[1,10^n] = [1,10^(n - 1)] + 9 * n * 10^(n - 1)"
-->
[1,10^n - 1] = [1,10^(n - 1)] + 9 * n * 10^(n - 1)
另外


if(bit == 1)            return 9;

这两句是多余的,当然也可以说是用来节约计算时间
[其他解释]

引用:

引用:题目二
写了个非常复杂的实现，跪求优化。

public static int get(int x){

int start = 1;//1位数开始位
int end = 9;//1位数结束位
int r = 1;//当前位数
while(true){

if(x <= end){//是不是r位数

int ……

引用:

有个笔误
“那大概能看出[1,10^n] = [1,10^(n - 1)] + 9 * n * 10^(n - 1)"
-->
[1,10^n - 1] = [1,10^(n - 1)] + 9 * n * 10^(n - 1)
另外
Java code?12if(bit == 1) return 9;
这两句是多余的,当然也可以说是用来节约计算时间
……

思想是一样的，找到是落在多少位数的区间，再去找落在哪个数，再定位到该数的某位，返回。
感觉是不是有更好的算法呢。。。
[其他解释]
该回复于2012-11-21 10:39:50被管理员删除
[其他解释]
学习一下以备使用
[其他解释]
改版后的代码真难看，受不了
[其他解释]
第一题和第三题求代码，然后果断散分！！
[其他解释]
第一题怎么做？
[其他解释]
该回复于2012-11-24 09:57:59被管理员删除

某公司技术岗笔考题

热点推荐