某公司技术岗笔试题

Question

1、用数组实现队列，可实现自动伸缩。当队列满时，容量增加一倍，当队列所占容量不足1/4,将容量减少为原来的一半。
2、将1、2、3、4、5、6……组成一个数，如1234567891011121314151617181920212223……，求第n位为多少
3、结点相连，结点连通具有自反性、传递性、还有一个什么性质忘了，说明结点所得到的是树还是图，还是什么都不是。比如（1,2），（1,3），（1，4），（2,6），（3，5）组成一个树。

Answer 1

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

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;

}


}

Answer 2

算法不好..不知道有没问题..
加了写测试代码在里面，大概没问题吧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));
}我觉得最重要的是观察长度吧
[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)

Answer 3

有个笔误
“那大概能看出[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;这两句是多余的,当然也可以说是用来节约计算时间

Answer 4

    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));
    }