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

// 分裂问题一个数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 ^ 50n是long类型 r - l 50000l和r是int类型。importjava.util.ArrayList;importjava.util.HashMap;importjava.util.Map;importjava.util.Set;public class Code_SplitZeroOne{// n100// n100, 最终裂变的数组长度多少 // n50, 最终裂变的数组长度多少 // n25, 最终裂变的数组长度多少 //..// n1,.最终裂变的数组长度多少 // 请都填写到lenMap中去 public static long len(long n, HashMapLong, LonglenMap){if(n0||n1){lenMap.put(n,1L);return1;}long halflen(n/2,lenMap);long all(half1)1;lenMap.put(n, all);returnall;}// n100// n100, 最终裂变的数组中一共有几个1 // n50, 最终裂变的数组一共有几个1 // n25, 最终裂变的数组一共有几个1 //..// n1,.最终裂变的数组一共有几个1 // 请都填写到onesMap中去 public static long ones2(long num, HashMapLong, LongonesMap){if(num1||num0){onesMap.put(num, num);returnnum;}// n1long halfones2(num /2, onesMap);long midnum %21?1:0;long allhalf *2 mid;onesMap.put(num, all);returnall;}public static long ones(long n, HashMapLong, LongonesMap){if(n0||n1){onesMap.put(n,n);returnn;}int mid(n %2)1?1:0;long halfones(n/2,onesMap);long all(half1) mid;onesMap.put(n, all);returnall;}public static long nums3(long n, long l, long r){//HashMapLong, LongallMapnew HashMap();HashMapLong, LonglenMapnew HashMap();HashMapLong, LongoneMapnew HashMap();long lenlen(n,lenMap);long onesones(n,oneMap);returndp2(n,l,r,lenMap,oneMap);}public static long dp2(long n, long l, long r, HashMapLong,LonglenMap, HashMapLong,LongonesMap){long allLenlenMap.get(n);if(l1allLenr){returnonesMap.get(n);}long all0;int mid(n%21)?1:0;long halfLen(allLen-1)/2;if(lhalfLen1){alldp2(n/2,l,Math.min(r,halfLen),lenMap,onesMap);}if(rhalfLen1){alldp2(n/2,Math.max(l-halfLen-1,1),r-halfLen-1,lenMap,onesMap);}all((lhalfLen1||rhalfLen1)?0:mid);return all;}//为了测试//彻底生成n的最终分裂数组返回 public static ArrayListIntegertest(long n){ ArrayListIntegerarrnew ArrayList();process(n,arr);return arr;} public static void process(long n,ArrayListIntegerarr){ if(n1||n0){ 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(n1||n0){returnn1?1:0;}long halfsize(n /2);long leftlhalf ?0:nums1(n /2, l, Math.min(half, r));long mid(lhalf 1||rhalf 1)?0:(n1);long rightrhalf 1? nums1(n /2, Math.max(l - half -1,1), r - half -1):0;returnleft mid right;}public static long size(long n){if(n1||n0){return1;}else{long halfsize(n /2);return(half1)1;}}public static void main(String[]args){long num671;ArrayListIntegeranstest(num);int testTime10000;System.out.println(功能测试开始);for(int i0;itestTime;i){int a(int)(Math.random()* ans.size())1;int b(int)(Math.random()* ans.size())1;int lMath.min(a, b);int rMath.max(a, b);int ans10;for(int jl -1;jr;j){if(ans.get(j)1){ans1;}}long ans2nums1(num, l, r);long ans3nums3(num, l, r);if(ans1!ans2||ans1!ans3){System.out.println(出错了!);}}System.out.println(功能测试结束);System.out.println();System.out.println(性能测试开始);num(2L50) 22517998136L;long l30000L;long r800000200L;long start;long end;startSystem.currentTimeMillis();System.out.println(nums1结果 : nums1(num, l, r));endSystem.currentTimeMillis();System.out.println(nums1花费时间(毫秒) : (end - start));startSystem.currentTimeMillis();System.out.println(nums3结果 : nums3(num, l, r));endSystem.currentTimeMillis();System.out.println(nums3花费时间(毫秒) : (end - start));System.out.println(性能测试结束);System.out.println();System.out.println(单独展示nums2方法强悍程度测试开始);num(2L55) 22517998136L;l30000L;r6431000002000L;startSystem.currentTimeMillis();System.out.println(nums2结果 : nums3(num, l, r));//-1429513860endSystem.currentTimeMillis();System.out.println(nums2花费时间(毫秒) : (end - start));System.out.println(单独展示nums2方法强悍程度测试结束);}}