常见编程题目

1. 最长公共序列问题，（）

code
public class LCS {

public int[][] getMatrix(String aStr,String bStr){
    int aLen = aStr.length();
    int bLen = bStr.length();
    
    int[][] matrix = new int[aLen+1][bLen+1];
    
    for(int i=0;i<=aLen;i++){
        for(int j=0;j<=bLen;j++){
            if(i==0||j==0){
                matrix[i][j]=0;                 
            }else if(aStr.charAt(i-1)==bStr.charAt(j-1)){
                matrix[i][j]=matrix[i-1][j-1]+1;
            }else{
                int a=matrix[i-1][j];
                int b=matrix[i][j-1];
                matrix[i][j]=a>=b?a:b;
            }
            
        }
    }
    return matrix;
}


public int subStrL(String str1,String str2){
    int len1 = str1.length();
    int len2 = str2.length();
    
    int result =0;
    int c[][]=new int[len1+1][len2+1];
    
    for(int i=0;i<=len1;i++){
        for(int j=0;j<=len2;j++){
            if(i==0||j==0){
                c[i][j]= 0;
            }
            else if(str1.charAt(i-1)== str2.charAt(j-1)){
                c[i][j]= c[i-1][j-1]+1;
                result = Integer.max(c[i][j], result);
            }else{
                c[i][j]=0;
            }
        }
    }
    
    return result;
}

public static void main(String[] args){
    LCS lcs = new LCS();
    String aString="fyghyr", bString="a3afhyghyt";
    int [][] b = lcs.getMatrix(aString,bString);
    
    System.out.println("max lcs length    "+b[aString.length()][bString.length()]);
    
    int i=aString.length(),j=bString.length();
    String lcString="";
    
    while(i!=0&&j!=0){
        if(aString.charAt(i-1)==bString.charAt(j-1)){
            lcString=aString.charAt(i-1)+lcString;
            i--;
            j--;
        }else if(b[i-1][j]>=b[i][j-1]){
            i--;
        }else{
            j--;
        }
    }
    
    System.out.println(lcString);
    System.out.println(lcs.subStrL(aString, bString));
}

}

#### 2. 最大公约数问题

辗转相除。
最小公倍数 = m*n/最大公约数

#### 3. 全排列（带重复）

#### 4. 最长递增序列

#### 5. 括号匹配问题
stack
#### 6. 旋转数组的最小值
```code```
    int a [] = {2,3,5,6,-1,0,1};
        
        int start = 0;
        int end = a.length-1;
        while(a[start]>=a[end]){
            if(end-start==1){
                System.out.println(a[end]);
                return;
            }else{
                int middle = (start+end)/2;
                if(a[middle]>a[start]){
                    start=middle;
                }else if(a[middle]<a[end]){
                    end=middle;
                }
            }
        }
        
        System.out.println(a[start]);

7.给定一组数字能组成的最大整数

高位到低位依次比较， 排序

8.中序表达式转后序，后序表达式的计算

package com.hq;

import java.util.Stack;

public class Calculate {
    public String toBehind(String middle){
        String newExpr = "";
        Stack<Character> stack = new Stack<>();
        
        for(int i=0;i<middle.length();i++){
            char c = middle.charAt(i);
            switch(c){
            case '(':
                stack.push(c);
                break;
            case ')':
                if(stack.isEmpty()){
                    System.out.println("error");
                    return "error";
                }
                while(!stack.isEmpty()&& stack.peek()!='('){
                    newExpr+=stack.pop();
                }
                stack.pop();
                break;
                
            default:
                if(isOp(c)){
                    if(stack.isEmpty()||stack.peek()=='('){
                        stack.push(c);
                    }else{
                        if(getPri(c)> getPri(stack.peek())){
                            stack.push(c);
                        }else{
                            while (!stack.isEmpty()&& stack.peek()!='('&&getPri(c)<=getPri(stack.peek())) {
                                newExpr+=stack.pop();
                            }
                            
                            stack.push(c);
                        }
                    }
                }else{
                    newExpr+=c;
                }
                break;
            }
            
        }
        while (!stack.isEmpty()) {
            newExpr+=stack.pop();
        }
        return newExpr;
    }
    
    
    public boolean isOp(char c){
        return c=='/'||c=='+'||c=='-'||c=='*';
    }
    
    public int getPri(char c) {
        if(c=='*'||c=='/'){
            return 2;
        }
        return 1;
    }
    
    
    public boolean isNum(char c){
        return '0'<=c && '9'>=c;
    }
    
    public double calculate(String behind){
        Stack<Double> stack  = new Stack<>();
        for(int i=0;i<behind.length();i++){
            char c = behind.charAt(i);
            if(isNum(c)){
                stack.push(Double.parseDouble(c+""));
            }else{
                double b = stack.pop();
                double a = stack.pop();
                switch (c) {
                case '*':
                    stack.push(a*b);
                    break;
                case '/':
                    stack.push(a/b);
                    break;
                case '+':
                    stack.push(a+b);
                    break;
                case '-':
                    stack.push(a-b);
                    break;
                default:
                    break;
                }
            }
        }
        
        if(stack.isEmpty()){
            return 0;
        }
        return stack.pop();
    }
    public static void main(String[] args){
        Calculate calculate = new Calculate();
        
        System.out.println(calculate.toBehind("9-1*(3+1)-2"));
        
        System.out.println(calculate.calculate(calculate.toBehind("9-1*(3+1)-2")));
    }
}

9. 序列化和反序列化二叉树