人民搜索笔试题2

2、假设数组B是升序Int数组A循环移若干得到的位，实现对数组B进行查找的高效算法

step1:从数组的末尾向前遍历，比较B[i]<B[i-1],如果是，则B[i]就是A[0],记录下标j=i;

step2:判读查找数据data,data>B[0],则在B[0]~B[j-1]范围内通过二分查找查找该data；如果data<B[i],则在B[j]~B[B.length-1]范围内通过二分查找查找该data;

step3:输出该data在数组B中的下标

时间复杂度:假设数组长度为n，查找下标j的时间复杂度为O(n),查找data的时间复杂为：O(log2(n)),总的时间复杂度为O(n+log2(n))=O(n)。

3、只有整数和+-*/四种运算组成的算术表达书，实现其求值

考察的是后缀表达式，运用到栈的知识点。

package stack;

public class MyStack {
    private int maxSize;
    private int[] stackArray;
    private int top;

    public MyStack(int s) {
        maxSize = s;
        stackArray = new int[maxSize];
        top = -1;
    }

    public void push(int c) {
        stackArray[++top] = c;
    }

    public int pop() {
        return stackArray[top--];
    }

    public int peek() {
        return stackArray[top];
    }

    public boolean isEmpty() {
        return (top == -1);
    }

    public boolean isFull() {
        return (top == maxSize - 1);
    }

    
    public static void main(String[] args) {
        MyStack theStack = new MyStack(10);
//        theStack.push(10);
//        theStack.push(20);
//        theStack.push(30);
//        theStack.push(40);
//        theStack.push(50);
        while (!theStack.isEmpty()) {
            long value = theStack.pop();
            System.out.print(value);
            System.out.print(" ");
        }
        System.out.println("");
    }
}

package peopleseach;

import java.util.Scanner;

import stack.MyStack;

/**
 * 后缀表达式
 * 
 * @author he
 * 
 */
public class SuffixExpression {

    /**
     * 输入后缀表达式
     * 
     * @param expression
     *            后缀表达式
     */
    private static String InputExpression(MyStack stack) {
        Scanner scanner = new Scanner(System.in);
        String signStr="";//符号字符串
        String str = null;
        do {
            System.out.println("请输入整数或者计算符----输入q即为退出");
            str = scanner.nextLine();
            if (!str.isEmpty() && !"q".equals(str)) {
                char c = str.charAt(0);
                //如果是计算符号，则拼接成符号字符串
                if(c=='+'||c=='-'||c=='*'||c=='/')
                    signStr+=c;
                else
                    //如果是整数，则入栈
                    stack.push(Integer.parseInt(str));
            }
        } while (!"q".equals(str));
        return signStr;
    }

    /**
     * 计算后缀表达式
     * 
     * @param signStr
     *            计算符号字符串
     */
    private static void calculate(MyStack stack, String signStr) {
        int result=0;
        for (int i = 0; i < signStr.length(); i++) {
            char c = signStr.charAt(i);
            int b = stack.pop();
            int a = stack.pop();
            switch (c) {
            case '+':
                result = a + b;
                break;
            case '-':
                result = a - b;
                break;
            case '*':
                result = a * b;
                break;
            case '/':
                result = a / b;
                break;
            }
            stack.push(result);
        }
        System.out.println("计算结果为："+result);
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        MyStack stack = new MyStack(10);
        String signStr = InputExpression(stack);
        calculate(stack, signStr);
    }

}

 4、还有一个是考贪心算法的，你让他们看算法导论那本书，关于fractional knapsack problem的那一段，就是0-1背包的一种变形；

5、链表相邻元素翻转，如a->b->c->d->e->f-g，翻转后变为：b->a->d->c->f->e->g

6、求正整数n所有可能的和式的组合（如；4=1+1+1+1、1+1+2、1+3、2+1+1、2+2）