猿辅导前两题

第一题：

import java.util.Stack;

public class Partion1 {

    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        String s = sc.nextLine();
//        int n = Integer.parseInt(s);
//        Partion1 partion1 = new Partion1();
//        String[] res = new String[n];
//        for(int i=0;i<n;i++){
//            String s1 = sc.nextLine();
//           res[i]=partion1.partion(s1);
//        }
//        for(int i=0;i<n;i++){
//            System.out.print(res[i]);
//            if(i!=n-1){
//                System.out.println();
//            }
//
//        }
//        5
//A11B
//(AA)2A
//((A2B)2)2G
//(YUANFUDAO)2JIAYOU
//A2BC4D2
        Partion1 partion1 = new Partion1();
        System.out.println(partion1.partion("(AA)2A"));
    }

    private String partion(String s){
        if(s==null||s.length()==0) return "";
        Stack<String> stack = new Stack<>();
        for(int i=0;i<s.length();){
            char c = s.charAt(i);
            if(c=='('){
                stack.add("(");
            }else if(c==')'){
                //合并（ 与）之间的字符串，以便后面出现数字重复
                StringBuffer buffer = new StringBuffer();
                String pop1 = stack.pop();
                while(!("(".equals(pop1))){
                    buffer.insert(0,pop1);
                    pop1 = stack.pop();
                }
                stack.add(buffer.toString());
            }else if(Character.isDigit(c)){
                //读取多位数字
                int index = i+1;
                while(index<s.length()&&Character.isDigit(s.charAt(index))){
                    index++;
                }
                int n = Integer.parseInt(s.substring(i,index));
                //重复多次字符串
                String s1 = stack.pop();
                StringBuffer stringBuffer = new StringBuffer();
                for(int k=0;k<n;k++){
                    stringBuffer.append(s1);
                }
                stack.add(stringBuffer.toString());
                i= index-1;
            }else {
                stack.add(String.valueOf(c));
            }
            i++;
        }
        if(stack.isEmpty()){
            return "";
        }else {
            StringBuffer sb = new StringBuffer();
            int size = stack.size();
            for(int i=0;i<size;i++){
                sb.insert(0,stack.pop());
            }
            return sb.toString();
        }

    }
}

第二题：

import java.util.Arrays;
import java.util.Scanner;

public class Partion2 {

    public static void main(String[] args) {
//        Scanner sc= new Scanner(System.in);
//        String s = sc.nextLine();
//        String[] s1 = s.split(" ");
//        int N = Integer.parseInt(s1[0]);
//        int M = Integer.parseInt(s1[1]);
//        int k = Integer.parseInt(s1[2]);
//        int[][] nums = new int[N][M];
//        for(int i=0;i<N;i++){
//            String s2 = sc.nextLine();
//            String[] s3 = s2.split(" ");
//            for(int j=0;j<M;j++){
//                nums[i][j] = Integer.parseInt(s3[j]);
//            }
//        }

        int[][] nums = new int[][]{{1,3,3},{2,4,9},{8,9,2}};

        Partion2 partion2 = new Partion2();

        System.out.println(partion2.pathLen1(nums,1));
    }

    public  int pathLen(int[][] nums,int k){
        if(nums==null || nums.length==0 ) return 0;
        if(k<0) k = 0;
        rows = nums.length;
        cols = nums[0].length;
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                dfs(i,j,k,0,nums);
            }
        }
        return maxLen;
    }

    private int maxLen = 0;
    private int[][] dir = {{-1,0},{1,0},{0,1},{0,-1}};
    public void dfs(int r,int c,int k,int path,int[][] nums){
        if(k<0 || path==rows*cols){
            return;
        }
        path++;
        maxLen = Math.max(path,maxLen);
        for(int[] d:dir){
            int rNext = r+d[0];
            int cNext = c+d[1];
            if(rNext<0 ||rNext>=nums.length || cNext<0 || cNext>=nums[0].length ){
                continue;
            }
            if(nums[rNext][cNext] <=nums[r][c]){
                dfs(rNext,cNext,k-1,path,nums);
            }else {
                dfs(rNext,cNext,k,path,nums);
            }
        }

    }




    //带记忆的dfs

    private int rows=0;
    private int cols = 0;
     public  int pathLen1(int[][] nums,int k){
        if(nums==null || nums.length==0 ) return 0;
        if(k<0) k = 0;
        rows = nums.length;
        cols = nums[0].length;
        boolean[][] used = new boolean[rows][cols];
        int[][][] dp = new int[rows][cols][k+1];
        int res = 0;
        for(int i=0;i<nums.length;i++){
            for(int j=0;j<nums[0].length;j++){
                dp[i][j][k] = dfs1(i,j,k,nums,dp);
                res = Math.max(res,dp[i][j][k]);
            }
        }
        return res;
    }


    public int dfs1(int r,int c,int k,int[][] nums,int[][][] dp){
         if(dp[r][c][k]!=0) return dp[r][c][k];
        dp[r][c][k] = 1;
        for(int[] d:dir){
            int rNext = r+d[0];
            int cNext = c+d[1];
            if(rNext<0 ||rNext>=rows || cNext<0 || cNext>=cols ){
                continue;
            }
            if(nums[rNext][cNext] <=nums[r][c] && k>0){
                dp[r][c][k] = Math.max(dp[r][c][k],dfs1(rNext,cNext,k-1,nums,dp)+1);
            }else if(nums[rNext][cNext] > nums[r][c]){
                dp[r][c][k] = Math.max(dp[r][c][k],dfs1(rNext,cNext,k,nums,dp)+1);
            }
        }
        return dp[r][c][k];
    }


}