788. 旋转数字

解题思路

• 利用前面已经求出的数来判断后续数据是否为好数，将现在要查的数分为前面几位和最后一位

约规

• 0、1、8为普通数，在pd中为0，而2、5、6、9为好数，在pd中为1，而其余为坏数，在pd中为-1；

举例

• 例如将1021：分为102和1，通过判断102和1是否为好数来判断1021是否为好数
  • 若102和1中有任一数为好数，则1021为好数；
  • 若102和1中有任一数为坏数，则1021为坏数；
  • 而只有当102和1均为普通数时，1021为普通数
  • （上述1021为好数，只是举个例子）

初始化

• 通过打表写出得出10是好数/坏数，并且赋值给 pd 数组

    int[] pd=new int[10001];
    pd[0]=0;
    pd[1]=0;
    pd[2]=1;
    pd[3]=-1;
    pd[4]=-1;
    pd[5]=1;
    pd[6]=1;
    pd[7]=-1;
    pd[8]=0;
    pd[9]=1;

• 这里创建数组使用 10001 ，导致空间复杂度非常不优秀，而如果使用 n+1 会导致触发当输入n为个位数时的数组越栈，改进的话对n为个位数的数据进行改进，这里谨给出个人打表想法，并没有试验：

    if(n<10)
    {
        switch(n)
        {
            case 0:return 0;
            case 1:return 0;
            case 2:return 1;
            case 3:return 1;
            case 4:return 1;
            case 5:return 2;
            case 6:return 3;
            case 7:return 3;
            case 8:return 3;
            case 9:return 4;
        }
    }
    int[] pd=new int[n+1];

代码

• 完整代码：（未对空间复杂度优化）

public class Solution {
    public int RotatedDigits(int n) {
        int[] pd=new int[10001];
        pd[0]=0;
        pd[1]=0;
        pd[2]=1;
        pd[3]=-1;
        pd[4]=-1;
        pd[5]=1;
        pd[6]=1;
        pd[7]=-1;
        pd[8]=0;
        pd[9]=1;
        for(int i=10;i<=n;i++)
        {
            int a=i/10;
            int b=i%10;
            if(pd[a]==-1)
            {
                pd[i]=-1;
            }
            
            if(pd[a]==1)
            {
                if(pd[b]==-1)
                {
                    pd[i]=-1;
                }
                if(pd[b]==1)
                {
                    pd[i]=1;
                }
                if(pd[b]==0)
                {
                    pd[i]=1;
                }
            }
            if(pd[a]==0)
            {
                if(pd[b]==-1)
                {
                    pd[i]=-1;
                }
                if(pd[b]==1)
                {
                    pd[i]=1;
                }
                if(pd[b]==0)
                {
                    pd[i]=0;
                }
            }
        }
        int sum=0;
        for(int i=0;i<=n;i++)
        {
            if(pd[i]==1)
            {
                sum++;
            }
        }
        return sum;
    }
}

复杂度分析：

• 时间复杂度为O（n）,只有遍历
• 空间复杂度为O（10001），直接创建dp为10001大小的数组