当前位置：首页 > news >正文

数据结构与算法-分裂问题,将数字分成0或1,求l到r之间有多少个1.

news 2026/5/12 15:24:40

// 分裂问题
一个数n，可以分裂成一个数组[n/2, n%2, n/2]，这个数组中哪个数不是1或者0，就继续分裂下去。
比如 n = 5，一开始分裂成[2, 1, 2]， [2, 1, 2]这个数组中不是1或者0的数，会继续分裂下去，比如两个2就继续分裂 [2, 1, 2] -> [1, 0, 1, 1, 1, 0, 1]，那么我们说，5最后分裂成[1, 0, 1, 1, 1, 0, 1]。每一个数都可以这么分裂，在最终分裂的数组中，假设下标从1开始给定三个数n、l、r，返回n的最终分裂数组里[l,r]范围上有几个1。 n <= 2 ^ 50，n是long类型， r - l <= 50000，l和r是int类型。

importjava.util.ArrayList;importjava.util.HashMap;importjava.util.Map;importjava.util.Set;public class Code_SplitZeroOne{// n=100// n=100, 最终裂变的数组，长度多少？ // n=50, 最终裂变的数组，长度多少？ // n=25, 最终裂变的数组，长度多少？ //..// n=1,.最终裂变的数组，长度多少？ // 请都填写到lenMap中去！ public static long len(long n, HashMap<Long, Long>lenMap){if(n==0||n==1){lenMap.put(n,1L);return1;}long half=len(n/2,lenMap);long all=(half<<1)+1;lenMap.put(n, all);returnall;}// n=100// n=100, 最终裂变的数组中，一共有几个1 // n=50, 最终裂变的数组，一共有几个1 // n=25, 最终裂变的数组，一共有几个1 //..// n=1,.最终裂变的数组，一共有几个1 // 请都填写到onesMap中去！ public static long ones2(long num, HashMap<Long, Long>onesMap){if(num==1||num==0){onesMap.put(num, num);returnnum;}// n>1long half=ones2(num /2, onesMap);long mid=num %2==1?1:0;long all=half *2+ mid;onesMap.put(num, all);returnall;}public static long ones(long n, HashMap<Long, Long>onesMap){if(n==0||n==1){onesMap.put(n,n);returnn;}int mid=(n %2)==1?1:0;long half=ones(n/2,onesMap);long all=(half<<1)+ mid;onesMap.put(n, all);returnall;}public static long nums3(long n, long l, long r){//HashMap<Long, Long>allMap=new HashMap<>();HashMap<Long, Long>lenMap=new HashMap<>();HashMap<Long, Long>oneMap=new HashMap<>();long len=len(n,lenMap);long ones=ones(n,oneMap);returndp2(n,l,r,lenMap,oneMap);}public static long dp2(long n, long l, long r, HashMap<Long,Long>lenMap, HashMap<Long,Long>onesMap){long allLen=lenMap.get(n);if(l<=1&&allLen<=r){returnonesMap.get(n);}long all=0;int mid=(n%2==1)?1:0;long halfLen=(allLen-1)/2;if(l<halfLen+1){all+=dp2(n/2,l,Math.min(r,halfLen),lenMap,onesMap);}if(r>halfLen+1){all+=dp2(n/2,Math.max(l-halfLen-1,1),r-halfLen-1,lenMap,onesMap);}all+=((l>halfLen+1||r<halfLen+1)?0:mid);return all;}//为了测试//彻底生成n的最终分裂数组返回 public static ArrayList<Integer>test(long n){ ArrayList<Integer>arr=new ArrayList<>();process(n,arr);return arr;} public static void process(long n,ArrayList<Integer>arr){ if(n==1||n==0){ arr.add((int)n);} else { process(n/2,arr);arr.add((int)(n%2));process(n /2, arr);}}public static long nums1(long n, long l, long r){if(n==1||n==0){returnn==1?1:0;}long half=size(n /2);long left=l>half ?0:nums1(n /2, l, Math.min(half, r));long mid=(l>half +1||r<half +1)?0:(n&1);long right=r>half +1? nums1(n /2, Math.max(l - half -1,1), r - half -1):0;returnleft + mid + right;}public static long size(long n){if(n==1||n==0){return1;}else{long half=size(n /2);return(half<<1)+1;}}public static void main(String[]args){long num=671;ArrayList<Integer>ans=test(num);int testTime=10000;System.out.println("功能测试开始");for(int i=0;i<testTime;i++){int a=(int)(Math.random()* ans.size())+1;int b=(int)(Math.random()* ans.size())+1;int l=Math.min(a, b);int r=Math.max(a, b);int ans1=0;for(int j=l -1;j<r;j++){if(ans.get(j)==1){ans1++;}}long ans2=nums1(num, l, r);long ans3=nums3(num, l, r);if(ans1!=ans2||ans1!=ans3){System.out.println("出错了!");}}System.out.println("功能测试结束");System.out.println("==============");System.out.println("性能测试开始");num=(2L<<50)+ 22517998136L;long l=30000L;long r=800000200L;long start;long end;start=System.currentTimeMillis();System.out.println("nums1结果 : "+ nums1(num, l, r));end=System.currentTimeMillis();System.out.println("nums1花费时间(毫秒) : "+(end - start));start=System.currentTimeMillis();System.out.println("nums3结果 : "+ nums3(num, l, r));end=System.currentTimeMillis();System.out.println("nums3花费时间(毫秒) : "+(end - start));System.out.println("性能测试结束");System.out.println("==============");System.out.println("单独展示nums2方法强悍程度测试开始");num=(2L<<55)+ 22517998136L;l=30000L;r=6431000002000L;start=System.currentTimeMillis();System.out.println("nums2结果 : "+ nums3(num, l, r));//-1429513860end=System.currentTimeMillis();System.out.println("nums2花费时间(毫秒) : "+(end - start));System.out.println("单独展示nums2方法强悍程度测试结束");}}