EASY TO UNDERSTAND AND MUCH FASTER(JAVA)


  • 0
    M

    creat the initial array as "122"
    count the number of 1 and extend the array at the same time

    public class LeetCode{
    	public int magicalString(int n) {
    		if(n<=0)return 0;
    		if(n<=3)return 1;
            int[] str=new int[n+1];
            str[0]=1;str[1]=str[2]=2;
            int result=1;
            int flag=1;
            int ext=2;// the begin index of extend
            int len=3;
            for(;len<n;ext++){
            	if(str[ext]==1){
            		str[len++]=flag;
            		result++; //count the num of 1
            	}else{
            		str[len++]=flag;
            		str[len++]=flag;
            	}
            	flag^=3;
            }
            for(int k=ext;k<n;k++){
            	if(str[k]==1)result++;
            }
            return result;     
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.