科大讯飞2021/8/15笔试
30道选择题+3道编程题
1、将一个数的二进制倒数第二位0换成1，输出替换后的结果
输入一个数如10，起二进制表达为1010，将倒是第二位0换成1，输出结果1110，即14
例如2，二进制表达10，倒数第二个0换成1后是110，即6
90%
public int changeNumber (int num) {
//一直循环判断倒数第二个0
int count = 0,base = 0;
int tmp = num;
while (tmp != 0){
if(count == 2){
break;
}
// 判断当前位置上的值
if((num & (int) Math.pow(2,base)) == 0){
count++;
}
base++;
tmp /= 2;
}
if(count == 0){
return num + (int)Math.pow(2,base) + (int)Math.pow(2,base+1);
}else if(count == 1){
return num + (int)Math.pow(2,base);
}else {
return num + (int) Math.pow(2, base-1);
}
} 2、给定一个字符串，长度不超过2*10^5，该字符串由小写字母和?组成,?可以替换成任意字母，求让26个字符完整的最小字符串长度。如不存在，输出-1
输入：abcdefghigklmnopqrstuvwwwxyz 输出：28
输入：abcdefghigklmnopqrstuv????xyz. 输出：26
想到的解题思路是滑动窗口的思想，但是当时没写出来～～ or leetcode的最小覆盖
66.7% 超时
int result = 0;
int targetDis = 0;
public int leafPairs(TreeNode root, int dis) {
targetDis = dis;
leafPairsCore(root, 0);
return result;
}
public List<Integer> leafPairsCore(TreeNode root, int height) {
if (root == null) return new LinkedList<>();
List<Integer> tmp = new LinkedList<>();
if (root.left == null && root.right == null) {
tmp.add(height);
return tmp;
}
List<Integer> left = new LinkedList<>();
if (root.left != null) {
left = leafPairsCore(root.left, height + 1);
}
List<Integer> right = new LinkedList<>();
if (root.right != null) {
right = leafPairsCore(root.right, height + 1);
}
if (left.size() == 0) {
return right;
}
if (right.size() == 0) {
return left;
}
for (Integer itemLeft : left) {
for (Integer itemRight : right) {
if ((itemLeft + itemRight - 2 * height) == targetDis) {
result++;
}
}
}
for (Integer item : left) {
tmp.add(item);
}
for (Integer item : right) {
tmp.add(item);
}
return tmp;
} 