4.10华为第2题解答

题目没有说清楚是否是递归展开的部分是否需要翻转.事实证明题目的意思是整体展开后才反序

重点在于如何展开,想法是递归.如果没有找到数字那么直接输出原字符串,如果找到数字n,说明数字后面

有一对括号.

原来的字符串拆为4部分,第1部分是数字n之前,第2部分是数字n,第3部分是n后面的括号中内容,第4部分是括号后面部分

s=part1+part2+(part3)+part4

递归展开part3,重复n次后挂到part1后面.再挂上part4递归展开的结果得到整个展开式

下面的代码保留了一些调试信息.如果要通过测试,需要将类名改为Main并且将main函数中的

new HuaWeiQ5()...改为new Main()...

import java.util.*;
public class HuaWeiQ5 {
public String expandString(String s) {
    boolean findNumber=false;
    for(int i=0;i<s.length();i++)
        if(Character.isDigit(s.charAt(i))) {
            findNumber=true;
            break;
        }
    if(!findNumber) {
        StringBuilder sb=new StringBuilder(s);
        sb.reverse();
        //return sb.toString();
        return s;
    }
    Stack<Character>stack=new Stack<Character>();
    int firstDigitPos=-1,lastDigitPos=-1;
        int i=0;
        while(!Character.isDigit(s.charAt(i)))i++;
        firstDigitPos=i;
        while(Character.isDigit(s.charAt(i)))i++;
        lastDigitPos=i-1;
        String part1=s.substring(0,firstDigitPos);
        String part2=s.substring(firstDigitPos,lastDigitPos+1);
        int leftParentesePos=lastDigitPos+1;
        int rightParentesePos=-1;
        //s[leftParentesePos]应该是一个括号,我们需要找到与它匹配的括号
        stack.push(s.charAt(leftParentesePos));
        for(i=leftParentesePos+1;i<s.length();i++) {
            if(isLeftParenthese(s.charAt(i)))
                    stack.push(s.charAt(i));
            else if(isRightParenthese(s.charAt(i)))
                stack.pop();
            if(stack.isEmpty()) {
                rightParentesePos=i;
                break;}
        }
        String part3=s.substring(leftParentesePos+1,rightParentesePos);
        String part4=s.substring(rightParentesePos+1);
        //System.out.println(part1);
        //System.out.println(part2);
        //System.out.println(part3);
        String later=expandString(part4);
                int repeatTimes=Integer.parseInt(part2);
        StringBuilder sb=new StringBuilder(part1);
        part3=expandString(part3);
        for(int j=0;j<repeatTimes;j++)
            sb.append(part3);
        sb.append(later);
    return sb.toString();
}
public boolean isLeftParenthese(char ch) {
    
    return ch=='('||ch=='['||ch=='{';
}
public boolean isRightParenthese(char ch) {
    
    return ch==')'||ch==']'||ch=='}';
}
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //String s="abc3(A)";
        Scanner sc=new Scanner(System.in);
        String s=sc.nextLine();
        String ans=new HuaWeiQ5().expandString(s);
        System.out.println(ans);
    }
}

#华为##笔试题目#

全部评论

推荐最新楼层

热情_

北京长城研修学院算法工程师

package com.company; import java.util.Scanner; public class Main { public static String strGame(String str){ if(str==null||str.length()<=0) return str; String new_str=""; int index[]={0}; String res=getStr(str,index); for(int i=0;i<res.length();i++) new_str=res.charAt(i)+new_str; return new_str; } public static String getStr(String str,int re_index[]){ if(str==null||str.length()<=0) return str; int index=re_index[0]; String res=""; String num=""; while(index<str.length()){ if(str.charAt(index)>='0'&&str.charAt(index)<='9'){ num=num+str.charAt(index); index++; } else if(str.charAt(index)==')'||str.charAt(index)==']'||str.charAt(index)=='}') { re_index[0]=index+1; return res; } else if(str.charAt(index)=='('||str.charAt(index)=='['||str.charAt(index)=='{'){ re_index[0]=index+1; String repeat=getStr(str,re_index); index=re_index[0]; int n=Integer.valueOf(num); num=""; while(n>0){ res+=repeat; n--; } } else{ res+=str.charAt(index); index++; } } return res; } public static void main(String[] args) { // write your code here Scanner sc = new Scanner(System.in); String str = sc.nextLine(); ///abc3(A4(b)) str=strGame(str); System.out.print(str); } }

4.10华为第2题解答

全站热榜

创作者周榜