神奇数字的数量 DFS深度优先搜索

待我称王封你为后i 2022-06-08 00:19 75阅读 0赞

![这里写图片描述][SouthEast]

题意如上图，这个题主要就是如何判断一个数字是不是神奇数字，这个技术拆分出所有的位，然后DFS深度优先遍历判断。

代码如下：

import java.util.ArrayList;
    import java.util.List;
    
    public class Solution
    {
        
        /*
         * 神奇数字的判断
         * */
        boolean getCount(int num)
        {
            //小于10的肯定不是
            if(num<=10)
                return false;
    
            String numStr=""+num;
            int sum=0;
            List<Integer> list=new ArrayList<Integer>();
            for(int i=0;i<numStr.length();i++)
            {
                int oneBit=numStr.charAt(i)-'0';
                sum+=oneBit;
                list.add(oneBit);
            }
    
            //奇数肯定不是
            if(sum%2==1)
                return false;
    
            return isRes(list,sum/2,0,0);
        }
    
        /*
         * DFS神奇数字的判断
         * 就是选择当前数字和不选择当前数字的递归搜索
         * */
        private boolean isRes(List<Integer> list, int target, int index, int sum) 
        {
            if(sum>target)
                return false;
            else if(sum==target)
                return true;
    
            if(index==list.size())
                return sum==target;
            else 
            {
                //选择当前数组
                boolean add=isRes(list, target, index+1, sum+list.get(index));
                if(add==false)
                    return isRes(list, target, index+1, sum); //不选择
                else 
                    return true;
            }
        }
    
        //统计left到right的神奇数字的数量
        int getMagicNum(int left,int right)
        {
            int res=0;
            for(int i=left;i<=right;i++)
            {
                if(getCount(i))
                    res++;
            }
            return res;
        }
    
        public static void main(String[] args) 
        {
            Solution solution=new Solution();
            System.out.println(solution.getMagicNum(1, 50));
        }
    }

[SouthEast]: /images/20220608/9bede17e91104dd2921073c2383f0d9d.png