某公司技术岗笔试题
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 void main(String[] args) {
/*
* 这一段是测试代码
*/
StringBuffer stringBuffer = new StringBuffer();
for(int i = 1; i < 100000; i ++){
stringBuffer.append(i);
}
for(int i = 0; i < 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) <= 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 < 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));
}
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));
}
if(bit == 1) return 9;
