|
锁定老帖子 主题：最新的百度笔试题
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-10-26
izat 写道
chinpom 写道
public class PowerQuestion {
public static int modeXp(int x, int y, int n) {
if (y == 0) return 1;
int z = modeXp(x, y >> 1, n); //把y除以2并取整
if ((y & 1) == 0) { //如果y为偶数
return (z * z) % n;
} else {
return (x * z * z) % n;
}
}
public static void main(String[] args) {
System.out.println(modeXp(9, 9, 1000));
}
}
假设N为 x,y,n 三个数中最长的二进制位数，则算法的时间复杂度为O(N^3)。
lz的解法不会越界的吧 - -# 可以优化倒是肯定的
public static int foo(int a, int b) {
a = a % 1000;
int res = a;
int i = 1;
for (; i * 2 < b; i *= 2) {
res *= res;
res %= 1000;
}
for (; i < b; i++) {
res *= a;
res %= 1000;
}
return res;
}
|
| 返回顶楼 | |
|
发表时间：2010-10-26
2.仅用O(1)的空间复杂度，把int数组分为2部分，奇数靠左，偶数靠右
考查的快速排序算法，只不过比较的不是大小而是奇偶 while(back>front) front：从前往后遍历数组，遇到奇（偶） 停下 back：从后往前遍历数组，遇到偶（奇） 停下 if back>front 交换数组中front,back位置数据, back--,front++ |
| 返回顶楼 | |
|
发表时间：2010-10-26
3.判断一个括号字符串是否正确匹配，比如什么({})<[(())]>之类的
我答的用了编译原理的递归向下法 表达式求解的一部分,,记得可以用栈的方式解决,(用2个栈) 算法（算法题我都有瞎做的成分，就不写我的解法了） 1.写个函数用于对变形的递增数组进行二分查找，比如这样的[7, 8, 9, 1, 2, 3]从1开始循环地看是递增的，但事先你不知道从哪一位开始递增。并且分析时间复杂度。 题意不明确 变形的递增数组是不是1次变形[7, 8, 9, 1, 2, 3] 还是有可能多次变形[7, 8, 9, 4, 5, 6,1, 2, 3] 另外是不是还有混合方式 [7 ,10 ,12, 8 ,9 ,11 ,1 ,2 ,3] 1).第一种情形,且查询量小:可以直接用二分法查找,比较的时候会发生状态转移 2).做预处理,建立索引(或排序) |
| 返回顶楼 | |
|
发表时间：2010-10-26
yymt 写道 2.仅用O(1)的空间复杂度，把int数组分为2部分，奇数靠左，偶数靠右
考查的快速排序算法，只不过比较的不是大小而是奇偶 while(back>front) front：从前往后遍历数组，遇到奇（偶） 停下 back：从后往前遍历数组，遇到偶（奇） 停下 if back>front 交换数组中front,back位置数据, back--,front++ 一个back，一个front，空间复杂度就是O(2)! 交换两个数的位置，一般也需要用到临时存储变量吧！这点好像没细说吧！ 虽然可以用a+b;a-b;a-b来减少个临时变量 |
| 返回顶楼 | |
|
发表时间：2010-10-26
bachelor007 写道 yymt 写道 2.仅用O(1)的空间复杂度，把int数组分为2部分，奇数靠左，偶数靠右
考查的快速排序算法，只不过比较的不是大小而是奇偶 while(back>front) front：从前往后遍历数组，遇到奇（偶） 停下 back：从后往前遍历数组，遇到偶（奇） 停下 if back>front 交换数组中front,back位置数据, back--,front++ 一个back，一个front，空间复杂度就是O(2)! 交换两个数的位置，一般也需要用到临时存储变量吧！这点好像没细说吧！ 虽然可以用a+b;a-b;a-b来减少个临时变量 O(1)表示常数空间的意思吧,,并不是指用1个变量吧... |
| 返回顶楼 | |
|
发表时间：2010-10-26
yymt 写道 O(1)表示常数空间的意思吧,,并不是指用1个变量吧... 你是对的 |
| 返回顶楼 | |
|
发表时间：2010-10-26
fwoncn 写道 1.0<a,b<100000，求幂a^b结果的最后三位数 1.用一个数组a来存放每次乘法得出结果的后三位 2.每次做乘法运算的时候，跟数组进行对比，不存在继续运算,如果存在，进入步骤3 3.记录对应的下标index和数组的大小length，a[index]和a[length-1]之间是循环出现的 4.（省略......） 总结：最多做1000次乘法运算，进行的比较次数最多为n*logn(n<=1000) |
| 返回顶楼 | |
|
发表时间：2010-10-26
都是大牛啊
|
| 返回顶楼 | |
|
发表时间：2010-10-26
参考izat的思路，再做成递归，应该可以再减少一些计算量：
public class Tst4 { public static void main(String[] args) { System.out.println(cal(3,10,1000)); } public static int cal(int a, int b, int div){ a = a % div; if(a == 0){ return 0; } return calMode(a, b, div); } public static int calMode(int a, int b, int div){ if(a == 1 || b==0){ return 1; } if(b == 1){ return a; } int result = a; int i=2; for(; i<=b; i*=2){ result *= result; result %= div; } i/=2; return (result * calMode(a, b-i, div)) % 1000; } } |
| 返回顶楼 | |
|
发表时间：2010-11-18
//Get a^b last 3 digit.
public static int powerLast3(int a, int b)
{
int result = getLast3(a);
for(int i=0; i<b-1; i++)
{
result *= getLast3(a);
result = getLast3(result);
}
return result;
}
//Get x last 3 digit.
public static int getLast3(int x)
{
return x%1000;
}
符号匹配判断：
public static boolean isMatched(String src)
{
List<Character> stack = new ArrayList<Character>();
for(int i=0; i<src.length(); i++)
{
char x= src.charAt(i);
if (stack.size() > 0) {
if (isCharMatched(stackTop(stack), x)) {
stack.remove(stack.size() - 1);
continue;
}
}
stack.add(x);
}
if(stack.size()==0)
return true;
return false;
}
private static char stackTop(List<Character> stack) {
return ((char)stack.get(stack.size()-1));
}
private static boolean isCharMatched(char src, char target)
{
if(src=='<' && target=='>')
return true;
if(src=='(' && target==')')
return true;
if(src=='[' && target==']')
return true;
if(src=='{' && target=='}')
return true;
return false;
}
二分查找
public static int binarySearch(int[] src, int x)
{
int base = base(src);
int leftIndex = 0;
int rightIndex = src.length-1;
while(leftIndex <= rightIndex)
{
int m = src[l2p((leftIndex + rightIndex)/2, base, src.length)];
if(m==x)
return l2p((leftIndex+rightIndex)/2, base, src.length);
if(x<m)
{
rightIndex = (leftIndex+rightIndex)/2-1;
}else {
leftIndex = (leftIndex+rightIndex)/2+1;
}
}
return -1;
}
public static int l2p(int index, int base, int size)
{
return (index+base)%size;
}
/**
* @param src
*/
private static int base(int[] src) {
int left=0, right=src.length-1;
while(left<right-1)
{
if(src[(left+right)/2] >= src[left]) {
left = (left+right)/2;
}else
{
right = (left+right)/2;
}
}
return left + 1;
}
|
| 返回顶楼 | |
LZ那样求幂a^b结果的最后三位数的话，就算是long型都会很快越界的。比如 20^15 就已经超过64位有符号的最大long值了，而且大量的乘法的效率低。原问题的形式可以用 x^y mod N 来表示，这在RSA加密算法中是属于基础的准备算法，可以这样来求：
