8月24日shopee笔试编程题讨论

第1题给一个整数，然后1为a,b,c 2为e,f,g,以此类推，要求打印出所有可能情况，按字典序

比如输入12 输出
ad
ae
af
bd
be
bf
cd
ce
cf

用递归解决（毕竟本身就必须要指数级复杂，应该没有比递归更舒服的了）

 public class Main {
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         String n = sc.nextLine();
         int x=0;
         String d="";
         if(n.length()>0)print(n,d,x);
     }
 
     public static void print(String n,String d,int x){
         if(x==n.length()){
             System.out.println(d);
             return;
         }
         char c=n.charAt(x);
         char add='a';
         String newd=d;
         int offset= (int)(c-'1');
         if(offset==8){
             add+=8*3;
             newd=d+String.valueOf(add);
             print(n,newd,x+1);
             add+=1;
             newd=d+String.valueOf(add);
             print(n,newd,x+1);
         }else{
             add+=offset*3;
             newd=d+String.valueOf(add);
             print(n,newd,x+1);
             add+=1;
             newd=d+String.valueOf(add);
             print(n,newd,x+1);
             add+=1;
             newd=d+String.valueOf(add);
             print(n,newd,x+1);
         }
         return;
     }
 
 }

第2题跟爬楼梯类似，整数背包，数n 有20 10 5 4 2 1来减求次数最少，-》用打表大法加递归

public class Main {
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         int n = sc.nextInt();
         int ans = 0;
         HashMap<Integer,Integer> ***=new HashMap<Integer,Integer>();
         ans=gotnum(n,***);
         System.out.println(ans);
     }
     public static int gotnum(int n,HashMap<Integer,Integer> c){
         int min=99999999;
         if(n==0)return 0;
         if(c.containsKey(n))return c.get(n);
         if(n>=20){
             min=Math.min(min,gotnum(n-20,c));
         }
         if(n>=10){
             min=Math.min(min,gotnum(n-10,c));
         }
         if(n>=5){
             min=Math.min(min,gotnum(n-5,c));
         }
         if(n>=4){
             min=Math.min(min,gotnum(n-4,c));
         }
         if(n>=2){
             min=Math.min(min,gotnum(n-2,c));
         }
         if(n>=1){
             min=Math.min(min,gotnum(n-1,c));
         }
         c.put(n,min+1);
         return min+1;
     }
 }

第3题计算器，只有加减乘除括号，数字在0-9，就逆波兰表达式就行

1+2*3-（5-4）+6/3

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String n = sc.nextLine();
        int ans = 0, x=0,y=0;
        char d;
        Stack<Character> cal=new Stack<Character>();
        Stack<Integer> num=new Stack<Integer>();
        for(int i = 0; i < n.length(); i++){
            if(n.charAt(i)==')'){
                while(cal.peek()!='('){
                    d=cal.pop();
                    x=num.pop();
                    y=num.pop();
                    if(d=='+'){
                        num.push(x+y);
                    }
                    if(d=='-'){
                        num.push(y-x);
                    }
                    if(d=='*'){
                        num.push(x*y);
                    }
                    if(d=='/'){
                        num.push(y/x);
                    }
                }
                cal.pop();
                continue;
            }
            if(n.charAt(i)=='('){cal.push('(');continue;}
            if(n.charAt(i)=='+'||n.charAt(i)=='-'){
                while(!cal.empty()&&cal.peek()!='('){
                    d=cal.pop();
                    x=num.pop();
                    y=num.pop();
                    if(d=='+'){
                        num.push(x+y);
                    }
                    if(d=='-'){
                        num.push(y-x);
                    }
                    if(d=='*'){
                        num.push(x*y);
                    }
                    if(d=='/'){
                        num.push(y/x);
                    }
                }
                cal.push(n.charAt(i));
                continue;
            }
            if(n.charAt(i)=='*'||n.charAt(i)=='/'){
                cal.push(n.charAt(i));
                continue;
            }
            if(n.charAt(i)>='0'&&n.charAt(i)<='9'){
                num.push((int)(n.charAt(i)-48));
                continue;
            }
            System.out.println("ERROR");
            return;
        }
        while(!cal.empty()){
            d=cal.pop();
            x=num.pop();
            y=num.pop();
            if(d=='+'){
                num.push(x+y);
            }
            if(d=='-'){
                num.push(y-x);
            }
            if(d=='*'){
                num.push(x*y);
            }
            if(d=='/'){
                num.push(y/x);
            }
        }
        ans=num.pop();

        System.out.println(ans);
    }
}

#Shopee##笔试题目#