百度不收录网站文章,网页设计图片锚点链接怎么做html,书店网站模板,wordpress 汉语字体题目1
给定一个有正、有负、有0的数组arr#xff0c;
给定一个整数k#xff0c;
返回arr的子集是否能累加出k
1#xff09;正常怎么做#xff1f;
2#xff09;如果arr中的数值很大#xff0c;但是arr的长度不大#xff0c;怎么做#xff1f;
问题 1#xff09;…题目1
给定一个有正、有负、有0的数组arr
给定一个整数k
返回arr的子集是否能累加出k
1正常怎么做
2如果arr中的数值很大但是arr的长度不大怎么做
问题 1思路
如果数组中只有正数那么这就是一个普通的背包问题
递归函数用 process(i,j) 表示从0到i随便选能否选出累加和为j的数字。
在 process 内部可以选i或者不选i。
如果不选 i就看 process(i-1, j) 是否返回 true如果选 i就看 process(i-1, j-arr[i]) 是否返回 true
将递归转换成 dp就是dp[i][j]表示从0到i随便选能否选出累加和为j的数字。
dp 表的难点在于数组中有负数需要将下标做一个平移。
问题 2思路 我的思路是当 arr 数值很大的时候可以用 暴力递归 HashMap 来做缓存表这样只需要计算那些用得到的结果而不需要写满整个 arr 数据范围的结果。 左神的思路是假设 arr 的长度是 40用分治左边 20 个数用暴力算出所有可能的累加和2^201048576右边也得到 1048576 个结果。一般都是二分之后再整合你要分成三部分也可以但整合的时候就会复杂一些
如果单独用左部分或者单独用右部分就能够得到目标累加和的话直接返回就可以了。如果不行要考虑左右合并的情况。
题目2
给定一个正数数组arr
返回arr的子集“不能累加出的“最小正数
1正常怎么做
2如果arr中肯定有1这个值怎么做
问题 1思路
和题目 1 很像而且所有的数都是正数可以看成是一个普通的背包问题。
process(i,j) 表示从0到i随便选能否选出累加和为j的数字。
在 process 内部可以选i或者不选i。
如果不选 i就看 process(i-1, j) 是否返回 true如果选 i就看 process(i-1, j-arr[i]) 是否返回 true
最后从 j1 开始 j一直找到第一个 process(i, j) 返回为 false 的 j就是最终结果。
问题 2思路 其实 问题1的最优思路就是如果没有 1则返回答案 1。如果有 1则用下面的思路。 先排序排序后左边第 0 位置一定是 1。
定义变量 range1含义为从 1-range 范围上的正数都能累加出来。下面我们来分析 range 的扩充条件
如果 1 位置的数还是 1则 range 变成 2。
如果 2 位置的数是 2则 range 变成 4。
普遍的我来到 i 位置发现 arr[i]17range100代表从 0 到 i-1 位置能够得到 1~100 里的所有数由此可以推断加上 i 位置之后可以得到 1~117 所有的数。
普遍的我来到 i 位置发现 arr[i]101range100代表从 0 到 i-1 位置能够得到 1~100 里的所有数由此可以推断加上 i 位置之后可以得到 1~201 所有的数。
但普遍的我来到 i 位置发现 arr[i]102range100代表从 0 到 i-1 位置能够得到 1~100 里的所有数但以后怎么也得不到 101 了。
所以range 扩充的条件是
如果 arr[i] range1那么以后就再也得不到 range1 的累加和了直接返回 range1否则range 可以扩充为 range arr[i]
题目3
Leetcode原题
https://leetcode.com/problems/patching-array/
思路
我们先举一个极端的例子假设 nums 为空n1000我们想要生成从 1~1000 之间所有的数。
思路和题目2很像。用 range 表示当前能够得到的最大累加和。
首先我肯定需要 1这样就能得到 [1,1] 区间所有的数range 1。
然后我需要 2就可以得到 [1, 12] 区间所有的数range 3。
然后我需要 4就可以得到 [1, 34] 区间所有的数range 7。
然后我需要 8…
然后我们忘掉前面的例子举一个普遍的例子。
假设 nums[4, 5, 17, 39]n83
首先我们来看 nums 中的第一个数字 4我们要先能够得到 4 之前所有的数字所以根据前面的分析需要加入 1,2得到 range7
在此基础上来到 nums 中的第二个数字 5更新range为 7512
在此基础上来到 nums 中的第三个数字 17不能直接更新 range需要想办法得到 13 14 15 16。所以需要加入 range1 13并且更新 range 为 121325。然后用 17 更新 range251742
在此基础上来到 nums 中的第四个数字39更新range为423981
整个数组遍历结束了而最终目标83还有距离所以需要再补一个range182就能得到1~83范围内所有的数字。
题目4
给定整数power给定一个数组arr给定一个数组reverse含义如下
arr的长度一定是2的power次方
reverse中的每个值一定都在0~power范围。
例如power 2, arr {3, 1, 4, 2}reverse {0, 1, 0, 2}
任何一个在前的数字可以和任何一个在后的数组构成一对数
可能是升序关系、相等关系或者降序关系
比如arr开始时有如下的降序对(3,1)、(3,2)、(4,2)一共3个
接下来根据reverse对arr进行调整
reverse[0] 0, 表示在arr中划分每1(2的0次方)个数一组然后每个小组内部逆序那么arr变成[3,1,4,2]此时有3个逆序对
reverse[1] 1, 表示在arr中划分每2(2的1次方)个数一组然后每个小组内部逆序那么arr变成[1,3,2,4]此时有1个逆序对
reverse[2] 0, 表示在arr中划分每1(2的0次方)个数一组然后每个小组内部逆序那么arr变成[1,3,2,4]此时有1个逆序对
reverse[3] 2, 表示在arr中划分每4(2的2次方)个数一组然后每个小组内部逆序那么arr变成[4,2,3,1]此时有4个逆序对
所以返回[3,1,1,4]表示每次调整之后的逆序对数量
输入数据状况
power的范围[0,20]
arr长度范围[1,10的7次方]
reverse长度范围[1,10的6次方]
思路
假设我们有 8 个数arr [2 1 7 5 3 4 6 8]
当以 2 个数为一组的时候我们假设每个组内逆序对的个数之和是 a正序对个数之和是 b
注意每一个组内的逆序对第一个数要来自组内左侧第二个数要来自组内右侧。
这样在每个组中逆序对相加求总的逆序对数量的时候才不会重复计算。2个一组的时候[2 | 1] [7 | 5] [3 | 4] [6 | 8]
其中正序对包括 (3,4),(6,8)正序对个数为2.
其中逆序对包括 (2,1),(7,5)逆序对个数为2.4个一组的时候[2 1 | 7 5][3 4 | 6 8]
其中正序对包括 (2,7),(2,5),(1,7),(1,5),(3,6),(3,8),(4,6),(4,8)正序对个数为8.
其中逆序对没有逆序对个数为08个一组的时候[2 1 7 5 | 3 4 6 8]
其中正序对包括 (2,3),(2,4),(2,6),(2,8),(1,3),(1,4),(1,6),(1,8),(7,8),(5,6),(5,8),正序对个数为11.
其中逆序对包括 (7,3),(7,4),(7,6),(5,3),(5,4),逆序对个数为5
同样的我们假设 42的2次方个一组的时候逆序对的个数为 c正序对个数之和是 d.
同样的我们假设 82的3次方个一组的时候逆序对的个数为 e正序对个数之和是 f.
我们把上面的假设总结成表格
几个数一组逆序对的个数正序对的个数22的1次方ab42的2次方cd82的3次方ef
当我们将“ 42的2次方个数字组成的小组”内部逆序的时候它只影响“22的1次方个数字一组”的小组和“42的2次方个数字一组的小组”不会影响“82的3次方一组的小组”。逆序后表格变成如下
几个数一组逆序对的个数正序对的个数22的1次方b左右交换a左右交换42的2次方d左右交换c左右交换82的3次方e不变f不变
普遍的当我们要逆序“2的n次方个数字组成的小组”的时候表格中“2的n次方一组的小组”这一行下面的所有小组都不会被影响。这一行上面的所有小组包括自身正序对个数和逆序对个数发生交换。
这样每一次组内做逆序的时候就可以非常快速的计算逆序之后的逆序对数量。
那么怎么拥有一开始的表格信息用归并排序来算。去看体系学习班第4节和第5节是和merge sort有关的题目。
题目5
约瑟夫环问题
给定一个链表头节点head和一个正数m
从头开始每次数到m就杀死当前节点
然后被杀节点的下一个节点从1开始重新数
周而复始直到只剩一个节点返回最后的节点
Leetcode :
https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
