解决leetcode第4059题字典序最大的答案数组

4059.字典序最大的答案数组难度困难问题描述给你一个长度为n的整数数组nums。你可以重新排列其中的元素以形成任意排列perm。定义一个长度为15的数组power。对于每个0i15考查perm的前j个元素的第(14-i)位power[i]是满足这些位全为1的最大整数j其中0jn。二进制位的位置从右向左编号从第0位开始。返回可能得到的字典序最大的power数组。排列是数组中所有元素的一种重新排列。置位指的是数字在二进制表示中对应位的值为1。对于两个长度相同的数组如果在它们不同的第一个下标处数组a包含的元素大于数组b中的元素则称数组a的字典序大于数组b。示例1输入nums[7,5]输出[0,0,0,0,0,0,0,0,0,0,0,0,2,1,2]解释选择perm[7,5]。两个元素的第2位都置位了因此power[12]2。第一个元素的第1位置位了但第二个元素没有因此power[13]1。两个元素的第0位都置位了因此power[14]2。第一个元素的所有更高位都未置位因此其余项都为0。示例2输入nums[3,1,7]输出[0,0,0,0,0,0,0,0,0,0,0,0,1,2,3]解释选择perm[7,3,1]。第一个元素的第2位置位了但第二个元素没有因此power[12]1。前两个元素的第1位都置位了但第三个元素没有因此power[13]2。所有三个元素的第0位都置位了因此power[14]3。第一个元素的所有更高位都未置位因此其余项都为0。提示1nums.length5*10**40nums[i]2**15问题分析这个问题很难读懂必须结合后面的示例反复阅读才能够找到那么一丝丝的感觉因而越发显出它的不凡之处。其实要获得字典序最大的power数组关键在于perm这个看似是原数组nums的任意排列其实只能取nums的降序排列形式才能得到字典序最大的power数组。为此程序设计了三个函数来解决这一问题函数 int_change_to_15_binary(num)将一个num整数转化为15位的二进制字符串并返回函数 get_1_nums_of_index_i(binary_array_15,i)从一个由15位二进制字符串组成的数组中统计出各个二进制字符串的第i位是字符1的个数并返回函数get_power_array_from_perm(perm)则根据传入的经过降序处理的二进制字符串数组perm得到最终结果power数组并返回。主程序则先对输入的nums数组进行降序排序然后转化为15位进制字符串数组最后调用get_power_array_from_perm(perm)得到最终结果问题得以解决。程序如下#将一个整数num转化为15位二进制数并返回 def int_change_to_15_binary(num): numbin(num)[2:] nlen(num) num0*(15-n)num return num #检查一个由15位二进制数字符串所组成的数组第i位上1的个数并返回 def get_1_nums_of_index_i(binary_array_15,i): i_str.join([x[i] for x in binary_array_15]) return i_str.count(1) #从perm数组中统计并得出power数组返回 def get_power_array_from_perm(perm): power[] pr_array[] for i in perm: pr_array.append(int_change_to_15_binary(i)) for i in range(15): power.append(get_1_nums_of_index_i(pr_array,i)) return power #主程序 numseval(input(pls input nums)) nums.sort(reverseTrue) print(get_power_array_from_perm(nums))运行实例一pls input nums[5,10,30][0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 1]运行实例二pls input nums[3,1,7][0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3]